This paper develops a stochastic programming framework for multi-agent systems where task decomposition, assignment, and scheduling problems are simultaneously optimized. The framework can be applied to heterogeneous mobile robot teams with distributed sub-tasks. Examples include pandemic robotic service coordination, explore and rescue, and delivery systems with heterogeneous vehicles. Due to their inherent flexibility and robustness, multi-agent systems are applied in a growing range of real-world problems that involve heterogeneous tasks and uncertain information. Most previous works assume a unique way to decompose a task into roles that can later be assigned to the agents. This assumption is not valid for a complex task where the roles can vary and multiple decomposition structures exist. Meanwhile, it is unclear how uncertainties in task requirements and agent capabilities can be systematically quantified and optimized under a multi-agent system setting. A representation for complex tasks is proposed: agent capabilities are represented as a vector of random distributions, and task requirements are verified by a generalizable binary function. The conditional value at risk (CVaR) is chosen as a metric in the objective function to generate robust plans. An efficient algorithm is described to solve the model, and the whole framework is evaluated in two different practical test cases: capture-the-flag and robotic service coordination during a pandemic (e.g., COVID-19). Results demonstrate that the framework is generalizable, scalable up to 140 agents and 40 tasks for the example test cases, and provides low-cost plans that ensure a high probability of success.
翻译:本文为任务分解、任务分配和时间安排问题同时得到优化的多试剂系统开发了一个随机性编程框架。框架可以适用于具有分布式子任务的不同移动机器人小组,例如:大型机器人服务协调、探索和救援,以及具有不同车辆的运载系统。由于其固有的灵活性和稳健性,多试剂系统应用于涉及不同任务和不确定信息的日益扩大的现实世界问题。大多数以前的工作都以独特的方式将任务分解成一个任务,然后可以分配给代理人的角色。这一假设不适用于任务可能变化和存在多重分解结构的复杂任务。与此同时,不清楚如何在多试剂系统设置下系统地量化和优化任务要求和代理能力的不确定性。提出了复杂任务的代表性:代理能力是随机分配的载体,任务要求由一般可计量的二进制功能加以核实。在目标函数中选择了风险的有条件值(CVaR)作为生成稳健计划的衡量标准。一个高效的算法用于解决模式和多重分解结构的多变性结构。在两个不同的试样中,展示了一个测试案例:检验结果框架。