WHAT IS IT?
-----------
This project demonstrates a variety of different search
algorithms, by forcing them to compete with one another in a
well-defined search-space. Each algorithm is implemented by
a different team, consisting of robots. Every robot on a
given team executes that team's search technique; the goal
being to collect the most energy pods (represented by a
white patch).
The robot teams presented here use three elementary search
procedures: depth-first search, breadth-first search, and
the random walk. However, it shouldn't be too difficult to
engineer your own algorithm that does at least as well as,
if not better than, the other robot teams. 'robots' provides
a nice framework for building your own procedure.
Each of the three search algorithms presented here are
easy to understand if you think of them as trying to
solve a maze. The depth-first search picks one particular
path and continues down it until it reaches a dead-end. It
then back-tracks to the next path it hasn't explored, and
follows it to the end, and so on until it finds the exit.
Breadth-first search takes the opposite approach, moving
one step forward in each direction and looking for the exit.
If it doesn't find it, it takes a second step forward in
each direction, and so on, slowly spiraling outwards.
The random-walk approach eschews any procedure whatsoever,
and blindly moves about. If it finds the exit, terrific- if
not, it just keeps moving randomly.
HOW TO USE IT
-------------
The PODS slider determines how many energy pods will be
scattered randomly across the screen. (You will see that,
during run-time, the value of the PODS slider decreases as
robots find the pods. As StarLogo checks the value of the
slider each time-step to see if all pods have been
collected, it is best not to change the value of the slider
while the model is running.)
The ROBOTS slider controls how many robots are on each team.
After you set both PODS and ROBOTS to the desired values,
press the SETUP button to initialize the search-space. When
you are ready to begin, press the GO button.
There are four pre-defined teams of robots, 'depth-firsts',
'breadth-firsts', 'random-walks', and 'your-bots'. Their
corresponding colors are red, blue, green, and yellow. The
robots will begin executing their commands, stamping the
patch they are on to indicate they have checked it, and the
model will run until all pods have been found. Once this
occurs, you will be alerted with a system beep. Check the
output window for a listing of each team's overall score;
obviously, the team that collected the most pods wins the
search game.
THINGS TO NOTICE
----------------
Run the model a few times at the same settings. (Remember,
you will have to reset the PODS slider at the start of each
run.) Notice how each team ranks- what search algorithm
performs the best for this type of world?
Watch how each type of robot moves (i.e. how it searches the
world). Breadth-first search methodically searches
everything within a radius of 1, then every square with a
radius of 2, etc... Depth-first search goes in the opposite
extreme, pursuing one particular path until it reaches a
dead-end, after which it attempts to find a new route.
Random walks simply move randomly about. What are the
advantages of each type of search?
What are the advantages and disadvantages of each kind of
search? Which algorithm, if any, performs the best? Which
algorithm does the worst? What does breadth-first gain by
its methodological approach, considering every square it
runs into? What do the depth-firsts and the random-walks
gain with their random elements?
THINGS TO TRY
-------------
A good demonstration of each type of search technique can be
given if ROBOTS is only set to 1. Or, you can temporarily
get rid of a team by commenting out the appropriate code in
the procedures window- put a semicolon (;) in front of the
call to 'make-' in the 'setup' procedure, and a
semicolon in front of 'move-' inside of 'go'. How
could these robots perform better? What advantage is gained
by working as a team (as the depth-firsts do, by checking
the patch color) as opposed to working in isolation (as the
breadth-firsts will do)?
One of the robot teams is called 'your-bots'. Unfortunately,
the members of 'your-bots' perform very badly, only going
straight-forward each time step. See if you can program them
to be more successful. You only need to change their name
and shape, and give them a different body of code to
execute. Try the following:
ask-your-bots
[stamp (color + 4)
fd 1
if ((pc-at 0 0) > white)
[setxy (random screen-size) (random screen-size)]]
Notice how this search algorithm performs compared to the
others.
EXTENDING THE MODEL
-------------------
You can also create additional teams to compete against the
existing ones. The procedure for adding a new 'breed' of
robot is as follows:
-Create a New Breed: ''
-Create a New Global Variable: '-score'
-Under 'setup', add a new line: 'make-', and
make the corresponding procedure, following the format
of the other robot teams:
to make-depth-firsts
create-depth-firsts robots
ask-depth-firsts
[setc red
setshape depth-first-shape
seth ((random 4) * 90)
setxy (random screen-size)
(random screen-size)]
end
-Under 'go', add a new line: 'move-', and
make the corresponding procedure, following the general
format of the other robot teams:
to move-depth-firsts
ask-depth-firsts
[stamp (color + 4)
fd 1
if ((pc-at 0 0) > white)
[ifelse ((random 2) = 0)
[rt 90
fd 1
lt 90]
[lt 90
fd 1
rt 90]]]
end
-Add three lines in the procedure
'closing-ceremony', following the format of the other
robot teams:
setdepth-firsts-score
sum-of-depth-firsts [team-points]
type "|Depth-Firsts Scored: |
print depth-firsts-score
-Finally, you can make a monitor, to watch the progress
of your team. In the interface window, create a monitor
called -score. Then go to the bottom of the
procedures window, and create a short procedure for the
monitor, in the format of the others:
to red-score
output (sum-of-depth-firsts [team-points])
end
There are three nameless turtle-variables for you to use
(although you can create more, or rename them if it suits
your needs.)
'robots' is a great project with which to explore genetic
algorithms. (See the Connected Mathematics project 'genetic
mouse' for a good explanation and simulation of genetic
algorithms.) Try to build a team of robots who attempt to
evolve a better search strategy, by each having differences
in their technique, differences which only get to be passed
on to future generations of robots if that robot is
successful, i.e. it can find the pods.
The comma command (,) appears in a few places. This command
corrects a problem that might arise with synchronicity-
turtles acting out of turn. It essentially tells a turtle
who reaches it to wait until all other turtles have reached
it before proceeding. But what would happen if you were to
take it out? A team whose algorithm is very short might (in
the long run, and with many turtles acting on the screen at
once) gain an advantage, time-wise, over turtles who need to
exectue a lot of code. Experiment with timing and
synchronization in StarLogo- what do you notice?
STARLOGO FEATURES
-----------------
'robots' was designed with StarLogoT1, and utilizes
some of that version's new features. Notice that, when all
pods have been collected, StarLogo alerts you with a beep.
In the procedure 'update-world', we have the simple observer
command 'beep', which does exactly what you'd expect.
Also watch the PODS slider during the run of the project-
it decrements each time a robot collects a pod. This is due
to the observer primitive 'setpods', which allows you to
set a specified slider-variable to any value within its
limits.
In order to generate a number of randomly-placed pods equal
to the PODS slider, we have a procedure 'create-pods', and
an auxilliary procedure 'find-unique-patch'. Instead
of picking random patches and setting their values, we have
turtles move randomly about, until each turtle is alone in
its patch. Each turtle then sets the patches as pods.
We do this through recursive calls to the
'find-unique-patch', and we guarantee that there really will
be PODS number of energy pods. (If we just pick random
patches, there is a slight chance that the same patch will
be picked twice.)