RI: Small: Multi-Agent (Multi-Robot) Task Allocation with Formal Guarantees in Dynamic Environments under Realistic Constraints

该方案旨在研究在不确定环境中多个智能代理之间的分散任务分配算法，重点关注可证明的性能界限。要考虑四种任务设置及其组合：(1)任务之间的约束(例如，不相交的任务组、任务之间的优先关系)；(2)代理之间的约束(例如，通信网络的维护)；(3)代理组之间的约束(例如，要求一组包括具有专门技能的代理)；(4)附加任务的在线到达。已有的具有可证明的性能界限的任务分配算法通常不考虑上述现实约束。另一方面，考虑上述某些约束的方法没有性能限制。此外，目前的算法通常假设存在一个集中式协调器(例如，基于市场的方法中的拍卖商)，并且可能不可扩展。因此，现有的文献与多机器人应用的实际需求之间存在差距。因此，需要设计既考虑实际约束又具有形式化性能保证的分布式任务分配方法。评估计划将在搜救环境中使用模拟和真实的机器人。该项目将使用USARSim环境和大约50个模拟机器人。该项目将依赖于开发任务分配算法的数学技术将取决于问题的特征。当任务之间存在约束时，该项目将使用组合优化和线性规划的技术。对于每个任务可以由多个代理执行的任务，该项目将使用合作博弈论和联盟形成的概念，并结合整数优化技术。对于动态产生的任务，该项目将探索使用随机规划技术，其关键思想是使用任务分配问题的对偶整数规划模型来为代理设计“投标规则”，以确保整个系统的性能保证。广泛的应用领域--包括应急响应、国土安全、环境监测、危险废物清理和制造--有望从本项目提出的任务分配技术中受益。该项目的成果将使应用领域能够通过提供允许机器人自主高效地在它们之间协调和分配任务的技术来更充分地从新兴的机器人技术中获益。研究生将在开展这项拟议的研究中发挥主要作用。此外，该项目将通过机器人学院暑期奖学金计划，为卡内基梅隆大学的本科生和其他机构的本科生提供研究机会。

This proposal aims to develop algorithms for decentralized task allocation among multiple intelligent agents in uncertain environments with a focus on provable performance bounds. Four task settings and their combinations are to be considered: (1) constraints among tasks (e.g., disjoint task groups, precedence relations among tasks); (2) constraints among agents (e.g., maintenance of a communication network); (3) constraints among groups of agents (e.g., requiring a group to include agents with specialized skills); (4) on-line arrival of additional tasks. Existing algorithms for task allocation that have provable performance bounds usually do not consider the realistic constraints stated above. On the other hand, approaches that consider some of the constraints above do not have performance bounds. Furthermore, current algorithms often assume the existence of a centralized coordinator (e.g., an auctioneer in market-based approaches) and may not be scalable. Thus, there is a gap between the existing literature and the practical requirements in multi-robot applications. Hence, there is a need to design distributed task allocation methods that take into consideration practical constraints and have formal performance guarantees. The evaluation plan will use simulated and real robots in search and rescue contexts. The project will use the USARSim environment with approximately 50 simulated robots.The mathematical techniques upon which this project will rely to develop algorithms for task allocation will depend on the problem characteristics. When there are constraints among tasks, the project will use techniques from combinatorial optimization and linear programming. For tasks where each task can be performed by multiple agents, the project will use concepts from cooperative game theory and coalition formation in conjunction with integer optimization techniques. For dynamically arising tasks, the project will explore the use of stochastic programming techniques with the key idea being use of the dual of the integer program model of the task allocation problem to design "bidding rules" for agents that ensure a performance guarantee for the overall system.A wide range of application domains -- including emergency response, homeland security, environmental monitoring, hazardous waste cleanup and manufacturing -- stand to benefit from the task allocation techniques proposed in this project. Results from this project will enable application domains to more fully reap the benefits of emerging robotic technology by providing techniques that allow robots to autonomously and efficiently coordinate and allocate tasks among themselves. Graduate students will play a major role in conducting the proposed research. Additionally, this project will provide research opportunities to undergraduate students both within Carnegie Mellon University and from other institutions through the Robotics Institute Summer Scholar program.