A Discussion on the Scalability of Heuristic Approximators (Extended Abstract)
DOI:
https://doi.org/10.1609/socs.v15i1.21796Keywords:
Machine And Deep Learning In Search, Combinatorial OptimizationAbstract
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
Issue
Section
Extended Abstracts