C++代写 | COSC1076 Advanced Programming Assignment 1

C++实现路径规划的简化算法

COSC1076 Advanced Programming Techniques
Assignment 1
1.1 Overview
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
• Correctly Implement a pre-defined API
• Implement a medium size C++ program
• Use a prescribed set of C++11/14 language features
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
If there are questions, you must ask via the relevant Canvas discussion forums in a general manner (replicate your problem in a different context in isolation before posting).
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).
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.3 Start-up Code
On Canvas 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
• 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)
Assessment Type: Individual assignment; no group work. Submit online via Canvas→Assignments→Programming Assignment 1. Marks awarded for meeting requirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums.
Due date: 23:59pm, 25/Aug/2019; Deadlines will not be advanced but they may be extended. Please check Canvas→Syllabus or via Canvas→Assignments→Programming Assignment 1 for the most up to date information.
As this is a major assignment in which you demonstrate your understanding, a university standard late penalty of 10% per each working day applies for up to 5 working days late, unless special consideration has been granted.
Weighting: 15 marks
Page 1 of 11

,
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.
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.
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.
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.
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:
~~~~~~~~~~~~~
~………..~
~=======.===~
~..=…=….~
~..=…..=..~
~..=..=..=..~
~~~~~~~~~~~~~
Aspects of the maze are represented by different symbols:
Symbol Meaning
. (dot)
= (equal) ~ (tilda)
Empty/Open Space. The robot can enter any open space.
Wall or Obstacle within the maze. The robot cannot pass obstacles
The edge of the maze. Every maze is always bounded by the edge symbols
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:
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. • For this assignment the direction the robot is “facing” is ignored.
(0,0)
.
.
(12,0)
.
.
.
.
(0,6)
.
.
(12,6)
Page 2 of 11

,
!
In worked examples, the robot’s position will be marked by a star *.
For example, if the robot is at position (8,2):
then the robot could move to positions (8,1) or (8,3). 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.
The Milestone 2 algorithm, is given the starting position of the robot and calculates:
• All possible locations that the robot can reach from 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.
This algorithm is given below.
To conduct this algorithm, each position must be annotated by the distance that the position is from the robot’s starting position, x.
.
.
.
=
*
=
=
.
.
Pseudocode for Milestone 2: Generate all Reachable Positions
1 Let x be the starting position of the robot with distance 0
2 Let P be a list of positions the robot can reach, with distances (initially contains x)
3 Let T be a temporary list (initially empty)
4 repeat
foreach Position, q that the robot can reach from p do
8 |
| AddqtoPifandonlyifthereisnoiteminPwiththesameco-ordinateasq end
Select an item p from P that is not in T
5 |
6 |
7 | | Set the distance of q to be one more than the distance of p
9 |
10 |
11 until No such position p can be found
AddptoT
3.2 Worked Example
A worked example of stage 1 is given using the above maze.
Let us assume that the robot knows the map, and it’s 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-coordinate>, <y-coordinate>, <distance>)
For example, as the distance from the starting location is 0, this gives the tuple: (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.
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:
.
.
.
=
*
=
=
.
.
1 This is a simplified algorithm for the purposes of this assignment. There are many variations in literature, so be careful!
Page 3 of 11

,
These are given below. They are also a distance of 1 from the starting position, x, so they form tuples: 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.
In the 2nd iteration of the loop, an item is selected from P. This item may be:
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:
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 =[(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)]
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.
~
~
~
.
*
.
=
.
=
~~~~~~~~~~~~~
~………..~
~=======.===~
~xx=…=….~
~xx=…..=..~
~xx=..=..=..~
~~~~~~~~~~~~~
The final cost of reaching each co-ordinate (from starting position (8,2) which has a cost of 0) :
~~~~~~~~~~~~~
~87654321234~
~=======0===~
~xx=765=1234~
~xx=65432=45~
~xx=76=43=56~
~~~~~~~~~~~~~
Page 4 of 11

,
4. Task
This assignment is divided 4 Milestones. To receive a PS grade, you only need to complete Milestones 1 & 2.
To receive higher grades, you will need to complete Milestones 3 & 4. You must complete these milestones in sequence. See the Marking Rubric on Canvas for more details.
4.1 Milestone 1: Unit Tests
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.
A Unit test consists of three text files:
1. <testname>.maze – The complete maze
2. <testname>.initial – The starting position of the robot.
3. <testname>.pos – The list of all position(s) and distances that the robot can reach from the starting position. 4. <testname>.goal – (Milestone 3 only) The goal co-ordinate for path planning
5. <testname>.path – (Milestone 3 only) The path from the starting position to the goal
Your unit tests should be sufficient so that, if all of your unit tests pass, you are confident that your code in 100% correct.
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!
4.2 Milestone 2: Reachable Positions with Distances
Your task is to implement the an API that facilitates the simplified path planning algorithm described in Section 3.1 using three C++ Classes:
• 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:
• 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.
!
The starter code provides a simple unit testing wrapper to help run your unit tests. The testing code is executed by: ./test <testname>
!
You are implementing an API (set of methods), not a full C++ program. To actually run your code, you will need the unit testing file provided in the starter code.
Remember you cannot modify the pre-defined methods!
Page 5 of 11

,
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.
// x-co-ordinate
int getX();
// y-co-ordinate
int getY();
// Distance
int getDistance();
To help with using Position-Distance’s, the PDPtr type is defined. This is a pointer to a PositionDistance object.
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.
// Pointer to a PositionDistance
typedef PositionDistance* PDPtr;
// 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);
// Checks if the list contains a position-distance with the same co-ordinate
// as the given position.
bool containsCoordinate(PDPtr position);
// Remove everything from the list
// Don’t forget to clean-up the memory!
void clear();
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.
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.
PDPtr positions[100];
int numPositions;
Page 6 of 11

,
!
Make sure you correctly clean-up the memory used by the 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:
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 4. The path planning method for Milestone 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.
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.
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:
The getReachablePositions method returns a deep copy of the PDList.
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
// Initialise a with a given maze of size (x,y) PathPlanning(Grid maze, int rows, int cols);
// A 2D array to represent the maze or observations
// REMEMBER: in a grid, the location (x,y) is found by grid[y][x]! typedef char** Grid;
// The initial position
void initialPosition(int x, int y);
// Method for Milestone 2
// Return a DEEP COPY of the PDList of all position-distance’s // that the robot can reach
PDList* getReachablePositions();
!
A deep copy of a PDList is a new list is with a copy of all of the PositionDistance objects.
software
Page 7 of 11

,
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:
• 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.
4.3 Milestone 3: Path Planning
The PathPlanning class contains an additional method:
This method finds a path from the robot’s 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.
You will need to include additional Milestone 3 tests as part of your submission.
4.4 Milestone 4: Efficient Memory Management
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. • 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.
!
Take careful note. If your submission does not comply with these requirements it will receive a NN grade.
!
This is an extension Milestone. You only need to attempt this if seek a DI grade for this assignment.
// Method for Milestone 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 is an extension Milestone. You only need to attempt this if seek a HD grade for this assignment.
Page 8 of 11

,
4.4.1 Code Description
Finally, for this Milestone, in your implementation of the PathPlanning class, you must:
• 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 Description
Types.h Header file the typeedefs used in the assignment
PositionDistance.h/cpp
PDList.h/cpp
PathPlanning.h/cpp The PathPlanning class unit_tests.cpp 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
The PositionDistance class
The PDList class
A unit test can be run with the command:
For example, using the starter code
5.2. Getting Started
./unit_tests <testname>
./unit_tests sampleTest/milestone2
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. Submission Instructions
The assignment submission is divided into two ZIP files:
1. Your code solution (in <student_id>.zip>)
2. Your unit tests (in <student_id>_tests.zip)
Upload both ZIP files to the Assignment 1 Module on Canvas.
You may re-submit multiple times, however, only your latest submission will be marked. Be careful, resubmissions after the due- date are subject to late penalties.
Page 9 of 11

,
6.1. Submitting Code Files (.h/.cpp)
Place all of your code, header files (.h/.hpp) and code files (.cpp) into a single ZIP file. Do not use sub-directories. The ZIP file must be named by your student number:
<student_id>.zip
For example, if your student number is s123456, your code file submission should be:
s123456.zip
6.2 Submitting Unit Tests (.maze/.initial/.pos)
Place all of your unit test files in a separate ZIP file. You may organise these tests in a clear manner to help us.
The ZIP file must be named by your student number + the “tests” label:
<student_id>_tests.zip
For example, if your student number is s123456, your unit tests submission should be: s123456_tests.zip
7. Academic integrity and plagiarism (standard warning)
Academic integrity is about honest presentation of your academic work. It means acknowledging the work of others while developing your own insights, knowledge and ideas. You should take extreme care that you have:
 Acknowledged words, data, diagrams, models, frameworks and/or ideas of others you have quoted (i.e. directly copied), summarised, paraphrased, discussed or mentioned in your assessment through the appropriate referencing methods,
 Provided a reference list of the publication details so your reader can locate the source if necessary. This includes material taken from Internet sites.
If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work and ideas of another person without appropriate referencing, as if they were your own.
RMIT University treats plagiarism as a very serious offence constituting misconduct. Plagiarism covers a variety of inappropriate behaviours, including:
 Failure to properly document a source
 Copyright material from the internet or databases
 Collusion between students
For further information on our policies and procedures, please refer to the University website.
8. Assessment declaration
When you submit work electronically, you agree to the assessment declaration.
!
This must also include what you wrote to test your Milestone 3.
Page 10 of 11

,
9. Rubric/assessment criteria for marking
Weight
HD+
HD
DI
CR
PA
FL
NN
Unit Tests 10%
Outstanding and Flawless
Comprehensive Unit tests for Milestones 2 & 3, covering the majority of common use cases, and most edge cases
Comprehensive Unit tests for Milestones 2 & 3, covering the majority of common use cases, and most edge cases
Comprehensive Unit tests for Milestone 2, covering the majority of common use cases, and most edge cases
Sufficient Unit tests for Milestone 2, covering the majorit
Poor (or missing) Unit tests for any part of the assignment, with poor coverage
Not Completed
Unit tests contain no errors
Unit tests contain no errors
Unit tests contain no errors
Unit tests contain no errors
Unit tests may contain errors
Software 60% Implementation
Outstanding and Flawless
Complete and error-free implementation of Milestones 2, 3 & 4.
Complete and error-free implementation of Milestones 2 & 3.
Complete and error-free implementation of Milestone 2.
Complete and mostly error-free implementation of Milestone 2.
Incomplete or error ridden implementation of Milestone 2.
Not Completed
Compiles with the Milestone 2 & 4 mandatory requirements and restrictions.
Compiles with the Milestone 2 mandatory requirements and restrictions.
Compiles with the Milestone 2 mandatory requirements and restrictions.
Compiles with the Milestone 2 mandatory requirements and restrictions.
Failure to comply with the Milestone 2 mandatory requirements and restrictions.
Code Style 15%
Outstanding and Flawless
Exceptional and clear software design.
Good and clear software design.
Suitable consideration given to quality software design.
Some consideration given to quality software design.
Poor and messy software design.
Not Completed
Exceptional coding style and suitably documented code. No input from the developers is required to comprehend the code.
Exceptional coding style and suitably documented code.
Suitable coding style and suitably documented code. Code is readable, but parts of the software may not be clear
Suitable coding style and suitably documented code, but code is confusing to comprehend without further explanation from the developers
Poor and messy coding style with minimal documented code
Excellent use of permitted C++11/14 language features.
Excellent use of permitted C++11/14 language features.
Excellent use of permitted C++11/14 language features.
Sufficient use of permitted C++11/14 language features.
Poor use of permitted C++11/14 language features.
Code Description 15% /Report
Outstanding and Flawless
Suitable report for Milestones 2, 3 & 4, with good analysis
Suitable report for Milestones 2 & 3, with good analysis
Suitable report for Milestone 2, with good analysis
Suitable report for Milestone 2, with limited analysis
Poor, unclear, and confusing code description & report.
Not Completed
Page 11 of 11