AI Research Portal

This paper introduces a formalism for probabilistic Hierarchical Goal Network (HGN) planning with action-insertion semantics, enabling the integration of domain knowledge from goal decomposition methods into probabilistic planners. The authors propose and evaluate two UCT-based algorithms: UCTbase, an asymptotically optimal approach that transforms the HGN problem into a stochastic shortest path (SSP) problem, and UCTcomp, a compressed variant that reduces search tree size by sharing learned value estimates across related goal networks. Experimental results on modified FOND HTN benchmark domains demonstrate that UCTcomp converges more quickly, requires less memory, and consistently finds lower-cost solutions on larger problems, outperforming UCTbase which struggles with scalability on such instances.

The paper addresses several bottlenecks in hierarchical planning for stochastic environments:

Lack of Probabilistic HGN Planning: Prior work on HGNs has primarily focused on deterministic settings, with scant research on how HGNs can be applied in stochastic environments.

Formalization of probabilistic HGN planning with action-insertion semantics.
Introduction of UCTbase, a baseline UCT-based algorithm that transforms a probabilistic HGN problem into an equivalent stochastic shortest path (SSP) problem, yielding asymptotically optimal behavior.
Introduction of UCTcomp, a compressed UCT variant that reduces the size of the search tree by sharing learned value estimates across related goal networks.
Empirical evaluation demonstrating that UCTcomp converges more quickly, requires less memory, and consistently finds lower-cost solutions on larger problems compared to UCTbase.

The paper formalizes probabilistic HGN planning with action-insertion semantics, allowing actions to be executed independently of the hierarchy. This enables recovery from unexpected states and handling of incomplete hierarchical models. The planning objective is to complete an initial goal network, which serves as a temporally extended goal. Solutions are represented as action-method policies that select actions or methods based on the current node (state, goal network).

Two UCT-based algorithms are proposed:

UCTbase: This approach transforms a probabilistic HGN planning problem P = (D, s₀, gn₀) into an equivalent stochastic shortest path (SSP) problem P = (Š, Ã, Pr, š₀, S_g). The state space Š comprises all nodes (s, gn), where s is the world state and gn is the goal network. SSP actions directly encode the three types of node progression: Deterministic Goal Release (P_rel), Deterministic Goal Decomposition (P_dec), and Probabilistic Action Application (P_app). UCT is then applied directly to solve this SSP, which is provably asymptotically optimal.
UCTcomp: To address the scalability limitations of UCTbase, UCTcomp introduces a "compressed" approach. Instead of treating each (s, gn) pair as a distinct state, it creates only one tree node per underlying world state s. It maintains a separate Q-function for each unconstrained subgoal encountered in that world state, allowing learned information to be shared across nodes with different goal networks. The algorithm extends action selection to include both primitive actions and methods. At a node n = (s, gn), it considers all applicable actions and methods relevant to some unconstrained subgoal i ∈ UC(gn). It chooses the action or method that maximizes the sum of Q-values for multiple subgoals. During rollouts, UCB1 values are used for selection.

Both algorithms adapt UCT for goal-directed planning using the GUBS (Goals with Utility-Based Semantics) criterion, which jointly maximizes the probability of goal achievement and minimizes expected cost using the utility function: U(σ) = util(|σ|) + K_g1[σ_−1 is a goal node]

Planning Objective: Maximize the GUBS utility function: U(σ) = util(|σ|) + K_g1[σ_−1 is a goal node], where util is a strictly decreasing utility over cost, and K_g is a goal utility constant.
Utility Function Parameters: K_g is set to 1. The utility function is defined as util(cost) = exp(-cost).
UCT Exploration Constant: The UCT exploration constant C is set to sqrt(2).
Rollout Procedure: A fixed number of rollouts are performed at each decision step.
Rollout Depth: A maximum rollout depth of 20 was enforced.
Q-function (UCTcomp): For actions a, Q(s, a) is the estimated reward of executing a in state s. For decompositions, Q(s, (i, m)) denotes the estimated reward of using method m to decompose subgoal i in state s.
UCB1 Value Calculation (UCTcomp): UCB1(Q, N, s, u) = Q(s, u) + C sqrt(log(N(s)) / N_a(i)(s, u)).
Action Selection (UCTcomp): Chooses the action or method u that maximizes the sum of Q-values (or UCB1 values during rollouts) across all unconstrained subgoals i ∈ UC(gn).
Q-value Initialization: All Q-values were initialized to 0.
Tie-breaking: Random selection is used to break ties.
Computational Resources: All trials were run independently on compute nodes with 32 GB memory.

Datasets: Four benchmark domains adapted from FOND HTN literature: Transport Domain, Satellite Domain, Depot Domain, and Childsnack Domain. Each domain consists of 15 problems.
Metrics: Average cost of solutions, average number of nodes in the search tree.
Baselines: UCTbase (asymptotically optimal approach).
Experimental Setup: 20 independent trials per algorithm per problem. 100 action executions per trial budget. 1000 rollouts at each decision step.
Performance on Smaller Problems: UCTbase consistently outperformed UCTcomp in terms of solution quality on smaller problems (e.g., Satellite problems 1–3 and Transport problems 1–5), converging within the allotted budget of 1000 rollouts per decision step.
Performance on Larger Problems: UCTcomp consistently outperformed UCTbase in terms of average solution cost on larger, more complex problems (e.g., Depot problems 4-6 and Satellite problems 11-14). UCTbase often failed to return solutions due to exceeding memory constraints on these larger problems, while UCTcomp was able to solve them.
Memory and Scalability: UCTcomp demonstrated greater memory efficiency and broader scalability, particularly on larger problems. UCTbase consistently produced larger search trees, with node counts significantly exceeding those of UCTcomp.

Suboptimality of UCTcomp: UCTcomp may fail to capture interdependencies among subgoals within a goal network because it maintains separate Q-functions for each individual subgoal, implicitly assuming they can be optimized independently. This can lead to suboptimal solutions, and UCTcomp cannot guarantee convergence to an optimal policy even with unlimited compute.
Myopic Action Selection (UCTcomp): The current greedy action selection strategy in UCTcomp focuses only on immediate unconstrained subgoals, which can lead to locally optimal behaviors that interfere with future subgoals, especially with misleading or unsafe methods.

Method evidence: "We design and evaluate two UCT-based algorithms for solving probabilistic HGN planning problems: an asymptotically optimal approach and a compressed, shared-value approach that optimizes separately for each goal within the goal-subgoal hierarchy." (section: Abstract)
Result evidence: "Our results demonstrate that on larger problems, the compressed search converges more quickly and outperforms the asymptotically optimal search." (section: Abstract)
Limitation evidence: "By maintaining separate Q-functions for each subgoal, UCTcomp may fail to capture interdependencies among subgoals within a goal network. The selection process—which selects actions and methods based on Q-functions for each individual subgoal—implicitly assumes that subgoals can be optimized independently, treating them as separable objectives. However, this assumption breaks down in problems where the optimal strategy for achieving one subgoal depends on the configuration of other subgoals in the goal network. In such cases, the compressed representation may lead the algorithm toward suboptimal solutions, as it cannot reason about future, constrained subgoals in the full goal network. This efficiency-optimality trade-off implies that UCTcomp, unlike UCTbase, cannot guarantee convergence to an optimal policy even with unlimited compute." (section: 4.2 Compressed UCT (UCTcomp))

Probabilistic Hierarchical Goal Network Planning with UCT

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures