The Provable Virtue of Laziness in Motion Planning

Nika Haghtalab, Simon Mackenzie, Ariel D. Procaccia, Oren Salzman, Siddhartha S. Srinivasa

IJCAI 2019 pp. 6161-6165

doi:10.24963/IJCAI.2019/855 /ijcai/2019/haghtalab2019ijcai-provable/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Haghtalab et al. "The Provable Virtue of Laziness in Motion Planning." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/855

Markdown

[Haghtalab et al. "The Provable Virtue of Laziness in Motion Planning." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/haghtalab2019ijcai-provable/) doi:10.24963/IJCAI.2019/855

BibTeX

@inproceedings{haghtalab2019ijcai-provable,
  title     = {{The Provable Virtue of Laziness in Motion Planning}},
  author    = {Haghtalab, Nika and Mackenzie, Simon and Procaccia, Ariel D. and Salzman, Oren and Srinivasa, Siddhartha S.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {6161-6165},
  doi       = {10.24963/IJCAI.2019/855},
  url       = {https://mlanthology.org/ijcai/2019/haghtalab2019ijcai-provable/}
}