nils-herrmann/clean_scirepeval huggingface dataset:
Particle Filters in Robotics

In recent years, particle filters have solved several hard perceptual problems in robotics. Early successes of particle filters were limited to low-dimensional estimation problems, such as the problem of robot localization in environments with known maps. More recently, researchers have begun exploiting structural properties of robotic domains that have led to successful particle filter applications in spaces with as many as 100,000 dimensions. The fact that every model--no mater how detailed--fails to capture the full complexity of even the most simple robotic environments has lead to specific tricks and techniques essential for the success of particle filters in robotic domains. This article surveys some of these recent innovations, and provides pointers to in-depth articles on the use of particle filters in robotics.
A probabilistic technique for simultaneous localization and door state estimation with mobile robots in dynamic environments

Virtually all existing mobile robot localization techniques operate on a static map of the environment. When the environment changes (e.g., doors are opened or closed), there is an opportunity to simultaneously estimate the robot's pose and the state of the environment. The resulting estimation problem is high-dimensional, rendering current localization techniques inapplicable. This paper proposes an efficient, factored estimation algorithm for mixed discrete-continuous state estimation. Our algorithm integrates particle filters for robot localization, and conditional binary Bayes filters for estimating the dynamic state of the environment. Experimental results illustrate that our algorithm is highly effective in estimating the status of doors, and outperforms a state-of-the-art localizer in dynamic environments.
Learning Occupancy Grids With Forward Sensor Models

This article describes a new algorithm for acquiring occupancy grid maps with mobile robots. Virtually all existing occupancy grid mapping algorithms decompose the highdimensional mapping problem into a collection of one-dimensional problems, where the occupancy of each grid cell is estimated independently. This induces conflicts that may lead to inconsistent maps. This article shows how to solve the mapping problem in the original, high-dimensional space, thereby maintaining all dependencies between neighboring cells. As a result, maps generated by our approach are often more accurate than those generated using traditional techniques. Our approach relies on a statistical formulation of the mapping problem using forward models. It employs the expectation maximization algorithm for searching maps that maximize the likelihood of the sensor measurements.
Quantitatively tight sample complexity bounds

I present many new results on sample complexity bounds (bounds on the future error rate of arbitrary learning algorithms). Of theoretical interest are qualitative and quantitative improvements in sample complexity bounds as well as some techniques and criteria for judging the tightness of sample complexity bounds. 
On the practical side, I show quantitative results (with true error rate bounds sometimes less than 0.01) for decision trees and neural networks with these sample complexity bounds applied to real world problems. I also present a technique for using both sample complexity bounds and (more traditional) holdout techniques. 
Together, the theoretical and practical results of this thesis provide a well-founded practical method for evaluating learning algorithm performance based upon both training and testing set performance. 
Code for calculating these bounds is provided.
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.
A Real-time Algorithm for Acquiring Multi-Planar Volumetric Models with Mobile Robots

This paper summarizes recent research on developing autonomous robot systems than can acquire volumetric 3D maps with mobile robots in real-time. The core of our system is a real-time version of the popular expectation algorithm, developed for extracting scalar surfaces from sets of range scans (Martin, Thrun, 2002). Maps generated by this algorithm consists of a small number of planar rectangular surfaces, which are augmented by fine-grained polygons for non-flat environmental features. Experimental results obtained in a corridor-type environment illustrate that compact and accurate maps can be acquired in real-time from range and camera data.
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.
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.
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 (a few
Particle Filters for Mobile Robot Localization

This chapter investigates the utility of particle filters in the context of mobile robotics. In particular, we report results of applying particle filters to the problem of mobile robot localization, which is the problem of estimating a robot’s pose relative to a map of its environment. The localization problem is a key one in mobile robotics, because it plays a fundamental role in various successful mobile robot systems; see e.g., (Cox and Wilfong 1990, Fukuda, Ito, Oota, Arai, Abe, Tanake and Tanaka 1993, Hinkel and Knieriemen 1988, Leonard, Durrant-Whyte and Cox 1992, Rencken 1993, Simmons, Goodwin, Haigh, Koenig and O’Sullivan 1997, Weis, Wetzler and von Puttkamer 1994) and various chapters in (Borenstein, Everett and Feng 1996) and (Kortenkamp, Bonasso and Murphy 1998). Occasionally, it has been referred to as “the most fundamental problem to providing a mobile robot with autonomous capabilities” (Cox 1991).
Learning occupancy grids with forward models

Presents a way to acquire occupancy grid maps with mobile robots. Virtually all existing occupancy grid mapping algorithms decompose the high-dimensional mapping problem into a collection of one-dimensional problems, where the occupancy of each grid cell is estimated independently of others. This induces conflicts that can lead to inconsistent maps. The paper shows how to solve the mapping problem in the original, high-dimensional space, thereby maintaining all dependencies between neighboring cells. As a result, maps generated by our approach are often more accurate than those generated using traditional techniques. Our approach relies on a rigorous statistical formulation of the mapping problem using forward models. It employs the expectation maximization algorithm for estimating maps, and a Laplacian approximation to determine uncertainty.
Monte carlo em for data-association and its applications in computer vision

Estimating geometry from images is at the core of many computer vision applications, whether it concerns the imaging geometry, the geometry of the scene, or both. Examples include image mosaicking, pose estimation, multi baseline stereo, and structure from motion. All these problems can be modeled probabilistically and translate into well-understood statistical estimation problems, provided the correspondence between measurements in the different images is known. 
I will show that, if the correspondence is not known, the statistically optimal estimate for the geometry can be obtained using the expectation-maximization (EM) algorithm. In contrast to existing techniques, the EM algorithm avoids the estimation bias associated with computing a single “best” set of correspondences, but rather considers the distribution over all possible correspondences consistent with the data. While the latter computation is intractable in general, I show that it can be approximated well in practice using Markov chain Monte Carlo sampling. As part of this, I have designed an efficient sampler specifically tuned to the correspondence problem. 
The resulting Monte Carlo EM approach represents the first truly multiview algorithm for geometric estimation with unknown correspondence. This is especially relevant in the structure from motion domain, where the state of the art relies on robust estimation of two or three-view geometric constraints. In addition, I will show that the probabilistic approach I propose allows for a seamless and principled way of integrating prior knowledge, appearance models, and statistical models for occlusion and clutter.
A Heuristic Search Algorithm for Acting Optimally in Markov Decision Processes with Deterministic Hidden State

We propose a heuristic search algorithm for finding optimal policies in a new class of sequential decision making problems. This class extends Markov decision processes by a limited type of hidden state, paying tribute to the fact that many robotic problems indeed possess hidden state. The proposed search algorithm exploits the problem formulation to devise a fast bound-searching algorithm, which in turn cuts down the complexity of finding optimal solutions to the decision making problem by orders of magnitude. Extensive comparisons with state-of-the-art MDP and POMDP algorithms illustrate the effectiveness of our approach.
Optimizing schedules for prioritized path planning of multi-robot systems

The coordination of robot motions is one of the fundamental problems for multi-robot systems. A popular approach to avoid planning in the high-dimensional composite configuration space is the prioritized and decoupled technique. In this paper we present a method for optimizing priority schemes for such prioritized and decoupled planning technique. 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 greatly 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.
A system for multi-agent coordination in uncertain environments

This paper present a multi-agent architecture for coordinating large numbers of mobile agents (e.g. robots) cooperating in uncertain environments. In particular, the Canadian Traveler Problem (CTP) is the problem of nding a shortest path to a goal location in a graph, where individual edges of the graph might or might not be traversable[1]. The agent has an initial probabilistic knowledge about the states of the edges. Whether or not an edge is traversable can only be found out by moving there. Hence, an optimal solution to a CTP is a contingency plan, which o ers alternative routes if edges are not available. Finding an optimal contingency plan is known to be NP-hard. We focus on the multi-agent CTP, which involves multiple agents attempting to reach multiple target locations. Finding an optimal solution is even harder, since the space of actions at each point in time is exponential in the number of agents. Our multi-agent architecture approaches the above mentioned set of intractable problems in an eÆcient, real-time manner. The architecture supports a large number of mobile, goal-driven information agents that strive to maximize their reward for reaching goals. These agents are coordinated at a higher level by dispatcher agents whose purpose is to maximize the total reward accumulated over time. Extensive experimental results have been obtained in the context of natural disaster relief. Our experiments have been carried out in a realistic simulation of Honduras after Hurricane Mitch destroyed most of the country's infrastructure.
Hierarchical POMDP Decomposition for A Conversational Robot

POMDPs provide a useful framework for decisionmaking in the presence of uncertainty. Finding solutions to large-scale problems, however, has proven computationally infeasible. We propose a hierarchical approach to POMDPs which takes advantage of structure in the domain to decompose the problem into a collection of smaller POMDPs. These can be solved independently, allowing us to solve larger problems than were previously possible. We apply this approach to the problem of humanrobot speech dialogues, and show that appropriate decomposition can yield signi cant computational time reduction when nding a POMDP solution.
A Probabilistic On-Line Mapping Algorithm for Teams of Mobile Robots

An efficient probabilistic algorithm for the concurrent mapping and localization problem that arises in mobile robotics is presented. The algorithm addresses the problem in which a team of robots builds a map on-line while simultaneously accommodating errors in the robots’ odometry. At the core of the algorithm is a technique that combines fast maximum likelihood map growing with a Monte Carlo localizer that uses particle representations. The combination of both yields an on-line algorithm that can cope with large odometric errors typically found when mapping environments with cycles. The algorithm can be implemented in a distributed manner on multiple robot platforms, enabling a team of robots to cooperatively generate a single map of their environment. Finally, an extension is described for acquiring three-dimensional maps, which capture the structure and visual appearance of indoor environments in three dimensions.
Using EM to Learn 3D Models of Indoor Environments with Mobile Robots

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 lowcomplexity 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.
Risk Sensitive Particle Filters

We propose a new particle filter that incorporates a model of costs when generating particles. The approach is motivated by the observation that the costs of accidentally not tracking hypotheses might be significant in some areas of state space, and next to irrelevant in others. By incorporating a cost model into particle filtering, states that are more critical to the system performance are more likely to be tracked. Automatic calculation of the cost model is implemented using an MDP value function calculation that estimates the value of tracking a particular state. Experiments in two mobile robot domains illustrate the appropriateness of the approach.
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.
A Bayesian Multiresolution Independence Test for Continuous Variables

In this paper we present a method of computing the posterior probability of conditional independence of two or more continuous variables from data, examined at several resolutions. Our approach is motivated by the observation that the appearance of continuous data varies widely at various resolutions, producing very different independence estimates between the variables involved. Therefore, it is difficult to ascertain independence without examining discretized data at several carefully selected resolutions. In our paper, we accomplish this using the exact computation of the posterior probability of independence, calculated analytically given a resolution. At each examined resolution and boundary placement, we assume a multinomial distribution with Dirichlet priors for the discretized table parameters, and compute the posterior using Bayesian integration. Across resolutions, we use a search procedure to approximate the Bayesian integral of probability over an exponential number of possible boundary placements. Our method generalizes to an arbitrary number variables in a straightforward manner. The test is suitable for Bayesian network learning algorithms that use independence tests to infer the network structure, in domains that contain any mix of continuous, ordinal discrete, and categorical variables.
Exploiting constraints during prioritized path planning for teams of mobile robots

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. We present a method for finding solvable 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 exists. By searching in the space of priorization schemes, our approach overcomes this limitation. To focus the search, our algorithm is guided by constraints generated from the task specification. To illustrate the appropriateness of this approach, the paper discusses experimental results obtained with real robots and through systematic robot simulation. The experimental results demonstrate that our approach successfully solves many more coordination problems than previous decoupled and prioritized techniques.
A Bayesian Algorithm for Simultaneous Localisation and Map Building

This paper describes a full probabilistic solution to the Simultaneous Localisation and Mapping (SLAM) problem. Previously, the SLAM problem could only be solved in real time through the use of the Kalman Filter. This generally restricts the application of SLAM methods to domains with straight-forward (analytic) environment and sensor models. In this paper the Sum-of-Gaussian (SOG) method is used to approximate more general (arbitrary) probability distributions. This representation permits the generalizations made possible by particle filter or Monte-Carlo methods, while inheriting the real-time computational advantages of the Kalman filter. The method is demonstrated by its application to sub-sea field data consisting of both sonar and visual observation of near-field landmarks.
Monte Carlo Localization with Mixture Proposal Distribution

Monte Carlo localization (MCL) is a Bayesian algorithm for mobile robot localization based on particle filters, which has enjoyed great practical success. This paper points out a limitation of MCL which is counter-intuitive, namely that better sensors can yield worse results. An analysis of this problem leads to the formulation of a new proposal distribution for the Monte Carlo sampling step. Extensive experimental results with physical robots suggest that the new algorithm is significantly more robust and accurate than plain MCL. Obviously, these results transcend beyond mobile robot localization and apply to a range of particle filter applications.
Decision-Theoretic, High-Level Agent Programming in the Situation Calculus

We propose a framework for robot programming which allows the seamless integration of explicit agent programming with decision-theoretic planning. Specifically, the DTGologmodel allows one to partially specify a control program in a highlevel, logical language, and provides an interpreter that, given a logical axiomatization of a domain, will determine the optimal completion of that program (viewed as a Markov decision process). We demonstrate the utility of this model with results obtained in an officedelivery robotics domain.