Grant: Discovery Grants Program - Individual

Peer-to-peer networks, multi-agent systems, sensor networks, and automatic teller machines are examples of systems whose components are distributed over a wide geographic area. In practice, design of distributed discrete-event systems is not fully automated. Rather, relying largely on heuristics, an ad hoc design is first proposed based on the system specifications, and only then is the design formally verified for correctness. Supervisory control theory of discrete-event systems offers a systematic way to design controllers for discrete-event systems based on the design specifications. The entire process can now be carried out on a computer, thus eliminating the need for someone with an extensive knowledge of the system to propose the initial, ad hoc design. To reduce the complexity of design, for distributed systems it is highly desirable to design local decentralized controllers, one for each system component, to simulate the control exercised by a global centralized controller. To make correct control decisions, the local controllers may need to communicate their observations of the system states. The objective of this work is to systematically design decentralized communicating controllers for a distributed discrete-event system based on a global design specification. Each local controller is equipped with a pair of maps which, roughly speaking, captures its control and observation, so that the local controllers can collectively implement the specification. We intend to apply our approach to an important class of discrete-event systems design problems, namely, the synthesis of communication protocols, and show that supervisory control theory can indeed replace ad hoc design methods for discrete-event systems.