Multi Graph Search for High-Dimensional Robot Motion Planning

Left: Mobile manipulators in warehouse settings demand efficient, predictable motion planning. Middle: MGS anchors search at key states and grows multiple subgraphs simultaneously, yielding a solution with a substantial reduction in search efforts. Right: Weighted-A* expands significantly more states to solve the same problem.

Abstract

Efficient motion planning for high-dimensional robotic systems, such as manipulators and mobile manipulators, is critical for real-time operation and reliable deployment. Although advances in planning algorithms have enhanced scalability to high-dimensional state spaces, these improvements often come at the cost of generating unpredictable, inconsistent motions or requiring excessive computational resources and memory.

In this work, we introduce Multi-Graph Search (MGS), a search-based motion planning algorithm that generalizes classical unidirectional and bidirectional search to a multi-graph setting. MGS maintains and incrementally expands multiple implicit graphs over the state space, focusing exploration on high-potential regions while allowing initially disconnected subgraphs to be merged through feasible transitions as the search progresses. We prove that MGS is complete and bounded-suboptimal, and empirically demonstrate its effectiveness on a range of manipulation and mobile manipulation tasks.

Method Overview

MGS is motivated by the observation that humans often solve complex tasks by identifying "mental landmarks" - promising regions of the state space that guide efficient problem-solving. We leverage this intuition by introducing a planning algorithm that searches using a set of key states distributed throughout the state space.

Unlike traditional search-based methods that progress unidirectionally from start to goal, our approach simultaneously explores multiple promising directions anchored by these key states, which serve as intermediate landmarks to structure and focus the search. This multi-directional search strategy enables efficient exploration of high-dimensional spaces while preserving the deterministic behavior and theoretical guarantees of classical search-based planners.

Key Contributions

A multi-directional heuristic search algorithm that performs simultaneous searches rooted at a set of key states distributed throughout the configuration space.
Theoretical analysis establishing completeness and bounded suboptimality with respect to discretization guarantees.
A principled strategy for selecting key states (graph roots) to identify promising regions for avoiding collisions.
Extensive simulation experiments and real-world demonstrations showing improved performance and reliability over traditional baselines.

Experiments

We evaluate MGS on a variety of manipulation and mobile manipulation tasks, comparing against state-of-the-art sampling-based and search-based planners. Our experiments demonstrate that MGS achieves significant improvements in planning time while maintaining solution quality guarantees.

Manipulation Tasks

We test MGS on challenging manipulation scenarios including shelf rearrangement, cage extraction, and bin picking tasks with a 7-DOF robot arm.

Constrained Environments

MGS excels in highly constrained environments where finding collision-free paths through narrow passages is critical.

Bin Picking

Complex bin picking scenarios require efficient exploration of high-dimensional configuration spaces.

Mobile Manipulation (9+ DOF)

We evaluate MGS on challenging mobile manipulation scenarios with a mobile base and 7-DOF arm, resulting in 9+ dimensional configuration spaces.

Table

Shelves & Bins

Rod

Tall Shelf

Results

MGS demonstrates substantial improvements over baseline methods across all experimental scenarios. By anchoring search at key states and growing multiple subgraphs simultaneously, MGS achieves:

Reduced search effort: Significantly fewer state expansions compared to unidirectional search methods.
Faster planning times: Improved computational efficiency in high-dimensional spaces.
Consistent behavior: Deterministic results with bounded suboptimality guarantees.
Scalability: Effective performance on mobile manipulation tasks with 9+ DOF.

BibTeX

@article{mishani2026mgs,
  author    = {Mishani, Itamar and Likhachev, Maxim},
  title     = {Multi Graph Search for High-Dimensional Robot Motion Planning},
  year      = {2026},
}