Programming for Engineers - Assignment 1: Shortest Route for robot HOOVI
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 robot to find the shortest route from its current position to its charging station.
Problem description
HOOVI is a battery-operated security and surveillance robot. It operates during the night and its task is to regularly check all locations in an office building for intruders. 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 first 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 audio and video sensors to assess whether a room is unoccupied. If that is the case, it will move straight on to the next room, or trigger an alarm otherwise. For the purposes of this assignment, you should assume the building is empty (there is no intruder).
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, the functionality described in 2. means that in the event the robot needs to return to the charger, it could be in any room on any floor when it needs to return to the charger.
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 | 1 of 4
Software Project - Assignment 1 Programming for Engineers 2023/24
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 roomN3.2. II) in the lift on the first floor. III) in room K1.1
Marking Criteria
There are two groups of assessment criteria, Program Internals (search algorithm) , Human-Computer-Interface (i.e., input and output on the command line interface)and English Writing Report . 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 does not automatically yield all the indicated 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 (55 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. Correct goal test. (3)
6. Some kind of search activity going on. (5)
7. Correct elements of Breadth-First-Search list/queue management. (6)
8. Overall correct and efficient BFS implementation. (10)
9. 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)
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)
English Writing Report (15 marks in total)
Please pay more attention on the requirement of report in the next part, and It is also highly recommended that if you could write down some of your own understanding during coding.
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 candidate number 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 – Firstly try to explain your algorithm with flow charts. Then, 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)
