Abstract
Satellite systems are beginning to incorporate complex autonomous operations, which calls for rigorous reliability assurances. Human operators usually plan satellite maneuvers in detail, but autonomous operation will require software to make decisions using noisy sensor data and problem solutions with numerical inaccuracies. For such systems, formal verification guarantees are particularly attractive. This paper presents automatic verification techniques for providing assurances in satellite maneuvers. The specific reliability criteria studied are rendezvous and conjunction avoidance for two satellites performing orbital transfers. Three factors pose challenges for verifying satellite systems: (a) incommensurate orbits, (b) uncertainty of orbital parameters after thrusting, and (c) nonlinear dynamics. Three abstractions are proposed for contending with these challenges: (a) quotienting of the state-space based on periodicity of the orbital dynamics, (b) aggregation of similar transfer orbits, and (c) overapproximation of nonlinear dynamics using hybridization. The method’s feasibility is established via experiments with a prototype tool that computes the abstractions and uses existing hybrid systems model checkers.
Most of this research was conducted under the Air Force’s 2011 Summer Faculty Fellowship Program and Space Scholars Program at the Air Force Research Laboratory at Kirtland Air Force Base. The Illinois researchers were also supported by NSF CAREER Grant 1054247.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allgeier, S.E., Fitz-Coy, N.G., Erwin, R.S., Lovell, T.A.: Metrics for mission planning of formation flight. In: Proc. AAS/AIAA Astrodynamics Specialist Conference, Girdwood, AK (July 2011)
Althoff, M., Stursberg, O., Buss, M.: Reachability analysis of nonlinear systems with uncertain parameters using conservative linearization. In: 47th IEEE Conference on Decision and Control (CDC), pp. 4042–4048 (December 2008)
Althoff, M., Le Guernic, C., Krogh, B.H.: Reachable set computation for uncertain time-varying linear systems. In: Hybrid Systems: Computation and Control (HSCC), pp. 93–102. ACM, New York (2011)
Althoff, M., Rajhans, A., Krogh, B., Yaldiz, S., Li, X., Pileggi, L.: Formal verification of phase-locked loops using reachability analysis and continuization. In: IEEE/ACM International Conference on Computer-Aided Design, ICCAD (2011)
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T.A., Ho, P.-H., Nicollin, X., Olivero, A., Sifakis, J., Yovine, S.: The algorithmic analysis of hybrid systems. Theoretical Computer Science 138(1), 3–34 (1995)
Asarin, E., Dang, T., Girard, A.: Hybridization methods for the analysis of nonlinear systems. Acta Informatica 43, 451–476 (2007)
Bate, R.R., Mueller, D.D., White, J.E.: Fundamentals of Astrodynamics. Dover (1971)
Battin, R.H.: An introduction to the mathematics and methods of astrodynamics. AIAA education series. American Institute of Aeronautics and Astronautics (1999)
Bosse, A.B., Barnds, W.J., Brown, M.A., Creamer, N.G., Feerst, A., Henshaw, C.G., Hope, A.S., Kelm, B.E., Klein, P.A., Pipitone, F., Plourde, B.E., Whalen, B.P.: Sumo: Spacecraft for the Universal Modification of Orbits. In: Proc. of SPIE, vol. 5419, pp. 36–46 (2004)
Dang, T., Maler, O., Testylier, R.: Accurate hybridization of nonlinear systems. In: Hybrid Systems: Computation and Control (HSCC), pp. 11–20. ACM, New York (2010)
Flieller, D., Riedinger, P., Louis, J.P.: Computation and stability of limit cycles in hybrid systems. Nonlinear Analysis: Theory, Methods, & Applications 64(2), 352–367 (2006)
Frehse, G.: PHAVer: Algorithmic Verification of Hybrid Systems Past HyTech. In: Morari, M., Thiele, L. (eds.) HSCC 2005. LNCS, vol. 3414, pp. 258–273. Springer, Heidelberg (2005)
Frehse, G., Le Guernic, C., Donzé, A., Cotton, S., Ray, R., Lebeltel, O., Ripado, R., Girard, A., Dang, T., Maler, O.: SpaceEx: Scalable Verification of Hybrid Systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 379–395. Springer, Heidelberg (2011)
Gurfil, P., Kholshevnikov, K.V.: Manifolds and metrics in the relative spacecraft motion problem. Journal of Guidance Control and Dynamics 29(4), 1004–1010 (2006)
Henzinger, T.A., Ho, P.-H., Wong-Toi, H.: Hytech: a model checker for hybrid systems. Journal on Software Tools for Technology Transfer 1, 110–122 (1997)
Kaynar, D.K., Lynch, N., Segala, R., Vaandrager, F.: The Theory of Timed I/O Automata. Synthesis Lectures in Computer Science. Morgan & Claypool (2006)
Kurzhanskiy, A.A., Varaiya, P.: Ellipsoidal toolbox. In: 45th IEEE Conference on Decision and Control (CDC), pp. 1498–1503 (December 2006)
Lynch, N., Segala, R., Vaandrager, F.: Hybrid i/o automata. Inf. Comput. 185(1), 105–157 (2003)
Masur, H., Tabachnikov, S.: Rational billiards and flat structures. In: Hasselblatt, B., Katok, A. (eds.) Handbook of Dynamical Systems, Handbook of Dynamical Systems, vol. 1 Part A, ch. 13, pp. 1015–1089. Elsevier Science (2002)
Ocampo, C.: Finite burn maneuver modeling for a generalized spacecraft trajectory design and optimization system. Annals of the New York Academy of Sciences 1017(1), 210–233 (2004)
Römgens, B.A., Mooij, E., Naeije, M.C.: Verified interval orbit propagation in satellite collision avoidance. In: Proc. AIAA Guidance, Navigation, and Control, Portland, OR (2011)
Vallado, D.A., McClain, W.D.: Fundamentals of astrodynamics and applications. Space technology library. Microcosm Press (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johnson, T.T., Green, J., Mitra, S., Dudley, R., Erwin, R.S. (2012). Satellite Rendezvous and Conjunction Avoidance: Case Studies in Verification of Nonlinear Hybrid Systems. In: Giannakopoulou, D., Méry, D. (eds) FM 2012: Formal Methods. FM 2012. Lecture Notes in Computer Science, vol 7436. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32759-9_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-32759-9_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32758-2
Online ISBN: 978-3-642-32759-9
eBook Packages: Computer ScienceComputer Science (R0)