3rd CHR Summer School 2013

Programming and Reasoning with Rules and Constraints

8th-12th of July, 2013 — Berlin, Germany

Courses

  1. Introduction to CP and Modeling a Constraint Problem (4h), Slim Abdennadher, German University in Cairo
  2. Consistency Techniques and Constraint Reasoning, Carmen Gervet, German University in Cairo, Egypt
  3. Constraint-Based Scheduling (2h), Armin Wolf, Fraunhofer FOKUS, Berlin, Germany
  4. Introduction to CHR (2h), Thom Fruehwirth, Ulm University, Germany
  5. Implementing Constraint Solvers using CHR (2h), Slim Abdennadher, German University in Cairo
  6. Analysis of CHR Solvers (2h), Slim Abdennadher, German University in Cairo
  7. Abductive Reasoning and language processing with CHR (2-4h), Henning Christiansen, Roskilde University
  8. Probabilistic CHR: CHRiSM (2h), Jon Sneyers, K.U.Leuven, Belgium
  9. ASV Roboat - an autonomous sailing boat for ocean monitoring and its long-term routing (2h), Roland Stelzer, INNOC, Vienna, Austria and Jon Sneyers, K.U.Leuven, Belgium
  10. Confluence Analysis of CHR Programs (2h), Hariolf Betz, Ulm University, Germany
  11. Optimizing Compilation of CHR (2h), Jon Sneyers, K.U.Leuven, Belgium
  12. Source to Source Transformation for CHR (1h), Nada Sharaf, German University in Cairo, Egypt
  13. Parallel Execution of CHR on a Graphical Processing Unit (1h), Amira Zaki, Ulm University, Germany

Courses Abstracts

Introduction to CP and Modeling a Constraint Problem (4 hours)
Slim Abdennadher, German University in Cairo

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 main goal of this course is to give an introduction to a new programming paradigm based on constraints over different domains, such as Booleans, real (rational) numbers or finite domains. Special emphasis will be put on the practical use of these methods, in particular for solving combinatorial optimizations problems. No prior background knowledge is assumed, although familiarity with Prolog is useful.

Consistency Techniques and Constraint Reasoning (2 hours)
Carmen Gervet, German University in Cairo, Egypt

Constraint Programming manipulates elements from a finite set, or domain. It combines the deterministic removal of inconsistent values from domains with the non-deterministic search for solution(s). This lecture discusses different consistency notions and algorithms such as node, arc and path consistency.

Constraint-Based Scheduling (2 hours)
Armin Wolf, Fraunhofer FOKUS

Constraint-based scheduling is one of the most successful industrial application areas of Constraint Programming. Even for energy management questions arising in the context of the energy turnaround constraint-based scheduling approaches offer interesting opportunities for cost optimizations or load balancing according to the volatile availability of renewable energies. The course will introduce propagation and pruning techniques used for different kinds of resources and tasks, e.g. timetabling, edge-finding for exclusive and cumulative resources as well as for preemptive and non-preemptive tasks. Furthermore costs for resource usage like time-variable energy tariffs as well as load profiles are considered, too. Finally there will be some examples on how to model and solve practical scheduling problems, e.g. cost-optimal scheduling of electrical consumers.

Introduction to CHR (2 hours)
Thom Fruehwirth, Ulm University, Germany

This basic introduction to CHR covers the syntax, semantics, and basic properties using several program examples. No prior background knowledge is assumed, although familiarity with Prolog is useful.

Implementing Constraint Solvers using CHR (2 hours)
Slim Abdennadher, German University in Cairo and Thom Fruehwirth, University Ulm

After the previous introductory session that presents CHR as a general-purpose language, this course presents CHR as a special-purpose language to implement solvers over various domains.

Analysis of CHR Solvers (2 hours)
Slim Abdennadher, German University in Cairo

Program analysis, both static and dynamic, is the central issue of programming environments. The 2 hour course provides an overview about several techniques to prove properties of CHR solvers. In particular, we will discuss:

The course is based on several research papers, especially the paper As time goes by: Constraint Handling Rules - A Survey of CHR Research from 1998 to 2007 and on a chapter of the book Constraint Handling Rules.

No special background is needed!

Abductive Reasoning and language processing with CHR (2-4 hours)
Henning Christiansen, Roskilde University

Abduction refers to the sort reasoning that infers facts by means of which a given observation can be explained. This can be understood as reasoning backwards from an observed effect to its possible cause, e.g., from symptoms to diagnosis. Abduction is often accompanied by so-called integrity constraints that limit the inferred facts or causes to be what is believed to conform with some possible world.

CHR allows an elegant encoding of abduction, by mapping abducible facts into CHR constraints and integrity constraints into CHR rules. Combining this with Prolog as a general knowledge representation system yields an easy-to-use and powerful environment for abductive reasoning. When, furthermore, this is combined with Prolog's grammar notation, DCGs, we obtain a system abductive language interpretation.

CHR Grammars represent another system in which CHR rules are applied for bottom-up analysis, which can also be combined with abduction in CHR as described.

Finally, we may sketch how these techniques can be extended with probabilities as to find most probable out of many possible explanations, and we will indicate theoretical results that tie together the three areas of abductive logic programming, constraint logic programming and CHR.

Probabilistic CHR: CHRiSM (2 hours)
Jon Sneyers, K.U.Leuven, Belgium

CHRiSM is a probabilistic variant of CHR, based on CHR(PRISM). In CHRiSM, every rule instance can either be fired, or not fired, depending on its probability. The body of a rule can also contain probabilistic disjunctions: instead of the standard Prolog backtracking, one disjunct will be chosen randomly. All probability distributions in CHRiSM can be chosen manually, or learned from a training set consisting of so-called (full or partial) observations.

In this lecture we will introduce the syntax and semantics of CHRiSM based on a series of examples. We discuss relevant topics of program analysis such as ambiguity and probabilistic termination. Finally we take a look at two applications of CHRiSM: the APOPCALEAPS music generation and learning system, and an application in probabilistic legal reasoning

ASV Roboat - an autonomous sailing boat for ocean monitoring and its long-term routing (2 hours)
Roland Stelzer, INNOC, Vienna, Austria and Jon Sneyers, K.U.Leuven, Belgium

Recent events, like the devastating tsunamis in Asia, the Deep-water Horizon oil spill in Gulf of Mexico, accidents involving refugee boats in the Mediterranean Sea and pirate activities in the Gulf of Aden have impressively emphasized the importance of a fully integrated ocean observation system. Robotic sailing boats offer the possibility of sampling an area of interest with high temporal and spatial resolution at low cost. This talk gives an overview about the main building blocks and maritime research missions of the ASV Roboat. This boat won several international competitions in robotic sailing in recent years and is therefore at the forefront of international excellence. The ASV Roboat has completed a several-day research mission in the Baltic Sea. By using a hydrophone attached to the boat's keel, the acoustic signals of a number of whales were recorded during the survey, and valuable information was collected on the presence of these animals in the study area. Robotic sailing represent a rapidly emerging technology for various tasks on lakes and oceans. The talk also features a discussion of the Roboat Routing world record attempt with CHR.

Confluence Analysis of CHR Programs (2 hours)
Hariolf Betz, Ulm University, Germany

Confluence is one of the most powerful properties in state transition systems. Confluence guarantees that programs can be executed concurrently and/or on incomplete input without influencing the outcome of the computation.

In this lecture, we will assess the following points:

Optimizing Compilation of CHR (2 hours)
Jon Sneyers, K.U.Leuven, Belgium

In this lecture we give an overview of the most important implementation techniques to obtain a CHR compiler that produces efficient target code. We will focus on CHR(Prolog) systems that compile CHR to Prolog, although most techniques are equally relevant in other host languages like Java. After introducing the basic compilation scheme, we discuss several optimizations, including constraint store indexing (attributed variables, hash tables), join ordering, passive occurrences, late storage, functional dependencies, guard reasoning, and propagation history elimination. We will identify a minimal set of optimizations needed to get a compiler that achieves the complexity-wise completeness property in terms of both time and space complexity

Source to Source Transformation for CHR (1 hour)
Nada Sharaf, German University in Cairo, Egypt

In this presentation, source-to-source transformation for visualizing CHR is discussed. Firstly, A newly implemented transformation tool is introduced. The tool aims at adding different visualization features to CHR programs. With this tool, it is possible to visualize the execution of the different CHR rules on a list of constraints or to visualize the constraints as geometric objects to see how the application of the rules affect them. In addition, with the presented approach, it is possible to visualize different data structures and algorithms such as visualizing sorting algorithms, Boolean algebra algorithms, and tree-searching algorithms.

Secondly, the transformation process is presented. Source-to-source transformation is used to avoid applying any changes to the compiler or the runtime system. The transformation process and scheme are discussed. Finally, different demonstrations of visualizing algorithms and CHR programs are presented.

Finally, different demonstrations of visualizing algorithms and CHR programs are presented.

Parallel Execution of CHR on a Graphical Processing Unit (1 hour)
Amira Zaki, Ulm University, Germany

Graphical Processing Units (GPUs) consist of hundreds of small cores, collectively operating to provide massive computation capabilities. The aim of this talk is present a means to utilize this technology to execute Constraint Handling Rules (CHR) which are inherently parallel. A translation scheme is defined to transform a subset of CHR to C++, then to use a GPU to fire the rules on all combinations of constraints. As proof of concept, the scheme was performed on several CHR examples which will be shown in the talk.