From Architectures to Emergent Behavior: Tools for the Specification, Design and Simulation of Multi-Agent Hybrid Systems
We envision a design, simulation, and verification environment for multi-agent hierarchical hybrid control systems as shown in the following Figure. The specifications are described by the desired emergent behavior of the collection of agents. These requirements are usually described linguistically, such as increased safety and throughput, reduced emissions for AHS, or increased frequency of landings and takeoffs and optimum utilization of air space for Air Traffic Management Systems. These requirements should get ``compiled'' into a system architecture.
 Multi-Agent Hybrid System Design Enviroment |
The controller of each agent is described by a multi-layer hierarchy. The higher layers are typically modeled by discrete-event systems and take strategic decisions in coordination with other agents. The lower layers, on the other hand, typically involve continuous dynamics and performing path planning and regulation tasks. The control laws at different layers along with the inter-agent coordination schemes are to be designed, in order to satisfy the specified requirements such as safety, productivity, efficient resource utilization, etc. Tools used for design may be conventional discrete / continuous / hybrid tools. Once the control laws for individual agents are designed, the various layers can be formalized as collections of hybrid modules. This will allow micro-simulation of individual agents and macro-simulation of the collective emergent behavior, and support attempts at both micro- and macro-verification of crucial system characteristics.
The environment can be customized to a specific application, such as Automated Highway Systems (AHS) or Air Traffic Management Systems (ATMS). As an example, consider the case of AHS. The hybrid system description language can be customized to the specific application domain as shown in [1]. Then, controllers for the various AHS maneuvers are designed to satisfy safety, comfort, and efficiency requirements using the tools to be developed here (an example of this for AHS is in [2]). A language for describing such dynamically changing networks of hybrid systems called SHIFT is described in [1]. SHIFT adds the functionality to dynamically create and destroy new components and change I/O connections and event synchronizations as part of the discrete state transitions.
Hybrid Modules: Specification
Here, we present a reasonably general model for multi-agent systems.
Each agent is modeled as a hybrid system that may coordinate its
actions with other agents or treat the actions of other agents as disturbances.
The modeling framework is modular in that a hybrid system can be
specified as a composition of subsystems, and hierarchical in that a
hybrid system can be specified at different levels of abstraction.
On one level, an agent may be modeled as a collection of subsystems
representing the plant dynamics, sensors, actuators, communication devices,
and controllers.
On a more abstract level, an agent may be modeled as a finite automaton
representing a strategy transducing one hybrid data stream (sensor data and
input signals) to another hybrid data stream (control commands and output
signals).
In our framework, a hybrid dynamical system (which may represent a subsystem of an agent, or an entire agent, or a collection of agents) is modeled as a hybrid module. A hybrid module is a hybrid automaton with an I/O interface, which is necessary for modular and hierarchical design. Hybrid automata were designed by one of our team members as mathematical models for hybrid dynamical systems [3]. The state of a hybrid module is a tuple (q,x) in Q × R^n, where Q is a finite set of discrete states and x is a vector denoting the values of continuous state variables. For example, q may represent a control mode and x may represent sensor data. A hybrid module interacts with other modules through discrete and continuous inputs (u) and outputs (y). For example, discrete inputs may represent local commands from other modules within the same agent or external events caused by other agents, and continuous inputs may represent environmental disturbances. The dynamic evolution of the continuous state is defined by differential equations of the form x'(t)=f^q(x(t),u(t),y(t)) and algebraic assignments of the form x(t):=g^q(x(t),u(t),y(t)), with the restriction that there are no loops in the dependency graph of the algebraically defined states. The stepwise evolution of the discrete state is defined by a finite state machine. An edge between discrete states is labeled by a guarded assignment. The edge may be executed only if the corresponding guard is true, which is a boolean expression over the variables x(t),u(t),y(t). Upon execution of an edge, the continuous state is reinitialized using the corresponding assignment, which assigns new values to the continuous state variables as a function of x(t),u(t),y(t). Also associated with each discrete state is an invariant, which is a boolean expression over x(t),u(t),y(t). As soon as the invariant becomes false, a discrete state change is forced. The discrete and continuous outputs of a hybrid module are defined by algebraic expressions of the form y=h^q(x(t),y(t)). The trajectories of a hybrid module are defined as sequences of alternating segments of dynamic evolution of the continuous state and stepwise evolution of the discrete state.
The two main operations on a hybrid module are parallel composition and output hiding. By composing two modules, we identify inputs of one module with outputs of the other module. For example, an agent may be modeled by composing modules that represent sensors, actuators, and controllers. In this case, sensor output is identified with controller input, and controller output represents control commands and is identified with actuator input. By hiding the output of a module, it is no longer visible to the environment of the module. For example, after composition with actuators, the controller output may be hidden so that it is not visible to other agents. Decomposing a complex system into a subsystem hierarchy of hybrid modules and defining the interactions between the modules and the environmental inputs constitutes a control architecture. The following figure depicts subsystem interconnections and agent interactions.
 Multiple Agent Interaction |
Conversely, if a hybrid system is constructed from hybrid modules using composition and hiding, then the construction can be ``flattened'' into a single equivalent hybrid module by simple and well-defined operations such as variable substitution and parallel composition of finite state machines along with logical operations on guards, assignments, and invariants. This enables a fully modular and hierarchical design philosophy for complex hybrid systems.