接線に基づく効率的なトポロジー多様経路探索
An efficient tangent based topologically distinctive path finding for grid maps
グリッドマップ上で接線グラフを利用し、多数のトポロジー的に異なる経路をリアルタイムに生成する手法を提案。キューに優先度制約を導入し、既存手法より高効率で約320本の経路を100ms以内に生成できることを示した。
分類: cs.RO
原文アブストラクト
Conventional local planners frequently become trapped in a locally optimal trajectory, primarily due to their inability to traverse obstacles. Having a larger number of topologically distinctive paths increases the likelihood of finding the optimal trajectory. It is crucial to generate a substantial number of topologically distinctive paths in real-time. Accordingly, we propose an efficient path planning approach based on tangent graphs to yield multiple topologically distinctive paths. Diverging from existing algorithms, our method eliminates the necessity of distinguishing whether two paths belong to the same topology; instead, it generates multiple topologically distinctive paths based on the locally shortest property of tangents. Additionally, we introduce a priority constraint for the queue during graph search, thereby averting the exponential expansion of queue size. To illustrate the advantages of our method, we conducted a comparative analysis with various typical algorithms using a widely recognized public dataset\footnote{https://movingai.com/benchmarks/grids.html}. The results indicate that, on average, our method generates 320 topologically distinctive paths within a mere 100 milliseconds. This outcome underscores a significant enhancement in efficiency when compared to existing methods. To foster further research within the community, we have made the source code of our proposed algorithm publicly accessible\footnote{https://joeyao-bit.github.io/posts/2023/09/07/}. We anticipate that this framework will significantly contribute to the development of more efficient topologically distinctive path planning, along with related trajectory optimization and motion planning endeavors.
