Multi-robot task planning and sequencing using the SAT-TSP language

Abstract

The Sat-Tsp language was recently proposed [1] for expressing and solving high-level robotic path planning problems. In this paper we show how different constraints that commonly appear in path planning problems, such as set constraints, counting constraints, and ordering constraints can all be expressed in the Sat-Tsp language. We also show how the language can be used to express multi-robot path planning problems. We evaluate our existing solver approaches on test problems that include a variety of complex constraints and we demonstrate the language through a ROS implementation. We also provide a new approach that reduces the Sat-Tsp language to the generalized traveling salesman problem language. We show that this new approach outperforms our existing approaches on problems that contain one-on-a-set constraints.