Most search algorithms, from the classic A* to the modern Monte-Carlo Tree Search (MCTS) used in AlphaZero, represent the future as a tree. In this tree, every sequence of actions is a unique path, and every node is a unique state.
This representation is intuitive but computationally disastrous. In many domains, different paths lead to the exact same outcome—a phenomenon known as a transposition. If you are organizing a shelf, it doesn't matter if you pick up the book first or the vase first; the resulting state is the same. Yet, a standard tree search treats these as two distinct branches, re-evaluating the same subproblems over and over.
The research direction across these papers focuses on "folding" these redundant trees into more efficient structures, such as Directed Acyclic Graphs (DAGs) or abstracted state spaces, to ensure that every unit of computation uncovers something truly new.
The Transposition Problem: From Trees to Graphs
The most direct way to eliminate redundancy is to recognize when two different action sequences arrive at the identical state. In games like Chess or Go, this happens constantly.
Johannes Czech, Kristian Kersting, and Patrick Korus addressed this in Monte-Carlo Graph Search for AlphaZero. By replacing the search tree with a Directed Acyclic Graph (DAG), they allowed the algorithm to share information across different subtrees. If the agent learns that a specific position is losing in one branch, it immediately knows it is losing in all other branches that lead to that same position. This "graph-based" approach significantly boosted playing strength by reducing redundant neural network evaluations.
Similarly, Julia Grosse proposed in Probabilistic DAG search that tree-based models suffer from a combinatorial explosion in problems where the order of decisions is irrelevant, such as feature selection. By collapsing these permutations into a single DAG node, the search space remains manageable.
The Permutation Problem: Partial Order Reduction
Even when states aren't identical, the actions leading to them might be independent. If an agent needs to turn on a light and open a door, the order (Light-then-Door vs. Door-then-Light) is often irrelevant.
This is the core of Partial-Order Reduction (POR). As noted in the 2014 CAV award announcement, pioneers like Patrice Godefroid and Pierre Wolper transformed model checking by recognizing that many execution paths in concurrent systems lead to the same result.
In automated planning, this is often implemented using Stubborn Sets. Martin Wehrle and colleagues have refined this in Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning, showing that by ignoring redundant action permutations, planners can solve complex problems that were previously out of reach. Robert C. Holte further generalized these ideas in A Generalization of Sleep Sets Based on Operator Sequence Redundancy, providing a framework to prune paths where action order does not affect the final outcome.
State and Belief Abstraction
Sometimes, two states aren't identical, but they are "functionally equivalent" for the task at hand. If a robot is searching for a target, two different sensor readings might lead to nearly identical "belief states" about where the target is.
Christian Fritz 0001 explored this in Finding State Similarities for Faster Planning, using regression to identify which variables actually matter for the goal. By grouping states that share these critical variables, the planner avoids redundant work.
In the realm of uncertainty, Moran Barenboim and Vadim Indelman introduced an "abstract observation model" in Adaptive Information Belief Space Planning. Instead of calculating a unique response for every possible future observation, they cluster similar observations together. This allows the agent to plan for groups of outcomes at once, drastically reducing the computational overhead of searching through a belief tree.
Reusability and Memory
A final facet of this research is the transition from "forgetful" search to "persistent" memory. Standard MCTS often discards the intermediate states of a simulation once the value is updated.
Rinu Boney and colleagues argued in Learning to Play Imperfect-Information Games by Imitating an Oracle Planner that this is a waste of expensive data. By reusing generated states, agents can learn more efficiently. Similarly, the ReSPIRe framework by Han Gao and Kangjie Zhou focuses on Informative and Reusable Belief Tree Search, recycling previous computations to maintain high-performance tracking in robots with limited processing power.
By moving away from the rigid structure of the tree and toward graphs, abstractions, and reusable memories, these researchers are making AI planning not just faster, but more fundamentally aware of the structural symmetries of the worlds they navigate.