Lagrangian approximations for stochastic reachability of a target tube. (English) Zbl 1461.93029
Summary: We consider the problem of stochastic reachability of a target tube for a discrete-time, stochastic dynamical system with bounded control authority. We propose grid-free algorithms to compute under- and over-approximations of the stochastic reach set, and a corresponding feedback-based controller associated with a given likelihood. Our approach employs set-theoretic (Lagrangian) techniques for nonlinear systems with affine stochastic disturbances. With available set computation tools, these algorithms can only be implemented on linear systems. We use the law of total probability to partition the potentially unbounded disturbance set, and compute minimal and maximal reach sets via a robust approach. We propose a heuristic to partition the disturbance set using an ellipsoid when the disturbance is Gaussian, and a polyhedron otherwise. For linear dynamics and convex and compact sets, we employ existing tools from support functions and robust linear programming to efficiently approximate the stochastic reach set. We synthesize an admissible controller using the disturbance minimal reach sets by solving a series of linear programs. We demonstrate our approach on systems with linear dynamics (time-invariant and time-varying) and arbitrary disturbances (as well as Gaussian), including trajectory following for a Dubin’s vehicle and space vehicle rendezvous and docking.
MSC:
| 93B03 | Attainable sets, reachability |
| 93E03 | Stochastic systems in control theory (general) |
| 93C55 | Discrete-time control/observation systems |
| 93C05 | Linear systems in control theory |
References:
| [1] | Abate, A.; Amin, S.; Prandini, M.; Lygeros, J.; Sastry, S., Computational approaches to reachability analysis of stochastic hybrid systems, (Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (2007)), 4-17 · Zbl 1221.93030 |
| [2] | Abate, A.; Prandini, M.; Lygeros, J.; Sastry, S., Probabilistic reachability and safety for controlled discrete time stochastic hybrid systems, Automatica, 44, 2724-2734 (2008) · Zbl 1152.93051 |
| [3] | Bak, S.; Duggirala, P. S., HyLAA: A tool for computing simulation-equivalent reachability for linear systems, (Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (2017)), 173-178 |
| [4] | Ben-Tal, A.; Goryashko, A.; Guslitzer, E.; Nemirovski, A., Adjustable robust solutions of uncertain linear programs, Mathematical Programming, 99, 2, 351-376 (2004) · Zbl 1089.90037 |
| [5] | Bertsekas, D., Dynamic programming and optimal control. vol. 1 (2005), Athena Scientific: Athena Scientific Belmont, MA · Zbl 1125.90056 |
| [6] | Bertsekas, D.; Rhodes, I., On the minimax reachability of target sets and target tubes, Automatica, 7, 2, 233-247 (1971) · Zbl 0215.21801 |
| [7] | Bertsekas, D. P.; Shreve, S. E., Stochastic optimal control: the discrete time case (1978), Academic Press · Zbl 0471.93002 |
| [8] | Billingsley, P., Probability and measure (1995), Wiley: Wiley New York · Zbl 0822.60002 |
| [9] | Blanchini, F.; Miani, S., Set-theoretic methods in control (2008), Birkhäuser · Zbl 1140.93001 |
| [10] | Borelli, F.; Bemporad, A.; Morari, M., Predictive control for linear and hybrid systems (2017), Cambridge Univ. Press · Zbl 1365.93003 |
| [11] | Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge Univ. Press · Zbl 1058.90049 |
| [12] | Cauchi, N.; Laurenti, L.; Lahijanian, M.; Abate, A.; Kwiatkowska, M.; Cardelli, L., Efficiency through uncertainty: scalable formal synthesis for stochastic hybrid systems, (Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (2019)), 240-251 · Zbl 1542.93107 |
| [13] | Genz, A., Numerical computation of multivariate normal probabilities, Journal of Computational and Graphical Statistics, 1, 2, 141-149 (1992) |
| [14] | Girard, A. (2005). Reachability of uncertain linear systems using zonotopes. In Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (pp. 291-305). · Zbl 1078.93005 |
| [15] | Gleason, J., Vinod, A., & Oishi, M. (2017). Underapproximation of reach-avoid sets for discrete-time stochastic systems via Lagrangian methods. In Proc. IEEE Conf. on Decision and Ctrl. (p.. 4283-4290). |
| [16] | Harman, R.; Lacko, V., On decompositional algorithms for uniform sampling from n-spheres and n-balls, Journal of Multivariate Analysis, 101, 10, 2297-2304 (2010) · Zbl 1205.65029 |
| [17] | Kariotoglou, N.; Kamgarpour, M.; Summers, T.; Lygeros, J., The linear programming approach to reach-avoid problems for Markov decision processes, Journal of Artificial Intelligence Research, 60, 263-285 (2017) · Zbl 1427.90286 |
| [18] | Kolmanovsky, I.; Gilbert, E. G., Theory and computation of disturbance invariant sets for discrete-time linear systems, Mathematical Problems in Engineering, 4, 317-367 (1998) · Zbl 0923.93005 |
| [19] | Kurzhanskiy, Alex A.; Varaiya, Pravin, Ellipsoidal toolboxTechnical report (2006), EECS Department, University of California: EECS Department, University of California Berkeley · Zbl 1366.93039 |
| [20] | Kwiatkowska, M., Norman, G., & Parker, D. (2011). PRISM 4.0: Verification of probabilistic real-time systems. In Proc. Int’l. Conf. on Computer Aided Verification, vol. 6806 (pp. 585-591). |
| [21] | Le Geurnic, C., Reachability analysis of hybrid systems with linear continuous dynamics (2009), Université Joseph-Fourier, (Ph.D. thesis) |
| [22] | Le Guernic, C.; Girard, A., Reachability analysis of linear systems using support functions, Nonlinear Analysis. Hybrid Systems, 4, 2, 250-262 (2010) · Zbl 1201.93018 |
| [23] | Lesser, K., Oishi, M., & Erwin, R. S. (2013). Stochastic reachability for control of spacecraft relative motion. In Proc. IEEE Conf. on Decision and Ctrl. (pp. 4705-4712). |
| [24] | Lipp, T.; Boyd, S., Variations and extension of the convex-concave procedure, Optimization and Engineering, 17, 2, 263-287 (2016) · Zbl 1364.90260 |
| [25] | Maidens, J. N.; Kaynama, S.; Mitchell, I. M.; Oishi, M. M.K.; Dumont, G. A., Lagrangian methods for approximating the viability kernel in high-dimensional systems, Automatica, 49, 7, 2017-2029 (2013) · Zbl 1364.93057 |
| [26] | Muller, M. E., A note on a method for generating points uniformly on n-dimensional spheres, Communications of the ACM, 2, 4, 19-20 (1959) · Zbl 0086.11605 |
| [27] | Rockafellar, R.; Wets, R., Variational analysis, vol. 317 (2009), Springer Science & Business Media |
| [28] | Sartipizadeh, H., Vinod, A., Açikmese, B., & Oishi, M. (2019). Voronoi partition-based scenario reduction for fast sampling-based stochastic reachability computation of LTI systems. In American Ctrl. Conf. (pp. 37-44). |
| [29] | Soudjani, S., Gevaerts, C., & Abate, A. (2015) FAUST \({}^2\) : Formal abstractions of uncountable-STate STochastic processes. In Tools and Alg. for the Construction and Analysis of Systems, vol. 15 (pp. 272-286). |
| [30] | Summers, S.; Kamgarpour, M.; Lygeros, J.; Tomlin, C., A stochastic reach-avoid problem with random obstacles, (Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (2011), ACM), 251-260 · Zbl 1364.93870 |
| [31] | Summers, S.; Lygeros, J., Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem, Automatica, 46, 1951-1961 (2010) · Zbl 1371.93220 |
| [32] | Tomlin, C. J.; Mitchell, I.; Bayen, A. M.; Oishi, M., Computational techniques for the verification of hybrid systems, Proceedings of the IEEE, 91, 7, 986-1001 (2003) |
| [33] | Vinod, A.; Gleason, J.; Oishi, M., SReachTools: A MATLAB stochastic reachability toolbox, (Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (2019)), 33-38 · Zbl 1542.93030 |
| [34] | Vinod, A.; Oishi, M., Scalable underapproximation for the stochastic reach-avoid problem for high-dimensional LTI systems using Fourier transforms, IEEE Control Systems Letters, 1, 2, 316-321 (2017) |
| [35] | Vinod, A., & Oishi, M. (2018). Scalable underapproximative verification of stochastic LTI systems using convexity and compactness. In Proc. Int’l. Conf. on Hybrid Systems: Comp. and Ctrl. (pp. 1-10). · Zbl 1417.93338 |
| [36] | Vinod, A., & Oishi, M. (2019). Affine controller synthesis for stochastic reachability via difference of convex programming. In Proc. IEEE Conf. on Decision and Ctrl. (pp. 7273-7280). |
| [37] | Vinod, A.; Oishi, M., Stochastic reachability of a target tube: Theory and computation, Automatica, 125 (2021), (in press) · Zbl 1461.93554 |
| [38] | Wiesel, W., Spaceflight dynamics (1989), McGraw-Hill |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
