I need a C++ Assignment to be done by the 8th of April.I have attached the assignment specifications, starter code, and rubric of the assignment below.Also, I wanted to let you guys know that you can add extra methods to the assignment but you can't delete the existing ones.
Please do let me know if you guys can do it ASAP.
Advanced Programming Techniques COSC1076 | Semester 1 2021 Assignment 1 | Implementing a Path Planning Algorithm Assessment Type Individual Assessment. Clarifications/updates may be made via announcements/rel- evant discussion forums. Due Date 11.59pm, Sunday 11 April 2021 (Before Week 6) Silence Policy From 5.00pm, Friday 09 April 2021 (Week 5) Weight 30% of the final course mark Submission Online via Canvas. Submission instructions are provided on Canvas. 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. Figure 1: An example robot In this assignment you will: • Practice the programming skills such as: – Pointers – Dynamic Memory Management – Arrays • 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 Rubric on Canvas: • Milestone 1: Writing Tests. • Milestone 2-4: Implementation of the Path Planner. • Style & Code Description: Producing well formatted, and well documented code. 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: 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. • 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 error-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. 2 Introduction 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 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 example: ========== =S.......= ========.= =......=.= ==.=.=...= =..=..=.== =.===.=..= =..==G==.= ===.====== ========== Aspects of the environment are represented by different symbols: Symbol Meaning = (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: (0,0) . . (9,0) . . . . (0,8) . . (9,8) Two dimensional environments can be designed in different ways. For this assignment we will use environments where: 1. There is one goal (ending) point denoted by character “G”. 2. The environment is always surrounded by walls. 3. The environment can contains junctions, corridors “open” space, loops or islands. For the purposes of this assignment we will make several important assumptions: 2 • 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 any one of 4 cells, that are to the left, right, up, or down from the robots 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. forward search: Conduct a forward search algorithm starting from the “start”, until the goal is reached. The pseudo-code for the algorithm you need to implement is provided to you in Section 3.2.1. 2. backtracking : Move backwards from the “goal” using, the results of forward search, to identify the shortest path from the start to goal. 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. 3. Executes the forward search algorithm (Section 3.2.1) until the robot reaches the goal. 4. Executes the backtracking algorithm (Section 3.3.1) to find the shortest 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 Rubric on Canvas. Milestones should be completed in sequence. 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 a environment to solve (as Input), and then test that our program’s Output is what we expect it to be. A test consists of two text-files: 1.
.env - The input environment for the program to solve 2. .out - 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 your tests using the diff tool. You should aim to write a minimum of four tests. We will mark your tests based on how suitable they are for testing that your program is 100% correct. Just having four tests is not enough for full marks. The starter code contains a folder with one sample test case. This should give you an idea of how your tests should be formatted. 3.2 Milestone 2: Forward Search In this milestone, you will implement a forward search algorithm that starts from the “start” position and explore the environment is a systematic way until it reaches the “goal” position. The pseudo-code for the algorithm you need to implement is provided below: 3.2.1 Forward Search 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 distance_travelled (the distance that the algorithm took to reach that position from the robot’s starting position). 3 Pseudocode for the forward Search algorithm 1 Input: E - the environment 2 Input: S - start location of the robot in the environment 3 Input: G - goal location for the robot to get reach 4 Let P be a list of positions the robot can reach, with distances (initially contains S). This is also called the open-list. 5 Let C be a list of positions the that has already being explored, with distances (initially empty). This is also called the closed-list. 6 repeat 7 Select the node p from the open-list P that has the smallest estimated distance (see Section 3.2.2) to goal and, is not in the closed-list C. 8 for Each position q in E that the robot can reach from p do 9 Set the distance_travelled of q to be one more that that of p 10 Add q to open-list P only if it is not already in it. 11 end 12 Add p to closed-list C. 13 until The robot reaches the goal, that is, p == G, or no such position p can be found 3.2.2 Estimated distance For the above algorithm we need to estimate the distance from a given node to the goal node. It is not possible to know the exact distance from a given node to the goal before solving the path planning problem. However we can come up with an approximation. In this implementation we use the following approximation as the estimated distance from a given node, p, to the goal node G. Estimated distance = distance_travelled of node p+Manhattan distance from p to G The Manhattan distance from node p with coordinates (colp, rowp) to node G with coordinates (colG, rowG) is computed as: Manhattan_distance = |colp − colG|+ |rowp − rowG| here |x| is the absolute value of x. The Manhattan distance represent the shortest distance from a node to goal if there are no obstacles. 3.2.3 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 design1. You will implement 3 classes: • Node class - to represent a position (col, row, distance_travelled) of the robot. • NodeList class - provides a method for storing a list of node objects as used in pseudo-code above. • PathSolver class - that executes the forward search and backtracking 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 methods and fields. 3.2