運動学的に基づく部分木重複度によるソフト重複検出の改善
Improved Soft Duplicate Detection in Search-Based Motion Planning
連続空間の探索型動作計画において、後続状態の到達可能性（部分木の重なり）を用いて状態の重複度を測る新しい指標を提案し、局所解への停滞を抑える。
著者: Nader Maray, Anirudh Vemula, Maxim Likhachev
分類: cs.RO
原文アブストラクト
Search-based techniques have shown great success in motion planning problems such as robotic navigation by discretizing the state space and precomputing motion primitives. However in domains with complex dynamic constraints, constructing motion primitives in a discretized state space is non-trivial. This requires operating in continuous space which can be challenging for search-based planners as they can get stuck in local minima regions. Previous work on planning in continuous spaces introduced soft duplicate detection which requires search to compute the duplicity of a state with respect to previously seen states to avoid exploring states that are likely to be duplicates, especially in local minima regions. They propose a simple metric utilizing the euclidean distance between states, and proximity to obstacles to compute the duplicity. In this paper, we improve upon this metric by introducing a kinodynamically informed metric, subtree overlap, between two states as the similarity between their successors that can be reached within a fixed time horizon using kinodynamic motion primitives. This captures the intuition that, due to robot dynamics, duplicate states can be far in euclidean distance and result in very similar successor states, while non-duplicate states can be close and result in widely different successors.
