We consider a cross-cultural interaction scenario where a group of soldiers assisted by robots interact with local vendors in a market place. We develop a model to quantify, analyze and predict the perception of the actions of the soldiers and the robot by the local population. The model assumes that humans are considering collections of concrete and intangible values which are not, in general, directly and linearly convertible into each other. We argue that satisfactory modeling accuracy can be achieved by restricting the considered intangibles to a small set of {\em culture sanctioned social values}. For these values, the culture provides a name, calculation methods, as well as associated rules of conduct. We validate our model by comparing the predicted values with the judgment of a large group of human observers cognizant of the modeled culture. We use the model to evaluate the tradeoffs between several long term strategies to maintain security as well as to increase the trust and goodwill of the local population.

For many classification problems, genetic algorithms prove to be effective without extensive domain engineering. However, the chess King-Rook-King endgame problem appears to be an exception. We explore whether modifications to a baseline parallel genetic algorithm can improve the accuracy on this particular problem. After describing the problem domain and our implementation of a parallel genetic algorithm, we present an empirical evaluation of several approaches intended to improve overall performance. Our results confirm the challenging nature of this domain. We describe several directions that may yet deliver significant improvements.

We present a framework to represent and reason about nar- ratives. We build a symbolic probabilistic representation of the temporal sequence of world states and events implied by a narrative using statistical approaches. We show that the combination of this representation together with domain knowledge and symbolic probabilistic reasoning algorithms enables understanding of a narrative and answering semantic questions whose responses are not contained in the narrative. In our experiments, we show the power of our framework (vs. traditional approaches) in answering semantic questions for two domains of RoboCup soccer commentaries and early reader children stories focused on spatial contexts.

When analysing social media conversations, in search of the public opinion about an unfolding event that is be- ing discussed in real-time (e.g., presidential debates, major speeches, etc.), it is important to distinguish between two groups of participants: opinion-makers and opinion-holders. To address this problem, we propose a supervised machine-learning approach, which uses inexpensively acquired labeled data from monothematic Twitter accounts to learn a binary classifier for the labels “political account” (opinion-makers) and “non-political account” (opinion-holders). While the classifier has a 83% accuracy on individual tweets, when applied to the last 200 tweets from accounts of a set of 1000 Twitter users, it classifies accounts with a 97% accuracy. This high accuracy derives from our decision to incorporate information about classifier probability into the classification. Our work demonstrates that machine learning algorithms can play a critical role in improving the quality of social media analytics and understanding, whose importance is increasing as social media adoption becomes widespread.

Many exponentially-hard problems can be solved by searching through a space of states to determine a sequence of steps constituting a solution. Algorithms that produce optimal solutions (e.g., shortest path) generally require greater computational resources (e.g., time) than their sub-optimal counterparts. Consequently, many optimal algorithms cannot produce any usable solution when the amount of time available is limited or hard to predict in advance. Anytime algorithms address this problem by initially finding a suboptimal solution very quickly and then generating incrementally better solutions with additional time, effectively providing the best solution generated so far anytime it is required. In this research, we generate initial solutions cheaply using a fast search algorithm. We then improve this low-quality solution by identifying subsequences of steps that appear, based on heuristic estimates, to be considerably longer than necessary. Finally, we perform a more expensive search between the endpoints of each subsequence to find a shorter connecting path. We will show that this improves the overall solution incrementally over time while always having a valid solution to return whenever time runs out. We present results that demonstrate in several problem domains that AIRS (Anytime Iterative Refinement of a Solution) rivals other widely used and recognized anytime algorithms and also produces results comparable to other popular (but not anytime) heuristic algorithms such as Bidirectional A* search.

Automated planning is a well studied research topic thanks to its wide range of real-world applications. Despite significant progress in this area many planning problems still remain hard and challenging. Some techniques such as learning macro-operators improve the planning process by reformulating the (original) planning problem. While many encouraging practical results have been derived from such reformulation methods, little attention has been paid to the theoretical properties of reformulation such as soundness, completeness, and algorithmic complexity. In this paper we build up a theoretical framework describing reformulation schemes such as action elimination or creating macro-actions. Using this framework, we show that finding entanglements (relationships useful for action elimination) is as hard as planning itself. Moreover, we design a tractable algorithm for checking under what conditions it is safe to reformulate a problem by removing primitive operators (assembled to a macro-operator).

In this paper, we present a novel approach NL2OCL to translate English specification of constraints to formal constraints such as OCL (Object Constraint language). In the used approach, input English constraints are syntactically and semantically analyzed to generate a SBVR (Semantics of Business Vocabulary and Rules) based logical representation that is finally mapped to OCL. During the syntactic and semantic analysis we have also addressed various syntactic and semantic ambiguities that make the presented approach robust. The presented approach is implemented in Java as a proof of concept. A case study has also been solved by using our tool to evaluate the accuracy of the presented approach. The results of evaluation are also compared to the pattern based approach to highlight the significance of the used approach.

Maritime threat detection is a challenging problem because maritime environments can involve a complex combination of concurrent vessel activities, and only a small fraction of these may be irregular, suspicious, or threatening. Previous work on this task has been limited to analyses of single vessels using simple rule-based models that alert watchstanders when a proximity threshold is breached. We claim that Probabilistic Graphical Models (PGMs) can be used to more effectively model complex maritime situations. In this paper, we study the performance of PGMs for detecting (small boat) maritime attacks. We describe three types of PGMs that vary in their representational expressiveness and evaluate them on a threat recognition task using track data obtained from force protection naval exercises involving unmanned sea surface vehicles. We found that the best-performing PGMs can outperform the deployed rule-based approach on these tasks, though some PGMs require substantial engineering and are computationally expensive.

Bill Swartout Introduced by Alan Kay at XEROX PARC in the 1970's, the desktop metaphor, which was later adopted in the Macintosh and Windows operating systems, has become the primary way we think about interacting with computers. Over the last decade, we have been developing sophisticated virtual humans at the USC Institute for Creative Technologies.

Chairs and committees of the FLAIRS-25 conference.