D* Extra Lite: A dynamic A* with search-tree cutting and frontier-gap repairing

Przybylski, M. ; Putz, B.

International Journal of Applied Mathematics and Computer Science, Tome 27 (2017) no. 2, pp. 273-290.

Résumé

Searching for the shortest-path in an unknown or changeable environment is a common problem in robotics and video games, in which agents need to update maps and to perform re-planning in order to complete their missions. D* Lite is a popular incremental heuristic search algorithm (i.e., it utilizes knowledge from previous searches). Its efficiency lies in the fact that it re-expands only those parts of the search-space that are relevant to registered changes and the current state of the agent. In this paper, we propose a new D* Extra Lite algorithm that is close to a regular A*, with reinitialization of the affected search-space achieved by search-tree branch cutting. The provided worst-case complexity analysis strongly suggests that D* Extra Lite’s method of reinitialization is faster than the focused approach to reinitialization used in D* Lite. In comprehensive tests on a large number of typical two-dimensional path-planning problems, D* Extra Lite was 1.08 to 1.94 times faster than the optimized version of D* Lite. Moreover, while demonstrating that it can be particularly suitable for difficult, dynamic problems, as the problem-complexity increased, D* Extra Lite’s performance further surpassed that of D*Lite. The source code of the algorithm is available on the open-source basis.

Détail

Keywords: shortest path planning, incremental heuristic search, mobile robot navigation, video game
Mots-clés : planowanie najkrótszej ścieżki, wyszukiwanie heurystyczne, nawigacja robota mobilnego, gra wideo

Bibliographie

[1] Aine, S. and Likhachev, M. (2016). Truncated incremental search, Artificial Intelligence 234: 49–77.

[2] Belter, D., Łabecki, P., Fankhauser, P. and Siegwart, R. (2016). RGB-D terrain perception and dense mapping for legged robots, International Journal of Applied Mathematics and Computer Science 26(1): 81–97, DOI: 10.1515/amcs-2016-0006.

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

[4] Hernández, C., Asín, R. and Baier, J.A. (2015). Reusing previously found A* paths for fast goal-directed navigation in dynamic terrain, 19th AAAI Conference on Artificial Intelligence, Austin, TX, USA, pp. 1158–1164.

[5] Hernández, C., Baier, J.A. and Asín, R. (2014). Making A* run faster than D*-Lite for path-planning in partially known terrain, Proceedings of the 24th International Conference on Automated Planning and Scheduling, Portsmouth, NH, USA, pp. 504–508.

[6] Hernández, C., Meseguer, P., Sun, X. and Koenig, S. (2009). Path-Adaptive A* for incremental heuristic search in unknown terrain, Proceedings of the 19th International Conference on Automated Planning and Scheduling, Thessaloniki, Greece, pp. 358–361.

[7] Hernández, C., Sun, X., Koenig, S. and Meseguer, P. (2011). Tree Adaptive A*, 10th International Conference on Autonomous Agents and Multiagent Systems, Taipei, Taiwan, Vol. 1, pp. 123–130.

[8] Koenig, S. and Likhachev, M. (2001). Improved fast replanning for robot navigation in unknown terrain, Technical Report GIT-COGSCI-2002/3, Georgia Institute of Technology, Atlanta, GA.

[9] Koenig, S. and Likhachev, M. (2005a). Adaptive A*, Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, The Netherlands, pp. 1311–1312.

[10] Koenig, S. and Likhachev, M. (2005b). Fast replanning for navigation in unknown terrain, IEEE Transactions on Robotics 21(3): 354–363.

[11] Koenig, S., Likhachev, M. and Furcy, D. (2004). Lifelong planning A*, Artificial Intelligence 155(1): 93–146.

[12] Koenig, S. and Sun, X. (2009). Comparing real-time and incremental heuristic search for real-time situated agents, Autonomous Agents and Multi-Agent Systems 18(3): 313–341.

[13] Likhachev, M., Ferguson, D.I., Gordon, G.J., Stentz, A. and Thrun, S. (2005). Anytime Dynamic A*: An anytime, replanning algorithm, Proceedings of the 15th International Conference on Automated Planning and Scheduling, Monterey, CA, USA, pp. 262–271.

[14] Podsędkowski, L. (1998). Path planner for nonholonomic mobile robot with fast replanning procedure, 1998 IEEE International Conference on Robotics and Automation, Lueven, Belgium, Vol. 4, pp. 3588–3593.

[15] Podsędkowski, L., Nowakowski, J., Idzikowski, M. and Vizvary, I. (2001). A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots, Robotics and Autonomous Systems 34(2): 145–152.

[16] Przybylski, M., Koguciuk, D., Siemiątkowska, B., Harasymowicz-Boggio, B. and Chechliński, Ł. (2015). Integration of qualitative and quantitative spatial data within a semantic map for service robots, in R. Szewczyk et al. (Eds.), Progress in Automation, Robotics and Measuring Techniques. Volume 2: Robotics, Springer, Cham, pp. 223–232.

[17] Przybylski, M. and Siemiątkowska, B. (2012). A new CNN-based method of path planning in dynamic environment, in L. Rutkowski et al. (Eds.), Artificial Intelligence and Soft Computing, ICAISC 2012, Lecture Notes in Computer Science, Vol. 7268, Springer, Berlin/Heidelberg, pp. 484–492.

[18] Stentz, A. (1994). Optimal and efficient path planning for partially-known environments, Proceedings of the 1994 IEEE International Conference on Robotics and Automation, San Diego, CA, USA, Vol. 4, pp. 3310–3317.

[19] Stentz, A. (1995). The Focussed D* algorithm for real-time replanning, Proceedings of the 14th International Joint Conference on Artificial Intelligence, Montreal, Quebec, Canada, Vol. 2, pp. 1652–1659.

[20] Sturtevant, N.R. (2012). Benchmarks for grid-based pathfinding, IEEE Transactions on Computational Intelligence and AI in Games 4(2): 144–148.

[21] Sun, X. and Koenig, S. (2007). The Fringe-Saving A* search algorithm—a feasibility study, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, pp. 2391–2397.

[22] Sun, X., Koenig, S. and Yeoh, W. (2008). Generalized Adaptive A*, Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Estoril, Portugal, Vol. 1, pp. 469–476.

[23] Trovato, K.I. (1990). Differential A*: An adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment, International Journal of Pattern Recognition and Artificial Intelligence 4(2): 245–268.

[24] Trovato, K.I. and Dorst, L. (2002). Differential A*, IEEE Transactions on Knowledge and Data Engineering 14(6): 1218–1229.

[25] van Toll, W. and Geraerts, R. (2015). Dynamically Pruned A* for re-planning in navigation meshes, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, pp. 2051–2057.