Redundancy Elimination in Highly Parallel Solutions of Motion Coordination Problems

Abstract

Problems of coordinated motion of multiple entities are addressed in this paper. These problems are dealt on the abstract level where they can be viewed as a task of constructing a spatial-temporal plan for a set of identical mobile entities. The entities are moving in a certain environment and they need to reach given goal positions starting from initial ones. The most abstract formal representations of coordinated motion problems are known as "pebble motion on a graph" and "multi-robot path planning". The existent state-of-the-art algorithms for pebble motion and multi-robot problems were suspected of generating solutions containing redundancies and this hypothesis eventually confirmed. It this paper, we present several techniques for identifying and eliminating redundancies from solutions generated by these algorithms. An extensive experimental evaluation was performed and it showed that the quality of generated solutions can be improved up to the order of magnitude. We also identify parameters characterizing instances of problems where the improvement is expectable.