Reasoning about joint beliefs for execution-time communication decisions
Just as POMDPs have been used to reason explicitly about uncertainty in single-agent systems, there has been recent interest in using multi-agent POMDPs to coordinate teams of agents in the presence of uncertainty. Although multi-agent POMDPs are known to be highly intractable, communication at every time step transforms a multi-agent POMDP into a more tractable single-agent POMDP. In this paper, we present an approach that generates "centralized" policies for multi-agent POMDPs at plan-time by assuming the presence of free communication, and at run-time, handles the problem of limited communication resources by reasoning about the use of communication as needed for effective execution. This approach trades off the need to do some computation at execution-time for the ability to generate policies more tractably at plan-time. In our algorithm, each agent, at run-time, models the distribution of possible joint beliefs. Joint actions are selected over this distribution, ensuring that agents remain synchronized. Communication is used to integrate local observations into the team belief only when those observations would improve team performance. We show, both through a detailed example and with experimental results, that our approach allows for effective decentralized execution while avoiding unnecessary instances of communication.

title: SetA*: an efficient BDD-based heuristic search algorithm
abstract: In this paper we combine the goal directed search of A* with the ability of BDDs to traverse an exponential number of states in polynomial time. We introduce a new algorithm, SetA*, that generalizes A* to expand sets of states in each iteration. SetA* has substantial advantages over BDDA*, the only previous BDD-based A* implementation we are aware of. Our experimental evaluation proves SetA* to be a powerful search paradigm. For some of the studied problems it outperforms BDDA*, A*, and BDD-based breadth-first search by several orders of magnitude. We believe exploring sets of states to be essential when the heuristic function is weak. For problems with strong heuristics, SetA* efficiently specializes to single-state search and consequently challenges single-state heuristic search in general.

title: Using decision tree confidence factors for multi-agent control
abstract: Although Decision Trees are widely used for classification tasks, they are typically not used for agent control. This paper presents a novel technique for agent control in a complex multiagent domain based on the confidence factors provided by the C4.5 Decision Tree algorithm. Using Robotic Soccer as an example of such a domain, this paper incorporates a previously-trained Decision Tree into a full multiagent behavior that is capable of controlling agents throughout an entire game. Along with using Decision Trees for control, this behavior also makes use of the ability to reason about action-execution time to eliminate options that would not have adequate time to be executed successfully. This multiagent behavior represents a bridge between low-level and high-level learning in the Layered Learning paradigm. The newly created behavior is tested empirically in game situations.

title: Route Planning by Analogy
abstract: There have been several efforts to create and use real maps in computer applications that automatically find good map routes. In general, online map representations do not include information that may be relevant for the purpose of generating good realistic routes, including for example traffic patterns, construction, or number of lanes. Furthermore, the notion of a good route is dependent on a variety of factors, such as the time of the day, and may also be user dependent. This motivation leads to our work on the accumulation and reuse of previously traversed routes as cases. In this paper, we demonstrate our route planning method which retrieves and reuses multiple past routing cases that collectively form a good basis for generating a new routing plan. We briefly present our similarity metric for retrieving a set of similar routes. The metric effectively takes into account the geometric and continuous-valued characteristics of a city map. We then present the replay mechanism and how the planner produces the route plan by analogizing from the retrieved similar past routes. We discuss in particular the strategy used to merge a set of cases and generate the new route. We use illustrative examples and show some empirical results from a detailed online map of the city of Pittsburgh containing over 18,000 intersections and 25,000 street segments.

title: Motion Control in Dynamic Multi-Robot Environments
abstract: This paper presents the motion control system used by CMUnited-98, the small-size league champion at RoboCup-98. The robotic soccer team consists of five robots that aim at achieving specific goals while navigating in a limited space shared with the five other opponent robots. We introduce our motion control algorithm, which allows a general differential-driven robot to accurately reach a target point with a desired orientation in an environment with multiple moving obstacles. We describe how the features of our motion controller help to build interesting and robust behaviors. We also briefly compare our system to other motion control techniques and include descriptions and illustrations of the performance of our fully-implemented motion control algorithm.

title: Exploiting domain geometry in analogical route planning
abstract: Automated route planning consists of using real maps to automatically find good map routes. Two shortcomings to standard methods are (1) that domain information may be lacking, and (2) that a ‘good’ route can be hard to define. Most on-line map representations do not include information that may be relevant for the purpose of generating good realistic routes, such as traffic patterns, construction, and one-way streets. The notion of a good route is dependent not only on geometry (shortest path),but also on a variety of other factors, such as the day and time, weather conditions,and perhaps most importantly,user-dependent preferences. These features can be learned by evaluating real-world execution experience. These difficulties motivate our work on applying analogical reasoning to route planning. Analogical reasoning is a method of using past experience to improve problem solving performance in similar new situations.Our approach consists of the accumulation and reuse of previously traversed rou...

title: Automatic Clustering of Faces in Meetings
abstract: Meetings are an integral part of business life for any organization. In previous work, we have developed a physical awareness system called CAMEO (camera assisted meeting event observer) to record and process the audio/visual information of a meeting. An important task in meeting understanding is to know who and how many people are attending the meeting. In this paper, we present an automatic approach to detect, track, and cluster people's faces in long video sequences. This is a challenging problem due to the appearance variability of people's faces (illumination, expression, pose,...). Two main novelties are presented: a robust real-time adaptive subspace face tracker which combines color and appearance. A temporal subspace clustering algorithm. The effectiveness and robustness of the proposed system is demonstrated over a data set of long videos (i.e. 1 hour).

title: Oracular Partially Observable Markov Decision Processes: A Very Special Case
abstract: We introduce the oracular partially observable Markov decision process (OPOMDP), a type of POMDP in which the world produces no observations; instead there is an "oracle," available in any state, that tells the agent its exact state for a fixed cost. The oracle may be a human or a highly accurate sensor. At each timestep the agent must choose whether to take a domain-level action or consult the oracle. This formulation comprises a factorization between information-gathering actions and domain-level actions, allowing us to characterize the value of information and to examine the problem of planning under uncertainty from a novel perspective. We propose an algorithm to capitalize on this factorization and the special structure of the OPOMDP, and we test the algorithm's performance on a new sample domain. On this new domain, we are able to solve a problem with hundreds of thousands of action-states and vastly outperform a previous state-of-the-art approximate technique

title: A Case-Based Approach for Indoor Location
abstract: Location is an important dimension for context-awareness in ubiquitous devices. Nowadays different techniques are used alone or together to determine the position of a person or object. One aspect of the problem concerns to indoor location. Various authors propose the analysis of Radio Frequency (RF) footprints. 
 
In this paper we defend that case-based reasoning can make an important contribution for location from RF footprints. We apply an empirical dissimilarity metric for footprint retrieval and compare this approach with the results obtained with a neural network and C5.0 learning algorithms. 
 
The RF footprints are obtained from a Global System for Mobile Communications and General Packet Radio Service (GSM/GPRS) network. Signals from these networks are particularly complex when compared to the ones obtained from WiFi or Bluetooth networks.

title: CMRoboBits: Creating an Intelligent AIBO Robot
abstract: CMRoboBits is a course offered at Carnegie Mellon University that introduces students to all the concepts needed to create a complete intelligent robot. In particular, the course focuses on the areas of perception, cognition, and action by using the Sony AIBO robot as the focus for the programming assignments. This course shows how an AIBO and its software resources make it possible for students to investigate and work with an unusually broad variety of AI topics within a single semester. While material presented in this article describes using AIBOs as the primary platform, the concepts presented in the course are not unique to the AIBO and can be applied on different kinds of robotic hardware.