caa a22 4500 605514836 CHVBK 20210128100706.0 cr unu---uuuuu 210128e20150901xx s 000 0 eng 10.1007/s10458-014-9266-0 doi (NATIONALLICENCE)springer-10.1007/s10458-014-9266-0 Reusing cost-minimal paths for goal-directed navigation in partially known terrains [Elektronische Daten] [Carlos Hernández, Tansel Uras, Sven Koenig, Jorge Baier, Xiaoxun Sun, Pedro Meseguer] Situated agents frequently need to solve search problems in partially known terrains in which the costs of the arcs of the search graphs can increase (but not decrease) when the agents observe new information. An example of such search problems is goal-directed navigation with the freespace assumption in partially known terrains, where agents repeatedly follow cost-minimal paths from their current locations to given goal locations. Incremental heuristic search is an approach for solving the resulting sequences of similar search problems potentially faster than with classical heuristic search, by reusing information from previous searches to speed up its current search. There are two classes of incremental heuristic search algorithms, namely those that make the $$h$$ h -values of the current search more informed (such as Adaptive A*) and those that reuse parts of the A* search trees of previous searches during the current search (such as D* Lite). In this article, we introduce Path-Adaptive A* and its generalization Tree-Adaptive A*. Both incremental heuristic search algorithms terminate their searches before they expand the goal state, namely when they expand a state that is on a provably cost-minimal path to the goal. Path-Adaptive A* stores a single cost-minimal path to the goal state (the reusable path), while Tree-Adaptive A* stores a set of cost-minimal paths to the goal state (the reusable tree), and is thus potentially more efficient than Path-Adaptive A* since it uses information from all previous searches and not just the last one. Tree-Adaptive A* is the first incremental heuristic search algorithm that combines the principles of both classes of incremental heuristic search algorithms. We demonstrate experimentally that both Path-Adaptive A* and Tree-Adaptive A* can be faster than Adaptive A* and D* Lite, two state-of-the-art incremental heuristic search algorithms for goal-directed navigation with the freespace assumption. The Author(s), 2014 Situated-agent nationallicence Planning nationallicence Path-planning nationallicence Incremental-heuristic-search nationallicence Hernández Carlos Departamento de Ingeniería Informática, Universidad Católica de la Ssma. Concepción, Concepción, Chile aut Uras Tansel Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA aut Koenig Sven Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA aut Baier Jorge Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Santiago, Chile aut Sun Xiaoxun Google, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA aut Meseguer Pedro IIIA - CSIC, Campus Universitat Autonòma de Barcelona, 08193, Bellaterra, Spain aut Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 850-895 1387-2532 29:5<850 2015 29 10458 https://doi.org/10.1007/s10458-014-9266-0 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10458-014-9266-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Hernández Carlos Departamento de Ingeniería Informática, Universidad Católica de la Ssma. Concepción, Concepción, Chile aut NATIONALLICENCE 700 1- Uras Tansel Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Koenig Sven Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Baier Jorge Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Santiago, Chile aut NATIONALLICENCE 700 1- Sun Xiaoxun Google, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA aut NATIONALLICENCE 700 1- Meseguer Pedro IIIA - CSIC, Campus Universitat Autonòma de Barcelona, 08193, Bellaterra, Spain aut NATIONALLICENCE 773 0- Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 850-895 1387-2532 29:5<850 2015 29 10458