Diverse planning consists of generating multiple different solutions for the same planning problem. I explore solution diversity, based on quantitative (domain-independent) and qualitative (domain-dependent) distance metrics, in deterministic and nondeterministic planning domains.

Goal-driven autonomy (GDA) is a conceptual model for creating an autonomous agent that monitors a set of expectations during plan execution, detects when discrepancies occur, builds explanations for the cause of failures, and formulates new goals to pursue when planning failures arise. While this framework enables the development of agents that can operate in complex and dynamic environments, implementing the logic for each of the subtasks in the model requires substantial domain engineering. We present a method using case-based reasoning and intent recognition in order to build GDA agents that learn from demonstrations. Our approach reduces the amount of domain engineering necessary to implement GDA agents and learns expectations, explanations, and goals from expert demonstrations. We have applied this approach to build an agent for the real-time strategy game StarCraft. Our results show that integrating the GDA conceptual model into the agent greatly improves its win rate.

We consider the detection of activations over graphs under Gaussian noise, where signals are piece-wise constant over the graph. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with proveable theoretical guarantees for general graph topologies. We cast this as a hypothesis testing problem, and first provide a universal necessary condition for asymptotic distinguishability of the null and alternative hypotheses. We then introduce the spanning tree wavelet basis over graphs, a localized basis that reflects the topology of the graph, and prove that for any spanning tree, this approach can distinguish null from alternative in a low signal-to-noise regime. Lastly, we improve on this result and show that using the uniform spanning tree in the basis construction yields a randomized test with stronger theoretical guarantees that in many cases matches our necessary conditions. Specifically, we obtain near-optimal performance in edge transitive graphs, $k$-nearest neighbor graphs, and $\epsilon$-graphs.

Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on R^d. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this distance converges to an unpleasant distance function on the underlying space whose properties are detrimental to machine learning. We also study the behavior of the shortest path distance in weighted kNN graphs.

Diabetes management is a difficult task for patients, who must monitor and control their blood glucose levels in order to avoid serious diabetic complications. It is a difficult task for physicians, who must manually interpret large volumes of blood glucose data to tailor therapy to the needs of each patient. This paper describes three emerging applications that employ AI to ease this task: (1) case-based decision support for diabetes management; (2) machine learning classification of blood glucose plots; and (3) support vector regression for blood glucose prediction. The first application provides decision support by detecting blood glucose control problems and recommending therapeutic adjustments to correct them. The second provides an automated screen for excessive glycemic variability. The third aims to build a hypoglycemia predictor that could alert patients to dangerously low blood glucose levels in time to take preventive action. All are products of the 4 Diabetes Support SystemTM project, which uses AI to promote the health and wellbeing of people with type 1 diabetes. These emerging applications could potentially benefit 20 million patients who are at risk for devastating complications, thereby improving quality of life and reducing health care cost expenditures.

Fast approximate nearest neighbor (NN) search in large databases is becoming popular. Several powerful learning-based formulations have been proposed recently. However, not much attention has been paid to a more fundamental question: how difficult is (approximate) nearest neighbor search in a given data set? And which data properties affect the difficulty of nearest neighbor search and how? This paper introduces the first concrete measure called Relative Contrast that can be used to evaluate the influence of several crucial data characteristics such as dimensionality, sparsity, and database size simultaneously in arbitrary normed metric spaces. Moreover, we present a theoretical analysis to prove how the difficulty measure (relative contrast) determines/affects the complexity of Local Sensitive Hashing, a popular approximate NN search method. Relative contrast also provides an explanation for a family of heuristic hashing algorithms with good practical performance based on PCA. Finally, we show that most of the previous works in measuring NN search meaningfulness/difficulty can be derived as special asymptotic cases for dense vectors of the proposed measure.

The increasingly prevalent view that recommendation is a conversation between user and system is driving a renewed interest in approaches to system design that involve the user in meaningful ways. In addition to this the proliferation of mobile devices and the near-ubiquity of sensing technologies means that there are now many opportunities to capture real-life experiences, in real-time, providing a new source of raw material for case-based reasoning. In this paper we consider the availability of real-world exercise information, in this cases corresponding to jogging routes, and meth- ods by which we can involve a user in recommending such routes. We describe the Exercise Builder, a proof-of-concept application that attempts to help visitors to a new city to plan their jogging routes by combining case retrieval, interactive adaptation, and multimedia explanation in a single online service.

Conversational case-based reasoning systems use an interactive dialog to retrieve stored cases. Normally the ordering of questions in this dialog is chosen based only on their discriminativeness. However, because the user may not be able to answer all questions, even highly discriminative questions are not guaranteed to provide information. This paper presents a customization method CCBR systems can apply to adjust entropy-based discriminativeness considerations by predictions of user ability to answer questions. The method uses a naive Bayesian classifier to classify users into user groups based on the questions they answer, applies information from group profiles to predict which future questions they are likely to be able to answer, and selects the next questions to ask based on a combination of information gain and response likelihood. The method was evaluated for a mix of simulated user groups, each associated with particular probabilities for answering questions about each case indexing feature, in four sample domains. For simulated users with varying abilities to answer particular questions, results showed improvement in dialog length over a non-customized entropy-based approach in all test domains.

Over the past 11 years, this FLAIRS special track program has provided a focal point for the North American case-based reasoning (CBR) community, though it has drawn good international participation as well. Five papers were accepted this year. Ontañón presents seven different case acquisition techniques for CBR systems that use learning from demonstration and performs a comparative evaluation in the context of real-time strategy games. Ontañón and Plaza describe a preliminary formal model of knowledge transfer in case-based inference based on the idea of partial unification. Jalali and Leake present a new approach for ordering questions in conversational CBR systems that takes into account not just their discriminativeness but also the user's ability to answer.

Real-time Strategy (RTS) games are complex domains which are a significant challenge to both human and artificial intelligence (AI). For that reason, and although many AI approaches have been proposed for the RTS game AI problem, the AI of all commercial RTS games is scripted and offers a very static behavior subject to exploits. In this paper, we will focus on a case-based reasoning (CBR) approach to this problem, and concentrate on the process of case-acquisition. Specifically, we will describe 7 different techniques to automatically acquire plans by observing human demonstrations and compare their performance when using them in the Darmok 2 system in the context of an RTS game.