Constraint programming is a successful technology for solving combinatorial problems modeled as constraint satisfaction problems (CSPs). Many real life problems come from uncertain and dynamic environments, which means that the initial description of the problem may change during its execution. In these cases, the solution found for a problem may become invalid. The search of robust solutions for dynamic CSPs (DynCSPs) has become an important issue in the field of constraint programming. In this paper we reformulate DynCSPs withlinear constraints as weighted CSPs (WCSPs), and we present an approach that searches for robust solutions in problems without associated information about possible future changes. Thus, the best solution for a modeled WCSP will be a robust solution for the original DynCSP.

The Resource-Constrained Project Scheduling Problem (RCPSP) and some of its extensions have been widely studied. Many approaches have been considered to solve this problem: constraint programming (CP), Boolean satisfiability (SAT), mixed integer linear programming (MILP), branch and bound algorithms (BB) and others. In this paper, we present a new approach for solving this problem: satisfiability modulo theories (SMT). Solvers for SMT generalize SAT solving by adding the ability to handle arithmetic and other theories. We provide several encodings of the RCPSP into SMT, and introduce rcp2smt, a tool for solving RCPSP instances using SMT solvers, which exhibits good performance.

The International Symposium on Abstraction, Reformulation and Approximation (SARA) series was established in 1994. It continues to provide a way for researchers to share results on ARA. The Ninth International Symposium on Abstraction, Reformulation and Approximation was held on July 17-18, 2011 at a renovated medieval castle in the Parador de Cardona hotel in Catalonia, Spain, about 60 miles northwest of Barcelona. This year the paper submissions came from four different continents and thirteen different countries. This volume contains all twenty of the papers that were accepted by the program committee for presentation at the symposium and publication in the proceedings.

This paper presents a training game intended to train crisis management teams to negotiate collaboratively in order to reach the group goal in the best way possible. The importance of the group goal in comparison to their individual goals is touched upon as well, as are various conflicts that can occur during such a negotiation. The game, which is implemented in the Blocks World 4 Teams environment, gives a team a specific scenario and allows them to negotiate a plan of action. This plan of action is then performed by agents, after which the team members will be debriefed on their performance. An experiment, containing multiple rounds to test the effect the game has on participants, is planned in the near future.

The better the team mental model, the better the teamwork. An important aspect of what determines a good team model is the extent to which the model is shared by the team members. This paper presents suggestions for measuring the extent to which teams have a shared mental model and describes how these measures are related to team performance. The most promising measures of sharedness proposed so far rely on using a compositional approach for team modeling and on a situation-sensitive relevance relation that indicates to what extent components contribute to team performance. A case study illustrates the approach and initial results on measuring performance when teams use different levels of sharedness.

For tasks that need to be accomplished in unconstrained environments, as in the case of Urban Search and Rescue (USAR), human-robot collaboration is considered as an indispensable component. Collaboration is based on accurate models of robot and human perception consistent with one another, so that exchange of information critical to the accomplishment of a task is performed efficiently and in a simplified fashion to minimize the interaction overhead. In this paper, we highlight the features of a human-robot team, i.e. how robot perception may be combined with human perception based on a task-driven direction for USAR. We elaborate on the design of the components of a mixed-initiative system wherein a task assigned to the robot is planned and executed jointly with the human operator as a result of their interaction. Our description is solidified by demonstrating the application of mixed-initiative planning in a number of examples related to the morphological adaptation of the rescue robot.

It is costly and time consuming to develop Multiple Choice Questions (MCQ) by hand. Using web-based resources to automate components of MCQ development would greatly benefit the education community through reducing reduplication of effort. Similar to many areas of Natural Language Processing (NLP), human-judged data is needed to train automated systems, but the majority of such data is proprietary. We present a graph-based representation for gathering training data from existing, web-based resources that increases access to such data and better directs the development of good questions.

This paper is about generating questions in human-robot interaction. We survey existing work on the forms and meanings of questions in English and discuss the pragmatic effects resulting from an interplay between the choice of syntactic form and intonation. We propose an approach to formalization based on a notion of common ground and commitment, set in a model of situated dialogue as part of collaborative activity where we explicitly model the beliefs and intentions of both the robot and the human. Questions come about by abductively inferring an intentional structure grounded in the belief model and indicating commitments. Content planning and surface realization turn this into a question of the appropriate form.

This paper shows that automatically generated questions can help classify children’s spoken responses to a reading tutor teaching them to generate their own questions. We use automatic question generation to model and classify children’s prompted spoken questions about stories. On distinguishing complete and incomplete questions from irrelevant speech and silence, a language model built from automatically generated questions out-performs a trigram language model that does not exploit the structure of questions.

In this paper we develop a model to simulate the evolution of a pollution-free resource gathering technology that is initially less efficient but ultimately reaches parity with polluting technology. We find that for low levels of pollution, pressure exerted by society can indeed encourage the development and use of non-polluting technology, with greater pressure being associated with faster achievement of efficiency parity and lower overall pollution. However, greater pressure is also associated with lower populations and at the highest levels of pressure there are significant risks of population crashes. We find that these results hold for both localized pollution and globalized pollution, with globalized pollution encouraging faster achievement of efficiency parity. For high levels of pollution we find that introducing societal pressure significantly increases the occurrence of population crashes, and thus the strategy is only effective under certain conditions.