NSF-BSF: RI: Small: Scalable Learning in Heuristic Search

Pathfinding problems are a common issue in computation. Pathfinding is the search that a computer program makes for the shortest route between points. It is common is a very common issue in computation in the natural sciences and mathematics, who may have multiple potential pathways that use considerable computational power or even human intervention to test.

Therefore, finding efficient solutions to pathfinding problems is crucial for technological advancement. Recent research has shown that the combination of two artificial intelligence methods, namely machine learning and heuristic search, can, in principle, solve any pathfinding problem without human assistance. This project aims to scale this approach to more complex pathfinding problems by investigating novel ways of applying machine learning to heuristic search to create an approach that learns to adapt to the problem at hand.

This will result in computational approaches that can efficiently solve a wider array of real-world problems.

Search algorithms have been integral to artificial intelligence. Heuristic search, specifically, has played a crucial role in problem-solving across diverse applications including robotics, chemical synthesis, quantum computing, theorem proving, and puzzles. However, the effectiveness of heuristic search is contingent on accurate heuristic functions, which estimate the cost to solve a problem from a given state.

Constructing heuristic functions often requires domain-specific knowledge which may entail months or years of research, depending on the application. To address this limitation, recent research explores the use of deep neural networks and reinforcement learning to learn heuristic functions, achieving optimal or near-optimal solutions in various domains.

Despite these advancements, learned heuristic functions face challenges in scaling with increased problem complexity, leading to inefficient solutions or failure in finding a solution. This project aims to enhance the scalability of heuristic search by investigating four novel applications of machine learning to heuristic search: (1) dynamic heuristic functions -- heuristic functions that can update themselves based on search instead of remaining static, (2) heuristic ensembles -- combining multiple heuristic functions in to one, (3) learning how to search -- use machine learning to learn better search algorithms, and (4) learning in bidirectional search -- use machine learning to learn better bidirectional search algorithms. The project will use puzzle solving, chemical synthesis, and theorem proving for evaluation.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.