Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2020, Vol. 54 Issue (2): 291-300    DOI: 10.3785/j.issn.1008-973X.2020.02.010
Computer Technology, Information Engineering     
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
Download: HTML     PDF(1054KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 15 May 2019      Published: 10 March 2020
CLC:  TH 181  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jun LIU
Shuo FENG
Jian-hua REN
Cite this article:

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.

URL:

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


移动机器人路径动态规划有向D*算法

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


关键词： 动态路径规划,  有向D*算法,  导向函数,  路径平滑度函数,  转弯因子 
Fig.1 Schematic diagram of grid model
Fig.2 Directed D* algorithm system structure diagram
Fig.3 Searching method comparison between traditional D* algorithm and proposed algorithm
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
Tab.1 Probability of event A occurring k times under different segmentation conditions at z of 15, 25 and 50
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
Tab.2 Relationship between average distance of key nodes and environmental dimension
Fig.4 Relationship between average distance and obstacle coverage rate
Fig.5 Flow chart of directed D* algorithm
环境 起始节点 目标节点
502 (1, 1) (50, 50)
1002 (1, 1) (100, 100)
5002 (1, 1) (500, 500)
Tab.3 Environment parameters with varying complexity
Fig.6 Environment diagrams with varying degrees of complexity
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
Tab.4 Comparison of route length in different environments
算法 ES=502 ES=1002 ES=5002
O（T） F（T） O（T） F（T） O（T） F（T）
有向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
Tab.5 Comparison of route planning time in different environments
Fig.7 Route planning results for different maps
算法 拐点数目
ES=502 ES=1002 ES=5002
有向D* 3 10 12
D* Lite 5 13 17
Focussed D* 5 20 25
Tab.6 Number of inflection points in different environments
[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!