A hierarchical structure of interacting automata for modeling battlefield dynamics: Controllability and formal specification

This dissertation extends the Ramadge and Wonham model of interacting automata for the control of Discrete Event Dynamic Systems (DEDS) to model the hierarchical structure of large, complex systems. This research stems from efforts to create an Intelligent Assistant for the formulation and evaluation of dynamic, multi-layered battleplans. The distinctive features of the extended model are (1) its support of aggregation of information at every level within the hierarchy, (2) its restriction of information flow to contiguous hierarchical levels, (3) its support of non-atomic high-level event structures, and (4) its feedback mechanism, appropriately permissive for battlefield dynamics.; We define formally the control imposed by the hierarchical structure. The effects of aggregation within this hierarchical framework on controllability are presented in the notions of 2-level controllability and markability which are necessary and sufficient conditions for the existence of a hierarchically structured supervisor as modeled within this framework. The hierarchical structure of supervisors can result in an exponential reduction in supervisory state space size.; The set of 2-level controllable languages is not closed under intersection or union. The intersection of 2-level controllable languages is 2-level controllable if these languages meet a nonconflicting requirement, as is the case in the nonhierarchical framework. For any given language that is not 2-level controllable, but for which a subset exists that is 2-level controllable, the existence of a unique supremal 2-level controllable sublanguage is not guaranteed.; To facilitate the development of intuitive interfaces, usable by non-computer professionals, we formulate a class of language-based supervisor specifications, based on top-down hierarchical design techniques, including the specification of desired concurrency between distributed system components. We define realizability as a set of conditions on a given specification. Realizability is a sufficient condition for the existence of a hierarchy of supervisors exerting the specified control and incorporating the desired aggregation. We give an algorithm for the construction of the appropriate hierarchy of automata, allowing for the iterative process of supervisor specification, simulation, and refinement.