Cooperative path-finding can be abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. This work proposes a fast algorithm that can provide completeness guarantees for a general class of problems without any assumptions about the graph's topology. Specifically, the approach can address any solvable instance where there are at most n-2 agents in a graph of size n. The algorithm employs two primitives: a "push" operation where agents move towards their goals up to the point that no progress can be made, and a "swap" operation that allows two agents to swap positions without altering the configuration of other agents. Simulated experiments are provided on hard instances of cooperative path-finding, including comparisons against alternative methods. The results are favorable for the proposed algorithm and show that the technique scales to problems that require high levels of coordination, involving hundreds of agents.

We consider settings in which a semi-autonomous agent has uncertain knowledge about its environment, but can ask what action the human operator would prefer taking in the current or in a potential future state. Asking queries can improve behavior, but if queries come at a cost (e.g., due to limited operator attention), the value of each query should be maximized. We compare two strategies for selecting action queries: 1) based on myopically maximizing expected gain in long-term value, and 2) based on myopically minimizing uncertainty in the agent's policy representation. We show empirically that the first strategy tends to select more valuable queries, and that a hybrid method can outperform either method alone in settings with limited computation.

Poor quality data is a growing and costly problem that affects many enterprises across all aspects of their business ranging from operational efficiency to revenue protection. In this paper, we present an application -- Data Quality Rules Accelerator (DQRA) -- that accelerates Data Quality (DQ) efforts (e.g. data profiling and cleansing) by automatically discovering DQ rules for detecting inconsistencies in data. We then present two evaluations. The first evaluation compares DQRA to existing solutions; and shows that DQRA either outperformed or achieved performance comparable with these solutions on metrics such as precision, recall, and runtime. The second evaluation is a case study where DQRA was piloted at a large utilities company to improve data quality as part of a legacy migration effort. DQRA was able to discover rules that detected data inconsistencies directly impacting revenue and operational efficiency. Moreover, DQRA was able to significantly reduce the amount of effort required to develop these rules compared to the state of the practice. Finally, we describe ongoing efforts to deploy DQRA.

Video games are increasingly producing huge datasets available for analysis resulting from players engaging in interactive environments. These datasets enable investigation of individual player behavior at a massive scale, which can lead to reduced production costs and improved player retention. We present an approach for modeling player retention in Madden NFL 11, a commercial football game. Our approach encodes gameplay patterns of specific players as feature vectors and models player retention as a regression problem. By building an accurate model of player retention, we are able to identify which gameplay elements are most influential in maintaining active players. The outcome of our tool is recommendations which will be used to influence the design of future titles in the Madden NFL series.

For large scale enterprise implementations, a key problem, that has not been tackled much, is the ability to automatically map users’ requirements to reference process models. We present a tool called Process Model Requirements Gap Analyzer (ProcGap), which uses a combination of natural language processing, information retrieval and semantic reasoning to automatically match and map textual requirements to industry-specific process models. We present the results of mapping requirements from an industry project to an existing process model. We compare our approach to two previously implemented approaches and show that our approach outperforms them. In a case study, we also found that a user group with ProcGap had better performance than a user group that performed the same task manually.

Recently, geospatial abduction was introduced by the authors in [Shakarian et. al. 2010] as a way to infer unobserved geographic phenomena from a set of known observations and constraints between the two. In this paper, we introduce the SCARE-S2 software tool which applies geospatial abduction to the environment of Afghanistan. Unlike previous work, where we looked for small weapon caches supporting local attacks, here we look for insurgent high-value targets (HVT's), supporting insurgent operations in two provinces. These HVT's include the locations of insurgent leaders and major supply depots. Applying this method of inference to Afghanistan introduces several practical issues not addressed in previous work. Namely, we are conducting inference in a much larger area (24,940 sq km as compared to 675 sq km in previous work), on more varied terrain, and must consider the influence of many local tribes. We address all of these problems and evaluate our software on 6 months of real-world counter-insurgency data. We show that we are able to abduce regions of a relatively small area (on average, under 100 sq km and each containing, on average, 4.8 villages) that are more dense with HVT's (35 X more than the overall area considered).

This paper describes a system to help intelligence analysts track and analyze information being published in multiple sources, particularly open sources on the Web. The system integrates technology for Web harvesting, natural language extraction, and network analytics, and allows analysts to view and explore the results via a Web application. One of the difficult problems we address is the entity resolution problem, which occurs when there are multiple, differing ways to refer to the same entity. The problem is particularly complex when noisy data is being aggregated over time, there is no clean master list of entities, and the entities under investigation are intentionally being deceptive. Our system must not only perform entity resolution with noisy data, but must also gracefully recover when entity resolution mistakes are subsequently corrected. We present a case study in arms trafficking that illustrates the issues, and describe how they are addressed.

We report on an emerging application focused on the design of resilient long reach passive optical networks using combinatorial optimisation techniques. The objective of the application is to determine the optimal position and capacity of a set of metro nodes. We specifically consider dual parented networks whereby each customer must be associated with two metro nodes. An important property of such a placement is resilience to single node failure. Therefore excess capacity should be provided at each metro node in order to ensure that customers can be redistributed amongst the metro sites. Our application, as well as finding optimal node placements, can compute the minimum level of excess capacity on all metro nodes. In this paper we present three alternative approaches to optimal metro node placement.We present a detailed analysisof the impact of different placement approaches on the distribution of excess capacity throughout the network. We show that preferential distributions occur in practice, based on a case-study in Ireland. Finally we show that load and excess capacity provision are independent of each other.

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 and shares difficulties encountered in transitioning AI technology from university researchers to patients and physicians.

Due to the rapid aging of the population, many technical solutions for the care of the elderly are being developed, often involving fall detection with accelerometers. We present a novel approach to fall detection with location sensors. In our application, a user wears up to four tags on the body whose locations are detected with radio sensors. This makes it possible to recognize the user’s activity, including falling any lying afterwards, and the context in terms of the location in the apartment. We compared fall detection using location sensors, accelerometers and accelerometers combined with the context. A scenario consisting of events difficult to recognize as falls or non-falls was used for the comparison. The accuracy of the methods that utilized the context was almost 40 percentage points higher compared to the methods without the context. The accuracy of pure location-based methods was around 10 percentage points higher than the accuracy of accelerometers combined with the context.