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.