On Pebble Motion on Graphs and Abstract Multirobot Path Planning
Pavel Surynek · 2009
A problem of rearranging a group of robots that are moving in a certain environment is addressed in this paper (multi1 robot path planning). A case when a graph modeling the en1 vironment is bi1connected is particularly studied. The paper puts into a relation the well known problems of moving pebbles on graphs (sliding box puzzles) with problems of multi1robot path planning. Theoretical results gained for problems of pebble motion on graphs are utilized for the de1 velopment of algorithms for multi1robot path planning. As the optimization variant of both problems (a shortest solu1 tion is required) is known to be computationally hard ( �P� hard), we concentrate on construction of sub1optimal solv1 ing procedures. However, the quality of solution is still an objective. A process of a composition of a sub1optimal solu1 tion of the problem of multi1robot path planning (a plan) of the pre1calculated optimal plans for the sub1proble ms (ma1 cros) is suggested. The plan composition using macros was integrated into two existing sub1optimal solving algorithms. In both cases, substantial improvements of the quality of re1 sulting plans were achieved in comparison to the original versions. The no less important result is that one of the ex1 isting algorithms was generalized by integrating macros for a larger class of problems of multi1robot path planning.