Constraint-Based Reasoning


The CP'98 Workshop on Constraint Problem Reformulation

AI Magazine

Roughly 30 people attended this workshop. This article summarizes the papers presented at the workshop and highlights some of the questions and issues raised during the discussion. The task of selecting the best representation for solving a problem by means of automatically reformulating the problem is a core challenge in AI. Saul Amarel (1968) outlined the impact of different representations of the missionaries and cannibals problem on the performance of the algorithms used to solve the problem. He also proposed automating the reformulation process and, consequently, the process of selecting representations: The general problem of representation is concerned with the relationship between different ways of formulating a problem to a problem solving system and the efficiency with which the system can be expected to find a solution to the problem.


Articles

AI Magazine

The symposium took place in July 2009 in Lake Arrowhead, California. Consequently, ARA techniques have been studied in various subfields in AI and related disciplines and have been used in various settings including automated reasoning, cognitive modeling, constraint programming, design, diagnosis, machine learning, model-based reasoning, planning, reasoning, scheduling, search, theorem proving, and intelligent tutoring. The considerable interest in ARA techniques and the great diversity of the researchers involved had led to work on ARA being presented at many different venues. Consequently, there was a need to have a single forum where researchers of different backgrounds and disciplines could discuss their work on ARA. As a result, the Symposium on Abstraction, Reformulation, and Approximation (SARA) was established in 1994 after a series of workshops in 1988, 1990, and 1992.


Stand-Allocation System (SAS)

AI Magazine

The system ensures a high standard of quality in customer service, airport safety, and use of stand resources. This article describes our experience in developing an AI system using standard off-the-shelf software components. Although there were some initial hitches when the new airport opened on 6 July 1998, operations quickly returned to normal within a week's time. Within a month, operational statistics surpassed those of the old airport--80 percent of all flights were on time or within 15 minutes of schedule, all passengers cleared immigration within 15 minutes, and average baggage waiting time was only 10 minutes. During the 1998 Christmas holiday, HKIA serviced about 100,000 passengers daily and maintained equally high service standards.


Principles of Constraint Programming and Constraint Processing: A Review

AI Magazine

You wait forever for one to come along, and then two come along at once. In this case, there has been a large gap in the market for a theoretical introduction to constraint programming ever since Edward Tsang's Foundations of Constraint Satisfaction (1993) went out of print. Therefore, we are very pleased to see two books written by two of the leading researchers in this field come along to fill the gap. Constraint programming is a very active research area within AI. It is a highly successful technology for solving a wide range of combinatorial problems, including scheduling, rostering, assignment, routing, and design. A number of companies, like ILOG, Dash Optimization, and Parc Technologies, market model building and constraint programming toolkits, which are used by companies as diverse as Amazon.com, Constraint programming is a declarative style of modeling combinatorial problems in which the user identifies the decision variables, their possible domain of values, and specifies constraints over the allowed values (for example, no two of these variables can take the same value). Sophisticated but general purpose AI search techniques like constraint propagation (to prune irrelevant parts of the search tree) and dependency directed backtracking can then be used to find solutions. Given the many advances made in constraint programming over the last decade, a new text would have been needed even if Edward Tsang's book had remained in print. These two new texts are written by two of the leading researchers in this field. Principles of Constraint Programming by Krzysztof Apt contains chapters that cover topics like local consistency, constraint propagation, linear equations, interval reasoning, and search. Constraint Processing by Rina Dechter covers similar ground but also has chapters that cover topics like local search, tree decomposition methods, optimization, and probabilistic networks more extensively. Dechter's book also contains a chapter by David Cohen and Peter Jeavons on tractability and one by Francesca Rossi on constraint logic programming. There is much in common between the two books. This is perhaps not so surprising since Krzysztof Apt thanks Rina Dechter for much useful discussion that helped him enter the field and start doing research in the area.


Spar: A Planner That Satisfies Operational and Geometric Goals in Uncertain Environments

AI Magazine

A prerequisite for intelligent behavior is the ability to reason about actions and their effects. This ability is the essence of the classical AI planning problem in which plans are constructed by reasoning about how available actions can be applied to achieve various goals. For this reasoning process to occur, the planner must be aware of its available actions, the situations in which they are applicable, and the changes affected in the world by their execution. Classical AI planners typically use a highlevel, symbolic representation of actions (for example, well-formed formulas from predicate calculus). Although this type of representational scheme is attractive from a computational standpoint, it cannot adequately represent the intricacies of a domain that includes complex actions, such as robotic assembly (consider, for example, that any geometric configuration of the robotic manipulator is a rather complex function of six joint angles).


Model-Based Computing for Design and Control of Reconfigurable Systems

AI Magazine

Complex electromechanical products, such as high-end printers and photocopiers, are designed as families, with reusable modules put together in different manufacturable configurations, and the ability to add new modules in the field. The modules are controlled locally by software that must take into account the entire configuration. This poses two problems for the manufacturer. The first is how to make the overall control architecture adapt to, and use productively, the inclusion of particular modules. The second is to decide, at design time, whether a proposed module is a worthwhile addition to the system: will the resulting system perform enough better to outweigh the costs of including the module?


Report on the SAT 2007 Conference on Theory and Applications of Satisfiability Testing

AI Magazine

The SAT Conference on Theory and Applications of Satisfiability Testing was held in Lisbon, Portugal, 28-31 May 2007. The conference, which attracted a record-breaking 80 participants, featured 34 papers and two invited presentations. The venue also included the SAT competition, the QBF evaluation, the PB evaluation, and the MAX-SAT evaluation. Moreover, SAT and extensions of SAT find many practical applications, including planning, software and hardware model checking, bioinformatics, equivalence check ing, test-pattern generation, software package installation, and cryptography. The annual SAT conference is now widely recognized as "the venue" for AI Magazine Volume 28 Number 4 (2007) ( AAAI) This year marked the tenth SAT meeting.


Representing and Reasoning with Preferences

AI Magazine

I consider how to represent and reason with users' preferences. While areas of economics like social choice and game theory have traditionally considered such topics, I will argue that computer science and artificial intelligence bring some fresh perspectives to the study of representing and reasoning with preferences. For instance, I consider how we can elicit preferences efficiently and effectively. With one agent, the agent's desired goal may not be feasible. The agent wants a cheap, low-mileage Ferrari, but no such car exists.


Preferences in Constraint Satisfaction and Optimization

AI Magazine

We review constraint-based ap - proaches to handle preferences. We start by defining the main notions of constraint programming and then give various concepts of soft constraints and show how they can be used to model quantitative preferences. We then consider how soft constraints can be adapted to handle other forms of preferences, such as bipolar, qualitative, and temporal preferences. Finally, we describe how AI techniques such as abstraction, explanation generation, machine learning, and preference elicitation can be useful in modeling and solving soft constraints. Intuitively, constraints are restrictions on the possible scenarios.


Preference Handling for Artificial Intelligence

AI Magazine

This editorial explains the benefits of preferences for AI systems and draws a picture of current AI research on preference handling. It thus provides an introduction to the topics covered by this special issue on preference handling. To act autonomously, the systems must choose among different actions and means of expression; to intelligently support humans' actions, they must understand and respond to the humans' choices. It is a natural assumption that agents who are acting in the world are experiencing the consequences of their actions and are not indifferent with respect to those experiences. An autonomous system such as a Mars rover can experience the consequences of moving along a path by measuring the energy consumption after the move, which will depend on the difficulty of the chosen path, and then judge whether the path was good or bad.