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

• Autorzy: Przybylski M. , Putz B.

Identyfikatory

DOI

10.1515/amcs-2017-0020

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

shortest path planning; incremental heuristic search; mobile robot navigation; video game

PL

planowanie najkrótszej ścieżki; wyszukiwanie heurystyczne; nawigacja robota mobilnego; gra wideo

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2017
• Tom: Vol. 27, no. 2
• Strony: 273--290
• Opis fizyczny: Bibliogr. 25 poz., rys., tab., wykr.

Twórcy

autor

Przybylski M.

• Institute of Automatic Control and Robotics, Warsaw University of Technology, ul. św. A. Boboli 8, 02-525 Warsaw, Poland

autor

Putz B.

• Institute of Automatic Control and Robotics, Warsaw University of Technology, ul. św. A. Boboli 8, 02-525 Warsaw, Poland

Bibliografia

• [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.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).