This tutorial includes code to solve planning problems with an angelic search algorithm. Angelic search is a better version of the hierarchical search algorithm as it can find a solution faster. Angelic search will only consider high level actions that can reach the goal, it prefers high level actions with more refinements over high level actions with less refinments.
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.
Angelic 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. Angelic search also need an optimistic description that possibly overstates the reachable set and an pessimistic description that possibly understates the reachable set. The ability to reject high level actions gives angelic search a computational advantage over hierarchical search.
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 includes 3 problems that are defined as angelic search problems. The output from a run is shown below the code. Each problem needs a hierarchy of possible actions, an optimistic description and a pessimistic description.
# 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])
# Create an initial plan
optimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & $-At(Home)' )
pessimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & ~At(Home)' )
initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
# Angelic Search
plan = problem.angelic_search(library, initial_plan)
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)
# Create an initial plan
optimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond='At(Home)', effect='$+At(SFO) & $-At(Home)' )
pessimistic = aima.planning.AngelicHLA('Go(Home, SFO)', precond='At(Home)', effect='$+At(SFO) & ~At(Home)' )
initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
# Angelic Search
plan = problem.angelic_search(library, initial_plan)
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]
# Angelic Search (Part 1)
problem = aima.planning.RealWorldPlanningProblem(initial='At(MyOffice) & LetterAt(MailOffice) & ~Has(Letter)', goals='At(MailOffice)', actions=actions)
optimistic = aima.planning.AngelicHLA('Go(MyOffice, MailOffice)', precond='At(MyOffice)', effect ='$+At(MailOffice) & $-At(MyOffice)')
pessimistic = aima.planning.AngelicHLA('Go(MyOffice, MailOffice)', precond='At(MyOffice)', effect ='$+At(MailOffice) & ~At(MyOffice)')
initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
plan = problem.angelic_search(library, initial_plan)
print('--- Robot delivery part 1 ---')
print(plan, '\n')
print([x.__dict__ for x in plan])
print()
# Angelic Search (Part 2)
problem = aima.planning.RealWorldPlanningProblem(initial='At(MailOffice) & Has(Letter)', goals='At(MyOffice)', actions=actions)
optimistic = aima.planning.AngelicHLA('Go(MailOffice, MyOffice)', precond='At(MailOffice)', effect='$+At(MyOffice) & $-At(MailOffice)')
pessimistic = aima.planning.AngelicHLA('Go(MailOffice, MyOffice)', precond='At(MailOffice)', effect='$+At(MyOffice) & ~At(MailOffice)')
initial_plan = [aima.planning.AngelicNode(problem.initial, None, [optimistic], [pessimistic])]
plan = problem.angelic_search(library, initial_plan)
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}]