CSCE 782: Problem Set 2

Due: Tuesday, 21 September 2004, before class

Upload Problem Set

Figure 1: The new Roomba Discovery from iRobot, a company that boasts professor Rodney A. Brooks as a co-founder and chief technology officer

Roomba Teams

For this problem set you will use NetLogo to build a simplified simulation of your algorithm for getting multiple Roombas to coordinate in the cleaning of a floor. You will need to strictly adhere to the limitations of the physical device (it is very easy to cheat in a simulation), as well as to provide solid evidence that your solution works well.

The Roomba Robots

You simulation will have a slider for chosing among different number of robots, from 1 to 10. Each robot starts life in a randomly chosen location and does not know how many other robots there are or how big the world is (or even that its a square). Like the real Roomba, a robot can only see or clean the dirt that is in its patch. Unlike the real Roomba, your robots will be able to talk to each other but only if both robots are on the same patch. The robots can move at most a distance of 1 during each time click, but they can communicate as much as they want and turn as far as they want.

The robots also have an energy variable which starts at 300 and is reduced by 1 at each click. The only way to re-charge is by going to the patch at 0,0. Once a robot reaches 0,0 it will gain 20 units of energy at each time click, up to 300. There is no limit on the number of robots that can be recharging at one time.

The dirt

Each patch will have a dirt variable that represents the amount of dirt that is located at that patch. The higher the number the more dirt there is. 0 means no dirt. You will want to ask the patches to set their color to reflect their dirt. Dirt will be added to a patch at each tick, the amount will be taken from a poisson distribution with a mean lambda where lambda itself will be chosen from a poisson distribution of mean 5. In other words:

;during setup do
ask patches [set lambda random-poisson 5]

;then at each time click
ask patches [
  set dirt dirt + random-poisson lambda]
The effect of this should be that some patches get dirty faster than others. Notice also that your robot cannot read lambda directly from the patch. When a robot reaches a patch all it can do is clean it up, that is, set dirt 0.


The obvious monitor that you need to have, and by which I will measure the effectiveness of your solution is sum values-from patches [dirt] over time. You should plot this value so we can see how it changes over time.

A secondary measure of cleaniless is a low standard-deviation values-from patches [dirt] as we want the house to be envenly clean. You should also monitor this value.


There are several specific requirements that I want you to focus on.

  1. You should treat this as a negotiation problem. Each robot needs to negotiate with the other robots about what areas to cover. This could be a very haphazard one-on-one negotiation, or you could implement a more systematic method. Remember that the robots do not know initially how many of them there are, or even how big the field is.
  2. You will need to think about how you can justify the quality of your solution. Namely, you will need to compare it with some strawman simple implementation and, if possible, also provide some mathematical analysis to show that your solution will never be too far from the optimal (BTW, I don't know if this is possible?).
  3. The robots should never run out of battery.
  4. Performace should scale near-linearly as more robots are added.

Submission Instructions

This problem set is to be done individually. You cannot ask or receive help from anyone. As will all the problem sets, you will hand them in using our department's dropbox. You will hand in only one file, your .nlogo file. You will use the information tab of the program for writing your detailed explanation of the techniques you used, how the program works, how to set the controls to obtain the different behaviors you want to show, etc. The information tab needs to start with:

email: (I will email your grade and comments to this address)

I understand that it is the responsibility of every member of the Carolina community to uphold an maintain the academic standards and integrity of the University of South Carolina. Any member of the University community, who has reasonable grounds to believe that an infraction of the Code of Student Academic Responsibility has occurred, has an obligation to report the alleged violation.

I certify that I have neither given nor received unauthorized aid on this problem set.

José M. Vidal
Last modified: Sat Sep 4 14:30:46 EDT 2004