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!$).$

Tips

Make sure you get all the bookkeeping right. This includes handling of repeated states $($in

particular, what happens when you find a better path to a state already on the fringe$)$ and

saving the optimal solution path.

Pav attention to tiebreaking. If you have multiple nodes on the fringe with the same