Learning to solve planning problems efficiently by means of genetic programming

Area of Science:

• Artificial Intelligence
• Computer Science

Background:

• Declarative problem solving, like planning, presents challenges for Genetic Programming (GP).
• Existing GP applications in planning involve searching plan space or evolving entire planners.

Purpose of the Study:

• To evolve heuristics to enhance the efficiency of existing planning systems.
• To offer a more feasible and efficient alternative to evolving entire planners or searching plan space.

Main Methods:

• Evolving heuristics using Genetic Programming (GP) for specific planning domains.
• Introducing and utilizing an Instance-Based Crossover genetic operator.
• Leveraging traces from a base planner as genetic material.

Main Results:

• The EvoCK approach successfully evolved heuristics that improved the performance of the PRODIGY4.0 planner.
• Demonstrated effectiveness in the blocks world and logistics planning domains.
• Instance-Based Crossover proved capable of utilizing planner traces for evolution.

Conclusions:

• Evolving heuristics is a viable strategy for improving planner efficiency.
• The EvoCK approach offers a more efficient and adaptable method for AI planning.
• The Instance-Based Crossover operator shows promise for GP-based planning.