无人机实心圆

AdvancesinAppliedMathematics应用数学进展,2019,8(8),1457-1462PublishedOnlineAugust2019inHans.
http://www.
hanspub.
org/journal/aamhttps://doi.
org/10.
12677/aam.
2019.
88170文章引用:徐迅,管玉洁,黄雅娟,吴烨.
一种无人机覆盖路径规划问题的算法[J].
应用数学进展,2019,8(8):1457-1462.
DOI:10.
12677/aam.
2019.
88170AnAlgorithmforCoveragePathPlanningwithUnmannedAerialVehiclesXunXu*,YujieGuan,YajuanHuang,YeWuSchoolofMathematicsandStatistics,ChangshaUniversityofScienceandTechnology,ChangshaHunanReceived:Aug.
1st,2019;accepted:Aug.
15th,2019;published:Aug.
22nd,2019AbstractTheapplicationofUnmannedAerialVehiclesinroadmonitoringofdisasteremergencyrescuesystemwhichenablesrescueorganizationstoobtainroadnetworkconditionsintimeprovidesmoreaccurategroundinformationandimprovesrescueefficiency.
Monitoringroadbyunmannedaerialvehiclesneedstopathplanningaccordingtothecharacteristicsofremotesensingimagingandtimeisanimportantindexofdisasteremergencyrescuesystemdesign.
Inordertospeedupthesolutionoftrackplanning,asetcoveragemodelisestablishedconsideringthecharacteristicsofroadmonitoringindisasteremergencyrescuesystem.
Athree-stagealgorithmisproposedtodecoupletheproblemintotwosubproblems.
Finally,aconcreteexampleisgiventoverifythefea-sibilityofthealgorithm.
KeywordsRoadMonitoring,PathPlanning,IntegerProgramming,LocationSetCoveringProblem,TravellingSalesmanProblem一种无人机覆盖路径规划问题的算法徐迅*,管玉洁,黄雅娟,吴烨长沙理工大学数学与统计学院,湖南长沙收稿日期:2019年8月1日;录用日期:2019年8月15日;发布日期:2019年8月22日摘要无人机应用于灾害应急救援系统的道路监控,使得救援组织能及时获得道路网络状况,提供更高精度的地面信息,提升救援效率.
无人机监控道路需要根据遥感成像的特点规划航迹,而时间是灾害应急救援*第一作者.
徐迅等DOI:10.
12677/aam.
2019.
881701458应用数学进展系统设计的重要指标.
为了加快航迹规划的求解速度,考虑灾害应急救援系统的道路监控问题的特点,建立了集合覆盖模型.
提出将该问题解耦成两个子问题的三阶段算法,根据约束条件推导出可行域,缩短了算法的搜索时间.
最后通过一个具体算例验证了算法的可行性.
关键词道路监控,航迹规划,整数规划,位置集合覆盖问题,旅行商问题Copyright2019byauthor(s)andHansPublishersInc.
ThisworkislicensedundertheCreativeCommonsAttributionInternationalLicense(CCBY).
http://creativecommons.
org/licenses/by/4.
0/1.
引言我国地域广阔,地理条件复杂,自然灾害时有发生.
自然灾害对国民经济和人民安全造成的影响日益严重,自然灾害不但破坏建筑,造成道路损毁,还带来通信的中断,这使得救援困难,医疗物资不能及时到位,从而导致不必要的伤亡[1].
而虽然自然灾害是无法避免的,但通过一个全面和高效率的灾害管理系统,可以大大减轻其影响:时间是灾害管理成功的最重要因素[2],而无人机(UnmannedAerialVehicle,UAV)不受地形限制,道路限制,具有低成本、低损耗、可重复使用且风险小等诸多优势[3],可以在第一时间将食品,饮用水,医疗药品等救援物资送达指定区域,并且可以搭载数码设备,实施对地观测,为救援人员提供道路受损信息.
无人机的航迹规划是指在适当的时间内找到满足约束条件的一条可行最优的路径.
但是由于路径规划是一个NP-Hard问题,当问题规模过大时,算法很难在短时间内找到最优的路径,所以在求解大规模航迹规划时,通常采用搜索算法,启发式算法,神经网络等方法[4][5][6]求得"尽可能好"的解.
文献[7]以最小化无人机巡视环路的飞行时间为路径规划的目标,讨论了具有遥感能力的无人机的路径规划.
文献[8]将巡检的路径规划问题制定为扩展的旅行商问题(Travellingsalesmanproblem,TSP).
文献[9]提出了几种在搜救系统中无人机离散路径规划的方法.
文献[10]以最小化航线数量为目标提出了新的算法.
文献[11]提出了基于旋转卡尺的算法解决起降点在路径中的覆盖路径规划问题.
文献[12]分析了现有文献中关于覆盖路径规划问题,还介绍了通常用于评估覆盖任务成功与否的性能指标.
目前关于二,三维航迹规划研究大多是研究点到点的航迹规划,即研究出发点与目标点间的最优航迹.
而当灾害发生时,使用无人机对目标道路网络进行遥感成像,收集道路受损信息要求的是以航迹上的每个点为圆心,拍摄半径为半径的圆的集合覆盖整个道路区域.
2.
问题描述及模型分析自然灾害发生后,道路被损坏的同时,通信线路也常常被破坏.
我们需要n架续航能力为LE(Long-Endurance)的无人机完成对某一道路网络的监控覆盖,为救援人员提供道路状况信息.
记道路网络为区域(){},,RoadRoadRoadRoadRoadGxyzG=∈,无人机的理想可视半径为r0(不考虑遮挡的情况下,实际可视范围与无人机和地面的相对高度差h成正比,这里设在理想相对高度差0h的可视半径为理想可视半径r0),每t秒拍摄一张照片(视频也可看作是照片的集合,例如帧率为60fps的视频可是视作每1/60秒拍摄一张照片),航迹为由方程(),,0,1,2,iFxyzin==确定的空间曲线Fi.
则第i架无人机沿着曲线Fi的监控区域,iFMonitorG可表示为OpenAccess徐迅等DOI:10.
12677/aam.
2019.
881701459应用数学进展222,0,,0,00,,,10iiroadFMonitoriiijijijijzzGxyzxxyyrxyzFh∞=∪.
则总的监控区域,1inMonitorFMonitorjGG==∪,综上所述,本文所研究的航迹规划问题可描述为:从所有满足,1inFMonitorRoadiGG=∪的F曲线中找到n条最优的空间曲线Fi.
目前一般的三维航迹规划问题解决的是点到点的路径优化,其搜索空间为(){}minmaxminmaxminmax0,,,,generalGxyzxxxyyyzzzhλ其中minmaxminmaxminmaxxxyyzz分别表示待监控道路区域的经度,纬度和海拔的最小值和最大值,0hλ是满足拍摄分辨率的最大相对高度.
然而由,11inRoadFMonitorkikGGFG∞===∪∪知对于(),,RoadRoadRoadRoadxyzG∈,有(),,RoadRoadRoadxyzG∈,即222,00ijRoadijijijiRoadijRoadijzzxyzFstxxyyrh()2220,,0,,RoadRoadRoadRoadRoadRoadRoadgeneralxyzGzzGxyzxxyyrGh∈∴∪()2220,,0,,RoadRoadRoadRoadCRoadgeneralRoadRoadxyzGzzGGGxyzxxyyrh=∪所以,本文提出的初始可行域G比一般的搜索空间Ggeneral要小.
当地形起伏不大时,无人机的相对高度变化不大,可视半径的变化可忽略不计,可视半径可看作常数,本文将三维航迹规划问题转化为二维航迹规划问题以简化计算量,从而快速获得一个较好的解.
3.
近似算法研究为解决基于无人机的道路监控的二维航迹规划问题,我们采用栅格法进行空间的划分.
将空间离散化为mgrid行ngrid列的矩形单元后,道路监控的二维航迹规划问题即变为寻找一系列相邻的单元,使得以这些单元的中心为圆心,可视半径为圆的半径的实心圆覆盖道路所在的单元.
传统的算法解决点到点之间的航迹规划使用的方法是采用网格划分规划空间后,构造以当前节点为中心的九宫图作为算法的数据结构,共有8个相邻节点,航迹由相邻网格节点连接形成,并连接起始节点和目标节点.
此算法的时间复杂度大于gridgridgridmmnC+.
可见此方法的计算量十分巨大.
因此我们提出以下三阶段算法:第一阶段:首先求出_mincircle.
当问题规模较小时,以道路所在单元中心为圆心画圆确定G,将1GG=所在的单元视为位置集合覆盖问题(LocationSetCoveringProblem,LSCP)中的候选拍摄点,建立整数规划模型.
使用分支定界法求解得到目标函数的最小值_mincircle.
当问题规模较大时,使用二分法确定覆盖整个道路网络所需实心圆的最少数目_mincircle,_mincircle的初始搜索区间[]_,_circleleftcircleright,其中2_πroadScircleleftr=,_2roadLcirclerightr=,roadS是道路面积,roadL是道路长度,r是无人机的可视半径.
徐迅等DOI:10.
12677/aam.
2019.
881701460应用数学进展第二阶段:记"每一个含有_mincircle个单元的集合"为一个方案,若由_mincircle个单元中心为圆心的实心圆集合能覆盖整个道路网络.
显然当无人机的航迹经过方案中_mincircle个单元的中心时,无人机能完成道路监控任务.
定义不同单元间中心的距离为两个单元间的边的权重,记录下此方案的总权重.
比较不同方案的总权重,使用启发式算法寻找总权重较小的方案或者遍历得到总权重最小的方案;第三阶段最后将总权重较小的方案中的_mincircle个单元中心坐标看作旅行商问题的城市坐标,求解该旅行商问题.
三阶段算法的时间复杂度主要在第一阶段求解整数规划模型,确定s种有_mincircle个候选拍摄点的方案,算法步骤:STEP1:对区域Ggeneral使用栅格法进行空间的划分,以道路所在单元中心为圆心画圆确定G,将1GG=所在的单元视为LSCP问题中的候选拍摄点,建立整数规划模型.
使用分支定界法求解,并确定_mincircle.
STEP2:检查STEP1中求出的_mincircle个拍摄点,若存在两点之间的距离小于UAVsvt=,(UAVv为无人机的速度,s为无人机拍摄两张照片所需的最小飞行间距,在一般情况下,如果1,iiLL+两点间的距离小于s,可以降低无人机的速度,使得无人机从iL飞到1iL+时,相机能够拍照,但是降低速度无疑会使完成任务的时间变长,而灾害救援系统有时间限制),则从1G删去处于更"稠密"区域的那点.
返回到STEP1重新计算.
如果所有点的距离均不小于s,则计算当前方案的总权重,执行STEP3.
STEP3:使用启发式算法求解出满足预定精度的方案或使用遍历算法得到最优方案.
STEP4:求解出访问STEP3中求出的最优方案中_mincircle个单元的先后顺序.
4.
算例研究如图1所示,本文将空间划分为16*16个正方形单元,单元的边长记为一个单位长度,黄色单元为道路.
无人机可视半径设置为3个单位长度,即3r=.
第一阶段求解得到_min4circle=.
第二,三阶段使用遍历算法求解,结果如图2,黄色与白色区域为初始可行域G.
红色空心圆所在的第87号,第105号,第151号和第155号单元是总权重最小的方案的四个单元.
由151号单元到87号单元再到105号单元最后到155号单元即为最终航迹.
值得注意的是,本文并未预设无人机的起飞点,但这并不影响算法的有效性,为了符合生活实际,只需要在第三阶段的算法中添加一个起飞点的坐标,即可得到实际问题的解决方案.
Figure1.
Rasterizedroadnetwork图1.
栅格化后的道路网络徐迅等DOI:10.
12677/aam.
2019.
881701461应用数学进展Figure2.
Thesolutionresultofpath图2.
航迹的求解结果5.
结束语时间是灾害应急救援系统中的重要因素,受灾地区的救援物资运送受到道路的影响,使用无人机遥感成像可以快速提供道路受损状况,并弥补卫星遥感成像精度不足的问题.
本文将灾害应急救援系统中无人机道路监控航迹规划问题解耦为LSCP问题和TSP问题,给出了覆盖整个道路网络所需实心圆的数目的大致范围[]_,_circleleftcircleright与一种能够减少模型求解时间的三阶段算法.
基金项目长沙理工大学大学生创新训练计划立项项目(无人机救灾响应系统开发).
参考文献[1]夏威.
交通道路灾害监测与应急响应系统的研究[J].
通讯世界,2015(17):245-247.
[2]Luo,C.
,Miao,W.
,Ullah,H.
,etal.
(2019)UnmannedAerialVehiclesforDisasterManagement.
In:Durrani,T.
S.
,Wang,W.
andForbes,S.
M.
,Eds.
,GeologicalDisasterMonitoringBasedonSensorNetworks,Springer,Berlin,83-107.
https://doi.
org/10.
1007/978-981-13-0992-2_7[3]金伟,葛宏立,杜华强,等.
无人机遥感发展与应用概况[J].
遥感信息,2009(1):88-92.
[4]巴海涛.
无人机航迹规划研究[D]:[硕士学位论文].
西安:西北工业大学,2006.
[5]郑昌文,严平,丁明跃,等.
飞行器航迹规划研究现状与趋势[J].
宇航学报,2007(6):1441-1446.
[6]胡中华.
基于智能优化算法的无人机航迹规划若干关键技术研究[D]:[博士学位论文].
南京:南京航空航天大学,2011.
[7]Jang,D.
S.
,Chae,H.
J.
andChoi,H.
L.
(2017)OptimalControl-BasedUAVPathPlanningwithDynamical-ly-ConstrainedTSPwithNeighborhoods.
17thInternationalConferenceonControl,AutomationandSystems,RamadaPlaza,18-21October2017,373-378.
https://doi.
org/10.
23919/ICCAS.
2017.
8204468[8]Jeong,S.
,Simeone,O.
andKang,J.
(2017)MobileEdgeComputingviaaUAV-MountedCloudlet:OptimizationofBitAllocationandPathPlanning.
IEEETransactionsonVehicularTechnology,67,2049-2063.
https://doi.
org/10.
1109/TVT.
2017.
2706308[9]SanJuan,V.
,Santos,M.
andAndújar,J.
M.
(2018)IntelligentUAVMapGenerationandDiscretePathPlanningforSearchandRescueOperations.
Complexity,2018,ArticleID:6879419.
https://doi.
org/10.
1155/2018/6879419徐迅等DOI:10.
12677/aam.
2019.
881701462应用数学进展[10]Torres,M.
,Pelta,D.
A.
,Verdegay,J.
L.
,etal.
(2016)CoveragePathPlanningwithUnmannedAerialVehiclesfor3DTerrainReconstruction.
ExpertSystemswithApplications,55,441-451.
https://doi.
org/10.
1016/j.
eswa.
2016.
02.
007[11]Gomez,J.
I.
V.
,Melchor,M.
M.
andLozada,J.
C.
H.
(2017)OptimalCoveragePathPlanningBasedontheRotatingCa-lipersAlgorithm.
InternationalConferenceonMechatronics,ElectronicsandAutomotiveEngineering,Cuernavaca,21-24November2017,140-144.
https://doi.
org/10.
1109/ICMEAE.
2017.
11[12]Cabreira,T.
,Brisolara,L.
andFerreira,P.
R.
(2019)SurveyonCoveragePathPlanningwithUnmannedAerialVe-hicles.
Drones,3,4.
https://doi.
org/10.
3390/drones3010004知网检索的两种方式:1.
打开知网首页:http://cnki.
net/,点击页面中"外文资源总库CNKISCHOLAR",跳转至:http://scholar.
cnki.
net/new,搜索框内直接输入文章标题,即可查询;或点击"高级检索",下拉列表框选择:[ISSN],输入期刊ISSN:2324-7991,即可查询.
2.
通过知网首页http://cnki.
net/顶部"旧版入口"进入知网旧版:http://www.
cnki.
net/old/,左侧选择"国际文献总库"进入,搜索框直接输入文章标题,即可查询.
投稿请点击:http://www.
hanspub.
org/Submission.
aspx期刊邮箱:aam@hanspub.
org