Thumbnail

Partial Move A*

Cazenave, Tristan (2010), Partial Move A*, 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010 - proceedings, IEEE, p. 25-31

View/Open
Type
Communication / Conférence
Date
2010
Conference title
22th International Conference on Tools with Artificial Intelligence
Conference date
2010-10
Conference city
Arras
Conference country
France
Book title
22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010 - proceedings
Publisher
IEEE
ISBN
978-1-4244-8817-9
Pages
25-31
Publication identifier
Metadata
Show full item record
Author(s)
Cazenave, Tristan
Abstract (EN)
Some shortest path problems that can be solved using the A* algorithm have a large branching factor due to the combination of multiple choices at each move. Multiple sequence alignment and multi-agent pathfinding are examples of such problems. If the search can be stopped after each choice instead of being stopped at each combination of choices, it takes much less memory and much less time. The goal of the paper is to show that Partial Move A* is much better than A* for these problems when the branching factor is large due to a large combination of choices at each move. When there is such a large combination of choices at each move, Partial Move A* can yield large memory gains and speedups over regular A*.
Subjects / Keywords
A*; Partial Move A*; shortest path problem