Multi-robot path planning is dificult 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 eficiently. 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 effiectiveness 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 out-performs either approach alone.
@cite_21: Abstract Artificial intelligence (AI) research has developed an extensive collection of methods to solve state-space problems. Using the challenging domain of Sokoban, this paper studies the effect of general search enhancements on program performance. We show that the current state of the art in AI generally requires a large research and programming effort to use domain-dependent knowledge to solve even moderately complex problems in such difficult domains. The application of domain-specific knowledge to exploit properties of the search space can result in large reductions in the size of the search tree, often several orders of magnitude per search enhancement. This application-specific knowledge is discovered and applied using application-independent search enhancements. Understanding the effect of these enhancements on the search leads to a new taxonomy of search enhancements, and a new framework for developing single-agent search applications. This is used to illustrate the large gap between what is portrayed in the literature versus what is needed in practice.
@cite_7: Heuristic search has been successful for games like chess and checkers, but seems to be of limited value in games such as Go and shogi, and puzzles such as Sokoban. Other techniques are necessary to approach the performance that humans achieve in these hard domains. This paper explores using planning as an alternative problem-solving framework for Sokoban. Previous attempts to express Sokoban as a planning application led to poor performance results. Abstract Sokoban is introduced as a new planning formulation of the domain. The approach abstracts a Sokoban problem into rooms and tunnels. This allows for the decomposition of the hard initial problem into several simpler sub-problems, each of which can be solved efficiently. The experimental results show that the abstraction has the potential for an exponential reduction in the size of the search space explored.
The work that bears most similarity to our own is not explicitly in robot path planning, but in solving the Sokoban puzzle @cite_7 @cite_21 . That domain is significantly more constrained than ours (the map is necessarily an orthogonal grid and the stones can only move when they are pushed by the man) but the method they employ is similar. Dividing a map up into and they use the strongly-connected-component algorithm to identify equivalent arrangements of boulders in each subpart. Equivalent arrangements are then treated as a single abstract state -- corresponding to a configuration in our formulation -- which is used as the state in a global search. The particular structures they represent are different, but the general ideas of partitioning into independent local subproblems and identifying abstract states from strongly connected components, are the same as those employed in this work.