John Muir Ant Eval

john-muir-ant-eval

Forced Evolution in Silico by Artificial Transposons and their Genetic Operators: The John Muir Ant Problem — Spirov et al. (2009) (arXiv:0910.5542, 2009)

What this evaluates

Evaluates the ability of a genetic algorithm to evolve a navigation program for an artificial ant to traverse a complex, toroidal grid trail with gaps and high-difficulty sections. The benchmark measures how well the evolved program generalizes beyond the standard Santa Fe trail into a chaotic extended sector.

Datasets

• John Muir Ant Problem — total 89; splits: test (89)

Metrics

• score (primary) — range: [0, 89]
  • Number of food items collected by the ant while traversing the trail within a maximum of 330 time steps. A score of 64 is considered effective.

Input / output format

Input: A 32x32 toroidal grid with a predefined 89-step trail containing food items and gaps. The ant's program receives sensor inputs (e.g., food ahead, empty ahead, left, right) and outputs actions (move forward, turn left, turn right).

Output: A sequence of actions (program) executed by the ant for up to 330 steps on the trail.

Scoring recipe

def evaluate_ant_program(program, trail, max_steps=330):
    ant_pos = 0
    score = 0
    for step in range(max_steps):
        if ant_pos >= len(trail): break
        sensor = get_sensors(trail, ant_pos)
        action = program.run(sensor)
        ant_pos = move(ant_pos, action, trail)
        if trail[ant_pos] == FOOD: score += 1
    return score

Common pitfalls

• The trail extends beyond the standard Santa Fe trail (first 64 steps) into a chaotic high-difficulty sector, requiring generalization beyond simple trail following.
• The evaluation uses a fixed maximum of 330 time steps; exceeding this limit stops the run regardless of progress.
• Score is averaged over 100 independent runs to account for stochasticity in the genetic algorithm.

Evidence (verbatim from paper)

The test trail used in this work is illustrated in Fig. 4. It can be seen that up to the 64th element our trail coincides with the Santa Fe trail, but afterwards includes chaotically scattered elements of high difficulty. ... Everywhere in this section we will accept that an effective navigation algorithm should exceed a score of 64 in 330 time steps. ... The score values are averaged over 100 runs in both cases.

Citation

@misc{spirov2009forced,
  title={Forced Evolution in Silico by Artificial Transposons and their Genetic Operators: The John Muir Ant Problem},
  author={Spirov et al. (2009)},
  year={2009},
  note={arXiv:0910.5542}
}

• arXiv: 0910.5542