Paper Info
Title
An SMT-Based Approach to Motion Planning for Multiple Robots With Complex Constraints
Abstract
In this paper, we propose a new method for solving multirobot motion planning problems with complex constraints. We focus on an important class of problems that require an allocation of spatially distributed tasks to robots, along with efficient paths for each robot to visits their task locations. We introduce a framework for solving these problems that naturally couples allocation with path planning. The allocation problem is encoded as a Boolean Satisfiability problem (SAT) and the path planning problem is encoded as a traveling salesman problem (TSP). In addition, the framework can handle complex constraints such as battery life limitations, robot carrying capacities, and robot-task incompatibilities. We propose an algorithm that leverages recent advances in Satisfiability Modulo Theory (SMT) to combine state-of-the-art SAT and TSP solvers. We characterize the correctness of our algorithm and evaluate it in simulation on a series of patrolling, periodic routing, and multirobot sample collection problems. The results show our algorithm significantly outperforms state-of-the-art mathematical programming solvers.
Year
DOI
Venue
2019
10.1109/tro.2019.2896401
IEEE Transactions on Robotics
Keywords
Field
DocType
Robot kinematics,Planning,Task analysis,Path planning,Robot sensing systems,Routing
Motion planning,Modulo,Correctness,Satisfiability,Boolean satisfiability problem,Robot kinematics,Control engineering,Theoretical computer science,Travelling salesman problem,Robot,Mathematics
Journal
Volume
Issue
ISSN
35
3
1552-3098
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Frank Imeson1533.74
Stephen L Smith2116383.01