April  2014, 10(2): 443-460. doi: 10.3934/jimo.2014.10.443

Computation of bang-bang and singular controls in collision avoidance

1. 

Institute of Computational and Applied Mathematics, University of Muenster, Einsteinstr. 62, D-48149 Muenster, Germany

2. 

CSIRO Computational Informatics, Locked Bag 17, North Ryde NSW 1670, Australia

3. 

CSIRO Computational Informatics, GPO Box 664, Canberra ACT 2601, Australia

Received  November 2012 Revised  August 2013 Published  October 2013

We study optimal cooperative collision avoidance strategies for two participants in a planar close proximity encounter. Previous research focused on special cases of this problem and showed that bang-bang strategies without switching are optimal in most situations, while singular controls only appear for the case of participants with unequal linear speeds under certain conditions. This paper extends the earlier analyses to a general case of a coplanar close proximity encounter, for which both parameters of the problem may take arbitrary admissible values. For such a case, we present a theoretical and numerical study of the structure of optimal controls. We prove that both controls can not be singular simultaneously and that the only possible singular control is a zero control. We derive formulas for the singular surfaces and verify that sufficient conditions hold for the computed extremal solutions. We identify different types of structural changes of the control strategies and show how the control structure changes with the change in the model parameters and initial conditions.
Citation: Helmut Maurer, Tanya Tarnopolskaya, Neale Fulton. Computation of bang-bang and singular controls in collision avoidance. Journal of Industrial and Management Optimization, 2014, 10 (2) : 443-460. doi: 10.3934/jimo.2014.10.443
References:
[1]

M. S. Aronna, J. F. Bonnans, A. V. Dmitruk and P. A. Lotito, Quadratic conditions for bang-singular extremals, Numer. Algebra Control Optim., 2 (2012), 511-546. doi: 10.3934/naco.2012.2.511.

[2]

M. S. Aronna, Second Order Analysis of Optimal Control Problems with Singular Arcs. Optimality Conditions and Shooting Algorithm, Ph.D thesis, ÉEcole Polytechnique Palaiseau, France, 2011.

[3]

C. Büskens, Optimierungsmethoden und Sensitivitätsanalyse für optimale Steuerprozesse mit Steuer- und Zustands-Beschränkungen, Ph.D thesis, Institut für Numerische Mathematik, Universität Münster, Münster, Germany, 1998.

[4]

C. Büskens and H. Maurer, SQP-methods for solving optimal control problems with control and state constraints: Adjoint variables, sensitivity analysis and real-time control. SQP-based direct discretization methods for practical optimal control problems, J. Comput. Appl. Math., 120 (2000), 85-108. doi: 10.1016/S0377-0427(00)00305-8.

[5]

C. Büskens and H. Maurer, Sensitivity analysis and real-time optimization of parametric nonlinear programming problems, in Online Optimization of Large Scale Systems (eds. M. Gr\"otschel, S. O. Krumke and J. Rambau), Springer, Berlin, 2001, 3-16.

[6]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Duxbury Press, Brooks-Cole Publishing, 1993.

[7]

M. Hestens, Calculus of Variations and Optimal Control Theory, John Wiley & Sons, Inc., New York-London-Sydney, 1966.

[8]

A. J. Krener, The high order maximum principle and its application to singular extremals, SIAM J. Control and Optimization, 15 (1977), 256-293. doi: 10.1137/0315019.

[9]

H. Maurer, Numerical solution of singular control problems using multiple shooting methods, J. Optimization Theory and Applications, 18 (1976), 235-257. doi: 10.1007/BF00935706.

[10]

H. Maurer, C. Büskens, J.-H. R. Kim and Y. Kaya, Optimization methods for the verification of second-order sufficient conditions for bang-bang controls, Optimal Control Appl. Methods, 26 (2005), 129-156. doi: 10.1002/oca.756.

[11]

H. Maurer and H. J. Oberle, Second order sufficient conditions for optimal control problems with free final time: The Riccati approach, SIAM J. Control and Optim., 41 (2002), 380-403. doi: 10.1137/S0363012900377419.

[12]

H. Maurer, T. Tarnopolskaya and N. L. Fulton, Singular controls in optimal collision avoidance for participants with unequal linear speeds, ANZIAM J., 53 (2012), C1-C19.

[13]

H. Maurer, T. Tarnopolskaya and N. L. Fulton, Optimal bang-bang and singular controls in collision avoidance for participants with unequal linear speeds, in 51st IEEE Conference on Decision and Control (CDC), Maui, USA, 2012, 7697-7702. doi: 10.1109/CDC.2012.6426792.

[14]

A. W. Merz, Optimal aircraft collision avoidance, in Proceedings of the Joint Automatic Control Conference, Paper 15-3, 1973, 449-454.

[15]

A. W. Merz, Optimal evasive manoeuvres in maritime collision avoidance, Navigation, 20 (1973), 144-152.

[16]

H. J. Oberle, Numerical computation of singular control functions in trajectory optimization problems, J. of Guidance, Control and Dynam., 13 (1990), 153-159. doi: 10.2514/3.20529.

[17]

N. P. Osmolovskii and H. Maurer, Applications to Regular and Bang-Bang Control. Second-Order Necessary and Sufficient Optimality Conditions in Calculus of Variations and Optimal Control, Advances in Control and Design, Vol. 24, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2012. doi: 10.1137/1.9781611972368.

[18]

N. P. Osmolovskii and H. Maurer, Equivalence of second order optimality conditions for bang-bang control problems. I. Main results, Control and Cybernetics, 34 (2005), 927-950; II. Proofs, variational derivatives and representations, Control and Cybernetics, 36 (2007), 5-45.

[19]

L. S. Pontryagin, W. G. Boltyanski, R. V. Gamkrelidze and E. F. Mishchenko, The Mathematical Theory of Optimal Processes, Wiley, New York, 1965.

[20]

T. Tarnopolskaya and N. L. Fulton, Optimal cooperative collision avoidance strategy for coplanar encounter: Merz's solution revisited, J. Optim. Theory Appl., 140 (2009), 355-375. doi: 10.1007/s10957-008-9452-9.

[21]

T. Tarnopolskaya and N. L. Fulton, Parametric behavior of the optimal control solution for collision avoidance in a close proximity encounter, in 18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation (eds. R. S. Andersson et al.), 2009, 425-431.

[22]

T. Tarnopolskaya and N. L. Fulton, Synthesis of optimal control for cooperative collision avoidance for aircraft (ships) with unequal turn capabilities, J. Optim. Theory Appl., 144 (2010), 367-390. doi: 10.1007/s10957-009-9597-1.

[23]

T. Tarnopolskaya and N. L. Fulton, Dispersal curves for optimal collision avoidance in a close proximity encounter: A case of participants with unequal turn rates, in Lecture Notes in Engineering and Computer Science: Proceedings of The World Congress on Engineering 2010, WCE 2010, IAENG, 2010, 1789-1794.

[24]

T. Tarnopolskaya and N. L. Fulton, Non-unique optimal collision avoidance strategies for coplanar encounter of participants with unequal turn capabilities, IAENG Int. J. Appl. Math., 40 (2010), 289-296.

[25]

T. Tarnopolskaya and N. L. Fulton, Synthesis of optimal control for cooperative collision avoidance in a close proximity encounter: Special cases, in Proceedings of the 18th World Congress of the International Federation of Automatic Control (IFAC), Vol. 18, Milano, Italy, 2011, 9775-9781.

[26]

T. Tarnopolskaya, N. L. Fulton and H. Maurer, Synthesis of optimal bang-bang control for cooperative collision avoidance for aircraft (ships) with unequal linear speeds, J. Optim. Theory Appl., 155 (2012), 115-144. doi: 10.1007/s10957-012-0049-y.

[27]

G. Vossen, Numerische Lösungsmethoden, Hinreichende Optimalitätsbedingungen und Sensitivitätsanalyse für Optimale Bang-Bang und Singuläre Steuerungen, Ph.D thesis, Institut für Numerische und Angewandte Mathematik, Universität Münster, Münster, Germany, 2005.

[28]

G. Vossen, Switching time optimization for bang-bang and singular controls, J. Optim. Theory Appl., 144 (2010), 409-429. doi: 10.1007/s10957-009-9594-4.

[29]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57. doi: 10.1007/s10107-004-0559-y.

show all references

References:
[1]

M. S. Aronna, J. F. Bonnans, A. V. Dmitruk and P. A. Lotito, Quadratic conditions for bang-singular extremals, Numer. Algebra Control Optim., 2 (2012), 511-546. doi: 10.3934/naco.2012.2.511.

[2]

M. S. Aronna, Second Order Analysis of Optimal Control Problems with Singular Arcs. Optimality Conditions and Shooting Algorithm, Ph.D thesis, ÉEcole Polytechnique Palaiseau, France, 2011.

[3]

C. Büskens, Optimierungsmethoden und Sensitivitätsanalyse für optimale Steuerprozesse mit Steuer- und Zustands-Beschränkungen, Ph.D thesis, Institut für Numerische Mathematik, Universität Münster, Münster, Germany, 1998.

[4]

C. Büskens and H. Maurer, SQP-methods for solving optimal control problems with control and state constraints: Adjoint variables, sensitivity analysis and real-time control. SQP-based direct discretization methods for practical optimal control problems, J. Comput. Appl. Math., 120 (2000), 85-108. doi: 10.1016/S0377-0427(00)00305-8.

[5]

C. Büskens and H. Maurer, Sensitivity analysis and real-time optimization of parametric nonlinear programming problems, in Online Optimization of Large Scale Systems (eds. M. Gr\"otschel, S. O. Krumke and J. Rambau), Springer, Berlin, 2001, 3-16.

[6]

R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modeling Language for Mathematical Programming, Duxbury Press, Brooks-Cole Publishing, 1993.

[7]

M. Hestens, Calculus of Variations and Optimal Control Theory, John Wiley & Sons, Inc., New York-London-Sydney, 1966.

[8]

A. J. Krener, The high order maximum principle and its application to singular extremals, SIAM J. Control and Optimization, 15 (1977), 256-293. doi: 10.1137/0315019.

[9]

H. Maurer, Numerical solution of singular control problems using multiple shooting methods, J. Optimization Theory and Applications, 18 (1976), 235-257. doi: 10.1007/BF00935706.

[10]

H. Maurer, C. Büskens, J.-H. R. Kim and Y. Kaya, Optimization methods for the verification of second-order sufficient conditions for bang-bang controls, Optimal Control Appl. Methods, 26 (2005), 129-156. doi: 10.1002/oca.756.

[11]

H. Maurer and H. J. Oberle, Second order sufficient conditions for optimal control problems with free final time: The Riccati approach, SIAM J. Control and Optim., 41 (2002), 380-403. doi: 10.1137/S0363012900377419.

[12]

H. Maurer, T. Tarnopolskaya and N. L. Fulton, Singular controls in optimal collision avoidance for participants with unequal linear speeds, ANZIAM J., 53 (2012), C1-C19.

[13]

H. Maurer, T. Tarnopolskaya and N. L. Fulton, Optimal bang-bang and singular controls in collision avoidance for participants with unequal linear speeds, in 51st IEEE Conference on Decision and Control (CDC), Maui, USA, 2012, 7697-7702. doi: 10.1109/CDC.2012.6426792.

[14]

A. W. Merz, Optimal aircraft collision avoidance, in Proceedings of the Joint Automatic Control Conference, Paper 15-3, 1973, 449-454.

[15]

A. W. Merz, Optimal evasive manoeuvres in maritime collision avoidance, Navigation, 20 (1973), 144-152.

[16]

H. J. Oberle, Numerical computation of singular control functions in trajectory optimization problems, J. of Guidance, Control and Dynam., 13 (1990), 153-159. doi: 10.2514/3.20529.

[17]

N. P. Osmolovskii and H. Maurer, Applications to Regular and Bang-Bang Control. Second-Order Necessary and Sufficient Optimality Conditions in Calculus of Variations and Optimal Control, Advances in Control and Design, Vol. 24, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2012. doi: 10.1137/1.9781611972368.

[18]

N. P. Osmolovskii and H. Maurer, Equivalence of second order optimality conditions for bang-bang control problems. I. Main results, Control and Cybernetics, 34 (2005), 927-950; II. Proofs, variational derivatives and representations, Control and Cybernetics, 36 (2007), 5-45.

[19]

L. S. Pontryagin, W. G. Boltyanski, R. V. Gamkrelidze and E. F. Mishchenko, The Mathematical Theory of Optimal Processes, Wiley, New York, 1965.

[20]

T. Tarnopolskaya and N. L. Fulton, Optimal cooperative collision avoidance strategy for coplanar encounter: Merz's solution revisited, J. Optim. Theory Appl., 140 (2009), 355-375. doi: 10.1007/s10957-008-9452-9.

[21]

T. Tarnopolskaya and N. L. Fulton, Parametric behavior of the optimal control solution for collision avoidance in a close proximity encounter, in 18th World IMACS Congress and MODSIM09 International Congress on Modelling and Simulation (eds. R. S. Andersson et al.), 2009, 425-431.

[22]

T. Tarnopolskaya and N. L. Fulton, Synthesis of optimal control for cooperative collision avoidance for aircraft (ships) with unequal turn capabilities, J. Optim. Theory Appl., 144 (2010), 367-390. doi: 10.1007/s10957-009-9597-1.

[23]

T. Tarnopolskaya and N. L. Fulton, Dispersal curves for optimal collision avoidance in a close proximity encounter: A case of participants with unequal turn rates, in Lecture Notes in Engineering and Computer Science: Proceedings of The World Congress on Engineering 2010, WCE 2010, IAENG, 2010, 1789-1794.

[24]

T. Tarnopolskaya and N. L. Fulton, Non-unique optimal collision avoidance strategies for coplanar encounter of participants with unequal turn capabilities, IAENG Int. J. Appl. Math., 40 (2010), 289-296.

[25]

T. Tarnopolskaya and N. L. Fulton, Synthesis of optimal control for cooperative collision avoidance in a close proximity encounter: Special cases, in Proceedings of the 18th World Congress of the International Federation of Automatic Control (IFAC), Vol. 18, Milano, Italy, 2011, 9775-9781.

[26]

T. Tarnopolskaya, N. L. Fulton and H. Maurer, Synthesis of optimal bang-bang control for cooperative collision avoidance for aircraft (ships) with unequal linear speeds, J. Optim. Theory Appl., 155 (2012), 115-144. doi: 10.1007/s10957-012-0049-y.

[27]

G. Vossen, Numerische Lösungsmethoden, Hinreichende Optimalitätsbedingungen und Sensitivitätsanalyse für Optimale Bang-Bang und Singuläre Steuerungen, Ph.D thesis, Institut für Numerische und Angewandte Mathematik, Universität Münster, Münster, Germany, 2005.

[28]

G. Vossen, Switching time optimization for bang-bang and singular controls, J. Optim. Theory Appl., 144 (2010), 409-429. doi: 10.1007/s10957-009-9594-4.

[29]

A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2006), 25-57. doi: 10.1007/s10107-004-0559-y.

[1]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[2]

Karl Kunisch, Lijuan Wang. The bang-bang property of time optimal controls for the Burgers equation. Discrete and Continuous Dynamical Systems, 2014, 34 (9) : 3611-3637. doi: 10.3934/dcds.2014.34.3611

[3]

Karl Kunisch, Lijuan Wang. Bang-bang property of time optimal controls of semilinear parabolic equation. Discrete and Continuous Dynamical Systems, 2016, 36 (1) : 279-302. doi: 10.3934/dcds.2016.36.279

[4]

Walter Alt, Robert Baier, Matthias Gerdts, Frank Lempio. Error bounds for Euler approximation of linear-quadratic control problems with bang-bang solutions. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 547-570. doi: 10.3934/naco.2012.2.547

[5]

Gengsheng Wang, Yubiao Zhang. Decompositions and bang-bang properties. Mathematical Control and Related Fields, 2017, 7 (1) : 73-170. doi: 10.3934/mcrf.2017005

[6]

M. Soledad Aronna, J. Frédéric Bonnans, Andrei V. Dmitruk, Pablo A. Lotito. Quadratic order conditions for bang-singular extremals. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 511-546. doi: 10.3934/naco.2012.2.511

[7]

Jiaqin Wei. Time-inconsistent optimal control problems with regime-switching. Mathematical Control and Related Fields, 2017, 7 (4) : 585-622. doi: 10.3934/mcrf.2017022

[8]

Thomas I. Seidman. Optimal control of a diffusion/reaction/switching system. Evolution Equations and Control Theory, 2013, 2 (4) : 723-731. doi: 10.3934/eect.2013.2.723

[9]

Changjun Yu, Shuxuan Su, Yanqin Bai. On the optimal control problems with characteristic time control constraints. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1305-1320. doi: 10.3934/jimo.2021021

[10]

Matthias Gerdts, René Henrion, Dietmar Hömberg, Chantal Landry. Path planning and collision avoidance for robots. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 437-463. doi: 10.3934/naco.2012.2.437

[11]

Claudia Totzeck. An anisotropic interaction model with collision avoidance. Kinetic and Related Models, 2020, 13 (6) : 1219-1242. doi: 10.3934/krm.2020044

[12]

Andrea Signori. Penalisation of long treatment time and optimal control of a tumour growth model of Cahn–Hilliard type with singular potential. Discrete and Continuous Dynamical Systems, 2021, 41 (6) : 2519-2542. doi: 10.3934/dcds.2020373

[13]

M. Delgado-Téllez, Alberto Ibort. On the geometry and topology of singular optimal control problems and their solutions. Conference Publications, 2003, 2003 (Special) : 223-233. doi: 10.3934/proc.2003.2003.223

[14]

Enkhbat Rentsen, J. Zhou, K. L. Teo. A global optimization approach to fractional optimal control. Journal of Industrial and Management Optimization, 2016, 12 (1) : 73-82. doi: 10.3934/jimo.2016.12.73

[15]

Fabio Bagagiolo. Optimal control of finite horizon type for a multidimensional delayed switching system. Discrete and Continuous Dynamical Systems - B, 2005, 5 (2) : 239-264. doi: 10.3934/dcdsb.2005.5.239

[16]

Galina Kurina, Sahlar Meherrem. Decomposition of discrete linear-quadratic optimal control problems for switching systems. Conference Publications, 2015, 2015 (special) : 764-774. doi: 10.3934/proc.2015.0764

[17]

Fabio Bagagiolo. An infinite horizon optimal control problem for some switching systems. Discrete and Continuous Dynamical Systems - B, 2001, 1 (4) : 443-462. doi: 10.3934/dcdsb.2001.1.443

[18]

Wensheng Yin, Jinde Cao, Yong Ren. Inverse optimal control of regime-switching jump diffusions. Mathematical Control and Related Fields, 2021  doi: 10.3934/mcrf.2021034

[19]

Piermarco Cannarsa, Cristina Pignotti, Carlo Sinestrari. Semiconcavity for optimal control problems with exit time. Discrete and Continuous Dynamical Systems, 2000, 6 (4) : 975-997. doi: 10.3934/dcds.2000.6.975

[20]

Jérome Lohéac, Jean-François Scheid. Time optimal control for a nonholonomic system with state constraint. Mathematical Control and Related Fields, 2013, 3 (2) : 185-208. doi: 10.3934/mcrf.2013.3.185

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (895)
  • HTML views (0)
  • Cited by (2)

[Back to Top]