Joint Task Assistance Planning via Nested Branch and Bound (Extended Version)

• URL: http://arxiv.org/abs/2602.13932v2
• Date: Tue, 24 Feb 2026 17:45:35 GMT
• Title: Joint Task Assistance Planning via Nested Branch and Bound (Extended Version)
• Abstract summary: We introduce and study the Joint Task Assistance Planning problem which generalizes prior work on optimizing assistance in robotic collaboration.<n>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.<n>The objective is to compute a path for both robots that maximizes the total duration of assistance given.
• Score: 6.531546527140475
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement [0.9199488958939335]
  A fundamental challenge in multi-robot motion planning is achieving sufficient coordination without incurring the large computational expense of searching the joint configuration space of the robot group.<n>We present a method for multiple mobile robot motion planning that achieves an improvement in planning time up to an order of magnitude by leveraging the insight that we can use discrete search over a workspace decomposition to provide coordination between robots during planning.
  arXiv  Detail & Related papers  (2026-05-19T18:44:09Z)
• Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO [6.508086451004438]
  We present a collaborative planning strategy based on Multi-Agent Proximal Policy Optimization (MAPPO) to coordinate a team of heterogeneous robots.<n>We benchmark our approach against single-objective optimal solutions obtained through exhaustive search and evaluate its ability to perform online replanning in the context of a planetary exploration scenario.
  arXiv  Detail & Related papers  (2026-04-01T17:53:51Z)
• Structural Induced Exploration for Balanced and Scalable Multi-Robot Path Planning [6.823580643749891]
  Multi-robot path planning is a fundamental yet challenging problem due to its complexity and the need to balance global efficiency with fair task allocation among robots.<n>Traditional swarm intelligence methods, although effective on small instances, often converge prematurely and struggle to scale to complex environments.<n>We present a structure-induced exploration framework that integrates structural priors into the search process of the ant colony optimization (ACO)
  arXiv  Detail & Related papers  (2025-12-25T12:53:24Z)
• Efficient Computation of a Continuous Topological Model of the Configuration Space of Tethered Mobile Robots [9.67618824743514]
  We build a topological model of the configuration space of a tethered robot starting from a polygonal representation of the workspace where the robot moves.<n>We show how this approach improves the performances of existing algorithms that build other types of representations of the configuration space.<n>The proposed model can be computed in a fraction of the time required to build traditional homotopy-augmented graphs.
  arXiv  Detail & Related papers  (2025-12-08T08:45:17Z)
• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations. We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation. In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-29T20:22:22Z)
• Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses [1.2810395420131764]
  Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. We consider a realistic problem of online order delivery in a warehouse, where a fleet of robots bring the products belonging to each order from shelves to workstations. This creates a stream of inter-dependent pickup and delivery tasks and the associated MAPF problem consists of computing realistic collision-free robot trajectories.
  arXiv  Detail & Related papers  (2024-08-26T15:13:38Z)
• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  Task And Motion Planning (TAMP) is the problem of finding a solution to an automated planning problem. We propose a general and open-source framework for modeling and benchmarking TAMP problems. We introduce an innovative meta-technique to solve TAMP problems involving moving agents and multiple task-state-dependent obstacles.
  arXiv  Detail & Related papers  (2024-08-11T14:57:57Z)
• Online Concurrent Multi-Robot Coverage Path Planning [5.801044612920816]
  In a horizon, the path planning and the path execution interleave, meaning when the path planning occurs for robots with no paths, the robots with outstanding paths do not execute.<n>We propose a centralized algorithm that is not horizon-based.<n>It plans paths at any time for a subset of robots with no paths, who have reached their previously assigned goals, while the rest execute their outstanding paths.
  arXiv  Detail & Related papers  (2024-03-15T16:51:30Z)
• A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems [6.853165736531941]
  A multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths. We propose an efficient conflict-guided method to compute the next best assignment. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces.
  arXiv  Detail & Related papers  (2024-02-19T19:04:19Z)
• DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
  We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2022-09-07T00:35:27Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  We study the problem of multi-robot active mapping, which aims for complete scene map construction in minimum time steps. The key to this problem lies in the goal position estimation to enable more efficient robot movements. We propose a novel algorithm, namely NeuralCoMapping, which takes advantage of both approaches.
  arXiv  Detail & Related papers  (2022-03-30T14:03:17Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• Towards Coordinated Robot Motions: End-to-End Learning of Motion Policies on Transform Trees [63.31965375413414]
  We propose to solve multi-task problems through learning structured policies from human demonstrations. Our structured policy is inspired by RMPflow, a framework for combining subtask policies on different spaces. We derive an end-to-end learning objective function that is suitable for the multi-task problem.
  arXiv  Detail & Related papers  (2020-12-24T22:46:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.