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

DOI10.1007/978-3-319-68167-2_30MaRDI QIDQ5096103zbMATH OpenOpenAlexFDO

Authors Shankara Narayanan Krishna, Aviral Kumar, Fabio Somenzi, Behrouz Touri, Ashutosh Trivedi

Publication date 12 August 2022

Published in Automated Technology for Verification and Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.04151

Mathematics Subject Classification ID

Attainable sets, reachability (93B03) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

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

Recommendations

• Global Almost-Sure Reachability in Stochastic Constant-Rate Multi-Mode Systems
• Probabilistic reach-avoid problems in nondeterministic systems with time-varying targets and obstacles
• Avoidance trajectories using reachable sets and parametric sensitivity analysis
• Revisiting underapproximate reachability for multipushdown systems
• Bounded-rate multi-mode systems based motion planning
• The linear programming approach to reach-avoid problems for Markov decision processes
• Reach control problem for affine multi-agent systems on simplices
• Hybrid Systems: Computation and Control
• Probabilistic Reach-Avoid Computation for Partially Degenerate Stochastic Processes
• An algorithm for constructing reachable sets for systems with multiple integral constraints

Cited in

(1)

• The complexity of linear temporal verification for continuous counter systems

This page was built for publication: The Reach-Avoid Problem for Constant-Rate Multi-mode Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096103)