# Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems

arXiv: https://arxiv.org/abs/2304.06876 · HTML: https://mlsanity.com/paper/2304.06876/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 36 references that are in the map.
- First posted on arXiv 14 Apr 2023.

## Builds on (most cited first, 8 of 8)

- [Contraction Theory for Nonlinear Stability Analysis and Learning-based Control: A Tutorial Overview](https://mlsanity.com/paper/2110.00675/) (2021)
- [FaSTrack: a Modular Framework for Fast and Guaranteed Safe Motion Planning](https://mlsanity.com/paper/1703.07373/) (2017)
- [Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation](https://mlsanity.com/paper/1809.07051/) (2018)
- [Let's Collaborate: Regret-based Reactive Synthesis for Robotic Manipulation](https://mlsanity.com/paper/2203.06861/) (2022)
- [Gaussian Belief Trees for Chance Constrained Asymptotically Optimal Motion Planning](https://mlsanity.com/paper/2202.12407/) (2022)
- [Planning with SiMBA: Motion Planning under Uncertainty for Temporal Goals using Simplified Belief Guides](https://mlsanity.com/paper/2210.10202/) (2022)
- [Chance-Constrained Motion Planning with Event-Triggered Estimation](https://mlsanity.com/paper/2210.07190/) (2022)
- [A Rapidly-Exploring Random Trees Motion Planning Algorithm for Hybrid Dynamical Systems](https://mlsanity.com/paper/2210.15082/) (2022)

## Abstract (arXiv)

This paper introduces a sampling-based strategy synthesis algorithm for nondeterministic hybrid systems with complex continuous dynamics under temporal and reachability constraints. We model the evolution of the hybrid system as a two-player game, where the nondeterminism is an adversarial player whose objective is to prevent achieving temporal and reachability goals. The aim is to synthesize a winning strategy -- a reactive (robust) strategy that guarantees the satisfaction of the goals under all possible moves of the adversarial player. Our proposed approach involves growing a (search) game-tree in the hybrid space by combining sampling-based motion planning with a novel bandit-based technique to select and improve on partial strategies. We show that the algorithm is probabilistically complete, i.e., the algorithm will asymptotically almost surely find a winning strategy, if one exists. The case studies and benchmark results show that our algorithm is general and effective, and consistently outperforms state of the art algorithms.