Computer Science – Artificial Intelligence
Scientific paper
2011-10-31
Journal Of Artificial Intelligence Research, Volume 31, pages 497-542, 2008
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.2408
Multi-robot path planning is difficult due to the combinatorial explosion of the search space with every new robot added. Complete search of the combined state-space soon becomes intractable. In this paper we present a novel form of abstraction that allows us to plan much more efficiently. The key to this abstraction is the partitioning of the map into subgraphs of known structure with entry and exit restrictions which we can represent compactly. Planning then becomes a search in the much smaller space of subgraph configurations. Once an abstract plan is found, it can be quickly resolved into a correct (but possibly sub-optimal) concrete plan without the need for further search. We prove that this technique is sound and complete and demonstrate its practical effectiveness on a real map. A contending solution, prioritised planning, is also evaluated and shown to have similar performance albeit at the cost of completeness. The two approaches are not necessarily conflicting; we demonstrate how they can be combined into a single algorithm which outperforms either approach alone.
No associations
LandOfFree
Exploiting Subgraph Structure in Multi-Robot Path Planning does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exploiting Subgraph Structure in Multi-Robot Path Planning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exploiting Subgraph Structure in Multi-Robot Path Planning will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-466735