Improved search-tree reinitialization for an incremental heuristic search domains with long actions

• Autorzy: Przybylski M.
• Języki publikacji: EN

Abstrakty

EN

Incremental heuristic search algorithms, such as D* Lite, are commonly used for mobile robot motion planning. The main disadvantage of D* Lite and similar algorithms is that the reinitialization requires a computation of all actions affected by changes in an environment. In case of long actions (motion primitives intersecting multiple map cells), a number of affected actions can be extremely large. Therefore, in this paper a new incremental search algorithm D* State Cut based on the recent D* Extra Lite algorithm is proposed. In comparison to D* Extra Lite, D* State Cut does not require affected actions to be computed; it is sufficient to compute only successors of changed actions with annotations about a change type (cost increase or decrease). In the tests, for domains with a significant number of long actions, D* State Cut was up-to two times quicker than D* Extra Lite.

Słowa kluczowe

EN

traffic planning; action plan; task planning

PL

planowanie ruchu; planowanie działań; planowanie zadań

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2018
• Tom: z. 196
• Strony: 301--310
• Opis fizyczny: Bibliogr. 16 poz., rys., tab., wykr.

Twórcy

autor

Przybylski M.

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

Bibliografia

• [1] K. Gochev, A. Safonova, M. Likhachev. Incremental planning with adaptive dimensionality. In: ICAPS. Proceedings, 2013, pp. 82-90.
• [2] K. Gochev, A. Safonova, M. Likhachev. Anytime tree-restoring weighted A* graph search. In: Seventh Annual Symposium on Combinatorial Search. Proceedings, 2014, pp. 80-88.
• [3] C. Hernández, R. Asín, J. A. Baier. Reusing previously found A* paths for fast goal-directed navigation in dynamic terrain. In: Twenty-Ninth AAAI Conference on Artificial Intelligence, Austin, Texas, USA. Proceedings, 2015, AAAI'15, pp. 1158-1164.
• [4] S. Koenig, M. Likhachev. Adaptive A*. In: Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, Netherlands. Proceedings, 2005, AAMAS '05, pp. 1311-1312.
• [5] S. Koenig, M. Likhachev. Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics, 2005, Vol. 21, No. 3, pp. 354-363.
• [6] S. Koenig, M. Likhachev, D. Furcy. Lifelong planning A*. Artificial Intelligence, 2004, Vol. 155, No. 1, pp. 93-146.
• [7] M. Likhachev, D. Ferguson. Planning long dynamically feasible maneuvers for autonomous vehicles. The International Journal of Robotics Research, 2009, Vol. 28, No. 8, pp. 933-945.
• [8] M. Pivtoraiko, R. A. Knepper, A. Kelly. Differentially constrained mobile robot motion planning in state lattices. Journal of Field Robotics, 2009, Vol. 26, No. 3, pp. 308-333.
• [9] L. Podsędkowski et al. A new solution for path planning in partially known or unknown environment for nonholonomic mobile robots. Robotics and Autonomous Systems, 2001, Vol. 34, No. 2, pp. 145-152.
• [10] M. Przybylski. AD*-Cut: A search-tree cutting anytime dynamic A* algorithm. In: Proceedings of the 28th International Conference on Automated Planning and Scheduling. Proceedings, 2018, ICAPS'18, pp. 494-499.
• [11] M. Przybylski, B. Putz. D* Extra Lite: a Dynamic A* with Search-tree Cutting and Frontier-gap Repairing. International Journal of Applied Mathematics and Computer Science (AMCS), 2017, Vol. 27, No. 2, pp. 273-290.
• [12] A. Stentz. The Focussed D* algorithm for real-time replanning. In: Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2, Montreal, Quebec, Canada. Proceedings, 1995, IJCAI'95, pp. 1652-1659.
• [13] N. R. Sturtevant. Benchmarks for grid-based pathfinding. Computational Intelligence and AI in Games, IEEE Transactions on, 2012, Vol. 4, No. 2, pp. 144-148.
• [14] X. Sun, S. Koenig. The Fringe-Saving A* search algorithm-a feasibility study. In: Proceedings of the 20th International Joint Conference on Artifical Intelligence, Hyderabad, India. Proceedings, 2007, IJCAI'07, pp. 2391-2397.
• [15] X. Sun, S. Koenig, W. Yeoh. Generalized Adaptive A*. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems Volume 1, Estoril, Portugal. Proceedings, 2008, AAMAS'08, pp. 469-476.
• [16] K. I. Trovato, L. Dorst. Differential A*. IEEE Transaction on Knowledge and Data Engineering, 2002, Vol. 14, No. 6, pp. 1218-1229.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).