Author name cluster

Forest Agostinelli

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

15 papers

2 author rows

AAAI Conference 2026 Conference Paper

Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search

Gal Hadar
Forest Agostinelli
Shahaf S. Shperberg

Many sequential decision-making problems can be formulated as shortest-path problems, where the objective is to reach a goal state from a given starting state. Heuristic search is a standard approach for solving such problems, relying on a heuristic function to estimate the cost to the goal from any given state. Recent approaches leverage reinforcement learning to learn heuristics by applying deep approximate value iteration. These methods typically rely on single-step Bellman updates, where the heuristic of a state is updated based on its best neighbor and the corresponding edge cost. This work proposes a generalized approach that enhances both state sampling and heuristic updates by performing limited-horizon searches and updating each state's heuristic based on the shortest path to the search frontier, incorporating both edge costs and the heuristic values of frontier states.

PDF Details DOI

PRL Workshop 2025 Workshop Paper

Beyond Single-Step Updates: Reinforcement Learning of Heuristics with Limited-Horizon Search

Gal Hadar
Forest Agostinelli
Shahaf S. Shperberg

Many sequential decision-making problems can be formulated as shortest-path problems, where the objective is to reach a goal state from a given starting state. Heuristic search is a standard approach for solving such problems, relying on a heuristic function to estimate the cost to the goal from any given state. Recent approaches leverage reinforcement learning to learn heuristics by applying deep approximate value iteration. These methods typically rely on single-step Bellman updates, where the heuristic of a state is updated based on its best neighbor and the corresponding edge cost. This work proposes a generalized approach that enhances both state sampling and heuristic updates by performing limitedhorizon searches and updating each state’s heuristic based on the shortest path to the search frontier, incorporating both edge costs and the heuristic values of frontier states.

PDF Details

PRL Workshop 2025 Workshop Paper

Inductive Logic Programming for Heuristic Search

Rojina Panta
Vedant Khandelwal
Celeste Veronese
Amit Sheth
Daniele Meli
Forest Agostinelli

Pathfinding problems are found through computing, chemistry, mathematics, and robotics. Solving pathfinding problems is typically achieved through heuristic search, which is guided by a heuristic function that can be learned using deep neural networks. However, since deep neural networks are typically not explainable, the extraction of new knowledge from these learned heuristic functions is cumbersome. On the other hand, to the best of our knowledge, it has yet to be shown how heuristic functions represented as logic programs, which have been shown to be explainable, can be learned. In this work, we present an algorithm to learn heuristic functions represented as logic programs using dynamic programming and inductive logic programming. Furthermore, we build on dynamic programming concepts to improve the learned logic programs by reusing predicates learned for solving simpler pathfinding problem instances to solve more complex instances. We use the 8-puzzle to demonstrate the effectiveness of our algorithm. Code — https: //github. com/Rojina99/HeurSearchILP

PDF Details

PRL Workshop 2025 Workshop Paper

Learning to Learn from Search

Forest Agostinelli
Shahaf S. Shperberg

The effectiveness of heuristic search when solving pathfinding problems often relies on the accuracy of the heuristic function. While it has been shown that heuristic functions can be learned using deep reinforcement learning, it is assumed that learning is only performed once and that the heuristic function remains fixed when attempting to solve a problem instance. However, heuristic search, itself, produces data from which a heuristic function can learn. For example, given the nodes expanded during search, Bellman updates of the states associated with those nodes can be quickly computed. In this paper, we introduce Learning to Learn from Search (L2LFS), an algorithm that trains a sequence of heuristic functions, where each heuristic function in the sequence learns from data obtained when performing heuristic search with the previous heuristic function. We will show that data obtained during search can be encoded into a fixed length encoding and that this data can be used to train a subsequent heuristic function that better estimates Bellman updates when compared to one that does not use this encoding. Future work will refine and repeat this process multiple times in hopes of yielding iteratively improving heuristic functions. computed. This data can be used to improve a subsequent heuristic function that would then be used in a subsequent search. This process can then be repeated with the objective of yielding iteratively improving heuristic functions. In this paper, we introduce learning to learn from search (L2LFS), an algorithm that builds on DeepCubeA (Agostinelli et al. 2019) to train heuristic functions to improve their cost-to-go estimation (i. e. , learn) based on data obtained from search. Data obtained during search that is used to improve a subsequent heuristic function is referred to as the search summary. A heuristic function that also takes a search summary as an input is referred to as a summaryaware heuristic function (SAHF). In this paper, we make the following contributions: • Showing that search summaries can be encoded into a fixed-length representation. • Leveraging this encoding to train SAHFs that learn from search. • Showing that SAHFs better estimate the Bellman updates of states seen during a subsequent search when compared to a heuristic function that is not summary-aware.

PDF Details

PRL Workshop 2025 Workshop Paper

Quantum Circuit Synthesis with Deep Reinforcement Learning and Heuristic Search

Ian Turner
Peng Fu
Forest Agostinelli

Quantum circuit synthesis is the process of implementing a quantum algorithm with a given discrete gate set. In this paper, we first show how this problem can be posed as a pathfinding problem. Next, we use DeepCubeA to learn a heuristic function for quantum circuit synthesis for one to three qubit circuits with deep reinforcement learning and solve problem instances with batch weighed A* search. We compare our approach against several other state-of-the-art quantum circuit synthesis algorithms and show that are our approach is competitive.

PDF Details

HAXP Workshop 2024 Workshop Paper

A Conflict-Driven Approach for Reaching Goals Specified with Negation as Failure

Forest Agostinelli

First-order logic allows for the expressive specification of goals. Using negation as failure, one can specify what must not be true in a goal state instead of what must be true, which can result in succinct goal specifications while also being computationally advantageous. However, due to non-monotonicity, integration of negation as failure and recent deep reinforcement learning methods that incorporate first-order logic in goal specification can be cumbersome. To address this problem, we create a conflict-driven algorithm for non-monotonic goal specification that refines search for a goal state based on conflicts encountered during search. Our results show that this conflict-driven approach results in significantly shorter paths and can significantly speed up search when compared to not taking conflicts into consideration. Furthermore, our results show that finding paths to goals can be much more efficient when goals are specified with negation as failure instead of without negation as failure.

PDF

PRL Workshop 2024 Workshop Paper

Finding Reaction Mechanism Pathways with Deep Reinforcement Learning and Heuristic Search

Rojina Panta
Mohammadamin Tavakoli
Christian Geils
Pierre Baldi
Forest Agostinelli

Artificial intelligence (AI) has been used to predict the outcomes of chemical reactions. However, most of these reaction predictors are designed to predict the major outcome of overall transformations, skipping the chemical reactions at a mechanistic level. Therefore, we are unable to identify intermediates and byproducts of the reaction. Information on the reaction mechanisms enable practitioners to validate the feasibility of that reaction, identify intermediate molecules, improve reaction efficiency, and anticipate the results of similar reactions under various conditions. Despite recent efforts in developing mechanistic reaction predictors, predicting the sequence of mechanistic reactions given the reactants and products is currently an open area of research in chemistry. To address this issue, we use DeepCubeA with Hindsight Experience Replay to learn a heuristic function that generalizes over start and goal states to guide A* search to predict the sequence of mechanistic reactions of an overall chemical transformation, from reactants to products. problem, we will pose finding a sequence of reaction mechanisms as a pathfinding problem where the start states are reactants and the goal states are products. We will build on the DeepCubeA (Agostinelli et al. 2019) algorithm to learn a heuristic function represented as a deep neural network (DNN) (Schmidhuber 2015) with deep reinforcement learning and use the learned heuristic function with A* search (Hart, Nilsson, and Raphael 1968) to find paths. Overall Transformation S O Cl S Cl O S OH O Cl Major Product 1 S S Cl 21 O 10 OH 10 S 20 O Cl O Cl H O+ S 20 O- Cl 21 10=20; 20, 21=21

PDF Details

RLC Conference 2024 Conference Paper

Learning Discrete World Models for Heuristic Search

Forest Agostinelli
Misagh Soltani

For many sequential decision making problems, planning is often necessary to find solutions. However, for domains such as those encountered in robotics, the transition function, also known as the world model, is often unknown. While model-based reinforcement learning methods learn world models that can then be used for planning, such approaches are limited by errors that accumulate when the model is applied across many timesteps as well as the inability to re-identify states during planning. To solve these problems, we introduce DeepCubeAI, an algorithm that learns a world model that represents states in a discrete latent space, uses reinforcement learning to learn a heuristic function that generalizes over start and goal states using this learned model, and combines the learned model and learned heuristic function with heuristic search to solve problems. Since the latent space is discrete, we can prevent the accumulation of small errors by rounding and we can re-identify states by simply comparing two binary vectors. In our experiments on a pixel representation of the Rubik's cube, Sokoban, IceSlider, and DigitJump, we find that DeepCubeAI is able to apply the model for thousands of steps without accumulating any error. Furthermore, DeepCubeAI solves over 99% of test instances in all domains, generalizes across goal states, and significantly outperforms a greedy policy that does not plan with the learned world model.

PDF Details

RLJ Journal 2024 Journal Article

Learning Discrete World Models for Heuristic Search

Forest Agostinelli
Misagh Soltani

PDF Details

PRL Workshop 2024 Workshop Paper

Q* Search: Heuristic Search with Deep Q-Networks

Forest Agostinelli
Shahaf S. Shperberg
Alexander Shmakov
Stephen Marcus McAleer
Roy Fox
Pierre Baldi

Efficiently solving problems with large action spaces using A* search has been of importance to the artificial intelligence community for decades. This is because the computation and memory requirements of A* search grow linearly with the size of the action space. This burden becomes even more apparent when A* search uses a heuristic function learned by computationally expensive function approximators, such as deep neural networks. To address this problem, we introduce Q* search, a search algorithm that uses deep Q-networks to guide search in order to take advantage of the fact that the sum of the transition costs and heuristic values of the children of a node can be computed with a single forward pass through a deep Q-network without explicitly generating those children. This significantly reduces computation time and requires only one node to be generated per iteration. We use Q* search on different domains and action spaces, showing that Q* suffers from only a small runtime overhead as the action size increases. In addition, our empirical results show Q* search is up to 129 times faster and generates up to 1288 times fewer nodes than A* search. Finally, although obtaining admissible heuristic functions from deep neural networks is an ongoing area of research, we prove that Q* search is guaranteed to find a shortest path given a heuristic function does not overestimate the sum of the transition cost and cost-to-go of the state.

PDF Details

ICAPS Conference 2024 Conference Paper

Specifying Goals to Deep Neural Networks with Answer Set Programming

Forest Agostinelli
Rojina Panta
Vedant Khandelwal

Recently, methods such as DeepCubeA have used deep reinforcement learning to learn domain-specific heuristic functions in a largely domain-independent fashion. However, such methods either assume a predetermined goal or assume that goals will be given as fully-specified states. Therefore, specifying a set of goal states to these learned heuristic functions is often impractical. To address this issue, we introduce a method of training a heuristic function that estimates the distance between a given state and a set of goal states represented as a set of ground atoms in first-order logic. Furthermore, to allow for more expressive goal specification, we introduce techniques for specifying goals as answer set programs and using answer set solvers to discover sets of ground atoms that meet the specified goals. In our experiments with the Rubik

Details

HAXP Workshop 2023 Workshop Paper

Specifying Goals to Deep Neural Networks with Answer Set Programming

Forest Agostinelli

The ability to easily and unambiguously specify a goal to a planner is fundamental to human-AI collaboration and knowledge discovery. Recently, deep reinforcement learning has been used to train deep neural networks (DNNs) as heuristic functions for planning problems. While DNNs can be powerful function approximators that, combined with reinforcement learning, require little to no domain-specific knowledge to learn, there is no formal way to specify goals to DNNs. We introduce a method of training DNN heuristic functions to estimate the distance between a given state and a goal, where a goal is represented as a set of atoms in first-order logic. We then use answer set programming to specify goals, where a set of atoms representing a goal is obtained from the stable model of an answer set program. The DNN heuristic function is then combined with search to reach goals. In our experiments with the Rubik's cube and Sokoban, we show that we can specify and reach a variety of different goals without any need to re-train the DNN. Furthermore, since the specification language is first-order logic, one can specify a goal without having to know what states meet that specification, beforehand. Therefore, our approach can also be used to discover states that meet a given specification.

Details

AAAI Conference 2022 System Paper

ALLURE: A Multi-Modal Guided Environment for Helping Children Learn to Solve a Rubik’s Cube with Automatic Solving and Interactive Explanations

Kausik Lakkaraju
Thahimum Hassan
Vedant Khandelwal
Prathamjeet Singh
Cassidy Bradley
Ronak Shah
Forest Agostinelli
Biplav Srivastava

Modern artificial intelligence (AI) methods have been used to solve problems that many humans struggle to solve. This opens up new opportunities for knowledge discovery and education. We demonstrate ALLURE, a collaborative educational AI system for learning to solve the Rubik’s cube that is designed to help students improve their problem solving skills. ALLURE can both find its own strategies for solving the Rubik’s cube and explain those strategies to humans. In the future, ALLURE will also be able to collaborate with humans by building on user-provided strategies for solving the Rubik’s cube and as well as generalize to other search and automated planning problems. Interaction between AI and user is facilitated by visual and natural language modalities.

PDF Details

PRL Workshop 2021 Workshop Paper

Obtaining Approximately Admissible Heuristic Functions through Deep Reinforcement Learning and A* Search

Forest Agostinelli
Stephen McAleer
Alexander Shmakov
Roy Fox
Marco Valtorta
Biplav Srivastava
Pierre Baldi

real world applications would ensure that artificial intelligence agents can solve problems in the most efficient way Deep reinforcement learning has been shown to be able to possible, or close to the most efficient way possible, which train deep neural networks to implement effective heuristic could significantly reduce the resources consumed by such functions that can be used with A* search to solve probagents. lems with large state spaces. However, these learned heuristic Obtaining an admissible heuristic function often requires functions are not guaranteed to be admissible. We introduce domain-specific knowledge. For example, pattern databases approximately admissible conversion, an algorithm that can convert any inadmissible heuristic function into a heuristic (PDBs) (Culberson and Schaeffer 1998) have been sucfunction that is admissible in the vast majority of cases with cessful at finding optimal solutions to puzzles such as the no domain-specific heuristic information. We apply approxiRubik’s cube (Korf 1997), 15-puzzle, and 24-puzzle (Korf mately admissible conversion to heuristic functions parameand Felner 2002; Felner, Korf, and Hanan 2004). Howterized by deep neural networks and show that these heuristic ever, ensuring that these PDBs produce admissible heurisfunctions can be used to find optimal solutions, or bounded tics requires knowledge about how the puzzle pieces intersuboptimal solutions, even when doing a batched version of act. There has been previous research on using deep neuA* search. We test our method on the 15-puzzle and 24ral networks to learn heuristic functions (Chen and Wei puzzle and obtain a heuristic function that is empirically ad2011; Wang et al. 2019; Ferber, Helmert, and Hoffmann missible over 99. 99% of the time and that finds optimal so2020) including the DeepCubeA algorithm (McAleer et al. lutions for 100% of all test configurations. To the best of our knowledge, this is the first demonstration that approximately 2019; Agostinelli et al. 2019) which used deep reinforceadmissible heuristics can be obtained using deep neural netment learning and weighted A* search (Pohl 1970) to solve works in a domain independent fashion. the aforementioned puzzles. However, the heuristic functions produced by DeepCubeA are not admissible. In this paper, we define an approximately admissible

PDF Details

NeurIPS Conference 2013 Conference Paper

Adaptive Multi-Column Deep Neural Networks with Application to Robust Image Denoising

Forest Agostinelli
Michael Anderson
Honglak Lee

Stacked sparse denoising auto-encoders (SSDAs) have recently been shown to be successful at removing noise from corrupted images. However, like most denoising techniques, the SSDA is not robust to variation in noise types beyond what it has seen during training. We present the multi-column stacked sparse denoising autoencoder, a novel technique of combining multiple SSDAs into a multi-column SSDA (MC-SSDA) by combining the outputs of each SSDA. We eliminate the need to determine the type of noise, let alone its statistics, at test time. We show that good denoising performance can be achieved with a single system on a variety of different noise types, including ones not seen in the training set. Additionally, we experimentally demonstrate the efficacy of MC-SSDA denoising by achieving MNIST digit error rates on denoised images at close to that of the uncorrupted images.

PDF Details