Cart-pole
The problem
A pole is hinged to a cart that runs on a track, and falls unless the cart moves under it. A controller pushes the cart left or right to keep the pole upright and the cart on the track. Barto, Sutton and Anderson (1983) made it the standard test of learning control, and it has been used to compare reinforcement learning and neuroevolution methods since.
The system here is theirs, with the equations of motion corrected by Florian (2007), and the settings of Gomez, Schmidhuber and Miikkulainen (2008, Accelerated neural evolution through cooperatively coevolved synapses, JMLR 9: 937-965), who compare many methods on it:
| Setting | Value |
|---|---|
| Cart | 1 kg, on a track from −2.4 m to 2.4 m |
| Pole | 0.1 kg, 1 m long (a half-length of 0.5 m) |
| Friction | 0.0005 of the cart on the track, 0.000002 N m s at the hinge |
| Force | up to 10 N either way, held for each step of 0.02 s |
| Start | the pole at 4° from vertical, the cart at rest in the middle |
| Failure | the pole beyond 12°, or the cart beyond the track's ends |
| Success | 100,000 steps without failing, over 33 minutes of simulated time |
The equations are integrated by fourth-order Runge-Kutta in two steps of 0.01 s per step, with
genoxide's portable math::sin_cos, so a run is the same bits on every platform
(genoxide::problems::control::CartPole).
The Python version runs the task, the network and the fitness in Rust
(gx.problems.control.CartPole, gx.nn.Mlp, Balance), and NEAT with gx.Neat, its
networks' policies run in Rust too: it prints the same output and writes the same trace.
What makes it hard
Not much, for a method that searches the weights of a network: Gomez et al. (2008) found that random weight guessing solves it in 199 attempts on average. It is the baseline of the pole balancing family, before the double pole.
What is hard is the length of the test: a controller has to keep the system stable for 100,000 steps, not just to catch the pole once. Most random networks drop the pole within a few dozen steps, and some keep it up for thousands of steps while the cart drifts slowly to the end of the track.
Representation
A multilayer perceptron (nn::Mlp) of 4 inputs, 8 hidden tanh units and a tanh output, without
biases: Igel's (2003, Neuroevolution for reinforcement learning using evolution strategies, CEC
2003: 2588-2595) network for this task, 40 weights, a Real genome in [−1, 1] each
(Mlp::representation). The inputs are the cart's position and velocity and the pole's angle and
angular velocity, scaled to about [−1, 1]; the output, in (−1, 1), is the force in units of 10 N.
Without biases the network is an odd function of the state, as the task is symmetric: Igel found
that biases slow the search.
The fitness is the number of steps the network balances the pole, up to 100,000, maximized.
Algorithm
CMA-ES (Hansen and Ostermeier, 2001, Evolutionary Computation 9(2): 159-195), the method genoxide recommends for continuous problems of up to a few hundred genes, with its defaults: a population of 4 + ⌊3 ln 40⌋ = 15 and a step size of 0.3 of each gene's range, and IPOP restarts in case a run converges without a solution. The run stops at 100,000 steps, or after 100,000 evaluations.
Then NEAT (neat::Neat, Stanley and Miikkulainen 2002) solves the same task, evolving the
network's structure with its weights, with the paper's settings: 150 networks that start from the 4
inputs and a bias connected to the output, and grow hidden nodes and connections. Its output, the
paper's steepened sigmoid in (0, 1), is the force as 2 × output − 1. The XOR by NEAT
page describes the method.
Output
The first line gives the steps the best network balanced, the evaluations and the generations it took. The second gives how far the cart and the pole went from the middle and the vertical over the 100,000 steps, and the third the network's weights. The last two lines are NEAT's: the steps its best network balanced, after how many evaluations and generations, 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 criterion, 100,000 steps. The run of output.txt reaches it after
30 evaluations, in 1 generation, and its network keeps the cart within 9 cm of the middle and the
pole within 4° over the 100,000 steps.
Over seeds 1 to 100, all 100 runs solved the task, after 45 evaluations on average (a median of 30, at most 165). The counts are of whole generations of 15: the engine evaluates a generation before it checks the stop.
Gomez et al. (2008, table 1) list the average evaluations of 50 runs for this task: 98 for CoSyNE, 199 for random weight guessing, 283 for CMA-ES (from Igel 2003), 289 for ESP, 302 for SANE, 352 for CNE and 743 for NEAT, and thousands for the value-function methods. The setups differ in details that matter at these small numbers: Igel's CMA-ES started the pole upright, without friction, and turned the network's output into a push of ±10 N at random with the output's probability, where here the force is the output itself and the pole starts at 4°.
NEAT's run of output.txt balances the pole with a network of its initial population: 150
evaluations, generation 0, no hidden node. Over seeds 1 to 20, all 20 runs solved it, after 187
evaluations on average. Gomez et al.'s 743 for NEAT comes from other code and settings.
Known optimum: Balanced for 100,000 steps of 0.02 s (the success criterion of Gomez et al. 2008)
Source: examples/cart_pole
Interactive run: tachsin.gr/projects/genoxide/examples/cart-pole
cargo run --release --example cart_pole
//! Cart-pole: evolve the weights of a neural network that balances a pole on a cart for 100,000
//! steps, by CMA-ES.
//!
//! The classic control task (Barto, Sutton and Anderson 1983), with Florian's (2007) corrected
//! equations and Gomez, Schmidhuber and Miikkulainen's (2008) settings: a 1 kg cart on a 4.8 m
//! track, a pole of 1 m and 0.1 kg starting at 4° from vertical, and a force of up to 10 N every
//! 0.02 s. The network sees the cart's position and velocity and the pole's angle and angular
//! velocity, and outputs the force: 4 inputs, 8 hidden tanh units and a tanh output, without
//! biases, 40 weights. The fitness is the number of steps before the pole passes 12° or the cart
//! leaves the track, maximized by CMA-ES until a network balances it for 100,000 steps, over 33
//! minutes of simulated time.
//!
//! 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 cart_pole
//! ```
mod trace;
use genoxide::neat::{Neat, Network};
use genoxide::nn::{Activation, Mlp};
use genoxide::prelude::*;
use genoxide::problems::control::{CartPole, SUCCESS_STEPS};
// 4 inputs, 8 hidden units, 1 output, without biases: Igel's (2003) network for this task
pub fn network() -> Result<Mlp> {
let mlp = Mlp::new([4, 8, 1], Activation::Tanh)?;
Ok(mlp.output_activation(Activation::Tanh).bias(false))
}
// the largest |x| and |θ| (in degrees) over an episode of `steps` steps
fn extent(task: &CartPole, network: &Mlp, weights: &[f64], steps: u32) -> Result<(f64, f64)> {
let mut policy = network.with(weights)?;
let mut task = *task;
let (mut observation, mut action) = ([0.0; 4], [0.0]);
let (mut position, mut angle) = (0.0_f64, 0.0_f64);
for _ in 0..steps {
task.observe(&mut observation);
policy.forward(&observation, &mut action);
task.step(action[0]);
let [x, _, theta, _] = task.state();
position = position.max(x.abs());
angle = angle.max(theta.abs().to_degrees());
}
Ok((position, angle))
}
fn main() -> Result<()> {
let mlp = network()?;
let task = CartPole::new();
// the steps balanced, up to 100,000
let steps = |weights: &Reals| -> Option<f64> {
let mut policy = mlp.with(weights).ok()?;
Some(f64::from(task.run(&mut policy, SUCCESS_STEPS)))
};
let cmaes = Cmaes::builder(mlp.representation(-1.0..=1.0)?)
.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(&mlp, &task);
let outcome = Engine::new(cmaes, steps)
.stop_when(Stop::target(f64::from(SUCCESS_STEPS)).or(Stop::evaluations(100_000)))
.on_generation(|snapshot| trace.record(snapshot))
.run()?;
println!(
"balanced for {} steps (the goal: {SUCCESS_STEPS}) after {} evaluations in {} generations",
outcome.best_fitness(),
outcome.evaluations(),
outcome.generations()
);
let weights = outcome.best_genome();
let (position, angle) = extent(&task, &mlp, weights, SUCCESS_STEPS)?;
println!("over the 100000 steps: the cart within {position:.4} m, the pole within {angle:.4}°");
let rounded: Vec<String> = weights.iter().map(|w| format!("{w:.3}")).collect();
println!("weights: [{}]", rounded.join(", "));
trace.write(weights);
neat(&task)?;
Ok(())
}
// the same task by NEAT, with the paper's settings: networks that grow from the inputs and a bias
// connected to the output, whose output, in (0, 1), is the force as 2 × output − 1
fn neat(task: &CartPole) -> Result<()> {
let steps = |network: &Network| -> Option<f64> {
let mut evaluator = network.feed_forward().ok()?;
let mut policy = |observation: &[f64], action: &mut [f64]| {
let mut output = [0.0];
evaluator.activate(observation, &mut output);
action[0] = 2.0 * output[0] - 1.0;
};
Some(f64::from(task.run(&mut policy, SUCCESS_STEPS)))
};
let neat = Neat::builder(4, 1).seed(1).build()?;
let outcome = Engine::new(neat, steps)
.stop_when(Stop::target(f64::from(SUCCESS_STEPS)).or(Stop::evaluations(100_000)))
.run()?;
let network = outcome.best_genome();
println!(
"\nNEAT: balanced for {} steps after {} evaluations in {} generations",
outcome.best_fitness(),
outcome.evaluations(),
outcome.generations()
);
println!(
"the network: {} hidden nodes, {} enabled connections",
network.hidden(),
network.enabled()
);
Ok(())
}
python examples/cart_pole/main.py
"""Cart-pole: evolve the weights of a neural network that balances a pole on a cart for 100,000
steps, by CMA-ES.
The classic control task (Barto, Sutton and Anderson 1983), with Florian's (2007) corrected
equations and Gomez, Schmidhuber and Miikkulainen's (2008) settings: a 1 kg cart on a 4.8 m track,
a pole of 1 m and 0.1 kg starting at 4° from vertical, and a force of up to 10 N every 0.02 s. The
network sees the cart's position and velocity and the pole's angle and angular velocity, and
outputs the force: 4 inputs, 8 hidden tanh units and a tanh output, without biases, 40 weights.
The fitness is the number of steps before the pole passes 12° or the cart leaves the track,
maximized by CMA-ES until a network balances it for 100,000 steps, over 33 minutes of simulated
time. 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/cart_pole/main.py
"""
import numpy as np
import genoxide as gx
from genoxide.problems.control import SUCCESS_STEPS, Balance, CartPole
from trace import Trace, degrees
# 4 inputs, 8 hidden units, 1 output, without biases: Igel's (2003) network for this task
mlp = gx.nn.Mlp([4, 8, 1], "tanh", output_activation="tanh", bias=False)
task = CartPole()
def extent(weights, steps):
"""The largest |x| and |θ| (in degrees) over an episode of ``steps`` steps."""
states = task.episode(mlp.policy(weights), steps)
return float(np.max(np.abs(states[:, 0]))), float(np.max(degrees(np.abs(states[:, 2]))))
# the steps balanced, up to 100,000, evaluated in Rust
cmaes = gx.Cmaes(mlp.representation((-1.0, 1.0)), 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(mlp, task)
result = cmaes.run(
Balance(task, mlp), target=SUCCESS_STEPS, evaluations=100_000, on_generation=trace.record
)
print(
f"balanced for {result.best_fitness:.0f} steps (the goal: {SUCCESS_STEPS}) after "
f"{result.evaluations} evaluations in {result.generations} generations"
)
weights = result.best_genome
position, angle = extent(weights, SUCCESS_STEPS)
print(f"over the 100000 steps: the cart within {position:.4f} m, the pole within {angle:.4f}°")
print("weights: [" + ", ".join(f"{w:.3f}" for w in weights) + "]")
trace.write(weights)
# the same task by NEAT, with the paper's settings: networks that grow from the inputs and a bias
# connected to the output, whose output, in (0, 1), is the force as 2 × output − 1
def steps(network):
policy = network.feed_forward().policy(scale=2.0, offset=-1.0)
return task.run(policy, SUCCESS_STEPS)
neat = gx.Neat(4, 1, seed=1)
result = neat.run(steps, target=SUCCESS_STEPS, evaluations=100_000)
network = result.best_genome
print(
f"\nNEAT: balanced for {result.best_fitness:.0f} steps after {result.evaluations} evaluations "
f"in {result.generations} generations"
)
print(f"the network: {network.hidden()} hidden nodes, {network.enabled()} enabled connections")
What it prints, from a seeded run:
balanced for 100000 steps (the goal: 100000) after 30 evaluations in 1 generations
over the 100000 steps: the cart within 0.0924 m, the pole within 3.9342°
weights: [-0.559, -0.971, -0.280, -0.638, 0.250, 0.841, -1.000, -0.897, 1.000, -0.174, 0.185, 0.967, -0.445, -0.624, -0.628, -0.721, -0.970, 0.821, 0.252, -0.805, 0.330, 1.000, -0.181, -0.217, -0.175, -0.027, -0.002, -0.474, -0.282, -0.159, 0.794, 0.045, -1.000, -0.526, 0.254, -0.358, -0.495, 1.000, -1.000, 1.000]
NEAT: balanced for 100000 steps after 150 evaluations in 0 generations
the network: 0 hidden nodes, 5 enabled connections