"The Crossword puzzle (CP) is a simple problem to illustrate the formalization process of a problem into a CSP. The problem is to place words of a dictionary in a given structure satisfying certain constraints. The variables are the rows and columns in the crossword, and their values are the words in a dictionary."
– Marc Torrens. An Application using the JCL: The Air Travel Planning System. Diploma Thesis, 1997, Chapter 1, Section 1.2.1.
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.
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.
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.
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.
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).
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?