Hierarchical control for finite state machines

We base the notion of state aggregation for finite state machines (FSM) on the dynamical consistency (DC) relation ([17]) between the blocks of states in any given state space partition pi. In this framework, we present the new notion of ST dynamical consistency (ST-DC) for source-target (ST) FSMs where there is a preferred sense of flow from a set of source states (S) to a set of target states (T). It is proven that if a partition pi is ST in-block controllable (ST-IBC), the partition machine of an ST FSM M based on pi, Mpi (i.e. high level abstraction of M based on pi), is controllable if and only if M itself is controllable. We also prove that all ST-IBC partition machines of M form a lattice and any chain from the top to the bottom of this lattice provides a hierarchical feedback control structure.;This methodology is next extended to optimal control problems for discrete event systems (DES) modelled by finite state machines. A partition machines based scheme called hierarchically accelerated dynamic programming (HADP) is introduced which significantly speeds up the standard dynamic programming procedure (up to several orders of magnitude) at the cost of a certain degree of sub-optimality. We present necessary and sufficient conditions for the HADP procedure to generate globally optimal solutions and, further, give bounds on the degree of sub-optimality. An example called the Broken Manhattan Grid (BMG) system is used to illustrate the implementation of HADP, and flexible and generalisable code for this example is described.;Many complex systems appear in the form of the product of multiple interacting sub-systems. A formulation of multi-agent systems is presented where the dynamics of the agents are described by default specifications, of a sets of forbidden state-event relational pairs, denoted R . Such systems are called relational multi-agent product systems (MA( R )). The application of the HADP methodology to relational multi-agent product systems is analysed. A multi-machine system consisting of a time counter and agents called a timed multi-agent relational product (TMA( R )) is formulated.;To apply hierarchical control to the routing problem for networks, we consider two conceptual classes of networks: first, link network systems (LN), and, second, buffer network systems (BN). The notions of dynamical costs and network states are introduced. In particular, the notion of throughput-independent ST-IBC (TI-ST-IBC) partitions is used to formulate the incremental HADP ( IHADP) methodology. For the multiple objective optimisation problem of LNs, a notion of (vector) network state is introduced to carry the information describing the available transmission capacity of each link. For buffer network systems, the notion of (matrix) network states is given.