Introduction
In Inductive Logic Programming (ILP), the principle of Occam’s Razor typically guides the search for the "shortest" program that explains a given set of observations. While textual brevity often correlates with generalizability, it does not necessarily imply execution efficiency. In robotics, a textually simple strategy—such as delivering items one by one—can be significantly more resource-intensive than a more complex strategy that utilizes composite objects, such as a bag, to deliver multiple items simultaneously.
Cropper and Muggleton (IJCAI 2015) address this discrepancy by introducing Metagol$_O$, a system designed to minimize resource complexity (e.g., time, energy, or distance) rather than just textual length.
Methodology: Meta-Interpretive Learning and Iterative Descent
Metagol$_O$ extends Meta-Interpretive Learning (MIL), a framework that allows for the learning of recursive programs and the invention of new predicates. The core innovation is the Iterative Descent search strategy:
- Baseline Discovery: The system first identifies the textually simplest program ($H_1$) that satisfies the goal.
- Resource Profiling: It calculates the resource cost (e.g., total moves) associated with $H_1$.
- Iterative Optimization: The system then searches for an alternative program that is no longer than $H_1$ but possesses a strictly lower resource cost.
- Convergence: This process repeats until no further efficiency gains can be found within the search space.
This approach allows the learner to move beyond simple planning (finding a sequence of moves for a specific instance) to strategy learning (finding a general program applicable to any number of objects).
Experimental Evaluation
The Postman Problem
In the "Postman Problem," a robot must collect $n$ letters and deliver them to $d$ destinations. Without the ability to compose objects (i.e., putting letters in a bag), the optimal strategy scales at $O(nd)$. However, by allowing the robot to use a container, the complexity can be reduced to $O(n + d)$.
As shown in the experimental results, Metagol$_O$ successfully learns to utilize the bag_letter action, resulting in a strategy that remains efficient as the number of objects increases, whereas the standard Metagol$_D$ system remains trapped in a textually simple but computationally expensive strategy.
The Sorter Problem
The "Sorter Problem" requires the robot to sort a list of numbers. This is a classic benchmark for algorithmic efficiency. While Bubble Sort is textually simple, its complexity is $O(n^2)$. In contrast, Quick Sort is more textually complex but operates at $O(n \log n)$.
Metagol$_O$ was able to discover a variant of Quick Sort by prioritizing resource efficiency. The empirical data demonstrates a clear divergence: as the list length grows, the resource cost for Metagol$_D$ grows quadratically, while Metagol$_O$ maintains the more efficient logarithmic scaling.
Key Insights
- Compositionality: The ability to form "composite objects" is a fundamental requirement for moving between complexity classes (e.g., from $O(nd)$ to $O(n+d)$).
- Efficiency as an Objective: By incorporating resource cost into the objective function, ILP systems can naturally learn sophisticated algorithmic structures like recursion and partitioning.
- Generalization: Unlike traditional planners, Metagol$_O$ produces general-purpose programs that scale to arbitrary problem sizes.
Conclusion and Future Work
Metagol$_O$ demonstrates that prioritizing execution efficiency over textual brevity allows for the discovery of significantly more powerful robot strategies. Future research directions include improving search speed via binary search on resource bounds, handling noisy environments, and exploring the autonomous invention of composite objects without prior background knowledge.
Summary updated