Graph decomposition for efficient multi-robot path planning

Abstract

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.