Constraint Programming (CP) makes it possible to model and specify problems with uncertain, incomplete information and to solve combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis. Constraint Handling Rules (CHR) is both a versatile theoretical formalism based on logic and an efficient practical high-level programming language based on declarative rules and constraints. Well-understood analysis techniques are available for the language. CHR applications will be presented as well.
Lecturers include:
The use of constraints had its scientific and commercial breakthrough in the 1990s. Programming with constraints makes it possible to model and specify problems with uncertain, incomplete information and to solve combinatorial problems, as they are abundant in industry and commerce, such as scheduling, planning, transportation, resource allocation, layout, design, and analysis. Constraint-based programming languages enjoy elegant theoretical properties, conceptual simplicity, and practical success. The idea of constraint-based programming is to solve problems by simply stating constraints (conditions, properties) which must be satisfied by a solution of the problem. Constraints can be considered as pieces of partial information. Constraints describe properties of unknown objects and relationships between them. Constraints are formalized as distinguished, predefined predicates in first-order predicate logic. The unknown objects are modeled as variables.
The lectures on constraint satisfaction and consistency techniques will take the students through the journey of what is happening behind the magic of constraint modeling. We will study the techniques of handling each constraint as well as a system of constraints. We will investigate the design and implementation of constraint propagators. Since constraint reasoning is often not enough to obtain a solution to a constraint problem, one needs to perform some search. We will study the core components of basic and advanced search techniques that are combined with constraint solving.
Rule-based programming experiences renaissance due to its applications in areas such as Business Rules, Semantic Web, Computational Biology, Verification and Security. Executable rules are used in declarative programming languages, in program transformation and analysis, and for reasoning in artificial intelligence applications. Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed, committed-choice, guarded multiset rewrite rules. It can embed many rule-based formalisms and concisely describe and efficiently execute algorithms in a declarative way. CHR is the only declarative language known in which every algorithm can be implemented with optimal space and time complexity. This tutorial to CHR covers the syntax, semantics, and basic properties of the language using several program examples. It shows CHR's strengths as a programming language and how to use CHR for solving problems quickly and elegantly. Simple examples teach how to write and reason about CHR programs, and what problems one can solve effectively with CHR.
Program analysis, both static and dynamic, is the central issue of programming environments. The clean semantics of CHR facilitates non-trivial program analysis and transformation. The course provides an overview about several techniques to prove properties of CHR solvers:
This course presents CHR as a special-purpose language to implement solvers over various domains.
Robotic sailing boats execute complex sailing processes completely autonomously and without human interaction. Starting with finding a route based on weather data, to the autonomous execution of manoeuvres, robotic boats are able to reach any desired destination. In this lecture, we present a rule-based algorithm for long-term routing of robotic sailboats. It computes optimal routes based on wind conditions, ocean currents, and shorelines, while taking the boats individual characteristics into account. We implemented our algorithm in the declarative rule-based programing language Constraint Handling Rules (CHR). Our method is based on the A*-algorithm and incorporates changing weather conditions by dynamically adapting the underlying routing graph. A comparison with existing commercial applications yields considerably shorter computation times for our implementation. It works with real-life wind and currents forecasts, high-resolution map data, and provides a graphical user interface.
In this lecture we present CHRiSM, a probabilistic extension of CHR based on CHR(PRISM). PRISM is a probabilistic extension of Prolog in which stochastic models can be represented, probabilistic inference can be done, and the parameters of the model (the underlying probability distributions) can be learned. CHRiSM adds the power of CHR rules to this mix, increasing the expressiveness of the formalism. We then demonstrate an application, called APOPCALEAPS, which was implemented in CHRiSM. It is a system that generates pop music songs. Its parameters can be tuned manually or learned automatically based on a given set of example songs.
Coinduction is an important theoretical tool for reasoning about infinite data structures such as streams. This course will introduce the notion of coinduction and show how the CHR language can be used to program coinductive reasoning.
The courses are accompanied by daily practical hands-on lab hours in the afternoon.Thom Frühwirth, October 12, 2011.