# Reach-Avoid Problems via Sum-of-Squares Optimization and Dynamic Programming

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2018.

## Built on by (most cited first, 4 of 4)

- [Safe Occlusion-aware Autonomous Driving via Game-Theoretic Active Perception](https://mlsanity.com/paper/2105.08169/) (2021)
- [Safe Large-Scale Robust Nonlinear MPC in Milliseconds via Reachability-Constrained System Level Synthesis on the GPU](https://mlsanity.com/paper/2604.07644/) (2026)
- [Infinite-Horizon Reach-Avoid Zero-Sum Games via Deep Reinforcement Learning](https://mlsanity.com/paper/2203.10142/) (2022)
- [Neural Network-assisted Interval Reachability for Systems with Control Barrier Function-Based Safe Controllers](https://mlsanity.com/paper/2504.08249/) (2025)

## Abstract (arXiv)

Reach-avoid problems involve driving a system to a set of desirable configurations while keeping it away from undesirable ones. Providing mathematical guarantees for such scenarios is challenging but have numerous potential practical applications. Due to the challenges, analysis of reach-avoid problems involves making trade-offs between generality of system dynamics, generality of problem setups, optimality of solutions, and computational complexity. In this paper, we combine sum-of-squares optimization and dynamic programming to address the reach-avoid problem, and provide a conservative solution that maintains reaching and avoidance guarantees. Our method is applicable to polynomial system dynamics and to general problem setups, and is more computationally scalable than previous related methods. Through a numerical example involving two single integrators, we validate our proposed theory and compare our method to Hamilton-Jacobi reachability. Having validated our theory, we demonstrate the computational scalability of our method by computing the reach-avoid set of a system involving two kinematic cars.