Reach-Avoid Problem for Constant-Rate Multi-Mode Systems.


Krishna S., Aviral Kumar, Fabio Somenzi, Behrouz Touri, and Ashutosh Trivedi

The classical piano mover’s problem—of moving a piano without hitting obstacles—and its variants are paradigms of motion planning problems and have been extensively studied in robotics and artificial intelligence. A number of practical solutions exists ranging from "best-effort" sampling-based techniques such as rapidly exploring random trees and dense trees, to "complete" combinatorial techniques such as cylindrical algebraic decomposition algorithm and Canny’s algorithm. The general motion planning problem with polyhedral obstacles was shown (Reif 1979) to be PSPACE-complete and a form of planning under uncertainty in 3D environment is known (Canny and Reif 1987, and Canny 1988) to be NEXPTIME-hard. In this paper we take a fresh look at this classical problem, and give a precise boundary between decidable and undecidable motion planning problems for systems with simple and natural dynamics. For this purpose we consider constant-rate multi-mode systems and study reach-while-avoid problem for point-objects with obstacles given by linear inequalities. We show that this problem is in general undecidable, and we recover decidability by making certain assumptions about the obstacles. We also present a new algorithm to solve this problem and compare the performance with sampling based algorithms.



Under review.
Email me for a copy of the paper © 2017.