Denna handledning innehåller kod för att lösa planeringsproblem med en ängslig algoritm. Ängslig sökning är en bättre version av den hierarkiska sökalgoritmen eftersom den kan hitta en lösning snabbare. Ängslig sökning kommer bara att överväga åtgärder på hög nivå som kan nå målet, algoritmen föredrar åtgärder som har fler förfiningar jämfört med åtgärder med färre förfiningar.
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åltillståndet.
Ängslig 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. Ängslig sökning behöver en optimistisk beskrivning som möjligen överskattar den nåbara uppsättningen och en pessimistisk beskrivning som eventuellt underskattar den nåbara uppsättningen. Förmågan att avvisa åtgärder på hög nivå ger ängslig sökning en beräkningsfördel jämfört med hierarkisk sökning.
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 ängslig sökning i Python.
Problem och lösningar
Koden nedan inkluderar 3 problem som definieras som sökproblem. Utmatningen från en körning visas under koden. Varje problem behöver en hierarki av möjliga åtgärder, en optimistisk beskrivning och en pessimistisk beskrivning.
# 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}]