Denna handledning innehåller kod i Python för att lösa klassiska planeringsproblem med en total orderplanerare. En total orderplan är en lösning på ett planeringsproblem som visar en linjär ordning av åtgärder som ska vidtas för att nå ett måltillstånd.
Planering och schemaläggning är en process för att ta fram en plan för åtgärder som ska genomföras och i vilken ordning dessa åtgärder ska genomföras. Ett planeringsproblem beskrivs med ett PDDL (Planning Domain Definition Language). Ett klassiskt planeringsproblem har ett initialt tillstånd, ett måltillstånd och möjliga åtgärder att vidta. Stater och möjliga åtgärder läggs till som meningar till en kunskapsbas. Varje möjlig åtgärd har ett funktionsnamn, variabler, förutsättningar och effekter. Ett planeringsproblem kan lösas med framåt- (progression) sökning eller bakåt (regression) sökning. Framåt sökning startar från det ursprungliga tillståndet och bakåt sökning startar från målet tillstånd.
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 total orderplan i Python.
Problem och lösningar
Denna exempelkod innehåller tre planeringsproblem och deras lösningar. Jag var tvungen att dela upp robotleveransproblemet i två delar, detta eftersom det var för svårt för algoritmen att få ett brev från postkontoret och föra tillbaka det till mitt kontor: At (Robert, MyOffice) & At (Letter, MyOffice). Det är också ett problem att få algoritmen att släppa brevet på mitt kontor i den andra delen (den hittar en lösning men inte i rätt ordning).
# Import libraries
import aima.utils
import aima.planning
# Air cargo problem
def air_cargo_problem():
# Create a problem
problem = aima.planning.PlanningProblem(initial='At(C1, SFO) & At(C2, JFK) & At(P1, SFO) & At(P2, JFK)',
goals='At(C1, JFK) & At(C2, SFO)',
actions=[aima.planning.Action('Load(c, p, a)',
precond='At(c, a) & At(p, a)',
effect='In(c, p) & ~At(c, a)',
domain='Cargo(c) & Plane(p) & Airport(a)'),
aima.planning.Action('Unload(c, p, a)',
precond='In(c, p) & At(p, a)',
effect='At(c, a) & ~In(c, p)',
domain='Cargo(c) & Plane(p) & Airport(a)'),
aima.planning.Action('Fly(p, f, to)',
precond='At(p, f)',
effect='At(p, to) & ~At(p, f)',
domain='Plane(p) & Airport(f) & Airport(to)')],
domain='Cargo(C1) & Cargo(C2) & Plane(P1) & Plane(P2) & Airport(SFO) & Airport(JFK)')
# Total order plan
solution = aima.planning.Linearize(problem).execute()
print("Air Cargo: {0}".format(solution))
print()
# Driving in romania
def romania():
# Create a knowledge base
knowledge_base = [
aima.utils.expr("Connected(Bucharest,Pitesti)"),
aima.utils.expr("Connected(Pitesti,Rimnicu)"),
aima.utils.expr("Connected(Rimnicu,Sibiu)"),
aima.utils.expr("Connected(Sibiu,Fagaras)"),
aima.utils.expr("Connected(Fagaras,Bucharest)"),
aima.utils.expr("Connected(Pitesti,Craiova)"),
aima.utils.expr("Connected(Craiova,Rimnicu)")
]
# Add rules to knowledge base
knowledge_base.extend([
aima.utils.expr("Connected(x,y) ==> Connected(y,x)"),
aima.utils.expr("At(Sibiu)")
])
# Create a drive action
drive = aima.planning.Action('Drive(x, y)', precond='At(x) & Connected(x,y)', effect='At(y) & ~At(x)')
# Create a goal
goals = 'At(Bucharest)'
# Total order plan
problem = aima.planning.PlanningProblem(knowledge_base, goals, [drive])
solution = aima.planning.Linearize(problem).execute()
print("Romania: {0}".format(solution))
print()
# Robot delivery problem
def robot_delivery_problem(initial_state, goals):
# Create a knowledge base
kb = [aima.utils.expr("Connected(MyOffice, Floor)"),
aima.utils.expr("Connected(Floor, MailOffice)"),
aima.utils.expr("Connected(Floor, Fikarum)"),
aima.utils.expr("Connected(Fikarum, MailOffice)"),
aima.utils.expr("Connected(Floor, MyOffice)"),
aima.utils.expr("Connected(MailOffice, Floor)"),
aima.utils.expr("Connected(Fikarum, Floor)"),
aima.utils.expr("Connected(MailOffice, Fikarum)")
]
# Add initial state to the knowledge base
kb.extend(initial_state)
# Create actions
actions = [aima.planning.Action("Pickup(b, p, r)",
precond="At(b, r) & At(p, r) & ~Has(b, p)",
effect="Has(b, p) & ~At(p, r)",
domain=[aima.utils.expr("Robot(b)"), aima.utils.expr("Packet(p)"), aima.utils.expr("Room(r)")]),
aima.planning.Action("Drop(b, p, r)",
precond="At(b, r) & Has(b, p)",
effect="At(p, r) & ~Has(b, p)",
domain=[aima.utils.expr("Robot(b)"), aima.utils.expr("Packet(p)"), aima.utils.expr("Room(r)")]),
aima.planning.Action("Move(b, f, t)",
precond="At(b, f) & Connected(f, t)",
effect="At(b, t) & ~At(b, f)",
domain=[aima.utils.expr("Robot(b)"), aima.utils.expr("Room(f)"), aima.utils.expr("Room(t)")])
]
# Create domains
domains = "Robot(Robert) & Packet(Letter) & Room(MyOffice) & Room(Floor) & Room(MailOffice) & Room(Fikarum)"
# Create a planning problem
problem = aima.planning.PlanningProblem(kb, goals, actions, domains)
# Return the problem
return problem
# The main entry point for this module
def main():
# Air cargo problem
air_cargo_problem()
# Romania problem
romania()
# Robot delivery: first part
initial_state = [
aima.utils.expr("At(Robert, MyOffice)"),
aima.utils.expr("At(Letter, MailOffice)"),
aima.utils.expr("~Has(Robert, Letter)")
]
goals = [aima.utils.expr("At(Robert, MailOffice)"), aima.utils.expr("Has(Robert, Letter)")]
problem = robot_delivery_problem(initial_state, goals)
solution = aima.planning.Linearize(problem).execute()
print("Robot delivery, part 1: {0}".format(solution))
print()
# Robot delivery: second part
initial_state = [
aima.utils.expr("At(Robert, MailOffice)"),
aima.utils.expr("Has(Robert, Letter)")
]
goals = [aima.utils.expr("At(Robert, MyOffice)")]
problem = robot_delivery_problem(initial_state, goals)
solution = aima.planning.Linearize(problem).execute()
print("Robot delivery, part 2: {0}".format(solution))
print()
# Tell python to run main method
if __name__ == "__main__": main()Air Cargo: [Load(C1, P1, SFO), Load(C2, P2, JFK), Fly(P2, JFK, SFO), Fly(P1, SFO, JFK), Unload(C2, P2, SFO), Unload(C1, P1, JFK)]
Romania: [Drive(Sibiu, Fagaras), Drive(Fagaras, Bucharest)]
Robot delivery, part 1: [Move(Robert, MyOffice, Floor), Move(Robert, Floor, MailOffice), Pickup(Robert, Letter, MailOffice)]
Robot delivery, part 2: [Move(Robert, MailOffice, Floor), Move(Robert, Floor, MyOffice)]