Hierarchical Planning for Heterogeneous Multi-Robot Routing Problems via Learned Subteam Performance

A recent paper by members of the DCIST alliance proposes a new hierarchical planner for task allocation problems where tasks correspond to heterogeneous multi-robot routing problems defined on different areas of a given environment. The researchers tackled this complex planning problem with a novel planner which breaks down the complexity of the original problem into two subproblems: the high-level problem of allocating robots to routing tasks, and the low-level problem of computing the actual routing paths for each subteam. The planner uses a Graph Neural Network (GNN) as a heuristic to estimate subteam performance for specific coalitions on specific routing tasks. It then iteratively refines the estimates to the real subteam performances as solutions of the low-level problems become available. On a testbed problem having an area inspection problem as the base routing task, the experiments show that the new hierarchical planner is able to compute optimal or near-optimal (within 7%) solutions approximately 16 times faster (on average) than an optimal baseline that computes plans for all the possible allocations in advance to obtain precise routing times. The experiments also show that a GNN-based estimator can provide an excellent trade-off between solution quality and computation time compared to other baseline (non-learned) estimators.

Capabilities: T2C1 E+G (Simultaneous Task Assignment and Planning)

Points of Contact: Nicholas Roy (PI) and Jacopo Banfi

Video: N/A

Paper: https://ieeexplore.ieee.org/document/9705621

Citation: J. Banfi, A. Messing, C. Kroninger, E. Stump, S. Hutchinson, N. Roy. “Hierarchical Planning for Heterogeneous Multi-Robot Routing Problems via Learned Subteam Performance.” IEEE Robotics and Automation Letters, to appear (2022).