能力不確実性下における異種ロボットチームのロバストタスクスケジューリング
Robust Task Scheduling for Heterogeneous Robot Teams under Capability Uncertainty
タスク分解・割当・スケジューリングを同時最適化する確率的計画法を提案し、エージェント能力を確率分布で表しCVaRでロバストな計画を生成する。旗取りゲームとパンデミック下のサービス調整で有効性を検証した。
著者: Bo Fu, William Smith, Denise Rizzo, Matthew Castanier, Maani Ghaffari, Kira Barton
分類: cs.RO, cs.MA
原文アブストラクト
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 one fixed 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.
