Abstract
Incremental heuristic search algorithms can solve sequences of similar search problems potentially faster than heuristic search algorithms that solve each search problem from scratch. So far, there existed incremental heuristic search algorithms (such as Adaptive A*) that make the h-values of the current A* search more informed, which can speed up future A* searches, and incremental heuristic search algorithms (such as D* Lite) that change the search tree of the current A* search to the search tree of the next A* search, which can be faster than constructing it from scratch. In this paper, we present Tree Adaptive A*, which applies to goal-directed navigation in unknown terrain and builds on Adaptive A* but combines both classes of incremental heuristic search algorithms in a novel way. We demonstrate experimentally that it can run faster than Adaptive A*, Path Adaptive A* and D* Lite, the top incremental heuristic search algorithms in the context of goal-directed navigation in unknown grids. Categories and Subject Descriptors 1.2.8 [Problem Solving, Control Methods, and Search]: [Graph and tree search strategies] General Terms Algorithms, Experimentation.
Original language | English |
---|---|
Title of host publication | 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 |
Publisher | International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS) |
Pages | 113-120 |
Number of pages | 8 |
Volume | 1 |
Publication status | Published - 2011 |
Event | 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China Duration: 2 May 2011 → 6 May 2011 |
Other
Other | 10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 |
---|---|
Country/Territory | Taiwan, Province of China |
City | Taipei |
Period | 2/05/11 → 6/05/11 |
Keywords
- Agent reasoning::Planning (single and multi-agent)
- Path planning
- Robot reasoning::Planning
ASJC Scopus subject areas
- Artificial Intelligence