An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning

Abstract

An abstraction of a problem of rearranging group of mobile robots is addressed in this paper (the problem of multi-robot path planning). The robots are moving in an environment in which they must avoid obstacles and each other. An abstraction where the environment is modeled as an undirected graph is adopted throughout this work. A case when the graph modeling the environment is biconnected is particularly studied. This paper puts into a relation the well known problems of moving pebbles on graphs (sliding box puzzles) with problems of multi-robot path planning. Theoretical results gained for problems of pebble motion on graphs are utilized for the development of algorithms for multi-robot path planning. As the optimization variant of both problems (a shortest solution is required) is known to be computationally hard (NP-hard), we concentrate on construction of sub-optimal solving procedures. However, the quality of solution is still an objective. Therefore a process of composition of a suboptimal solution of the problem (a plan) of the precalculated optimal plans for the sub-problems (macros) is suggested. The plan composition using macros was integrated into two existing sub-optimal solving algorithms. In both cases, substantial improvements of the quality of resulting plans were achieved in comparison to the original algorithms. The no less important result is that one of the existing algorithms was generalized by integrating macros for larger class of problems of multi-robot path planning.