##
Almost-Sure Reachability in Stochastic Multi-Mode System.

* Fabio Somenzi, Behrouz Touri, and Ashutosh Trivedi *

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. We introduce and
study a stochastic extension of a constant-rate multi-mode system where the
dynamics is specified by mode-dependent compactly supported probability
distributions over a set of constant rate vectors. Given a tolerance ε > 0, the
almost- sure reachability problem for stochastic multi-mode systems is to decide
the existence of a control strategy that steers the system almost-surely from an
arbitrary start state to an ε-neighborhood of an arbitrary target state while
staying inside a pre-specified safety set. We prove a necessary and sufficient
condition to decide almost-sure reachability and, using this condition, we show
that almost-sure reachability can be decided in polynomial time. Our algorithm
can be used as a path-following algorithm in combination with any off-the-shelf
path-planning algorithm to make a robot with noisy low-level controllers follow
a given path with arbitrary precision.

*
Under review.
*

Email me for a copy of the paper © 2017.