Partial Order Planner in Python

This tutorial shows the usage of a partial order planner in Python to solve classical planning problems. A partial order planner tries to find a solution to a planning problem by splitting up the problem in subproblems and then combining subplans into a complete plan. A partial order planner assumes that subproblems is independent of each other.

A solution to a planning problem is a list of actions to perform in order to reach a goal state. A planning problem is described with a Planning Domain Definition Language (PDDL). A planning problem has an initial state, a goal state and possible actions to execute. 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 a partial order plan in python.

Problems and solutions

The code below includes two problems that I am trying to solve with a partial order planner, the output from a run is shown below the code. The partial order planner does not find a solution every time and it can find wrong solutions. A partial order planner can only be used on problems that have independent subproblems.

# Import libraries
import aima.utils
import aima.planning

# Spare tire problem
def spare_tire_problem():

    problem = aima.planning.PlanningProblem(initial='At(Flat, Axle) & At(Spare, Trunk)',
                        goals='At(Spare, Axle) & At(Flat, Ground)',
                        actions=[aima.planning.Action('Remove(obj, loc)',
                                        precond='At(obj, loc)',
                                        effect='At(obj, Ground) & ~At(obj, loc)',
                                        domain='Tire(obj)'),
                                aima.planning.Action('PutOn(t, Axle)',
                                        precond='At(t, Ground) & ~At(Flat, Axle)',
                                        effect='At(t, Axle) & ~At(t, Ground)',
                                        domain='Tire(t)'),
                                aima.planning.Action('LeaveOvernight',
                                        precond='',
                                        effect='~At(Spare, Ground) & ~At(Spare, Axle) & ~At(Spare, Trunk) & \
                                    ~At(Flat, Ground) & ~At(Flat, Axle) & ~At(Flat, Trunk)')],
                        domain='Tire(Flat) & Tire(Spare)')

    # Partial order plan
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

# Robot delivery problem
def robot_delivery_problem(initial_state, goals):

    # Create a knowledge base
    kb = "Connected(MyOffice, Floor) & Connected(Floor, MailOffice) & Connected(Floor, Fikarum) & Connected(Fikarum, MailOffice) & Connected(Floor, MyOffice) & Connected(MailOffice, Floor) & Connected(Fikarum, Floor) & Connected(MailOffice, Fikarum)"

    # Add initial state to the knowledge base
    kb += " & " + initial_state

    # Create actions 
    actions = [aima.planning.Action("Pickup(b, p, r)", 
                                    precond="At(b, r) & At(p, r)", 
                                    effect="Has(b, p) & ~At(p, r)",
                                    domain="Robot(b) & Packet(p) & Room(r)"),
               aima.planning.Action("Drop(b, p, r)",
                                    precond="At(b, r) & Has(b, p)",
                                    effect="At(p, r) & ~Has(b, p)",
                                    domain="Robot(b) & Packet(p) & Room(r)"),
               aima.planning.Action("Move(b, f, t)",
                                    precond="At(b, f) & Connected(f, t)",
                                    effect="At(b, t) & ~At(b, f)",
                                    domain="Robot(b) & Room(f) & 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():

    # Spare tire problem
    spare_tire_problem()

    # Robot delivery: first part
    initial_state = "At(Robert, MyOffice) & At(Letter, MailOffice)"
    goals = "At(Robert, MailOffice) & Has(Robert, Letter)"
    problem = robot_delivery_problem(initial_state, goals)
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

    # Robot delivery: second part
    initial_state = "At(Robert, MailOffice) & Has(Robert, Letter)"
    goals = "At(Robert, MyOffice)"
    problem = robot_delivery_problem(initial_state, goals)
    plan = aima.planning.PartialOrderPlanner(problem)
    plan.execute()
    print()

# Tell python to run main method
if __name__ == "__main__": main()

Probably Wrong
Causal Links
(PutOn(Spare, Axle), At(Spare, Axle), Finish)
(Start, Tire(Spare), PutOn(Spare, Axle))
(Remove(Flat, Axle), NotAt(Flat, Axle), PutOn(Spare, Axle))
(Start, Tire(Flat), Remove(Flat, Axle))
(Start, At(Flat, Axle), Remove(Flat, Axle))
(Remove(Spare, Flat), At(Spare, Ground), PutOn(Spare, Axle))
(Start, Tire(Spare), Remove(Spare, Flat))
(Remove(Flat, Axle), At(Flat, Ground), Finish)

Constraints
Start < PutOn(Spare, Axle)
Remove(Flat, Axle) < PutOn(Spare, Axle)
Start < Remove(Flat, Axle)
Remove(Spare, Flat) < PutOn(Spare, Axle)
PutOn(Spare, Axle) < Finish
Start < Finish
Remove(Flat, Axle) < Finish
Start < Remove(Spare, Flat)

Partial Order Plan
[{Start}, {Remove(Spare, Flat), Remove(Flat, Axle)}, {PutOn(Spare, Axle)}, {Finish}]

Probably Wrong
Causal Links
(Move(Robert, MyOffice, MailOffice), At(Robert, MailOffice), Finish)
(Start, Robot(Robert), Move(Robert, MyOffice, MailOffice))
(Start, Room(MyOffice), Move(Robert, MyOffice, MailOffice))
(Start, Room(MailOffice), Move(Robert, MyOffice, MailOffice))
(Pickup(Robert, Letter, MailOffice), Has(Robert, Letter), Finish)
(Start, Packet(Letter), Pickup(Robert, Letter, MailOffice))
(Start, Room(MailOffice), Pickup(Robert, Letter, MailOffice))
(Start, Robot(Robert), Pickup(Robert, Letter, MailOffice))
(Start, At(Letter, MailOffice), Pickup(Robert, Letter, MailOffice))
(Start, At(Robert, MyOffice), Move(Robert, MyOffice, MailOffice))
(Move(Robert, MyOffice, MailOffice), At(Robert, MailOffice), Pickup(Robert, Letter, MailOffice))

Constraints
Start < Pickup(Robert, Letter, MailOffice)
Start < Finish
Move(Robert, MyOffice, MailOffice) < Pickup(Robert, Letter, MailOffice)
Start < Move(Robert, MyOffice, MailOffice)
Pickup(Robert, Letter, MailOffice) < Finish
Move(Robert, MyOffice, MailOffice) < Finish

Partial Order Plan
[{Start}, {Move(Robert, MyOffice, MailOffice)}, {Pickup(Robert, Letter, MailOffice)}, {Finish}]

Probably Wrong
Causal Links
(Move(Robert, MailOffice, MyOffice), At(Robert, MyOffice), Finish)
(Start, Room(MyOffice), Move(Robert, MailOffice, MyOffice))
(Start, Room(MailOffice), Move(Robert, MailOffice, MyOffice))
(Start, Robot(Robert), Move(Robert, MailOffice, MyOffice))
(Start, At(Robert, MailOffice), Move(Robert, MailOffice, MyOffice))

Constraints
Start < Finish
Move(Robert, MailOffice, MyOffice) < Finish
Start < Move(Robert, MailOffice, MyOffice)

Partial Order Plan
[{Start}, {Move(Robert, MailOffice, MyOffice)}, {Finish}]