CO4104/CO7104 Assessment 4

CO4104/CO7104 Assessment 4 (2013-2014)

This is the fourth (and last) assessed courswork in CO4104/CO7104. This exercise does not use Course Master and you need to submit your work via the handin system!. Student’s registered to CO4104 (or anyone else, for that matter) can submit here .

The deadline for this worksheet is 18 Janary, 23:59 (11:59pm). It should be handed in on the Departmental Handin System.

A forum has been set up for questions regarding this assessment. The forum will be monitored throughout the period until submission. If you see that your message is not answered in reasonable time feel free to send me an email saying that there are messages awaiting my approval (and answer).

Exercise 1

This exercise is motivated by a problem in robotics. The idea is that there is a robot exploring an unknown terrain. The robot starts with a vague information about the surroundings and as it goes along it improves its view of the environment.
The exercise is not meant to be completely realistic! This is just the motivation.

The main concepts that you will be practicing during this assessment are inheritance, virtual functions, and the usage of some of the features of the STL.

A few more details about the setting of the exercise.
The idea is that there is an arena in which a robot is going around. As the robot goes around it learns more about the environment it refines its information regarding where it can and cannot go and what is the cost of going through different areas.

You are asked to implement the classes:

1. Arena – the base class of all the hierarchy.
2. OneCell – an abstract class represnting areas for which not much is known and they are summarized as one area.
3. Cell – an area that is thought to be passable that has a price (in terms, e.g., of energy) that it would cost to pass through.
4. Block – an area that is thought to be not passable.
5. Zone – an area that was refined and contains a greed of areas about which something is known.

The idea would be to start with some zone that has some basic information about the arena (i.e., it contains an array/vector/whatever you want of OneCells). Then, one of these OneCells is refined with more information and becomes a zone with more refined information.
After this process repeats for a while, you get some kind of recursive maze strucure through which the robot can navigate. The most complicated part of this assessment would be to implement checking whether there is a way to cross this maze.

Technically, I have created the header files of all these classes. You have to complete them with additional members, decide where to implement virtual functions, and complete the implementations. You will have to submit ten files: Arena.*pp, OneCell.*pp, Cell.*pp, Block.*pp, and Zone.*pp. Most of the work will be done in Zone. The header files include detailed descriptions of the functions that you are required to implement.

Materials provided:

1. cpp
2. hpp
3. hpp
4. hpp
5. hpp
6. hpp
7. cpp
8. Makefile
9. zip– Just one zip file containing everything

Graph Search Algorithms

Here are a few details about how to search whether there is a path across a graph from some part to some other part. This is required for the implementation of the member existsPath.

This is a pseudo code of a search algorithm in graphs:
bool DFS(set<location> placesToStartFrom,set<location> placesToReach)
stack<location> st;
set<location> visited;

st.push(placesToStartFrom);
while (!st.empty) {
location current = st.pop()

if (visited.find(current)) {
continue;
}

visited.add(current)

if (placesToReach.find(current)) {
return true;
}

foreach (neighbor of current) {
st.add(neighbor)
}
}
return false;
}

So the algorithm starts with the set of locations that you want to start from and the set of states you want to reach. Then, it has a stack of the locations that need handling and the set of locations that have been visited. As long as the stack is not empty there is some chance to reach the target. The search proceeds by taking one element from the stack. If that element has already been visited, then clearly there is no reason to search from it again. Otherwise, mark that element visited and check if it is part of the target set. If it is not in the target set continue searching by adding its neighbors to the stack.
A simple optimization is to check if a location is visited before adding it to the stack and not adding it at all if it was already visited.

For the purposes of this assignment, the location should be replaced by a combination of a location in the zone along with the entry direction to it. Then, in order to determine whether something is a neighbor of current you have to check that it is possible to go inside the current location from the entry direction to the exit direction.

If you want to read more about this you should look up the algorithms for depth first search or breadth first search. The algorithm implemented above is DFS.