Total Order Planner in Python

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)]

Leave a Reply

Your email address will not be published. Required fields are marked *