High-level planning and low-level execution: towards a complete robotic agent
We have been developing Rogue, an architecture that integrates high-level planning with a low-level executing robotic agent. Rogue is designed as the o ce gofer task planner for Xavier the robot. User requests are interpreted as high-level planning goals, such as getting co ee, and picking up and delivering mail or faxes. Users post tasks asynchronously and Rogue controls the corresponding planning and execution continuous process. This paper presents the extensions to a nonlinear state-space planning algorithm to allow for the interaction to the robot executor. We focus on presenting how executable steps are identi ed based on the planning model and the predicted execution performance; how interrupts from users requests are handled and incorporated into the system; how executable plans are merged according to their priorities; and how monitoring execution can add more perception knowledge to the planning and possible needed re-planning processes. The complete Rogue system will learn from its planning and execution experiences to improve upon its own behaviour with time. We nalize the paper by brie y discussing Rogue's learning opportunities. This research is sponsored in part by the Wright Laboratory, Aeronautical Systems Center, Air Force Material Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the o cial policies or endorsements, either expressed or implied, of the Wright Laboratory or the U. S. Government.  Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and the full citation on the rst page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior speci c permission and/or a fee.

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: 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: 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: 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: 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: 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: 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: 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.