Advanced Programming Techniques
COSC1076 | Semester 1 2022
Assignment 1 | Implementing a Path Planning Algorithm
Assessment Type Individual Assessment. Clarifications/updates may be made via announcements
evant discussion forums.
Due Date 11.59pm, Sunday 10 April 2022 (Before Week 7)
Silence Policy From 5.00pm, Friday 08 April 2022 (Week 6)
Weight 30% of the final course mark
Submission Online via Canvas. Submission instructions are provided on Canvas.
In this assignment you will implement a simplified algorithm for Path Planning, and use it with a simple
simulated 2D robot moving around a room.
Figure 1: An example robot
In this assignment you will:
• Practice the programming skills such as:
– Dynamic Memory Management
• Implement a medium size C++ program using predefined classes
• Use a prescribed set of C++11/14 language features
This assignment is marked on three criteria, as given on the Marking Ru
• Milestone 1: Writing Tests.
• Milestone 2-4: Implementation of the Path Planner.
• Style & Code Description: Producing well formatted, and well
1.1 Relevant Lecture/Lab Material
To complete this assignment, you will require skills and knowledge from workshop and lab material for Weeks
2 to 4 (inclusive). You may find that you will be unable to complete some of the activities until you have
completed the relevant lab work. However, you will be able to commence work on some sections. Thus, do the
work you can initially, and continue to build in new features as you learn the relevant skills.
1.2 Learning Outcomes
This assessment relates to all of the learning outcomes of the course which are:
• Analyse and Solve computing problems; Design and Develop suitable algorithmic solutions using software
concepts and skills both (a) introduced in this course, and (b) taught in pre-requisite courses; Implement
and Code the algorithmic solutions in the C++ programming language.
• Discuss and Analyse software design and development strategies; Make and Justify choices in software
design and development; Explore underpinning concepts as related to both theoretical and practical
applications of software design and development using advanced programming techniques.
• Discuss, Analyse, and Use appropriate strategies to develop e
or-free software including static code anal-
ysis, modern debugging skills and practices, and C++ debugging tools.
• Implement small to medium software programs of varying complexity; Demonstrate and Adhere to good
programming style, and modern standards and practices; Appropriately Use typical features of the C++
language include basic language constructs, abstract data types, encapsulation and polymorphism, dy-
namic memory management, dynamic data structures, file management, and managing large projects
containing multiple source files; Adhere to the C++14 ISO language features.
• Demonstrate and Adhere to the standards and practice of Professionalism and Ethics, such as described
in the ACS Core Body of Knowledge (CBOK) for ICT Professionals.
One challenge in robotics is called path planning. This is the process of the robot figuring out how to navigate
etween two points within some environment. In this assignment you will implement a simplified path planning
algorithm for a robot moving about a simple 2D environment - a rectangular room with obstacles.
We will represent a simple 2D environment as a grid of ASCII characters. For example1:
Aspects of the environment are represented by different symbols:
= (equal) Wall or Obstacle within the environment. The robot cannot pass obstacles
. (dot) Empty/Open Space.
S The start position of the robot
G The goal point that the robot is trying to reach.
Each location in the environment is indexed by a (col,row) co-ordinate. The top-left corner of the environment
is always the co-ordinate (0,0), the col-coordinate increases right-wards, and the row-coordinate increases
down-wards. For the above environment, the four corners have the following co-ordinates:
Two dimensional environments can be designed in different ways. For this assignment we will use environments
1. There is one goal (ending) point denoted by character “G”.
2. The environment is always su
ounded by walls.
1for illustration purposes we are using an environment of 10x10, but the grid size for the implementation is different. Please
ead the document carefully to find the appropriate grid size for each milestone.
3. The environment can contains junctions, co
idors “open” space, loops or islands.
For the purposes of this assignment we will make several important assumptions:
• The robot knows the map of the whole environment it is in, at the start.
• Robot can only be located at cells marked as empty/open spaces.
• It may not be possible for the robot to reach every empty space.
• The robot can move-to (or reach) any one of 4 cells, that are to the left, right, up, or down from the
obots originating cell. Robot cannot move diagonally.
• For this assignment the direction the robot is “facing” is ignored.
In this assignment, the path planning problem is divided into two parts:
1. Identify Reachable Positions: Identify all possible locations that the robot can reach given the starting
position, and calculate the number of steps need to reach each position from start. The pseudo-code fo
the algorithm you need to implement is provided to you in Section 3.2.1.
2. Path Planning : Using the identified reachable positions, finds a path from the robot’s starting position
to the specified goal co-ordinate. You will have to develop the pseudo-code for this part. A description of
the algorithm you need to implement is provided to you in Section 3.3.1.
While there are many ways to navigate a 2D environment, you must implement the algorithms provided
in this document. If you don’t, you will receive a NN grade.
3 Assessment Details
The task for this assignment is to write a full C++ program that:
1. Reads in a 20x20 environment from standard-input (std::cin).
2. Finds the robot’s starting position within the environment (denoted by “S”).
3. Executes the Identify Reachable Positions algorithm (Section 3.2.1).
4. Executes the Path Planning algorithm (Section XXXXXXXXXXto find a path.
5. Prints out the environment and the path to be followed by robot to standard output (std::cout).
You may assume that the environment is a fixed size of 20x20, except for Milestone 4.
This assignment has four Milestones. To receive a PA/CR grade, you only need to complete Milestones 1 & 2.
To receive higher grades, you will need to complete Milestones 3 & 4. Take careful note of the Marking Ru
on Canvas. Milestones should be completed in sequence. For example, if you attempt Milestone 3, but you
Milestone 2 is buggy, you won’t get any marks for Milestone 3.
3.1 Milestone 1: Writing Tests
Before starting out on implementation, it is good practice to write some tests. We are going to use I/O-blackbox
testing. That is, we will give our program an environment to solve (as Input), and then test that our program’s
Output is what we expect it to be.
To run I/O-blackbox testing, we need to design appropriate environments and workout what should be the output
if our program is 100% co
A test consists of two text-files:
1. .env - The input environment for the program to solve
2. .expout - The expected output which is the solution to the environment.
A test passes if the output of your program matches the expected output. Section 4.4 explains how to run you
tests using the diff tool. We will also do a demo in the lectorial (Workshop).
You should aim to write a minimum of four tests2. We will mark your tests based on how suitable they are
for testing that your program is 100% co
ect. Just having four tests is not enough for full marks. Identify
scenarios where your program might
eak and construct tests accordingly.
The starter code contains a folder with one sample test case. This should give you an idea of how your tests
should be formatted (the sample will not be counted when marking).
2This is upto M3, for M4 you should write additional tests.
3.2 Milestone 2: Identify Reachable Positions
In this milestone, you will implement a Reachable Positions algorithm that starts from the “start” position and
explore the environment in a systematic way. The pseudo-code for the algorithm you need to implement is
3.2.1 Reachable Positions Algorithm
In this algorithm, a position in the environment that the robot can reach is denoted by a node and each node
will contain the (col,row) co-ordinate and distanceToS (the distance that the algorithm took to reach that
position from the robot’s starting position, S).
Pseudocode for the Reachable Positions algorithm
1 Input: E - the environment
2 Input: S - start location of the robot in the environment
3 Let O be a list of nodes (positions with distances) the robot can reach. Initially contains S. This is
also called the open-list.
4 Let C be a temporary list of nodes. Initially empty. This is also called the closed-list.
5 Define a variable p and point it to the start node in O
7 for Each node q that the robot can reach from pa do
8 Set the distanceToS of q to be one more that that of p
9 Add q to O if and only if there is no item in O with the same co-ordinate as q.
11 Add p to closed-list C.
12 Select a node p from the open-list, O, that is NOT in the closed-list C.
13 until no such position p can be found
awhen picking q, you should do that in the following order relative to p: up, right, down, left
A video of a worked example of the above algorithm is provided on canvas (assignment 1 page).
3.2.2 Implementation details
It is important to have a good design for our programs and use suitable data structures and classes. In
Assignment 1, you will implement our design3. You will implement 3 classes:
• Node class - to represent a position (col, row, distanceToS ) of the robot.
• NodeList class - provides a method for storing a list of node objects as used in pseudo-code above.
• PathPlanner class - that executes the reachable positions algorithm and path planning algorithms.
• The main file that uses these classes, and does any reading/writing to standard input/output.
You are given these classes in the starter code. You may add any of your own code, but you must not modify
the definitions of the provided class