Please wait a minute...
浙江大学学报(工学版)  2020, Vol. 54 Issue (2): 291-300    DOI: 10.3785/j.issn.1008-973X.2020.02.010
计算机技术、信息工程     
移动机器人路径动态规划有向D*算法
刘军(),冯硕,任建华
兰州理工大学 机电工程学院,甘肃 兰州 730050
Directed D* algorithm for dynamic path planning of mobile robots
Jun LIU(),Shuo FENG,Jian-hua REN
School of Electromechanical Engineering, Lanzhou University of Technology, Lanzhou 730050, China
 全文: PDF(1054 KB)   HTML
摘要:

针对传统D*路径规划算法搜索效率低、成本较高的问题,提出有向D*算法. 该算法考虑目标点与障碍物信息,引入关键节点概念,逐级扩展确定可行路径,并且引入导向函数以控制单次搜索的节点搜索范围来提高搜索效率;在原欧几里得评价指标的基础上引入路径平滑度函数对偏移路径进行惩罚,避免机器人无效转弯而增加移动成本;通过路径平滑度函数中的“转弯因子”协调路径长度与平滑度之间的关系,给出路径平滑度函数的分段原理与转弯因子的确定方法,并对算法收敛性进行证明. 在不同环境下的仿真实验表明,该算法较传统算法能更好地兼顾局部搜索与全局最优性,尤其适用于障碍物较多的复杂环境.

关键词: 动态路径规划有向D*算法导向函数路径平滑度函数转弯因子    
Abstract:

A directed D* route planning algorithm was proposed, aiming at the low efficiency and high cost of the traditional D* route planning algorithms. In the proposed directed D* algorithm, the key nodes are defined by utilizing the location information of target points and obstacles so that the feasible routes could be determined by a stepwise expanding way, and a directed function is introduced to control the single searching range of nodes in order to improve the searching efficiency. A path smoothness function which punishes the deviation of paths is introduced to the algorithm in addition to Euclidean evaluation function, in order to avoid the redundant turning of robots and reduce the costs. The length of the path and the smoothness are taken into account simultaneously by the turning factor of the path smoothness function. The piecewise principle of the path smoothness function and the determining method of the turning factor are proposed. The convergence of the algorithm was also proved. Simulation experiments in different environments show that the proposed algorithm can balance the local searching and the global optimality, and it is especially suitable for complex environments with many obstacles.

Key words: dynamic path planning    directed D* algorithm    steering function    path smoothness function    turning factor
收稿日期: 2019-05-15 出版日期: 2020-03-10
CLC:  TH 181  
基金资助: 国家自然科学基金资助项目(71861025);科技部国家重点研发计划资助项目(2018YFB1703105);兰州理工大学红柳一流学科建设资助项目
作者简介: 刘军(1974—),男,教授,博士,从事复杂制造系统、生产调度与控制研究. orcid.org/0000-0001-7600-2801. E-mail: lzhjliu@126.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
刘军
冯硕
任建华

引用本文:

刘军,冯硕,任建华. 移动机器人路径动态规划有向D*算法[J]. 浙江大学学报(工学版), 2020, 54(2): 291-300.

Jun LIU,Shuo FENG,Jian-hua REN. Directed D* algorithm for dynamic path planning of mobile robots. Journal of ZheJiang University (Engineering Science), 2020, 54(2): 291-300.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2020.02.010        http://www.zjujournals.com/eng/CN/Y2020/V54/I2/291

图 1  栅格模型示意图
图 2  有向D*算法系统结构图
图 3  传统D*算法与本研究算法的搜索方法对比
k z=15 z=25 z=50
b=4 b=6 b=8 b=10 b=4 b=6 b=8 b=10 b=4 b=6 b=8 b=10
3 1.8×10?1 9.3×10?2 5.1×10?2 3.1×10?2 2.4×10?1 2.0×10?1 1.4×10?1 9.3×10?2 7.2×10?2 1.9×10?1 2.3×10?1 2.2×10?1
6 5.7×10?3 7.7×10?4 1.7×10?4 4.9×10?5 5.4×10?2 1.1×10?2 3.1×10?3 1.0×10?3 1.7×10?1 1.2×10?1 5.5×10?2 2.6×10?2
9 1.7×10?5 5.8×10?7 4.9×10?8 7.2×10?9 1.8×10?3 9.8×10?5 1.1×10?5 1.8×10?6 7.8×10?2 1.4×10?2 2.6×10?3 6.0×10?4
12 4.4×10?9 3.9×10?11 1.3×10?12 9.5×10?14 1.3×10?5 1.9×10?7 8.0×10?9 6.5×10?10 1.1×10?2 5.0×10?4 3.7×10?5 4.2×10?6
表 1  z=15、25、50时不同分段情况下事件A发生k次的概率
ES NE NO NK DK
502 2.5×103 1.5×103 3.0×102 8
1002 1.0×104 6.0×103 1.2×103 8
5002 2.5×105 1.5×105 3.0×104 8
1 0002 1.0×106 6.0×105 1.2×105 8
表 2  关键节点平均距离与环境维数的关系
图 4  平均距离与障碍物覆盖率的关系
图 5  有向D*算法流程图
环境 起始节点 目标节点
502 (1, 1) (50, 50)
1002 (1, 1) (100, 100)
5002 (1, 1) (500, 500)
表 3  不同复杂程度的环境参数
图 6  不同复杂程度的环境示意图
ES 有向D* D* Lite Focussed D*
502 72.06 77.09 75.24
1002 155.28 161.49 158.78
5002 828.62 860.72 1 134.80
表 4  不同环境下路径长度对比
算法 ES=502 ES=1002 ES=5002
OT FT OT FT OT FT
有向D* 14.56 0.65 55.70 1.12 113.50 18.90
D* Lite 14.02 2.14 50.70 10.46 114.34 764.20
Focussed D* 17.29 2.67 65.01 14.41 150.88 860.41
表 5  不同环境下路径规划时间对比
图 7  不同地图路径规划结果
算法 拐点数目
ES=502 ES=1002 ES=5002
有向D* 3 10 12
D* Lite 5 13 17
Focussed D* 5 20 25
表 6  不同环境下拐点数目对比
1 DADI R, PASHA S N, SALLAUDDIN M. Cognitive-based adaptive path planning for mobile robot in dynamic environment [C]// 1st International Conference on Artificial Intelligence and Cognitive Computing. Singapore: AICC, 2018: 117-123.
2 FARIDI A Q, SHARMA S, SHUKLA A, et al Multi-robot multi-target dynamic path planning using artificial bee colony and evolutionary programming in unknown environment[J]. Intelligent Service Robotics, 2018, 11 (2): 171- 186
doi: 10.1007/s11370-017-0244-7
3 KADRY S, ABDALLAH A, JOUMAA C. On the optimization of Dijkstras algorithm [M]// Informatics in control, automation and robotics. Berlin: Springer, 2012: 393-397.
4 LIU Y, LIANG J H, LI J, et al Robot path planning based on Dijkstra’s algorithm and genetic algorithm[J]. Frontier Computing, 2016, 422: 397- 408
5 霍凤财, 迟金, 黄梓健, 等 移动机器人路径规划算法综述[J]. 吉林大学学报:信息科学版, 2018, 36 (6): 639- 647
HUO Feng-cai, CHI Jin, HUANG Zi-jian, et al Overview of path planning algorithms for mobile robots[J]. Journal of Jilin University: Information Science Edition, 2018, 36 (6): 639- 647
6 HART P E, NILSSON N J, RAPHAEL B A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4 (2): 100- 107
doi: 10.1109/TSSC.1968.300136
7 MOHD N Z, MOHANTA J C Methodology for path planning and optimization of mobile robots: a review[J]. Procedia Computer Science, 2018, 133: 141- 152
doi: 10.1016/j.procs.2018.07.018
8 朱大奇, 颜明重 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25 (7): 961- 967
ZHU Da-qi, YAN Ming-zhong Overview of path planning techniques for mobile robots[J]. Control and Decision-making, 2010, 25 (7): 961- 967
9 KHATIB O Real-time obstacle avoidance for manipulators and mobile robot[J]. The International Journal of Robotics Research, 1986, 5 (1): 90- 98
doi: 10.1177/027836498600500106
10 YANG G W, DENG Y, ZHUANG X D, et al. An improved real-time path planning of mobile robot in a complex and dynamic environment [C]// 2017 1st International Conference on Electronics Instrumentation and Information Systems (EIIS). Harbin: IEEE, 2017: 1-4.
11 WANG S M, ZHAO T T, LI W J. Mobile robot path planning based on improved artificial potential field method [C]// International Conference of Intelligent Robotic and Control Engineering. Lanzhou: IEEE, 2018: 29-33.
12 LIANG X X, LIU C Y, SONG X L, et al. Research on mobile robot path planning in dynamic environment [C]// 2017 Chinese Automation Congress (CAC). Jinan: IEEE, 2017: 3890-3894.
13 KOENIG S, LIKHACHEY M, FURCY D Lifelong planning A*[J]. Artificial Intelligence, 2004, 155 (1/2): 93- 146
14 PATLE B K, PANDEY A, JAGADEESH A, et al Path planning in uncertain environment by using firefly algorithm[J]. Defence Technology, 2018, 14 (6): 691- 701
doi: 10.1016/j.dt.2018.06.004
15 PANDA R K, CHOUDHURY B B. An effective path planning of mobile robot using genetic algorithm [C]// IEEE International Conference on Computational Intelligence and Communication Technology. Ghaziabad: IEEE, 2015: 287-291.
16 STENTZ A. The D* algorithm for real-time planning of optimal traverses [EB/OL]. (1994-09-01) [2019-04-15]. http://pdfs.semanticscholar.org/8e60/573c99d2d290dd9163272ea21727c382d00b.pdf.
17 STENTZ A. Optimal and efficient path planning for partially-known environments [C]// IEEE International Conference on Robotics and Automation. Pittsburgh: IEEE, 1994: 3310-3317.
18 史久根, 李凯业 基于分层改进D~*算法的室内路径规划[J]. 计算机应用研究, 2015, 32 (12): 3609- 3612
SHI Jiu-gen, LI Kai-ye Indoor path planning based on hierarchical improved D~* algorithm[J]. Computer Application Research, 2015, 32 (12): 3609- 3612
doi: 10.3969/j.issn.1001-3695.2015.12.018
19 STENTZ A. The focussed D* algorithm for real-time replanning [C]// Proceedings of the 14th International Joint Conference on Artificial Intelligence. Montreal: [s.n.], 1995: 1652-1659.
20 KOENIG S, LIKHACHEV M Fast replanning for navigation in unknown terrain[J]. IEEE Transactions on Robotics, 2005, 21 (3): 354- 363
doi: 10.1109/TRO.2004.838026
No related articles found!