We examine the suitability of using decision processes to model real-world systems of intelligent adversaries. Decision processes have long been used to study cooperative multiagent interactions, but their practical applicability to adversarial problems has received minimal study. We address the pros and cons of applying sequential decision-making in this area, using the crime of money laundering as a specific example. Motivated by case studies, we abstract out a model of the money laundering process, using the framework of interactive partially observable Markov decision processes (I-POMDPs). We address why this framework is well suited for modeling adversarial interactions. Particle filtering and value iteration are used to solve the model, with the application of different pruning and look-ahead strategies to assess the tradeoffs between solution quality and algorithmic run time. Our results show that there is a large gap in the level of realism that can currently be achieved by such decision models, largely due to computational demands that limit the size of problems that can be solved. While these results represent solutions to a simplified model of money laundering, they illustrate nonetheless the kinds of agent interactions that cannot be captured by standard approaches such as anomaly detection. This implies that I-POMDP methods may be valuable in the future, when algorithmic capabilities have further evolved.

Human experts in scientific fields routinely work with evidence that is noisy and untrustworthy, heuristics that are unproven, and possible conclusions that are contradictory. We present a fully implemented AI system, Calvin, for cosmogenic isotope dating, a domain that is fraught with these difficult issues. Calvin solves these problems using an argumentation framework and a system of confidence that uses two-dimensional vectors to express the quality of heuristics and the applicability of evidence. The arguments it produces are strikingly similar to published expert arguments. Calvin is in daily use by isotope dating experts.

Military course-of-action (COA) diagrams are used to depict battle scenarios and include thousands of unique symbols, complete with additional textual and designator modifiers. We have created a real-time sketch recognition interface that recognizes 485 freely-drawn military course-of-action sym- bols. When the variations (not allowable by other systems) are factored in, our system is several orders of magnitude larger than the next biggest system. On 5,900 hand-drawn symbols, the system achieves an accuracy of 90% when con- sidering the top 3 interpretations and requiring every aspect of the shape (variations, text, symbol, location, orientation) to be correct.

Demand and capacity imbalances in the US national airspace are resolved using traffic management initiatives designed, in current operations, with little collaboration with the airspace users. NASA and its partners have developed a new collaborative concept of operations that requires the users and airspace service provider to work together to choose initiatives that better satisfy the business needs of the users while also ensuring safety to the same standard as today. In this paper, we describe an approach to implementing this concept through a software negotiation framework underpinned by technology developed in the artificial intelligence community. We describe our exploration of peer-to-peer negotiation and how the number of conversation threads and the time sensitivity of offer acceptance led us to a centralized approach. The centralized approach uses hill climbing to evaluate airport slot allocations from a user perspective and a linear programming solver to seek solutions compatible across the user community. Our experiments with full sized problems identify the potential operational benefits as well as limitations, and where future research needs to be focused.

Document clustering has been applied in web information retrieval, which facilitates users’ quick browsing by organizing retrieved results into different groups. Meanwhile, a tree-like hierarchical structure is wellsuited for organizing the retrieved results in favor of web users. In this regard, we introduce a new method for hierarchical clustering of web snippets by exploiting a phrase-based document index. In our method, a hierarchy of web snippets is built based on phrases instead of all snippets, and the snippets are then assigned to the corresponding clusters consisting of phrases. We show that, as opposed to the traditional hierarchical clustering, our method not only presents meaningful cluster labels but also improves clustering performance.

Automatically constructing novel representations of tasks from analysis of state spaces is a longstanding fundamental challenge in AI. I review recent progress on this problem for sequential decision making tasks modeled as Markov decision processes. Specifically, I discuss three classes of representation discovery problems: finding functional, state, and temporal abstractions. I describe solution techniques varying along several dimensions: diagonalization or dilation methods using approximate or exact transition models; reward-specific vs reward-invariant methods; global vs. local representation construction methods; multiscale vs. flat discovery methods; and finally, orthogonal vs. redundant representa- tion discovery methods. I conclude by describing a number of open problems for future work.

The paper presents an investigation of the use of two alternative forms of CNF formulae—prime implicates and minimal CNF—to compactly represent belief states in the context of conformant planning. For each representation, we define a transition function for computing the successor belief state resulting from the execution of an action in a belief state; results concerning soundness and completeness are provided. The paper describes a system (PIP) which dynamically selects either of these two forms to represent belief states, and an experimental evaluation of PIP against state-of-the-art conformant planners. The results show that PIP has the potential of scaling up better than other planners in problems rich in disjunctive information about the initial state.

Existing controller-based approaches for centralized and decentralized POMDPs are based on automata with output known as Moore machines. In this paper, we show that several advantages can be gained by utilizing another type of automata, the Mealy machine. Mealy machines are more powerful than Moore machines, provide a richer structure that can be exploited by solution methods, and can be easily incorporated into current controller-based approaches. To demonstrate this, we adapted some existing controller-based algorithms to use Mealy machines and obtained results on a set of benchmark domains. The Mealy-based approach always outperformed the Moore-based approach and often outperformed the state-of-the-art algorithms for both centralized and decentralized POMDPs. These findings provide fresh and general insights for the improvement of existing algorithms and the development of new ones.

In this paper, we propose a generative model to automatically discover the hidden associations between topics words and opinion words. By applying those discovered hidden associations, we construct the opinion scoring models to extract statements which best express opinionists’ standpoints on certain topics. For experiments, we apply our model to the political area. First, we visualize the similarities and dissimilarities between Republican and Democratic senators with respect to various topics. Second, we compare the performance of the opinion scoring models with 14 kinds of methods to find the best ones. We find that sentences extracted by our opinion scoring models can effectively express opinionists’ standpoints.

Auctions are promising decentralized methods for teams of agents to allocate and re-allocate tasks among themselves in dynamic, partially known and time-constrained domains with positive or negative synergies among tasks. Auction-based coordination systems are easy to understand, simple to implement and broadly applicable. They promise to be efficient both in communication (since agents communicate only essential summary information) and in computation (since agents compute their bids in parallel). Artificial intelligence research has explored auction-based coordination systems since the early work on contract networks, mostly from an experimental perspective. This overview paper describes our recent progress towards creating a framework for the design and analysis of cooperative auctions for agent coordination.