Software Design and Implementation

---

P1: The "Dumba"

Paired assignment 1 should be completed in class with a partner.

The "Roomba" Problem

It is the humblest of tasks - cleaning up - that has turned out to be the - killer app - for household robots. Imagine yourself as a Roomba vacuum named Dumba: your goal is to suck up the debris from the free space around you - ideally without missing any nooks or crannies. The robotics community calls this the coverage problem: it is the task of ensuring that all the grass is mowed, all the surface receives paint, or all the Martian soil is surveyed.

At first this problem might seem pretty easy. After all, if your parents gave you a vacuum cleaner and told you to vacuum your room without missing a spot, you probably do a pretty great job without even thinking too much about it. Shouldn't it be straightforward to convey your strategy to a robot?

Unfortunately, there are a couple of obstacles that make the job considerably more difficult than yours. First, Dumba has very limited "sight"; it can only sense what's directly around it. Second, Dumba is totally unfamiliar with the environment it is supposed to clean. While you could probably walk around your room blindfolded without crashing into things, Dumba is not so lucky. Third, Dumba has a very limited memory. In fact, it can't even remember which part of the room it has seen and which part it has not.

While these challenges make Dumba's job (and our job of programming it) more difficult, they also make the coverage problem an interesting and non-trivial computer science problem worth serious study.

The environment

Our first task in solving this problem is to represent it in a way that the computer can handle. In other words, we need to define the data we will be working with to solve this problem. For example, how will we represent where the obstacles in the room are? Where the robot is? We could represent the room as a plane, and then list the coordinates of the object's corners and the coordinates of Dumba'ss location. While this representation is reasonable, we will actually use a slightly simpler approach.

Dumba cannot travel onto obstacles (the blue cells which we will also call walls); as we mentioned above, it does not know the positions of those obstacles ahead of time. What it CAN sense is its immediate surroundings: the four cells directly to its north, east, west, or south. We will pick an ordering of these senses as a string of four letters in NEWS order, meaning that we first see what is in our neighboring cell to the North, next to the East, then West, and finally South. If the cell to the north is empty, the letter in the first position is an x. If the cell to the north is occupied, the letter in that first position is an N. The second letter, an x or an E, indicates whether the eastern neighbor is empty or occupied; the third, x or W, is the west; the fourth, x or S, is the south. At its position in the lower-left-hand corner a room, for example, the sensors would report its four-letter surroundings as xxWS. There are sixteen possible surroundings for Dumba, shown below with their textual representations.

State

As we've seen, Dumba can sense its immediate surroundings. This will be important in its decision-making process. For example, if Dumba is in the process of moving north and it senses that the cell to its north is a wall, it should not try to continue moving north!

But how does Dumba know whether it is moving north or some other direction? Dumba doesn't have an innate sense of direction. Instead, we make use of a powerful concept called state. The state of a computer (or a person or almost any other thing) is simply its current condition: on or off, happy or sad, underwater or in outer space, etc. In computer science, we often use "state" to refer to the internal information that describes what a computer is doing.

Dumba's state is extremely simple: it is a single number in the range 0-99. Somewhat surprisingly, it is enough to give Dumba some pretty complex behaviors. Dumba always starts in state 0.

The state of anything can be described with a set of numbers.. but describing human states would take at least trillions of values.

Although Dumba's state is numeric, it is helpful to think of it in English terms. For example, we might think of state 0 as meaning "I am heading north until I can't go any further." However, it's important to note that none of the state numbers has any special built-in meaning; it is up to us to make those decisions. Moreover, Dumba doesn't actually have a sense of which directions it is pointing. But we can define our own conception of which direction Dumba is "pointing" by defining an appropriate set of states.

For example, imagine that Dumba wants to perform the task of continually moving north until it gets to a wall. We might decide that state 3 means "I'm heading north until I can't go any further (and when I get to a wall to my north, then I'll consider what to do next!)." When Dumba gets to a wall, it can to enter a new state such as "I'm heading west until I can't go any further (and when I get to a wall to my west, I'll have to think about what to do then!)." We might choose to call that state 4 or 16; we can pick, as long as the states do not overlap.

Takeaway message: The state is simply a number representing a task that you would like Dumba to undertake.

Think Locally, Act Globally

Now we know how to represent Dumba's surroundings, and how to represent its state. But how do we make Dumba do anything?

Dumba moves by following a set of rules that specify actions and possibly state changes. Which rule Dumba chooses to follow depends on its current state and its current surroundings. Thus, Dumba's complete "thought process" is as follows:

• I take stock of my current state and immediate surroundings.
• Based on that information, I find a rule that tells me both a direction to move and the state I want to be in next.

Dumba uses a five-part rule to express this thought process.

• The first rule, 0 xxWx -> E 1
  re-expressed in English, says "If I'm in state 0 and only my western neighbor contains an obstacle, take one step east and change into state 1."
• The second rule,
  0 xxxx -> W 0
  says "If I'm in state 0 with no obstacles around me, move one step west and stay in state 0.

At each step, Dumba examines the list of rules, looking for the one rule that applies. A rule applies if the state part of the rule matches Dumba's current state and the surroundings part of the rule matches the current surroundings. What happens if there are NO rules that match its current state and surroundings? The robot will stop running. Taken together, these two rules use local information to direct Dumba across an open area westward to a boundary.

Just as state 0 represents the "go west" task, we can specify two rules that will make state 1 be the "go east" task:

• 1 xxxx -> E 1
• 1 xExx -> W 0

These rules transition back to state 0, creating an infinite loop back and forth across an open row, as shown in the following image:

By the way, sometimes you might not want Dumba to move as the result of applying a rule. Rather than specifying a move direction ("E", "W", "N", or "S"), you may use the upper-case letter "X" to indicate "stay where you are". For example, the rule

0 Nxxx -> X 1

is saying "if I'm in state 0 and there is a wall to the north, don't move but enter state 1."

Algorithims and Rules

So far we've looked at how to write rules that make Dumba move. But in trying to solve problems with Dumba, it's usually helpful to take a more global view of how Dumba is accomplishing its task, and then to translate that approach into rules. In other words, we want to develop an algorithm that allows Dumba to accomplish the desired task, where that task is usually to cover the entire room. In the previous section, Dumba had the more modest goal of simply moving back and forth in an empty room. The algorithm for accomplishing this task is the following:

• Move west until Dumba hits a wall to the west
• Then move east until Dumba hits a wall to the east
• Then go back to step 1

Now the question becomes: how do we translate this algorithm into the rules from the previous section:

0 **x* -> W 0

0 **W* -> E 1

1 *x** -> E 1

1 *E** -> W 0

As written, it is difficult to see the connection between the steps of the algorithm and the Dumba rules. We can see that Dumba will need two states to keep track of which direction it is moving (i.e., is it in step 1 or step 2?), but it's still not exactly clear how the algorithm translates into precise rules. Essentially, each of Dumba's rules applies in an "if-then" fashion. In other words, if Dumba is in a particular state and sees a particular environment, then it takes a certain action and potentially enters a new state. With some minor modifications, we can rewrite the algorithm above to follow Dumba's "if-then" rule structure more directly:

Repeat the following steps forever:

• If Dumba is moving west and there is no wall to the west, then keep moving \ west.
• If Dumba is moving west and there is a wall to the west, then start moving \ east.
• If Dumba is moving east and there is no wall to the east, then keep moving \ east.
• If Dumba is moving east and there is a wall to the east, then start moving \ west.

Now we can see more clearly the direct translation between the steps of this algorithm and the Dumba rules: each step in the algorithm translates directly into a rule in Dumba, where state 0 represents "Dumba is moving West" and state 1 represents "Dumba is moving East". Formulating algorithms in this way is the key to writing successful programs in Dumba.

---

The instructions

This Paired Assignment has several steps:

1. Create a document called yourusername1-yourusername2-p1.docx into which you will enter the following.

2. Develop a set of rules that direct Dumba to cover an empty rectangular room. This set of rules should regardless of the size of the room or where the robot starts.

   You might start by altering the rules above so that they side-step into a neighboring row after clearing the current one that Dumba traversed. However, once you have an idea for how you might solve the problem, plan your algorithm, and then express that algorithm into a set of Dumba rules.

3. Next describe any constraints of your algorithm.  Does the Dumba need to begin in a particular place in the room?  Where should the Dumba start? If the Dumba begins elsewhere, what will happen?

4. Next discuss your level of success 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.

5. Next, discuss about how well your algorithm will function if there is an obstacle in the room.  Will it still work? If not, what will happen? Does it matter where the obstacle is, like against a wall or out in the open. Explain.

6. Upload the Word document to Moodle once you are done. In the case of algorithm development like this, the "driver" is the one who is typing, and the "navigator" is the other partner.  For all pair work, partners should work together for the entire time if at all possible. Then the driver submits the file yourusername1-yourusername2-p1.docx, 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, (file yourusername1.docx,  and file yourusername2-p1.docx, each fully acknowledging the thinking and work of the other partner by name and what was accomplished.

Note that 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!

Note that this assignment was adapted from "http://www.cs.hmc.edu/csforall/Introduction/Introduction.html#picobot".