Double pole balancing without velocities
The problem
The double pole again, two poles side by side on a cart, with the same system and settings, but the controller sees only three of the six state variables: the cart's position and the two poles' angles. Without the velocities, it can't tell a pole that is passing through the vertical from one at rest there; it has to infer them from what it saw before, so it needs memory. Gruau, Whitley and Pyeatt (1996) introduced this version as the hardest of the pole balancing tasks, and it remains the standard test of neuroevolution of recurrent networks (Stanley and Miikkulainen 2002; Igel 2003; Gomez et al. 2008).
| Setting | Value |
|---|---|
| Cart, poles, friction, force | as the double pole's: 1 kg; 1 m and 0.1 kg, 0.1 m and 0.01 kg; up to 10 N every 0.02 s |
| Observed | the cart's position and both poles' angles, scaled to about [−1, 1] |
| Start | the long pole at 4° from vertical, the rest 0 |
| Failure | either pole beyond 36°, or the cart beyond ±2.4 m |
| Fitness | Gruau et al.'s damping fitness over 1000 steps |
| Success | 100,000 steps from the start, and 1000 steps from at least 200 of 625 other starts |
Gruau et al. made two further changes to rule out controllers that keep the poles up by jiggling the cart back and forth, which needs no velocities:
- The damping fitness,
0.1 f₁ + 0.9 f₂over an episode of 1000 steps:f₁ = t / 1000for thetsteps the poles stayed up, andf₂ = 0.75 / Σ (|x| + |ẋ| + |θ₁| + |θ̇₁|)over the last 100 of them (0 ift < 100), which rewards bringing the cart and the long pole to rest. - The generalization test: a network that balances the poles for 100,000 steps must also balance them for 1000 steps from at least 200 of 625 starts, which give the cart's position and velocity and the long pole's angle and angular velocity each of 5 values across ±2.16 m, ±1.35 m/s, ±3.6° and ±8.6°/s (Igel 2003 gives the values).
The task is genoxide::problems::control::DoublePole::without_velocities(), with
damping_fitness, generalization and solved, integrated as the double pole by fourth-order
Runge-Kutta with portable sin and cos, the same bits on every platform.
The Python version runs the task, the network and the damping fitness in Rust
(gx.problems.control.DoublePole(velocities=False), gx.nn.Elman, Balance(...,
fitness="damping")), and NEAT with gx.Neat, its recurrent networks' policies run in Rust
too: it prints the same output and writes the same trace.
What makes it hard
The controller must estimate velocities from positions, and the fitness sees only 1000 steps (20 s) while success takes 100,000 and a test from 625 other starts that the search never sees. A search can climb the damping fitness to networks that hold the poles for 1000 steps, calmly, and fail soon after, or that balance from the one start but from no other. Igel (2003) found that CMA-ES does exactly that: it converges on such a network, its step size shrinks, and nothing in the fitness pulls it towards networks that generalize.
Representation
An Elman network (nn::Elman, Elman 1990, Finding structure in time, Cognitive Science 14(2):
179-211): 3 inputs, 3 hidden tanh units, each receiving the inputs and the three hidden outputs of
the previous step, and a tanh output, the force in units of 10 N. Without biases, as for the
double pole, it has 3 × (3 + 3) + 3 = 21 weights, a Real genome in [−1, 1] each. The context
starts at 0 in every episode.
Algorithm
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195) with its default
population, 4 + ⌊3 ln 21⌋ = 13, and initial step size, 0.3 of each gene's range, maximizing the
damping fitness, with IPOP restarts. As Igel (2003) did against the convergence above, its step
size is bounded below (CmaesBuilder::min_step), at 0.05 of each gene's range, a sixth of the
initial one: the search keeps exploring around the networks that balance for 1000 steps until one
passes the tests.
After each generation, the generation's best network, if it balanced the 1000 steps, runs the tests: 100,000 steps from the start, and the 625 starts of the generalization test. The run stops when one passes both, or after 100,000 evaluations; the tests aren't counted as evaluations, as in the papers.
Then NEAT (neat::Neat, Stanley and Miikkulainen 2002) solves the same task, evolving recurrent
networks (.feed_forward(false), evaluated by Network::recurrent, one step of time per control
step) with the paper's settings for it: 1000 networks that start from the 3 inputs and a bias
connected to the output, a compatibility coefficient c₃ of 3 and threshold of 4, and new
connections with probability 0.3. Its output, the paper's steepened sigmoid in (0, 1), is the force
as 2 × output − 1. It maximizes the same damping fitness, with the same tests, up to 400,000
evaluations. The XOR by NEAT page describes the method.
Output
The first line gives the evaluations and generations until a network passed the tests, the second how many of the 625 starts it balanced, the third its damping fitness. The fourth gives how far the cart and the two poles went from the middle and the vertical over the 100,000 steps, and the fifth the network's weights. The last three lines are NEAT's: the evaluations and generations until its network passed the tests, how many of the 625 starts it balanced, and the network's hidden nodes and enabled connections.
The project page plays this run back.
Good results
The goal is the task's success criteria. The run of output.txt meets them after 1,677
evaluations, in 128 generations; its network balances from 201 of the 625 starts.
Over seeds 1 to 100, all 100 runs solved the task, after 3,043 evaluations on average (a median of 2,405, at most 9,698), their networks balancing from 247 of the 625 starts on average. Without the bound on the step size, 10 of 20 runs I tried solved it within 30,000 evaluations: of the others, 5 converged on networks that balance for the 100,000 steps but fail the generalization test, and 5 on networks that balance for 1,166 to 4,978 steps.
Gomez et al. (2008, table 4) list the average evaluations to solve this task with the damping
fitness: 3,416 for CoSyNE, 6,061 for CMA-ES (from Igel 2003, a recurrent network of 3 hidden units,
its step size bounded at half the initial one), 6,929 for NEAT (with populations of 16), 26,342 for
ESP, 87,623 for CNE, 451,612 for SANE, 840,000 for cellular encoding (Gruau et al.'s single run) and
1,232,296 for random weight guessing. Stanley and Miikkulainen (2002) report 33,184 for NEAT with
populations of 1000, and generalization scores of 286 for NEAT, 289 for ESP and 300 for cellular
encoding; Igel reports 250 for CMA-ES. The setups differ in the network (Igel's is fully recurrent,
its output fed back too), the start (Igel started the long pole at 4.5°) and the sum of the damping
fitness (Stanley and Miikkulainen and Gomez et al. print a sum from t − 100 to t, 101 steps;
here, as in Igel, 100).
NEAT's run of output.txt meets the criteria after 33,488 evaluations, in 33 generations, with a
network of 4 hidden nodes and 18 enabled connections balancing from 212 of the 625 starts. Over seeds
1 to 20, 17 runs solved it within 400,000 evaluations, after 92,115 evaluations on average (a
median of 77,282), their networks balancing from 273 of the 625 starts on average; the
other 3 hadn't. That is slower than Stanley and Miikkulainen's 33,184, in a setup that differs as
described above.
Known optimum: Balanced for 100,000 steps, and for 1000 steps from at least 200 of 625 other starts (Gruau et al.'s success criteria)
Source: examples/double_pole_no_velocities
Interactive run: tachsin.gr/projects/genoxide/examples/double-pole-no-velocities
cargo run --release --example double_pole_no_velocities
//! Double pole balancing without velocities: evolve the weights of a recurrent neural network that
//! balances two poles on a cart seeing only their angles and the cart's position, by CMA-ES.
//!
//! Wieland's (1991) double pole, with Florian's (2007) corrected equations and Gomez, Schmidhuber
//! and Miikkulainen's (2008) settings, made non-Markovian by Gruau, Whitley and Pyeatt (1996): the
//! network doesn't see the velocities, and has to infer them from what it saw before. It is an
//! Elman network: 3 inputs, 3 hidden tanh units that also receive their own previous outputs, and a
//! tanh output, without biases, 21 weights. The fitness is Gruau et al.'s damping fitness over 1000
//! steps, maximized by CMA-ES with its step size bounded below, as Igel (2003) did. The task is
//! solved, by Gruau et al.'s criteria, when the best network of a generation balances the poles
//! for 100,000 steps and, from 625 other starts, for 1000 steps from at least 200.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example double_pole_no_velocities
//! ```
mod trace;
use genoxide::neat::{Neat, Network, Recurrent};
use genoxide::nn::{Activation, Elman};
use genoxide::prelude::*;
use genoxide::problems::control::{DoublePole, GENERALIZATION_THRESHOLD, Policy, SUCCESS_STEPS};
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
// 3 inputs, 3 hidden units with a context, 1 output, without biases
pub fn network() -> Result<Elman> {
let elman = Elman::new(3, 3, 1, Activation::Tanh)?;
Ok(elman.output_activation(Activation::Tanh).bias(false))
}
// a network that solved the task: its weights, and the starts of the generalization test it passed
struct Solution {
weights: Reals,
generalization: u32,
evaluations: u64,
generation: u64,
}
// the largest |x|, |θ₁| and |θ₂| (in degrees) over an episode of `steps` steps
fn extent(task: &DoublePole, network: &Elman, weights: &[f64], steps: u32) -> Result<[f64; 3]> {
let mut policy = network.with(weights)?;
let mut task = *task;
let (mut observation, mut action) = ([0.0; 3], [0.0]);
let mut largest = [0.0_f64; 3];
for _ in 0..steps {
task.observe(&mut observation);
policy.forward(&observation, &mut action);
task.step(action[0]);
let [x, _, theta_1, _, theta_2, _] = task.state();
let values = [
x.abs(),
theta_1.abs().to_degrees(),
theta_2.abs().to_degrees(),
];
for (largest, value) in largest.iter_mut().zip(values) {
*largest = largest.max(value);
}
}
Ok(largest)
}
fn main() -> Result<()> {
let elman = network()?;
let task = DoublePole::without_velocities();
// Gruau et al.'s damping fitness over 1000 steps
let damping = |weights: &Reals| -> Option<f64> {
let mut policy = elman.with(weights).ok()?;
Some(task.damping_fitness(&mut policy))
};
let cmaes = Cmaes::builder(elman.representation(-1.0..=1.0)?)
.min_step(0.05)
.restarts(cmaes::Restarts::Ipop)
.maximize()
.seed(1)
.build()?;
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env(&elman, &task);
let solved = Arc::new(AtomicBool::new(false));
let stop = Arc::clone(&solved);
let mut solution = None;
let outcome = Engine::new(cmaes, damping)
.stop_when(Stop::custom(move |_| stop.load(Ordering::Relaxed)))
.stop_when(Stop::evaluations(100_000))
.on_generation(|snapshot| trace.record(snapshot))
// the tests of the generation's best network, if it balanced the 1000 steps (then its
// fitness is at least 0.1)
.on_generation(|snapshot| {
let best = snapshot.population().best(Objective::Maximize);
let score = |best: &&Individual<Reals>| best.fitness().and_then(Fitness::score);
let Some(best) = best.filter(|best| score(best) >= Some(0.1)) else {
return;
};
let mut policy = elman.with(best.genome()).expect("the network's weights");
if task.run(&mut policy, SUCCESS_STEPS) < SUCCESS_STEPS {
return;
}
let generalization = task.generalization(&mut policy);
if generalization >= GENERALIZATION_THRESHOLD {
let progress = snapshot.progress();
solution = Some(Solution {
weights: best.genome().clone(),
generalization,
evaluations: progress.evaluations(),
generation: progress.generation(),
});
solved.store(true, Ordering::Relaxed);
}
})
.run()?;
let Some(solution) = solution else {
println!("not solved after {} evaluations", outcome.evaluations());
return Ok(());
};
println!(
"solved after {} evaluations in {} generations",
solution.evaluations, solution.generation
);
println!(
"balanced for {SUCCESS_STEPS} steps from the start, and for 1000 steps from {} of the 625 \
generalization starts (at least {GENERALIZATION_THRESHOLD} needed)",
solution.generalization
);
let weights = &solution.weights;
let mut policy = elman.with(weights)?;
println!("damping fitness {:.6}", task.damping_fitness(&mut policy));
let [position, long, short] = extent(&task, &elman, weights, SUCCESS_STEPS)?;
println!(
"over the 100000 steps: the cart within {position:.4} m, the poles within {long:.4}° and \
{short:.4}°"
);
let rounded: Vec<String> = weights.iter().map(|w| format!("{w:.3}")).collect();
println!("weights: [{}]", rounded.join(", "));
trace.write(weights);
neat(&task)?;
Ok(())
}
// a recurrent NEAT network as a controller: its output, in (0, 1), is the force as
// 2 × output − 1, and its state is cleared at the start of each episode
struct Controller(Recurrent);
impl Policy for Controller {
fn act(&mut self, observation: &[f64], action: &mut [f64]) {
let mut output = [0.0];
self.0.activate(observation, &mut output);
action[0] = 2.0 * output[0] - 1.0;
}
fn reset(&mut self) {
self.0.reset();
}
}
// the same task by NEAT, with the paper's settings for it: 1000 recurrent networks that grow from
// the three inputs and a bias connected to the output, c3 = 3 and a threshold of 4, and new
// connections with probability 0.3; the damping fitness, and the same success criteria
fn neat(task: &DoublePole) -> Result<()> {
let damping = |network: &Network| -> Option<f64> {
let mut policy = Controller(network.recurrent().ok()?);
Some(task.damping_fitness(&mut policy))
};
let neat = Neat::builder(3, 1)
.population_size(1000)
.compatibility(1.0, 1.0, 3.0, 4.0)
.structural_mutation(0.03, 0.3)
.feed_forward(false)
.seed(1)
.build()?;
let solved = Arc::new(AtomicBool::new(false));
let stop = Arc::clone(&solved);
let mut solution = None;
let outcome = Engine::new(neat, damping)
.stop_when(Stop::custom(move |_| stop.load(Ordering::Relaxed)))
.stop_when(Stop::evaluations(400_000))
// the tests of the generation's best network, if it balanced the 1000 steps
.on_generation(|snapshot| {
let best = snapshot.population().best(Objective::Maximize);
let score = |best: &&Individual<Network>| best.fitness().and_then(Fitness::score);
let Some(best) = best.filter(|best| score(best) >= Some(0.1)) else {
return;
};
let mut policy = Controller(best.genome().recurrent().expect("the network's nodes"));
if task.run(&mut policy, SUCCESS_STEPS) < SUCCESS_STEPS {
return;
}
let generalization = task.generalization(&mut policy);
if generalization >= GENERALIZATION_THRESHOLD {
let progress = snapshot.progress();
solution = Some((
best.genome().clone(),
generalization,
progress.evaluations(),
progress.generation(),
));
solved.store(true, Ordering::Relaxed);
}
})
.run()?;
let Some((network, generalization, evaluations, generation)) = solution else {
println!(
"\nNEAT: not solved after {} evaluations",
outcome.evaluations()
);
return Ok(());
};
println!("\nNEAT: solved after {evaluations} evaluations in {generation} generations");
println!(
"balanced for {SUCCESS_STEPS} steps from the start, and for 1000 steps from \
{generalization} of the 625 generalization starts"
);
println!(
"the network: {} hidden nodes, {} enabled connections",
network.hidden(),
network.enabled()
);
Ok(())
}
python examples/double_pole_no_velocities/main.py
"""Double pole balancing without velocities: evolve the weights of a recurrent neural network that
balances two poles on a cart seeing only their angles and the cart's position, by CMA-ES.
Wieland's (1991) double pole, with Florian's (2007) corrected equations and Gomez, Schmidhuber and
Miikkulainen's (2008) settings, made non-Markovian by Gruau, Whitley and Pyeatt (1996): the
network doesn't see the velocities, and has to infer them from what it saw before. It is an Elman
network: 3 inputs, 3 hidden tanh units that also receive their own previous outputs, and a tanh
output, without biases, 21 weights. The fitness is Gruau et al.'s damping fitness over 1000 steps,
maximized by CMA-ES with its step size bounded below, as Igel (2003) did. The task is solved, by
Gruau et al.'s criteria, when the best network of a generation balances the poles for 100,000
steps and, from 625 other starts, for 1000 steps from at least 200. Then the same task by NEAT.
The task, the networks and the fitness run in Rust (``gx.problems.control``, ``gx.nn``,
``gx.neat``), so the runs are the Rust example's, to the bit, on every platform.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/double_pole_no_velocities/main.py
"""
import numpy as np
import genoxide as gx
from genoxide.problems.control import (
GENERALIZATION_THRESHOLD,
SUCCESS_STEPS,
Balance,
DoublePole,
)
from trace import Trace, degrees
# 3 inputs, 3 hidden units with a context, 1 output, without biases
elman = gx.nn.Elman(3, 3, 1, "tanh", output_activation="tanh", bias=False)
task = DoublePole(velocities=False)
def extent(weights, steps):
"""The largest |x|, |θ₁| and |θ₂| (in degrees) over an episode of ``steps`` steps."""
states = np.abs(task.episode(elman.policy(weights), steps))
return (
float(np.max(states[:, 0])),
float(np.max(degrees(states[:, 2]))),
float(np.max(degrees(states[:, 4]))),
)
def generation_best(progress):
"""The position of the generation's best network, the first of equals, if it balanced the
1000 steps of the damping fitness (then its fitness is at least 0.1), or None."""
scores = progress.scores
if np.all(np.isnan(scores)):
return None
best = int(np.nanargmax(scores))
return best if scores[best] >= 0.1 else None
def tests(policy):
"""Gruau et al.'s tests: the starts of the generalization test that ``policy`` passed, if it
balances the poles for 100,000 steps from the start and passes the test, or None."""
if task.run(policy, SUCCESS_STEPS) < SUCCESS_STEPS:
return None
generalization = task.generalization(policy)
return generalization if generalization >= GENERALIZATION_THRESHOLD else None
# Gruau et al.'s damping fitness over 1000 steps, evaluated in Rust
cmaes = gx.Cmaes(
elman.representation((-1.0, 1.0)),
min_step=0.05,
restarts="ipop",
objective="maximize",
seed=1,
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace(elman, task)
solution = None
def on_generation(progress):
"""Records the generation, and runs the tests of the generation's best network: the run
stops once it passes them."""
global solution
trace.record(progress)
best = generation_best(progress)
if best is None:
return True
weights = progress.population[best]
generalization = tests(elman.policy(weights))
if generalization is None:
return True
solution = (weights, generalization, progress.evaluations, progress.generation)
return False
result = cmaes.run(
Balance(task, elman, fitness="damping"), evaluations=100_000, on_generation=on_generation
)
if solution is None:
print(f"not solved after {result.evaluations} evaluations")
else:
weights, generalization, evaluations, generation = solution
print(f"solved after {evaluations} evaluations in {generation} generations")
print(
f"balanced for {SUCCESS_STEPS} steps from the start, and for 1000 steps from "
f"{generalization} of the 625 generalization starts (at least {GENERALIZATION_THRESHOLD} "
"needed)"
)
print(f"damping fitness {task.damping_fitness(elman.policy(weights)):.6f}")
position, long, short = extent(weights, SUCCESS_STEPS)
print(
f"over the 100000 steps: the cart within {position:.4f} m, the poles within {long:.4f}° "
f"and {short:.4f}°"
)
print("weights: [" + ", ".join(f"{w:.3f}" for w in weights) + "]")
trace.write(weights)
# the same task by NEAT, with the paper's settings for it: 1000 recurrent networks that grow
# from the three inputs and a bias connected to the output, c3 = 3 and a threshold of 4, and
# new connections with probability 0.3; the damping fitness, and the same success criteria. A
# recurrent network as a controller: its output, in (0, 1), is the force as 2 × output − 1,
# and its state is cleared at the start of each episode
def controller(network):
return network.recurrent().policy(scale=2.0, offset=-1.0)
def damping(network):
return task.damping_fitness(controller(network))
neat = gx.Neat(
3,
1,
population_size=1000,
compatibility=(1.0, 1.0, 3.0, 4.0),
structural_mutation=(0.03, 0.3),
feed_forward=False,
seed=1,
)
neat_solution = None
def neat_generation(progress):
"""Runs the tests of the generation's best network: the run stops once it passes them."""
global neat_solution
best = generation_best(progress)
if best is None:
return True
network = progress.population[best]
generalization = tests(controller(network))
if generalization is None:
return True
neat_solution = (network, generalization, progress.evaluations, progress.generation)
return False
result = neat.run(damping, evaluations=400_000, on_generation=neat_generation)
if neat_solution is None:
print(f"\nNEAT: not solved after {result.evaluations} evaluations")
else:
network, generalization, evaluations, generation = neat_solution
print(f"\nNEAT: solved after {evaluations} evaluations in {generation} generations")
print(
f"balanced for {SUCCESS_STEPS} steps from the start, and for 1000 steps from "
f"{generalization} of the 625 generalization starts"
)
print(
f"the network: {network.hidden()} hidden nodes, {network.enabled()} enabled "
"connections"
)
What it prints, from a seeded run:
solved after 1677 evaluations in 128 generations
balanced for 100000 steps from the start, and for 1000 steps from 201 of the 625 generalization starts (at least 200 needed)
damping fitness 0.112648
over the 100000 steps: the cart within 0.3839 m, the poles within 6.0695° and 13.9836°
weights: [-0.062, -0.160, 0.593, 0.125, -0.869, 0.073, 0.077, -0.987, 0.896, 0.614, 0.513, 0.671, -0.017, -0.895, 0.929, 0.526, -0.074, -0.093, -0.288, 0.922, 0.696]
NEAT: solved after 33488 evaluations in 33 generations
balanced for 100000 steps from the start, and for 1000 steps from 212 of the 625 generalization starts
the network: 4 hidden nodes, 18 enabled connections