Can Machine Learning Solve a Maze?

This project follows the Engineering Design Process. Confirm with your teacher if this is acceptable for your project, and review the steps before you begin.

Setting up the Google Colab Environment

1. You will need a Google account. If you do not have one, make one when prompted.
2. Download the maze.ipynb file from Science Buddies.
3. Upload the file to Google Colaboratory (you will need to sign in to your Google account at this point or make an account).
4. Read the Troubleshooting Tips and How to Use This Notebook sections. Follow the instructions you find there.
5. Run the code block under Importing Libraries, to bring in all of the functions.

Creating the Maze Environment

1. The first thing you need to do is create a maze for your agent to learn to navigate. We have done this for you in the code provided. Read through the comments and code in the Creating the Maze Environment section of the Colab notebook to make sure you understand it.
   1. The maze is a 5 by 5 grid of rows and columns. The numbering for the rows and columns starts at 0. In figure 1, the coordinates (or location) of the start (S) are (0,0). The coordinates for the goal (G) are (4,4).
      Image Credit: Science Buddies
      Figure 1. Coordinates are used in the maze class to tell the AI agent where the start and goal are in the maze. The coordinates are based on rows and columns starting at (0,0).
   2. The code for the maze has a 0 (for an empty space) or a 1 (for a wall) for every block in the grid. You can see this in Figure 2.
   3. In the maze visualization the empty spaces are black and the walls are white. You can see this in Figure 2.
   Image Credit: Science Buddies
   Figure 2. The code tells the AI agent where the empty spaces and walls are. We can visualize the maze using black for empty spaces and white for walls
2. Decide if you will use the maze we have provided or create your own. To make your own maze, change the code for the maze and the coordinates for the start (S) and goal (G).
   1. The size of the maze is entirely up to you, but it's essential to ensure that both the start and goal positions are located within the maze boundaries and not within any walls. Avoid creating mazes that have no possible route to reach the goal from the starting point, as it would make the task impossible for the agent to learn.
3. Run the code blocks for the maze class, and the maze visualization. Do this step even if you are using the maze we provided.

Navigating the Maze Untrained

1. We have provided the code that sets up the agent and defines the reward system for it. Read through and run the code blocks (without making any changes) labeled:
   1. Implementing the Agent
   2. Defining the Reward System
2. Now that your agent has been created and a starting point for the reward system has been implemented, it is time to see how the agent does before it has been trained (learned).
   1. Run the Testing the Agent code block ten times. In a lab notebook, record the number of steps the agent used to travel between the start and the goal, as well as the total reward each time.
   2. Calculate the average steps and average reward across all ten test trials.
   3. Solve the maze yourself by hand. What is the fewest number of steps you can take to solve the maze? Write this in your lab notebook and compare it to the average number of steps the untrained agent took. How efficient was the untrained agent at solving the maze?

Training the Agent

1. We have provided the code that defines the training function. Read through and run the code block labeled Setting Up the Reinforcement Loop. This code trains a reinforcement learning agent to navigate a maze using the Q-learning algorithm. The agent starts at the maze's initial position and selects actions based on the Q-table. It receives rewards and penalties for reaching the goal, hitting walls, or taking steps. The Q-table is updated during training to improve the agent's decision-making. After training, the average reward and average steps per episode are displayed, along with plots showing the training process.
   

   https://www.youtube.com/watch?v=qhRNvCVVJaA
2. Now that we have the training function implemented, it is now time to train the agent. Run the Training the Agent code block. In a lab notebook, record the average steps and rewards during the training process. Both of these figures will be in the output of the cell.

Evaluating the Agent

1. Run the Testing the Agent code block ten times. In a lab notebook, record the number of steps the agent took to travel between the start and the goal, as well as the total reward each time.
2. Calculate the average steps and average reward across all ten test trials.
3. Compare how efficiently the untrained and trained agents were at solving the maze. How did the trained agent do compared to the fewest number of steps possible for the maze?

Experimenting and Improving

1. Try experimenting with a different reward system to see how that affects how the agent learns. Copy or run this cell multiple times, changing the goal reward from 0 to 1, 10, 20, 30, etc... and to 100 and 1000. Keep track of the changes you make and the results in your lab notebook.
2. Each time compare your results to the untrained agent, the ideal number of steps, and your previous results. Which reward system resulted in the agent learning how to solve the maze in the least amount of steps first? Which reward system most consistently results in the agent solving the maze in the same number of steps?
3. Keep tweaking the reward system until you have a reward system that consistently performs well.