I am going to solve planning problems with a hierarchical search algorithm in this tutorial. In hierarchical search, we divide possible actions into a hierarchical structure with levels. A large planning problem can be easier an less complex to solve if we can delegate responsibilty of subtasks to many levels in a hierarchy.
A solution to planning problem is a sequence of actions that takes an agent from an initial state to a goal state. A planning problem is described with a Planning Domain Definition Language (PDDL). A planning problem has an initial state, a goal state and possible actions to execute. States and possible actions are added as sentences to a knowledge base. Each possible action has a function name, variables, preconditions and effects. A planning problem can be solved with forward (progression) search or backward (regression) search. Forward search starts from the initial state and backward search starts from the goal state.
Hierarchical search needs a description of a hierarchy of actions, from high level actions (HLA) to primitive actions. High level actions (HLA) is refined into more specific actions, this process continues until we have primitive actions that does not have any refinements. Primitive actions will be included as steps in the final solution to the problem.
I am using code from aima-python in this tutorial (download package), these modules include all the necessary classes and functions for hierarchical search in python.
Problems and solutions
The code below illustrates three problems that is defined as hierarchical search problems. The output from a run is shown below the code. I need to define a hierarchy of possible actions for each problem in order to be able to solve each problem.
# Import libraries
import aima.utils
import aima.planning
# Get to SFO problem
def get_to_SFO1():
# 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)']] }
# Possible actions
go_SFO = aima.planning.HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
taxi_SFO = aima.planning.HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')
drive_SFOLongTermParking = aima.planning.HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )
shuttle_SFO = aima.planning.HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')
# Create a problem
problem = aima.planning.RealWorldPlanningProblem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO])
# Hierarchical Search
plan = problem.hierarchical_search(library)
print('--- Get to SFO1 problem ---')
print (plan, '\n')
print ([x.__dict__ for x in plan])
print()
# Get to SFO problem
def get_to_SFO2():
# 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)'],
['At(SFOLongTermParking) & ~At(Home)'],
['At(SFO) & ~At(SFOLongTermParking)'],
['At(SFO) & ~At(Home)']]}
# Possible actions
go_home_sfo1 = aima.planning.HLA('Go(Home, SFO)', precond='At(Home) & Have(Car)', effect='At(SFO) & ~At(Home)')
go_home_sfo2 = aima.planning.HLA('Go(Home, SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
drive_home_sfoltp = aima.planning.HLA('Drive(Home, SFOLongTermParking)', precond='At(Home) & Have(Car)', effect='At(SFOLongTermParking) & ~At(Home)')
shuttle_sfoltp_sfo = aima.planning.HLA('Shuttle(SFOLongTermParking, SFO)', precond='At(SFOLongTermParking)', effect='At(SFO) & ~At(SFOLongTermParking)')
taxi_home_sfo = aima.planning.HLA('Taxi(Home, SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')
actions = [go_home_sfo1, go_home_sfo2, drive_home_sfoltp, shuttle_sfoltp_sfo, taxi_home_sfo]
# Create a problem
problem = aima.planning.RealWorldPlanningProblem(initial='At(Home)', goals='At(SFO)', actions=actions)
# Hierarchical Search
plan = problem.hierarchical_search(library)
print('--- Get to SFO2 problem ---')
print(plan, '\n')
print([x.__dict__ for x in plan])
print()
# Robot delivery problem
def robot_delivery():
# Hierarchy of possible actions (Important that steps have different names, see Go and Walk)
library = {
'HLA': [
'Go(MyOffice, MailOffice)',
'Go(MailOffice, MyOffice)',
'Walk(MyOffice, Floor)',
'Walk(MailOffice, Floor)',
'Walk(Floor, MailOffice)',
'Walk(Floor, MyOffice)',
'Pickup(Letter, MailOffice)',
'Drop(Letter, MyOffice)'
],
'steps': [
['Walk(MyOffice, Floor)', 'Walk(Floor, MailOffice)', 'Pickup(Letter, MailOffice)'],
['Walk(MailOffice, Floor)', 'Walk(Floor, MyOffice)', 'Drop(Letter, MyOffice)'],
[],
[],
[],
[],
[],
[]
],
'precond': [
['At(MyOffice) & ~Has(Letter)'],
['At(MailOffice) & Has(Letter)'],
['At(MyOffice)'],
['At(MailOffice)'],
['At(Floor)'],
['At(Floor)'],
['At(MailOffice) & LetterAt(MailOffice)'],
['At(MyOffice) & Has(Letter)']
],
'effect': [
['At(MailOffice) & ~At(MyOffice) & ~LetterAt(MailOffice)'],
['At(MyOffice) & ~At(MailOffice) & LetterAt(MyOffice)'],
['At(Floor) & ~At(MyOffice)'],
['At(Floor) & ~At(MailOffice)'],
['At(MailOffice) & ~At(Floor)'],
['At(MyOffice) & ~At(Floor)'],
['Has(Letter) & ~LetterAt(MailOffice)'],
['~Has(Letter) & LetterAt(MyOffice)']
]
}
# Possible actions
myoffice_to_mailoffice = aima.planning.HLA('Go(MyOffice, MailOffice)', precond='At(MyOffice) & ~Has(Letter)', effect='At(MailOffice) & ~At(MyOffice) & ~LetterAt(MailOffice)')
mailoffice_to_myoffice = aima.planning.HLA('Go(MailOffice, MyOffice)', precond='At(MailOffice) & Has(Letter)', effect='At(MyOffice) & ~At(MailOffice) & LetterAt(MyOffice)')
myoffice_to_floor = aima.planning.HLA('Walk(MyOffice, Floor)', precond='At(MyOffice)', effect='At(Floor) & ~At(MyOffice)')
mailoffice_to_floor = aima.planning.HLA('Walk(MailOffice, Floor)', precond='At(MailOffice)', effect='At(Floor) & ~At(MailOffice)')
floor_to_mailoffice = aima.planning.HLA('Walk(Floor, MailOffice)', precond='At(Floor)', effect='At(MailOffice) & ~At(Floor)')
floor_to_myoffice = aima.planning.HLA('Walk(Floor, MyOffice)', precond='At(Floor)', effect='At(MyOffice) & ~At(Floor)')
pickup_letter = aima.planning.HLA('Pickup(Letter, MailOffice)', precond='At(MailOffice) & LetterAt(MailOffice)', effect='Has(Letter) & ~LetterAt(MailOffice)')
drop_letter = aima.planning.HLA('Drop(Letter, MyOffice)', precond='At(MyOffice) & Has(Letter)', effect='~Has(Letter) & LetterAt(MyOffice)')
actions = [myoffice_to_mailoffice, mailoffice_to_myoffice, myoffice_to_floor, mailoffice_to_floor, floor_to_mailoffice, floor_to_myoffice, pickup_letter, drop_letter]
# Hierarchical Search (Part 1)
problem = aima.planning.RealWorldPlanningProblem(initial='At(MyOffice) & LetterAt(MailOffice) & ~Has(Letter)', goals='At(MailOffice) & Has(Letter)', actions=actions)
plan = problem.hierarchical_search(library)
print('--- Robot delivery part 1 ---')
print(plan, '\n')
print([x.__dict__ for x in plan])
print()
# Hierarchical Search (Part 2)
problem = aima.planning.RealWorldPlanningProblem(initial='At(MailOffice) & Has(Letter)', goals='At(MyOffice) & LetterAt(MyOffice)', actions=actions)
plan = problem.hierarchical_search(library)
print('--- Robot delivery part 2 ---')
print(plan, '\n')
print([x.__dict__ for x in plan])
print()
# The main entry point for this module
def main():
# Get to SFO1 problem
get_to_SFO1()
# Get to SFO2 problem
get_to_SFO2()
# Robot delivery problem
robot_delivery()
# Tell python to run main method
if __name__ == "__main__": main()--- Get to SFO1 problem ---
[Drive(Home, SFOLongTermParking), Shuttle(SFOLongTermParking, SFO)]
[{'name': 'Drive', 'args': (Home, SFOLongTermParking), 'precond': [At(Home), Have(Car)], 'effect': [At(SFOLongTermParking), NotAt(Home)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Shuttle', 'args': (SFOLongTermParking, SFO), 'precond': [At(SFOLongTermParking)], 'effect': [At(SFO), NotAt(LongTermParking)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]
--- Get to SFO2 problem ---
[Taxi(Home, SFO)]
[{'name': 'Taxi', 'args': (Home, SFO), 'precond': [At(Home)], 'effect': [At(SFO), NotAt(Home)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]
--- Robot delivery part 1 ---
[Walk(MyOffice, Floor), Walk(Floor, MailOffice), Pickup(Letter, MailOffice)]
[{'name': 'Walk', 'args': (MyOffice, Floor), 'precond': [At(MyOffice)], 'effect': [At(Floor), NotAt(MyOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Walk', 'args': (Floor, MailOffice), 'precond': [At(Floor)], 'effect': [At(MailOffice), NotAt(Floor)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Pickup', 'args': (Letter, MailOffice), 'precond': [At(MailOffice), LetterAt(MailOffice)], 'effect': [Has(Letter), NotLetterAt(MailOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]
--- Robot delivery part 2 ---
[Walk(MailOffice, Floor), Walk(Floor, MyOffice), Drop(Letter, MyOffice)]
[{'name': 'Walk', 'args': (MailOffice, Floor), 'precond': [At(MailOffice)], 'effect': [At(Floor), NotAt(MailOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Walk', 'args': (Floor, MyOffice), 'precond': [At(Floor)], 'effect': [At(MyOffice), NotAt(Floor)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}, {'name': 'Drop', 'args': (Letter, MyOffice), 'precond': [At(MyOffice), Has(Letter)], 'effect': [NotHas(Letter), LetterAt(MyOffice)], 'domain': None, 'duration': 0, 'consumes': {}, 'uses': {}, 'completed': False}]