In this report, we will look at solving air cargo problems with Planning Searches. Planning solvers using state-space searches have been around since at least 1971 when STRIPS was first released.

Since then it has seen many iterations, in this paper we will be using the Graphplan algorithm made popular in 1995.

Problem 1 is loading two pieces of cargo using two airplanes with two destinations.

Optimal Plan for problem 1.

```
Load(C1, P1, SFO)
Load(C2, P2, JFK)
Fly(P2, JFK, SFO)
Unload(C2, P2, SFO)
Fly(P1, SFO, JFK)
Unload(C1, P1, JFK)
```

This generated sequence came from our __breadth_first_search__ (BFS), which also finished the quickest in just under .2 seconds. BFS will continue to be our search that finishes the quickest of the methods that result in optimal plans. BFS is also both complete, in that it will find a solution **if it exists**, and has **guaranteed optimality**.

As you can see below, several search methods were able to generate optimal plans. Our __depth_first searches__ (DFS) however did not, but they did finish quickly! Our __depth_first__ searches are neither *complete* ( it is not guaranteed to find a solution ) nor *optimal* ( it is not guaranteed to find an optimum plan), but it will be included in all tables for completeness.

Problem 2 expands both our cargo pieces and airplanes to three with three destinations.

Optimal plan #rgb(239, 234, 234)

```
Load(C1, P1, SFO)
Fly(P1, SFO, JFK)
Load(C2, P2, JFK)
Fly(P2, JFK, SFO)
Load(C3, P3, ATL)
Fly(P3, ATL, SFO)
Unload(C3, P3, SFO)
Unload(C2, P2, SFO)
Unload(C1, P1, JFK)
```

This solution comes to us from our __A\*-levelsum__ algorithm. While this algorithm boasts the fewest new nodes by a large margin ( 85% fewer new nodes than the 2nd fewest algorithm ), it also finishes painfully slowly. **Levelsum** works by guiding the search based on the sum of the levels where the goals are first encountered. However, the slow down might be due to the implementation rather than the algorithm itself.

Our other A* search, __A\*-ignore-preconditions__, works by **relaxing the problem** by dropping preconditions from all actions. This makes our algorithm *admissible* by not overestimating. From AI-A modern approach, "There are two ways we can relax this problem to make it easier: by adding more edges to the graph making it strictly easier to find a path, or by grouping multiple nodes together, forming an abstraction of the statespace that has fewer states and thus is easier to search".

__A\*-ignore-preconditions__ uses the first approach of adding more edges to the graph.

Problem 3 expands our cargo and airport to four, but reduces our planes to only two. Problem 3 is the closest to a real world problem, so we will use it to finish our report and make some final conclusions on our algorithms.

Optimal Plan

```
Load(C1, P1, SFO)
Load(C2, P2, JFK)
Fly(P1, SFO, ATL)
Load(C3, P1, ATL)
Fly(P2, JFK, ORD)
Load(C4, P2, ORD)
Fly(P2, ORD, SFO)
Fly(P1, ATL, JFK)
Unload(C4, P2, SFO)
Unload(C3, P1, JFK)
Unload(C2, P2, SFO)
Unload(C1, P1, JFK)
```

This optimal plan comes from our __uniform_cost_search__, which is guaranteed *complete and optimal*, if step cost is greater than (ε where ε > 0) and the path cost is always increasing. Our __uniform_cost_search__ actually has the highest *Goal Tests* of every algorithm tested for problem 3. Despite this, it finishes around middle of the pack as far as time wise. It is a good choice of the guaranteed optimal algorithms for balancing memory and runtime .

In this paper we are looking at how different searches solve our Planning problems, comparing *informed searches*, searches where we provide heuristics to guide the search, and *uninformed*, searches that traverse the tree without guidance.

As we have seen, our informed searches, while guaranteed to be optimal and complete, typically take much longer to complete than our uninformed searches. Part of this might be due to our implementation, but it might also be that informed searches just require more computational power and are going to take longer.

Some uninformed searches generated plans that were incredibly bad, like __depth_first_graph_search__ , which generated plans with 392 moves for a problem that only required 12. Others , like our 'breadth_first_search' - give us both guaranteed optimality *and* completeness , all with the speed of an uninformed search. The downsides to BFS family of searches is of course memory. A breadth first search will typically expand b^{k} nodes and requires all nodes to reside in memory, from both the frontier and the explored states.

In the end, the choice of search algorithm should depend on the problem, how large it is, how much memory is required, and how fast does the solution need to be generated.

- Artifical Intelligence, A Modern Approach (Norvig and Russell). Revision 3.
- Wikipedia, https://en.wikipedia.org/wiki/Graphplan
- UCI, https://www.ics.uci.edu/~welling/teaching/271fall09/UninformedSearch271f09.pdf