C++
1(8 18 ) 1.1Overview
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.
In this assignment you will:
:
Practice the programming skills covered throughout this course, such as: :
Pointers
Dynamic Memory Management Provided API API
Correctly Implement a pre-defined API API
Implement a medium size C++ program C++
Use a prescribed set of C++11/14 language features C++ 11/14
This assignment is divided into four Milestones: :
Milestone 1: Writing Unit Tests
Milestone 2: Minimum required component for implementing a simple Grid Search
Milestone 3: Optional component to extend the search for a simplified path planner
Milestone 4: Optional component for efficient memory management
1.2 Relevant Lecture/Lab Material /
To complete this assignment, you will require skills and knowledge from lecture and lab material for Weeks 2
to 4 (inclusive).
2 4 ( 2 4 )
1.3 Start-up Code
You will find starter code to help you get running with the assignment. This code includes:
:
Header files, of the API (C++ classes) that you will implement API(C++)
Dummy (empty) code files, for you to implement ()
Unit Testing code, to help you write and run tests on your implementation
Example Unit Test case(s)
Page 1 of 10
2. Learning Outcomes
This assessment is relevant to the following Learning Outcomes:
:
1. 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.
(a)
(b); C++
2. 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.
;;
3. Discuss, Analyse, and Use appropriate strategies to develop error-free software including static code analysis, modern debugging skills and practices, and C++ debugging tools.
C++
4. 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, dynamic memory management, dynamic data structures, file management, and managing large projects containing multiple source files; Adhere to the C++11/C++14/C++17 ISO language definition and features.
;; C++; ; C++ 11/C++ 14/C++ 17 ISO
5. 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.
(CBOK)
3.Assessment details
One challenge in robotics is called path planning. This is the process of the robot figuring out how to navigate between two points within some environment. In this assignment you will implement a simplified path planning problem for a robot moving about a simple 2D maze.
In this assignment, the simple 2D maze will be represented as a grid of ASCII characters. For example:
ASCII :
~~~~~~~~~~~~~
~..~
~=======.===~
~..==.~
~..=..=..~
~..=..=..=..~
~~~~~~~~~~~~~
Aspects of the maze are represented by different symbols:
:
Symbol Meaning
Empty/Open Space. The robot can enter any open space. . (dot) /
Wall or Obstacle within the maze. The robot cannot pass
obstacles
= (equal)
The edge of the maze. Every maze is always bounded by the edge symbols
~ (tilda)
Each location in the maze (including the maze edges) is indexed by a cartesian (x,y) co-ordinate. The top-left corner of the maze is always the co-ordinate (0,0), the x-coordinate increases right-wards, and the y-coordinate increases down-wards. For the above maze, the four corners have the following co-ordinates:
()(xy) (0,0)X Y :
For the purposes of this assignment we will make two important assumptions:
:
1 The robot knows the map of the whole maze
2 It may not be possible for the robot to reach every empty space
For this assignment, the robot:
:
May only be located at cells with empty spaces.
The robot can move to any one of 4 cells, that are to the left, right, up, or down from the robots originating cell.
4 For this assignment the direction the robot is facing is ignored.
Page 2 of 10
(0,0)
.
.
(12,0)
.
.
.
.
(0,6)
.
.
(12,6)
! In worked examples, the robots position will be marked by a star *. ! *
For example, if the robot is at position (8,2):
(8,2):
then the robot could move to positions (8,1) or (8,3).
(81)(83) 3.1 Reachable Positions
For this assignment, you will develop a simplified path planning solution1. In Milestone 2 you will develop a base algorithm, which can be used in Milestone 3 to develop the path planning algorithm.
1 2 3
The Milestone 2 algorithm, is given the starting position of the robot and calculates:
2 :
All possible locations that the robot can reach from x
X
The number of spaces that each position is from x, which is equivalent to the number of moves the robot
would need to make to reach each position.
x This algorithm is given below.
To conduct this algorithm, each position must be annotated by the distance that the position is from the robots starting position, x.
x
=*=
=..
Pseudocode for Milestone 2: Generate all Reachable Positions 2 :
Let x be the starting position of the robot with distance 0 x 0 Let P be a list of positions the robot can reach, with distances (initially contains x)
p ( x)
Let T be a temporary list (initially empty) T () repeat
| Select an item p from P that is not in T P T P
| foreach Position, q that the robot can reach from p do P do Q 7 | | Set the distance of q to be one more than the distance of p
| |AddqtoPifandonlyifthereisnoiteminPwiththesameco-ordinateasq
10 | AddptoT pT
11 until No such position p can be found P
7 q p
8 P Q Q P
1
2
3
4 5
6
8
9 |end
3.2 Worked Example
A worked example of stage 1 is given using the above maze. 1
Let us assume that the robot knows the map, and its starting position, x, is at co-ordinate (8,2). To help with annotations, the distance that the robot is from the starting position, x will added to the co-ordinate to form a 3- tuple:
x (82) X 3 :
(
For example, as the distance from the starting location is 0, this gives the tuple: (8,2,0).
0:(8,2,0)
Initially, P contains the starting location and distance, such that P = [(8,2,0)]. Also initially, the temporary list,
T is empty.
p p=[(8,2,0)] t
In the loop, since P contains one item, it is selected, so that p =(8,2,0). Since T does not contain an item with the co-ordinate of p, the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:
p p=(8,2,0) t p P :
1 This is a simplified algorithm for the purposes of this assignment. There are many variations in literature, so be careful!
!
Page 3 of 10
=*=
=..
,
These are given below. They are also a distance of 1 from the starting position, x, so they form tuples: x 1:
1. (8,1,1) 2. (8,3,1)
All of these are added to P, such that: P =[(8,2,0),(8,1,1),(8,3,1)]. Also p is added to T, such that: T =[(8,2,0)]. The loop then repeats.
p :p=[(8,2,0)(8,1,1)(8,3,1)]p T,: In the 2nd iteration of the loop, an item is selected from P. This item may be:
P : 1. (8,1,1)
2. (8,3,1)
since the item (8,2,0) has a co-ordinate that is in T, it is not considered. For this example, the item (8,1,1) is selected so that p =(8,1,1), and the loop continues. By looking at the map, it is possible to determine all places from p that the robot can reach:
(8,2,0) t(8,1,1) P=(8,1,1) P :
These locates are, with their respective distances: :
1. (7,1,2) 2. (9,1,2) 3. (8,2,2)
Note that the distance is always one more than the distance in p. The first two are added to P, but the third has a co-ordinate that is already in P, so it is not added. Thus:
p p p :
P=[(8,2,0),(8,1,1),(8,3,1),(7,1,2),(9,1,2)].
Also p is added to T, such that: T =[(8,2,0),(8,1,1)] p T :T =[(8,2,0)(8,1,1)]
The loop repeats until it is impossible to find an item in P that does not have the same co-ordinate as an item in T. Eventually P contains the list of all positions the robot can reach in the maze and the distance to those positions. These will be all but the squares marked with an x.
P T P X
~~~
.*.
=.=
~~~~~~~~~~~~~
~..~
~=======.===~
~xx==.~
~xx=..=..~
~xx=..=..=..~
~~~~~~~~~~~~~
The final cost of reaching each co-ordinate (from starting position (8,2) which has a cost of 0) :
( 0 (8,2)):
~~~~~~~~~~~~~
~87654321234~
~=======0===~
~xx=765=1234~
~xx=65432=45~
~xx=76=43=56~
~~~~~~~~~~~~~
Page 4 of 10
,
4. Task
This assignment is divided 4 Milestones. 4 You must complete these milestones in sequence.
4.1 Milestone 1: Unit Tests 1:
Before starting out on implementation, you need to write a series of unit tests, so that you can test if your
implementation is 100% correct.
100% A Unit test consists of three text files: :
1.
3.
5.
Your unit tests should be sufficient so that, if all of your unit tests pass, you are confident that your code in 100% correct.
100% The starter code provides sample unit tests to help you get started These example tests are not sufficient. You will need to write your own tests!
starter !
! The starter code provides a simple unit testing wrapper to help run your unit tests. The testing code is executed by: ./test
:./test
4.2 Milestone 2: Reachable Positions with Distances 2:
Your task is to implement the an API that facilitates the simplified path planning algorithm described in Section
3.1 using three C++ Classes:
API API C++ 3.1 :
PostionDistance PDList
PathPlanning
For each class, you are given the API that you must implement. This API is a set of pre-defined methods on the classes. You are able to add any of your own code, but you must not modify the provided API. In addition to implementing the classes:
API API API:
You must provide some documentation about your implementation.
Your code should be well formatted, following the style guide
Your implementation of the API must comply with the a set of requirements and restrictions. API
!
You are implementing an API (set of methods), not a full C++ program. To actually run your code,
testing file provided in the starter code. Remember you cannot modify the pre-defined methods!
API() C++
Page 5 of 10
you will need the unit
4.2.1 PositionDistance Class
The PositionDistance classes represents one co-ordinate (x,y) of the robot within a maze, and the distance of that co-ordinate from the starting position. It has three methods that provide the components of the position of the robot.
PositionDistance (xy)
// x-co-ordinate int getX();
// y-co-ordinate int getY();
// Distance
int getDistance();
To help with using Position-Distances, the PDPtr type is defined. This is a pointer to a PositionDistance object.
PDPtr PositionDistance
4.2.2 PDList Class
The PDList class provides a method for storing a list of PositionDistance objects, as used in the pseudocode (Section 3.1). It has one constructor, one de-constructor, and a number of methods.
PDList PositionDistance ( 3.1 )
// Create a New Empty
List PDList();
// Clean-up the list ~PDList();
// Number of items in the list int size();
// Get a pointer to the position-distance at index
i PDPtr get(int i);
// Add a position-distance (as a pointer) to the list ()
// This class now has control over the pointer
// And should delete the pointer if the position-distance is removed from the
list void addBack(PDPtr position);
void addBack(PDPtr );
// Checks if the list contains a position-distance with the same co-ordinate
// as the given position. bool containsCoordinate(PDPtr position); (PDPtr );
// Remove everything from the list
// Dont forget to clean-up the memory! void clear();
// Pointer to a PositionDistance typedef PositionDistance* PDPtr;
To implement the PDList you MUST use an array of pointers. To help you with this, the starter code gives an example way for storing the array of pointers. You are free to change this if you wish.
PDList
The PDList class has full control over all pointers that are stored in the list. Thus, if items are removed
from the list you must remember to delete the PositionDistance object.
PDList
PDPtr positions[100]; int numPositions;
PositionDistance
Page 6 of 10
,
! Make sure you correctly clean-up the memory used by the PDList!
! PDList !
4.2.3 PathPlanning Class
The PathPlanning class provides an API (set of methods) to implementation of the algorithm in Section 3.1,
and a simplified path planning algorithm. It has three components:
PathPlanning 3.1 API() :
1.Creating the class, using a map of the maze
2.Providing the initial position of the robot
3.The method for Milestone 2 for retrieving the possible positions the robot can reach, along with the
distances 2 4.The path planning method for Milestone 3 3
The map of the maze is provided in the constructor of the PathPlanning
The maze is provided as a Grid, which is defined as a 2D array (see below). The top-left corner of the 2D array corresponds to the location (0,0). The parameters rows and cols give the size of the maze.
()(0,0)
It is very important to understand what the Grid type is. It is defined as a 2D array (given below). If you recall from lectures/labs, a 2D array is indexed by rows then columns. So if you want to look-up a position (x,y) in the maze, you find this by maze[y][x], that is, first you look-up the y value, then you look-up the x value.
()/ (xy) [y][x] y x
// A 2D array to represent the maze or observations // REMEMBER: in a grid, the location (x,y) is found by
grid[y][x]!
:(xy)[y][x]! typedef char** Grid;
The initial position of the robot is given to the PathPlanning class through the method
After being given the initial position, the PathPlanning may be asked for all of the possible positions (with distances) that the robot can reach:
():
// Initialise a with a given maze of size (x,y) PathPlanning(Grid maze, int rows, int cols);
// The initial position
void initialPosition(int x, int y);
// Method for Milestone 2 2
// Return a DEEP COPY of the PDList of all position-distances
// that the robot can reach PDList PDList* getReachablePositions();
The getReachablePositions method returns a deep copy of the PDList. getReachablePositions PDList
! A deep copy of a PDList is a new list is with a copy of all of the PositionDistance objects.
! PDList PositionDistance
4.2.4 Code Description
At the top of your PathPlanning implementation you must provide a description of the design of your implementation.
Provide this in a comment-block. This block should:
:
Describe (briefly) the approach you have taken in your implementation ()
Describe (briefly) any issues you encountered ()
Justify choices you made in your software design and implementation
Analyse (briefly) the efficiency and quality of your implementation, identifying both positive and negative aspects of your software
()
Page 7 of 10
4.2.5 Code Style
Your code style will be assessed. It should be well-formatting and comply with the course style guide.
4.2.6 Mandatory Requirements and Restrictions !
Your implementation MUST: :
Your PDList implementation must use an Array of Pointers to store all PositionDistance
objects. Your implementation may:
PDList PositionDistance
:
Add additional methods to the given classes. However, your code will ONLY be assessed using the methods listed in this spec, and provided in the starter code.
Your implementation MUST NOT: :
Alter the definition of the provided methods.
Use the STL containers (such as array, vector, list, deque, map, or any of utility). For this assignment
they are banned. If you are unsure if you can use an STL container, ask on the forum first.
STL (deque, map ) STL
4.3 Milestone 3: Path Planning 3:
! This is an extension Milestone.
!
The PathPlanning class contains an additional method: PathPlanning :
// Method for Milestone 3 3
// Get the path from the starting position to the given co-ordinate
// The path should be a DEEP COPY
PDList* getPath(int toX, int toY);
This method finds a path from the robots starting position to the specified goal co-ordinate. This should contain the ordered sequence of PositionDistance objects including the starting position and the given goal co- ordinate. You may assume that the goal co-ordinate can be reached from the starting position.
To solve this problem, you will be able to use the list of reachable positions that is generated in your Milestone 2. The algorithm is not given to you. However, think carefully about what information is contained in the list, specifically the distance information. There may also be more than one valid path.
2
You will need to include additional Milestone 3 tests as part of your assignment 1. 1 3
4.4 Milestone 4: Efficient Memory Management 4: ! This is an extension Milestone.
For this Milestone, you need implement the classes to use memory as efficiently as possible. Your code should only consume as much memory as is necessary.
To do this, you may wish to consider the following: :
Limiting the size of the array of pointers in PDList to only the number of cells needed to store all of the elements of the list.
PDList
Storing the maze in PathPlanning to use only the number of rows and columns given in the constructor
Which class(es) have ownership over any memory, variable or parameter.
Page 8 of 10
4.4.1 Code Description
Finally, for this Milestone, in your implementation of the PathPlanning class, you must:
PathPlanning :
Describe (briefly) the approach you have taken in your implementation. ()
Justify (briefly) why your implementation is efficient. ()
5.Starter Code
The starter code comes with the following
files:
:
File
Types.h
PositionDistance.h/cpp
PDList.h/cpp PathPlanning.h/cpp unit_tests.cpp
Description
Header file the typeedefs used in the assignment
typeedefs
The PositionDistance class The PDList class
The PathPlanning class
Code file to run unit tests
To compile individual files, into object file for testing, you can use the command:
:
g++ -Wall -Werror -std=c++14 -O -c file.cpp
5.1. Running Unit Tests
To compile the unit test code, with your implementation into an executable, you can use the command:
:
g++ -Wall -Werror -std=c++14 -O -o unit_tests PositionDistance.cpp PDList.cpp PathPlanning.cpp unit_tests.cpp
A unit test can be run with the command: : ./unit_tests
For example, using the starter code
./unit_tests sampleTest/milestone2
5.2. Getting Started
Part of the learning process of the skill of programming is devising how to solve problems. The best way to get started is to try just give some programming a go and try things out. Experimenting and practising are important
to the process of learning the skills of programming and this course.
,
6:
Page 9 of 10
1Unit Tests:Comprehensive Unit tests for Milestones 2 & 3, covering the majority of common use cases, and most edge cases
2 3
2Software Implementation :
Complete and error-free implementation of Milestones 2, 3 & 4.
23 4
Compiles with the Milestone 2 & 4 mandatory requirements and restrictions.
2 4
3Code Style:
Exceptional and clear software design.
Exceptional coding style and suitably documented code. No input from the developers is required to comprehend the code.
Excellent use of permitted C++11/14 language features. C++ 11/14
4Code Description/Report /
Suitable report for Milestones 2, 3 & 4, with good analysis 23 4
Page 10 of 10
Reviews
There are no reviews yet.