function ANGELIC-SEARCH(problem, hierarchy, initialPlan) returns solution or fail
frontier ← a FIFO queue with initialPlan as the only element
loop do
if EMPTY?(frontier) then return fail
plan ← POP(frontier) /* chooses the shallowest node in frontier */
if REACH+(problem.INITIAL-STATE, plan) intersects problem.GOAL then
if plan is primitive then return plan /* REACH+ is exact for primitive plans */
guaranteed ← REACH−(problem.INITIAL-STATE, plan) ∩ problem.GOAL
if guaranteed ≠ {} and MAKING-PROGRESS(plan, initialPlan) then
finalState ← any element of guaranteed
return DECOMPOSE(hierarchy, problem.INITIAL-STATE, plan, finalState)
hla ← some HLA in plan
prefix,suffix ← the action subsequences before and after hla in plan
for each sequence in REFINEMENTS(hla, outcome, hierarchy) do
frontier ← INSERT(APPEND(prefix, sequence, suffix), frontier)
function DECOMPOSE(hierarchy, s0, plan, sf) returns a solution
solution ← an empty plan
while plan is not empty do
action ← REMOVE-LAST(plan)
si ← a state in REACH−(s0, plan) such that sf ∈ REACH−(si, action)
problem ← a problem with INITIAL-STATE = si and GOAL = sf
solution ← APPEND(ANGELIC-SEARCH(problem, hierarchy, action), solution)
sf ← si
return solution
Figure ?? A hierarchical planning algorithm that uses angelic semantics to identify and commit to high-level plans that work while avoiding high-level plans that don't. The predicate MAKING-PROGRESS checks to make sure that we aren't stuck in an infinite regression of refinements. At top level, call ANGELIC-SEARCH with [Act] as the initialPlan.