The present project consist on an Air Cargo transport system, where several cargo wants to be moved from one city to another city's airport, having several planes to achieve it.

To do so, we implement a planning search agent to solve the problem with different approaches.

In a regular search algorithm, like for the adversarial search in the Isolation game, the problem-solving agent deals with atomic representation of states and thus needs good domain-specific heuristics to perform well. With first-order-logic we can build domain-independent heuristics based on the logical structure of the problem.

To measure the performance, we first run the already studied **uninformed non-heuristic search algorithms**. The caractheristics that makes this algorithms uninformed, is the fact that they do not have any information about the states beyond that the one provided in the problem definition. Therefore, they can only *'ask'* if each new state that the algorithm creates is the goal or not, and act in consequence by stopping if it is the goal, or creating new states if it is not.

An automatic **domain-independent heristics with A*** that searches on top o a planning graph has been created to compare the search efficiency agains the previously explained methods.

Planning Domain Definition Language - PDDL - allows to performe a **factored representation** of the world in which a state is represented by a collection of variables. This way, 4 things needs to be defined in the search problem:

- The initial state
- The actions that are available in the state
- The result of applying the action
- The goal state

The actions are described by a set of **Action schemas** that implicitly define the `ACTIONS(s)`

and `RESULT(s,a)`

functions needed to do a problem-solving search. Actions schemas are a lifted (from propositional logic to first-order-logic) representation that describes an action based on the preconditions for that action to occur, and the effects that action will produce. The action-schema for our current problem are the action of loading/unloading a cargo into a plane, and the plane to fly:

```
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))
```

As we said, we also need the Initial and Goal state for each of the 3 different problems proposed by Udacity, increasing the complexity:

```
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))
```

```
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))
```

```
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))
```

In this link there is a complete description of the search algorithm that had been used in this problem. The search algorithms code has been taken from the well known book: *"Artificial Intelligence, a modern approach"*. The search algorithms can be divided into two subgroups:

Uninformed search, also called blind search, is a class of general purpose search algorithms that operate in a brute-force way. These algorithms can be applied to a variety of search problems, but since they don't take into account the target problem.

If information is available about the problem this could guide the search. Information is put in an evaluation function f(n) to be able to give a value to each state. Sometimes a heuristic function h(n) is used to guess the value if the information isn't perfect.

To run our search algorithms on the different problems we have to run the file run_search.py to which we can pass the parameteres included in that file as:

```
PROBLEMS = [["Air Cargo Problem 1", air_cargo_p1],
["Air Cargo Problem 2", air_cargo_p2],
["Air Cargo Problem 3", air_cargo_p3]]
SEARCHES = [["breadth_first_search", breadth_first_search, ""],
['breadth_first_tree_search', breadth_first_tree_search, ""],
['depth_first_graph_search', depth_first_graph_search, ""],
['depth_limited_search', depth_limited_search, ""],
['uniform_cost_search', uniform_cost_search, ""],
['recursive_best_first_search', recursive_best_first_search, 'h_1'],
['greedy_best_first_graph_search', greedy_best_first_graph_search, 'h_1'],
['astar_search', astar_search, 'h_1'],
['astar_search', astar_search, 'h_ignore_preconditions'],
['astar_search', astar_search, 'h_pg_levelsum'],
]
```

```
# Uninformed Search algorithms
def tree_search(problem, frontier):
frontier.append(Node(problem.initial))
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
frontier.extend(node.expand(problem))
return None
def graph_search(problem, frontier):
frontier.append(Node(problem.initial))
explored = set()
while frontier:
node = frontier.pop()
if problem.goal_test(node.state):
return node
explored.add(node.state)
frontier.extend(child for child in node.expand(problem)
if child.state not in explored and
child not in frontier)
return None
```

The algorithms used following this approach are the following:

- Breadth First Search
def breadth_first_tree_search(problem): return tree_search(problem, FIFOQueue())

- Breadth First Tree Search
def breadth_first_search(problem): node = Node(problem.initial) if problem.goal_test(node.state): return node frontier = FIFOQueue() frontier.append(node) explored = set() while frontier: node = frontier.pop() explored.add(node.state) for child in node.expand(problem): if child.state not in explored and child not in frontier: if problem.goal_test(child.state): return child frontier.append(child) return None

- Depth First Graph Search
def depth_first_graph_search(problem): return graph_search(problem, Stack())

- Depth Limited Search
def depth_limited_search(problem, limit=50): def recursive_dls(node, problem, limit): if problem.goal_test(node.state): return node elif limit == 0: return 'cutoff' else: cutoff_occurred = False for child in node.expand(problem): result = recursive_dls(child, problem, limit - 1) if result == 'cutoff': cutoff_occurred = True elif result is not None: return result return 'cutoff' if cutoff_occurred else None return recursive_dls(Node(problem.initial), problem, limit)

Uniform Cost Search

def uniform_cost_search(problem): return best_first_graph_search(problem, lambda node: node.path_cost)

Recursive Best First Search

def recursive_best_first_search(problem, h=None): h = memoize(h or problem.h, 'h') def RBFS(problem, node, flimit): if problem.goal_test(node.state): return node, 0 # (The second value is immaterial) successors = node.expand(problem) if len(successors) == 0: return None, infinity for s in successors: s.f = max(s.path_cost + h(s), node.f) while True: # Order by lowest f value successors.sort(key=lambda x: x.f) best = successors[0] if best.f > flimit: return None, best.f if len(successors) > 1: alternative = successors[1].f else: alternative = infinity result, best.f = RBFS(problem, best, min(flimit, alternative)) if result is not None: return result, best.f node = Node(problem.initial) node.f = h(node) result, bestf = RBFS(problem, node, infinity) return result

- Greedy Best First Graph Search
def best_first_graph_search(problem, f): f = memoize(f, 'f') node = Node(problem.initial) if problem.goal_test(node.state): return node frontier = PriorityQueue(min, f) frontier.append(node) explored = set() while frontier: node = frontier.pop() if problem.goal_test(node.state): return node explored.add(node.state) for child in node.expand(problem): if child.state not in explored and child not in frontier: frontier.append(child) elif child in frontier: incumbent = frontier[child] if f(child) < f(incumbent): # del frontier[incumbent] frontier.append(child) return None

Based on Udacity advice somo of the algorithms were not run because of a long execution time:

- For poblem 2 Breadth Dirst Tree Search, Depth Limited Search and Recursive Best Search
- For problem 3: Breadth First Tree Search, Depth Limited Search, Uniform Cost Search, and Recursive Best First Search.

Results can be stored running the next commands:

```
python run_search.py -p 1 -s 1 2 3 4 5 6 7 >> problem1_uninformed.txt
python run_search.py -p 2 -s 1 3 5 7 >> problem2_uninformed.txt
python run_search.py -p 3 -s 1 3 5 7 >> problem3_uninformed.txt
```

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

Breadth First Search | Yes |
6 |
0.034 | 43 | 56 | 180 |

Breadth First Tree Search | Yes |
6 |
1.045 | 1458 | 1459 | 5960 |

Depth First Graph Search | No | 12 | 0.009 |
12 | 13 | 48 |

Depth Limited Search | No | 50 | 0.089 | 101 | 271 | 414 |

Uniform Cost Search | Yes |
6 |
0.038 | 55 | 57 | 224 |

Recursive Best First Search | Yes |
6 |
3.084 | 4229 | 4230 | 17029 |

Greedy Best First Graph Search | Yes |
6 |
0.01 |
7 |
9 | 29 |

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

Breadth First Search | Yes |
9 |
12.847 | 3343 | 4609 | 30509 |

Breadth First Tree Search | -- | -- | -- | -- | -- | -- |

Depth First Graph Search | No | 575 | 4.055 | 582 | 583 | 5211 |

Depth Limited Search | -- | -- | -- | -- | -- | -- |

Uniform Cost Search | Yes |
9 |
18.379 | 4853 | 4855 | 44041 |

Recursive Best First Search | -- | -- | -- | -- | -- | -- |

Greedy Best First Graph Search | Yes |
9 |
1.47 |
399 |
401 | 3617 |

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

Breadth First Search | Yes |
12 |
74.815 | 14663 | 18098 | 129631 |

Breadth First Tree Search | -- | -- | -- | -- | -- | -- |

Depth First Graph Search | No | 596 | 4.511 |
627 |
628 | 5176 |

Depth Limited Search | -- | -- | -- | -- | -- | -- |

Uniform Cost Search | Yes |
12 |
92.658 | 18223 | 18225 | 159618 |

Recursive Best First Search | -- | -- | -- | -- | -- | -- |

Greedy Best First Graph Search | No | 22 | 28.939 | 5578 | 5580 | 49150 |

If we consider the most important point to reach the optimal solution within the constraint of 10 minutes, only Breadth First Search and Uniform Cost Search algorithms perform that well.

However, Depth First Graph Search seems to be the fastest (despite for the problem 2 Greedy Best First Graph Search performed amazingly fast) and also seems to need the least number of node expansions i.e. less memory use. However, it didn't find the optimal path at any of the problems.

Therefore, we can only keep Depth First Search and Uniform Cost Search as they are the only ones which always find the optimal path, and between this two, **Depth First Search performs a little bit better than Uniform Cost Search in the three cases**.

Only in the cases where the optimal path is not the criteria to determine which algorithm to use, the Greedy Best First Graph Search will be the best choice. It's execution time is more than aceptable and it only didn’t find the optimal path in the most complex problem (3). It did find 22 instead of 12, which is not that bad if the look at Depth First Graph which is the fastest but found a path of length 596.

As we have mentioned prevously, informed search uses domain-specific knowledge and can find the solutions more efficiently thanks to knowledge.

3 different heuristics will be implemented for the A* algorithm.

```
def h_1(self, node: Node):
# note that this is not a true heuristic
h_const = 1
return h_const
def h_pg_levelsum(self, node: Node):
'''
This heuristic uses a planning graph representation of the problem
state space to estimate the sum of all actions that must be carried
out from the current state in order to satisfy each individual goal
condition.
'''
# requires implemented PlanningGraph class
pg = PlanningGraph(self, node.state)
pg_levelsum = pg.h_levelsum()
return pg_levelsum
def h_ignore_preconditions(self, node: Node):
'''
This heuristic estimates the minimum number of actions that must be
carried out from the current state in order to satisfy all of the goal
conditions by ignoring the preconditions required for an action to be
executed.
'''
# TODO implement (see Russell-Norvig Ed-3 10.2.3 or Russell-Norvig Ed-2 11.2)
# Bring the knowledge base of locial expressions
kb = PropKB()
# Add the possitive sentence of the current state
kb.tell(decode_state(node.state, self.state_map).pos_sentence())
count = 0
# Iterate over all the goals in the problem
for clause in self.goal:
# If the goal is not already among the positive states - which means
# we have no reach the goal yet - then increase the counter
if clause not in kb.clauses:
count += 1
return count
```

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

A* Search with h1 heuristic | Yes |
6 |
0.043 | 55 | 57 | 224 |

A* Search with Ignore Preconditions heuristic | Yes |
6 |
0.039 |
41 | 43 | 170 |

A* Search with Level Sum heuristic | Yes |
6 |
5.10 | 7 |
9 | 28 |

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

A* Search with h1 heuristic | Yes |
9 |
18.371 | 4853 | 4855 | 44041 |

A* Search with Ignore Preconditions heuristic | Yes |
9 |
6.270 |
1428 | 1430 | 13085 |

A* Search with Level Sum heuristic | No | 21 | 249.784 | 97 |
99 | 906 |

--- This last one is raising an error ---

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions | Goal Tests | New Nodes |
---|---|---|---|---|---|---|

A* Search with h1 heuristic | Yes |
12 |
91.983 | 18223 | 18225 | 159618 |

A* Search with Ignore Preconditions heuristic | Yes |
12 |
27.898 |
5040 | 5042 | 44944 |

A* Search with Level Sum heuristic | No |
21 | 333.905 | 71 |
73 | 687 |

--- This last one is raising an error ---

The first and very important point of these approaches is that all of them led to the optimal path (except level sum in problem 3 - level sum may have a implementation bug).

However, it is clear that **Ignore Preconditions heuristic outperform the others** if we look at the execution time.

The Level Sum heuristic on the other hand has expanded way less nodes that the other heuristics. Then, if memory usage is the main criteria, this would be the heuristic to use, with the disadvantage of being vey slow. The low speed is a consequence of having to explore the graph and check in which level the goal is.

If we compare the winning strategy of each block:

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions |
---|---|---|---|---|

Breadth First Search | Yes |
6 |
0.034 |
43 |

A* Search with Ignore Preconditions heuristic | Yes |
6 |
0.039 | 41 |

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions |
---|---|---|---|---|

Breadth First Search | Yes |
9 |
12.847 | 3343 |

A* Search with Ignore Preconditions heuristic | Yes |
9 |
6.270 |
1428 |

Search Strategy | Optimal | Path Length | Execution Time (s) | Node Expansions |
---|---|---|---|---|

Breadth First Search | Yes |
12 |
74.815 | 14663 |

A* Search with Ignore Preconditions heuristic | Yes |
12 |
27.898 |
5040 |

It looks clear how A* outperforms Bread First Search, and clearer when the problem gains complexity. This shows the **benefits of informed search over uninformed search** where the results are achieved using less memory and in less time. Furthermore, informed search allows to customize a trade-off between speed and memory by customizing the different heurisitics that can not be done with uninformed search strategies.