  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.
