PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Treść / Zawartość
Identyfikatory
Warianty tytułu
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.
Rocznik
Strony
273--290
Opis fizyczny
Bibliogr. 25 poz., rys., tab., wykr.
Twórcy
  • Institute of Automatic Control and Robotics, Warsaw University of Technology, ul. św. A. Boboli 8, 02-525 Warsaw, Poland
autor
  • 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-5338a348-4749-43c0-9c0a-8fffcd5a1686
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.