Andy Zeng
Pacman Search

Teach Pacman how to intelligently find his food in the shortest time possible!

Many problems in AI can be solved in theory by intelligently searching through many possible solutions: reasoning can be reduced to performing a search. For example, logical proof can be viewed as searching for a path that leads from premises to conclusions, where each step is the application of an inference rule. Planning algorithms search through trees of goals and subgoals, attempting to find a path to a target goal, a process called means-ends analysis. Simple exhaustive searches are rarely sufficient for most real world problems: the search space (the number of places to search) quickly grows to astronomical numbers. The result is a search that is too slow or never completes. The solution, for many problems, is to use "heuristics" or "rules of thumb" that eliminate choices that are unlikely to lead to the goal (called "pruning the search tree"). In this project, we will explore a few fundamental search algorithms (DFS, BFS, UCS, A*), and apply them to Pacman scenarios. The goal of the Pacman agent will be to find paths through his maze world (void of ghosts), both to reach a particular location and to collect food efficiently.

Depth-First Search

- Implemented using a graph search version of DFS; avoids expanding already visited states.
- Search algorithm is complete (finds some goal).
- The Pacman board will show an overlay of the states explored, and the order in which they were explored (brighter red means earlier exploration).
- The fringe is managed using a stack data structure.

Breadth-First Search

- Again, uses a graph search algorithm that avoids expanding any already visited states.
- Implemented using a graph search version of DFS; avoids expanding already visited states.
- Code is generic - can be used for puzzle solving algorithms.

Uniform-Cost Search

- BFS finds the fewest-actions path to the goal, we might want to find paths that are "best" in other senses.
- By changing the cost function, we can encourage Pacman to find different paths. For example, we can charge more for dangerous steps in ghost-ridden areas or less for steps in food-rich areas, and a rational Pacman agent should adjust its behavior in response.
- Left image: original BFS algorithm.
- Right image: modified with UCS cost-function algorithm.

A* Search

- A* implemented to take a heuristic function as an argument.
- A* implementation on the original problem of finding a path through a maze to a fixed position using the Manhattan distance heuristic.
- Finds the optimal solution slightly faster than uniform cost search in the maze (about 549 vs. 620 search nodes).

Corners Search Problem:
- In corner mazes, there are four dots, one in each corner. The search problem is to find the shortest path through the maze that touches all four corners (whether the maze actually has food there or not).
- A* implementation is used with a Manhattan distance heuristic.
- Finds the optimal solution much faster than BFS.

Admissibility vs. Consistency:
- Heuristics are just functions that take search states and return numbers that estimate the cost to a nearest goal - more effective heuristics will return values closer to the actual goal costs.
- To be admissible, the heuristic values must be lower bounds on the actual shortest path cost to the nearest goal (and non-negative).
- To be consistent, it must additionally hold that if an action has cost c, then taking that action can only cause a drop in heuristic of at most c.
- Admissibility isn't enough to guarantee correctness in graph search -- you need the stronger condition of consistency. However, admissible heuristics are usually also consistent, especially if they are derived from problem relaxations.
- The only way to guarantee consistency is with a proof. However, inconsistency can often be detected by verifying that for each node you expand, its successor nodes are equal or higher in in f-value. - The trivial heuristics are the ones that return zero everywhere (UCS) and the heuristic which computes the true completion cost.

Suboptimal Search

- A suboptimal path is reasonable when computation time becomes an issue.
- Greedy search implementation: Pacman finds a path to the closest dot.