動的に変化するポリゴンマップにおける経路計画のオンボード処理時間削減
Reducing Onboard Processing Time for Path Planning in Dynamically Evolving Polygonal Maps
動的環境のポリゴンマップで最短経路を高速に求めるため、Minimal Constructアルゴリズムを適用し、従来のA*より短時間で滑らかな経路が得られることを示した。
著者: Aditya Shirwatkar, Aman Singh, Jana Ravi Kiran
分類: cs.RO
原文アブストラクト
Autonomous agents face the challenge of coordinating multiple tasks (perception, motion planning, controller) which are computationally expensive on a single onboard computer. To utilize the onboard processing capacity optimally, it is imperative to arrive at computationally efficient algorithms for global path planning. In this work, it is attempted to reduce the processing time for global path planning in dynamically evolving polygonal maps. In dynamic environments, maps may not remain valid for long. Hence it is of utmost importance to obtain the shortest path quickly in an ever-changing environment. To address this, an existing rapid path-finding algorithm, the Minimal Construct was used. This algorithm discovers only a necessary portion of the Visibility Graph around obstacles and computes collision tests only for lines that seem heuristically promising. Simulations show that this algorithm finds shortest paths faster than traditional grid-based A* searches in most cases, resulting in smoother and shorter paths even in dynamic environments.
