# Stochastic Reachability Analysis and Controller Synthesis

Reachability analysis is powerful in its ability to provide assurances of safety despite bounded control authority and disturbances. However, for generic systems and constraints, computing the minimal reachable set (equivalently, the viability kernel) can be prohibitively expensive. We investigate techniques to improve the computational cost for certain classes of systems. Some of the techniques we have developed are based on structure decomposition, and involve solving multiple smaller reachability calculations. Other techniques use the efficient Lagrangian methods available for minimal reachable set calculation, by iteratively computing the maximal reachable set over small time horizons. With these techniques, viable sets can be computed for systems with several tens of states. Stochastic reachability analysis provides a minimum likelihood of safety, despite bounded control authority and stochastic disturbances. Computing stochastic reachable sets is also very computationally expensive. We have begun to investigate methods to compute stochastic viable sets for moderate dimensional systems. We are also developing optimal controllers for systems under incomplete information. We have applied these techniques to problems in safe delivery of automated anesteshia, aircraft flight management systems, and space vehicle docking.

### Related lab publications

Thorpe, Adam J., Kendric R. Ortiz, and Meeko MK Oishi. “Data-Driven Stochastic Reachability Using Hilbert Space Embeddings.” in *Automatica* 2021, accepted.

A. J. Thorpe and M. M. K. Oishi, “Model-Free Stochastic Reachability Using Kernel Distribution Embeddings,” in IEEE Control Systems Letters, vol. 4, no. 2, pp. 512-517, April 2020, doi: 10.1109/LCSYS.2019.2954102.

Abraham P. Vinod and Meeko Oishi, “Scalable Underapproximation for the Stochastic Reach-Avoid Problem for High-Dimensional LTI Systems Using Fourier Transforms,” *IEEE Control Systems Letters*, vol. 1, no. 2, June 2017, p. 316-321.

K. Lesser and M. Oishi, “Approximate Safety Verification and Control of Partially Observable Stochastic Hybrid Systems,” *IEEE Transactions on Automatic Control*, vol. 62, no. 1, pp. 81–96, 2017.

S. Kaynama, I.M. Mitchell, M. Oishi, G. Dumont, “Scalable Safety-Preserving Robust Control Synthesis for Continuous-Time Linear Systems,” *IEEE Transactions on Automatic Control*, vol. 60, no. 11, p. 3065-3070, March 2015.

K. Lesser and M. Oishi, “Reachability for Partially Observable Discrete Time Stochastic Hybrid Systems,” *Automatica*, vol. 50, no. 8, p. 1989-1998, August 2014.

S. Kaynama and M. Oishi, “A modified Riccati transformation for decentralized computation of the viability kernel under LTI dynamics,” *IEEE Transactions on Automatic Control*, vol. 58, no. 11, p. 2878-2892, November 2013.

I. Mitchell, S. Kaynama, M. Chen, and M. Oishi, “Safety preserving control synthesis for sampled data systems,” *Nonlinear Analysis: Hybrid Systems*, vol. 10, p. 63-82, November 2013.

J. Maidens, S. Kaynama, I. Mitchell, M. Oishi, and G. Dumont, “Lagrangian methods for computing the viability kernel in high-dimensional systems,” *Automatica*, vol. 49, no. 7, p. 2017-2029, July 2013.

S. Kaynama and M. Oishi, “Complexity reduction through a Schur-based decomposition for reachability analysis of linear time-invariant systems,” *International Journal of Control*, vol. 84, no. 1, p. 165-179, January 2011.

### Related lab conference proceedings

Thorpe, A.J., Ortiz, K.R. & Oishi, M.M.K., “Learning Approximate Forward Reachable Sets Using Separating Kernels,” *Proceedings of the 3rd Conference on Learning for Dynamics and Control*, in *Proceedings of Machine Learning Research* 144:201-212, 2021.

Thorpe, Adam J., Kendric R. Ortiz, and Meeko MK Oishi. “SReachTools Kernel Module: Data-Driven Stochastic Reachability Using Hilbert Space Embeddings of Distributions.” In the Proceedings of *IEEE International Conference on Decision and Control*, 2021, to appear.

A. J. Thorpe, V. Sivaramakrishnan and M. M. K. Oishi, “Approximate Stochastic Reachability for High Dimensional Systems,” 2021 American Control Conference (ACC), 2021, pp. 1287-1293, doi: 10.23919/ACC50511.2021.9483404.

Abraham Vinod and Meeko Oishi, “Exploiting Compactness and Convexity of Reach-Avoid Sets for Discrete-Time Stochastic LTI Systems for a Scalable Polytopic Underapproximation,” In the Proceedings of the *IEEE/ACM Hybrid Systems: Computation and Control Conference*, Porto, Portugal, April 2018, to appear.

Abraham Vinod, Baisravan HomChaudhuri, Christoph Hintz, Anup Parikh, Stephen P. Buerger, Meeko Oishi, Gregory Brunson, Shakeeb Ahmad, Rafael Fierro, “Coordinated Threat Intercept via Forward Stochastic Reachability,” In the Proceedings of the *American Control Conference*, Milwaukee, Wisconsin, June 2018, to appear.

Joseph Gleason, Abraham Vinod, and Meeko Oishi, “Underapproximation of Reach-Avoid Sets for Discrete-Time Stochastic Systems via Lagrangian Methods,” In the Proceedings of *IEEE International Conference on Decision and Control*, Melbourne, Australia, December 2017.

Abraham Vinod and Meeko Oishi, “Scalable Underapproximation for Stochastic Reach-Avoid Problem for High-Dimensional LTI Systems using Fourier Transforms,” In the Proceedings of *IEEE International Conference on Decision and Control*, Melbourne, Australia, December 2017.

B. HomChaudhuri, A. Vinod, M. Oishi, “Computation of forward stochastic reach sets: Application to stochastic, dynamic obstacle avoidance,” In the Proceedings of *American Control Conference*, Seattle, WA, May 2017, p. 4404-4411.

A. Vinod, B. HomChaudhuri, and M. Oishi, “Forward stochastic reachability analysis for uncontrolled linear systems using Fourier Transforms,” In the Proceedings of the International Conference on Hybrid Systems: Computation and Control, Pittsburgh, PA, April 2017, p. 35-44. **Best Student Paper Award.**

B. HomChaudhuri, M. Oishi, M. Baldwin, M. Shubert, and R.S. Erwin, “Computing reach-avoid sets for space vehicle docking under continuous thrust,” In the Proceedings of *IEEE International Conference on Decision and Control*, Las Vegas, NV, December 2016, p. 3312-3318.

J. Gleason, A.P. Vinod, M. Oishi, and R.S. Erwin, “Viable set approximation for linear-Gaussian systems with unknown, bounded variance,” In the Proceedings of *IEEE International Conference on Decision and Control*, Las Vegas, NV, December 2016, 7049-7055.

K. Lesser and M. Oishi, “Computing Probabilistic Viable Sets for Partially Observable Systems using Truncated Gaussians and Adaptive Gridding,” In the Proceedings of *American Control Conference *Chicago, IL, July 2015, p. 1505-1512.

K. Lesser and M. Oishi, “Finite State Approximation for Verification of Partially Observable Stochastic Hybrid Systems,” In the Proceedings of *Hybrid Systems: Computation and Control,* Seattle, WA, April 2015, p. 159-168.

T. Biswas, K. Lesser, M. Oishi, R. Dutta, “Using Linear System Reliability to Obtain Theoretical Understanding of Wireless Routing,” In the Proceedings of the *IEEE Global Communications Conference (GLOBECOM)*, Austin, TX, December 2014, p. 1310-1316.

K. Lesser, M. Oishi, and R.S. Erwin, “Stochastic reachability for control of spacecraft relative motion,” In the *Proceedings of the IEEE Conference on Decision and Control,* Florence, Italy, December 2013, p. 4705-4712.

S. Kaynama, M. Oishi, I.M. Mitchell, and G. Dumont, “Fixed-complexity piecewise ellipsoidal representation of the continual reachability set based on ellipsoidal techniques,” In the *Proceedings of the American Control Conference,* Montreal, QB, June 2012, p. 2425-2430.

I.M. Mitchell, M. Chen, and M. Oishi, “Ensuring safety of nonlinear sampled data systems through reachability,” In the Proceedings of the *IFAC Conference on Analysis and Design of Hybrid Systems,* TU Eindhoven, Netherlands, June 2012, p. 108-114.

S. Kaynama, M. Oishi, I.M. Mitchell, and G. Dumont, “Computing the viability kernel using maximal reachable sets,” In the Proceedings of *Hybrid Systems: Computation and Control,* Beijing, China, April 2012, p. 55-63.

S. Kaynama, M. Oishi, I.M. Mitchell, and G. Dumont, “Continual reachability set and its computation using maximal reachability techniques,” In the *Proceedings of the IEEE Conference on Decision and Control*, Orlando, FL, December 2011, p. 6110-6115.

N. Matni, M. Oishi, “Stability of switched block upper-triangular linear systems with bounded switching delay: Application to large distributed systems,” In the *Proceedings of the American Control Conference,* San Francisco, CA, June 2011, p. 1440-1445.

S. Kaynama and M. Oishi, “Decomposing transformations for reachability analysis of linear time-invariant systems,” In the *Proceedings of the American Control Conference*, Baltimore, MD, June 2010, p. 1874-1879.

S. Kaynama and M. Oishi, “Schur-based decomposition for reachability analysis and controller synthesis,” In the *Proceedings of the IEEE Conference on Decision and Control*, Shanghai, China, December 2009, p. 69-74.

N. Matni and M. Oishi, “Reachability-based abstraction for an aircraft landing under shared control,” In the *Proceedings of the American Control Conference*, Seattle, WA, June 2008, pp. 2278-2284.

### Related lab technical reports

A. Vinod, B. HomChaudhuri, C. Hintz, A. Parikh, S. P. Buerger, J. Salton, D. Novick, M. Oishi, and R. Fierro, “Aerial suppression of airborne platforms (ASAP): Coordinated capture of a threat uas via stochastic reachability,” in *International Symposium on Aerial Robotics*, University of Pennsylvania, Philadelphia, PA, June 2017.