A language for robot path planning in discrete environments: The TSP with Boolean satisfiability constraints
- 1 May 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10504729,p. 5772-5777
Abstract
In this paper we introduce a new language in which discrete path planning problems for mobile robots can be specified and solved. Given an environment represented as a graph and a Boolean variable for each vertex to represent its inclusion/exclusion on the path, we consider the problem of finding the shortest path (or tour) in the graph subject to a Boolean satisfiability (Sat) formula defined over the vertex variables. We call this problem Sat-Tsp. We show the expressiveness of this language for specifying complex motion planning objectives in a discrete environment. We then present three solution techniques for this problem, including a novel reduction to the well known travelling salesman problem (Tsp). We present extensive simulation results which compare the performance of the three solvers on standard benchmarks from Tsp, Sat, and Generalized Tsp (Gtsp) literature.Keywords
This publication has 11 references indexed in Scilit:
- Optimal control of non-deterministic systems for a computationally efficient fragment of temporal logic2013
- Sampling-Based Path Planning for a Visual Reconnaissance Unmanned Air VehicleJournal of Guidance, Control, and Dynamics, 2012
- Optimal path planning for surveillance with temporal-logic constraintsThe International Journal of Robotics Research, 2011
- Temporal-Logic-Based Reactive Mission and Motion PlanningIEEE Transactions on Robotics, 2009
- A memetic algorithm for the generalized traveling salesman problemNatural Computing, 2009
- Discrete abstractions for robot motion planning and control in polygonal environmentsIEEE Transactions on Robotics, 2005
- Efficient translation of Boolean formulas to CNF in formal verification of microprocessors2004
- SAT v CSP2000
- TSPLIB—A Traveling Salesman Problem LibraryINFORMS Journal on Computing, 1991
- The complexity of propositional linear temporal logicsJournal of the ACM, 1985