CSCE 782: Problem Set 2

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]
      

Monitors

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.

Requirements

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: