Lazy Incremental Search

The objective of lazy planning framework is to reduce the unnecessary edge evaluations during search by utilizing heuristic paths. To achieve minimal edge evaluations, the lazy search algorithms first compute the heuristics paths without edge evaluations and then restrict the evaluations only to the optimal path candidates found heuristically. We leverage the idea of lazy search to improve the performance of incremental search algorithms which use previous search results to facilitate a new optimal path in a dynamic environment.
Our proposed lazy incremental search method enables more efficient replanning than the existing incremental search algorithms.

Publications

Lazy Lifelong Planning for Efficient Replanning in Graphs with Expensive Edge Evaluation
Lim, J., Srinivasa, S., and Tsiotras, P., “Lazy Lifelong Planning for Efficient Replanning in Graphs with Expensive Edge Evaluation,” arXiv e-prints, arXiv:2105.12076, May. 2021.