Dynamic Coordination for Distributed Planning with Limited Communication

University Of Virginia Main Campus, Charlottesville VA

Investigators

Abstract

As is clear from the emergence of the Internet, the national electric power grid, and other large-scale network infrastructures, engineering systems today are increasingly reliant on distributed control authority and coordination between subsystems. Typically, coordination is achieved in engineering systems through the specification of ad hoc protocols for relatively well-defined (constrained) interactions between distributed systems. As information systems become more integrated into society, however, we find that existing protocols are not adequately tuned for new applications and/or unexpected situations. Though issues of decentralized control and planning are becoming more prevalent in the engineering systems we build today, there unfortunately appears to be little in the way of underlying guiding principles and theory for designing and operating such systems. Notions of game theory and decentralized control go only part way toward revealing the basic problems associated with distributed engineering systems, especially in situations where distributed agents/players/actors all recognize the same performance objective and would work together except for the problem of having little or no opportunities to coordinate their actions because of limited communication. In this project, the PI's goal is to derive an enhanced understanding of coordination without explicit communication by posing a new class of sequential decision processes, known as coordination processes, whose analysis will provide new theoretical insights and new algorithmic approaches in decentralized systems and distributed planning applications. The mathematical framework the PI team will investigate is rooted in the theory of controlled Markov processes and dynamic games, thus providing a firm foundation for new results, including new solution concepts and new algorithmic approaches for identifying optimal coordination strategies. The PI team will focus their efforts broadly on two subclasses of coordination problems: transient coordination processes where all actors seek to drive an underlying system to a terminal state with minimum cost; repeated play coordination processes where the objective is to learn optimal coordination strategies that tend to minimize the average cost perceived in repeated instances of a coordination problem. The PI team will evaluate their solution concepts and algorithmic procedures in the context of two illustrative applications, a robotic planning problem and an Internet traffic engineering problem, both of which require autonomous agents (actors) to coordinate without opportunities for explicit communication. Broader Impact: This work will impact diverse research communities, including those for control theory, game theory, and decision sciences. The results should find application in diverse sectors of engineering and computer science, including the design of new MAC-layer protocols, the design of better conflict resolution algorithms in distributed collaboration tools and peer-to-peer applications, the design and control of transportation resource management systems, and in future sensor management systems.