留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种利用双侧凸包扩张模型的路径快速规划算法

李改肖 吕程 彭认灿 董箭

李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
引用本文: 李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
LI Gaixiao, LÜ Cheng, PENG Rencan, DONG Jian. A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
Citation: LI Gaixiao, LÜ Cheng, PENG Rencan, DONG Jian. A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469

一种利用双侧凸包扩张模型的路径快速规划算法

doi: 10.13203/j.whugis20180469
基金项目: 

国家重点研发计划 2017YFC1405505

国家自然科学基金 41601498

详细信息
    作者简介:

    李改肖,博士,教授,主要从事海图制图理论与方法研究。lgxlndl@126.com

    通讯作者: 吕程,硕士,助理工程师。c191340844@qq.com
  • 中图分类号: P208

A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model

Funds: 

The National Key Research and Development Program of China 2017YFC1405505

the National Natural Science Foundation of China 41601498

More Information
    Author Bio:

    LI Gaixiao, PhD, professor, specializes in the theories and methods of Charting. E-mail: lgxlndl@126.com

    Corresponding author: LÜ Cheng, master, assistant engineer. E-mail: c191340844@qq.com
  • 摘要: 针对障碍环境中路径规划存在的运算效率低、最短路径遗失问题,根据凸包边界在构建空间网络模型过程中具有快速高效的特点,结合路径与障碍物的相对位置关系,提出了一种基于双侧凸包扩张模型的路径快速规划算法。该算法在对凸包边界算法进行改进的基础上,提取左右侧关联障碍物的凸包边界作为网络模型,利用最短路径算法搜寻目标路径,并在ArcGIS Engine环境对密集不规则障碍物进行了仿真实验。实验结果表明,与凸包边界算法和航路二叉树算法相比,所提出的算法具有构建空间网络模型效率高、实际最短路径不丢失等优点。
  • 图  1  凸包边界算法运算结果

    Figure  1.  Operation Result of Boundary of Convex-Hull Algorithm

    图  2  本文算法原理示意图

    Figure  2.  Schematic Diagram of Our Proposed Algorithm

    图  3  本文算法流程图

    Figure  3.  Flowchart of Our Proposed Algorithm

    图  4  障碍物及3组起终点

    Figure  4.  Obstacles and Three Groups of Start and End Points

    图  5  3种算法实验结果

    Figure  5.  Experimental Results of Three Algorithms

    图  6  构建空间网络模型耗时趋势

    Figure  6.  Time Consuming Trend of Constructing Spatial Network Model

    表  1  路径数量

    Table  1.   Number of Paths

    算法 路径数/条
    实验1 实验2 实验3
    凸包边界算法 37 63 19
    航路二叉树算法 92 110 45
    本文算法 72 95 28
    下载: 导出CSV

    表  2  空间网络模型构建耗时/ms

    Table  2.   Time Consumption of Constructing Spatial Network Model/ms

    算法 耗时
    实验1 实验2 实验3
    凸包边界算法 432 540 293
    航路二叉树算法 2 605 2 361 681
    本文算法 1 309 1 295 424
    下载: 导出CSV
  • 王连锋, 宋建社, 王正元, 等.带硬时间窗的战场物资配送车辆路径优化[J].系统工程与电子技术, 2013, 35(4):770-776 doi:  10.3969/j.issn.1001-506X.2013.04.15

    [1] Wang Lianfeng, Song Jianshe, Wang Zhengyuan, et al. Vehicle Routing Optimization with Hard Time Windows in Battlefield Resources Distribution[J]. Systems Engineering and Electronics, 2013, 35(4):770-776 doi:  10.3969/j.issn.1001-506X.2013.04.15
    [2] 李周清, 马祖军.区际救援物资中转调度的多目标优化问题研究[J].计算机工程与应用, 2010, 46(12):28-31 doi:  10.3778/j.issn.1002-8331.2010.12.008

    Li Zhouqing, Ma Zujun. Multi-objective Optimization Problem in Transshipment Scheduling of Inter-regional Relief Materials[J]. Computer Engineering and Applications, 2010, 46(12):28-31 doi:  10.3778/j.issn.1002-8331.2010.12.008
    [3] 李沛, 段海滨.基于改进万有引力搜索算法的无人机航路规划[J].中国科学:技术科学, 2012(10):1 130-1 136 https://www.cnki.com.cn/Article/CJFDTOTAL-JEXK201210005.htm

    Li Pei, Duan Haibin. Path Planning of Unmanned Aerial Vehicle Based on Improved Gravitational Search Algorithm[J]. Science China: Technological Sciences, 2012(10):1 130-1 136 https://www.cnki.com.cn/Article/CJFDTOTAL-JEXK201210005.htm
    [4] 张启瑞, 魏瑞轩, 何仁珂, 等.城市密集不规则障碍空间无人机航路规划[J].控制理论与应用, 2015, 32(10):1 407-1 413 doi:  10.7641/CTA.2015.50351

    Zhang Qirui, Wei Ruixuan, He Renke, et al. Path Planning for Unmanned Aerial Vehicle in Urban Space Crowded with Irregular Obstacles[J]. Control Theory and Applications, 2015, 32(10):1 407-1 413 doi:  10.7641/CTA.2015.50351
    [5] Kala R, Shukla A, Tiwari R. Robot Path Planning Using Dynamic Programming with Accelerating Nodes[J]. Journal of Behavioral Robotics, 2012, 3(1):002E
    [6] 吴博, 文元桥, 吴贝, 等.水面无人艇避碰方法回顾与展望[J].武汉理工大学学报(交通科学与工程版), 2016, 40(3):456-461 doi:  10.3963/j.issn.2095-3844.2016.03.013

    Wu Bo, Wen Yuanqiao, Wu Bei, et al. Review and Expectation on Collision Avoidance Method of Unmanned Surface Vessel[J]. Journal of Wuhan University of Technology(Transportation Science & Engineering), 2016, 40(3):456-461 doi:  10.3963/j.issn.2095-3844.2016.03.013
    [7] 余必秀, 初秀民, 柳晨光, 等.基于改进A*算法的无人航道测量船路径规划方法[J].武汉大学学报·信息科学版, 2019, 44(8):1 258-1 264 doi:  10.13203/j.whugis20170239

    Yu Bixiu, Chu Xiumin, Liu Chenguang, et al. A Path Planning Method for Unmanned Waterway Survey Ships Based on Improved A* Algorithm[J]. Geomatics and Information Science of Wuhan University, 2019, 44(8):1 258-1 264 doi:  10.13203/j.whugis20170239
    [8] Roberge V, Tarbouchi M, Labonte G. Comparison of Parallel Genetic Algorithm and Particle Swarm Optimization for Real-Time UAV Path Planning[J]. IEEE Transactions on Industrial Informatics, 2013, 9(1):132-141 doi:  10.1109/TII.2012.2198665
    [9] 占伟伟, 王伟, 陈能成, 等.一种利用改进A*算法的无人机航迹规划[J].武汉大学学报·信息科学版, 2015, 40(3):315-320 http://ch.whu.edu.cn/article/id/3203

    Zhan Weiwei, Wang Wei, Chen Nengcheng, et al. Path Planning Strategies for UAV Based on Improved A* Algorithm[J]. Geomatics and Information Science of Wuhan University, 2015, 40(3):315-320 http://ch.whu.edu.cn/article/id/3203
    [10] Rui N S, George A. An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation[J]. Frontiers in Artificial Intelligence and Applications, 2014, 262:314-322
    [11] 韩李涛, 郭欢, 张海思.一种多出口室内应急疏散路径规划算法[J].测绘科学, 2018, 43(12):105-110 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201812018.htm

    Han Litao, Guo Huan, Zhang Haisi. An Algorithm for Route Planning Applied in Multi-exit Indoor Emergency Evacuation[J]. Science of Surveying and Mapping, 2018, 43(12):105-110 https://www.cnki.com.cn/Article/CJFDTOTAL-CHKD201812018.htm
    [12] Asghar A, Amir S. Speeding up the Floyd–Warshall Algorithm for the Cycled Shortest Path Problem[J]. Applied Mathematics Letters, 2011, 25(1):1-5
    [13] 石为人, 王楷.基于Floyd算法的移动机器人最短路径规划研究[J].仪器仪表学报, 2009, 30(10):2 088-2 092 https://www.cnki.com.cn/Article/CJFDTOTAL-YQXB200910014.htm

    Shi Weiren, Wang Kai. Floyd Algorithm for the Shortest Path Planning of Mobile Robot[J]. Chinese Journal of Scientific Instrument, 2009, 30(10): 2 088-2 092 https://www.cnki.com.cn/Article/CJFDTOTAL-YQXB200910014.htm
    [14] Sudhakara P, Ganapathy V, Sudhakara P, et al. Path Planning of a Mobile Robot Using Amended A-Star Algorithm[J]. International Journal of Control Theory and Applications, 2016, 9(37):489-502
    [15] 陈若男, 文聪聪, 彭玲, 等.改进A*算法及其在室内机器人路径规划中的应用[J/OL].计算机应用, 2019, 39(4):78-83 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201904013.htm

    Chen Ruonan, Wen Congcong, Peng Ling, et al. Improved A* Algorithm and Apply to Indoor Path Planning for Mobile Robots[J]. Journal of Computer Applications, 2019, 39(4):78-83 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY201904013.htm
    [16] Frantisek D, Andrej B. Path Planning with Modified A Star Algorithm for a Mobile Robot[J]. Procardia Engineering, 2014, 96(1):59-69
    [17] 魏瑞轩, 许卓凡, 王树磊, 等.基于Laguerre图的自优化A-Star无人机航路规划算法[J].系统工程与电子技术, 2015, 37(3):577-582 https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD201503017.htm

    Wei Ruixuan, Xu Zhuofan, Wang Shulei, et al. Self-optimization A-Star Algorithm for UAV Path Planning Based on Laguerre Diagram[J]. Systems Engineering and Electronics, 2015, 37(3):577-582 https://www.cnki.com.cn/Article/CJFDTOTAL-XTYD201503017.htm
    [18] 胡晓敏, 梁天毅, 王明丰, 等.新型树启发式搜索算法的机器人路径规划[J].计算机工程与应用, 2020, 56(11):164-171 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202011025.htm

    Hu Xiaomin, Liang Tianyi, Wang Mingfeng, et al. Novel Tree Heuristic Search Algorithm for Robot Path Planning[J]. Computer Engineering and Applications, 2020, 56(11):164-171 https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG202011025.htm
    [19] 顾尚定, 周春辉, 文元桥, 等.基于拓扑位置关系的无人艇路径搜索方法[J].中国航海, 2019, 42(2):52-58 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201902011.htm

    Gu Shangding, Zhou Chunhui, Wen Yuanqiao, et al. Path Search of Unmanned Surface Vehicle Based on Topological Location[J]. Navigation of China, 2019, 42(2):52-58 https://www.cnki.com.cn/Article/CJFDTOTAL-ZGHH201902011.htm
    [20] 刘亚杰, 王航宇, 谢君.狭窄环境中基于几何法的全局路径规划新方法[J].海军工程大学学报, 2010, 22(4):82-86 https://www.cnki.com.cn/Article/CJFDTOTAL-HJGX201004017.htm

    Liu Yajie, Wang Hangyu, Xie Jun. A New Global Path Planning Method Based on Geometry Algorithm in a Narrow Environment[J]. Journal of Naval University of Engineering, 2010, 22(4):82-86 https://www.cnki.com.cn/Article/CJFDTOTAL-HJGX201004017.htm
    [21] 张立华.基于电子海图的航线自动生成理论与方法[M].北京:科学出版社, 2011

    Zhang Lihua.Theory and Method of Automatic Route Generation Based on Electronic Chart[M]. Beijing: Science Press, 2011
    [22] 刘亚杰, 李忠猛, 陈晓山.考虑空间约束的机库舰载机调运路径规划方法[J].海军工程大学学报, 2014, 38(3):100-103 https://www.cnki.com.cn/Article/CJFDTOTAL-HJGX201403021.htm

    Liu Yajie, Li Zhongmeng, Chen Xiaoshan. Path Planning for Transferring Shipborne Aircraft Restricted to Hangar Space[J]. Journal of Naval University of Engineering, 2014, 38(3):100-103 https://www.cnki.com.cn/Article/CJFDTOTAL-HJGX201403021.htm
    [23] 刘亚杰, 李忠猛, 谢君.基于改进遗传算法的舰载机出库调度优化方法[J].火力与指挥控制, 2015, 29(6):57-60 doi:  10.3969/j.issn.1002-0640.2015.06.014

    Liu Yajie, Li Zhongmeng, Xie Jun. Optimized Method of Carrier-borne Aircrafts ExportingScheduling Based on Improved Genetic Algorithm[J]. Fire Control and Command Control, 2015, 29(6):57-60 doi:  10.3969/j.issn.1002-0640.2015.06.014
    [24] 汤国安.地理信息系统[M].北京:科学出版社, 2010

    Tang Guoan. Geographic Information System[M]. Beijing: Science Press, 2010
    [25] De Berg M.计算几何:算法与应用[M].北京:清华大学出版社, 2005

    De Berg M. Computational Geometry: Algorithm and Application[M]. Beijing: Tsinghua University Press, 2005
  • [1] 徐丰, 牛继强, 林昊, 陈时雨, 张兵兵, 陈飞燕.  利用等距同构建立多尺度空间实体相似性度量模型 . 武汉大学学报 ● 信息科学版, 2019, 44(9): 1399-1406. doi: 10.13203/j.whugis20170344
    [2] 汤青慧, 唐旭, 崔晓晖, 胡石元, 刘耀林.  基于动态通达网络模型的最优航程规划方法 . 武汉大学学报 ● 信息科学版, 2015, 40(4): 521-528. doi: 10.13203/j.whugis20140387
    [3] 李清泉, 胡波, 乐阳.  一种基于约束的最短路径低频浮动车数据地图匹配算法 . 武汉大学学报 ● 信息科学版, 2013, 38(7): 805-808.
    [4] 孙伟伟, 刘春, 施蓓琦, 李巍岳.  利用偏最小二乘方法修复高光谱影像等距映射降维中遗失点的坐标 . 武汉大学学报 ● 信息科学版, 2012, 37(5): 550-554.
    [5] 杨传勇, 胡海, 胡鹏, 曹枫.  欧氏障碍空间的最短路径问题解法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1495-1499.
    [6] 王伟, 漆炜, 陈能成, 杨国诚.  顾及地价空间分布规律的城市基准地价以价定级方法研究 . 武汉大学学报 ● 信息科学版, 2011, 36(6): 747-751.
    [7] 白轶多, 胡鹏, 夏兰芳, 郭峰林.  关于k次短路径问题的分析与求解 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 492-494.
    [8] 呙维, 龚健雅, 朱欣焰.  一种基于层次拓扑模型的分布式最短路径算法 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 864-868.
    [9] 翁敏, 杜清运, 瞿嵘, 蔡忠亮.  基于典型事例推理的路径规划方法研究 . 武汉大学学报 ● 信息科学版, 2008, 33(12): 1263-1266.
    [10] 唐健, 史文中, 孟令奎.  基于遗传算法的时相关动态车辆路径规划模型 . 武汉大学学报 ● 信息科学版, 2008, 33(8): 875-879.
    [11] 樊雅婷, 杨建宇, 朱德海, 王彦集.  基于阈值的城镇土地定级距离衰减模型 . 武汉大学学报 ● 信息科学版, 2008, 33(3): 277-280.
    [12] 邵黎霞, 何宗宜.  基于时空棱镜和活动场所吸引率的目的地选择研究 . 武汉大学学报 ● 信息科学版, 2007, 32(6): 481-484.
    [13] 郑年波, 李清泉, 徐敬海, 宋莺.  基于转向限制和延误的双向启发式最短路径算法 . 武汉大学学报 ● 信息科学版, 2006, 31(3): 256-259.
    [14] 祝国瑞, 唐旭, 王平.  基于影响特征的点状定级因素分析 . 武汉大学学报 ● 信息科学版, 2004, 29(8): 736-739,751.
    [15] 翁敏, 毋河海, 杜清运, 蔡忠亮.  基于公交网络模型的最优出行路径选择的研究 . 武汉大学学报 ● 信息科学版, 2004, 29(6): 500-506.
    [16] 苏康, 刘经南, 闫利.  基于GIS的无人飞行器路径规划 . 武汉大学学报 ● 信息科学版, 2003, 28(2): 188-190,196.
    [17] 刘耀林, 范延平, 唐旭.  最短路径方法在土地定级中的应用 . 武汉大学学报 ● 信息科学版, 2000, 25(6): 510-515,557.
    [18] 乐阳, 龚健雅.  Dijkstra最短路径算法的一种高效率实现 . 武汉大学学报 ● 信息科学版, 1999, 24(3): 208-212.
    [19] 朱庆, 陈楚江.  不规则三角网的快速建立及其动态更新 . 武汉大学学报 ● 信息科学版, 1998, 23(3): 204-207.
    [20] 李武龙, 陈军.  线状障碍物的可视最短路径Voronoi图生成 . 武汉大学学报 ● 信息科学版, 1998, 23(2): 132-136,158.
  • 加载中
图(6) / 表(2)
计量
  • 文章访问数:  392
  • HTML全文浏览量:  130
  • PDF下载量:  39
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-02-04
  • 刊出日期:  2021-01-05

一种利用双侧凸包扩张模型的路径快速规划算法

doi: 10.13203/j.whugis20180469
    基金项目:

    国家重点研发计划 2017YFC1405505

    国家自然科学基金 41601498

    作者简介:

    李改肖,博士,教授,主要从事海图制图理论与方法研究。lgxlndl@126.com

    通讯作者: 吕程,硕士,助理工程师。c191340844@qq.com
  • 中图分类号: P208

摘要: 针对障碍环境中路径规划存在的运算效率低、最短路径遗失问题,根据凸包边界在构建空间网络模型过程中具有快速高效的特点,结合路径与障碍物的相对位置关系,提出了一种基于双侧凸包扩张模型的路径快速规划算法。该算法在对凸包边界算法进行改进的基础上,提取左右侧关联障碍物的凸包边界作为网络模型,利用最短路径算法搜寻目标路径,并在ArcGIS Engine环境对密集不规则障碍物进行了仿真实验。实验结果表明,与凸包边界算法和航路二叉树算法相比,所提出的算法具有构建空间网络模型效率高、实际最短路径不丢失等优点。

English Abstract

李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
引用本文: 李改肖, 吕程, 彭认灿, 董箭. 一种利用双侧凸包扩张模型的路径快速规划算法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
LI Gaixiao, LÜ Cheng, PENG Rencan, DONG Jian. A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
Citation: LI Gaixiao, LÜ Cheng, PENG Rencan, DONG Jian. A Rapid Path Planning Algorithm Based on the Bilateral Convex-Hull Expanding Model[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 58-64. doi: 10.13203/j.whugis20180469
  • 自动路径规划是基于空间网络模型的起讫点,进行最优路径分析,对于解决资源分配[1-2]、路线设计及优化[3-5]等问题具有重要意义,是空间网络分析的关键。自动路径规划的本质在于最优路径分析方法在空间网络模型中的应用,然而受限于传统城市道路导航的应用需求,现有的经典路径规划算法大都基于预设的静态空间网络模型。随着自动路径规划应用领域的日益扩展,面向动态空间网络模型的最优路径解算逐渐成为研究热点,尤其在舰船航路规划[6-7]、低空无人机导航[8-9]等应用领域,对动态空间网络模型构建的准确性和高效性提出了更为严格的指标要求。因此,分析和论证计划路径与空间障碍实体的关系,准确高效构建具备自动避碰特性的动态空间网络模型的方法,对于研究舰船无人驾驶、无人机自动导航、舰载机出入库等问题具有重要的理论和现实意义。

    现有的自动路径规划算法大致可分为基于静态空间网络模型的最优路径分析方法和基于动态空间网络模型的最优路径分析方法两种。前者关注最优路径分析方法的构建与改进,如利用改进的迪杰斯特拉(Dijkstra)算法[9-11]、弗洛伊德(Floyd)算法[12-13]、A*算法[14-16]模型对静态空间网络模型进行路径规划,上述算法虽然表现出良好的准确性和实时性,但均依赖于预设的静态空间网络模型,在无预设路径网络的舰船航路规划、无人机导航等领域的应用中存在较大局限性。为了满足相关领域的应用需求,实现无预设网络空间的最优路径规划,需进行基于动态空间网络模型的路径分析。文献[17]利用Laguerre图算法进行路径预规划,满足了动态空间网络模型构建的实时性与准确性要求,但该算法所规划的路径为障碍物间中间路径,而不是起讫点间的实际最短路径;为保证最短路径规划的准确性,文献[18]提出了一种新型的边缘点树启发式搜索算法,该算法将地图空间离散化处理,根据障碍安全距离筛选可靠边缘点、搜索潜力点,得出最短路径;文献[19]提出了基于拓扑位置关系的无人艇路径搜索方法,该方法在地图要素表达、拓扑关系谓词和拓扑路径可达的基础上构建路径网,并用Dijkstra算法进行最短路径分析;文献[20]根据障碍物的二分性特点构建动态空间网络模型,实现了起讫点间最短路径分析,但该方法在复杂空间中的网络模型构建效率不高;为了提高网络模型的构建效率,文献[21-23]提出了利用凸包边界的思想进行路径规划的方法,该方法虽有效地提高了动态空间网络模型的构建效率,但在网络模型的准确性方面存在明显不足。

    为了克服传统凸包边界算法的不足,本文综合凸包边界算法[20]的高效性及航路二叉树算法[21]的准确性,提出了一种基于双侧凸包扩张算法的动态空间网络模型构建方法,并在ArcGIS Engine环境下,结合复杂障碍空间进行了仿真实验。实验结果表明,该算法在动态空间网络模型的构建中具有快速、准确、可行性好的优点。

    • 凸包是数据点的自然极限边界,是包含所有数据点的最小凸多边形,连接任意两点的线段必须完全位于该凸多边形中,同时区域的面积也达到最小值[24]。设S是平面E2中的点集,CSS的凸包,BS为凸包边界,对于$ \exists {p_1}, {p_2} \in S $,且有:

      $$ p = t{p_1} + \left( {1 - t} \right){p_2} $$ (1)

      式中,0≤t≤1。若点p属于S,则S为凸集,CS为包含S的最小凸集[25]

    • 凸包边界算法是以凸包为几何基础的动态空间网络模型构建算法。该算法根据路径与空间障碍物的关系,以计算路径与相关联障碍物凸包边界的方式构建空间网络模型,其基本思想如下[21]:设OK为与路径r相关联的障碍物集合,满足:

      $$ {O_K} = \left\{ {{o_i}\left| {r \cap {o_i} \ne \emptyset } \right.} \right\} $$ (2)

      式中,oi表示空间中所有障碍物集合O中的任意障碍物。设点pj(xj, yj)为ojOK的顶点,该顶点到路径r的距离dj为:

      $$ {d_j} = \frac{{a{x_j} + b{y_j} + c}}{{\sqrt {{a^2} + {b^2}} }} $$ (3)

      式中,abc为路径r所在直线方程的参数。若dj>0,则pjPup;若dj < 0,则pjPdown,其中,PupPdown分别为路径r上方、下方的点集。遍历OK后,将路径r的端点pspe分别与点集PupPdown进行凸包运算,以其凸包边界BupBdown作为新的规划路径集合。若BupBdown中仍有路径与障碍物相关联,则重复上述步骤。

      凸包边界算法将障碍空间中的路径规划问题转换为凸包计算问题,利用凸包边界一次性绕过与路径相关联的所有障碍物。该算法能够基于障碍物信息快速构建动态空间网络模型,满足了自动路径规划实时高效的要求[20],但在处理中间路径时仍存在较大局限性。

    • 由§1.2中凸包边界算法的构建原理可知,该方法利用了凸包边界BS包含点集S的特性进行动态空间网络模型的构建,按照一定寻优规则可进行最优路径规划。然而,在特殊的障碍物空间中,由于凸包边界思想未能对凸包内部障碍物实体间的相关路径进行规划,导致所构建空间网络模型的准确性不足,尤其是在最短路径规划时具有较大局限性。如图 1所示,O1O2O3为障碍物,实线为凸包边界算法构建的网络模型,路径SP2P7T为网络模型中最短路径。显然,基于凸包边界算法构建的网络模型得到的最短路径与实际最短路径SP1P4P9T不一致。

      图  1  凸包边界算法运算结果

      Figure 1.  Operation Result of Boundary of Convex-Hull Algorithm

    • 由§1.3的分析可知,凸包边界算法虽然提高了网络模型的构建效率,但所构建网络模型的准确性不足。造成上述问题的原因在于利用凸包边界进行避碰路径规划时,仅规划了与路径相关联障碍物的最外侧路径,未对关联障碍物内部的路径进行规划,因此丢失了障碍物内部的部分路径。对此,本文提出了一种双侧凸包扩张算法,在改进路径与障碍物凸包运算的基础上,提取路径左右侧关联障碍物凸包边界,进而构建动态空间网络模型。

      本文算法改进主要包括以下两个方面:(1)为提高算法所构网络模型的准确性,针对关联障碍物内部路径丢失的问题,本文提出了构建关联障碍物左右侧凸包的方法,该方法既保持了最外侧凸包边界,又在关联障碍物内部增加两族检测路径,防止最短路径的丢失。(2)由于凸包边界算法中路径关联障碍物的顶点是先进行位置划分、再进行凸包运算,从而导致计算冗余问题,为了提高算法的运算效率,本文将该过程化简为对路径及关联障碍物的边界直接进行凸包运算,降低凸包运算频数,提高算法运行效率。为了进一步化简网络结构,本文对于单侧障碍物进行优化处理,只保留满足条件的较短路径。

      首先对于满足式(2)的障碍物oiOK,点Ai为障碍物oi的中心点,对于路径ST,设向量$ \boldsymbol{P} = \left[ {S, T} \right], \boldsymbol{Q} = \left[ {S, {A_i}} \right] $,则:

      $$ {d_i} = \left\| {\boldsymbol{P} \times \boldsymbol{Q}} \right\| = \left\| \boldsymbol{P} \right\| \cdot \left\| \boldsymbol{Q} \right\| \cdot \sin \phi $$ (4)

      式中,di为向量积;ϕ为两向量的夹角。根据向量叉乘的定义可知,di的正负决定了点Ai的位置。若di>0,则Ai位于路径ST左侧,定义障碍物oi为路径ST的左侧障碍物;若di < 0,则Ai位于路径ST右侧,定义障碍物oi为路径ST的右侧障碍物。

      当障碍物均位于路径一侧时,由路径ST将凸包边界分为左侧路径rl与右侧路径rr,若其中长度较短的路径rmin满足:

      $$ {r_{{\rm{min}}}} \cap O = \emptyset $$ (5)

      则只保留该路径,舍弃长度较长的路径。式中,O为障碍物集合。

      然后分别对路径与其左右两侧障碍物进行凸包运算,并将凸包边界作为新路径,循环上述方法直至所有路径均无关联障碍物。如图 2所示,点A1A3位于路径ST左侧,A2位于路径ST右侧,即O1O3为路径ST的左侧障碍物,O2为右侧障碍物。对于路径P1P9与障碍物O2进行运算时,显然路径P1P4P9的长度小于路径P1P5P6P9,且路径P1P4P9不与其他障碍物相交,则只保留路径P1P4P9

      图  2  本文算法原理示意图

      Figure 2.  Schematic Diagram of Our Proposed Algorithm

      最后使用最短路径搜索算法进行自动路径规划,本文算法流程图如图 3所示。

      图  3  本文算法流程图

      Figure 3.  Flowchart of Our Proposed Algorithm

    • 为了验证本文算法在密集不规则障碍物条件下进行自动路径规划的可行性及优越性,本文在ArcGIS Engine环境下实现了该算法,并对文献[20]中的凸包边界算法进行最短路径的可行性比较分析,对文献[21]中的航路二叉树算法进行优越性对比分析。

      图 4所示,根据某地实际建筑物分布抽象得到密集不规则的障碍物区域,针对该区域进行自动路径规划的仿真实验,灰色区域表示障碍物,并设置3组起讫点坐标分别为(S1, T1)、(S2, T2)和(S3, T3)。

      图  4  障碍物及3组起终点

      Figure 4.  Obstacles and Three Groups of Start and End Points

      实验分为3组,均应用凸包边界算法、航路二叉树算法和本文算法3种自动路径规划方法进行实验,其结果如图 5所示,实线表示空间网络模型,红色粗实线表示当前网络模型中的最短路径。其中,图 5(a)5(b)5(c)对应路径S1, T1,记为实验1;图 5(d)5(e)5(f)对应路径S2, T2,记为实验2;图 5(g)5(h)5(i)对应路径S3, T3,记为实验3。由图 5可以发现,实验1与实验3中本文算法与航路二叉树算法均可规划出起讫点间的最短路径,凸包边界算法规划出了错误的最短路径;实验2中3种算法规划的结果一致,均得到了实际最短路径。可见,凸包边界算法进行障碍物空间最短路径自动规划的真实性不足,其余两种算法在规划实际最短路径时具有较强的稳定性。

      图  5  3种算法实验结果

      Figure 5.  Experimental Results of Three Algorithms

      此外,为了验证本文算法网络模型构建的效率和网络模型结构复杂度的优势,本文对上述实验进行了量化分析,空间网络模型的路径数量及构建耗时如表 1表 2所示。

      表 1  路径数量

      Table 1.  Number of Paths

      算法 路径数/条
      实验1 实验2 实验3
      凸包边界算法 37 63 19
      航路二叉树算法 92 110 45
      本文算法 72 95 28

      表 2  空间网络模型构建耗时/ms

      Table 2.  Time Consumption of Constructing Spatial Network Model/ms

      算法 耗时
      实验1 实验2 实验3
      凸包边界算法 432 540 293
      航路二叉树算法 2 605 2 361 681
      本文算法 1 309 1 295 424

      图 5表 1表 2可以看出,凸包边界算法构建空间网络模型耗时短,所构建的网络结构简单,但受算法原理限制,往往不能规划起讫点间的实际最短路径;航路二叉树算法能够准确地自动规划起讫点间的实际最短路径,但构建空间网络模型耗时长、网络结构复杂;本文算法则综合了前两种算法的优点,在保证规划实际最短路径的同时,提高了算法的执行效率。

      针对在不同数量的障碍物环境中构建动态空间网络模型,本文在障碍物大小、形状相似且分布均匀的环境中,分别统计3种算法构建空间网络模型的耗时,并取其平均值。运行环境配置如下:Intel i7-2670 QM CPU(主频2.2 GHz),内存8 GB,硬盘128 GB SSD。其构网耗时变化趋势如图 6所示。

      图  6  构建空间网络模型耗时趋势

      Figure 6.  Time Consuming Trend of Constructing Spatial Network Model

      根据图 6统计的结果分析3种算法的时间复杂度。设障碍物数量为n,每次路径搜索需判断当前路径与其余障碍物是否相交,即进行n次运算,则凸包边界算法的平均时间复杂度为:

      $$ {T_1}\left( n \right) = O\left( {\frac{{n\left( {n - 1} \right)}}{2}} \right) $$ (6)

      航路二叉树算法的平均时间复杂度为:

      $$ {T_2}\left( n \right) = O\left( {1.5 \times \frac{{n\left( {n - 1} \right)}}{2}} \right) $$ (7)

      本文算法的平均时间复杂度为:

      $$ {T_3}\left( n \right) = O\left( {\frac{{n\left( {n - 1} \right)}}{2} + 2n} \right) $$ (8)

      从式(6)~(8)可以看出,虽然三者时间复杂度形式都为O(n2),但T3(n)的一阶系数大于T1(n),二阶系数小于T2(n),故本文算法时间复杂度介于凸包边界算法与航路二叉树算法之间,与实际运算时间相符。

    • 本文针对当前自动路径规划算法存在的准确性及时效性不足的问题,结合凸包边界思想在空间网络模型构建中的优势,提出了基于双侧凸包扩张模型的障碍物环境中快速路径规划算法。仿真实验结果表明,本文算法既克服了凸包边界算法无法规划最短路径的不足,又保持了网络模型结构简单、构网耗时短的优势,能够快速、准确地进行动态的自动路径规划,在无预设网络的无人舰艇航行、无人机导航等领域具有较高的应用价值。但需要指出的是,本文算法在进行包含弧多边形、凹多边形等障碍物的路径规划时仍有一定的局限性。

参考文献 (25)

目录

    /

    返回文章
    返回