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.

The current study investigates the relationship between children’s curiosity and question asking ability. Generation of two types of questions was assessed: identification (yes/no questions asked to identify a target from an array) and understanding questions, asked to learn more about a topic. The latter was related to children’s curiosity, as was the ability to recognize the effectiveness of questions in solving a mystery. Training on asking identification questions was effective in improving children’s ability to ask that type of question, but did not transfer to the other task. Training on asking understanding questions was not successful. Children’s curiosity did not influence the effectiveness of the training.

This paper discusses the implementation and evaluation of automatically generated cloze questions in the style of the definitions found in Collins COBUILD English language learner’s dictionary. The definitions and the cloze questions are used in an automated reading tutor to help second and third grade students learn new vocabulary. A parser provides syntactic phrase structure trees for the definitions. With these parse trees as input, a pattern matching program uses a set of syntactic patterns to extract the phrases that make up the cloze question answers and distracters.

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.