A Discussion on the Scalability of Heuristic Approximators (Extended Abstract)
Sumedh Pendurkar, Taoan Huang, Sven Koenig, Guni Sharon · Proceedings of the International Symposium on Combinatorial Search · 2022
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.