Abstract
The Lazy Shortest Path (LazySP) class consists
of motion-planning algorithms that only evaluate
edges along candidate 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 such as manipulation in cluttered environments and planning for robots in surgical settings; 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