Hierarchical Search

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:

(a) the high level action "Go to San Fransisco airport" (Go(Home, SFO)), might have two possible refinements, "Drive to San Fransisco airport" and "Taxi to San Fransisco airport".
(b) A recursive refinement for navigation in the vacuum world would be: to get to a destination, take a step, and then go to the destination.
implementation: An HLA refinement that contains only primitive actions is called an implementation of the HLA
An implementation of a high-level plan (a sequence of HLAs) is the concatenation of implementations of each HLA in the sequence
A high-level plan achieves the goal from a given state if at least one of its implementations achieves the goal from that state

The refinements function input is:

hla: the HLA of which we want to compute its refinements
state: the knoweledge base of the current problem (Problem.init)
library: the hierarchy of the actions in the planning problem



In [ ]:

    
from planning import * 
from notebook import psource



In [11]:

    
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

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.)

The algorithms input is: problem and hierarchy

problem: is of type Problem
hierarchy: is a dictionary consisting of all the actions and the order in which they are performed.

In top level call, initialPlan contains [act] (i.e. is the action to be performed)



In [16]:

    
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))

Example

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.

hierarchy



In [17]:

    
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:



In [18]:

    
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.

Then our problem is:



In [19]:

    
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)']



In [20]:

    
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

Top level call



In [22]:

    
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)]}]

Example 2



In [23]:

    
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)']] 
        }



In [25]:

    
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)]}]