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

July 12, 2017 · The Ethereal · 🏛 Automated Technology for Verification and Analysis

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Shankara Narayanan Krishna, Aviral Kumar, Fabio Somenzi, Behrouz Touri, Ashutosh Trivedi arXiv ID 1707.04151 Category cs.LO: Logic in CS Cross-listed cs.FL, cs.RO Citations 5 Venue Automated Technology for Verification and Analysis Last Checked 5 months ago

Abstract

A constant-rate multi-mode system is a hybrid system that can switch freely among a finite set of modes, and whose dynamics is specified by a finite number of real-valued variables with mode-dependent constant rates. Alur, Wojtczak, and Trivedi have shown that reachability problems for constant-rate multi-mode systems for open and convex safety sets can be solved in polynomial time. In this paper, we study the reachability problem for non-convex state spaces and show that this problem is in general undecidable. We recover decidability by making certain assumptions about the safety set. We present a new algorithm to solve this problem and compare its performance with the popular sampling based algorithm rapidly-exploring random tree (RRT) as implemented in the Open Motion Planning Library (OMPL).