用图神经网络加速复杂环境中的路径规划,成功率超99%。
GNN-DIP: Neural Corridor Selection for Decomposition-Based Motion Planning
- 用图神经网络预测通道优先级,引导搜索避开低效区域
- 2D/3D环境下路径规划成功率99%-100%,速度提升2-280倍
- 适合高复杂度静态与动态场景的实时路径规划应用
通过狭窄通道的运动规划仍是核心挑战:基于采样的规划器很少在这些关键区域放置样本,即使样本落入通道,两点间的直线连接也常因靠近障碍物而被碰撞检测拒绝。分解式规划器通过将自由空间划分为凸单元来解决这两个问题——每个通道都被精确表示为单元边界,且单元内任意路径天然无碰撞。然而,随着环境复杂度增加,候选通道数量呈组合爆炸式增长,成为通道选择的瓶颈。本文提出GNN-DIP框架,将图神经网络(GNN)与两阶段分解启发式规划器(DIP)结合。GNN在单元邻接图上预测门户得分,引导通道搜索聚焦近优区域,同时保证完备性。在2D中,采用带飞镖算法的受限Delaunay三角剖分可获得精确最短路径;在3D中,使用斜板凸分解与门户面采样实现近优路径评估。在包含最多246个障碍物的2D狭窄通道场景、3D瓶颈环境及动态2D设置中,GNN-DIP实现了99–100%的成功率,并比基于采样的基线提速2–280倍。
原文摘要 · Abstract (English)
Motion planning through narrow passages remains a core challenge: sampling-based planners rarely place samples inside these narrow but critical regions, and even when samples land inside a passage, the straight-line connections between them run close to obstacle boundaries and are frequently rejected by collision checking. Decomposition-based planners resolve both issues by partitioning free space into convex cells -- every passage is captured exactly as a cell boundary, and any path within a cell is collision-free by construction. However, the number of candidate corridors through the cell graph grows combinatorially with environment complexity, creating a bottleneck in corridor selection. We present GNN-DIP, a framework that addresses this by integrating a Graph Neural Network (GNN) with a two-phase Decomposition-Informed Planner (DIP). The GNN predicts portal scores on the cell adjacency graph to bias corridor search toward near-optimal regions while preserving completeness. In 2D, Constrained Delaunay Triangulation (CDT) with the Funnel algorithm yields exact shortest paths within corridors; in 3D, Slab convex decomposition with portal-face sampling provides near-optimal path evaluation. Benchmarks on 2D narrow-passage scenarios, 3D bottleneck environments with up to 246 obstacles, and dynamic 2D settings show that GNN-DIP achieves 99--100% success rates with 2--280 times speedup over sampling-based baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。