From: Lucas Kreger-Stickles (lucasks_at_cs.washington.edu)
Date: Mon Oct 20 2003 - 11:01:50 PDT
Lucas Kreger-Stickles
Title/Author
"Evolving Robot Tank Controllers", Jacob Eisenstein
Summary:
Eisenstein discusses the successes and shortcomings of using his
TableREX language and genetic programming to create tank controller
programs for the "RoboCode" environment.
Two Most Important Ideas (and why):
*Encoding has a significant effect on the controllers produced.
Much of the paper is devoted to Eisenstein's encoding scheme,
TableREX. What we learn is that this scheme affects the search in a
number of ways: First, encoding in a way that is interpreted slows
execution, but in Eisenstein's case, decreased overall evaluation time.
This affects search in that it allowed him to explore more generations
of evolution. Second, by selecting a high level encoding Eisenstein
assures that all 'offspring' are at the least legitimate programs.
Also, and perhaps most importantly, Eisenstein's encoding constrains the
search space significantly from the set of programs that can be
expressed with Java, to those that can be expressed as a fixed length
genome of TableREX instructions. In particular, the fixed length of the
genome assures that even if his functions are complete (ie NAND) his
TableREX programs cannot produce all functions or sequences of
functions. Eisenstein addresses many of these short comings throughout
his paper: indicating that targeting may not have evolved because
TableREX was not expressive enough, and that students at California
Polytechnic may not have been so successful because they were compiling
to Java Byte code, which took much longer.
*Evaluation has a significant effect on the controllers produced.
Eisenstein discusses how throughout his process he modified his
evaluation function several times. He discusses how an original
function that measured total points over a series of battles produced
robots that won one big blowout and lost all others. By changing the
evaluation function to value points scored early on more he was able to
generate robots that dodged most others. In addition, Eisenstein
discuses how the nature of his evaluation function made coevolution
impossible, since most robots were better off doing nothing.
These two ideas are the most important since they have the most effect
on out projects. What they demonstrate is that small changes in the
encoding and evaluation have dramatic affects on the robot controllers
produced.
Largest Flaws:
*Tested on his training data:
I consider one of the largest flaw of Eisenstein's paper to be that
he tested the success of his controllers on his training data. By his
own admission, even against the same robot that a controller may have
learned against, changing as little as the starting position lead to a
dramatic reduction in success rates. Thus robust robots were not
created, but rather, specialized solutions (that pretty much were
allowed to cheat since the opponent could not 'learn' the starting
position).
*Didn't address how slowed behaviors might be more likely to be interrupted:
I think it is important to note that since Eisenstein's robots were
being interpreted through file IO they may have been less likely to
develop complex behaviors because their threads may have been
interrupted frequently by the system because they took too long.
Eisenstein never addresses this, though he does concede that even in
pure Java, "very long sequences of of actions are usually a mistake".
Open Questions:
*How could we get Coevolution to work?
This seems like an interesting method that would hopefully produce
more robust robot controllers instead of specialized solutions. How do
we evolve populations that are not 'catatonic'?
*If we don't use genetic programming then what?
What are other possible means of searching for an effective robot
tank controller? Furthermore, how do we define this as a search
problem: what is the goal, a state, legitimate successors, potential
heuristics?
This archive was generated by hypermail 2.1.6 : Mon Oct 20 2003 - 11:01:50 PDT