A Discussion on the Scalability of Heuristic Approximators (Extended Abstract)

Authors

  • Sumedh Pendurkar Texas A&M University
  • Taoan Huang University of Southern California
  • Sven Koenig University of Southern California
  • Guni Sharon Texas A&M University

Keywords:

Machine And Deep Learning In Search, Combinatorial Optimization

Abstract

In this work, we examine a line of recent publications that propose to use deep neural networks to approximate the goal distances of states for heuristic search. We present a first step toward showing that this work suffers from inherent scalability limitations since --- under the assumption that P≠NP --- such approaches require network sizes that scale exponentially in the number of states to achieve the necessary (high) approximation accuracy.

Downloads

Published

2022-07-17