浙江大学学报(工学版)  2020, Vol. 54 Issue (2): 291-300    DOI: 10.3785/j.issn.1008-973X.2020.02.010
 计算机技术、信息工程

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

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

 CLC: TH 181

 服务 把本文推荐给朋友 加入引用管理器 E-mail Alert 作者相关文章 刘军 冯硕 任建华

#### 引用本文:

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.

#### 链接本文:

 图 1  栅格模型示意图 图 2  有向D*算法系统结构图 图 3  传统D*算法与本研究算法的搜索方法对比 表 1  z=15、25、50时不同分段情况下事件A发生k次的概率 表 2  关键节点平均距离与环境维数的关系 图 4  平均距离与障碍物覆盖率的关系 图 5  有向D*算法流程图 表 3  不同复杂程度的环境参数 图 6  不同复杂程度的环境示意图 表 4  不同环境下路径长度对比 表 5  不同环境下路径规划时间对比 图 7  不同地图路径规划结果 表 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- 647HUO 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- 967ZHU 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!