---------- @ARTICLE{Bennewitz04a, M. Bennewitz, W. Burgard, G. Cielniak, and S. Thrun. Learning motion patterns of people for compliant motion. Whenever people move through their environments they do not move randomly. Instead, they usually follow specific trajectories or motion patterns corresponding to their intentions. Knowledge about such patterns enables a mobile robot to robustly keep track of persons in its environment and to improve its behavior. This paper proposes a technique for learning collections of trajectories that characterize typical motion patterns of persons. Data recorded with laser-range finders is clustered using the expectation maximization algorithm. Based on the result of the clustering process we derive a Hidden Markov Model (HMM) that is applied to estimate the current and future positions of persons based on sensory input. We also describe how to incorporate the probabilistic belief about the potential trajectories of persons into the path planning process. We present several experiments carried out in different environments with a mobile robot equipped with a laser range scanner and a camera system. The results demonstrate that our approach can reliably learn motion patterns of persons, can robustly estimate and predict positions of persons, and can be used to improve the navigation behavior of a mobile robot. ---------- @ARTICLE{Thrun04a, S. Thrun, S. Thayer, W. Whittaker, C. Baker, W. Burgard, D. Ferguson, D. Haehnel, M. Montemerlo, A. Morris, Z. Omohundro, C. Reverte, and W. Whittaker. Autonomous exploration and mapping of abandoned mines. Abandoned mines pose significant threats to society, yet a large fraction of them lack accurate maps. This article discusses the software architecture of an autonomous robotic system designed to explore and map abandoned mines. We have built a robot capable of autonomously exploring abandoned mines. A new set of software tools is presented, enabling robots to acquire maps of unprecedented size and accuracy. On May 30, 2003, our robot "Groundhog" successfully explored and mapped a main corridor of the abandoned Mathies mine near Courtney, PA. The article also discusses some of the challenges that arise in the subterraneans environments, and some the difficulties of building truly autonomous robots. ---------- @INPROCEEDINGS{Pineau02f, J. Pineau, M. Montemerlo, N. Roy, S. Thrun, and M. Pollack. Towards robotic assistants in nursing homes: challenges and results. This paper describes a mobile robotic assistant, developed to assist elderly individuals with mild cognitive and physical impairments, as well as support nurses in their daily activities. We present three software modules relevant to ensure successful human-robot interaction: an automated reminder system; a people-tracking and detection system; and finally a high-level robot controller which performs planning under uncertainty by incorporating knowledge from low-level modules, and selecting appropriate courses of actions. During the course of experiments conducted in an assisted living facility, the robot successfully demonstrated that it could autonomously provide reminders and guidance for elderly residents. ---------- @ARTICLE{Thrun03g, S. Thrun, M. Montemerlo, D. Koller, B. Wegbreit, J. Nieto, and E. Nebot. Fastslam: An efficient solution to the simultaneous localization and mapping problem with unknown data association. This article provides a comprehensive description of FastSLAM, a new family of algorithms for the simultaneous localization and mapping problem, which specifically address hard data association problems. The algorithm uses a particle filter for sampling robot paths, and extended Kalman filters for representing maps acquired by the vehicle. This article presents two variants of this algorithm, the original algorithm along with a more recent variant that provides improved performance in certain operating regimes. In addition to a mathematical derivation of the new algorithm, we present a proof of convergence and experimental results on its performance on real-world data. ---------- @INPROCEEDINGS{Dearden04a, R. Dearden, F. Huttner, R. Simmons, V. Verma, T. Willeke, and S. Thrun. Real-time fault detection and situational awareness for rovers: Report on the mars technology program task. An increased level of autonomy is critical for meeting many of the goals of advanced planetary rover missions such as NASA's 2009 Mars Science Lab. One important component of this is state estimation, and in particular fault detection on-board the rover. In this paper we describe the results of a project funded by the Mars Technology Program at NASA, aimed at developing algorithms to meet this requirement. We describe a number of particle filtering-based algorithms for state estimation which we have demonstrated successfully on diagnosis problems including the K-9 rover at NASA Ames Research Center and the Hyperion rover at CMU. Because of the close interaction between a rover and its environment, traditional discrete approaches to diagnosis are impractical for this domain. Therefore we model rover subsystems as hybrid discrete/continuous systems. There are three major challenges to make particle filters work in this domain. The first is that fault states typically have a very low probability of occurring, so there is a risk that no samples will enter fault states. The second issue is coping with the high-dimensional continuous state spaces of the hybrid system models, and the third is the severely constrained computational power available on the rover. This means that very few samples can be used if we wish to track the system state in real time. We describe a number of approaches to rover diagnosis specifically designed to address these challenges. ---------- @INPROCEEDINGS{Montemerlo04a, M. Montemerlo and S. Thrun. A multi-resolution pyramid for outdoor robot terrain perception. This paper addresses the problem of outdoor terrain modeling for the purposes of mobile robot navigation. We propose an approach in which a robot acquires a set of terrain models at differing resolutions. Our approach addresses one of the major shortcomings of Bayesian reasoning when applied to terrain modeling, namely artifacts that arise from the limited spatial resolution of robot perception. Limited spatial resolution causes small obstacles to be detectable only at close range. Hence, a Bayes filter estimating the state of terrain segments must consider the ranges at which that terrain is observed. We develop a multi-resolution approach that maintains multiple navigation maps, and derive rational arguments for the number of layers and their resolutions. We show that our approach yields significantly better results in a practical robot system, capable of acquiring detailed 3-D maps in large-scale outdoor environments. ---------- @INPROCEEDINGS{Gerkey04a, B. Gerkey, S. Thrun, and G. Gordon. Clear the building: Pursuit-evasion with teams of robots. We study a form of the pursuit-evasion problem, in which one or more searchers must move through a given environment so as to guarantee detection of any and all evaders, which can move arbitrarily fast. Our goal is to develop techniques for coordinating teams of robots to execute this task in application domains such as clearing a building, for reasons of security or safety. To this end, we introduce a new class of searcher, the pi-searcher, which can be readily instantiated as a physical mobile robot. We present a detailed analysis of the pursuit-evasion problem using pi-searchers. We show that computing the minimum number of pi-searchers required to search a given environment is NP-hard, and present the first complete search algorithm for a single pi-searcher. We show how this algorithm can be extended to handle multiple searchers, and give examples of computed trajectories. ---------- @INPROCEEDINGS{Biswas04a, R. Biswas, L. Guibas, and S. Thrun. A probabilistic approach to inference with limited information in sensor networks. We present a methodology for a sensor network to answer queries with limited and stochastic information using probabilistic techniques. This capability is useful in that it allows sensor networks to answer queries effectively even when present information is partially corrupt and when more information is unavailable or too costly to obtain. We use a Bayesian network to model the sensor network and Markov Chain Monte Carlo sampling to perform approximate inference. We demonstrate our technique on the specific problem of determining whether a friendly agent is surrounded by enemy agents and present simulation results for it. ---------- @INPROCEEDINGS{Glover04a, J. Glover, S. Thrun, and J.T. Matthews. Learning user models of mobility-related activities through instrumented walking aids. We present a robotic walking aid capable of learning models of users' walking-related activities. Our walker is instrumented to provide guidance to elderly people when navigating their environments; however, such guidance is difficult to provide without knowing what activity a person is engaged in (e.g., where a person wants to go). The main contribution of this paper is an algorithm for learning models of users of the walker. These models are defined at multiple levels of abstractions, and learned from actual usage data using statistical techniques. We demonstrate that our approach succeeds in determining the specific activity in which a user engages when using the walker. One of our proto-type walkers was tested in an assisted living facility near Pittsburgh, PA; a more recent model was extensively evaluated in a university environment. ---------- @INPROCEEDINGS{Anguelov04a, D. Anguelov, D. Koller, E. Parker, and S. Thrun. Detecting and modeling doors with mobile robots. We describe a probabilistic framework for detection and modeling of doors from sensor data acquired in corridor environments with mobile robots. The framework captures shape, color, and motion properties of door and wall objects. The probabilistic model is optimized with a version of the expectation maximization algorithm, which segments the environment into door and wall objects and learns their properties. The framework allows the robot to generalize the properties of detected object instances to new object instances. We demonstrate the algorithm on real-world data acquired by a Pioneer robot equipped with a laser range finder and an omni-directional camera. Our results show that our algorithm reliably segments the environment into walls and doors, finding both doors that move and doors that do not move. We show that our approach achieves better results than models that only capture behavior, or only capture appearance. ---------- @INPROCEEDINGS{Ferguson04a, D. Ferguson, T. Stentz, and S. Thrun. PAO* for planning with hidden state. We describe a heuristic search algorithm for generating optimal plans in a new class of decision problem, characterised by the incorporation of hidden state. The approach exploits the nature of the hidden state to reduce the state space by orders of magnitude. It then interleaves heuristic expansion of the reduced space with forwards and backwards propagation phases to produce a solution in a fraction of the time required by other techniques. Results are provided on an outdoor path planning application. ---------- @INPROCEEDINGS{Ferguson03a, D. Ferguson, A. Morris, D. Haehnel, C. Baker, Z. Omohundro, C. Reverte, S. Thayer, W. Whittaker, W. Whittaker, W. Burgard, and S. Thrun. An autonomous robotic system for mapping abandoned mines. We present the software architecture of a robotic system for mapping abandoned mines. The software is capable of acquiring consistent 2D maps of large mines with many cycles, represented as Markov random fields. 3D C-space maps are acquired from local 3D range scans, which are used to identify navigable paths using A* search. Our system has been deployed in three abandoned mines, two of which inaccessible to people, where it has acquired maps of unprecedented detail and accuracy. ---------- @INPROCEEDINGS{Bererton03a, C. Bererton, G. Gordon, and S. Thrun. Auction mechanism design for multi-robot coordination. The design of cooperative multi-robot systems is a highly active research area in robotics. Two lines of research in particular have generated interest: the solution of large, weakly coupled MDPs, and the design and implementation of market architectures. We propose a new algorithm which joins together these two lines of research. For a class of coupled MDPs, our algorithm automatically designs a market architecture which causes a decentralized multi-robot system to converge to a consistent policy. We can show that this policy is the same as the one which would be produced by a particular centralized planning algorithm. We demonstrate the new algorithm on three simulation examples: multi-robot towing, multi-robot path planning with a limited fuel resource, and coordinating behaviors in a game of paint ball. ---------- @INPROCEEDINGS{Likhachev03b, M. Likhachev, G. Gordon, and S. Thrun. ARA*: Anytime A* search with provable bounds on sub-optimality. In real world planning problems, time for deliberation is often limited. Anytime planners are well suited for these problems: they find a feasible solution quickly and then continually work on improving it until time runs out. In this paper we propose an anytime heuristic search, ARA*, which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. While improving its bound, ARA* reuses previous search efforts and, as a result, is significantly more efficient than other anytime search methods. In addition to our theoretical analysis, we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and a dynamic path planning problem for an outdoor rover. ---------- @INPROCEEDINGS{Pineau03c, J. Pineau, G. Gordon, and S. Thrun. Applying metric trees to belief-point POMDPs. Recent developments in grid-based and point-based approximation algorithms for POMDPs have greatly improved the tractability of POMDP planning. These approaches operate on sets of belief points by individually learning a value function for each point. In reality, belief points exist in a highly-structured metric simplex, but current POMDP algorithms do not exploit this property. This paper presents a new metric-tree algorithm which can be used in the context of POMDP planning to sort belief points spatially, and then perform fast value function updates over groups of points. We present results showing that this approach can reduce computation in point-based POMDP algorithms for a wide range of problems. ---------- @INPROCEEDINGS{Haehnel03b, D. Haehnel, D. Fox, W. Burgard, and S. Thrun. A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements. The ability to learn a consistent model of its environment is a prerequisite for autonomous mobile robots. A particularly challenging problem in acquiring environment maps is that of closing loops; loops in the environment create challenging data association problems [9]. This paper presents a novel algorithm that combines RaoBlackwellized particle filtering and scan matching. In our approach scan matching is used for minimizing odometric errors during mapping. A probabilistic model of the residual errors of scan matching process is then used for the resampling steps. This way the number of samples required is seriously reduced. Simultaneously we reduce the particle depletion problem that typically prevents the robot from closing large loops. We present extensive experiments that illustrate the superior performance of our approach compared to previous approaches. ---------- @INPROCEEDINGS{Montemerlo03b, M. Montemerlo, N. Roy, and S. Thrun. Perspectives on standardization in mobile robot programming: The carnegie mellon navigation (CARMEN) toolkit. In this paper we describe our open-source robot control software, the Carnegie Mellon Navigation (CARMEN) Toolkit. The ultimate goals of CARMEN are to lower the barrier to implementing new algorithms on real and simulated robots and to facilitate sharing of research and algorithms between different institutions. In order for CARMEN to be as inclusive of various research approaches as possible, we have chosen not to adopt strict software standards, but to instead focus on good design practices. This paper will outline the lessons we have learned in developing these practices. ---------- @INPROCEEDINGS{Thrun03e, S. Thrun and Y. Liu. Multi-robot SLAM with sparse extended information filers. We present an algorithm for the multi-robot simultaneous localization and mapping (SLAM) problem. Our algorithm enables teams of robots to build joint maps, even if their relative starting locations are unknown and landmarks are ambiguous--which is presently an open problem in robotics. It achieves this capability through a sparse information filter technique, which represents maps and robot poses by Gaussian Markov random fields. The alignment of local maps into a single global maps is achieved by a tree-based algorithm for searching similar-looking local landmark configurations, paired with a hill climbing algorithm that maximizes the overall likelihood by search in the space of correspondences. We report favorable results obtained with a real-world benchmark data set. ---------- @INPROCEEDINGS{Haehnel03c, D. Haehnel, W. Burgard, B. Wegbreit, and S. Thrun. Towards lazy data association in SLAM. We present a lazy data association algorithm for the simultaneous localization and mapping (SLAM) problem. Our approach uses a tree-structured Bayesian representation of map posteriors that makes it possible to revise data association decisions arbitrarily far into the past. We describe a criterion for detecting and repairing poor data association decisions. This technique makes it possible to acquire maps of large-scale environments with many loops, with a minimum of computational overhead for the management of multiple data association hypotheses. A empirical comparison with the popular FastSLAM algorithm shows the advantage of lazy over proactive data association. ---------- @INPROCEEDINGS{Rosencrantz03a, M. Rosencrantz, G. Gordon, and S. Thrun. D ecentralized sensor fusion with distributed particle filters. This paper presents a scalable Bayesian technique for decentralized state estimation from multiple platforms in dynamic environments. As has long been recognized, centralized architectures impose severe scaling limitations for distributed systems due to the enormous communication overheads. We propose a strictly decentralized approach in which only nearby platforms exchange information. They do so through an interactive communication protocol aimed at maximizing information flow. Our approach is evaluated in the context of a distributed surveillance scenario that arises in a robotic system for playing the game of laser tag. Our results, both from simulation and using physical robots, illustrate an unprecedented scaling capability to large teams of vehicles. ---------- @INPROCEEDINGS{Pineau03b, J. Pineau, G. Gordon, and S. Thrun. Policy-contingent abstraction for robust robot control. This paper presents a scalable control algorithm that enables a deployed mobile robot to make high-level control decisions under full consideration of its probabilistic belief. We draw on insights from the rich literature of structured robot controllers and hierarchical MDPs to propose PolCA, a hierarchical probabilistic control algorithm which learns both subtask-specific state abstractions and policies. The resulting controller has been successfully implemented onboard a mobile robotic assistant deployed in a nursing facility. To the best of our knowledge, this work is a unique instance of applying POMDPs to highlevel robotic control problems. ---------- @INPROCEEDINGS{Pineau03a, J. Pineau, G. Gordon, and S. Thrun. Point-based value iteration: An anytime algorithm for POMDPs. This paper introduces the Point-Based Value Iteration (PBVI) algorithm for POMDP planning. PBVI approximates an exact value iteration solution by selecting a small set of representative belief points and then tracking the value and its derivative for those points only. By using stochastic trajectories to choose belief points, and by maintaining only one value hyper-plane per point, PBVI successfully solves large problems: we present results on a robotic laser tag problem as well as three test domains from the literature. ---------- @INPROCEEDINGS{Verma03a, V. Verma, R. Simmons, and S. Thrun. Variable resolution particle filter. Particle filters are used extensively for tracking the state of non-linear dynamic systems. This paper presents a new particle filter that maintains samples in the state space at dynamically varying resolution for computational efficiency. Resolution within statespace varies by region, depending on the belief that the true state lies within each region. Where belief is strong, resolution is fine. Where belief is low, resolution is coarse, abstracting multiple similar states together. The resolution of the statespace is dynamically updated as the belief changes. The proposed algorithm makes an explicit bias-variance tradeoff to select between maintaining samples in a biased generalization of a region of state space versus in a high variance specialization at fine resolution. Samples are maintained at a coarser resolution when the bias introduced by the generalization to a coarse resolution is outweighed by the gain in terms of reduction in variance, and at a finer resolution when it is not. Maintaining samples in abstraction prevents potential hypotheses from being eliminated prematurely for lack of a sufficient number of particles. Empirical results show that our variable resolution particle filter requires significantly lower computation for performance comparable to a classical particle filter. ---------- @INPROCEEDINGS{Montemerlo03a, M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit. FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges. The ability to simultaneously localize a robot and accurately map its surroundings is considered by many to be a key prerequisite of truly autonomous robots. However, few approaches to this problem scale up to handle the very large number of landmarks present in real environments. Kalman filter-based algorithms, for example, require time quadratic in the number of landmarks to incorporate each sensor observation. This paper presents FastSLAM, an algorithm that recursively estimates the full posterior distribution over robot pose and landmark locations, yet scales logarithmically with the number of landmarks in the map. This algorithm is based on an exact factorization of the posterior into a product of conditional landmark distributions and a distribution over robot paths. The algorithm has been run successfully on as many as 50,000 landmarks, environments far beyond the reach of previous approaches. Experimental results demonstrate the advantages and limitations of the FastSLAM algorithm on both simulated and realworld data. ---------- @INPROCEEDINGS{Berna03a, M. Berna, B. Lisien, B. Sellner, G. Gordon, F. Pfenning, and S. Thrun. A learning algorithm for localizing people based on wireless signal strength that uses labeled and unlabeled data. This paper summarizes a probabilistic approach for localizing people through the signal strengths of a wireless IEEE 802.11b network. Our approach uses data labeled by ground truth position to learn a probabilistic mapping from locations to wireless signals, represented by piecewise linear Gaussians. It then uses sequences of wireless signal data (without position labels) to acquire motion models of individual people, which further improves the localization accuracy. The approach has been implemented and evaluated in an office environment. ---------- @INPROCEEDINGS{Roy03a, N. Roy, G. Gordon, and S. Thrun. Planning under uncertainty for reliable health care robotics. We describe a mobile robot system, designed to assist residents of an retirement facility. This system is being developed to respond to an aging population and a predicted shortage of nursing professionals. In this paper, we discuss the task of finding and escorting people from place to place in the facility, a task containing uncertainty throughout the problem. Planning algorithms that model uncertainty well such as Partially Observable Markov Decision Processes (POMDPs) do not scale tractably to real world problems such as the health care domain. We demonstrate an algorithm for representing real world POMDP problems compactly, which allows us to find good policies in reasonable amounts of time. We show that our algorithm is able to find moving people in close to optimal time, where the optimal policy starts with knowledge of the person's location. ---------- @INPROCEEDINGS{Nettleton03a, E. Nettleton, S. Thrun, and H. Durrant-Whyte. Decentralised slam with low-bandwidth communication for teams of airborne vehicles. This paper addresses the problem of simultaneous localization and mapping (SLAM) for teams of collaborating vehicles where the communication bandwidth is limited. We present a novel SLAM algorithm that enables multiple vehicles to acquire a joint map, but which can cope with arbitrary latency and bandwidth limitations such as typically found in airborne vehicle applications. The key idea is to represent maps in information form (negative log-likelihood), and to selectively communicate subsets of the information tailored to the available communication resources. We show that our communication scheme preserves the consistency, which has important ramifications for data association problems. We also provide experimental results that illustrate the effectiveness of our approach in comparison with previous techniques. ---------- @INPROCEEDINGS{Nieto02b, J. Nieto, J. Guivant, E. Nebot, and S. Thrun. Real time data association for FastSLAM. The ability to simultaneously localise a robot and accurately map its surroundings is considered by many to be a key prerequisite of truly autonomous robots. This paper presents a real-world implementation of FastSLAM, an algorithm that recursively estimates the full posterior distribution of both robot pose and landmark locations. In particular, we present an extension to FastSLAM that addresses the data association problem using a nearest neighbour technique. Building on this, we also present a novel multiple hypothesis tracking implementation (MHT) to handle uncertainty in the data association. Finally an extension to the multi-robot case is introduced. Our algorithm has been run successfully using a number of data sets obtained in outdoor environments. Experimental results are presented that demonstrate the performance of the algorithms when compared with standard Kalman Filter-based approaches. ---------- @INPROCEEDINGS{Bennewitz02b, M. Bennewitz, W. Burgard, and S. Thrun. Adapting navigation strategies using motions patterns of people. As people move through their environments, they do not move randomly. Instead, they are often engaged in typical motion patterns, related to specific locations they might be interested in approaching. In this paper we propose a method for adapting the behavior of a mobile robot according to the activities of the people in its surrounding. Our approach uses learned models of people's motion behaviors. Whenever the robot detects a person it computes a probabilistic estimate about which motion pattern the person might be engaged in. During path planning it then uses this belief to improve its navigation behavior. In different practical experiments carried out on a real robot we demonstrate that our approach allows a robot to quickly adapt its navigation plans according to the activities of the persons in its surrounding. We also present experiments illustrating that our approach provides a better behavior than a standard reactive collision avoidance system. ---------- @INPROCEEDINGS{Rosencrantz02a, M. Rosencrantz, G. Gordon, and S. Thrun. Locating moving entities in dynamic indoor environments with teams of mobile robots. This article presents an implemented multi-robot system for playing the popular game of laser tag. The object of the game is to search for and tag opponents that can move freely about the environment. The main contribution of this paper is a new particle filter algorithm for tracking the location of many opponents in the presence of pervasive occlusion. We achieve efficient tracking principally through a clever factorization of our posterior into roles that can be dynamically added and merged. When searching for opponents, the individual agents greedily maximize their information gain, using a negotiation technique for coordinating their search efforts. Experimental results are provided, obtained with a physical robot system in large-scale indoor environments and through simulation. ---------- @INPROCEEDINGS{Thrun01d, S. Thrun, Y. Liu, R. Emery, D. Chakrabarti, and W. Burgard. A method for acquiring multi-planar volumetric models with mobile robots based on the EM algorithm. This paper describes an algorithm for generating compact 3D models of indoor environments with mobile robots. Our algorithm employs the expectation maximization algorithm to fit a low-complexity planar model to 3D data collected by range finders and a panoramic camera. The complexity of the model is determined during model fitting, by incrementally adding and removing surfaces. In a final post-processing step, measurements are converted into polygons and projected onto the surface model where possible. Empirical results obtained with a mobile robot illustrate that high-resolution models can be acquired in reasonable time. ---------- @INPROCEEDINGS{Bennewitz01c, M. Bennewitz, W. Burgard, and S. Thrun. Optimizing priority schemes for decoupled path planning techniques. The coordination of the motions of the robots is one of the fundamental problems for multi-robot systems. A popular approach to avoid planning in the high-dimensional composite configuration space are prioritized and decoupled techniques. While these methods are very efficient, they have two major drawbacks. First, they are incomplete, i.e. they sometimes fail to find a solution even if one exists, and second, the resulting solutions are often not optimal. They furthermore leave open how to assign the priorities to the individual robots. In this paper we present a method for optimizing priority schemes for such prioritized and decoupled planning techniques. Our approach performs a randomized search with hill-climbing to find solutions and to minimize the overall path lengths. The technique has been implemented and tested on real robots and in extensive simulation runs. The experimental results demonstrate that our method is able to seriously reduce the number of failures and to significantly reduce the overall path length for different prioritized and decoupled path planning techniques and even for large teams of robots. ---------- @INPROCEEDINGS{Margaritis01a, D. Margaritis, C. Faloutsos, and S. Thrun. Netcube: A scalable tool for fast data mining and compression. We propose an novel method of computing and storing DataCubes. Our idea is to use Bayesian Networks, which can generate approximate counts for any query combination of attribute values and "don't cares." A Bayesian network represents the underlying joint probability distribution of the data that were used to generate it. By means of such a network the proposed method, NetCube, exploits correlations among attributes. Our proposed preprocessing algorithm scales linearly on the size of the database, and is thus scalable; it is also parallelizable with a straightforward parallel implementation. Moreover, we give an algorithm to estimate counts of arbitrary queries that is fast (constant on the database size). Experimental results show that NetCubes have fast generation and use. ---------- @INPROCEEDINGS{Bennewitz01d, M. Bennewitz, W. Burgard, and S. Thrun. Constraint-based optimization of priority schemes for decoupled path planning techniques. Coordinating the motion of multiple mobile robots is one of the fundamental problems in robotics. The predominant algorithms for coordinating teams of robots are decoupled and prioritized, thereby avoiding combinatorially hard planning problems typically faced by centralized approaches. While these methods are very efficient, they have two major drawbacks. First, they are incomplete, i.e. they sometimes fail to find a solution even if one exists, and second, the resulting solutions are often not optimal. In this paper we present a method for finding and optimizing priority schemes for such prioritized and decoupled planning techniques. Existing approaches apply a single priority scheme which makes them overly prone to failure in cases where valid solutions exist. By searching in the space of priorization schemes, our approach overcomes this limitation. It performs a randomized search with hill-climbing to find solutions and to minimize the overall path length. To focus the search, our algorithm is guided by constraints generated from the task specification. To illustrate the appropriateness of this approach, this paper discusses experimental results obtained with real robots and through systematic robot simulation. The experimental results illustrate the superior performance of our approach, both in terms of efficiency of robot motion and in the ability to find valid plans. ---------- @INPROCEEDINGS{Margaritis01b, D. Margaritis and S. Thrun. A bayesian multiresolution independence test for continuous variables. no abstract availbale ---------- @INPROCEEDINGS{Rosenberg00a, C. Rosenberg, M. Hebert, and S. Thrun. Color constancy using KL divergence. Color is a useful feature for machine vision tasks. However, its effectiveness is often limited by the fact that the measured pixel values in a scene are influenced by both object surface reflectance properties and incident illumination. Color constancy algorithms attempt to compute color features which are invariant of the incident illumination by estimating the parameters of the global scene illumination and factoring out its effect. A number of recently developed algorithms utilize statistical methods to estimate the maximum likelihood values of the illumination parameters. This paper details the use of KL-divergence as a means of selecting estimated illumination parameter values. We provide experimental results demonstrating the usefulness of the KL-divergence technique for accurately estimating the global illumination parameters of real world images. ---------- @INPROCEEDINGS{Bennewitz01b, M. Bennewitz, W. Burgard, and S. Thrun. Optimizing schedules for prioritized path planning of multi-robot systems. The coordination of the motions of the robots is one of the fundamental problems for multi-robot systems. A popular approach to avoid planning in the high-dimensional composite configuration space are prioritized and decoupled techniques. While these methods are very efficient, they have two major drawbacks. First, they are incomplete, i.e. they sometimes fail to find a solution even if one exists, and second, the resulting solutions are often not optimal. They furthermore leave open how to assign the priorities to the individual robots. In this paper we present a method for optimizing priority schemes for such prioritized and decoupled planning techniques. Our approach performs a randomized search with hill-climbing to find solutions and to minimize the overall path lengths. The technique has been implemented and tested on real robots and in extensive simulation runs. The experimental results demonstrate that our method is able to seriously reduce the number of failures and to significantly reduce the overall path length for different prioritized and decoupled path planning techniques and even for large teams of robots. ---------- @INPROCEEDINGS{Dellaert00b, F. Dellaert, S. Seitz, S. Thrun, and C. Thorpe. Feature correspondence: A markov chain monte carlo approach. When trying to recover 3D structure from a set of images, the most difficult problem is establishing the correspondence between the measurements. Most existing approaches assume that features can be tracked across frames, whereas methods that exploit rigidity constraints to facilitate matching do so only under restricted camera motion. In this paper we propose a Bayesian approach that avoids the brittleness associated with singling out one "best" correspondence, and instead consider the distribution over all possible correspondences. We treat both a fully Bayesian approach that yields a posterior distribution, and a MAP approach that makes use of EM to maximize this posterior. We show how Markov chain Monte Carlo methods can be used to implement these techniques in practice, and present experimental results on real data. ---------- @INPROCEEDINGS{Roy00b, N. Roy, J. Pineau, and S. Thrun. Spoken dialogue management using probabilistic reasoning. Spoken dialogue managers have benefited from using stochastic planners such as Markov Decision Processes (MDPs). However, so far, MDPs do not handle well noisy and ambiguous speech utterances. We use a Partially Observable Markov Decision Process (POMDP)-style approach to generate dialogue strategies by inverting the notion of dialogue state; the state represents the user's intentions, rather than the system state. We demonstrate that under the same noisy conditions, a POMDP dialogue manager makes fewer mistakes than an MDP dialogue manager. Furthermore, as the quality of speech recognition degrades, the POMDP dialogue manager automatically adjusts the policy. ---------- @INPROCEEDINGS{Simmons00b, R. Simmons, D. Apfelbaum, D. Fox, R.P. Goldmann, K.Z. Haigh, D.J. Musliner, M. Pelican, and S. Thrun. Coordinated deployment of multiple heterogeneous robots. To be truly useful, mobile robots need to be fairly autonomous and easy to control. This is especially true in situations where multiple robots are used, due to the increase in sensory information and the fact that the robots can interfere with one another. This paper describes a system that integrates autonomous navigation, a task executive, task planning, and an intuitive graphical user interface to control multiple, heterogeneous robots. We have demonstrated a prototype system that plans and coordinates the deployment of teams of robots. Testing has shown the effectiveness and robustness of the system, and of the coordination strategies in particular. ---------- @INPROCEEDINGS{Dellaert00a, F. Dellaert, S. Seitz, C. Thorpe, and S. Thrun. Structure from motion without correspondence. A method is presented to recover 3D scene structure and camera motion from multiple images without the need for correspondence information. The problem is framed as finding the maximum likelihood structure and motion given only the 2D measurements, integrating over all possible assignments of 3D features to 2D measurements. This goal is achieved by means of an algorithm which iteratively refines a probability distributionover the set of all correspondence assignments. At each iteration a new structure from motion problem is solved, using as input a set of 'virtual measurements' derived from this probability distribution. The distribution needed can be efficiently obtained by Markov Chain Monte Carlo sampling. The approach is cast within the framework of Expectation-Maximization,which guarantees convergence to a local maximizer of the likelihood. The algorithm works well in practice, as will be demonstrated using results on several real image sequences. ---------- @INPROCEEDINGS{Boutilier00a, C. Boutilier, R. Reiter, M. Soutchanski, and S. Thrun. Decision-theoretic, high-level robot programming in the situation calculus. We propose a method of approximate dynamic programming for Markov decision processes (MDPs) using algebraic decision diagrams (ADDs). We produce near-optimal value functions and policies with much lower time and space requirements than exact dynamic programming. Our method reduces the sizes of the intermediate value functions generated during value iteration by replacing the values at the terminals of the ADD with ranges of values. A representation using decision diagrams is well-suited to this task, for similar values can be directly merged without the need for reordering variables. Our method is demonstrated on a class of large MDPS (with up to 34 billion states), and we compare the results with the optimal value functions. ---------- @INPROCEEDINGS{Simmons00a, R. Simmons, D. Apfelbaum, W. Burgard, M. Fox, D. an Moors, S. Thrun, and H. Younes. Coordination for multi-robot exploration and mapping. This paper addresses the problem of exploration and mapping of an unknown environment by multiple robots. The mapping algorithm is an on-line approach to likelihood maximization that uses hill climbing to find maps that are maximally consistent with sensor data and odometry. The exploration algorithm explicitly coordinates the robots. It tries to maximize overall utility by minimizing the potential for overlap in information gain amongst the various robots. For both the exploration and mapping algorithms, most of the computations are distributed. The techniques have been tested extensively in real-world trials and simulations. The results demonstrate the performance improvements and robustness that accrue from our multirobot approach to exploration. ---------- @INPROCEEDINGS{Margaritis99a, D. Margaritis and S. Thrun. Bayesian network induction via local neighborhoods. In recent years, Bayesian networks have become highly successful tool for diagnosis, analysis, and decision making in real-world domains. We present an efficient algorithm for learning Bayes networks from data. Our approach constructs Bayesian networks by first identifying each node's Markov blankets, then connecting nodes in a maximally consistent way. In contrast to the majority of work, which typically uses hill-climbingapproaches that may produce dense and causally incorrect nets, our approach yields much more compact causal networks by heeding independencies inthe data. Compact causal networksfacilitatefast inference and are also easier to understand. We prove that under mild assumptions, our approach requires time polynomial in the size of the data and the number of nodes. A randomized variant, also presented here, yields comparable results at much higher speeds. ---------- @InProceedings{Fox99d, D. Fox, W. Burgard, H. Kruppa, and S. Thrun. Efficient multi-robot localization based on monte carlo approximation. This paper presents a probabilistic algorithm for collaborative mobile robot localization. Our approach uses a sample-based version of Markov localization, capable of localizing mobile robots in an any-time fashion. When teams of robots localize themselves in the same environment, probabilistic methods are employed to synchronize each robot's belief whenever one robot detects another. As a result, the robots localize themselves faster, maintain higher accuracy, and high-cost sensors are amortized across multiple robot platforms. The paper also describes experimental results obtained using two mobile robots, using computer vision and laser range-finding for detecting each other and estimating each other's relative location. The results, obtained in an indoor office environment, illustrate drastic improvements in localization speed and accuracy when compared to conventional single-robot localization. ---------- @INPROCEEDINGS{Thrun99f, S. Thrun, M. Bennewitz, W. Burgard, A.B. Cremers, F. Dellaert, D. Fox, D. Haehnel, G. Lakemeyer, C. Rosenberg, N. Roy, J. Schulte, D. Schulz, and W. Steiner. Experiences with two deployed interactive tour-guide robots. This paper describes and compares two pioneering mobile robot systems, which were recently deployed as interactive tour-guides in two museums. Both robots demonstrated safe and reliable navigation in proximity of people. They also interacted with museum visitor through various means, including the Web. Probabilistic algorithms and learning are pervasive in their software architectures. This article sketches the basic software, summarizes results, compares the robots, and discusses open problems. ---------- @ARTICLE{Thrun03f, S. Thrun. Towards a framework for human-robot interaction. The goal of this article is to introduce the reader to the rich and vibrant field of robotics, in hopes of laying out an agenda for future research on human robot interaction. Robotics is a field in change; the meaning of the term "robot" today differs substantially from the term just a decade ago. The primary purpose of this article is to provide a comprehensive description of past and present-day robotics. It identifies the major epochs of robotic technology and systems--from industrial to service robotics--and characterizes the different styles of human robot interaction paradigmatic for each epoch. To set an agenda for research on human robot interaction, the article articulates some of the most pressing open questions pertaining to modern-day human robot interaction. ---------- @ARTICLE{Verma04a, V. Verma, R. Simmons, G. Gordon, and S. Thrun. Particle filters for fault diagnosis. This article presents a number of complementary algorithms for detecting faults on-board operating robots, where we define a fault as a deviation from expected behavior. ---------- @ARTICLE{Thrun01h, S. Thrun. Is robotics going statistics? The field of probabilistic robotics. In the 1970s, most research in robotics presupposed the availability of exact models, of robots and their environments. Little emphasis was placed on sensing and the intrinsic limitations of modeling complex physical phenomena. This changed in the mid-1980s, when the paradigm shifted towards reactive techniques. Reactive controllers rely on capable sensors to generate robot control. Rejections of models were typical for researchers in this field. Since the mid-1990s, a new approach has begun to emerge: probabilistic robotics. This approach relies on statistical techniques to seamlessly integrate imperfect models and imperfect sensing. The present article describes the basics of probabilistic robotics and highlights some of its recent successes. ---------- @TECHREPORT{Glover03a, J. Glover, D. Holstius, M. Manojlovich, K. Montgomery, A. Powers, J. Wu, S. Kiesler, J. Matthews, and S. Thrun. A robotically-augmented walker for older adults. Many older adults use walkers to improve their stability and safety while walking. We have developed a robotically augmented walker to reduce fall risk and confusion, and to increase walker convenience and enjoyment. Using a modified version of the CARMEN navigation software suite [11], the walker is capable of parking itself and returning to the user when signaled by remote control. The system also supports navigation in large indoor environments by providing simple directions to target locations such as a cafeteria. The walker received positive reviews during informal testing with residents of a Pennsylvania residence facility for older adults. This research is sponsored by the National Science Foundation under the ITR Program, which is gratefully acknowledged. The views and concussions contained in this document are those of the authors and should not be interpreted as necessarily representing official policies of endorsements, either expressed or implied, of the United States Government of the National Science Foundation. ---------- @TECHREPORT{Likhachev03c, M. Likhachev, G. Gordon, and S. Thrun. ARA*: Formal analysis. In real world problems, time for deliberation is often limited. Anytime algorithms are beneficial in these conditions as they usually find a first, possibly highly suboptimal, solution very fast and then continually work on improving the solution until allocated time expires. While anytime algorithms are popular, existing anytime search methods are unable to provide a measure of goodness of their results. In this paper we propose the ARA* algorithm. ARA* is an anytime heuristic search which tunes its performance bound based on available search time. It starts by finding a suboptimal solution quickly using a loose bound, then tightens the bound progressively as time allows. Given enough time it finds a provably optimal solution. In addition to the theoretical analysis we demonstrate the practical utility of ARA* with experiments on a simulated robot kinematic arm and dynamic path planning problem for an outdoor rover.