Part $1$: Basic pathfinding

To begin with, you will consider the problem of finding a path through a maze from a given start

state to a given goal state. This scenario is illustrated in the figure above, where the start position

is indicated by the "Pacman" icon and the goal state is a dot. The maze layout will be given to

you in a simple text format, where $\text{'}\%\text{'}$ stands for walls, $\text{'}$P$\text{'}$ for the starting position, and $\text{'}.\text{'}$ for the

goal $($see sample maze file$).$ For this part of the assignment, all step costs are equal to one.

To solve different mazes, please implement the two search algorithms in the following two

groups.

Group $1$:

$$ Breadth$-$first search;

Group $2$:

$$ A$*$ search.

For $A^{**}$ search, use the Manhattan distance from the current position to the goal as the heuristic

function.

Run each of the above algorithms on the small maze, medium maze, big maze, and the open

maze. For each problem instance and each search algorithm, report the following:

a$.$ The solution and its path cost;

b$.$ Number of nodes expanded;

c$.$ Maximum tree depth searched;

d$.$ Maximum size of the fringe.

You can display the solution by putting a $\text{'}.\text{'}$ in every maze square visited on the path $($example

solution to the big maze$).$

Part $2$: Search with multiple goals

Now we consider a harder problem of finding the shortest path through a maze while

hitting multiple goals $($that is$,$ you want to make the Pacman, initially at $P,$ eat all the dots$).$

trickySearch.lay is a sample problem instance. Once again, in this part, we assume unit step

costs.

Revise your code from Part $1$ to deal with this scenario. This will require changing the goal test

$($have you eaten all the dots?$)$ and the state representation $($besides your current position in the

maze, is there anything else you need to know?$).$

Run the two search algorithms from Part $1$ on the tiny search, small search, and tricky search.

For each search method and problem instance, report the solution cost and number of nodes

expanded.

You will be surprised how inefficient the uninformed searches are even on the very small

problems! For the uninformed searches, feel free to put some reasonable upper limit on the

number of nodes expanded, and quit without reporting a solution if this limit is exceeded. To be

able to find a solution in a reasonable amount of time, it is crucial to design a good heuristic.

You should spend some time thinking about this. In the report, discuss the heuristic that you

chose and explain why it is admissible. Feel free to propose multiple heuristics and show results

for all of them. For reference, my implementation of $A^{**}$ search on the tricky search found a path

of length $61$ after expanding around $7600$ nodes. Try to design a heuristic that will do even

better!

Part $3($bonus$)$: Suboptimal search

Sometimes, even with $A^{**}$ and a good heuristic, finding the optimal path through all the dots is

hard. In these cases, we'd still like to find a reasonably good path, quickly. Write a suboptimal

search algorithm that will do a good job on medium search and big search. To get bonus points,

you should be able to find a path of length around $350$ on the big search after expanding around

$700$ nodes $($of course, you're welcome to try to do even better than that!$).$