Implementing the improved algorithm using a path finding algorithm

In the previous step, you implemented a working solution that moved the robot from its current position to the goal. Congratulations!

The only problem with this solution is that it will not work in different environments (i.e. if the robot starts at a different position or if the goal is a different cell). That’s because the code is hard-coded to work only in the specific environment.

A better solution is needed that will hopefully solve all instances of the problem. An algorithm is complete if it always produces a correct solution where one exists. Therefore, we need to implement a complete algorithm.

We need to implement an algorithm that finds the optimal next action for the robot. This problem is called path finding. There are known algorithms out there that solve the path finding problem. One such algorithm is called A* (pronounced ‘A-star’).

Using the A* algorithm implemented for you

For this course, you don’t need to implement A* or understand how the algorithm works. We will provide you with an implementation instead. Implementing this algorithm requires knowledge of advanced programming concepts, which we did not introduce to you. What you need to know is that this A* algorithm will return a path/solution to a path finding problem: given a start and a goal cell, it will give us a sequence of cells that we need to travel through to move from start to goal.

Open main.py in this lab, you will see certain new lines compared to the basic version.

As you will see, we are now using a path = utils.path_finding(robot) function to solve the problem. This function returns a path of cells that makes up a solution (if one exists). The A* algorithm therefore will return a sequence of cells in the variable path.

Recall that with the robot object, you can use the following commands:

The problem you need to solve

The problem that you need to focus on in this lab is the following. The A* algorithm returns a sequence of cells that the robot needs to travel through. But we need to find the right action (move right, move left, move up or move down) for the robot at each step. If we are currently at cell (1, 1) and the next cell in the path is to move to the cell (1, 2), in which direction should the robot move? Once the robot moves to (1, 2), the next step in the path is to move to cell (2, 2), again now which direction should the robot move?

Prepare

The files you will need to complete this exercise, and the solution to it, can be found in the ‘Supporting files and solutions‘ .zip file. Use the files in the folder ‘lab 8′.

Open Visual Studio Code and then open the main.py file. You will see a skeleton code with multiple TODO comments to help you complete this exercise. Each TODO block you will see (they appear as Python comments with leading # and the keyword TODO) is a small sub-task for you. 

Complete the code

Have a look at all the TODO comments and complete the code required for each.

Once you complete the code for each TODO, try to run the solution using different environments and check that the robot reaches the goal every time. Open a terminal: from the menu bar, Terminal → New Terminal. Then run python main.py env1 . Then try running python main.py env2 and finally python main.py env3.

If you get stuck, please check the solutions for hints!

Solutions

Remember, there is usually more than one solution. If you thought of something else, it’s not necessarily wrong. If your solution works, that’s great. Read the code here anyway and see if there is something different here and whether it is better.

A good programmer is one that reads and learns from others’ code!