This tutorial includes python code to solve classical planning problems with a total order planner. A total order plan is a solution to a planning problem that shows a linear ordering of actions to take in order to reach a goal state.
Planning and scheduling is a process to come up with a plan of actions to execute and in which order these actions should be executed. A planning problem is described with a Planning Domain Definition Language (PDDL). A classical planning problem has an initial state, a goal state and possible actions to take. 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.
I am using code from aima-python in this tutorial (download package), these modules include all the necessary classes and functions for the total order planner algorithm in python. The algorithm uses a solved planning graph and tries to find a valid total ordering solution for it.
Problems and solutions
This example code includes three planning problems and their total order plan solutions. I had to split up the robot delivery problem in two parts as it was to difficult for the algorithm to get a letter from the mail office and bring it back to my office: At(Robert, MyOffice) & At(Letter, MyOffice). It is also a problem to get the algorithm to drop the letter in my office in the second part (it finds a solution but not in the correct order).
# 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)]