---
title: "Machine Discovery of Effective Admissible Heuristics"
authors:
  - "Armand Prieditis"
doi: ""
url: "https://ijcai.org/proceedings/1991/105"
pdf: "https://ijcai.org/proceedings/1991/0105.pdf"
venue: "Proceedings of the Twelfth International Joint Conference on Artificial Intelligence"
year: 1991
pages: "720-724"
track: "Learning Be Knowledge Acquisition"
keywords:
---

# Machine Discovery of Effective Admissible Heuristics

Armand Prieditis

*Proceedings of the Twelfth International Joint Conference on Artificial Intelligence*, pages 720-724.

## Abstract

Admissible heuristics are an important class of heuristics worth discovering: they guarantee shortest path solutions in search algorithms such as A • and they guarantee less expensively produced, but boundedly longer solutions in search algorithms such as dynamic weighting. Unfortunately, effective (accurate and cheap to compute) admissible heuristics can take years for people to discover. Several researchers have suggested that abstractions of a problem can be used to gene rate admissible heuristics. This paper describes and evaluates an implemented program (Absolver II) that uses a means-ends analysis search control strategy to discover abstracted problems that result in effective admissible heuristics. Absolver II discovered several well-known and novel admissible heuristics, including the first known effective one for Rubik's Cube , thus concretely demonstrating that effective admissible heuristics can be tractably discovered by a machine.