We present an algorithm for robust and real-time visual tracking under challenging illumination conditions characterized by poor lighting as well as sudden and drastic changes in illumination. Robustness is achieved by adapting illumination-invariant binary descriptors to dense image alignment using the Lucas and Kanade algorithm. The proposed adaptation preserves the Hamming distance under least-squares minimization, thus preserving the photometric invariance properties of binary descriptors. Due to the compactness of the descriptor, the algorithm runs in excess of 400 fps on laptops and 100 fps on mobile devices.

In this paper, we analyze and extend the recently proposed closed-form online pose-chain simultaneous localization and mapping (SLAM) algorithm. Pose-chains are a specific type of extremely sparse pose-graphs and a product of contemporary SLAM front-ends, which perform accurate visual odometry and reliable appearance-based loop detection. They are relevant for challenging robotic applications in large-scale 3-D environments for which frequent loop detection is not desired or not possible. Closed-form online pose-chain SLAM efficiently and accurately optimizes pose-chains by exploiting their Lie group structure. The convergence and optimality properties of this solution are discussed in detail and are compared against state-of-the-art iterative methods. We also provide a novel solution space, that of similarity transforms, which has not been considered earlier for the proposed algorithm. This allows for closed-form optimization of pose-chains that exhibit scale drift, which is important to monocular SLAM systems. On the basis of extensive experiments, specifically targeting 3-D pose-chains and using a total of 60 km of challenging binocular and monocular data, it is shown that the accuracy obtained by closed-form online pose-chain SLAM is comparable with that of state-of-the-art iterative methods, while the time it needs to compute its solution is orders of magnitudes lower. This novel SLAM technique thereby is relevant to a broad range of robotic applications and computational platforms.

We extend the Iterative Closest Point (ICP) algorithm to obtain a method for continuous-time trajectory estimation (CICP) suitable for SLAM from actuated lidar. Traditional solutions to SLAM from actuated lidar rely heavily on the accuracy of an auxiliary pose sensor to form rigid frames. These frames are then used with ICP to obtain accurate pose estimates. However, since lidar records a single range sample at time, any error in inter-sample sensor motion must be accounted for. This is not possible if the frame is treated as a rigid point cloud. In this work, instead of ICP we estimate a continuous-time trajectory that takes into account inter-sample pose errors. The trajectory is represented as a linear combination of basis functions and formulated as a solution to a (sparse) linear system without restrictive assumptions on sensor motion. We evaluate the algorithm on synthetic and real data and show improved accuracy in open-loop SLAM in comparison to state-of-the-art rigid registration methods.

Visual place recognition and loop closure is critical for the global accuracy of visual Simultaneous Localization and Mapping (SLAM) systems. We present a place recognition algorithm which operates by matching local query image sequences to a database of image sequences. To match sequences, we calculate a matrix of low-resolution, contrast-enhanced image similarity probability values. The optimal sequence alignment, which can be viewed as a discontinuous path through the matrix, is found using a Hidden Markov Model (HMM) framework reminiscent of Dynamic Time Warping from speech recognition. The state transitions enforce local velocity constraints and the most likely path sequence is recovered efficiently using the Viterbi algorithm. A rank reduction on the similarity probability matrix is used to provide additional robustness in challenging conditions when scoring sequence matches. We evaluate our approach on seven outdoor vision datasets and show improved precision-recall performance against the recently published seqSLAM algorithm.

A novel closed-form solution for pose-graph SLAM is presented. It optimizes pose-graphs of particular structure called pose-chains by employing an extended version of trajectory bending. Our solution is designed as a back-end optimizer to be used within systems whose front-end performs state-of-the-art visual odometry and appearance based loop detection. The optimality conditions of our closed-form method and that of state-of-the-art iterative methods are discussed. The practical relevance of their theoretical differences is investigated by extensive experiments using simulated and real data. It is shown using 49 kilometers of challenging binocular data that the accuracy obtained by our closed-form solution is comparable to that of state-of-the-art iterative solutions while the time it needs to compute its solution is a factor 50 to 200 times lower. This makes our approach relevant to a broad range of applications and computational platforms.

We present a vision-based mapping and localization system for operations in pipes such as those found in Liquified Natural Gas (LNG) production. A forward facing fisheye camera mounted on a prototype robot collects imagery as it is teleoperated through a pipe network. The images are processed offline to estimate camera pose and sparse scene structure where the results can be used to generate 3D renderings of the pipe surface. The method extends state of the art visual odometry and mapping for fisheye systems to incorporate geometric constraints based on prior knowledge of the pipe components into a Sparse Bundle Adjustment framework. These constraints significantly reduce inaccuracies resulting from the limited spatial resolution of the fisheye imagery, limited image texture, and visual aliasing. Preliminary results are presented for datasets collected in our fiberglass pipe network which demonstrate the validity of the approach.

Stereo visual odometry and dense scene reconstruction depend critically on accurate calibration of the extrinsic (relative) stereo camera poses. We present an algorithm for continuous, online stereo extrinsic re-calibration operating only on sparse stereo correspondences on a per-frame basis. We obtain the 5 degree of freedom extrinsic pose for each frame, with a fixed baseline, making it possible to model time-dependent variations. The initial extrinsic estimates are found by minimizing epipolar errors, and are refined via a Kalman Filter (KF). Observation covariances are derived from the Cramer-Rao lower bound of the solution uncertainty. The algorithm operates at frame rate with unoptimized Matlab code with over 1000 correspondences per frame. We validate its performance using a variety of real stereo datasets and simulations.

Traditional lidar simulations render surface models to generate simulated range data. For objects with welldefined surfaces, this approach works well, and traditional 3D scene reconstruction algorithms can be employed to automatically generate the surface models. This approach breaks down, though, for many trees, tall grasses, and other objects with fine-scale geometry: surface models do not easily represent the geometry, and automated reconstruction from real data is difficult. In this paper, we introduce a new stochastic volumetric model that better captures the complexities of real lidar data of vegetation and is far better suited for automatic modeling of scenes from field collected lidar data. We also introduce several methods for automatic modeling and for simulating lidar data utilizing the new model. To measure the performance of the stochastic simulation we use histogram comparison metrics to quantify the differences between data produced by the real and simulated lidar. We evaluate our approach on a range of real world datasets and show improved fidelity for simulating geo-specific outdoor, vegetation scenes.

In earlier work closed-form trajectory bending was shown to provide an efficient and accurate out-of-core solution for loop-closing exactly sparse trajectories. Here we extend it to fuse exactly sparse trajectories, obtained from relative pose estimates, with absolute orientation data. This allows us to close-the-loop using absolute orientation data only. The benefit is that our approach does not rely on the observations from which the trajectory was estimated nor on the probabilistic links between poses in the trajectory. It therefore is highly efficient. The proposed method is compared against regular fusion and an iterative trajectory bending solution using a 5 km long urban trajectory. Proofs concerning optimality of our method are provided.

In this paper, we present an approach to bounded optimal planning and flexible execution for a robot team performing a set of spatially distributed tasks related by temporal ordering constraints such as precedence or synchronization. Furthermore, the manner in which the temporal constraints are satisfied impacts the overall utility of the team, due to the existence of both routing and delay costs. We present a bounded optimal offline planner for task allocation and scheduling in the presence of such cross-schedule dependencies, and a flexible, distributed online plan execution strategy. The integrated system performs task allocation and scheduling, executes the plans smoothly in the face of real-world variations in operation speed and task execution time, and ensures graceful degradation in the event of task failure. We demonstrate the capabilities of our approach on a team of three pioneer robots operating in an indoor environment. Experimental results demonstrate that the approach is effective for constrained planning and execution in the face of real-world variations.

Empirical evidence shows that error growth in visual odometry is biased. A projective bias model is developed and its parameters are estimated offline from trajectories encompassing loops. The model is used online to compensate for bias and thereby significantly reduces error growth. We validate our approach with more than 25 km of stereo data collected in two very different urban environments from a moving vehicle. Our results demonstrate significant reduction in error, typically on the order of 50%, suggesting that our technique has significant applicability to deployed robot systems in GPS denied environments.

HRI studies in a Middle Eastern environment are subject to nuances and subtleties. This study explores the nature of interactions, in an uncontrolled environment, between a permanently deployed bi-lingual robot-receptionist and interlocutors of varied native tongues. We correlate an interlocutor's native language with their propensity for accepting an invite and the duration of the ensuing conversation. Subsequently, we present results that demonstrate significant disparity in interactional patterns between English and Arabic speakers. We also assess the importance of a transliterated Arabic input mode for encouraging user interaction.

Regular inspection for corrosion of the pipes used in Liquified Natural Gas (LNG) processing facilities is critical for safety. We argue that a visual perception system equipped on a pipe crawling robot can improve on existing techniques (Magnetic Flux Leakage, radiography, ultrasound) by producing high resolution registered appearance maps of the internal surface. To achieve this capability, it is necessary to estimate the pose of sensors as the robot traverses the pipes. We have explored two monocular visual odometry algorithms (dense and sparse) that can be used to estimate sensor pose. Both algorithms use a single easily made measurement of the scene structure to resolve the monocular scale ambiguity in their visual odometry estimates. We have obtained pose estimates using these algorithms with image sequences captured from cameras mounted on different robots as they moved through two pipes having diameters of 152mm (6") and 406mm (16"), and lengths of 6 and 4 meters respectively. Accurate pose estimates were obtained whose errors were consistently less than 1 percent for distance traveled down the pipe.

Pipe inspection is a critical activity in gas production facilities and many other industries. In this paper, we contribute a stereo visual odometry system for creating high resolution, sub-millimeter maps of pipe surfaces. Such maps provide both 3D structure and appearance information that can be used for visualization, cross registration with other sensor data, inspection and corrosion detection tasks. We present a range of optical configuration and visual odometry techniques that we use to achieve high accuracy while minimizing specular reflections. We show empirical results from a range of datasets to demonstrate the performance of our approach.

Hala is a bilingual (Arabic and English) culturally-sensitive robot receptionist located at Carnegie Mellon University in Qatar. We report results from Hala's deployment by comparing her English dialogue corpus to that of a similar monolingual robot (named "Tank") located at CMU's Pittsburgh campus. Specifically, we compare the average number of turns per interaction, duration of interactions, frequency of interactions with personal questions, rate of non-understandings, and rate of thanks after the robot's answer. We provide possible explanations for observed similarities and differences and highlight potential cultural implications on the interactions.

Traditional approaches to programming robots are generally inaccessible to non-robotics-experts. A promising exception is the learning from demonstration paradigm. Here a policy mapping world observations to action selection is learned, by generalizing from task demonstrations by a teacher. Most learning from demonstration work to date considers data from a single teacher. In this paper, we consider the incorporation of demonstrations from multiple teachers. In particular, we contribute an algorithm that handles multiple data sources, and additionally reasons about reliability differences between them. For example, multiple teachers could be inequally proficient at performing the demonstrated task. We introduce Demonstration Weight Learning (DWL) as a learning from demonstration algorithm that explicitly represents multiple data sources and learns to select between them, based on their observed reliability and according to an adaptive expert learning inspired approach. We present a first implementation of DWL within a simulated robot domain. Data sources are shown to differ in reliability, and weighting is found impact task execution success. Furthermore, DWL is shown to produce appropriate data source weights that improve policy performance.

As robots become more commonplace within society, the need for tools to enable non-robotics-experts to develop control algorithms, or policies, will increase. Learning from demonstration (LfD) offers one promising approach, where the robot learns a policy from teacher task executions. Our interests lie with robot motion control policies which map world observations to continuous low-level actions. In this work, we introduce advice-operator policy improvement (A-OPI) as a novel approach for improving policies within LfD. Two distinguishing characteristics of the A-OPI algorithm are data source and continuous state-action space. Within LfD, more example data can improve a policy. In A-OPI, new data is synthesized from a student execution and teacher advice. By contrast, typical demonstration approaches provide the learner with exclusively teacher executions. A-OPI is effective within continuous state-action spaces because high level human advice is translated into continuous-valued corrections on the student execution. This work presents a first implementation of the A-OPI algorithm, validated on a Segway RMP robot performing a spatial positioning task. A-OPI is found to improve task performance, both in success and accuracy. Furthermore, performance is shown to be similar or superior to the typical exclusively teacher demonstrations approach.

Learning by demonstration can be a powerful and natural tool for developing robot control policies. That is, instead of tedious hand-coding, a robot may learn a control policy by interacting with a teacher. In this work we present an algorithm for learning by demonstration in which the teacher operates in two phases. The teacher first demonstrates the task to the learner. The teacher next critiques learner performance of the task. This critique is used by the learner to update its control policy. In our implementation we utilize a 1-Nearest Neighbor technique which incorporates both training dataset and teacher critique. Since the teacher critiques performance only, they do not need to guess at an effective critique for the underlying algorithm. We argue that this method is particularly well-suited to human teachers, who are generally better at assigning credit to performances than to algorithms. We have applied this algorithm to the simulated task of a robot intercepting a ball. Our results demonstrate improved performance with teacher critiquing, where performance is measured by both execution success and efficiency.

Hierarchical state machines have proven to be a powerful tool for controlling autonomous robots due to their flexibility and modularity. For most real robot implementations, however, it is often the case that the control hierarchy is hand-coded. As a result, the development process is often time intensive and error prone. In this paper, we explore the use of an experts learning approach, based on Auer and colleagues' Exp3 (1995), to help overcome some of these limitations. In particular, we develop a modified learning algorithm, which we call rExp3, that exploits the structure provided by a control hierarchy by treating each state machine as an 'expert'. Our experiments validate the performance of rExp3 on a real robot performing a task, and demonstrate that rExp3 is able to quickly learn to select the best state machine expert to execute. Through our investigations in these environments, we identify a need for faster learning recovery when the relative performances of experts reorder, such as in response to a discrete environment change. We introduce a modified learning rule to improve the recovery rate in these situations and demonstrate through simulation experiments that rExp3 performs as well or better than Exp3 under such conditions.

This paper addresses the challenges and benefits of undergraduate robotics education in technologically underserved communities. We present two robotics courses that the authors designed and taught in Qatar and Ghana. While different in context and setting, these courses share a similar structure and approach. We describe and analyze our experiences in the two case studies, and extract lessons that are relevant to others teaching robotics; especially in underserved communities. We also address the impact of these courses on the local communities and the broader academic community

In this paper, we focus on human-robot interaction in a team task where we identify the need for peer-to-peer (P2P) teamwork, with no fixed hierarchy for decision making between robots and humans. Instead, all team members are equal participants and decision making is truly distributed. We have fully developed a P2P team within Segway Soccer, a research domain, built upon Robocup robot soccer, that we have introduced to explore the challenge of P2P coordination in human-robot teams with dynamic, adversarial tasks. We recently participated in the first Segway Soccer games between two competing teams at the 2005 RoboCup US Open. We believe these games are the first ever between two human-robot P2P teams. Based on the competition, we realized two different approaches to P2P teams. We present our robot-centric approach to P2P team coordination and contrast it to the human-centric approach of the opponent team.

As we progress towards a world where robots play an integral role in society, a critical problem that remains to be solved is the pickup team challenge; that is, dynamically formed heterogeneous robot teams executing coordinated tasks where little information is known a priori about the tasks, the robots, and the environments in which they would operate. Successful solutions to forming pickup teams would enable researchers to experiment with larger numbers of robots and enable industry to efficiently and cost-effectively integrate new robot technology with existing legacy teams. In this paper, we define the challenge of pickup teams and propose the treasure hunt domain for evaluating the performance of pickup teams. Additionally, we describe a basic implementation of a pickup team that can search and discover treasure in a previously unknown environment. We build on prior approaches in market-based task allocation and plays for synchronized task execution, to allocate roles amongst robots in the pickup team, and to execute synchronized team actions to accomplish the treasure hunt task

With the wide availability, high information content, and suitability for human environments of low-cost color cameras, machine vision is an appealing sensor for many robot platforms. For researchers interested in autonomous robot teams operating in highly dynamic environments performing complex tasks, such as robot soccer, fast color-based object recognition is very desirable. Indeed, there are a number of existing algorithms that have been developed within the community to achieve this goal. Many of these algorithms, however, do not adapt for variation in lighting intensity, thereby limiting their use to statically and uniformly lit indoor environments. In this paper, we present a new technique for color object recognition that can adapt to changes in illumination but remains computationally efficient. We present empirical results demonstrating the performance of our technique for both indoor and outdoor environments on a robot platform performing tasks drawn from the robot soccer domain. Additionally, we compare the computational speed of our new approach against CMVision, a fast open-source color segmentation library. Our performance results show that our technique is able to adapt to lighting variations without requiring significant additional CPU resources.

In this paper, we make two contributions. First, we present a new domain, called Segway Soccer, for investigating the coordination of dynamically formed, mixed human-robot teams within the realm of a team task that requires real-time decision making and response. Segway Soccer is a game of soccer between two teams consisting of Segway riding humans and Segway RMP-based robots. We believe Segway Soccer is the first game involving both humans and robots in cooperative roles and with similar capabilities. In conjunction with this new domain, we present our work towards developing a soccer playing robot using the Segway RMP platform and vision as its primary sensing modality. As Segway Soccer is set in the outdoors, we have developed novel vision algorithms to adapt to changes in lighting conditions. We present the domain of Segway Soccer, its inherent challenges, and our work towards this goal.

Static cameras are pervasive in a variety of environments. However it remains a challenging problem to extract and reason about high-level features from real-time and continuous observation of an environment. In this paper, we present CAMEO, the Camera Assisted Meeting Event Observer, which is a physical awareness system designed for use by an agent-based electronic assistant. CAMEO is an inexpensive high-resolution omnidirectional vision system designed to be used in meeting environments. The multiple camera design achieves the desired high image resolution and lower cost that can be achieved when compared to traditional omnicameras that make use of a single camera and mirror solution.

The Segway human transport (HT) is a one person dynamically self-balancing transportation vehicle. The Segway robot mobility platform (RMP) is a modification of the HT capable of being commanded by a computer for autonomous operation. With these platforms, we are investigating human/robot coordination in adversarial environments through the game, Segway soccer. The players include robots (RMPs) and humans (riding HTs). The rules of the game are a combination of soccer and ultimate Frisbee rules. In this paper, we provide two contributions. First, we examine the capabilities and limitations of the Segway and describe the mechanical systems necessary to create a robot Segway soccer player. Second, we provide a detailed analysis of several ball manipulation/kicking systems and the implementation results of the CM-RMP pneumatic ball manipulation system.

Adversarial multi-robot problems, where teams of robots compete with one another, require the development of approaches that span all levels of control and integrate algorithms ranging from low-level robot motion control, through to planning, opponent modeling, and multiagent learning. Small-size robot soccer, a league within the RoboCup initiative, is a prime example of this multi-robot team adversarial environment. In this paper, we describe some of the algorithms and approaches of our robot soccer team, CMDragons'02, developed for RoboCup 2002. Our team represents an integration of many components, several of which that are in themselves state-of-the-art, into a framework designed for fast adaptation and response to the changing environment.

We describe an approach, called improbability filtering, to rejecting false-positive observations from degrading the tracking performance of an extended Kalman-Bucy filter. Improbability filtering removes false-positives by rejecting low likelihood observations as determined by the model estimates. It offers a computationally fast and robust method for removing this form of white noise without the need for a more advanced filter. We describe an application of the improbability filter approach to extended Kalman-Bucy filters for tracking ten robots and a ball moving at speeds approaching 5 m s/sup -1/ both accurately and reliably in real-time based on the observations of a single color camera. The environment is highly dynamic and non-linear, as exemplified by the motion of the ball which varies from free rolling under friction, to roiling up 45/spl deg/ inclined walls at the boundary, to being manipulated in unpredictable ways by a mechanical apparatus on each robot. The sensing apparatus, a camera and color blob tracking algorithms, suffers from the usual noise, latency, intermittency, as well as from false-positives caused by the misidentification of an observed object with a nonnegligible likelihood.