From: Patrick Haluptzok (patrickh_at_windows.microsoft.com)
Date: Fri Oct 17 2003 - 14:16:24 PDT
<<Paper Review - Robot Tank Controllers.doc>>
----------- Here is the paper contents -------------------
Paper Review - by Patrick Haluptzok - Oct 17 2003
Paper Reviewed: Evolving Robot Tank Controllers
Author: Jacob Eisenstien
Summary: Describes a method for using a GA to evolve a program that
controls the operation of a tank in a virtual world where it competes
against other tank agents.
Important Points:
* A GA could evolve an autonomous agent controller for a robot
that performed modestly well compared to simple handcrafted robot
controllers. The GA program was evolved using a constrained programming
language and breaking up the control of the robot into multiple pieces
which simplified the search space for the GA. Showing GA's successfully
evolving a robot controller demonstrates GA's evolving a solution to a
non-trivial problem, something GA's are not known to do very well.
* The fitness function was very important in making the GA
succeed. Using subtly different fitness functions greatly affected the
resulting behavior in the population that evolved. The success of the
GA process depended critically on the fitness function which guides the
GA's selection of robots for the next generation.
Flaws in Paper:
* Not realizing the GA population was getting stuck in local
maxima and addressing that directly in some way, at least as a direction
for future research. GA's are local search methods so they can get
stuck in local maxima, failing to improve and find more fit solutions.
The co-evolution approach resulted in robots that all sat in one
position because that was a local maximum, moving initially was more
likely to hurt than help. Evolving to move and even just ram your
sitting duck opponent would be more successful. Even in his more
successful experiment evolving his controller and measuring it against
other handcrafted robot programs the evolved robots only began to evade
other robots and didn't evolve to shoot their gun. In both cases the GA
became stuck in a local maxima and the number of random changes that
needed to occur to get out of that local maxima to another space in the
fitness landscape was so unlikely as to never occur. If GA's are to be
more successful then extensions to the GA approach are needed to prevent
the population from getting stuck in local maxima, and this is a major
problem.
Open research questions:
* Could using a different fitness function, changing the fitness
function over time, or changing the fitness function to strongly
encourage firing evolve a more successful tank controller? For example
could you constrain the tank to not be able to move and just evolve its
gun and radar movement and firing response first, and then allow it to
evolve moving. Would that lead to a higher fitness level? This is
important because GA's may need sophisticated and changing fitness
functions to evolve more successful programs and prevent the evolution
from getting stuck in local maxima.
* Could some of the advanced GA concepts such as multiple niches
be used to cause the GA to evolve more optimal controllers, preventing
the population from getting stuck in local maxima? Maybe with a fixed
fitness function a more sophisticated GA is required to allow
exploration of new places in the search space. Do GA's need to build in
mechanisms to prevent the population from converging at a local maxima?
* Would a different representation / programming language allow
the GA to more successfully find higher fitness robot controllers? Is
the representation chosen constraining or flawed in some way?
This archive was generated by hypermail 2.1.6 : Fri Oct 17 2003 - 14:16:31 PDT