Controller Synthesis for Hierarchical Agent Interactions

Overview & Synopsis

We give a formalism and an algorithm for synthesizing controllers to coordinate interactions among hierarchically organized agents. Typical applications are, for example, in harbor or warehouse automation. The formalism models agents as hierarchical input/output automata, and models a system of interacting agents as the parallel composition of the automata. It extends the usual parallel composition operation of I/O automata with a hierarchical composition operation for refining abstract tasks into lower-level subtasks. We provide an algorithm to synthesize hierarchically organized controllers to coordinate the agents' interactions in order to drive the system toward desired states. Our contribution is mostly theoretical: we formally define the representation, and present theorems about its properties (i.e., the parallel and hierarchical composition are distributive operations), as well as the correctness and completeness of the synthesis algorithm.