Constraint reasoning -- build your own solver

April 3, 1995

Duration

1 day

Presenter

    Thom Fruehwirth <thom@ecrc.de>
    European Computer-Industry Research Centre
    Munich, Germany

Description

A special purpose concurrent high-level language for writing constraint systems called constraint handling rules (CHRs) is introduced by means of examples shown running on a computer. This is also an excellent opportunity to learn about classical constraint systems (over Booleans and numbers etric reasoning), to see how they can be implemented in a straightforward way and how they are applied to solve real-life problems.

First, the history and state-of-the-art of constraint-based programming are given. We then identify the "black-box solver" problem encountered in real-life applications and propose a solution, namely a special purpose programming language for writing constraint systems, CHRs. We introduce syntax, semantics and pragmatics of the language. The CHR language has been implemented in 1993 as a library of ECRC's constraint logic programming platform ECLiPSe. CHRs have been used to implement a variety of constraint systems.

We explain how to solve Boolean constraints and how to use them in circuit design. We show how to solve linear equations over numbers and how to use them to do financial analysis. We also look at two novel constraint domains: One is temporal reasoning, where we will solve the workshop murder mystery, the other is geometric reasoning. We present an application study for SIEMENS in the domain of telecommunications. The color-graphic demonstrator involves geometric constraints to find the optimal placement of senders for wireless portable devices (e.g. portable phones).

Prerequisites

No specific background knowledge is required to access the tutorial.

Audience

The target audience is people interested in practical aspects of artificial intelligence based on the solid formal framework of classical logic, for which constraint reasoning is the example.

Presenter

Thom Fruehwirth received a Master (1986) and PhD (1990) in Computer Science from the Technical University of Vienna, Austria, in the area of logic programming.

From 1986 to 1990 he was a assistant at the Computer Science Department of the University. In 1989 he received a one year Fulbright grant to the State University of New York. In 1990, he was invited to the Weizmann Institute of Science, Israel. In 1991, Thom Fruehwirth joined ECRC (European Computer-Industry Research Centre) to work on constraint logic programming.

He has given recent tutorials about constraint handling at the Spring School on Constraints, Chatillon/Seine, France, in May 1994 and at the German Workshop on Logic Programming, Zurich, Switzerland, in October 1994. At the moment, Thom Fruehwirth is giving a course on Constraint Reasoning at the Ludwig-Maximilian-University in Munich.