Autonomous Robots · 2020 · 16 citations · 52 references
EngineeringAutonomous SystemsRobotics EngineeringMulti-robot SystemsRoboticsSchedulingDynamic SchedulingMulti-robot CoordinationMulti-robot SchedulingOptimal ControlOptimization Under UncertaintyTask AllocationDynamic Task AllocationMulti-robot Task AllocationTask Allocation Under UncertaintyTemporal ConstraintsTemporal Constraints Satisfaction
We consider the problem of dynamically allocating tasks to multiple agents under time window constraints and task completion uncertainty. Our objective is to minimize the number of unsuccessful tasks at the end of the operation horizon. We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination and addresses them in a hierarchical manner. The lower layer computes policies for individual agents using dynamic programming with tree search, and the upper layer resolves conflicts in individual plans to obtain a valid multi-agent allocation. Our algorithm, Stochastic Conflict-Based Allocation (SCoBA), is optimal in expectation and complete under some reasonable assumptions. In practice, SCoBA is computationally efficient enough to interleave planning and execution online. On the metric of successful task completion, SCoBA consistently outperforms a number of baseline methods and shows strong competitive performance against an oracle with complete lookahead. It also scales well with the number of tasks and agents. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
52
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
Julia: A Fresh Approach to Numerical Computing
Jeff Bezanson, Alan Edelman, Stefan Karpinski et al. · SIAM Review · 2017 · 6.3K citations
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations