Kory Becker - April 1, 2020

Synopsis

Artificial Intelligence planning is the process of determining an optimal plan of actions in order to achieve a goal state. AI planning is typically performed by analyzing the subset of available actions for a given domain and determining the shortest distance, cost, and least number of actions to execute in order to reach a goal state.

This report includes a heuristic analysis of the search complexity as a function of domain size, search time, algorithm, and heuristic for the AI planning problems Air Cargo 1-4. The report analyzes and compares uninformed search algorithms, including breadth first search and depth first search, with comparisons to heuristic-based search algorithms including greedy best first search and A* search. Finally, we summarize the optimality of the varying solutions against domain size, algorithm, and heuristic.

Air Cargo Problem 1
Search Method Heuristic Length Time (s) Actions Expansions Goal Tests New Nodes
Greedy Best First Graph Search h_unmet_goals 6 0.035 20 7 9 29
Uniform Cost Search 6 0.223 20 60 62 240
Astar Search h_unmet_goals 6 0.262 20 50 52 206
Breadth First Search 6 0.295 20 43 56 178
Greedy Best First Graph Search h_pg_maxlevel 6 1.587 20 6 8 24
Astar Search h_pg_maxlevel 6 3.872 20 43 45 180
Greedy Best First Graph Search h_pg_setlevel 6 3.946 20 6 8 28
Astar Search h_pg_levelsum 6 4.313 20 28 30 122
Greedy Best First Graph Search h_pg_levelsum 6 4.791 20 6 8 28
Astar Search h_pg_setlevel 6 5.131 20 33 35 138
Depth First Graph Search 20 0.113 20 21 22 84
Air Cargo Problem 2
Search Method Heuristic Length Time (s) Actions Expansions Goal Tests New Nodes
Greedy Best First Graph Search h_unmet_goals 9 0.231 72 17 19 170
Breadth First Search 9 4.592 72 3343 4609 30503
Astar Search h_unmet_goals 9 5.701 72 2467 2469 22522
Uniform Cost Search 9 7.605 72 5154 5156 46618
Greedy Best First Graph Search h_pg_levelsum 9 25.100 72 9 11 86
Greedy Best First Graph Search h_pg_setlevel 9 42.215 72 9 11 84
Greedy Best First Graph Search h_pg_maxlevel 9 51.763 72 27 29 249
Astar Search h_pg_levelsum 9 637.866 72 357 359 3426
Astar Search h_pg_setlevel 9 3675.842 72 1037 1039 9605
Astar Search h_pg_maxlevel 9 3740.885 72 2887 2889 26594
Depth First Graph Search 619 5.815 72 624 625 5602
Air Cargo Problem 3
Search Method Heuristic Length Time (s) Actions Expansions Goal Tests New Nodes
Breadth First Search 12 14.571 88 14663 18098 129625
Astar Search h_unmet_goals 12 14.939 88 7388 7390 65711
Uniform Cost Search 12 23.811 88 18510 18512 161936
Astar Search h_pg_levelsum 12 1774.122 88 369 371 3403
Greedy Best First Graph Search h_pg_maxlevel 13 120.258 88 21 23 195
Greedy Best First Graph Search h_pg_levelsum 14 102.666 88 14 16 126
Greedy Best First Graph Search h_unmet_goals 15 0.258 88 25 27 230
Greedy Best First Graph Search h_pg_setlevel 17 416.411 88 35 37 345
Depth First Graph Search 392 2.244 88 408 409 3364
Air Cargo Problem 4
Search Method Heuristic Length Time (s) Actions Expansions Goal Tests New Nodes
Astar Search h_unmet_goals 14 84.112 104 34330 34332 328509
Breadth First Search 14 116.875 104 99736 114953 944130
Uniform Cost Search 14 164.390 104 113339 113341 1066413
Greedy Best First Graph Search h_pg_levelsum 17 190.498 104 17 19 165
Greedy Best First Graph Search h_pg_maxlevel 17 419.806 104 56 58 580
Greedy Best First Graph Search h_unmet_goals 18 0.233 104 29 31 280
Greedy Best First Graph Search h_pg_setlevel 23 1816.019 104 107 109 1164

Results

The tables recorded above display the varying sequences of actions and timing metrics for solving each problem using differing algorithms and heuristics. The optimal plan, highlighted in green, corresponds to the plan with the minimal number of actions to reach a goal state with the least processing time. By contrast, the least optimal plan, highlighted in red, corresponds to the plan with the most number of actions and the longest processing time.

The growth trends displayed in the results demonstrate that as the problem sizes increase, so too do the number of actions executed and the number of expansions made during each search. This has a direct relationship to the processing time and optimal plan solution for each problem set. Further, as the domains grow larger, it becomes increasingly more time intensive to utilize Depth First Search type algorithms, which operate by traversing to the deepest extent within a search space before exploring other more promising paths.

Which algorithm would be most appropriate for planning in a very restricted domain (i.e., one that has only a few actions) and needs to operate in real time?

We can note from the results of the problem Air Cargo 1 that the optimal plan consists of 6 actions. As this corresponds to a relatively limited sequence of actions to achieve a goal state, we can compare this to a restricted and time-sensitive domain. As our data displays, Breadth First Search achieves the optimal action plan in shortest amount of time.

Which algorithm would be most appropriate for planning in very large domains (e.g., planning delivery routes for all UPS drivers in the U.S. on a given day)

The largest of the problem sets is Air Cargo 4 which results in an optimal plan consisting of 14 actions. This is a relatively larger domain and requires a much greater analysis of combinations of actions in order to achieve the goal state. Our data shows that searching a larger domain such as this can be performed in an optimal capability by using A* Search with the h_unmet_goals heuristic.

Which algorithm would be most appropriate for planning problems where it is important to find only optimal plans?

When the importance is placed upon only finding the most optimal plans at any cost and time duration, our data shows that Breadth First Search, Uniform Cost, and A* Search with h_unmet_goals can produce a goal plan with the least number of actions. In all 4 problem sets, these algorithms produced optimal plans, achieving the best plan sequences and timing metrics. Note, the tables for all 4 problems include these algorithms in the top 3-4 rows. When processing time is not considered, these algorithms are best suited for discovering optimal plans. In particular, the h_unmet_goals heuristic results in the shortest processing times for discovering optimal plans in both A* Search and Greedy Best First Graph Search algorithms.

Optimal Plans Discovered

The results demonstrate an optimal sequence of actions as discovered for each problem type. The plans are described below.

Air Cargo Problem 1

Solving Air Cargo Problem 1 using greedy_best_first_graph_search with h_unmet_goals.

# Actions   Expansions   Goal Tests   New Nodes
    20          7           9           29

Plan length: 6

Time elapsed in seconds: 0.04

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

Air Cargo Problem 2

Solving Air Cargo Problem 2 using greedy_best_first_graph_search with h_unmet_goals.

# Actions   Expansions   Goal Tests   New Nodes
    72          17          19         170

Plan length: 9

Time elapsed in seconds: 0.23

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

Air Cargo Problem 3

Solving Air Cargo Problem 3 using breadth_first_search.

# Actions   Expansions   Goal Tests   New Nodes
    88        14663       18098       129625

Plan length: 12

Time elapsed in seconds: 14.57

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

Air Cargo Problem 4

Solving Air Cargo Problem 4 using astar_search with h_unmet_goals.

# Actions   Expansions   Goal Tests   New Nodes
   104        34330       34332       328509

Plan length: 14

Time elapsed in seconds: 84.11

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