In exploratory domains, agents' actions map onto logs of behavior that include switching between activities, extraneous actions, and mistakes. These aspects create a challenging plan recognition problem. This paper presents a new algorithm for inferring students' activities in exploratory domains that is evaluated empirically using a new type of flexible and open-ended educational software for science education. Such software has been shown to provide a rich educational environment for students, but challenge teachers to keep track of students' progress and to assess their performance. The algorithm decomposes students’ complete interaction histories to create hierarchies of interdependent tasks that describe their activities using the software. It matches students' actions to a predefined grammar in a way that reflects that students solve problems in a modular fashion but may still interleave between their activities. The algorithm was empirically evaluated on people’s interaction with two separate software systems for simulating a chemistry laboratory and for statistics education. It was separately compared to the state-of-the-art recognition algorithms for each of the software. The results show that the algorithm was able to correctly infer students' activities significantly more often than the state-of-the-art, and was able to generalize to both of the software systems with no intervention.

Referring expressions such as “a long meeting” and “a restaurant near my brother’s” depend on information from the context to be accurately resolved. Interpreting these expressions requires pragmatic inferences that go beyond what the speaker said to what she meant; and to do this one must consider the speaker’s decisions with respect to her initial belief state and the alternative linguistic options she may have had. Modeling reference generation as a planning problem, where actions corre- spond to words that change a belief state, suggests that interpretation can also be viewed as recognizing belief- state plans that contain implicit actions. In this paper, we describe how planners can be adapted and used to interpret uncertain referring expressions.

Modern multi-core computers provide an opportunity to parallelize plan recognition algorithms to decrease runtime. Viewing the problem as one of parsing and performing a complete breadth first search, makes ELEXIR (Engine for LEXicalized Intent Recognition) (Geib '09, Geib '11) particularly suitable for such parallelism. This paper documents the extension of ELEXIR to utilize such modern computing platforms. We will discuss multiple possible algorithms for distributing work between parallel threads and the associated performance wins. We will show, that the best of these algorithms will provide close to linear speedup (up to a maximum number of processors), and that features of the problem domain have an impact on the speedup.

In many applications a user attempts to configure a complex object with many possible internal choices. Recommendation engines that automatically configure such objects given user preferences and constraints, may provide much value in such cases. These applications offer the user various methods to provide the input and generate appropriate recommendations. It is likely, though, that the user will not be able to fully express her preferences and constraints, requiring a phase of manual tuning of the recommended configuration. We suggest that following this manual revision, additional constraints and preferences can be automatically collected, and the recommended configuration can be automatically improved. Specifically, we suggest a recommender component that takes as input an initial manual configuration of a complex object, deduces certain user preferences and constraints from this configuration, and constructs an alternative configuration. We show an appealing application for our method in complex trip planning, and demonstrate its usability in a user study.

Exploring the conformational energy landscape of a molecule is an important but challenging problem because of the inherent complexity of this landscape. As part of this theme, various methods have been developed to compute transition paths between stable states of a molecule. Besides the methods classically used in biophysics/biochemistry, a recent approach originating from the robotics community has proven to be an efficient tool for conformational exploration. This approach, called the Transition-based RRT (T-RRT) is based on the combination of an effective path planning algorithm (RRT) with a Monte-Carlo-like transition test. In this paper, we propose an extension to TRRT based on a multi-tree approach, which we call Multi-T-RRT. It builds several trees rooted at different interesting points of the energy landscape and allows to quickly gain knowledge about possible conformational transition paths. We demonstrate this on the alanine dipeptide.

The Traveling Tournament Problem (TTP) is a well-known NP-complete problem in sports scheduling that was inspired by the application of optimizing schedules for Major League Baseball to reduce total team travel. The techniques and heuristics from the n-team TTP can be extended to optimize the scheduling of other sports leagues, such as the Nippon Professional Baseball (NPB) league in Japan. In this paper, we describe the additional scheduling constraints required by the NPB league, such as the requirement that each team play the same number of weekend home games, weekday home games, weekend road games, and weekday road games. We fully solve this TTP-variant for the case n=6, and conclude the paper by presenting the official 2013 NPB Central League Schedule, where we helped this Japanese baseball league reduce total team travel by over six thousand kilometres.

In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate. Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).

We present GOSMR ("goal oriented scenario modeling robots"), a cognitive architecture designed to show coordinated, goal-directed behavior over the Internet, focusing on the web browser as a case study. The architecture combines a variety of artificial intelligence techniques, including planning, temporal difference learning, elementary reasoning over uncertainty, and natural language parsing, but is designed to be computationally lightweight. Its intended use is to be deployed on virtual machines in large-scale network experiments in which simulated users' adaptation in the face of resource denial should be intelligent but varied. The planning system performs temporal difference learning of action times, discounts goals according to hyperbolic discounting of time-to-completion and chance of success, takes into account the assertions of other agents, and separates abstract action from site-specific affordances. Our experiment, in which agents learn to prefer a social networking style site for sending and receiving messages, shows that utility-proportional goal selection is a reasonable alternative to Boltzmann goal selection for producing a rational mix of behavior.

In this paper we apply AI planning to address the hypothesis exploration problem and provide assistance to network administrators in detecting malware based on unreliable observations derived from network traffic.Building on the already established characterization and use of AI planning for similar problems, we propose a formulation of the hypothesis generation problem for malware detection as an AI planning problem with temporally extended goals and actions costs. Furthermore, we propose a notion of hypothesis ``plausibility'' under unreliable observations, which we model as plan quality. We then show that in the presence of unreliable observations, simply finding one most ``plausible'' hypothesis, although challenging, is not sufficient for effective malware detection. To that end, we propose a method for applying a state-of-the-art planner within a principled exploration process, to generate multiple distinct high-quality plans. We experimentally evaluate this approach by generating random problems of varying hardness both with respect to the number of observations, as well as the degree of unreliability. Based on these experiments, we argue that our approach presents a significant improvement over prior work that are focused on finding a single optimal plan, and that our hypothesis exploration application can motivate the development of new planners capable of generating the top high-quality plans.

Commitments help model interactions in multiagent systems in a computationally realizable yet high-level manner without compromising the autonomy and heterogeneity of the member agents. Recent work shows how to combine commitments with goals and apply planning methods to enable agents to determine their actions. However, previous approaches to modeling commitments are confined to propositional representations, which limits their applicability in practical cases. We propose a first-order representation and reasoning technique that accommodates templatic commitments and goals that may be applied repeatedly with differing bindings for domain objects. Doing so not only leads to a more perspicuous modeling, but also supports many practical patterns.