这个Assignment是为清洁机器人设计一个寻找最短路径的程序

Software Project – Assignment 1
Programming for Engineers 2019/20 – MSc
[50% of total module marks]
Page | 1 of 4
Overview
This is an individual assignment worth 50% of your Programming for Engineers module marks.
The task is to construct a search program in C that implements an intelligent mechanism for a
cleaning robot to find the shortest route from its current position to its charging station.
Problem description
Meet HOOVI, a battery-operated automatic vacuum cleaner robot.
HOOVI operates during the night and its task is to keep clean all locations in an office
building. The building has three floors with a lobby as well as 12 offices and 12
reception rooms on each floor. There is also a lift for travelling to the next floor below or above.
Please consult the floor plans on the next page for details on how HOOVI can travel between
locations. Looking at these details, note that access to any office is only possible through its
dedicated reception room – for instance, on the second floor the office D3.2 can only be reached via
the reception room D3.1.
Room labels indicate pairs of connected reception & office rooms, as well as the floor number.
When developing your algorithm, take note of the common format in which these labels are written.
Each of the reception rooms has access to the lobby on that floor which must be crossed on the way
to the lift. (Tip: it may be a good idea to consider the lobby and the lift on each level as separate
rooms).
The charging station is in a separate room on the ground floor, accessible directly from the lift.
HOOVI can use the lift to travel between floors but only by one floor at each step.
Here more details about how HOOVI operates. You may use any of this to inform your program
design, but you also need to decide what is relevant for solving the problem and what is not:
1. HOOVI normally starts exploring the building by going from the charging room into the lift
and then travels to all locations (rooms, lobbies, lift) it can find a way into.
2. HOOVI has sensors to assess whether a room is dirty or clean and will only clean up those
rooms perceived as dirty. If a room is clean, it will move straight on to the next room.
3. HOOVI monitors its battery level whilst travelling or cleaning. If the battery level becomes
critically low, HOOVI should return to the charging station on the ground floor immediately.
4. Even though HOOVI will generally travel along the same route during cleaning, the
functionality described in 2. means that in the event the robot needs to return to the
charger, it may be in any room on any floor when it needs to return to the charger room.
5. HOOVI can determine the location in which it currently is and has a basic built-in model of
the building (that tells it where it can go from a given room), as illustrated in the floor plans.
6. HOOVI must perform a simulated search from the place it is currently in to find the charging
room. It has sufficient memory to remember any rooms it has considered going to during
that search.
Page | 2 of 4
Floor plans
Software Project – Assignment 1
Programming for Engineers 2019/20 – MSc
[50% of total module marks]
Page | 3 of 4
Task
Your task is to write a search program for HOOVI’s hardware platform with which it can find the
shortest path (i.e., least number of rooms travelled) from its current location to the charger room.
Extract the relevant problem-solving knowledge from the description above and devise a suitable
state representation to capture the information about locations. Devise a non-trivial successor
function that determines where HOOVI can go from any given place. For testing your program, you
should assume three scenarios and present the respective solution paths in your report, where
HOOVI is
I) in room K3.2. II) in the lift on the second floor. III) in room F1.1
Marking Criteria
There are two groups of assessment criteria, Program Internals (search algorithm) and HumanComputer-Interface (i.e., input and output on the command line interface). Each of the criteria in
these groups is worth a different amount of marks (Total: 100).
When developing your program, you should try to satisfy as many of these as you can. In the event
that you couldn’t manage to get your program to run, you can still get some marks for any sensible
elements that might form part of a correct solution. Note that satisfying a criterion somehow does
not automatically yield the stated marks – there may be deductions for inefficiencies and mistakes
made, or overly cumbersome approaches. While you are not primarily marked on the quality of your
code, it is advised to adhere to common practices. This includes sticking to the specification, using
suitable data types for representing the information and for storing results, avoiding undue code
duplication, and most importantly: use of comments in the code. Some features require you to think
about user interaction – make sure your program presents information clearly and is easy to use.
Program Internals (70 marks in total)
1. Appropriate state representation. (8)
2. Correct initial state defined. (2)
3. Core elements of a correct successor function that generates subsequent states. (4)
4. A successor function that generates valid states for solving the problem. (10)
5. A successor function that generates valid states such that HOOVI can use the search
sequence as a cleaning pattern for its routine job (all rooms to be searched). (16)
6. Correct goal test. (2)
7. Some kind of search activity going on. (5)
8. Correct elements of Breadth-First-Search list/queue management. (6)
9. Overall correct and efficient BFS implementation. (10)
10. An alternative working Depth-First-Search variant accessible within the same program (7)
Human-Computer-Interface (30 marks in total)
1. A text output of the starting location. (2)
2. A text output signaling that a solution path has been found. (2)
3. A text output of the goal location. (2)
Page | 4 of 4
4. Detailed printing of the solution path along the different locations involved. (6)
5. Detailed status messages about HOOVI’s search activity that can be switched on and off
through a variable in the code or by user input at the beginning of the program. (11)
6. The user can enter an arbitrary initial location at the start which is then used by the
algorithm to determine a solution path from there. (5)
7. The user can choose between BFS and DFS as search strategies from a menu. (2)
Report
Your report is a very important element of the assessment to confirm that you have written the
program yourself and understood the functionality implemented in it. It will hence be used to qualify
the marks you receive. Your report should point out the relevant marking criteria that you have
addressed, with detailed references to your source code, and answer the questions posed. If you
document your code extensively during development, then this will be a lot easier to do and you
need less explanation in the actual report text. For this reason, there is no minimum word count
given, but as a guideline, try not to exceed 1500 words in total (excluding Appendix).
Your report should have a title page with your name and candidate number on it and contain the
following chapters:
1. Introduction – A short section (no more than half a page) where you should describe the
purpose of the program and list the main functions in the code, briefly pointing out what
they do. You may then also include a screenshot of the program window, if you like.
2. Program description – here, you need to explain how your implementation addresses the
marking criteria. Focus on the Program Internals and make references to the code in the
appendix – you do not need to describe any of the interface criteria as these are self-evident.
Which search strategy do you think is most suited to this task – BFS or DFS? Explain why.
3. Appendix (source code as text, ideally with line numbers for easier reference from chapter 2)
Submission Requirements
Your submission must contain the following parts:
– Your program (source code file(s)) – must be zipped up into a single ZIP file!
– Your report as PDF (included in the ZIP)
You should submit your coursework online via Canvas. Keep in mind that this is an individual
assessment – the related University rules on academic misconduct apply, and here in particular with
respect to collusion with fellow students and plagiarising code from Web pages or elsewhere.
Submission Deadline
The assignment is due on Friday, 29 November 2018, by 4pm.
Good luck!