Learning to Control a Dynamic Physical System

Margaret E. Connell, Paul E. UtgoffAAAI 1987

Introduction

The "cart-pole" (or inverted pendulum) problem is a classic benchmark in control theory and artificial intelligence. It involves balancing a pole on a cart that moves along a track by applying horizontal forces. Historically, solving this problem required significant human intervention to define the state space. In 1987, researchers introduced CART, a system designed to learn this task autonomously by treating the state space as a continuous field rather than a set of discrete "boxes."

The cart-pole system used as a benchmark for the CART algorithm, showing the cart position (x), pole angle (θ), and applied force (F).

The Challenge of Dynamic Control

Two primary obstacles hindered early automated control systems:

  1. The Credit Assignment Problem: Reinforcement is sparse and delayed. A failure (the pole falling or the cart hitting a boundary) might be the result of a poor decision made dozens of steps earlier. Identifying which specific action led to the failure is difficult.
  2. State Space Representation: Previous successful methods, such as the "BOXES" algorithm, required human experts to manually partition continuous variables (position, velocity, angle) into discrete regions. If these boundaries were chosen poorly, the system could never learn to stabilize.

The authors of CART sought to eliminate these manual starting assumptions by creating a system that could handle continuous state space directly and learn from sparse, delayed reinforcement.

The CART Architecture

The CART system addresses these issues through four integrated components:

  • The Critic: Instead of binary success/failure feedback, the Critic identifies specific past states as "desirable" or "undesirable." It employs a heuristic: if the system survives for over 100 steps, it identifies a state 50 steps prior where the system was moving toward the center and marks it as desirable.
  • The Learning Element: Using Shepard’s Interpolation Method, the system constructs a continuous "desirability surface" in a 5D space (four state variables plus desirability). This allows CART to estimate the value of novel states based on their proximity to known good or bad data points.
  • The Performance Element: To determine the next action (push left or right), the system calculates the gradient of the desirability surface. It selects the force that aligns the system's trajectory most closely with the direction of increasing desirability.
  • The Problem Generator: This component resets the simulation with slight random variations, forcing the learner to explore diverse regions of the state space and avoid over-fitting to a single starting condition.

Experimental Results

The CART system demonstrated remarkable efficiency compared to contemporary methods. While the BOXES algorithm typically required around 600 trials and early neural networks required upwards of 10,000, CART achieved stable control in approximately 16 trials.

Experimental data showing the number of steps survived per trial across six different runs. Note the rapid increase in stability, culminating in a run of 70,000 steps.

As shown in the performance data, the system quickly learns to extend the duration of balance. In its most successful runs, the system balanced the pole for 70,000 time steps—roughly 25 minutes of real-time simulation—at which point the experiment was manually terminated. CART also proved robust to physical changes, such as a 10x increase in pole mass or unequal force application, consistently reaching stability in under 18 trials.

Conclusion

By moving from discrete "boxes" to a continuous desirability surface, CART proved that gradient-following methods could solve complex control problems with minimal prior knowledge. While the system relies on some heuristic parameters (like the 50-step look-back), it represented a significant leap in reinforcement learning efficiency for its time, highlighting the power of continuous interpolation over manual state partitioning.

Summary updated

BibTeX
@inproceedings{connell1987learning,
  author = {Margaret E. Connell and Paul E. Utgoff},
  title = {{Learning to Control a Dynamic Physical System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure