Introduction
In discrete planning domains—such as robotic navigation or complex puzzle solving—algorithms frequently rely on a policy to guide their search. Levin Tree Search (LTS) is a prominent example of this approach. However, as problem complexity increases, standard LTS often becomes overwhelmed by the sheer volume of the search tree.
To address this, researchers have traditionally turned to subgoal-based search, which breaks large problems into smaller, manageable pieces. The critical flaw in most current subgoal methods is their reliance on explicitly generating or reconstructing these subgoals, often utilizing heavy neural networks like VQ-VAEs. This explicit generation is computationally expensive, prone to compounding errors, and scales poorly. In "noisy" environments filled with task-irrelevant details, subgoal generators easily become distracted, leading to search failure.
This paper overcomes these limitations by introducing a highly efficient alternative: implicitly decomposing problems into "soft subtasks" through a mechanism known as rerooting. By leveraging state-space clustering and learned heuristics, this approach achieves state-of-the-art training efficiency without the massive computational overhead of explicit subgoal imagination.
Methodology: The Power of Rerooting
The authors build upon the recently introduced $\sqrt{\text{LTS}}$ (Root-LTS) algorithm. Rather than initiating a single search from the starting point, $\sqrt{\text{LTS}}$ implicitly begins a new search at every node it visits. The core innovation lies in the rerooter—a function that determines how much "search budget" to allocate to each potential starting point.
The paper proposes three novel rerooter designs:
- Global/Clustering ($\sqrt{\text{LTS-L}}$): This design uses the Leiden algorithm to cluster the state space into regions based on connectivity. When an agent enters a new or small cluster, the rerooter assigns it more weight, operating on the assumption that the agent has reached a structurally significant bottleneck (e.g., entering a new room).
- Local/Heuristic ($\sqrt{\text{LTS-H}}$): This approach utilizes a learned neural network to estimate the "cost-to-go" (the distance to the goal). Nodes that appear closer to the goal are allocated more search effort.
- Hybrid ($\sqrt{\text{LTS-LH}}$): This design synergizes both signals. Global clustering provides a stable, structural foundation, while the local heuristic refines the search within those specific regions.
Crucially, these rerooting methods are "soft." They do not force the agent to reach a rigidly defined state; instead, they gently nudge the search process to spend more time exploring promising areas.
Experimental Setup
The researchers evaluated their framework across four challenging discrete planning domains:
- BoulderDash: An agent collects diamonds while avoiding falling rocks. Researchers added task-irrelevant "dirt" tiles to artificially increase state-space complexity.
- CraftWorld: A complex environment requiring agents to craft items using a hierarchy of tools and resources, where a single misstep can cause a deadlock.
- Sokoban: The classic PSPACE-hard puzzle involving pushing boxes onto designated targets.
- Traveling Salesman Problem (TSP) in GridWorld: A variant where the agent must visit multiple cities and return home without getting trapped.
Key Findings and Results
- Implicit Outperforms Explicit: The results demonstrate that agents do not need to explicitly define or "draw" a subgoal to benefit from subtask structure. Simply recognizing movement into a new state-space cluster is sufficient to guide the search effectively.
- Robustness to Visual Noise: Because rerooting avoids reconstructing future states, it is highly robust to environmental noise. In BoulderDash environments filled with 50% irrelevant "dirt," explicit subgoal methods (like PHS*) timed out and made zero progress. In stark contrast, rerooting methods solved nearly 100% of the problems.
- Synergy of Signals: The hybrid rerooter ($\sqrt{\text{LTS-LH}}$) proved that global structure and local guidance are highly complementary. The authors provide a new theoretical proof (Theorem 3.2) demonstrating that $\sqrt{\text{LTS}}$ can effectively "fall back" on whichever signal is more informative in a given region.
- Computational Efficiency and Scalability: Across all tested domains, the hybrid rerooter achieved state-of-the-art online training efficiency. It solved problems using significantly fewer node expansions and less wall-clock time than non-rerooting baselines. By avoiding heavy subgoal generation models, rerooting methods were often 2x to 10x faster in wall-clock time compared to explicit subgoal methods.
Limitations and Future Directions
While highly effective, the approach has limitations. The clustering rerooter's success depends heavily on the state space featuring "bottleneck" structures. In highly connected environments like TSP, clusters become less distinct, weakening the global signal. Additionally, while the hybrid model mitigates this, the heuristic-only model can occasionally "overcommit" to a visually promising path that ultimately leads to a deadlock.
Future work will explore integrating alternative forms of "side information" to define rerooters. This could include leveraging human demonstrations or applying different types of topological analysis directly to the search tree, further enhancing the scalability and robustness of discrete planning agents.
Summary updated