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.

Burst detection is an important topic in temporal stream analysis. Usually, only the textual features are used in burst detection. In the theme extraction from current prevailing social media content, it is necessary to consider not only textual features but also the pervasive collaborative context, e.g., resource lifetime and user activity. This paper explores novel approaches to combine multiple sources of such indication for better burst extraction. We systematically investigate the characters of collaborative context, i.e., metadata frequency, topic coverage and user attractiveness. First, a robust state based model is utilized to detect bursts from individual streams. We then propose a learning method to combine these burst pulses. Experiments on a large real dataset demonstrate the remarkable improvements over the traditional methods.

This paper analyzes the performance of IDA* using additive heuristics. We show that the reduction in the number of nodes expanded using multiple independent additive heuristics is the product of the reductions achieved by the individual heuristics. First, we formally state and prove this result on unit edge-cost undirected graphs with a uniform branching factor. Then, we empirically verify it on a model of the 4-peg Towers of Hanoi problem. We also run experiments on the multiple sequence alignment problem showing more general applicability to non-unit edge-cost directed graphs. Then, we extend an existing model to predict the performance of IDA* with a single pattern database to independent additive disjoint pattern databases. This is the first analysis of the performance of independent additive heuristics.

The success of autonomous vehicles has made path planning in real, physically grounded environments an increasingly important problem. In environments where speed matters and vehicles must maneuver around obstructions, such as autonomous car navigation in hostile environments, the speed with which real vehicles can traverse a path is often dependent on the sharpness of the corners on the path as well as the length of path edges. We present an algorithm that incorporates the use of the turn angle through path nodes as a limiting factor for vehicle speed. Vehicle speed is then used in a time-weighting calculation for each edge. This allows the path planning algorithm to choose potentially longer paths, with less turns in order to minimize path traversal time. Results simulated in the Breve environment show that travel time can be reduced over the solution obtained using the Anytime D* Algorithm by approximately 10% for a vehicle that is speed limited based on turn rate.

Present-day programs are brittle as computers are notoriously lacking in common sense. While significant progress has been made in building large common sense knowledge bases, they are intrinsically incomplete and inconsistent. This paper presents a novel approach to bridging the gaps between multiple knowledge bases, making it possible to answer queries based on knowledge collected from multiple sources without a common ontology. New assertions are found by computing graph similarity with principle component analysis to draw analogies across multiple knowledge bases. Experiments are designed to find new assertions for a Chinese commonsense knowledge base using the OMCS ConceptNet and similarly for WordNet. The assertions are voted by online users to verify that 75.77% / 77.59% for Chinese ConceptNet / WordNet respectively are good, despite the low overlap in coverage among the knowledge bases.

The considerable interest in ARA techniques and the great diversity of the researchers involved had led to work on ARA being presented at many different venues. Consequently, there was a need to have a single forum where researchers of different backgrounds and disciplines could discuss their work on ARA. As a result, the Symposium on Abstraction, Reformulation, and Approximation (SARA) was established in 1994 after a series of workshops in 1988, 1990, and 1992. The current SARA, held at Lake Arrowhead, California, USA, on July 7-10, 2009, is the eighth in this series, following symposia in 1994, 1995, 1998, 2000, 2002, 2005, and 2007. Following a SARA tradition, this symposium brought together researchers with different backgrounds and facilitated lively discussions during and after the talks. There were 30 researchers from North and South America, Europe, and Australia. Additionally, SARA attendees were able to mingle and have fruitful discussions with members of the collocated Symposium on Combinatorial Search (SoCS). The collocation of SoCS was particularly useful in that many modern techniques in combinatorial search frequently utilize ARA methods. Finally, in addition to the regular and poster talks, there were three invited talks delivered by Jeff Orkin (Massachusetts Institute of Technology), Michael Genesereth (Stanford University), and Robert Holte (University of Alberta).

This article reports on the 2008 Reinforcement Learning Competition,  which began in November 2007 and ended with a workshop at the  International Conference on Machine Learning (ICML) in July 2008 in  Helsinki, Finland.  Researchers from around the world developed  reinforcement learning agents to compete in six problems of various  complexity and difficulty.  The competition employed fundamentally  redesigned evaluation frameworks that, unlike those in previous  competitions, aimed to systematically encourage the submission of  robust learning methods. We describe the unique challenges of  empirical evaluation in reinforcement learning and briefly review  the history of the previous competitions and the evaluation  frameworks they employed.  We also describe the novel frameworks  developed for the 2008 competition as well as the software  infrastructure on which they rely.  Furthermore, we describe the six  competition domains and present a summary of selected competition  results.  Finally, we discuss the implications of these results and  outline ideas for the future of the competition.

The European Conference on Case-Based Reasoning (CBR) in 2008 marked 15 years of international and European CBR conferences where almost seven hundred research papers were published. In this report we review the research themes covered in these papers and identify the topics that are active at the moment. The main mechanism for this analysis is a clustering of the research papers based on both co-citation links and text similarity. It is interesting to note that the core set of papers has attracted citations from almost three thousand papers outside the conference collection so it is clear that the CBR conferences are a sub-part of a much larger whole. It is remarkable that the research themes revealed by this analysis do not map directly to the sub-topics of CBR that might appear in a textbook. Instead they reflect the applications-oriented focus of CBR research, and cover the promising application areas and research challenges that are faced.

The major challenge in designing a discriminative learning algorithm for predicting structured data is to address the computational issues arising from the exponential size of the output space. Existing algorithms make different assumptions to ensure efficient, polynomial time estimation of model parameters. For several combinatorial structures, including cycles, partially ordered sets, permutations and other graph classes, these assumptions do not hold. In this thesis, we address the problem of designing learning algorithms for predicting combinatorial structures by introducing two new assumptions: (i) The first assumption is that a particular counting problem can be solved efficiently. The consequence is a generalisation of the classical ridge regression for structured prediction. (ii) The second assumption is that a particular sampling problem can be solved efficiently. The consequence is a new technique for designing and analysing probabilistic structured prediction models. These results can be applied to solve several complex learning problems including but not limited to multi-label classification, multi-category hierarchical classification, and label ranking.

Innate immunity now occupies a central role in immunology. However, artificial immune system models have largely been inspired by adaptive not innate immunity. This paper reviews the biological principles and properties of innate immunity and, adopting a conceptual framework, asks how these can be incorporated into artificial models. The aim is to outline a meta-framework for models of innate immunity.