動作計画における怠惰の証明された美徳
The Provable Virtue of Laziness in Motion Planning
最短経路に沿った辺のみを評価するLazySPアルゴリズムの辺評価回数について、確率的モデルで解析的な上界を示し、最悪ケースで漸近的に最適であることを証明した論文。
著者: Nika Haghtalab, Simon Mackenzie, Ariel D. Procaccia, Oren Salzman, Siddhartha S. Srinivasa
分類: cs.RO, cs.DS
原文アブストラクト
The Lazy Shortest Path (LazySP) class consists of motion-planning algorithms that only evaluate edges along shortest paths between the source and target. These algorithms were designed to minimize the number of edge evaluations in settings where edge evaluation dominates the running time of the algorithm; but how close to optimal are LazySP algorithms in terms of this objective? Our main result is an analytical upper bound, in a probabilistic model, on the number of edge evaluations required by LazySP algorithms; a matching lower bound shows that these algorithms are asymptotically optimal in the worst case.
