TLDR: A new research paper introduces Bilevel MCTS and Tree Collapsing, two innovations that drastically improve the efficiency of Monte-Carlo Tree Search (MCTS) in classical planning. By optimizing node selection to an amortized O(1) runtime and reducing tree depth, these methods, combined into a system called Nεbula, outperform current state-of-the-art AI planners in solving complex problems.
Classical planning, a core area of artificial intelligence, involves finding a sequence of actions to achieve a goal. While Monte-Carlo Tree Search (MCTS) has been highly successful in areas like reinforcement learning and game AI, its application in classical planning has faced significant challenges. One major hurdle is the time MCTS spends on selecting the next node to expand, especially in planning problems where the search depth can be arbitrarily large, unlike games with inherent depth limits.
Traditional priority-queue-based search methods can select nodes in constant time (O(1)), but MCTS, which uses a tree-based structure, typically requires time proportional to the search depth (O(log N) or O(D), where N is the number of leaf nodes and D is the depth). This becomes a significant bottleneck as planning problems grow in complexity and depth.
To address this, researchers have proposed a novel approach called Bilevel MCTS. This modification introduces a best-first search from each selected leaf node, with an expansion budget that adjusts based on the node’s depth. This clever strategy allows Bilevel MCTS to achieve an amortized O(1) runtime for node selection, effectively matching the efficiency of traditional queue-based methods. This is a crucial improvement, as empirical observations showed that standard MCTS could be orders of magnitude slower in node evaluations compared to Greedy Best-First Search (GBFS) in deep searches.
Further enhancing this, the paper introduces ‘Tree Collapsing’. This technique reduces the effective depth of the search tree by allowing grandparent nodes to ‘adopt’ their grandchildren if the number of children falls below a certain threshold. This bypasses unnecessary action selection steps, further improving performance. A dynamic version, Dynamic Tree Collapsing (DTC), eliminates the need for manual parameter tuning by setting the collapsing threshold based on the node’s depth.
The combination of Bilevel MCTS and Tree Collapsing, along with other established techniques like the UCB1-Normal2 Multi-Armed Bandit algorithm (suited for unbounded heuristic rewards), a novelty metric, and an alternation queue with boosted preferred operators, culminates in a new planning system named Nεbula. This comprehensive configuration was rigorously tested against state-of-the-art planners like LAMA, SM-Type-LAMA, NOLAN, DecStar, and ApxNovelty on benchmark instances from IPC2018 and IPC2023.
Nεbula demonstrated superior performance, solving more instances within the given time limits and achieving competitive IPC scores. The study highlights a synergistic effect between Bilevel MCTS and Tree Collapsing, where the latter significantly reduces the size of the backpropagation queue, leading to further runtime improvements. While computationally demanding, Nεbula’s true potential shines in longer, extended runs, where it significantly surpasses existing methods in coverage.
Also Read:
- Enhancing Transformer Performance in Automated Planning Through Symmetry Awareness
- Streamlining Knowledge Graph Completion with Probabilistic Circuits
This research marks a significant step forward in making MCTS a more practical and efficient tool for classical planning, addressing its long-standing bottleneck in node selection and paving the way for more powerful AI planning systems. For more details, you can refer to the full research paper here.
