article

Gradient Descent Approach to Optimal Mode Scheduling in Hybrid Dynamical Systems

Authors:

E. I. VerriestAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 136, Issue 2

Pages 167 - 186

https://doi.org/10.1007/s10957-007-9305-y

Published: 01 February 2008 Publication History

Abstract

This paper concerns the problem of optimally scheduling the sequence of dynamic response functions in nonlinear switched-mode hybrid dynamical systems. The control parameter has a discrete component and a continuous component, namely the sequence of modes and the duration of each mode, while the performance criterion consists of a cost functional on the state trajectory. The problem is naturally cast in the framework of optimal control. This framework has established techniques sufficient to address the continuous part of the parameter, but lacks adequate tools to consider the discrete element. To get around this difficulty, the paper proposes a bilevel hierarchical algorithm. At the lower level, the algorithm considers a fixed mode sequence and minimizes the cost functional with respect to the mode durations; at the upper level, it updates the mode sequence by using a gradient technique that is tailored to the special structure of the discrete variable (mode sequencing). The resulting algorithm is not defined on a single parameter space, but rather on a sequence of Euclidean spaces of increasing dimensions, an unusual setting for which there is no established notion of convergence. The paper suggests first a suitable definition of convergence based on the concepts of optimality functions; then, it proves that the proposed algorithm converges in that sense.

References

[1]

Lincoln, B., Rantzer, A.: Optimizing linear systems switching. In: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, FL, pp. 2063---2068 (2001)

[2]

Rehbinder, H., Sanfirdson, M.: Scheduling of a limited communication channel for optimal control. In: Proceedings of the 39th IEEE Conference on Decision and Control, Sidney, Australia, pp. 1011---1016 (2000)

[3]

Walsh, G., Ye, H., Bushnell, L.: Stability analysis of networked control systems. In: Proceedings of the American Control Conference, San Diego, CA, pp. 2876---2880 (1999)

[4]

Brockett, R.: Stabilization of motor networks. In: Proceedings of the 34th IEEE Conference on Decision and Control, New Orleans, LA, pp. 1484---1488 (1995)

[5]

Egerstedt, M., Wardi, Y.: Multiprocess control using queuing theory. In: Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, pp. 1991---1996 (2002)

[6]

Hristu-Varsakelis, D.: Feedback control systems as users of shared network: communication sequences that guarantee stability. In: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, FL, pp. 3631---3631 (2001)

[7]

Shaikh, M.S., Caines, P.: On trajectory optimization for hybrid systems: theory and algorithms for fixed schedules. In: Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, pp. 1997---1998 (2002)

[8]

Shaikh, M.S., Caines, P.E.: On the optimal control of hybrid systems: optimization of trajectories, switching times and location schedules. In: Proceedings of the 6th International Workshop on Hybrid Systems: Computation and Control, Prague, Czech Republic, pp. 466---481 (2003)

[9]

Xu, X., Antsaklis, P.: Optimal control of switched autonomous systems. In: Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, NV, pp. 4401---4406 (2002)

[10]

Xu, X., Antsaklis, P.J.: Optimal control of switched systems via nonlinear optimization based on direct differentiations of value functions. Int. J. Control 75, 1406---1426 (2002)

[11]

Piccoli, B.: Hybrid systems and optimal control. In: Proceedings of the 37th IEEE Conference on Decision and Control, Tampa, FL, pp. 13---18 (1998)

[12]

Sussmann, H.J.: A maximum principle for hybrid optimal control problems. In: Proceedings of the 38th IEEE Conference on Decision and Control, Phoenix, AZ, pp. 425---430 (1999)

[13]

Sussmann, H.J.: Set-valued differentials and the hybrid maximum principle. In: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, pp. 558---563 (2000)

[14]

Alamir, M., Attia, S.A.: On solving optimal control problems for switched nonlinear systems by strong variations algorithms. In: Proceedings of the 6th IFAC Symposium on Nonlinear Control Systems, Stuttgart, Germany, pp. 558---563 (2004)

[15]

Attia, S.A., Alamir, M., Canudas De Wit, C.: Sub optimal control of switched nonlinear systems under location and switching constraints. In: Proceedings of the 16th IFAC World Congress, Prague, Czech Republic (2005)

[16]

Egerstedt, M., Wardi, Y., Axelsson, H.: Transition-time optimization for switched systems. IEEE Trans. Autom. Control 51, 110---115 (2006)

[17]

Axelsson, H., Wardi, Y., Egerstedt, M.: Transition-time optimization for switched systems. In: Proceedings of the 16th IFAC World Congress, Prague, Czech Republic (2005)

[18]

Axelsson, H., Wardi, Y., Egerstedt, M., Verriest, E.I.: A provably convergent algorithm for transition-time optimization in switched systems. In: Proceedings of the 44th IEEE Conference on Decision and Control, Sevilla, Spain, pp. 558---563 (2005)

[19]

Polak, E.: Optimization Algorithms and Consistent Approximations. Springer, New York (1997)

[20]

Polak, E., Wardi, Y.: A study of minimizing sequences. SIAM J. Control Optim. 22, 599---609 (1984)

[21]

Armijo, L.: Minimization of functions having Lipschitz continuous first-partial derivatives. Pac. J. Math. 16, 1---3 (1966)

[22]

Axelsson, H., Wardi, Y., Egerstedt, M., Verriest, E.I.: Tracking the fluid level in a double tank system: an example of optimal control in a switched-mode system with arbitrary number of switches. Technical Memorandum, Georgia Institute of Technology, School of Electrical and Computer Engineering (April 2007), http://www.ece.gatech.edu/~magnus/Papers/ModeSwitch.pdf

Cited By

Yu JLin MPinosky AAbraham IBroad AArgall BMurphey T(2023)Hybrid control for combining model-based and model-free reinforcement learningInternational Journal of Robotics Research10.1177/0278364922108333142:6(337-355)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1177/02783649221083331
Khazaee MSadedel MDavarpanah A(2021)Behavior-Based Navigation of an Autonomous Hexapod Robot Using a Hybrid AutomatonJournal of Intelligent and Robotic Systems10.1007/s10846-021-01388-0102:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10846-021-01388-0
Sager SZeile C(2021)On mixed-integer optimal control with constrained total variation of the integer controlComputational Optimization and Applications10.1007/s10589-020-00244-578:2(575-623)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10589-020-00244-5
Show More Cited By

Gradient Descent Approach to Optimal Mode Scheduling in Hybrid Dynamical Systems
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Switched-mode systems: gradient-descent algorithms with Armijo step sizes

This paper concerns optimal mode-scheduling in autonomous switched-mode hybrid dynamical systems, where the objective is to minimize a cost-performance functional defined on the state trajectory as a function of the schedule of modes. The controlled ...
Hybrid Optimal Control under Mode Switching Constraints with Applications to Pesticide Scheduling
Special Issue on ICCPS 2016

This paper concerns optimal mode-scheduling in autonomous switched-mode hybrid dynamical systems, where the objective is to minimize a cost-performance functional defined on the state trajectory as a function of the schedule of modes. The controlled ...
Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step

We consider the minimization of a nonconvex quadratic form regularized by a cubic term, which may exhibit saddle points and a suboptimal local minimum. Nonetheless, we prove that, under mild assumptions, gradient descent approximates the global minimum to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 136, Issue 2

February 2008

82 pages

ISSN:0022-3239

Issue’s Table of Contents

Copyright © Copyright © 2008 Springer Science+Business Media, LLC.

Publisher

Plenum Press

United States

Publication History

Published: 01 February 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yu JLin MPinosky AAbraham IBroad AArgall BMurphey T(2023)Hybrid control for combining model-based and model-free reinforcement learningInternational Journal of Robotics Research10.1177/0278364922108333142:6(337-355)Online publication date: 1-May-2023
https://dl.acm.org/doi/10.1177/02783649221083331
Khazaee MSadedel MDavarpanah A(2021)Behavior-Based Navigation of an Autonomous Hexapod Robot Using a Hybrid AutomatonJournal of Intelligent and Robotic Systems10.1007/s10846-021-01388-0102:2Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s10846-021-01388-0
Sager SZeile C(2021)On mixed-integer optimal control with constrained total variation of the integer controlComputational Optimization and Applications10.1007/s10589-020-00244-578:2(575-623)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10589-020-00244-5
Zeile CRobuschi NSager S(2021)Mixed-integer optimal control under minimum dwell time constraintsMathematical Programming: Series A and B10.1007/s10107-020-01533-x188:2(653-694)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s10107-020-01533-x
Wang JBu LXing SWu YLi X(2021)Combined Online Checking and Control Synthesis: A Study on a Vehicle Platoon TestbedFormal Methods10.1007/978-3-030-90870-6_43(752-762)Online publication date: 20-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90870-6_43
Ali UEgerstedt M(2018)Hybrid Optimal Control under Mode Switching Constraints with Applications to Pesticide SchedulingACM Transactions on Cyber-Physical Systems10.1145/30474112:1(1-17)Online publication date: 3-Jan-2018
https://dl.acm.org/doi/10.1145/3047411
Chen HZhang W(2017)On weak topology for optimal control of switched nonlinear systemsAutomatica (Journal of IFAC)10.1016/j.automatica.2017.03.03981:C(409-415)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.automatica.2017.03.039
Xu WFeng ZPeng JYiu K(2017)Optimal switching for linear quadratic problem of switched systems in discrete timeAutomatica (Journal of IFAC)10.1016/j.automatica.2016.12.00278:C(185-193)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1016/j.automatica.2016.12.002
Cowlagi R(2017)Hierarchical trajectory optimization for a class of hybrid dynamical systemsAutomatica (Journal of IFAC)10.1016/j.automatica.2016.11.04077:C(112-119)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1016/j.automatica.2016.11.040
Jones AAli UEgerstedt MKoutsoukos XMitchell I(2016)Optimal pesticide scheduling in precision agricultureProceedings of the 7th International Conference on Cyber-Physical Systems10.5555/2984464.2984476(1-8)Online publication date: 11-Apr-2016
https://dl.acm.org/doi/10.5555/2984464.2984476
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents