Introduction
Presented at AAAI-87, MEDUSA is an experimental system designed to automate the creation of algorithms. While automated programming systems often struggle with the "combinatorial explosion" of searching through infinite possible code combinations, MEDUSA utilizes performance requirements—specifically asymptotic time complexity—as a primary filter to prune the search space effectively.
The Challenge of Algorithm Synthesis
Algorithm synthesis involves transforming a functional specification ("what to do") into an efficient implementation ("how to do it"). This process is notoriously difficult, traditionally requiring significant domain-specific knowledge and intuitive leaps. Previous systems were often either too general, leading to exhaustive searches, or required heavy user guidance. MEDUSA addresses this by focusing on planar intersection problems in computational geometry and using Big-Oh complexity as a constraint to maintain tractability.
Methodology: Cost-Constrained Refinement
MEDUSA employs a top-down refinement process, treating synthesis as a grammar generation problem where terminal nodes are known primitive algorithms. The system utilizes four primary subtask generation methods:
- Skeletal Algorithms: Templates for general paradigms like binary divide-and-conquer or mergesort.
- Logical Transformations: Using domain knowledge to simplify tasks (e.g., equating containment to subset and boundary intersection checks).
- Case Decomposition: Breaking a problem into disjoint scenarios, such as whether boundaries intersect or not.
- Dual Transforms: Mapping problems into a different mathematical space (e.g., points to lines) to find more efficient solutions.
A critical feature of MEDUSA is Cost Pruning. Every task is assigned a Big-Oh budget. If a proposed decomposition exceeds this budget, it is immediately discarded. Furthermore, the system uses a "Typical Cost" heuristic, favoring algorithms whose average performance matches the constraint, assuming that more complex templates are often more robust or easier to refine.
Evaluation and Results
MEDUSA was evaluated against a benchmark suite of 19 computational geometry problems. The system successfully synthesized all 19 algorithms without human intervention, deriving non-trivial solutions such as $O(N \log N)$ for arbitrary rectangle intersection and $O(N)$ for convex polygon intersection.
Conclusion and Future Work
The primary insight from MEDUSA is that performance constraints make synthesis easier by significantly reducing the search space. By treating complexity as a search filter rather than just a final goal, the system avoids the search-space explosion that plagued earlier synthesis attempts. However, limitations remain, such as the high computational cost of exploring dual transforms and the sensitivity of the system to manually estimated "typical costs." Future work aims to improve the ordering of dependent subtasks and refine comparison metrics for more complex geometric scenarios.
Summary updated