Search Reduction through Conservative Abstract-Space Based Heuristic

June 2017

Search Reduction through Conservative Abstract-Space Based Heuristic

Authors:

Ishani Chatterjee, Maxim Likhachev, and Manuela Veloso

Abstract:

The efficiency of heuristic search depends dramatically on the quality of the heuristic function. For an optimal heuristic search, heuristics that estimate cost-to-goal better typically lead to faster searches. For a sub-optimal heuristic search such as weighted A*, the search speed depends more on the correlation between the heuristic and the true cost-to-goal. In this extended abstract, we discuss our preliminary work on computing heuristic functions that exploit this fact. In particular, we introduce a many-to-one mapping from an original search space to a conservative abstract space. Edges in the abstract space capture reachability among all corresponding nodes in the original space. We compute a heuristic in the conservative abstract space which when used by the search in the original space reduces the number of searched nodes. Our preliminary results on 3D navigation show that in more complex scenarios the speedup can be dramatic.
@conference{Chatterjee-2017-122730,
author = {Ishani Chatterjee And Maxim Likhachev And Manuela Veloso},
title = {Search Reduction through Conservative Abstract-Space Based Heuristic},
booktitle = {Proceedings of 10th Annual Symposium on Combinatorial Search (SoCS '17)},
year = {2017},
month = {June},
pages = {161 - 162},
}
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.