Joint Task Assistance Planning via Nested Branch and Bound
Omer Daube, Oren Salzman
AI summary
Problem
Prior task assistance planning fixes the task robot's path and only optimizes the assistance robot's trajectory. This work addresses the computationally hard problem of jointly planning both robots' paths to maximize the total duration of assistance.
Approach
The authors introduce a hierarchical nested Branch and Bound framework that simultaneously explores task and assistance paths, using flow-based linear programming bounds to prune the search space and an incremental solver to avoid recomputing similar subproblems.
Key results
- Formulation of the Joint Task Assistance Planning (JOINTTAP) problem
- Nested Branch and Bound algorithm with flow-based LP upper bounds for efficient pruning
- Incremental optimization method for similar subproblems yielding up to 3× speedup
- Empirical validation demonstrating up to two orders of magnitude speedup over baselines in simulation and drone experiments
Why it matters
Provides a scalable planning foundation for cooperative robotic systems in communication-constrained or visually critical environments like search-and-rescue and tele-operation.
Abstract
We introduce and study the Joint Task Assistance Planning problem which generalizes prior work on optimizing assistance in robotic collaboration. In this setting, two robots operate over predefined roadmaps, each represented as a graph corresponding to its configuration space. One robot, the task robot, must execute a timed mission, while the other, the assistance robot, provides sensor-based support that depends on their spatial relationship. The objective is to compute a path for both robots that maximizes the total duration of assistance given. Solving this problem is challenging due to the combinatorial explosion of possible path combinations together with the temporal nature of the problem (time needs to be accounted for as well). To address this, we propose a nested Branch and Bound framework that efficiently explores the space of robot paths in a hierarchical manner. We empirically evaluate our algorithm and demonstrate a speedup of up to two orders of magnitude when compared to a baseline approach.