Hierarchical search is a a planning algorithm in high level of abstraction.
Instead of actions as in classical planning (chapter 10) (primitive actions) we now use high level actions (HLAs) (see planning.ipynb)
Each HLA has one or more refinements into a sequence of actions, each of which may be an HLA or a primitive action (which has no refinements by definition).
For example:
The refinements function input is:
from planning import *
from notebook import psource
psource(Problem.refinements)
def refinements(hla, state, library): # refinements may be (multiple) HLA themselves ...
"""
state is a Problem, containing the current state kb
library is a dictionary containing details for every possible refinement. eg:
{
'HLA': [
'Go(Home, SFO)',
'Go(Home, SFO)',
'Drive(Home, SFOLongTermParking)',
'Shuttle(SFOLongTermParking, SFO)',
'Taxi(Home, SFO)'
],
'steps': [
['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'],
['Taxi(Home, SFO)'],
[],
[],
[]
],
# empty refinements indicate a primitive action
'precond': [
['At(Home) & Have(Car)'],
['At(Home)'],
['At(Home) & Have(Car)'],
['At(SFOLongTermParking)'],
['At(Home)']
],
'effect': [
['At(SFO) & ~At(Home)'],
['At(SFO) & ~At(Home)'],
['At(SFOLongTermParking) & ~At(Home)'],
['At(SFO) & ~At(SFOLongTermParking)'],
['At(SFO) & ~At(Home)']
]
}
"""
e = Expr(hla.name, hla.args)
indices = [i for i, x in enumerate(library['HLA']) if expr(x).op == hla.name]
for i in indices:
actions = []
for j in range(len(library['steps'][i])):
# find the index of the step [j] of the HLA
index_step = [k for k,x in enumerate(library['HLA']) if x == library['steps'][i][j]][0]
precond = library['precond'][index_step][0] # preconditions of step [j]
effect = library['effect'][index_step][0] # effect of step [j]
actions.append(HLA(library['steps'][i][j], precond, effect))
yield actions
Hierarchical search is a breadth-first implementation of hierarchical forward planning search in the space of refinements. (i.e. repeatedly choose an HLA in the current plan and replace it with one of its refinements, until the plan achieves the goal.)
In top level call, initialPlan contains [act] (i.e. is the action to be performed)
psource(Problem.hierarchical_search)
def hierarchical_search(problem, hierarchy):
"""
[Figure 11.5] 'Hierarchical Search, a Breadth First Search implementation of Hierarchical
Forward Planning Search'
The problem is a real-world problem defined by the problem class, and the hierarchy is
a dictionary of HLA - refinements (see refinements generator for details)
"""
act = Node(problem.init, None, [problem.actions[0]])
frontier = deque()
frontier.append(act)
while True:
if not frontier:
return None
plan = frontier.popleft()
(hla, index) = Problem.find_hla(plan, hierarchy) # finds the first non primitive hla in plan actions
prefix = plan.action[:index]
outcome = Problem(Problem.result(problem.init, prefix), problem.goals , problem.actions )
suffix = plan.action[index+1:]
if not hla: # hla is None and plan is primitive
if outcome.goal_test():
return plan.action
else:
for sequence in Problem.refinements(hla, outcome, hierarchy): # find refinements
frontier.append(Node(outcome.init, plan, prefix + sequence+ suffix))
Suppose that somebody wants to get to the airport.
The possible ways to do so is either get a taxi, or drive to the airport.
Those two actions have some preconditions and some effects.
If you get the taxi, you need to have cash, whereas if you drive you need to have a car.
Thus we define the following hierarchy of possible actions.
library = {
'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],
'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],
'precond': [['At(Home) & Have(Car)'], ['At(Home)'], ['At(Home) & Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],
'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(SFOLongTermParking) & ~At(Home)'], ['At(SFO) & ~At(LongTermParking)'], ['At(SFO) & ~At(Home) & ~Have(Cash)']] }
the possible actions are the following:
go_SFO = HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
taxi_SFO = HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')
drive_SFOLongTermParking = HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )
shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')
Suppose that (our preconditionds are that) we are Home and we have cash and car and our goal is to get to SFO and maintain our cash, and our possible actions are the above.
prob = Problem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO])
The refinements of the action Go(Home, SFO), are defined as:
['Drive(Home,SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)']
for sequence in Problem.refinements(go_SFO, prob, library):
print (sequence)
print([x.__dict__ for x in sequence ], '\n')
[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] [{'completed': False, 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'uses': {}, 'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'consumes': {}, 'precond': [At(Home), Have(Car)]}, {'completed': False, 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'consumes': {}, 'precond': [At(SFOLongTermParking)]}] [HLA(Taxi(Home, SFO))] [{'completed': False, 'args': (Home, SFO), 'name': 'Taxi', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(Home), NotHave(Cash)], 'consumes': {}, 'precond': [At(Home)]}]
Run the hierarchical search
plan= Problem.hierarchical_search(prob, library)
print (plan, '\n')
print ([x.__dict__ for x in plan])
[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] [{'completed': False, 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'uses': {}, 'duration': 0, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'consumes': {}, 'precond': [At(Home), Have(Car)]}, {'completed': False, 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(LongTermParking)], 'consumes': {}, 'precond': [At(SFOLongTermParking)]}]
library_2 = {
'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)' , 'Metro(MetroStop, SFO)', 'Metro1(MetroStop, SFO)', 'Metro2(MetroStop, SFO)' ,'Taxi(Home, SFO)'],
'steps': [['Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)'], ['Taxi(Home, SFO)'], [], ['Metro1(MetroStop, SFO)'], ['Metro2(MetroStop, SFO)'],[],[],[]],
'precond': [['At(Home)'], ['At(Home)'], ['At(Home)'], ['At(MetroStop)'], ['At(MetroStop)'],['At(MetroStop)'], ['At(MetroStop)'] ,['At(Home) & Have(Cash)']],
'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(MetroStop) & ~At(Home)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'] , ['At(SFO) & ~At(MetroStop)'] ,['At(SFO) & ~At(Home) & ~Have(Cash)']]
}
plan_2 = Problem.hierarchical_search(prob, library_2)
print(plan_2, '\n')
print([x.__dict__ for x in plan_2])
[HLA(Bus(Home, MetroStop)), HLA(Metro1(MetroStop, SFO))] [{'completed': False, 'args': (Home, MetroStop), 'name': 'Bus', 'uses': {}, 'duration': 0, 'effect': [At(MetroStop), NotAt(Home)], 'consumes': {}, 'precond': [At(Home)]}, {'completed': False, 'args': (MetroStop, SFO), 'name': 'Metro1', 'uses': {}, 'duration': 0, 'effect': [At(SFO), NotAt(MetroStop)], 'consumes': {}, 'precond': [At(MetroStop)]}]