  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.
