Synthesizing Algorithms with Performance Constraints

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Automated Reasoning

This paper describes MEDUSA, an experimental algorithm synthesizer. MEDUSA is characterized by its top-down approach, its use of cost-constraints, and its restricted number of synthesis methods. Given this model, we discuss heuristics used to keep this process from being unbounded search through the solution space. The results indicate that the performance criteria can be used effectively to help avoid combinatorial explosion. The system has synthesized a number of algorithms in its test domain (geometric intersection problems) without operator intervention.