Caines, Peter E. (McGill Univ.), Shaikh, M. Shahid (FAST-National University)

New Results in Optimality Zone Hybrid Optimal Control Algorithms: Halting and Convergence

Scheduled for presentation during the Mini-Symposium "Computational Methods in Hybrid Systems" (TuA05), Tuesday, July 25, 2006, 10:50−11:15, Room F

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on April 25, 2024

Abstract

A general Hybrid Minimum Principle (HMP) for hybrid optimal control problems (HOCPs) is presented in [Shaikh & Caines, 2004, 2005] and in [Shaikh & Caines, 2004], a class of efficient, provably convergent Hybrid Minimum Principle (HMP) algorithms were obtained based upon the HMP. The notion of optimality zones (OZs) ([Shaikh & Caines, 2003, 2004]) provides a theoretical framework for the computation of optimal location (i.e. discrete state) schedules for HOCPs (i.e. discrete state sequences with the associated switching times and states). Basic properties of the topology of OZs are given and then this paper presents the algorithm HMPOZ which fully integrates the prior computation of the OZs into the HMP algorithms class. Summing (a) the computational investment in the construction of the OZs for a given HOCP, and (b) the complexity of (i) the computation of the optimal schedule, (ii) the optimal switching time and optimal switching state sequence, and (iii) the optimal continuous control input, yields a complexity estimate for the algorithm HMPOZ which is linear (i.e. $O(L)$) in the number of switching times $L$. The main result of the paper establishes the convergence and halting properties of the HMPOZ algorithm.