Dynamic Coordination for Distributed Planning with Limited Communication

通信有限的分布式规划的动态协调

• 批准号: 0414727
• 负责人: Stephen Patek
• 金额: $ 41.47万
• 依托单位: University of Virginia Main Campus
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2008-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0414727&HistoricalAwards=false
• 关键词: Dynamic; Coordination; Distributed; Planning; Limited

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 sectorsof 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.

从互联网、国家电网和其他大规模网络基础设施的出现可以清楚地看出，今天的工程系统越来越依赖于分布式控制权限和子系统之间的协调。 典型地，协调在工程系统中通过用于分布式系统之间的相对良好定义的（约束的）交互的ad hoc协议的规范来实现。 然而，随着信息系统越来越多地融入社会，我们发现现有的协议没有充分调整新的应用程序和/或意外的情况。 虽然分散控制和规划的问题在我们今天构建的工程系统中变得越来越普遍，但不幸的是，设计和操作此类系统的基本指导原则和理论似乎很少。 博弈论和分散控制的概念只是部分地揭示了与分布式工程系统相关的基本问题，特别是在分布式代理/参与者/行动者都认识到相同的性能目标并将一起工作的情况下，除了由于有限的通信而很少或根本没有机会协调他们的行动的问题。 在这个项目中，PI的目标是通过提出一类新的顺序决策过程（称为协调过程）来增强对协调的理解，而无需明确的通信，其分析将在分散系统和分布式规划应用中提供新的理论见解和新的算法方法。 PI团队将研究的数学框架植根于受控马尔可夫过程和动态博弈的理论，从而为新的结果提供坚实的基础，包括新的解决方案概念和新的算法方法，用于确定最佳协调策略。PI团队将把他们的努力主要集中在两个子类的协调问题：瞬态协调过程中，所有的演员寻求驱动一个底层系统的终端状态以最小的成本;重复播放协调过程中，目标是学习最佳的协调策略，往往最小化的平均成本感知在重复的情况下的协调问题。 PI团队将评估他们的解决方案的概念和算法程序的上下文中的两个说明性的应用程序，一个机器人规划问题和互联网交通工程问题，这两个都需要自主代理（演员），以协调没有明确的沟通机会。更广泛的影响：这项工作将影响不同的研究社区，包括控制理论，博弈论和决策科学。 研究结果将应用于工程和计算机科学的不同领域，包括新MAC层协议的设计，分布式协作工具和对等应用中更好的冲突解决算法的设计，运输资源管理系统的设计和控制，以及未来的传感器管理系统。