Browse Prior Art Database

THE ANATOMY OF EASY PROBLEMS: A CONSTRAINT-SATISFACTION FORMULATION

IP.com Disclosure Number: IPCOM000128344D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 15 page(s) / 40K

Publishing Venue

Software Patent Institute

Related People

Rina Dechter: AUTHOR [+4]

Abstract

This work aims towards the automatic generation of advice to guide the solution of difficult conatraiat-natistactioa problems (CSPs). The advice is generated by consulting relaxed, easy models which are backtrack-free.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE ANATOMY OF EASY PROBLEMS: A CONSTRAINT-SATISFACTION FORMULATION

Rina Dechter Judea Pearl December 1984 ...., Report No. CSD-840063

MA S T E R 'Cu'" " P Y The Anatomy of Easy Problems:

A Constraint-Satisfaction Formulation

Rina Dechter sad Judea Pearl

Computer Science Department University of California, Loa Angeles Loa Angeles, CA 90024 telephone number:(213) 825-3243 netmail adress: dechter UCLA-LOCUS.ARPA judeaOUCLA- LOCUS.ARPA

Topic: problem solving (automatic reasoning) Keywords: constraint-satisfaction, backtracking, heuristic-discovery, relaxation Word count: 4900

Abstract

This work aims towards the automatic generation of advice to guide the solution of difficult conatraiat-natistactioa problems (CSPs). The advice is generated by consulting relaxed, easy models which are backtrack-free.

We identify a subset of CSPa whose syntactic sad semantic properties make them easy to solve. The syntactic properties involve the structure of the constraint graph, while the seman-tic properties guarantee some local consistencies among the constraints. In particular, problems supported by tree-like constraint graphs, and none width-2 graphs, can be easily solved and are therefore chosen as the target model for the relaxation scheme. Optimal algorithms for solving easy problems are presented and analyzed. Finally, an efficient method is introduced for extract-ing advice from easy problems and using it to speedup the solution of hard problems.

1. Introduction

1.1 Why study easy problems!

An important component of human problem-solving expertise is the ability to use knowledge about solving easy problems to guide the solution of difficult ones. Only a few works in AI (Sacerdoti 1974( ,. [Carbonell 1983, , have attempted to equip machines with similar capabilities. Gaschnig (Gaschnig 1979) , Guida et.al (Guida 1979. and Pearl (Pearl 1983] suggested that knowledge about easy problems could be instruments! in the mechanical discovery of heuristics. Accord-ingly, it should be possible to manipulate the representation of a difficult problem until it is transformed into as easy one, solve the easy problem, then use the solution to guide the search process in the original problem.

UCLA Page 1 Dec 31, 1984

Page 2 of 15

THE ANATOMY OF EASY PROBLEMS: A CONSTRAINT-SATISFACTION FORMULATION

The implementation of this scheme requires three major steps: 1. aimpii>lcation 2. solu-tion 3. advice generation. Additionally, to perform the aimpti$cation step, we must have a sim-ple, a- priori criterion for deciding when a problem lends itself to easy solution.

This paper uses the domain of constrain tr.satisfaction tasks to examine the feasibility of these three steps. It establishes criteria for recognizing classes of easy problems, it provides spe-cial procedures for solving them, and it introduces an efficient method of extracting advice from them.

Constraint-satisfaction problems (CSP) invol...