Multi Graph Search for High-Dimensional Robot Motion Planning

• URL: http://arxiv.org/abs/2602.12096v1
• Date: Thu, 12 Feb 2026 15:50:15 GMT
• Title: Multi Graph Search for High-Dimensional Robot Motion Planning
• Abstract summary: Multi-Graph Search (MGS) is a search-based motion planning algorithm that generalizes classical unidirectional and bidirectional search to a multi-graph setting.<n>We prove that MGS is complete and bounded-suboptimal, and empirically demonstrate its effectiveness on a range of manipulation and mobile manipulation tasks.
• Score: 18.868434737285412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. Demonstrations, benchmarks and code are available at https://multi-graph-search.github.io/.

Related papers

• Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia Datasets [0.0]
  This paper introduces the Dynamic Exploration Graph (DEG), an extension of the continuous refining Exploration Graph.<n>At the core of the DEG design are two key innovations: a novel deletion algorithm which guarantees graph connectivity and a data distribution-agnostic method for graph expansion.<n> Empirical experiments in both streaming and online scenarios demonstrate the superior performance of the DEG.
  arXiv  Detail & Related papers  (2026-07-30T03:50:40Z)
• An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval [0.0]
  This paper presents a "continuous refining Exploration Graph" (crEG)<n>It is a novel approach for rapidly constructing a compact exploration graph with state-of-the-art search performance.<n>Both algorithms are specifically designed to produce and operate on undirected graphs with even degrees.
  arXiv  Detail & Related papers  (2026-07-30T03:22:17Z)
• Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets [4.512110686124693]
  We present an algorithmic framework based on graphs of space-time convex sets (ST-GCSs)<n>For multi-robot motion planning, we integrate ST-GCS planning and ECD into prioritized planning methods.<n>For large-scale demonstrations, the proposed multi-robot motion planner can solve instances with up to $100$ robots within only a few minutes.
  arXiv  Detail & Related papers  (2026-07-01T04:58:00Z)
• GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions [54.570944939061555]
  We present a comprehensive study of GPU-accelerated graph-based vector search algorithms.<n>We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units.<n>Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems.
  arXiv  Detail & Related papers  (2026-02-10T16:18:04Z)
• Generalizable Geometric Prior and Recurrent Spiking Feature Learning for Humanoid Robot Manipulation [90.90219129619344]
  This paper presents a novel R-prior-S, Recurrent Geometric-priormodal Policy with Spiking features.<n>To ground high-level reasoning in physical reality, we leverage lightweight 2D geometric inductive biases.<n>For the data efficiency issue in robotic action generation, we introduce a Recursive Adaptive Spiking Network.
  arXiv  Detail & Related papers  (2026-01-13T23:36:30Z)
• TGM: a Modular and Efficient Library for Machine Learning on Temporal Graphs [45.81179802109882]
  We introduce Temporal Graph Modelling (TGM), a research-oriented library for Machine Learning on temporal graphs.<n>TGM offers first-class support for dynamic node features, time-granularity conversions, and native handling of link-, node-, and graph-level tasks.<n> Empirically, TGM achieves an average 7.8x speedup across multiple models, datasets, and tasks compared to the widely used DyGLib.
  arXiv  Detail & Related papers  (2025-10-08T22:20:05Z)
• Search-Based Robot Motion Planning With Distance-Based Adaptive Motion Primitives [1.8874301050354767]
  This work proposes a motion planning algorithm for robotic manipulators that combines sampling-based and search-based planning methods.<n>The core contribution of the proposed approach is the usage of burs of free configuration space (C-space) as adaptive motion primitives.<n>Results demonstrate that the bur-based approach outperforms fixed-primitive planning in complex scenarios.
  arXiv  Detail & Related papers  (2025-07-01T21:33:33Z)
• Divide by Question, Conquer by Agent: SPLIT-RAG with Question-Driven Graph Partitioning [62.640169289390535]
  SPLIT-RAG is a multi-agent RAG framework that addresses the limitations with question-driven semantic graph partitioning and collaborative subgraph retrieval.<n>The innovative framework first create Semantic Partitioning of Linked Information, then use the Type-Specialized knowledge base to achieve Multi-Agent RAG.<n>The attribute-aware graph segmentation manages to divide knowledge graphs into semantically coherent subgraphs, ensuring subgraphs align with different query types.<n>A hierarchical merging module resolves inconsistencies across subgraph-derived answers through logical verifications.
  arXiv  Detail & Related papers  (2025-05-20T06:44:34Z)
• Global Tensor Motion Planning [18.678206099088843]
  Global Motion Planning (GTMP) is a sampling-based motion planning algorithm comprising only tensor operations.<n>We introduce a novel discretization structure represented as a random multipartite graph, enabling efficient vectorized sampling, collision checking, and search.<n> Experiments on lidar-scanned occupancy maps and the MotionBenchMarker dataset demonstrate GTMP's efficiency in batch planning compared to baselines.
  arXiv  Detail & Related papers  (2024-11-28T22:07:46Z)
• DyG-Mamba: Continuous State Space Modeling on Dynamic Graphs [59.434893231950205]
  Dynamic graph learning aims to uncover evolutionary laws in real-world systems. We propose DyG-Mamba, a new continuous state space model for dynamic graph learning. We show that DyG-Mamba achieves state-of-the-art performance on most datasets.
  arXiv  Detail & Related papers  (2024-08-13T15:21:46Z)
• Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences [20.879194337982803]
  Multi-Agent Path-Finding (MAPF) algorithms have shown promise in discrete 2D domains, providing rigorous guarantees. We propose an approach for accelerating conflict-based search algorithms by leveraging their repetitive and incremental nature.
  arXiv  Detail & Related papers  (2024-03-29T20:31:07Z)
• TAS: A Transit-Aware Strategy for Embodied Navigation with Non-Stationary Targets [55.09248760290918]
  We present a novel algorithm for navigation in dynamic scenarios with non-stationary targets.<n>Our novel Transit-Aware Strategy (TAS) enriches embodied navigation policies with object path information.<n> TAS improves performance in non-stationary environments by rewarding agents for synchronizing their routes with target routes.
  arXiv  Detail & Related papers  (2024-03-14T22:33:22Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  We present SimTeG, a frustratingly Simple approach for Textual Graph learning. We first perform supervised parameter-efficient fine-tuning (PEFT) on a pre-trained LM on the downstream task. We then generate node embeddings using the last hidden states of finetuned LM.
  arXiv  Detail & Related papers  (2023-08-03T07:00:04Z)
• Scalable Multi-agent Covering Option Discovery based on Kronecker Graphs [49.71319907864573]
  In this paper, we propose multi-agent skill discovery which enables the ease of decomposition. Our key idea is to approximate the joint state space as a Kronecker graph, based on which we can directly estimate its Fiedler vector. Considering that directly computing the Laplacian spectrum is intractable for tasks with infinite-scale state spaces, we further propose a deep learning extension of our method.
  arXiv  Detail & Related papers  (2023-07-21T14:53:12Z)
• ReVoLT: Relational Reasoning and Voronoi Local Graph Planning for Target-driven Navigation [1.0896567381206714]
  Embodied AI is an inevitable trend that emphasizes the interaction between intelligent entities and the real world. Recent works focus on exploiting layout relationships by graph neural networks (GNNs) We decouple this task and propose ReVoLT, a hierarchical framework.
  arXiv  Detail & Related papers  (2023-01-06T05:19:56Z)

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.