Logic-Based Inductive Synthesis of Efficient Programs

Andrew CropperIJCAI 2016

Abstract

Traditional Inductive Logic Programming (ILP) systems prioritize textual brevity, often overlooking execution efficiency. This paper introduces Metagol$_O$, a framework that synthesizes logic programs optimized for resource complexity. By employing iterative descent, the system identifies programs that minimize operational costs, such as robot actions or algorithmic steps, rather than just code length.

Introduction

In Inductive Logic Programming (ILP), the objective is to generate a hypothesis (program) that explains a given set of examples. Most contemporary synthesis tools rely on "Occam’s Razor," selecting the shortest possible code. However, textual brevity does not necessarily correlate with execution efficiency. For instance, a concise implementation of Bubble Sort ($O(n^2)$) might be textually similar to a concise Merge Sort ($O(n \log n)$), leading standard ILP systems to treat them as equivalent. This paper addresses this limitation by proposing a method to learn "resource-optimal" programs, ensuring that synthesized algorithms minimize costly actions.

Problem Definition

The primary challenge is that textual complexity is a flawed objective function when performance is the goal. In tasks such as robot planning, a textually short plan might involve redundant or "clumsy" actions.

Initial and final states for the robot planning task.

As shown in Figure 1, the system must transform an initial state into a final state. A resource-optimal approach ensures that the sequence of actions (e.g., grab, move, drop) is minimized according to a defined cost function.

Methods: Metagol$_O$

The proposed system, Metagol$_O$, extends the Meta-Interpretive Learning (MIL) framework. Unlike standard MIL systems that stop at the first (shortest) valid hypothesis, Metagol$_O$ utilizes an iterative descent strategy:

  1. Initial Search: The system finds the program with minimal textual complexity ($H_1$).
  2. Resource Bounding: The resource complexity of $H_1$—calculated as the sum of the costs of individual actions—is set as an upper bound.
  3. Iterative Refinement: The system searches for a new program that is more resource-efficient than the current bound, tightening the bound with each success until convergence.
Synthesized logic program and corresponding execution plan.

Figure 2 illustrates a synthesized program where the move predicate is decomposed into sub-tasks (p1, p2, p3) that involve specific physical actions. The framework treats "resource" abstractly, allowing it to minimize time, energy, or other domain-specific costs.

Key Results

The evaluation of Metagol$_O$ across robot planning and list sorting scenarios yielded several key insights:

  • Convergence: The search procedure is theoretically proven to converge to resource-optimal strategies.
  • Algorithm Selection: In sorting experiments, Metagol$_O$ successfully distinguished between algorithms based on efficiency, learning a Quick Sort strategy over less efficient alternatives.
  • Robot Efficiency: In the robot planning task, the system successfully synthesized a plan that minimized the number of grab and drop operations, even when a textually similar but less efficient plan was available.

Limitations and Future Work

While effective, the current framework requires human-provided cost functions for actions. Future research aims to enable the system to infer these costs or time complexity automatically. Additionally, scaling iterative descent to larger program spaces and generalizing to "monadic" predicates remain open challenges.

Summary updated

BibTeX
@inproceedings{cropper2016logic,
  author = {Andrew Cropper},
  title = {{Logic-Based Inductive Synthesis of Efficient Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure