Overview

Tree search represents possible decisions as branches and allocates effort among them to find a path to a goal or a strong strategy. Methods include A* and best-first search with heuristics, Monte Carlo tree search with value estimates, bidirectional search, and learned policies that guide which branches to expand or prune. These approaches are used in motion and classical planning, games, optimization, and language-model agents that reason, use tools, or generate code. A central challenge is balancing broad exploration against costly evaluation and rollout budgets, while ensuring that pruning does not discard useful solutions or undermine guarantees.

Latest papers

64 papers5 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

Aug 22, 2025

PuzzleJAX: A Benchmark for Reasoning and Learning

We introduce PuzzleJAX, a GPU-accelerated puzzle game engine and description language designed to support rapid benchmarking of tree search, reinforcement learning, and LLM reasoning abilities. Unlike existing GPU-accelerated learning environments that provide hard-coded implementations of fixed sets of games, PuzzleJAX allows dynamic compilation of any game expressible in its domain-specific language (DSL). This DSL follows PuzzleScript, which is a popular and accessible online game engine for designing puzzle games. In this paper, we validate in PuzzleJAX several hundred of the thousands of games designed in PuzzleScript by both professional designers and casual creators since its release in 2013, thereby demonstrating PuzzleJAX's coverage of an expansive, expressive, and human-relevant space of tasks. By analyzing the performance of search, learning, and language models on these games, we show that PuzzleJAX can naturally express tasks that are both simple and intuitive to understand, yet often deeply challenging to master, requiring a combination of control, planning, and high-level insight.
Dec 23, 2024

EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis

Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blowup, previous works introduced probabilistic and neural approaches to guide this combinatorial search by inducing heuristic cost functions. Best-first search algorithms ensure to search in the exact order induced by the cost function, significantly reducing the portion of the program space to be explored. A key limitation of existing best-first search algorithms is that they slow down over time: the delay between outputting successive programs grows with the number of programs already generated. We ask whether best-first search algorithms with constant delay exist. We design Eco Search, a new best-first bottom-up search algorithm. It combines the cost tuple representation of Bee Search with the per non-terminal data structures of Heap Search, thanks to a new frugal expansion strategy, and it uses bucket queues instead of priority queues, which is possible because the costs stored in each queue always lie in a window of constant width. We prove that Eco Search is the first constant-delay best-first search algorithm for pre-generation cost functions. Experimentally, we evaluate Eco Search on two classic program-synthesis benchmarks (DeepCoder and FlashFill) and observe that Eco Search solves 12% to 70% more tasks than its predecessors, and reaches the number of tasks they solve 1.6 to 3.2 times faster. This shows that constant delay can be achieved for best-first search in program synthesis, and that it makes a difference in practice.
May 6, 2024

Greedy Heuristics for Sampling-Based Motion Planning in High-Dimensional State Spaces

Informed sampling techniques accelerate the convergence of sampling-based motion planners by biasing sampling toward regions of the state space that are most likely to yield better solutions. However, when the current solution path contains redundant or tortuous segments, the resulting informed subset may remain unnecessarily large, slowing convergence. Our prior work addressed this issue by introducing the greedy informed set, which reduces the sampling region based on the maximum heuristic cost along the current solution path. In this article, we formally characterize the behavior of the greedy informed set within Rapidly-exploring Random Tree (RRT*)-like planners and analyze how greedy sampling affects exploration and asymptotic optimality. We then present Greedy RRT* (G-RRT*), a bi-directional anytime variant of RRT* that leverages the greedy informed set to focus sampling in the most promising regions of the search space. Experiments on abstract planning benchmarks, manipulation tasks from the MotionBenchMaker dataset, and a dual-arm Barrett WAM problem demonstrate that G-RRT* rapidly finds initial solutions and converges asymptotically to optimal paths, outperforming state-of-the-art sampling-based planners.
Aug 4, 2023

Solving Witness Triangle Puzzles Faster with an Automatically Learned Predicate

The Witness is a game with combinatorial puzzles that are challenging for both human players and AI solvers. Search-based AI solvers can require large amounts of time to solve such puzzles. We accelerate search by automatically learning a predicate that predicts whether a partial path to a Witness puzzle is completable to a solution path. We demonstrate that our learned predicate is human-explainable, which makes it amenable to proofs, and we prove a key property that allows us to use it for pruning successor states in search. Doing so accelerates search by about six times while maintaining search completeness. Conversely, given a fixed time budget per puzzle, our predicate-accelerated search can solve more puzzles of larger sizes than a baseline search using a hand-coded predicate. Finally, we empirically demonstrate how accelerating search using an automatically learned predicate can outperform two competitors, weighted A* and Levin tree search with neural networks, in terms of time and number of nodes expanded.