This project solves deterministic logistics planning problems for an Air Cargo transportation. We first construct a compact data structure called planning graph, then compare the performance of Forward state-space search algorithms with different heuristics.
This project was submitted as part of the completion for Udacity’s Artificial Intelligence Nanodegree program
- 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))
- Ignore preconditions heuristics
Let’s first consider the approach adding edges to the graph. To relax the problem, we ignore all preconditions for each action and all literals except those in the goals. With these assumptions, every action is executable in all states and any single goal can be attained by a single step. This heuristic computes the minimum number of steps required to so that the union of effects of actions can achieve the goals. For our case, it’s equivalent to counting the number of unsatisfied goals.
- level sum heuristics
Once constructed a planning graph, we can estimate the cost
of achieving any goal literals
We implement the level sum heuristic, sum of the level costs of the goals. This heuristic is inadmissible, but works well in practice.
To achieve the goal of the first problem, it is required to move the cargo 1 from SFO to JFK, and cargo 2 from JFK to SFO. The optimal solution has a sequence of six actions that loading each cargo to the planes at each airport (2), flying both planes to the other airports (2) and unloading the cargo (2). An example of optimal solution is [Load(C2, P2, JFK), Load(C1, P1, SFO), Fly(P2, JFK, SFO), Unload(C2, P2, SFO), Fly(P1, SFO, JFK), Unload(C1, P1, JFK)].
Maybe because this problem is relatively small, uninformed search algorithms could find the optimal planning solution in fairly short time. Though the depth first graph search algorithm and depth limited search algorithm explored smaller number of new nodes and used less data storage in shorter runtime, the solution they found were not optimal, including redundant actions. This is because the search is not complete. Among the search algorithms that found optimal planning solution, the breadth first search performed best.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
BFS | 43 | 180 | 0.1745 | 6 | Optimal |
BFTS | 1,458 | 5,960 | 6.0689 | 6 | optimal |
DFGS | 12 | 48 | 0.0525 | 12 | Not optimal |
Depth limited | 101 | 414 | 0.4362 | 50 | Not optimal |
All heuristics found the optimal solution. The A* with h_pg_levelsum expanded smallest number of nodes, though it took the longest time to run. The h_ignore_preconditions reached goal state faster than other two heuristics. Though the performance results of uninformed search and heuristic search were quite similar for this small problem, T he A* with h_ignore_preconditions performed slightly better than other search algorithms.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
A* with h_1 | 55 | 224 | 0.2438 | 6 | Optimal |
A* with h_ignore_preconditions | 41 | 170 | 0.1670 | 6 | Optimal |
A* with h_pg_levelsum | 32 | 148 | 1.3353 | 6 | Optimal |
For this problem, additional cargo, plane, and airport are introduced. Initially, the cargo 1 and plane 1 are at SFO; the cargo 2 and plane 2 are at JFK; and the cargo 3 and plane 3 are at ATL. At the goal state of the problem, the cargo 1 is at JFK, and cargo 2 and cargo 3 at ATL. Note that the goal state does not count where the planes end up. The optimal planning solution in this case consists of a sequence of 9 actions, loading the cargo at each airport (3), flying the planes to the desired airports(3), then unloading the cargos (3). An example of optimal planning is [Load(C2, P2, JFK), Load(C1, P1, SFO), Load(C3, P3, ATL), Fly(P2, JFK, SFO), Unload(C2, P2, SFO), Fly(P1, SFO, JFK), Unload(C1, P1, JFK), Fly(P3, ATL, SFO), Unload(C3, P3, SFO)].
Similar to problem 1, depth first graph search could find the solution quickly and opened less nodes, but the solution found was not optimal. Depth limited tree search also returned a nonoptimal solution after expanding so many nodes. Breadth first tree search took more than reasonable time to find the solution in the local environment. I suspect this is because, unlike the graph search, the breadth first tree search does not exclude reversing to the previous state. For example, for tree search, repeating loading a cargo to a plane and unloading the same cargo right after is considered as executable actions. Among the uninformed search algorithms, the BFS performed the best. It returned the optimal solution fast, expanding less number of nodes.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
BFS | 3,343 | 30,509 | 65.8927 | 9 | Optimal |
BFTS | - | - | >10min | - | - |
DFGS | 582 | 5,211 | 14.5242 | 575 | Not optimal |
Depth limited | 222,719 | 2,054,119 | 4797.7268 | 50 | Not optimal |
Again, all heuristics found the optimal solution. The h_pg_levelsum heuristic expanded significantly less number of new nodes, though it spent more time than other two. Depending on the user’s need for storage and runtime, the decision for the best heuristics could be different. If finding solution in quick runtime is important, then A* with h_ignore_preconditions is better, vice versa.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
A* with h_1 | 4,853 | 44,041 | 80.8756 | 9 | Optimal |
A* with h_ignore_preconditions | 1,450 | 13,303 | 24.0998 | 9 | Optimal |
A* with h_pg_levelsum | 168 | 1,618 | 110.4581 | 9 | Optimal |
In this case, a total of four cargos are located at four different airports and only two planes are available. Optimal planning solution has a sequence of 12 actions. One example of optimal solution is [Load(C1, P1, SFO), Fly(P1, SFO, ATL), Load(C3, P1, ATL), Fly(P1, ATL, JFK), Load(C2, P1, JFK), Unload(C1, P1, JFK), Unload(C3, P1, JFK), Fly(P1, JFK, ORD), Load(C4, P1, ORD), Fly(P1, ORD, SFO), Unload(C2, P1, SFO), Unload(C4, P1, SFO)].
The breadth first tree search and depth limited search could not find the solution in a reasonable time. Similar to the two previous problems, the solution found by depth first tree search was not optimal. Among the algorithms that found the optimal solution, BFS performed better. It was faster to run and opened less new nodes.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
BFS | 9,456 | 71,407 | 216.99247 | 12 | Optimal |
BFTS | - | - | >10min | - | - |
DFGS | 832 | 3,692 | 17.4152 | 662 | Not optimal |
Depth limited | - | - | >10min | - | - |
A* with h_pg_levelsum heuristic took more than 10 minutes to run in the local system. A* with h_ignore_preconditions could find the solution very fast, however, the solution found was not optimal.
Algorithm | Expansions | New nodes | Time elapsed (sec) | Plan length | Optimality |
---|---|---|---|---|---|
A* with h_1 | 11,804 | 88,393 | 228.3863 | 12 | Optimal |
A* with h_ignore_preconditions | 4,643 | 36,113 | 90.2555 | 13 | Not Optimal |
A* with h_pg_levelsum | - | - | > 10m | - | - |
- Artificial Intelligence: A Modern Approach, 3rd Ed, S. Russel and P. Norvig (2010)
- MIT OpenCourseWare lecture on GraphPlan and making planning graphs