Jag kommer att lösa planeringsproblem med en hierarkisk sökalgoritm i denna handledning. I hierarkisk sökning delar vi upp eventuella åtgärder i en hierarkisk struktur med nivåer. Ett stort planeringsproblem kan vara lättare och mindre komplicerat att lösa om vi kan delegera ansvar för delåtgärder till många nivåer i en hierarki.
En lösning på ett planeringsproblem är en sekvens av åtgärder som tar en agent från ett initialt tillstånd till ett måltillstånd. Ett planeringsproblem beskrivs med ett PDDL (Planning Domain Definition Language). Ett planeringsproblem har ett initialt tillstånd, ett måltillstånd och möjliga åtgärder att genomföra. Tillstånd och möjliga åtgärder läggs till som meningar i en kunskapsbas. Varje möjlig åtgärd har ett funktionsnamn, variabler, förutsättningar och effekter. Ett planeringsproblem kan lösas med framåtsökning (progression) eller bakåtsökning (regression). Framåtsökning startar från det ursprungliga tillståndet och bakåtsökning startar från målläget.
Hierarkisk sökning behöver en beskrivning av en hierarki av handlingar, från högnivååtgärder (HLA) till primitiva åtgärder. Åtgärder på hög nivå (HLA) förfinas till mer specifika åtgärder, denna process fortsätter tills vi har primitiva åtgärder som inte har några förfiningar. Primitiva åtgärder kommer att inkluderas som steg i den slutliga lösningen på problemet.
Jag använder kod från aima-python i den här handledningen (ladda ner paket), dessa moduler innehåller alla nödvändiga klasser och funktioner för en hierarkisk sökalgoritm i Python.
Problem och lösningar
Koden nedan illustrerar tre problem som definieras som hierarkiska sökproblem. Utmatningen från en körning visas under koden. Jag måste definiera en hierarki med möjliga åtgärder för att kunna lösa ett 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}]