Project #2: Floor Cleaning Robot Solution

    1. Project Objective:

Apply the knowledge learned from the course of data structures and implement an efficient robot floor cleaning algorithm.

    2. Project Description

You are to design an optimal floor cleaning algorithm to drive the robot. The floorplan is described as an ∗ matrix, in which each cell is marked with one the following status.

        a. “1” indicates an obstacle, which normally is a wall.

        b. “0” indicates a free space to be cleaned.

        c. “R” indicates where the robot is placed initially. This is also where the robot can be recharged. Note that this cell can only be connected for recharge and cannot be passed through. In other words, the robot should leave from “R” cell in the opposite direction to where it comes in.

The robot is to follow these rules:

        a. Always starts from the cell marked “R”.

        b. Needs to clean every free cell “0” on the floor.

        c. Cannot move into or cross any obstacle cell “1” or move outside the floor boundary.

        d. Can only move up, down, left and right.

        e. The robot is initially charged with a battery life “B”, which means the robot can move B steps before it runs out of power. Moving from one cell to next cell is counted as one step.

Note that the range of battery life “B” is -2147483648～2147483647.

        f. Needs to return for recharge before running out battery. Each recharge fully restores the battery life “B”.
        g. After cleaning all free cells, needs to return to the cell “R” for recharge.


    3. Test Case

Every student has to design and submit a test case prepared as a text file, named “floor.data”. The first line of the file contains three numbers, describing the number of rows (m), the number of columns (n) and the battery life (B). Following the first line, there shall be m lines and each line shall have n numbers, each represents the corresponding cell status.
EECS 204002 Data Structures 資料結構

a.    Example:

    • 10 30

1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
1
1
1
1
1
R  1
1
1
1
1


This case describes a floorplan with cells of 7 rows and 10 columns. The battery life allows the robot to move 30 steps for each fully charged run. We assume the row index and column index all starts from 0. Therefore, initially the robot is placed at cell (6, 4). Note that R can be at any, but only one, location.

        b. Valid Test Case

Make sure your test case is valid. A valid test case should have at least one solution to clean every free cell. Invalid test case gets no score. The size of the floorplan should be no more than 1000*1000.

        c. Test Case Competition

TAs will use all test cases collected from the class to evaluate your algorithm.


    4. Result output file

Output your optimized final floor cleaning path into a file named “final.path”. The first line should be the number of steps your algorithm used to finish the cleaning task and for the following lines, each should have two numbers i an j, representing the cell (i, j) walked subsequently by the cleaning robot.

Example:

6

    • 4

    • 5

    • 6

    • 5

    • 4

64
EECS 204002 Data Structures 資料結構

This example shows that the robot moves 6 steps. Obviously, this is not a complete floor cleaning path and will receive no score.

    5. Project Submission Rules

        a. First submission: submit both your test case and program to LMS following the set deadline.

        b. Final submission: submit both your revised program and project report. The deadline is one week after the first submission. In between, we will open all test student cases for program revision.
        c. Please use GitHub for source code control and show your program development history. Please follow the version control rules when doing programming.

    6. Grading Policy

        a. Algorithm Quality (60%)

            ▪ Basic Test (20%): TAs will provide two open test cases. For each test case passed by your program with correct solution, which may not be optimized, you receive 10% credit.
            ▪ First Submission and Final Submission Quality Test (Each 20%): Your implementation quality will be evaluated according to the following formula. For each test case j, we compute the numbers of wins for a person i of the robot walking steps and memory usage to be %,' and %,'. Simply, if your program achieves better quality or uses less memory than w other people, then the number of wins is w. The quality scores for a person i are then calculated as the following. Note that the total allowed execution time is restricted to be less than ten seconds.
-./ 10,2314,2

l  Step quality score: 15% ∗ ( '    0    )/  .

-./ 10,23-56 10,2
0    0
l  Memory usage score:
5%∗(
-./ ;0,23;4,2
)/  .


' -0./ ;0,23-056 ;0,2



0


where N is the total number of students in this class.

    • Illegal implementations receive zero scores: If your program cannot compile or execute on our testing platform, you get no score. Also, you should use only standard C++11 library, and should not use assembly codes. Note that our testing platform is a simple machine which supports only standard CPUs, supports no GPU, nor other non-CPU instructions, and is not connected to internet.
EECS 204002 Data Structures 資料結構

    b. Test cases (20%)

            ▪ Illegal test cases receive zero scores. Please make sure the matrix contains the correct number of elements in correct format, and all elements are of legal long integer numbers.

            ▪ Your test case is to be measured according to how well it can differentiate good algorithms from bad algorithms in the following formula.
20% ∗ (1 − 10 C4DE ?3@4 @A4B /F),
where N is the number of students, % is the number of steps of the i-th student’s program and ;%H is the best result.
Note: if your project cannot pass through your own test case, you will receive zero scores for the whole project.

    c. Report & Demo (20%)

        1. The report file should be named “report.pdf”.

        2. Each person should reserve a 15-min demo with TA. During the 1-on-1 demo, TA’s will ask you questions related to your project report, test case and your implemented code. TA may ask you to compile and execute your program on spot.
        3. Your project report is recommended to follow this outline:


1) Project Description

1-1) Program Flow Chart

1-2) Detailed Description

2) Test case Design

2-1) Detailed Description of the Test case


Note: The project report is limited to 10 pages.

Note: Your report can be either in Chinese or in English, or mixed.


Etiquette

    a. Do not plagiarize others’ work, or you will fail this course.

    b. No acceptance of late homework.

    c. Please frequently check the class website announcements for possible updates.