Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using Increasing Cost Tree Search (Extended Abstract)
Full Text: 7243-30176-1-PB.pdf
The Increasing Cost Tree Search (ICTS) algorithm is used to produce optimal solutions to the multi-agent path finding problem (MAPF). In this problem, multiple agents are trying to reach their goals without conflicting with each other, while minimizing the total cost of the paths. ICTS has been shown to be very effective in finding optimal solutions. In this paper we consider the problem of finding solutions with bounded suboptimality by changing the order in which ICTS searches its increasing cost tree. With a variety of strategies, we are unable to consistently and significantly reduce the cost of ICTS. Further experimentation suggests why significantly more work is needed to modify ICTS to find suboptimal solutions.
Citation
F. Aljalaud, N. Sturtevant. "Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using Increasing Cost Tree Search (Extended Abstract)". Symposium on Combinatorial Search, (ed: Malte Helmert, Gabriele Röger), pp 203-204, July 2013.| Keywords: | search, multi-agent, path planning |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Aljalaud+Sturtevant:SoCS13,
author = {Faten Aljalaud and Nathan R. Sturtevant},
title = {Finding Bounded Suboptimal Multi-Agent Path Planning Solutions Using
Increasing Cost Tree Search (Extended Abstract)},
Editor = {Malte Helmert, Gabriele Röger},
Pages = {203-204},
booktitle = {Symposium on Combinatorial Search},
year = 2013,
}Last Updated: July 10, 2020Submitted by Sabina P
