Grammatical Swarm Evolution

Grammatical swarm is an evolutionary method based on combination of Grammatical Evolution and Particle Swarm Optimization (PSO). In Robocode context it is used to evolve partial or full robot programs. Evolution is realized outside of Robocode and only final robot programs are tested against specified set of robots in the Robocode. Results of testing are used in the evolution process as fitness values.

Inispiration

Works:

• [1] GP-Robocode: Using Genetic Programming to Evolve Robocode Players by Yehonatan Shichel, Eran Ziserman, and Moshe Sipper
• [2] Grammatical Swarm: The generation of programs by social by Michael O`Neill and Anthony Brabazon

Robots:

• geep.mini.GPBotA: MiniRumble ‒ APS: 52.57% (267th), PL: 283-255 (252nd), Survival: 46.05%
• dggp.haiku.gpBot_0: NanoRumble ‒ APS: 50.18% (152nd), PL: 99-131 (146th), Survival: 45.3%

How it works

Steps:

1. PSO - updates particles (based on fitness value) with proper vectors that are used to search in the solution space
2. Grammatical Evolution - transforms particle vectors to full or partial robot programs
3. BNF Grammar - grammar that is specifying possibilities of robot programs generating
4. Output - robot programs
5. Target Function - quality criteria of robots which is calculated in robot tests (e.g. based on score against set of robots) and used to assign fitness values to robots (particles)

http://robocode.hmark.eu/gswarm.png

Regression methods

Behavioral regression

Final program is represented by sequence of orders or statements defined by grammar.

Grammar example:
<!EXP> = <!IFF> | <!LOG>
<!LOG> = <!OPP> | <!VAR> | <!CON>
<!IFF> = ((<!LOG> > <!LOG>) ? (<!EXP>) : (<!EXP>))
<!OPP> = <!LOG> + <!LOG> | <!LOG> - <!LOG> | <!LOG> * <!LOG> | Math.abs(<!LOG>) | Math.cos(Math.PI * <!LOG>) | (-(<!LOG>)) <!VAR> = (Math.random() * 2 - 1) | e.getDistance() / 300.0D | e.getBearingRadians() | e.getHeadingRadians() - getHeadingRadians() | e.getVelocity() / 300.0D | e.getEnergy() / 100.0D | getEnergy() / 100.0D
<!CON> = (- Math.PI / 2) | (-Math.PI / 4) | (Math.PI / 4) | (Math.PI / 2)

Robot example:
turnGunLeftRadians(robocode.util.Utils.normalRelativeAngle(((getY() > ((fireBullet(3)==null) ? 0.0 : 0.0)) ? (((Math.abs(getWidth()) > getGunHeadingRadians()) ? (Math.sin(0.0)) : (getHeadingRadians()))) : (e.getEnergy()))));

Parametric regression

Aimed to generate set of constants that are applied in manually defined programs.

Grammar example:
<!EXP> = goAhead((wallDistance() / 15) * <!CON> + (e.getDistance() / 15) * <!CON>) + northStickSensor() * <!CON>
<!CON> = -1.00 | -0.80 | -0.60 | -0.40 | -0.20 | 0.00 | 0.20 | 0.40 | 0.60 | 0.80 | 1.00

Robot example:
double turnRightRadians = robocode.util.Utils.normalRelativeAngle(goAhead((wallDistance() / 15) * -0.60 + (e.getDistance() / 15) * -0.4) + northStickSensor() * 0.2);

Symbolic regression

Aimed to generate math formulas.

Grammar example:
<!EXP> = 1 / (<!VAL>)
<!VAL> = <!VAL> <!OPP> <!VAL> | <!VAR>
<!OPP> = + | - | * | /
<!VAR> = e.getEnergy() | getEnergy() | e.getDistance()

Robot example:
setFire(enemyEnergy + getEnergy() / getEnergy() * getEnergy() / e.getDistance() + e.getEnergy() - e.getEnergy());

Experiments

hlavko.nano.Phoenix: NanoRumble ‒ APS: 54.06% (130th), PL: 115-115 (128th), Survival: 50.39%

• robot generated with behavioral regression (grammar is similar to GP-Bot grammar)
• using radar locking

hlavko.nano.Ringo 1.0: NanoRumble ‒ APS: 57.36% (94th), PL: 133-97 (100th), Survival: 55.09%

• movement and wall smoothing parameters are generated with parametric regression
• using wall smoothing movement and heads-on targeting

hlavko.nano.Ringo 2.0: NanoRumble ‒ APS: 59.23% (80th), PL: 143-87 (83rd), Survival: 60.25%

• same as hlavko.nano.Ringo 1.0 but added fire formula generated with symbolic regression

hlavko.micro.Flex 1.5: MicroRumble ‒ APS: 75.68% (17th), PL: 338-66 (47th), Survival: 79.89%

• one of the control strategies is generated with parametric regression
• fire formula is same as in the hlavko.nano.Ringo 2.0 (generated by symbolic regression)
• using set of strategies that controls movement and targeting