Abstract
Genetic programming (GP) is an automatic programming technique that has recently been applied to a wide range of problems including blocks-world planning. This paper describes a series of illustrative experiments in which GP techniques are applied to traditional blocks-world planning problems. We discuss genetic planning in the context of traditional AI planning systems, and comment on the costs and benefits to be expected from further work.
Introduction
In this 1994 study, Lee Spector explores the feasibility of evolving AI planners rather than manually engineering them. By applying Genetic Programming (GP) to the classic "blocks-world" domain, the research demonstrates that evolutionary algorithms can produce robust, domain-dependent planning programs. These evolved programs are capable of generalizing to unseen problems, moving beyond the generation of single plans to the creation of universal planning strategies.
Problem Statement
Traditional AI planning systems from the early 1990s typically relied on declarative representations, such as STRIPS operators. In these systems, every action's preconditions and effects must be explicitly defined. However, this approach is often hampered by the "frame problem" and the significant effort required to author complex domain models. Spector investigates whether GP—a technique that "grows" computer programs through simulated evolution—can bypass these hurdles by using a simulator to evaluate fitness rather than relying on formal logic models.
Methodology
The research utilizes GP to evolve LISP-like programs. The evolutionary process is defined by several key components:
- Function and Terminal Sets: Instead of hard-coding specific block names, the system uses functions like
PUTON(to move a block) andNEWTOWER(to move a block to the table). Control structures such asDO-ON-GOALSallow the program to iterate through unachieved goals. - Staged Fitness Functions: To guide the evolutionary search effectively, a multi-component fitness measure is introduced in stages: correctness (goals achieved), efficiency (number of moves), and parsimony (program simplicity).
- Simulation-Based Evaluation: Candidate programs are executed within a blocks-world simulator. This allows the GP system to evaluate performance based on actual outcomes rather than logical proofs.
The experiments primarily use the blocks-world domain, including the famous Sussman Anomaly benchmark. For advanced experiments, sets of 20 to 40 "fitness cases"—specific initial and goal configurations—were used for training and evaluation.
Key Insights
A major finding is that GP does not require a declarative model of the world; a simulator is sufficient for finding solutions. This positions GP as an "anytime" algorithm, where the best plan found so far can be retrieved at any point. Furthermore, the use of relative references (e.g., TOP and BOTTOM) instead of specific block names significantly improved the robustness and generalization of the evolved planners. The evolution process was even found to "discover" general stacking strategies that could solve problems with more blocks than were present during training.
Key Results
The study details three primary experiments:
- Single Plan: The system successfully evolved a maximally efficient solution to the Sussman Anomaly by generation 32.
- Universal Plan: A program was evolved that could achieve a specific goal configuration from any possible initial state of three blocks.
- Domain-Dependent Planner: This most advanced experiment resulted in a planner that solved all 169 possible 3-block problems and successfully generalized to 4-block problems it had never encountered.
Limitations and Future Outlook
While promising, the GP approach is computationally intensive, as evaluating thousands of programs in a simulator is time-consuming. The success of the evolutionary process is also highly sensitive to hyperparameters like population size and the specific function set provided. Additionally, early-stage fitness functions can be "coarse," creating a difficult landscape for the search algorithm. Future work aims to develop "domain-independent" planners capable of solving problems across diverse domains using a single evolved program.
Summary updated