  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.
