CIS480 Final Exam Study Notes

{Some sample answers}

1. Mission (Im)Possible:

Although there are several different ways to attack the kidnapped robot problem most (if not all) rely on asymmetry.  Conversely, in the mission impossible cases the problem cannot be solved due to symmetry.  Thus, the key to finding a solution is locating an asymmetry.  The simplest example of asymmetry is the scalene triangle.  For example, in the graphical representation below (I),  the shortest path from node c3 to node d6 is 4; from d6 to f6 is 2; and from f6 to c3 is 6.  Thus, we have a scalene triangle, though not necessarily in the strict metrical sense.  This asymmetrical relationship among them allows us to uniquely identify each of the 3 nodes.  And, if we already have a map containing those 3 points, we can locate any point in the environment, regardless of any underlying symmetry that the environment itself has.

I

This, in turn, allows us to produce an algorithm for solving the kidnapped robot problem.

2. Kidnapped Robot Algorithm

Again, there are various approaches one can use.  And especially there are many ways that we can take advantage of properties of the environment itself.  For example, in the environment (I) shown above we can systematically travel up and down the rows until we encounter one of the markers.  But that same algorithm would not work in other environments, such as North Campus.  Here is one that will work in any mappable environment.

          A. Starting at the current location, use the mapping algorithm to begin producing a

completely new map of the environment.

B. Continue this process until all 3 markers (or uniquely identifiable points) have

been encountered.  Identify these points on the previously made map.

C. When this occurs, the robot will be located at the 3^rd of these points.  So we know,

with respect to the original map, where the robot is located.  And we can also

calculate where the robot was “dropped off.”

3. Making (Im)Possible Determination

Are there 3 identifiable locations which can be used to form a scalene triangle?  Is this triangle unique?  If so, then we have an instance of Mission Possible.  If not, can we find

J

another way to uniquely identify a small set of nodes?  If there is none, then we have Mission Impossible.

What other ways are there to uniquely identify a set of nodes?  If we have one and only one triangle that is “scalene” with respect to the properties of the nodes, this forms a uniquely identifiable node set, even if the triangle is not scalene with respect to distance between nodes.  Thus, the nodes 12-7-6 in the North Campus map (J) form such a triangle with their neighbor numbers being 5, 7 & 4; and their distances being 1-1-2.  This is the case even though there are other nodes with 4 and 5 neighbors.

What about the nodes 9-8-7 which also have neighbor numbers 5, 7 & 4?  First, they do not threaten the uniqueness of the 12-7-6 triad, since their distances are 1-1-1.  Second, they cannot be used as a uniquely identifiable node set because they are not unique.  The nodes 12-7-13 are a matching set.

E

Exercise: What about the robot world shown in E above? 

Answer: Mission Possible, because 8-6-12 form a unique triangle with neighbor sets 5-4-2 and distances 2-1-2.

4. Placement of Markers

Once again, there is more than one approach.  One that is fairly direct to understand and implement is this:

Form a scalene triangle, and

Minimize the moves made before the markers are encountered

Although, there are questions of efficiency that can be explored, with respect to the upcoming exam, the approach given above will do.