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 bk 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.