Shushman Choudhury (Stanford University); Jayesh Gupta (Stanford University); Mykel Kochenderfer (Stanford University); Dorsa Sadigh (Stanford); Jeannette Bohg (Stanford)
 |
 |
 |
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.
 | Start Time | End Time |
|---|---|---|
| 07/15 15:00 UTC | 07/15 17:00 UTC |
The main idea of the algorithm is to use two levels, one for individual robots and one for coordination. The idea of two levels has been around for a long time in motion planning for multiple robots to avoid collisions. The existence of time windows considered in the paper helps, because robots tasks become unavailable and so robots do not need to try to avoid running into each other for a long time and give up the task to another robot (like it is shown in the video for the robot manipulators). The optimality and completeness properties of the algorithm depend on not having new tasks appear online, which limits the value of the approach, since often in real situations tasks appear on line. Yet, having those properties even under restricted conditions, is valuable. Interleaving planning with execution adds value to the method. The experimental results include two very different domains, where the different algorithms tested perform differently, so adding confidence to the value of the approach proposed.
Overall, I think the idea is a reasonable one. I like the proof of optimality in the supplement, but am annoyed that it is not in the main manuscript. I would highly recommend cutting down on the other description and trying to get the proof into the main manuscript without making the reader read additional documents. The biggest complaint I have is wrt comparisons to other works. Given the abundance of work in this area, EDD and Hungarian are not reasonable baselines in my opinion. Through Section III (C), the authors list several other works ([5][20][49]) that this work is inspired by. Using some of those as a baseline would have been interesting. Table II only shows how quickly SCoBA runs. A key claim was that SCoBA scales well. However, there is no comparison with the baselines wrt time complexity of execution. I think this is a major flaw and needs to be fixed. Table I is very dependent on the setup. If there are four arms instead of three, or if the particular constants of pick up speed are changed, these numbers change. I would have liked some comparison that is generic, and compares it across generic MRTA values.
In my opinion, this approach may has a significant impact to the robotic community but not only. Planning and Scheduling and sequential-decision making under uncertainty (dynamic programming, MDP, POMDPs) communities may also be interested. This approach merges two "worlds" reaching an important public. Globally, the paper is well-written and easy to follow. The proofs of optimality are given in the appendix (and are correct as far as I could check). I would advise authors to insert, at least, a proof-sketch in the paper corpus. Meanwhile I have a couple of questions. - Stochastic Conflict-Based Allocation: *During the child generation (alg. 1), a new policy tree is computed considering the k task to be excluded. But, nothing guarantee that new conflicts will appear given remaining tasks and the new policy tree. Is it right? And, what happens if no solution is found? You need to replan considering a different number of robots? how do you solve this issue? *At SCoBA level, what about the stochasticity? why is not the probability of a given conflict that is considered? For instance, there is a chance that an arm does not grasp an object, and if it is the case, and if I well understood, conflicts may arrive during execution if only the branch with correct grasp was considered for conflict resolution. How could you ensure to correctly handle such a small probability event? *Could you provide an theoretical analysis in how but the complexity of the planning problem can be broken by making use of you hierarchical planner compared to the state-of-the art approaches that solve the entire problem. Computation time gives some idea of the efficiency. But a theoretical analysis would enrich the discussion. Anyway the paper is original, with a strong empirical simulated evaluation. Minor comments: - the caption of table 1 and figure 5 relates to "boxes", while in the main text you talk about objects. Maybe use also "objects" in those table and figure.
 |
 |
 |