A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration


  • Richard Valenzano University of Alberta
  • Nathan Sturtevant University of Denver
  • Jonathan Schaeffer University of Alberta
  • Fan Xie University of Alberta




Heuristic search, GBFS, Preferred operators, Multi-heuristic best-first search, random exploration, epsilon-greedy node selection


GBFS-based satisficing planners often augment their search with knowledge-based enhancements such as preferred operators and multiple heuristics. These techniques seek to improve planner performance by making the search more informed. In our work, we will focus on how these enhancements impact coverage and we will use a simple technique called epsilon-greedy node selection to demonstrate that planner coverage can also be improved by introducing knowledge-free random exploration into the search. We then revisit the existing knowledge-based enhancements so as to determine if the knowledge these enhancements employ is offering necessary guidance, or if the impact of this knowledge is to add exploration which can be achieved more simply using randomness. This investigation provides further evidence of the importance of preferred operators and shows that the knowledge added when using an additional heuristic is crucial in certain domains, while not being as effective as random exploration in others. Finally, we demonstrate that random exploration can also improve the coverage of LAMA, a planner which already employs multiple enhancements. This suggests that knowledge-based enhancements need to be compared to appropriate knowledge-free random baselines so as to ensure the importance of the knowledge being used.




How to Cite

Valenzano, R., Sturtevant, N., Schaeffer, J., & Xie, F. (2014). A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 375-379. https://doi.org/10.1609/icaps.v24i1.13681