In this project, I have tried to understand problems in classical PDDL (Planning Domain Definition Language). We set up the problems for search, experiment with various automatically generated heuristics, including planning graph heuristics, to solve the problems. The aim of this project is to gain understanding about Planning Search to solve deterministic logistics planning problems for an Air Cargo transport system using a planning search agent.
With progression search algorithms like those in the navigation problem, optimal plans for each problem will be computed. Unlike the navigation problem, there is no simple distance heuristic to aid the agent. Instead, we implement domain-independent heuristics.
- my_air_cargo_problems.py
- my_planning_graph.py
All problems are in the Air Cargo domain. They have the same action schema defined, but different initial states and goals.
- Air Cargo Action Schema:
Action(Load(c, p, a),
PRECOND: At(c, a) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
EFFECT: ¬ At(c, a) ∧ In(c, p))
Action(Unload(c, p, a),
PRECOND: In(c, p) ∧ At(p, a) ∧ Cargo(c) ∧ Plane(p) ∧ Airport(a)
EFFECT: At(c, a) ∧ ¬ In(c, p))
Action(Fly(p, from, to),
PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
EFFECT: ¬ At(p, from) ∧ At(p, to))
- Problem 1 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK)
∧ At(P1, SFO) ∧ At(P2, JFK)
∧ Cargo(C1) ∧ Cargo(C2)
∧ Plane(P1) ∧ Plane(P2)
∧ Airport(JFK) ∧ Airport(SFO))
Goal(At(C1, JFK) ∧ At(C2, SFO))
- Problem 2 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK) ∧ At(C3, ATL)
∧ At(P1, SFO) ∧ At(P2, JFK) ∧ At(P3, ATL)
∧ Cargo(C1) ∧ Cargo(C2) ∧ Cargo(C3)
∧ Plane(P1) ∧ Plane(P2) ∧ Plane(P3)
∧ Airport(JFK) ∧ Airport(SFO) ∧ Airport(ATL))
Goal(At(C1, JFK) ∧ At(C2, SFO) ∧ At(C3, SFO))
- Problem 3 initial state and goal:
Init(At(C1, SFO) ∧ At(C2, JFK) ∧ At(C3, ATL) ∧ At(C4, ORD)
∧ At(P1, SFO) ∧ At(P2, JFK)
∧ Cargo(C1) ∧ Cargo(C2) ∧ Cargo(C3) ∧ Cargo(C4)
∧ Plane(P1) ∧ Plane(P2)
∧ Airport(JFK) ∧ Airport(SFO) ∧ Airport(ATL) ∧ Airport(ORD))
Goal(At(C1, JFK) ∧ At(C3, JFK) ∧ At(C2, SFO) ∧ At(C4, SFO))
"Artificial Intelligence: A Modern Approach" 3rd edition chapter 10 or 2nd edition Chapter 11 on Planning, available on the AIMA book site sections:
- The Planning Problem
- Planning with State-space Search
- Run uninformed planning searches for
air_cargo_p1
,air_cargo_p2
, andair_cargo_p3
; provide metrics on number of node expansions required, number of goal tests, time elapsed, and optimality of solution for each search algorithm. Include the result of at least three of these searches, including breadth-first and depth-first, in your write-up (breadth_first_search
anddepth_first_graph_search
). - If depth-first takes longer than 10 minutes for Problem 3 on your system, stop the search and provide this information in report.
- Use the
run_search
script for your data collection: from the command line typepython run_search.py -h
to learn more.
Progression planning problems can be solved with graph searches such as breadth-first, depth-first, and A*, where the nodes of the graph are "states" and edges are "actions". A "state" is the logical conjunction of all boolean ground "fluents", or state variables, that are possible for the problem using Propositional Logic.
For example, we might have a problem to
plan the transport of one cargo, C1, on a single available plane, P1, from one airport to another, SFO to JFK.
In this simple example, there are five fluents, or state variables, which means our state
space could be as large as
. Note the following:
- While the initial state defines every fluent explicitly, in this case mapped to TTFFF, the goal may
be a set of states. Any state that is
True
for the fluentAt(C1,JFK)
meets the goal. - Even though PDDL uses variable to describe actions as "action schema", these problems are not solved with First Order Logic. They are solved with Propositional logic and must therefore be defined with concrete (non-variable) actions and literal (non-variable) fluents in state descriptions.
- The fluents here are mapped to a simple string representing the boolean value of each fluent
in the system, e.g. TTFFTT...TTF. This will be the state representation in
the
AirCargoProblem
class and is compatible with theNode
andProblem
classes, and the search methods in the AIMA library.
"Artificial Intelligence: A Modern Approach" 3rd edition chapter 10 or 2nd edition Chapter 11 on Planning, available on the AIMA book site section:
- Planning Graph
- Run A* planning searches using the heuristics you have implemented on
air_cargo_p1
,air_cargo_p2
andair_cargo_p3
. Provide metrics on number of node expansions required, number of goal tests, time elapsed, and optimality of solution for each search algorithm and include the results in your report. - Use the
run_search
script for this purpose: from the command line typepython run_search.py -h
to learn more.
The planning graph is somewhat complex, but is useful in planning because it is a polynomial-size approximation of the exponential tree that represents all possible paths. The planning graph can be used to provide automated admissible heuristics for any domain. It can also be used as the first step in implementing GRAPHPLAN, a direct planning algorithm that you may wish to learn more about on your own (but we will not address it here).
Planning Graph example from the AIMA book
The file heuristic_analysis.pdf contains a decription and performance of the various heuristics implemented.
The file research_review.pdf contains a review of some of the developments in the AI field over the past few decades towards the problem of Planning and Search and understand their importance and impact to the discipline.
- Python 3.4 or higher
- Starter code includes a copy of companion code from the Stuart Russel/Norvig AIMA text.
The exercises in this project can take a long time to run (from several seconds to a several hours) depending on the heuristics and search algorithms you choose, as well as the efficiency of your own code. (You may want to stop and profile your code if runtimes stretch past a few minutes.) One option to improve execution time is to try installing and using pypy3 -- a python JIT, which can accelerate execution time substantially. Using pypy is not required (and thus not officially supported) -- an efficient solution to this project runs in very reasonable time on modest hardware -- but working with pypy may allow one to explore more sophisticated problems than the examples included in the project.