Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.

Advancing AI Research and Applications by Learning from What Went Wrong and Why

Humans learn from their mistakes. When things go badly, we notice that something is amiss, figure out what went wrong and why, and attempt to repair the problem. Artificial systems depend on their human designers to program in responses to every eventuality and therefore typically don’t even notice when things go wrong, following their programming over the proverbial, and in some cases literal, cliff. This article describes our past and current work on the Meta-Cognitive Loop, a domain-general approach to giving artificial systems the ability to notice, assess, and repair problems. The goal is to make artificial systems more robust and less dependent on their human designers.

This special issue of AI Magazine is dedicated to the proposition that problems populate the path to insight, implying the experiences and lessons learned should be shared.

In this paper, we show that a continuous spectrum of randomisation exists, in which most existing tree randomisations are only operating around the two ends of the spectrum. That leaves a huge part of the spectrum largely unexplored. We propose a base learner VR-Tree which generates trees with variable-randomness. VR-Trees are able to span from the conventional deterministic trees to the complete-random trees using a probabilistic parameter. Using VR-Trees as the base models, we explore the entire spectrum of randomised ensembles, together with Bagging and Random Subspace. We discover that the two halves of the spectrum have their distinct characteristics; and the understanding of which allows us to propose a new approach in building better decision tree ensembles. We name this approach Coalescence, which coalesces a number of points in the random-half of the spectrum. Coalescence acts as a committee of ``experts'' to cater for unforeseeable conditions presented in training data. Coalescence is found to perform better than any single operating point in the spectrum, without the need to tune to a specific level of randomness. In our empirical study, Coalescence ranks top among the benchmarking ensemble methods including Random Forests, Random Subspace and C5 Boosting; and only Coalescence is significantly better than Bagging and Max-Diverse Ensemble among all the methods in the comparison. Although Coalescence is not significantly better than Random Forests, we have identified conditions under which one will perform better than the other.

Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function Q* is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from Q*. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function Q*. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.

We propose a framework for analyzing and comparing distributions, allowing us to design statistical tests to determine if two samples are drawn from different distributions. Our test statistic is the largest difference in expectations over functions in the unit ball of a reproducing kernel Hilbert space (RKHS). We present two tests based on large deviation bounds for the test statistic, while a third is based on the asymptotic distribution of this statistic. The test statistic can be computed in quadratic time, although efficient linear time approximations are available. Several classical metrics on distributions are recovered when the function space used to compute the difference in expectations is allowed to be more general (eg. a Banach space). We apply our two-sample tests to a variety of problems, including attribute matching for databases using the Hungarian marriage method, where they perform strongly. Excellent performance is also obtained when comparing distributions over graphs, for which these are the first such tests.

In this editorial we introduce the articles published in this special AI Magazine issue on innovative applications of artificial intelligence. Discussed are a pick-pack-and-ship warehouse-management system, a neural network in the fishing industry, the use of AI to help mobile phone users, building business rules in the mortgage lending business, automating the processing of immigration forms, and the use of the semantic web to provide access to observational datasets.

The Association for the Advancement of Artificial Intelligence presented the 2007 Fall Symposium Series on Friday through Sunday, November 9–11, at the Westin Arlington Gateway, Arlington, Virginia. The titles of the seven symposia were (1) AI and Consciousness: Theoretical Foundations and Current Approaches, (2) Artificial Intelligence for Prognostics, (3) Cognitive Approaches to Natural Language Processing, (4) Computational Approaches to Representation Change during Learning and Development, (5) Emergent Agents and Socialities: Social and Organizational Aspects of Intelligence, (6) Intelligent Narrative Technologies, and (7) Regarding the "Intelligence" in Distributed Intelligent Systems.

Is it possible to build a conscious machine? There was an almost generally accepted of AI since its beginnings. The symposium was psychological, philosophical, and the first official place where scholars-- neuroscientific theories of consciousness; coming from different fields as far as (3) it is possible to address consciousness neuroscience and philosophy, psychology not only from neuroscience, and computer science--addressed psychology, and philosophy, the issue of consciousness in a but also from AI; and (4) the role of traditional AI environment. Furthermore, embodiment and situatedness is almost there was a good balance of universally recognized. A recurrent topic was the fact that The participants' talks centered on the topic of the symposium and generated the field of consciousness seems to be lively discussions of their research.