GraphPlan algorithm in Python

I am going to use a GraphPlan algorithm to solve classical planning problems in this tutorial. A solution to a planning problem is a sequence of actions that results in a goal state (a plan). Automated planning is important in the field of artificial intelligence.

An intelligent agent must be able to create plans to reach a goal from an initial state. A planning problem is described with a Planning Domain Definition Language (PDDL), a problem has an initial state, a goal state and possible actions. 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.

A GraphPlan algorithm repeteadly adds a level to a planning graph, a solution can be found if all of the goals in a level not is mutual exclusive. The algorithm terminates if it finds a solution that reaches the goal state or if no more levels can be added to the planning graph. A planning graph is a directed graph that is organized into levels. Two goals is mutual exclusive if they take out each other, you can not both eat the cake and have the cake.

I am using code from aima-python in this tutorial (download package), these modules include all the necessary classes and functions for the GraphPlan algorithm in python.

Problems and solutions

This example code includes three planning problems and their GraphPlan 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():

    # Planning 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)')

    # Graph plan solution
    solution = aima.planning.GraphPlan(problem).execute()
    print("Air Cargo: {0}".format(aima.planning.linearize(solution)))
    print()

# Drive 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)'

    # Graph plan solution
    problem = aima.planning.PlanningProblem(knowledge_base, goals, [drive])
    solution = aima.planning.GraphPlan(problem).execute()
    print("Romania: {0}".format(aima.planning.linearize(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="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 = [aima.utils.expr("Robot(Robert)"), 
               aima.utils.expr("Packet(Letter)"), 
               aima.utils.expr("Room(MyOffice)"), 
               aima.utils.expr("Room(Floor)"), 
               aima.utils.expr("Room(MailOffice)"), 
               aima.utils.expr("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.GraphPlan(problem).execute()
    print("Robot delivery, part 1: {0}".format(aima.planning.linearize(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.GraphPlan(problem).execute()
    print("Robot delivery, part 2: {0}".format(aima.planning.linearize(solution)))
    print()

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

Air Cargo: [Load(C1, P1, SFO), Load(C2, P2, JFK), Fly(P1, SFO, JFK), Fly(P2, JFK, SFO), Unload(C1, P1, JFK), Unload(C2, P2, SFO)]

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