|fmind 7f6e9c58cb new submission||1 year ago|
|aimacode||2 years ago|
|data/run||1 year ago|
|images||2 years ago|
|notebooks||1 year ago|
|reports||1 year ago|
|reviews||1 year ago|
|tests||2 years ago|
|README.md||1 year ago|
|example_have_cake.py||2 years ago|
|lp_utils.py||2 years ago|
|my_air_cargo_problems.py||1 year ago|
|my_planning_graph.py||1 year ago|
|run_search.py||1 year ago|
This project includes skeletons for the classes and functions needed 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 from lecture, optimal plans for each problem will be computed. Unlike the navigation problem, there is no simple distance heuristic to aid the agent. Instead, you will implement domain-independent heuristics.
“Artificial Intelligence: A Modern Approach” 3rd edition chapter 10 or 2nd edition Chapter 11 on Planning, available on the AIMA book site sections:
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))
air_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 (
run_searchscript for your data collection: from the command line type
python run_search.py -hto learn more.
Why are we setting the problems up this way?
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
Truefor the fluent
At(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
AirCargoProblemclass and is compatible with the
Problemclasses, 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:
air_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.
run_searchscript for this purpose: from the command line type
python run_search.py -hto learn more.
Why a Planning Graph?
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).
example_have_cakemodule as an example.
unittesttest cases to evaluate your implementations. All tests should pass before you submit your project for review. From the AIND-Planning directory command line:
python -m unittest tests.test_my_air_cargo_problems
python -m unittest tests.test_my_planning_graph
run_searchscript is provided for gathering metrics for various search methods on any or all of the problems and should be used for this purpose.