Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement

• URL: http://arxiv.org/abs/2605.20395v1
• Date: Tue, 19 May 2026 18:44:09 GMT
• Title: Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement
• Abstract summary: 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.
• Score: 0.9199488958939335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental challenge in multi-robot motion planning is achieving sufficient coordination to avoid inter-robot conflicts without incurring the large computational expense of searching the joint configuration space of the robot group. In this work, 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. While prior work uses workspace topology to inform when coordination between robots is needed and then composes robots into their joint configuration space, we take a step further by iteratively refining our workspace representation to allow our planner to search smaller, decoupled configuration spaces.

Related papers

• LAMP: Long-Horizon Adaptive Manipulation Planning for Multi-Robot Collaboration in Cluttered Space [6.871611081512488]
  Multi-robot manipulation requires jointly reasoning about contact formations, robot motions under coupled dynamics, and collision avoidance.<n>Existing approaches either learn to solve the problem end-to-end via reinforcement learning or restrict planning to a simpler surrogate problem.<n>We propose a Long-horizon Adaptive Manipulation Planning framework with two planners that enable tractable search over the full coupled space.
  arXiv  Detail & Related papers  (2026-06-28T12:12:48Z)
• Navigating the Clutter: Waypoint-Based Bi-Level Planning for Multi-Robot Systems [54.887871365121775]
  Multi-robot control in cluttered environments is a challenging problem that involves complex physical constraints.<n>We propose a hybrid multi-robot control framework that jointly optimize task and motion planning.<n>Our approach consistently improves task success over motion-agnostic and VLA-based baselines.
  arXiv  Detail & Related papers  (2026-04-22T22:58:47Z)
• Joint Task Assistance Planning via Nested Branch and Bound (Extended Version) [6.531546527140475]
  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.
  arXiv  Detail & Related papers  (2026-02-15T00:04:51Z)
• 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)
• COHERENT: Collaboration of Heterogeneous Multi-Robot System with Large Language Models [49.24666980374751]
  COHERENT is a novel LLM-based task planning framework for collaboration of heterogeneous multi-robot systems.<n>A Proposal-Execution-Feedback-Adjustment mechanism is designed to decompose and assign actions for individual robots.<n>The experimental results show that our work surpasses the previous methods by a large margin in terms of success rate and execution efficiency.
  arXiv  Detail & Related papers  (2024-09-23T15:53:41Z)
• 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)
• 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)
• Optimal task and motion planning and execution for human-robot multi-agent systems in dynamic environments [54.39292848359306]
  We propose a combined task and motion planning approach to optimize sequencing, assignment, and execution of tasks. The framework relies on decoupling tasks and actions, where an action is one possible geometric realization of a symbolic task. We demonstrate the approach effectiveness in a collaborative manufacturing scenario, in which a robotic arm and a human worker shall assemble a mosaic.
  arXiv  Detail & Related papers  (2023-03-27T01:50:45Z)
• Toward Efficient Task Planning for Dual-Arm Tabletop Object Rearrangement [12.928188950810043]
  In a non-monotone rearrangement task, complex object-object dependencies exist that require moving some objects multiple times to solve an instance. We develop effective task planning algorithms for scheduling the pick-n-place sequence that can be properly distributed between the two arms.
  arXiv  Detail & Related papers  (2022-07-17T05:11:14Z)
• Cooperative Task and Motion Planning for Multi-Arm Assembly Systems [32.56644393804845]
  Multi-robot assembly systems are becoming increasingly appealing in manufacturing. Planning for these systems in a manner that ensures each robot is simultaneously productive, and not idle, is challenging. We present a task and motion planning framework that jointly plans safe, low-makespan plans for a team of robots to assemble complex spatial structures.
  arXiv  Detail & Related papers  (2022-03-04T18:12:49Z)
• Show Me What You Can Do: Capability Calibration on Reachable Workspace for Human-Robot Collaboration [83.4081612443128]
  We show that a short calibration using REMP can effectively bridge the gap between what a non-expert user thinks a robot can reach and the ground-truth. We show that this calibration procedure not only results in better user perception, but also promotes more efficient human-robot collaborations.
  arXiv  Detail & Related papers  (2021-03-06T09:14:30Z)
• Combinatorics of a Discrete Trajectory Space for Robot Motion Planning [4.477410849696538]
  complexity of the problem is directly related to the dimension of the robot's configuration space. We present a discrete robot model based on the fundamental hardware specifications of a robot.
  arXiv  Detail & Related papers  (2020-05-25T12:14:20Z)

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.