Graph decomposition for efficient multi-robot path planning

Malcolm Ryan*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

48 Citations (Scopus)


In my previous paper (Ryan, 2006) I introduced the concept of subgraph decomposition as a means of reducing the search space in multi-robot planning problems. I showed how partitioning a roadmap into subgraphs of known structure allows us to first plan at a level of abstraction and then resolve these plans into concrete paths without the need for further search so we can solve significantly harder planning tasks with the same resources. However the subgraph types I introduced in that paper, stacks and cliques, are not likely to occur often in realistic planning problems and so are of limited usefulness. In this paper I describe a new kind of subgraph called a hall, which can also be used for planning and which occurs much more commonly in real problems. I explain its formal properties as a planning component and demonstrate its use on a map of the Patrick's container yard at the Port of Brisbane in Queensland Australia.

Original languageEnglish
Title of host publicationProceedings of the twentieth international joint conference on artificial intelligence
Place of PublicationCalifornia
PublisherInternational Joint Conferences on Artificial Intelligence
Number of pages6
Publication statusPublished - 2007
Externally publishedYes
EventTwentieth International Joint Conference on Artificial Intelligence - Hyderabad, India
Duration: 6 Jan 200712 Jan 2007


ConferenceTwentieth International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI-07


Dive into the research topics of 'Graph decomposition for efficient multi-robot path planning'. Together they form a unique fingerprint.

Cite this