Reusing cost-minimal paths for goal-directed navigation in partially known terrains
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 605514836 | ||
| 003 | CHVBK | ||
| 005 | 20210128100706.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150901xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s10458-014-9266-0 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s10458-014-9266-0 | ||
| 245 | 0 | 0 | |a Reusing cost-minimal paths for goal-directed navigation in partially known terrains |h [Elektronische Daten] |c [Carlos Hernández, Tansel Uras, Sven Koenig, Jorge Baier, Xiaoxun Sun, Pedro Meseguer] |
| 520 | 3 | |a 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. | |
| 540 | |a The Author(s), 2014 | ||
| 690 | 7 | |a Situated-agent |2 nationallicence | |
| 690 | 7 | |a Planning |2 nationallicence | |
| 690 | 7 | |a Path-planning |2 nationallicence | |
| 690 | 7 | |a Incremental-heuristic-search |2 nationallicence | |
| 700 | 1 | |a Hernández |D Carlos |u Departamento de Ingeniería Informática, Universidad Católica de la Ssma. Concepción, Concepción, Chile |4 aut | |
| 700 | 1 | |a Uras |D Tansel |u Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Koenig |D Sven |u Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA |4 aut | |
| 700 | 1 | |a Baier |D Jorge |u Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Santiago, Chile |4 aut | |
| 700 | 1 | |a Sun |D Xiaoxun |u Google, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA |4 aut | |
| 700 | 1 | |a Meseguer |D Pedro |u IIIA - CSIC, Campus Universitat Autonòma de Barcelona, 08193, Bellaterra, Spain |4 aut | |
| 773 | 0 | |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/5(2015-09-01), 850-895 |x 1387-2532 |q 29:5<850 |1 2015 |2 29 |o 10458 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s10458-014-9266-0 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s10458-014-9266-0 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Hernández |D Carlos |u Departamento de Ingeniería Informática, Universidad Católica de la Ssma. Concepción, Concepción, Chile |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Uras |D Tansel |u Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Koenig |D Sven |u Computer Science Department, University of Southern California, 90089-0781, Los Angeles, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Baier |D Jorge |u Departamento de Ciencia de la Computación, Pontificia Universidad Católica de Chile, Santiago, Chile |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Sun |D Xiaoxun |u Google, 1600 Amphitheatre Parkway, 94043, Mountain View, CA, USA |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Meseguer |D Pedro |u IIIA - CSIC, Campus Universitat Autonòma de Barcelona, 08193, Bellaterra, Spain |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Autonomous Agents and Multi-Agent Systems |d Springer US; http://www.springer-ny.com |g 29/5(2015-09-01), 850-895 |x 1387-2532 |q 29:5<850 |1 2015 |2 29 |o 10458 | ||