Abstract
This paper explores the application of Genetic Programming (GP) to the challenge of autonomous robot control, specifically focusing on a box-pushing task. By evolving populations of tree-structured computer programs, GP demonstrates the ability to discover complex control logic with minimal human intervention. This approach is contrasted with contemporary Reinforcement Learning (RL) methods, which often require extensive manual engineering of state spaces and behavior hierarchies. The results indicate that GP can successfully evolve robust strategies that emerge directly from high-level fitness measures.
Introduction: The Challenge of Automatic Programming
The fundamental goal of automatic programming is to enable computers to solve tasks based on "what" needs to be done rather than "how" to do it. In the context of robotics, this translates to defining a goal—such as moving a box to a wall—and allowing the system to discover the necessary sequence of actions.
The "box-moving" problem serves as a benchmark. A robot must locate a box in an irregularly shaped environment and push it to a boundary. This task is non-trivial; off-center pushes cause the box to rotate, requiring the robot to adjust its position dynamically. While Reinforcement Learning (RL) was the standard approach in the early 1990s, the authors argue that RL's "automatic" nature is often overstated due to the significant human effort required to pre-structure the learning environment.
Methodology: Genetic Programming for Robot Control
Genetic Programming (GP) evolves LISP-like symbolic expressions (S-expressions) represented as trees. Unlike Genetic Algorithms that use fixed-length strings, GP allows for variable-sized programs, enabling the evolution of increasingly complex logic.
Program Representation
The programs are composed of:
- Terminals: Leaf nodes representing sensors (e.g., 12 sonar inputs) and primitive actions (e.g.,
Move Forward,Turn Left). - Functions: Internal nodes providing logic and sequencing (e.g.,
IF-BUMP,PROGN2).
The Evolutionary Cycle
The process begins with a population of random programs. Each is evaluated in a simulated environment across multiple "fitness cases" (different starting positions). Fitness is determined by the final distance between the box and the wall. The most successful programs are selected for reproduction using crossover, where sub-trees from two parent programs are swapped to create novel offspring.
Results and Insights
The study compared two versions of the task. In Version 1, with helpful sensor terminals, GP achieved a perfect fitness score by generation 45. In the more challenging Version 2, where "helper" terminals were removed, GP still found a 100% successful solution by generation 20, albeit requiring a larger population size (2,000 individuals).
Critique of Manual Engineering
A key insight of the paper is the "13 Decisions" critique. The authors highlight that RL-based solutions often rely on 13 specific architectural choices made by humans—such as manually discretizing sensor data or pre-defining sub-behaviors like "unwedging." In contrast, GP discovers these behaviors emergently. For instance, the evolved programs learned to "clip" the box's corner to rotate it without being explicitly programmed to do so.
Conclusion
Genetic Programming offers a powerful alternative for robotic control, shifting the burden of design from the human engineer to the evolutionary process. While computationally intensive and currently limited to simulated environments, GP demonstrates that complex, robust behaviors can emerge from simple, high-level goal definitions. Future work must address the "sim-to-real" gap and the scalability of GP to multi-stage missions.
Summary updated