Software Design and Implementation
P3: The "Dumba", Maze Explorer
Paired assignment 3 should be completed in class with a partner.
States and Rules, revisited
Once you've developed a Dumba algorithm that completely traverses the empty room, we can try to develop an algorothm for more complex environments. Before we do that, however, it would be helpful to revisit the relationship between rules and states. As you may recall from the Dumba activity, rules determine what the Dumba is going to do by combining its state with the inputs it receives from its environment.
A simple rule that encode the instructions "when the dumba is in state 0 and it finds nothing to west, go west and stay at state 0" is as follows:
0 **x* -> W 0
(Recall that the asterixes (*) are wildcards that essentially express the idea that you do not care what is in these other directions.)
It is very important that you get these rules correct because otherwise, the stupid robot will likely not do as you tell it to do. To help you visualize what these rules are doing, we direct you to a simulator for the Dumba, which is called "Picobot" in their implementation, at http://www.cs.hmc.edu/picobot/. On the page, the simulated environment (the map) is to the left, whereas the space to put rules is to the right. There is a way to scroll through various maps on the arrow keys to the bottom right of the simulated environment. You can also edit these maps by clicking on a cell with your mouse clicking on an empty cell turns it into a wall and clicking on a wall turns it into an empty cell.
Starting with a blank room map, copy your rules to the space to the right and try it; see how your Dumba operates. Does it cover the room using your set of rules regardless of where it starts?
Mazes
Once you see the importance of creating the correct rules, let us look at an environment that is particularly interesting; the maze shown below, which has some important properties.
Notice that in this maze, all the walls are connected to the outer boundary, and all empty cells are adjacent to a wall; in other words, the empty cells are long corridors with turns in them. Any maze with this property can be completely explored with a simple algorithm called the right-hand rule (or the left-hand rule if you prefer). Imagine for a moment that you are in the maze rather than Dumba. In contrast to Dumba, you have a clear sense of the direction you are pointing, and you have two hands. Suppose you start by facing north with your right hand touching the wall. Notice how you can visit every empty cell by simply walking through the maze, making sure that your right hand is always touching the wall. Pause here for a moment to convince yourself that this algorithm works.
Converting the right-hand rule into a set of Dumba rules is an interesting computational challenge. After all, you have a sense of which way you are facing and you have a right hand that was guiding you around the walls, whereas Dumba has neither hands nor a sense of orientation. To program the Dumba the right-hand rule, we will again need to use states to represent information about the Dumba's orientation and which direction its "right hand" is pointing. It may seem that you need an impossibly large number of states to handle a large number of situations, but the number of situations is in fact finite and quite small, which makes it possible to program Dumba for this task.
To get started, it seems pretty natural, for example, to use the four states 0, 1, 2, and 3 to arbitrarily represent Dumba going north, south, eas t, or west; we will call this the direction to which it is pointing. Now, we will need to introduce rules that allow Dumba to behave as if it had a right hand to touch against the wall. Assuming we are in state 0, Dumba's imaginary right hand is then pointing east. There are two out of several conditions to consider:
- If there is a wall to the east and none to the north, the right-hand
rule would tell us to take a step to the north and keep heading north.
Taking a step to the north is no problem because "Keep pointing north" means "stay in state 0." - On the other hand, if Dumba is in state 0 and there is no wall to the east, it should take a step to the east and now think of itself as pointing to the east. "Pointing east" will mean changing to another state that is intended to encode that information (i.e. perhaps state 2?).
(Remember, your program should work regardless of where Dumba starts and for any maze with the property that all walls are connected to the outer boundary and all empty cells are adjacent to a wall.)
Finally, a word of caution: notice also that this algorithm will not visit every cell if (b) some walls are not connected to the outer boundary or (c) if some empty cells are not adjacent to a wall. These two cases are shown in the image below:
Of course, all empty cells must be reachable. If some cells are isolated from others, the problem is just physically impossible.
The instructions
This Paired Assignment has requirements:-
Create a document called yourusername1-yourusername2-p3.docx into which you will enter the following.
-
Develop a set of rules that directs Dumba to cover room that has the special properties outlined above.
You can take the two conditions outlined above, translate them into rules, and then add to them until you have a complete set. Be sure to carefully design your algorithm rather than add rules arbitrarily until it seems to work; debugging can be very difficult! -
Describe any constraints your algorithm has. What happens when the Dumba encounters a large bare room or a room with an "island"? Where should the Dumba start? If the Dumba begins elsewhere, what will happen?
-
Discuss how successful your algorithm is, given the planned starting place for your robot. Do you believe your algorithm will achieve the goal of having Dumba cover the room? If you believe your algorithm will work, explain why you think the room will be covered. If not, explain what you are having trouble getting Dumba to do.
-
Upload the Word document to Moodle once you are done. Remember that the driver submits the file yourusername1-yourusername2-p1.docx, and the navigator just submits the name of his or her partner.
Of course, all files should be shared between partners.
If it is not possible to work together the entire time, then files should be shared when separating and each person should then submit separate files. In your file yourusername.docx, you must fully acknowledge your partner's name and all the thinking and work the other person did when appropriate.
Submitted files with incorrect filenames may not receive full credit because it makes grading more difficult for us and the TAs, so please check filenames carefully!