Python Project: Solution Search applied to Pacman game:

We implemented breadth first search (BFS) using a FIFO data structure to explore graph paths, depth first search (DFS) using a stack data structure for exploring graph paths, uniform cost search and a star search, using priority queues to explore graph paths and had to compare the results.

We ran the algorithms on different sized mazes for Pacman to explore and made cost comparisons.

With a varying cost function, Pacman may choose different paths.

We explored charging more for for more dangerous steps in a ghost-ridden environment and charging less in food rich areas.

A rational Pacman agent would adjust his behavior in response to the cost comparison of the path taken.

Each search algorithm is similar except in how they manage the fringe of path exploration (data structures mentioned above).

BFS expands outward in every direction, but is not sensitive to exploration cost.

Uniform Cost Search is similar to BFS except that it gets farther in the lower cost area than BFS in getting to the goal node.

It is not as good as A-star search, because it explores every direction and has no information about the goal.

It starts at the top and works systematically down, finding the cheapest path in terms of cost.

DFS goes to the highest depth before going further in the search.

We did not do greedy search, but that goes straight to the solution node and is not optimal, since it goes through high cost areas to get to the goal.

A-star hedges its bets, explores a bit in the wrong direction, just to be sure because the heuristic it uses is imperfect, but it does a very small amount of work, not much worse than greedy, and it is optimal.

A-star uses backward costs and estimates of forward costs. It is optimal with admissible and consistent heuristics. Heuristic design is the key to it, and sometimes it makes sense to use a relaxed problem, and is what to use in practice.