/Heuristic Search on Graphs with Existence Priors for Expensive-to-Evaluate Edges

Heuristic Search on Graphs with Existence Priors for Expensive-to-Evaluate Edges

Venkatraman Narayanan and Maxim Likhachev
Conference Paper, International Conference on Automated Planning and Scheduling (ICAPS), June, 2017

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


We address the problem of finding shortest paths in graphs where some edges have a prior probability of existence, and their existence can be verified during planning with time- consuming operations. Our work is motivated by real-world robot motion planning, where edge existence is often expensive to verify (typically involves time-consuming collision-checking between the robot and world models), but edge existence probabilities are readily available. The goal then, is to develop an anytime algorithm that can return good solutions quickly by somehow leveraging the existence probabilities, and continue to return better-quality solutions or provide tighter suboptimality bounds with more time. While our motivation is fast and high-quality motion planning for robots, this work presents two fundamental contributions applicable to generic graphs with probabilistic edges. They are: a) an algorithm for efficiently computing all relevant shortest paths in a graph with probabilistic edges, and as a by-product the expected shortest path cost, and b) an anytime algorithm for evaluating (verifying existence of) edges in a collection of paths, which is optimal in expectation under a chosen distribution of the algorithm interruption time. Finally, we provide a practical approach to integrate a) and b) in the context of robot motion planning and demonstrate significant improvements in success rate and planning time for a 11 degree-of-freedom mobile manipulation planning problem. We also conduct additional evaluations on a 2D grid navigation domain to study our algorithm’s behavior.

BibTeX Reference
author = {Venkatraman Narayanan and Maxim Likhachev},
title = {Heuristic Search on Graphs with Existence Priors for Expensive-to-Evaluate Edges},
booktitle = {International Conference on Automated Planning and Scheduling (ICAPS)},
year = {2017},
month = {June},
keywords = {robot motion planning, lazy edge evaluation, heuristic search with probabilistic edges, anytime algorithm},