##
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.