COSC1076
Advanced Programming Techniques
Assignment 1
Particle Filter
Weight: 15% of the final course mark
Due Date: 11.59 pm, Friday 5 April 2019 (Week 5)
Learning Outcomes: This assignment contributes to CLOs: 1, 2, 3, 4, 6
Change Log
1.3
Added submission instructions
Updated code description requirements for Milestone 4
Minor corrections in Background
1.2
Updated references to classes
Updated notes on Unit Tests to be clearer about the purpose of the sample unit tests.
Updated parts of the Task descriptions to be clearer
Added Section “Getting Started”
1.1
Corrected positions on the worked example.
Updated compilation command, removing -c from full code command.
1.0
Initial Release
1
Contents
1 Introduction 3
1.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Relevant Lecture/Lab Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Start-up Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Plagiarism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Background 4
2.1 Particle Filter Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Worked Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Task 7
3.1 Milestone 1: Unit Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Milestone 2: Particle Filter API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.1 Particle Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.2 ParticleList Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.3 ParticleFilter Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.4 Code Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.5 Code Style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.6 Mandatory Requirements and Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Milestone 3: Unknown Orientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.4 Milestone 4: Efficient Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4.1 Code Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Starter Code 12
4.1 Running Unit Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.2 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5 Submission Instructions 13
5.1 Submitting Code Files (.h/.cpp) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Submitting Unit Tests (.maze/.obs/.pos) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2
1 Introduction
1.1 Summary
In this assignment you will implement an algorithm known as a Particle Filter, 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 the simple particle filter
Milestone 3: Optional component to extend the particle filter for map rotations
Milestone 4: Optional component for efficient memory management
1.2 Relevant Lecture/Lab Material
To complete this assignment, you will requires 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:
Dummy (empty) code files, for you to implement
Unit Testing code, to help you write and run tests on your implementation
Example Unit Test cases
1.4 Plagiarism
!
Plagiarism is a very serious offence.
A core learning outcomes for this course is for you to: 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.
The penalty for plagiarised assignments include zero marks for that assignment, or failure for this course.
Please keep in mind that RMIT University uses plagiarism detection software to detect plagiarism and that all
assignments will be tested using this software. See the RMIT website for more information about the university
policies on Plagiarism and Academic Misconduct.
3
2 Background
One challenge in robotics is called localisation. This is the process of the robot figuring out where it is within
some environment. One algorithm for localising a robot is called a Particle Filter. In this assignment you
will implement a simple particle filter 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) Empty/Open Space. The robot can enter any open space.
= (equal) Wall or Obstacle within the maze. The robot cannot pass obstacles
~ (tilda) 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 assumptions:

1. The robot know the map of the whole maze

2. While in the maze, the robot can only“see”one location about itself, represented as a 3×3 grid. For
   example, if the robot is at location (2,1) in the above maze, it can“see”:
   In the robot‘s view 3×3, the robot is always in the centre. The robot is also“facing”(or is orientated) in one of
   four directions This is represented by one of four characters:
   Symbol Meaning
   < Robot is facing LEFT

   Robot is facing RIGHT
   ^ Robot is facing UP
   v Robot is facing DOWN
   Thus, the position of the robot within the map is described as a 3-tuple, of its (x,y) co-ordinate and its
   orientation. For the above example, the robot’s position is (2,1,up).
   For this assignment, the robot can move about the maze using one of three actions:

3. Rotate clockwise 90?
4. Rotate counter-clockwise 90?
5. Move one space in the direction it is facing
   4
   !
   Note that the robot can never remain stationary! It must always either rotate or move one space. This
   is important!
   For example, if the robot started at position (2,1,up), then rotated counter-clockwise and moved one space
   forward to be at position (1,1,left), it would see:
   However, if the robot had rotated clockwise and moved one space forward to be at position (3,1,right), it
   would see almost exactly the same thing as when it started:
   The goal of localisation is for the robot to figure out its position within the maze, using only the information
   that the robot can see. The robot can do this by moving about the maze, collecting more information, and
   narrowing down its position.
   2.1 Particle Filter Algorithm
   One algorithm for localisation is called a Particle Filter. The robot estimates its position using a set of
   particles. A single particle represents one position that the robot could be at, that is (x, y, orientation).
   As the robot moves about the maze, it updates the particles (that it, its possible locations), until the robot
   collapses its location to a single particle.
   The overview of the particle filter algorithm is:
   Pseudocode for the Particle Filter you will implement
6. Let M be the map of the environment
7. Let P be a list of particles (initially empty)
8. repeat
   // Assume the robot has taken one action (rotate or move)
9. Get new observation o
10. Generate new particles, P
11. using P for where the robot could be
12. Using M, remove all particles from P
    0
    that do not match o
13. Replace P with P0, that is P = P0.
14. until Program Termination
    You will implement this assignment1.
    2.2 Worked Example
    A worked example of the particle filter algorithm is given using the above maze.
    Initially, the robot knows the map, M, and the list particles, P, which is empty.
    The robot gets it’s first observation:
    1This is a simplified algorithm for the purposes of this assignment. There are many variations in literature, so be careful!
    5
    Since this is the first observation, the robot could be at any position within the map, that is any (x, y,
    orientation). There are 39 (5 × 11 16) space that the robot could be at (taking into account walls). Since
    the robot is facing up, 39 particles should be generated and added to P0, all with the same orientation (up).
    Next these 39 particles are the observation, of which only 6 particles match the observation:
15. (2,1,up)
16. (3,1,up)
17. (4,1,up)
18. (5,1,up)
19. (6,1,up)
20. (10,1,up)
    All but these 6 particles are removed from P0. Finally, P is replaced with P0
    to now contain 6 particles.
    Next the robot takes an action and observes:
    Thus, the robot make a clockwise rotation action. Thus, for each particle in P, the robot is rotated, to generated
21. new particles in P0:
22. (2,1,right)
23. (3,1,right)
24. (4,1,right)
25. (5,1,right)
26. (6,1,right)
27. (10,1,right)
    These particles are matched against the observation. Unfortunately, all of the generated particles match the
    observation, so none are removed. (Don’t forget to set P = P0!). The robot takes another actions and observes:
    This must have been a forward move action (since the robot did not rotate), so P0
    is:
28. (3,1,right)
29. (4,1,right)
30. (5,1,right)
31. (6,1,right)
32. (7,1,right)
33. (11,1,right)
    Matching these against the observation removed 5 and 6, so that P is reduce to 4 particles.
    Finally, the robot takes one last action and observes:
    This was also a forward movement, so P0
    is:
34. (4,1,right)
35. (5,1,right)
36. (6,1,right)
37. (7,1,right)
    Matching these against the observation removed all but one particle. Thus, the position of the robot is narrowed
    to (7,1,right).
    6
38. 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.
    3.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:
39. <testname>.maze – The complete maze
40. <testname>.obs – A series of 3×3 observations, provided in sequence separated by new lines.

41. <testname>.pos – The final position(s) that the robot could be at once all of the observations have been
    processed. Each position must be placed on a separate line
    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!
    !
    The starter code provides a simple unit testing wrapper to help run your unit tests. The testing code is
    executed by: ./test <testname>
    3.2 Milestone 2: Particle Filter API
    Your task is to implement the an API that facilitates the Particle Filter algorithm described in Section 2.1 using
    three C++ Classes:
    Particle
    ParticleList
    ParticleFilter
    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.
    !
    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!
    7
    3.2.1 Particle Class
    The Particle classes represents one possible position (x,y,orientation) of the robot within a maze. It has
    three methods that provide the components of the position of the particle.
    // x-co-ordinate of the particle
    int getX();
    // y-co-ordinate of the particle
    int getY();
    // Orientation of the particle
    Orientation getOrientation();
    Notice that getOrientation() uses a custom type – Orientation. This type is represented as an Integer. The
    definition of the Orientation type provided in the started code, and is:
    // Orientation codes

    define ORIEN_LEFT 0

    define ORIEN_UP 1

    define ORIEN_RIGHT 2

    define ORIEN_DOWN 3

    typedef int Orientation
    To help with using Particles, the ParticlePtr type is defined. This is a pointer to a Particle object.
    // Pointer to a Particle
    typedef Particle* ParticlePtr;
    3.2.2 ParticleList Class
    The ParticleFilter class provides a method for storing a list of particles, for the P and P

42. variables in the
    particle filter pseudocode (Section 2.1). It has one constructor, one de-constructor, and four methods:
    // Create a New Empty List
    ParticleList();
    // Clean-up the particle list
    ~ParticleList();
    // Number of particles in the ParticleList
    int getNumberParticles();
    // Get a pointer to the i-th particle in the list
    ParticlePtr get(int i);
    // Add a particle (as a pointer) to the list
    // This class now has control over the pointer
    // And should delete the pointer if the particle is removed from the list
    void add_back(ParticlePtr particle);
    // Remove all particles from the list
    // Don’t forget to clean-up the memory!
    void clear();
    To implement the ParticleList you MUST use an array of pointers to particles. 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.
    8
    ParticlePtr particles[100];
    int numParticles;
    The ParticleList class has full control over all particle pointers that are stored in the list. Thus, if particles are
    removed from the list you must remember to“delete”the Particle object.
    !
    Make sure you correctly clean-up the memory used by the ParticleList!
    3.2.3 ParticleFilter Class
    The ParticleFilter class provides an API (set of methods) to implementation of the particle filter algorithm
    in Section 2.1. It has three components:
43. Creating a particle filter, using a map of the maze
44. Providing observation updates
45. Retrieving the possible locations of the robot
    The map of the maze is provided in the constructor of the ParticleFilter
    // Initialise a new particle filter with a given maze of size (x,y)
    ParticleFilter(Grid maze, int rows, int cols);
    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 mazey, that is, first you look-up the y value, then you look-up the x value.
    // A 2D array to represent the maze or observations
    // REMEMBER: in a grid, the location (x,y) is found by gridy!
    typedef char** Grid;
    New observations are given to the ParticleFilter through the method
    // A new observation of the robot, of size 3×3
    void newObservation(Grid observation);
    This also uses a grid. When this method is called, you may assume that:
    The grid is a 3×3 2D array, again indexed by rows then columns.
    The robot has taken precisely ONE action (either a 90?
    rotation, or a move forward) every time the
    newObservation method is called.
    The ParticleFilter may be asked for all of the possible locations that the robot might be at using:
    // Return a DEEP COPY of the ParticleList of all particles representing
    // the current possible locations of the robot
    ParticleList* getParticles();
    The getParticles method return an deep copy of the particles representing the possible locations of the robot.
    This means the returns a copy of all of the particles!
    !
    A deep copy of a ParticleList means that a new list is made with a copy of all of the particles.
    9
    3.2.4 Code Description
    At the top of your ParticleFilter 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
    3.2.5 Code Style
    Your code style will be assessed. It should be well-formatting and comply with the course style guide.
    3.2.6 Mandatory Requirements and Restrictions
    !
    Take careful note. If your submission does not comply with these requirements it will receive a NN grade.
    Your implementation MUST:
    Your ParticleList implmentation must use an Array of Pointers to store all Particle objects. The
    starter code provides an example to help you.
    Your implementation may:
    Add additional methods to your classes that extend the Particle, ParticleList or ParticleFilter.
    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 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.
    3.3 Milestone 3: Unknown Orientation
    !
    This is an extension Milestone. You only need to attempt this if seek a DI grade for this assignment.
    In Milestone 2 the orientation of robot is given in an observation. However, in practical situations, the robot
    only knows that it is“looking forwards”, that is, it does not know its orientation. Instead, the actual orientation
    of the robot in the maze must be deduced by the particle filter. Using the following maze.
    Consider the following observation, where the symbol representing the robot is an asterisk (*). Here it is
    assumed that the robot is facing towards the top of the observation grid.
    10
    In this case, the robot can actually be at one of 4 positions in the maze:
    (3,1,up)
    (4,3,right)
    (3,4,down)
    (2,3,left)
    For Milestone 2, you will need to modify your particle filter from milestone 1 to deduce the orientation of the
    robot if it is unknown. This will require you to think about how to handle different 90?
    rotations of the robot
    and maze. For observations for Milestone 2 you may assume that:
    The robot is represented using an asterisk (*).
    All observations assume that the direction the robot is facing towards the top of the grid.
    3.4 Milestone 4: Efficient Memory Management
    !
    This is an extension Milestone. You only need to attempt this if seek a HD grade for this assignment.
    For this Milestone, you need implement the ParticleList and ParticleFilter 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 ParticleList to only the number of cells needed to store all
    of the elements of the list.
    Storing the maze in ParticleFilter to use only the number of rows and columns given in the constructor
    Which class(es) have ownership over any memory, variable or parameter.
    3.4.1 Code Description
    Finally, for this Milestone, in your implementation of the ParticleFilter class, you must:
    Describe (briefly) the approach you have taken in your implementation.
    Justify (briefly) why your implementation is efficient.
    11
46. Starter Code
    The starter code comes with the following files:
    File Description
    Types.h Header file the typeedefs used in the assignment
    Particle.h Header file for the Particle class
    Particle.cpp Code file for the Particle class with dummy method implementations
    ParticleList.h Header file for the ParticleList class
    ParticleList.cpp Code file for the ParticleList class with dummy method implementations
    ParticleFilter.h Header file for the ParticleFilter class
    ParticleFilter.cpp Code file for the ParticleFilter class with dummy method implementations
    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
    4.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 Particle.cpp ParticleFilter.cpp
    ParticleList.cpp unit_tests.cpp
    A unit test can be run with the command:
    ./unit_tests <testname>
    For example, using the starter code
    ./unit_tests sampleTest/sample01
    4.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. Some suggestions of things you
    could think about are:
    Have you reviewed the Echo360 video on the assignment?
    Could you solve the particle filter problem by hand?
    Can you devise any simple tests, and test those by hand?
    Have a look at the header files and the methods you need to implement:
    Could you pick a class to start implementing?
    Could you pick a method that you could implement?
    12
47. Submission Instructions
    The assignment submission is divided into two ZIP files:
48. Your code solution (in <student_id>.zip>)
49. 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.
    5.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
    5.2 Submitting Unit Tests (.maze/.obs/.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:
    请加 WX：codehelp