Application of graph theory in hybrid control systems using state space mesh

Abstract

In this paper, a novel method is developed to control hybrid dynamical systems which contain both continuous and discrete dynamics. The objective of the controller is to drive the system from its initial state to the desired final state. The hybrid controller consists of two independent parts. To design the first part, the abstract controller, a regular mesh of the continuous state space is constructed. Then, a behaviour graph of the system is derived by choosing a finite family of control signals and considering the discrete dynamic of the system. Subsequent application of the Floyd–Warshall algorithm, which was originally developed to find the minimum length path in a graph, allows the abstract controller to be constructed. A new algorithm is proposed to derive the control command for the second part, which constructs a bisimulation relation and finalizes the control process. Finally, the controller is applied to a dynamic system, and the obtained results show the effectiveness of the proposed control methodology.

Keywords

Hybrid dynamical system hybrid automata Floyd–Warshall algorithm graph theory

Get full access to this article

View all access options for this article.

References

Tomlin

. Hybrid control of air traffic management. In: Proceedings of the 1999 American Society of Mechanical Engineers congress and exposition, Nashville, November, 1999, pp.365–372.

Zongxuan

Kumar

. Challenges and opportunities in automotive transmission control. In: The American control conference, Portland, OR, 8–10 June 2005, pp.3284–3289. IEEE.

Morris

Stauth

Parviz

. Self-assembly for microscale and nanoscale packaging: steps toward self-packaging. IEEE Trans Adv Packag 2005; 28(4): 600–611.

Branicky

. Multiple Lyapunov functions and other analysis tools for switched and hybrid systems. IEEE Trans Autom Control 1998; 43(4): 475–482.

Tabuada

. An approximate simulation approach to symbolic control. IEEE Trans Autom Control 2008; 53(6): 1406–1418.

Tabuada

Pappas

. Linear time logic control of discrete-time linear systems. IEEE Trans Autom Control 2006; 51(12): 1862–1877.

Yordanov

Belta

. Temporal logic control of discrete-time piecewise affine systems. In: The 48th IEEE conference on decision and control, Shanghai, China, 15–18 December 2009, pp.3182–2187. Piscataway, NJ: IEEE Press.

Alur

. Discrete abstractions of hybrid systems. Proc IEEE 2000; 88(7): 971–984.

Girard

Julius

Pappas

. Approximate simulation relations for hybrid systems. Discrete Event Dyn Syst: Theory Appl 2008; 18(2): 163–179.

10.

Girard

Pappas

. Approximation metrics for discrete and continuous systems. IEEE Trans Autom Control 2007; 52(5): 782–798.

11.

Lygeros

Tomlin

Sastry

. Hybrid systems: modeling, analysis and control. EECS 291E lecture notes and class projects, EECS Department, University of California, Berkeley, 1999.

12.

Berardi

De Santis

Di benedetto

. Invariant sets and control synthesis for switching systems with safety specification. In: The third international workshop on hybrid systems: computation and control, Pittsburgh, PA, 23–25 March 2000, pp.59–73. Springer.

13.

Lygeros

. On the existence of executions of hybrid automata. In: The 38th IEEE conference on decision and control, Pheonix, Arizona, December 1999, pp.2249–2254. Piscataway, NJ: IEEE Press.

14.

Baier

Katoen

J-P

. Principles of model checking. Cambridge, MA: MIT Press, 2008.

15.

Zienkiewicz

Taylor

Zhu

. The finite element method: basis and fundamentals. Oxford: Butterworth-Heinemann, 2005.

16.

Girard

Martin

. Motion planning for nonlinear systems using hybridizations and robust controllers on simplices. In: The 47th IEEE conference on decision and control, Cancun, Mexico, 9–11 December 2008, pp.239–244. Piscataway, NJ: IEEE Press.

17.

Habets

LCGJM

Collins

Van Schuppen

. Reachability and control synthesis for piecewise-affine hybrid systems on simplices. IEEE Trans Autom Control 2006; 51(6): 938–948.

18.

Khaki Sedigh

. Modern control systems. Tehran: University of Tehran Press, 2004.

19.

Asarin

Bournex

Dang

. Approximate reachability analysis of piecewise-linear dynamical systems. 2000, p.20–31.

20.

Cormen

. Introduction to algorithms. 2nd ed. Cambridge, MA: MIT Press, 2001.

21.

Putzer

. Avoiding the Jordan canonical form in the discussion of linear systems with constants coefficients. Am Math Month 1969; 73: 2–7.

22.

Wang

. A hybrid control scheme of adaptive and variable structure for flexible spacecraft. Aerosp Sci Technol 2004; 8: 423–430.