From: Raphael Hoffmann (raphaelh_at_u.washington.edu)
Date: Fri Oct 17 2003 - 21:06:53 PDT
Summary:
Jacob Eisenstein describes his design of a GA to evolve autonomous robot
tanks in a simulated environment and discusses the results.
Most important ideas:
* The author compared the robocode tank game to the survival of animals in
nature. Thus, he proposed not to develop tank control software based on
intuition and skills, but rather to let "artificial evolution" produce the
fittest robot. He showed that genetic algorithms can be applied to the
Robocode environment and that certain robot strategies become obvious
already after a relatively low number of generations.
* Defining an effective fitness function appears to be a rather challenging
task. Eisenstein experimented with different fitness functions and discussed
the results.
Even though the evolved robots are powerful enough to win against several
opponents, they somehow behave inexpectedly. Their main strategy is dodging,
not shooting. This shows that applying a GA to Robocode is a non-trivial
task and further improvements remain to be done.
Flaws:
* Using a genetic algorithm to directly evolve programs written in TableREX
does not make much sense to me. In other applications of a GA, that I've
seen, the fitness function was somehow continuous in most of the variables
that were encoded. So a minor change in the genetic code usually resulted
only in small changes of the fitness function.
This does not apply to the TableREX encoding. In most cases, changing a
command will produce nonsense. As a consequence, no complex structures, such
as a targeting device, could be developed.
I would try to define the behaviour of the robot not on the level of a
programming language, but on a higher level of conditions and actions, such
as "target gun to last scanned position of enemy", "drive closer to where
enemy was last scanned", "move away, orthogonal to direction of bullets from
enemy". The order of the commands and especially parameters, such as
distances, could be well trained by a GA.
* The way the author describes the development of the GA makes it appear
more or less like the outcome of a trial-and-error approach. I believe the
author should have been more scientifically profound at some design
decisions. For instance, the structure of the TableREX language should have
an essential impact on the quality of the evolved robots.
Finally, it is not clear how powerful the GA really was. The author should
have compared the results to the best random TableREX program generated in
an equal amount of time.
Future Research:
* The genetic encoding of a robot controller has a tremendous effect on the
quality of the GA. Further research on this topic could give answers to
questions, such as "Is it wise to directly encode programming language
commands?", "Should a new behaviour language be created?", "How should such
a language be designed?".
* The author mentions that complex subprograms could be evolved
independently by using different fitness functions for each subprogram (such
as the targeting device). I agree that this strategy could be effective.
Further research could assess the benefits of this approach.
This archive was generated by hypermail 2.1.6 : Fri Oct 17 2003 - 21:07:02 PDT