In this lab, you will be using Breadth-first search (BFS), Depth-first search (DFS), and A-Star to teach Pac-Man to navigate his world in the most efficient way possible.

A lab is an optional self-assessed project where you will implement the techniques discussed in the lesson on a real-world problem.

In this lab, you will teach Pac-Man to search his world to complete the following tasks:

• find a single obstacle.
• find multiple obstacles.
• find the fastest way to eat all the food in the map.

This lab is possible thanks to the generous contributions of the UC Berkeley AI division and their work on the Pac-Man Project. The below is an example of what your AI will help Pac-Man do by the end of this lab!

• Download the Pac-Man search code zip file.
• Follow the instructions for the problem set here.
• Once you have received a score of 20 you have successfully completed the lab. Please do not share your answers on a blog post etc. as this is one of the requests made by the project's maintainers.
• There is no submission for this lab. It is highly recommended to complete it though so that you can further improve your understanding and your portfolio.

Remember that you can get assistance from your mentor, the forums, or the Slack channel. You can also review the concepts from the previous lessons.