Welcome to Scholar Publishing Group

International Journal of Social Sciences and Economic Management, 2023, 4(2); doi: 10.38007/IJSSEM.2023.040213.

Threat Cost Based Multi-level Prediction D-star Algorithm


Huiheng Suo, Bosi Wei, Jian Wu, Xie Ma, Tao Yang, Yaoyu Huang, Yicheng Lu, Xiushui Ma

Corresponding Author:
Bosi Wei and Jian Wu

Nanchang Hangkong University, Nanchang, China


In this paper, we propose a Multi-level Prediction D-star algorithm (MLP D-star) based on threat cost to address the path planning problem of mobile robots in local unknown environments. The algorithm improves the node expansion of the D-star algorithm using a multi-level prediction structure, which avoids excessive turning points in the planned path. The cost function of this algorithm incorporates threat cost and heuristic function to prevent the issue of path crossing obstacles. Simulation results demonstrate that the improved MLP D-star algorithm has advantages in terms of real-time performance, practicality of path results, safety, and computational efficiency. 


Path Planning, MLP D-star Algorithm, D-star Algorithm, Modeling and Simulation

Cite This Paper

Huiheng Suo, Bosi Wei, Jian Wu, Xie Ma, Tao Yang, Yaoyu Huang, Yicheng Lu, Xiushui Ma. Threat Cost Based Multi-level Prediction D-star Algorithm. International Journal of Social Sciences and Economic Management (2023), Vol. 4, Issue 2: 96-107. https://doi.org/10.38007/IJSSEM.2023.040213.


[1] Zhang H-Y, Lin W-M, Chen A-X. Path planning for the mobile robot: A review . Symmetry, 2018, 10(10): 450.

[2] Gasparetto A, Boscariol P, Lanzutti A, et al. Path planning and trajectory planning algorithms: A general overview . Motion and Operation Planning of Robotic Systems: Background and Practical Approaches, 2015: 3-27.

[3] Dijkstra E W. A note on two problems in connexion with graphs. Edsger Wybe Dijkstra: His Life, Work, and Legacy. 2022: 287-290.

[4] Hart P E, Nilsson N J, Raphael B. A formal basis for the heuristic determination of minimum cost paths . IEEE transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[5] Stentz A. The focussed D* algorithm for real-time replanning . Proceedings of the IJCAI. 1995: 1652-1659.

[6] Liu Jun, Feng Shuo, Ren Jianhua. Directed D * algorithm for dynamic path planning of mobile robots. Journal of Zhejiang University ( Engineering Edition ), 2020, 54 ( 2 ) : 291-300.

[7] Rekleitis I, Bedwani J-L, Dupuis E, et al. Path planning for planetary exploration . Proceedings of the 2008 Canadian Conference on Computer and Robot Vision. IEEE, 2008: 61-68.

[8] Koenig S, Likhachev M. D^* lite . Aaai/iaai, 2002, 15: 476-483.

[9] Lavalle S M. Rapidly-exploring random trees: A new tool for path planning . 1998.

[10] Kuffner J J, Lavalle S M. RRT-connect: An efficient approach to single-query path planning . Proceedings of the Proceedings 2000 ICRA Millennium Conference IEEE International Conference on Robotics and Automation Symposia Proceedings (Cat No 00CH37065). IEEE, 2000: 995-1001.

[11] Karaman S, Walter M R, Perez A, et al. Anytime motion planning using the RRT . Proceedings of the 2011 IEEE international conference on robotics and automation. IEEE, 2011: 1478-1483.

[12] Khatib O. Real-time obstacle avoidance for manipulators and mobile robots . The international journal of robotics research, 1986, 5(1): 90-98.

[13] Fox D, Burgard W, Thrun S. The dynamic window approach to collision avoidance . IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.

[14] Lee D H, Lee S S, Ahn C K, et al. Finite distribution estimation-based dynamic window approach to reliable obstacle avoidance of mobile robot . IEEE Transactions on Industrial Electronics, 2020, 68(10): 9998-10006.

[15] Xiaoran Z, Hehua J. Path planning of mobile robot in local unknown environment . Proceedings of the The 2nd International Conference on Information Science and Engineering. IEEE, 2010: 5231-5234.