Question

You are required to create a robot path planner that is able to find an optimal path to navigate an environment and reach a target. By completing this assessment, you will show your skills on leveraging the best algorithm to solve a simplified real-world problem.

The maze can be seen in the image below. It can be seen that there are 12 rows and 24 columns, meaning there is a total of 288 blocks on the map. There are four different types of blocks in this map as follows:

• Green: wall

• White: space (void)

• Red: initial position of the robot

• Blue: the target

In C++, you can easily represent the entire maze using the following 2D array:

int maze[12][24] =

{

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1},

{1,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,1,1,1,0,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,1,0,0,9,1,0,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,0,1,0,1},

{1,0,1,1,1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1},

{1,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,0,1,0,1},

{1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,1},

{1,0,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,1},

{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, };

In this array, we use the following numbers to represent different types of blocks:

• 1: wall

• 0: space (void)

• -1: initial position of the robot

• 9: the target

In this assessment, you need to design and implement a robot path planner. Note you could select any of the taught algorithms in this course to be as your searching algorithm that you have to implement for robotics’ path planner. You do not have to draw a maze like the picture above. You can simply mark the shortest path obtained by your algorithm using for instance 2 (or any other numbers except 1, 0, -1, and 9) in the 2D array. If you draw the maze, however, it will be a lot easier to visualise the path and make sure that it is the closest path to the target when you are testing your program.

After implementation, write a reflective report detailing the experience of the development process. The report should be at least 1500 words and not more than 15 pages in length and include the following sections:

• Overview

• Review on some of the related robotics planners and utilised techniques

• Your designed planner and the flowchart of the development stages, this involving:

✓ What went right

✓ What went wrong

✓ What you are not sure about

• Performance analysis that involves computational complexity of the proposed planner strategy and computational actual average time taken during the running time.

• Conclusion

• List of references in Harvard format.

Task Instructions

• Appropriate, effective, and correct usage of C++ or Python.

CS1001 Advanced Algorithms

Dr. Ali Sadiq

• Good selection of search algorithm.

• Effective use of search algorithm.

The source code that you will be submitting:

1. Should be free or build warning, build errors, and all intermediate files (.obj, .pdb, etc), crashes, and errors (compile, run-time, logical, etc.).

2. Your code should be structured and written with the best practices in the field of programming.

3. There should be enough number of comments in the source files to show your understanding of the program.