The Provable Virtue of Laziness in Motion Planning

Authors

  • Nika Haghtalab Carnegie Mellon University
  • Simon Mackenzie Carnegie Mellon University
  • Ariel Procaccia Carnegie Mellon University
  • Oren Salzman Carnegie Mellon University
  • Siddhartha Srinivasa Carnegie Mellon University

Keywords:

Motion planning, robotics, Path planning

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; 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.

Downloads

Published

2018-06-15

How to Cite

Haghtalab, N., Mackenzie, S., Procaccia, A., Salzman, O., & Srinivasa, S. (2018). The Provable Virtue of Laziness in Motion Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 106-113. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/13879