We propose a planning method to enable fast autonomous flight in cluttered environments. Typically, autonomous navigation through a complex environment requires a continuous search on a graph generated by a k-connected grid or a probabilistic scheme. As the vehicle travels, updating the graph with data from onboard sensors is expensive as is the search on the graph especially if the paths must be kinodynamically feasible. We propose to avoid the online search to reduce the computational complexity. Our method models the environment differently in two separate regions. Obstacles are considered to be deterministically known within the sensor range and probabilistically known beyond the sensor range. Instead of searching for the path with the lowest cost (typically the shortest path), the method maximizes the likelihood to reach the goal in determining the immediate next step for navigation. With such a problem formulation, the online method realized by a trajectory library can determine a path within 0.2-0.3ms using a single CPU thread on a modem embedded computer. In experiments, it enables a lightweight UAV to fly at 10m/s in a cluttered forest environment (see Fig. 1 as an example).

We propose a novel method to enable fast autonomous flight in cluttered environments. Typically, autonomous navigation through a complex environment requires a continuous heuristic search on a graph generated by a k-connected grid or a probabilistic scheme. As the vehicle progresses, modification of the graph with data from onboard sensors is expensive as is search on the graph, especially if the paths must be kino-dynamically feasible. We suggest that computation needed to find safe paths during fast flight can be greatly reduced if we precompute and carefully arrange a dense set of alternative paths before the flight. Any prior map information can be used to prune the alternative paths to come up with a data structure that enables very fast online computation to deal with obstacles that are not on the map but only detected by onboard sensors. To test this idea, we have conducted a large number of flight experiments in structured (large industrial facilities) and unstructured (forests-like) environments. We show that even in the most unstructured environments, this method enables flight at a speed up to 10m/s while avoiding obstacles detected from onboard sensors.

We present a data processing pipeline to online estimate ego-motion and build a map of the traversed environment, leveraging data from a 3D laser, a camera, and an IMU. Different from traditional methods that use a Kalman filter or factor-graph optimization, the proposed method employs a sequential, multi-layer processing pipeline, solving for motion from coarse to fine. The resulting system enables high-frequency, low-latency ego-motion estimation, along with dense, accurate 3D map registration. Further, the system is capable of handling sensor degradation by automatic reconfiguration bypassing failure modules. Therefore, it can operate in the presence of highly dynamic motion as well as in dark, texture-less, and structure-less environments. During experiments, the system demonstrates 0.22% of relative position drift over 9.3km of navigation and robustness w.r.t aggressive motion such as highway speed driving (up to 33m/s).

Positioning and mapping can be conducted accurately by state-of-the-art state estimation methods. However, reliability of these methods is largely based on avoiding degeneracy that can arise from cases such as scarcity of texture features for vision sensors and lack of geometrical structures for range sensors. Since the problems are inevitably solved in uncontrived environments where sensors cannot function with their highest quality, it is important for the estimation methods to be robust to degeneracy. This paper proposes an online method to mitigate for degeneracy in optimization-based problems, through analysis of geometric structure of the problem constraints. The method determines and separates degenerate directions in the state space, and only partially solves the problem in well-conditioned directions. We demonstrate utility of this method with data from a camera and lidar sensor pack to estimate 6-DOF ego-motion. Experimental results show that the system is able to improve estimation in environmentally degenerate cases, resulting in enhanced robustness for online positioning and mapping.

Despite significant progress in GPS-denied autonomous flight, long-distance traversals (> 100 km) in the absence of GPS remain elusive. This paper demonstrates a method capable of accurately estimating the aircraft state over a 218 km flight with a final position error of 27 m, 0.012% of the distance traveled. Our technique efficiently captures the full state dynamics of the air vehicle with semi-intermittent global corrections using LIDAR measurements matched against an a priori Digital Elevation Model (DEM). Using an error-state Kalman filter with IMU bias estimation, we are able to maintain a high-certainty state estimate, reducing the computation time to search over a global elevation map. A sub region of the DEM is scanned with the latest LIDAR projection providing a correlation map of landscape symmetry. The optimal position is extracted from the correlation map to produce a position correction that is applied to the state estimate in the filter. This method provides a GPS-denied state estimate for long range drift-free navigation. We demonstrate this method on two flight data sets from a full-sized helicopter, showing significantly longer flight distances over the current state of the art.

Here, we present a general framework for combining visual odometry and lidar odometry in a fundamental and first principle method. The method shows improvements in performance over the state of the art, particularly in robustness to aggressive motion and temporary lack of visual features. The proposed on-line method starts with visual odometry to estimate the ego-motion and to register point clouds from a scanning lidar at a high frequency but low fidelity. Then, scan matching based lidar odometry refines the motion estimation and point cloud registration simultaneously.We show results with datasets collected in our own experiments as well as using the KITTI odometry benchmark. Our proposed method is ranked #1 on the benchmark in terms of average translation and rotation errors, with a 0.75% of relative position drift. In addition to comparison of the motion estimation accuracy, we evaluate robustness of the method when the sensor suite moves at a high speed and is subject to significant ambient lighting changes.

This work developed and evaluated a human-machine interface for the control of a roadable air vehicle (RAV), capable of surface driving, vertical takeoff, sustained flight, and landing. Military applications seek to combine the benefits of ground and air vehicles to maximize flexibility of movement but require that the operator have minimal pilot training. This makes the operator vulnerable to automation complexity issues; however, the operator will expect to be able to interact extensively and control the vehicle during flight. A mixed-initiative control approach mitigates these vulnerabilities by integrating the operator into many complex control domains in the way that they often expect---flexibly in charge, aware, but not required to issue every command. Intrinsic safety aspects were evaluated by comparing performance, decision making, precision, and workload for three RAV control paradigms: human-only, fully automated, and mixed-initiative control. The results suggest that the mixed-initiative paradigm leverages the benefits of human and automated control while also avoiding the drawbacks associated with each.

This paper presents novel data fusion methods that enable teams of vehicles to perform target search tasks without guaranteed communication. Techniques are introduced for merging estimates of a target's position from vehicles that regain contact after long periods of time, and a fully distributed team-planning algorithm is proposed, which utilizes limited shared information as it becomes available. The proposed data fusion techniques are shown to avoid overcounting information, which ensures that combining data from different vehicles will not decrease the performance of the search. Motivated by the underwater search domain, a realistic underwater acoustic communication channel is used to determine the probability of successful data transfer between two locations. The channel model is integrated into a simulation of multiple autonomous vehicles in both open water and harbor environments. The results demonstrate that the proposed distributed coordination techniques provide performance competitive with full communication.

The use of teams of small unmanned aircraft in real-world rapid-response missions is fast becoming a reality. One such application is search and detection of an evader in urban areas. This paper draws on results in graph-based pursuit-evasion, developing mappings from these abstractions to primitive motions that may be performed by aircraft, to produce search strategies providing guaranteed capture of road-bound targets. The first such strategy is applicable to evaders of arbitrary speed and agility, offering a conservative solution that is insensitive to motion constraints pursuers may possess. This is built upon to generate two strategies for capture of targets having a known speed bound that require searcher teams of much smaller size. The efficacy of these algorithms is demonstrated by evaluation in extensive simulation using realistic vehicle models across a spectrum of environment classes.

Visual odometry can be augmented by depth information such as provided by RGB-D cameras, or from lidars associated with cameras. However, such depth information can be limited by the sensors, leaving large areas in the visual images where depth is unavailable. Here, we propose a method to utilize the depth, even if sparsely available, in recovery of camera motion. In addition, the method utilizes depth by triangulation from the previously estimated motion, and salient visual features for which depth is unavailable. The core of our method is a bundle adjustment that refines the motion estimates in parallel by processing a sequence of images, in a batch optimization. We have evaluated our method in three sensor setups, one using an RGB-D camera, and two using combinations of a camera and a 3D lidar. Our method is rated #2 on the KITTI odometry benchmark irrespective of sensing modality, and is rated #1 among visual odometry methods.

Shipdeck landing is one of the most challenging tasks for a rotorcraft. Current autonomous rotorcraft use shipdeck mounted transponders to measure the relative pose of the vehicle to the landing pad. This tracking system is not only expensive but renders an unequipped ship unlandable. We address the challenge of tracking a shipdeck without additional infrastructure on the deck. We present two methods based on video and lidar that are able to track the shipdeck starting at a considerable distance from the ship. This redundant sensor design enables us to have two independent tracking systems. We show the results of the tracking algorithms in three different environments - field testing results on actual helicopter flights, in simulation with a moving shipdeck for lidar based tracking and in laboratory using an occluded, and, moving scaled model of a landing deck for camera based tracking. The complimentary modalities allow shipdeck tracking under varying conditions.

Engine malfunctions during helicopter flight poses a large risk to pilot and crew. Without a quick and coordinated reaction, such situations lead to a complete loss of control. An autonomous landing system could react quicker to regain control, however current emergency landing methods only generate dynamically feasible trajectories without considering obstacles. We address the problem of autonomously landing a helicopter while considering a realistic context: multiple potential landing zones, geographical terrain, sensor limitations and pilot contextual knowledge. We designed a planning system to generate alternate routes (AR) that respect these factors till touchdown exploiting the human-in-loop to make a choice. This paper presents an algorithm, RRT*-AR, building upon the optimal sampling-based algorithm RRT* to generate AR in realtime and examines its performance for simulated failures occurring in mountainous terrain, while maintaining optimality guarantees. After over 4500 trials, RRT*-AR outperformed RRT* by providing the human 280% more options 67% faster on average. As a result, it provides a much wider safety margin for unaccounted disturbances, and a more secure environment for a pilot. Using AR, the focus can now shift on delivering safety guarantees and handling uncertainties in these situations.

Micro aerial vehicles operating outdoors must be able to maneuver through both dense vegetation and across empty fields. Existing approaches do not exploit the nature of such an environment. We have designed an algorithm which plans rapidly through free space and is efficiently guided around obstacles. In this paper we present SPARTAN (Sparse Tangential Network) as an approach to create a sparsely connected graph across a tangential surface around obstacles. We find that SPARTAN can navigate a vehicle autonomously through an outdoor environment producing plans 172 times faster than the state of the art (RRT*). As a result SPARTAN can reliably deliver safe plans, with low latency, using the limited computational resources of a lightweight aerial vehicle.

Rows of trees such as in orchards, planted in straight parallel lines can provide navigation cues for autonomous machines that operate in between them. When the tree canopies are well managed, tree rows appear similar to corridor walls and a simple 2D sensing scheme suffices. However, when the tree canopies are three dimensional, or ground vegetation occludes tree trunks, it is necessary to use a three dimensional sensing mode. An additional complication in prolific canopies is that GPS is not reliable and hence is not suitable to register data from sensors onboard a traversing vehicle. Here, we present a method to register 3D data from a lidar sensor onboard a vehicle that must accurately determine its pose relative to the rows. We first register point cloud into a common reference frame and then determine the position of tree rows and trunks in the vicinity to determine the vehicle pose. Our method is tested online and with data from commercial orchards. Experimental results show that the accuracy is sufficient to enable accurate traversal between tree rows even when tree canopies do not approximate planar walls.

Specialty crops constitute a $45 billion/year industry. As opposed to crops such as wheat, cotton, corn and soybean, they are characterized by the need for intensive cultivation. Specialty crops growers currently face serious labor cost and availability problems, and few technological solutions exist to increase their efficiency given the past history of abundant supply of low-cost labor. This leads to an opportunity to use recent technological advances to not only increase efficiency and reduce labor costs in specialty crops production but also to support a domestic engineering solutions industry for specialty crops. We envision a family of reconfigurable vehicles that can be rapidly tasked to automate or augment pruning, thinning, harvesting, mowing, spraying, etc. They would share a common sensing and computing infrastructure, allowing applications created for one to be easily transferable to others - much like software applications today are transferable from one computer to another. In this paper we describe our work over the last three years designing and deploying a family of such vehicles, the Autonomous Prime Movers (APMs). The five vehicles completed so far have traveled autonomously over 300 km in research and commercial tree fruit orchards; preliminary results in time trials conducted by extension educators indicate efficiency gains of up to 58%.

Here we present an approach to estimate the global pose of a vehicle in the face of two distinct problems; first, when using stereo visual odometry for relative motion estimation, a lack of features at close range causes a bias in the motion estimate. The other challenge is localizing in the global coordinate frame using very infrequent GPS measurements. Solving these problems we demonstrate a method to estimate and correct for the bias in visual odometry and a sensor fusion algorithm capable of exploiting sparse global measurements. Our graph-based state estimation framework is capable of inferring global orientation using a unified representation of local and global measurements and recovers from inaccurate initial estimates of the state, as intermittently available GPS information may delay the observability of the entire state. We also demonstrate a reduction of the complexity of the problem to achieve real-time throughput. In our experiments, we show in an outdoor dataset with distant features where our bias corrected visual odometry solution makes a fivefold improvement in the accuracy of the estimated translation compared to a standard approach. For a traverse of 2km we demonstrate the capabilities of our graph-based state estimation approach to successfully infer global orientation with as few as 6 GPS measurements and with two-fold improvement in mean position error using the corrected visual odometry.

Currently deployed unmanned rotorcraft rely on carefully preplanned missions and operate from prepared sites and thus avoid the need to perceive and react to the environment. Here we consider the problems of finding suitable but previously unmapped landing sites given general coordinates of the goal and planning collision free trajectories in real time to land at the “optimal” site. This requires accurate mapping, fast landing zone evaluation algorithms, and motion planning. We report here on the sensing, perception and motion planning integrated onto a full-scale helicopter that flies completely autonomously. We show results from 8 experiments for landing site selection and 5 runs at obstacles. These experiments have demonstrated the first autonomous full-scale helicopter that successfully selects its own landing sites and avoids obstacles.

Safe robot navigation in tree fruit orchards requires that the vehicle be capable of robustly navigating between rows of trees and turning from one aisle to another; that the vehicle be dynamically stable, especially when carrying workers; and that the vehicle be able to detect obstacles on its way and adjust its speed accordingly. In this paper we address the latter, in particular the problem of detecting people and apple bins in the aisles between rows. One of our requirements is that the obstacle avoidance subsystem shouldn't add to the robot's hardware cost, so as to keep the acquisition cost to growers as low as possible. Therefore, we confine ourselves to solutions that use only the sensor suite already installed on the robot for navigation-in our case, a laser scanner, low-cost inertial measurement unit, and steering and wheel encoders. Our methodology is based on the classification and clustering of registered 3D points as obstacles. In the current implementation, obstacle avoidance takes in 3D point clouds collected in apple orchards and generates an off-line assessment of obstacle position. Tests conducted at our experimental orchard-like environment in Pittsburgh and an actual apple orchard in Washington state indicate that the method is able to detect people and bins located along the vehicle path. Stretch tests indicate that it is also capable of dealing with objects as small as 15 cm tall as long as they aren't covered by grass, and to detect people crossing the aisles at walking speed.

We present a monocular visual navigation methodology for autonomous orchard vehicles. Modern orchards are usually planted with straight and parallel tree rows that form a corridor-like environment. Our task consists of driving a vehicle autonomously along the tree rows. The original contributions of this paper are: 1) a method to recover vehicle rotation independently of translation by modeling the vehicle as a car-like robot driving on a 3D ground surface-the rotation is estimated from monocular images while the translation is measured by a wheel encoder; and 2) a method to fit the 3D points corresponding to the trees into straight lines via an optimization algorithm that minimizes the error variance on the robot lookahead point. Additionally, we use a simple vanishing point detection approach to find the ends of the tree rows. The vanishing point detection is integrated into the system via an extended Kalman filter. The methodology's robustness to environmental changes is validated in more than fifty experiments in research and commercial orchards, six of which are presented and discussed in detail.

We examine the scenario in which a mobile network of robots must search, survey, or cover an environment and communication is restricted by relative location. While many algorithms choose to maintain a connected network at all times while performing such tasks, we relax this requirement and examine the use of periodic connectivity, where the network must regain connectivity at a fixed interval. We propose an online algorithm that scales linearly in the number of robots and allows for arbitrary periodic connectivity constraints. To complement the proposed algorithm, we provide theoretical inapproximability results for connectivity-constrained planning. Finally, we validate our approach in the coordinated search domain in simulation and in real-world experiments.

Here we consider the problem of automatically segmenting images taken from a boat or low-flying aircraft. Such a capability is important for autonomous river following and mapping. The need for accurate segmentation in a wide variety of riverine environments challenges the state of the art vision-based methods that have been used in more structured environments such as roads and highways. Apart from the lack of structure, the principal difficulty is the large spatial and temporal variations in the appearance of water in the presence of nearby vegetation and with reflections from the sky. We propose a self-supervised method to segment images into `sky', `river' and `shore' (vegetation + structures) regions. Our approach uses assumptions about river scene structure to learn appearance models based on features like color, texture and image location which are used to segment the image. We validated our algorithm by testing on four datasets captured under varying conditions on different rivers. Our self-supervised algorithm had higher accuracy rates than a supervised alternative, often significantly more accurate, and does not need to be retrained to work under different conditions.

This paper presents coordination and data fusion methods for teams of vehicles performing target search tasks without guaranteed communication. A fully distributed team planning algorithm is proposed that utilizes limited shared information as it becomes available, and data fusion techniques are introduced for merging estimates of the target's position from vehicles that regain contact after long periods of time. The proposed data fusion techniques are shown to avoid overcounting information, which ensures that combining data from different vehicles will not decrease the performance of the search. Motivated by the underwater search domain, a realistic underwater acoustic communication channel is used to determine the probability of successful data transfer between two locations. The channel model is integrated into a simulation of multiple autonomous vehicles in both open ocean and harbor search scenarios. The simulated experiments demonstrate that distributed coordination with limited communication significantly improves team performance versus prior techniques that continually maintain connectivity.

We consider the perceptual challenges inherent in the robotic manipulation of previously unseen socks, with the end goal of manipulation by a household robot for laundry. The task poses challenging problems in modeling the appearance, shape and configuration of these textile items that tend to exhibit high variability in texture, design, and style while being highly articulated objects.

The harvest yield in vineyards can vary significantly from year to year and also spatially within plots due to variations in climate, soil conditions and pests. Fine grained knowledge of crop yields can allow viticulturists to better manage their vineyards. The current industry practice for yield prediction is destructive, expensive and spatially sparse - during the growing season sparse samples are taken and extrapolated to determine overall yield. We present an automated method that uses computer vision to detect and count grape berries. The method could potentially be deployed across large vineyards taking measurements at every vine in a non-destructive manner. Our berry detection uses both shape and visual texture and we can demonstrate detection of green berries against a green leaf background. Berry detections are counted and the eventual harvest yield is predicted. Results are presented for 224 vines (over 450 meters) of two different grape varieties and compared against the actual harvest yield as groundtruth. We calibrate our berry count to yield and find that we can predict yield of individual vineyard rows to within 9.8% of actual crop weight.

Sliding probe methods are designed for the in situ electrical property characterization of individual one-dimensional (1D) nanostructures by eliminating the contact resistance between the fixed-end support and the specimen. The key to achieve a high resolution is to keep a constant resistance between the other end of the specimen contacting to the sliding probe. To achieve this objective, we have developed several important techniques including multipoint continuous sliding, flexible probes, and specimen-shape adapting based on nanorobotic manipulation inside a transmission electron microscope (TEM). With a copper-nanowire-tipped probe, we have shown that a flexible probe facilitates the contact force control. The adapting of the shape of a probe tip is significant for keeping a constant contact area between the probe and the specimen. This can be implemented by using a soft probe or a tip with a shape resembling the profile of the specimen. Here we show that by flowing copper from a nanotube probe against the specimen, it is possible to make a well adapted shape of the tip to the specimen after the copper cooled down. By avoiding stick-slip motion and controlling the contact force and area, it will be possible to keep a constant contact resistance between the sliding probe and the specimen, hence significantly improve the measurement resolution. Sliding probe methods are an in situ technique characterized by higher resolution and simplicity in setup as compared with conventional two- and four-terminal methods, respectively. Furthermore, it is superior for local property characterization, which is of particular interest for hetero-structured nanomaterials and defect detection.

Enabling mobile robots to assemble large structures in constrained environments requires planning systems that are both capable of dealing with high complexity and can provide robust execution in the face of run-time failures. We achieve execution robustness through exception handling capabilities that are seamlessly integrated throughout the planning system. Having these recovery mechanisms in place allows us to leverage their capabilities to compensate for problems introduced by approximations made during planning. Turning an apparent problem into an opportunity, we are able to plan complex assembly tasks and execute them robustly without the computational cost associated with more sophisticated planners and apply some of the savings toward recovering from unforeseen run-time errors. We show results where simple planning strategies paired with exception-handling are able to achieve the same outcomes (and in less time) as more elaborate methods would.

We consider the problem of multi-robot coordination subject to constraints on the configuration. Specifically, we examine the case in which a mobile network of robots must search, survey, or cover an environment while remaining connected. While many algorithms utilize continual connectivity for such tasks, we relax this requirement and introduce the idea of periodic connectivity, where the network must regain connectivity at a fixed interval. We show that, in some cases, this problem reduces to the well-studied NP-hard multi-robot informative path planning (MIPP) problem, and we propose an online algorithm that scales linearly in the number of robots and allows for arbitrary periodic connectivity constraints. We prove theoretical performance guarantees and validate our approach in the coordinated search domain in simulation and in real-world experiments. Our proposed algorithm significantly outperforms a gradient method that requires continual connectivity and performs competitively with a market-based approach, but at a fraction of the computational cost.

We explore the interconnection between search and action in the context of mobile robotics. The task of searching for an object and then performing some action with that object is important in many applications. Of particular interest to us is the idea of a robot assistant capable of performing worthwhile tasks around the home and office (e.g., fetching coffee, washing dirty dishes, etc.). We prove that some tasks allow for search and action to be completely decoupled and solved separately, while other tasks require the problems to be analyzed together. We complement our theoretical results with the design of a combined search/action approximation algorithm that draws on prior work in search. We show the effectiveness of our algorithm by comparing it to state-of-the-art solvers, and we give empirical evidence showing that search and action can be decoupled for some useful tasks. Finally, we demonstrate our algorithm on an autonomous mobile robot performing object search and delivery in an office environment.

When operating in partially-known environments, autonomous vehicles must constantly update their maps and plans based on new sensor information. Much focus has been placed on developing efficient incremental planning algorithms that are able to efficiently replan when the map and associated cost function changes. However, much less attention has been placed on efficiently updating the cost function used by these planners, which can represent a significant portion of the time spent replanning. In this paper, we present the limited incremental distance transform algorithm, which can be used to efficiently update the cost function used for planning when changes in the environment are observed. Using this algorithm it is possible to plan paths in a completely incremental way starting from a list of changed obstacle classifications. We present results comparing the algorithm to the Euclidean distance transform and a mask-based incremental distance transform algorithm. Computation time is reduced by an order of magnitude for a UAV application. We also provide example results from an autonomous micro aerial vehicle with on-board sensing and computing.

This article compares several parameterizations and motion models for improving the estimation of the nonlinear uncertainty distribution produced by robot motion. In previous work, we have shown that the use of a modified polar parameterization provides a way to represent nonlinear measurements distributions in the Cartesian space as linear distributions in polar space. Following the same reasoning, we present a motion model extension that utilizes the same polar parameterization to achieve improved modeling of mobile robot motion in between measurements, gaining robustness with no additional overhead. We present both simulated and experimental results to validate the effectiveness of our approach.

Traditional industrial robots have been widely used in automotive manufacturing for nearly 30 years. However, there have been very few attempts to automate mobile robotic systems for final assembly operations, despite their potential for high flexibility and capability. This paper focuses on methods of tracking a dynamic moving vehicle that is similar to the vehicle body on a moving assembly line. We have investigated two tracking methods, one using a laser scanner and the other using a visual fiducial marker. We have also studied the tracking performance of a mobile base using the pure pursuit algorithm with low pass filtering. Experimental results are presented to illustrate the remaining main challenges in achieving robotic assembly on moving assembly lines.

A key problem in the deployment of sensor networks is that of determining the location of each sensor such that subsequent data gathered can be registered. We would also like the network to provide localization for mobile entities, allowing them to navigate and explore the environment. In this paper, we present a robust decentralized algorithm for mapping the nodes in a sparsely connected sensor network using range- only measurements and odometry from a mobile robot. Our approach utilizes an extended Kalman filter (EKF) in polar space allowing us to model the nonlinearities within the range-only measurements using Gaussian distributions. We also extend this unimodal centralized EKF to a multi-modal decentralized framework enabling us to accurately model the ambiguities in range-based position estimation. Each node within the network estimates its position along with its neighbor's position and uses a message-passing algorithm to propagate its belief to its neighbors. Thus, the global network localization problem is solved in pieces, by each node independently estimating its local network, greatly reducing the computation done by each node. We demonstrate the effectiveness of our approach using simulated and real-world experiments with little to no prior information about the node locations.

In this paper, we propose a framework for utilizing fixed, ultra-wideband ranging radio nodes to track a moving target node through walls in a cluttered environment. We examine both the case where the locations of the fixed nodes are known as well as the case where they are unknown. For the case when the fixed node locations are known, we derive a Bayesian room-level tracking method that takes advantage of the structural characteristics of the environment to ensure robustness to noise. We also develop a method using mixtures of Gaussians to model the noise characteristics of the radios. For the case of unknown fixed node locations, we present a two-step approach that first reconstructs the target node's path and then uses that path to determine the locations of the fixed nodes. We reconstruct the path by projecting down from a higher-dimensional measurement space to the 2D environment space using non-linear dimensionality reduction with Gaussian Process Latent Variable Models(GPLVMs). We then utilize the reconstructed path to map the locations of the fixed nodes using a Bayesian occupancy grid. We present experimental results verifying our methods in an office environment. Our methods are successful at tracking a moving target node and mapping the locations of fixed nodes using radio ranging data that are both noisy and intermittent.

The capability to assemble structures is fundamental to the use of robotics in precursor missions in orbit and on planetary surfaces. We have performed autonomous assembly in neutral buoyancy of elements of a space truss whose mating components require positioning tolerances of the same order of magnitude as the noise in the sensor systems used for the docking. Numerous trade-offs, design decisions, and innovations were made during the development of the assembly system in order to both reduce and compensate for the sensor noise. By using relative positioning, decoupling sensing and manipulation, caching high-quality position estimates, and developing a new waypoint-completion metric, we were able to reduce sensor noise to the sub-millimeter level and autonomously assemble components with millimeter tolerances. In this paper, we discuss our approaches to the problem and report the results of a series of autonomous assembly operations.

In this paper, we describe a method for coordinating multiple robots in a pursuit-evasion domain. We examine the problem of multiple robotic pursuers attempting to locate a non-adversarial mobile evader in an indoor environment. Unlike many other approaches to this problem, our method seeks to minimize expected time of capture rather than guaranteeing capture. This allows us to examine the performance of our algorithm in complex and cluttered environments where guaranteed capture is difficult or impossible with limited pursuers. We present a probabilistic formulation of the problem, discretize the environment, and define cost heuristics for use in planning. We then propose a scalable algorithm using an entropy cost heuristic that searches possible movement paths to determine coordination strategies for the robotic pursuers. We present simulated results describing the performance of our algorithm against state of the art alternatives in a complex office environment. Our algorithm successfully reduces capture time with limited pursuers in an environment beyond the scope of many other approaches.

Safe autonomous flight is essential for widespread acceptance of aircraft that must fly close to the ground. We have developed a method of collision avoidance that can be used in three dimensions in much the same way as autonomous ground vehicles that navigate over unexplored terrain. Safe navigation is accomplished by a combination of online environmental sensing, path planning and collision avoidance. Here we report results with an autonomous helicopter that operates at low elevations in uncharted environments some of which are densely populated with obstacles such as buildings, trees and wires. We have recently completed over 1000 successful runs in which the helicopter traveled between coarsely specified waypoints separated by hundreds of meters, at speeds up to 10 meters/sec at elevations of 5-10 meters above ground level. The helicopter safely avoids large objects like buildings and trees but also wires as thin as 6 mm. We believe this represents the first time an air vehicle has traveled this fast so close to obstacles. Here we focus on the collision avoidance method that learns to avoid obstacles by observing the performance of a human operator.

We are interested in the problem of a human operator who has to respond to requests for help from an autonomous robotic construction team. A difficult aspect of this problem is gaining an awareness of the requesting robot’s situation quickly enough to avoid slowing the whole team down. One approach to speeding the initial acquisition of situational awareness is to maintain a buffer of data, and play it back for the human when their help is needed. The paper reports on an experiment to determine the proper composition and length of this buffer for our domain of multi-robot construction. The experiments show that 5- 10 seconds of one raw video feed in combination with a processed display led to the fastest operator attainment of situational awareness. We draw several conclusions from this experiment, which may generalize to other scenarios.

A mobile robot we have developed is equipped with sensors to measure range to landmarks and can simultaneously localize itself as well as locate the landmarks. This modality is useful in those cases where environmental conditions preclude measurement of bearing (typically done optically) to landmarks. Here we extend the paradigm to consider the case where the landmarks (nodes of a sensor network) are able to measure range to each other. We show how the two capabilities are complimentary in being able to achieve a map of the landmarks and to provide localization for the moving robot. We present recent results with experiments on a robot operating in a randomly arranged network of nodes that can communicate via radio and range to each other using sonar. We find that incorporation of inter-node measurements helps reduce drift in positioning as well as leads to faster convergence of the map of the nodes. We find that addition of a mobile node makes the SLAM feasible in a sparsely connected network of nodes

This paper reports on an outdoor mobile robot that learns to avoid collisions by observing a human driver operate a vehicle equipped with sensors that continuously produce a map of the local environment. We have implemented steering control that models human behavior in trying to avoid obstacles while trying to follow a desired path. Here we present the formulation for this control system and its independent parameters, and then show how these parameters can be automatically estimated by observation of a human driver. We present results from experiments with a vehicle (both real and simulated) that avoids obstacles while following a prescribed path at speeds up to 4 m/sec. We compare the proposed method with another method based on principal component analysis, a commonly used learning technique. We find that the proposed method generalizes well and is capable of learning from a small number of examples

Recent research in human-robot interaction has investigated the concept of Sliding, or Adjustable, Autonomy, a mode of operation bridging the gap between explicit teleoperation and complete robot autonomy. This work has largely been in single-agent domains-involving only one human and one robot-and has not examined the issues that arise in multiagent domains. We discuss the issues involved in adapting Sliding Autonomy concepts to coordinated multiagent teams. In our approach, remote human operators have the ability to join, or leave, the team at will to assist the autonomous agents with their tasks (or aspects of their tasks) while not disrupting the team's coordination. Agents model their own and the human operator's performance on subtasks to enable them to determine when to request help from the operator. To validate our approach, we present the results of two experiments. The first evaluates the human/multirobot team's performance under four different collaboration strategies including complete teleoperation, pure autonomy, and two distinct versions of Sliding Autonomy. The second experiment compares a variety of user interface configurations to investigate how quickly a human operator can attain situational awareness when asked to help. The results of these studies support our belief that by incorporating a remote human operator into multiagent teams, the team as a whole becomes more robust and efficient

No abstract available.

We are developing a coordinated team of robots to assemble structures, a task that cannot be performed by any single robot. Even simple operations in this domain require complex interaction between multiple robots and the number of contingencies that must be addressed if the team is to act completely autonomously is prohibitively large. This scenario forces incorporation of a human operator. Ideally we would like a seamless interface between the robots and the operator such that the operator can interact with the system by helping it be more efficient or get out of a stuck condition or performing a task that the robots are not capable of themselves. We use an architecture that implements "sliding autonomy" to accomplish these goals. The system of robots can be fully autonomous as long as all is well. The system is capable of accepting input from the operator at any time, especially when it is unable to recover from a failure. We motivate this scenario with results from an extended series of experiments we have conducted with three robots that work together to dock both ends of a suspended beam. We show the difference in performance between a completely teleoperated system, a fully autonomous system, and one in which sliding autonomy has been incorporated.

Position estimation for planetary rovers has been typically limited to odometry based on proprioceptive measurements such as the integration of distance traveled and measurement of heading change. Here we present and compare two methods of online visual odometry suited for planetary rovers. Both methods use omnidirectional imagery to estimate motion of the rover. One method is based on robust estimation of optical flow and subsequent integration of the flow. The second method is a full structure-from-motion solution. To make the comparison meaningful we use the same set of raw corresponding visual features for each method. The dataset is an sequence of 2000 images taken during a field experiment in the Atacama desert, for which high resolution GPS ground truth is available.

No abstract available.

We present an early experimental result toward solving the localization problem with range-only sensors. We perform an experiment in which a mobile robot localizes using dead reckoning and range measurements to stationary radio-frequency beacons in its environment, incorporating the range measurements into the position estimate using a Kalman filter. This data set involves over 20,000 range readings to surveyed beacons while a robot moved continuously over a path for nearly 1 hour. Careful groundtruth accurate to a few centimeters was recorded during this motion. We show the improvement of the robot's position estimate over dead reckoning even when the range readings are very noisy. We extend this approach to the problem of simultaneous localization and mapping (SLAM), localizing both the robot and tag positions from noisy initial estimates.

This paper presents a motion planning method for mobile manipulators for which the base locomotion is less precise than the manipulator control. In such a case, it is advisable to move the base to discrete poses from which the manipulator can be deployed to cover a prescribed trajectory. The proposed method finds base poses that not only cover the trajectory but also meet constraints on a measure of manipulability. We propose a variant of the conventional manipulability measure that is suited to the trajectory control of the end effector of the mobile manipulator along an arbitrary curve in three space. Results with implementation on a mobile manipulator are discussed.

Detection of obstacles for autonomous vehicles is more difficult when the terrain is not locally planar and remains an open problem. We have developed an approach suited for obstacle detection in those cases where the terrain has significant curvature but is smooth enough that the obstacles are discrete. Our system consists of a low-cost scanning laser rangefinder and a novel algorithm that can reliably detect obstacles as small as 15 cm in curving terrain. This paper presents an analysis of the effectiveness of our system and a summary of experimental results from an outdoor mobile robot.

This paper presents methods of localization using cooperating landmarks (beacons) that provide the ability to measure range only. Recent advances in radio frequency technology make it possible to measure range between inexpensive beacons and a transponder Such a method has tremendous benefit since line of sight is not required between the beacons and the transponder and because the data association problem can be completely avoided. If the positions of the beacons are known, measurements from multiple beacons can be combined using probability grids to provide an accurate estimate of robot location. This estimate can be improved by using Monte Carlo techniques and Kalman filters to incorporate odometry data. Similar methods can be used to solve the simultaneous localization and mapping problem (SLAM) when beacon locations are uncertain. Experimental results are presented for robot localization. Tracking and SLAM algorithms are demonstrated in simulation.

This paper presents a comparison between methods that estimate motion of a camera from a sequence of video images. We implemented two methods: a homography based method that assumes planar environments; and shape-from-motion, a general method that can deal with a fully three dimensional world. Both methods were formulated in an iterative, online form to produce estimates of camera motion. We discuss a trade-off in accuracy and run time efficiency based on experimental results for these two general methods in relation to ground truth. We show how a variation of the homography method can produce accurate results in some cases when the environment is non-planar with low computational cost.

This paper presents a comprehensive navigation system capable of extended coverage operations in semi-structured environments. By semi-structured, we mean pre-mapped terrain that although locally smooth has potentially large changes in elevation and that is generally free of obstacles. The system has three key capabilities: it is able to track specified paths with high accuracy, detect small obstacles reliably, and plan coverage patterns to completely cover a specified area. These technologies have been combined and implemented on a mobile robot, which has accumulated over 90km of autonomous operation to date. Here we report on the components, the architecture, and experimental results.

Cameras and inertial sensors are good candidates to be deployed together for autonomous vehicle motion estimation, since each can be used to resolve the ambiguities in the estimated motion that results from using the other modality alone. We present an algorithm that computes optimal vehicle motion estimates by considering all of the measurements from a camera, rate gyro, and accelerometer simultaneously. Such optimal estimates are useful in their own right, and as a gold standard for the comparison of online algorithms. By comparing the motions estimated using visual and inertial measurements, visual measurements only, and inertial measurements only against ground truth, we show that using image and inertial data together can produce highly accurate estimates even when the results produced by each modality alone are very poor Our test datasets include both conventional and omnidirectional image sequences, and an image sequence with a high percentage of missing data.

Recent omnidirectional camera designs aim a conventional camera at a mirror that expands the camera's field of view. This wide view is ideal for three-dimensional vision tasks such as motion estimation and obstacle detection, but these applications require an accurate model of the imaging process. We present a full model of the imaging process, which includes the rotation and translation between the camera and mirror, and an algorithm that determines this relative position from observations of known points in a single image. We present tests of the model and of the calibration procedure for various amounts of misalignment between the mirror and camera. These tests show that the algorithm recovers the correct relative position, and that by using the full model, accurate shape-from-motion and stereo matching are possible even if the camera and mirror are severely misaligned.

Obstacle detection is a key component of autonomous systems. In particular, when dealing with large robots in unstructured environments, robust obstacle detection is vital. In this paper, we describe an obstacle detection methodology which combines two complementary methods: adaptive color segmentation, and stereo-based color homography. This algorithm is particularly suited for environments in which the terrain is relatively flat and of roughly the same color. We will show results in applying this method to an autonomous outdoor robot.

Algorithms for shape-from-motion simultaneously estimate the camera motion and scene structure. When extended to omnidirectional cameras, shape-from-motion algorithms are likely to provide robust motion estimates, in particular, because of the camera's wide field of view. In this paper, we describe both batch and online shape-from-motion algorithms for omnidirectional cameras, and a precise calibration technique that improves the accuracy of both methods. The shape-from-motion and calibration methods are general, and they handle a wide variety of omnidirectional camera geometries. In particular, the methods do not require that the camera-mirror combination have a single center of projection. We describe a noncentral camera that we have developed, and show experimentally that combining shape-from-motion with this design produces highly accurate motion estimates.

Autonomous planetary rovers operating in vast unknown environments must operate efficiently because of size, power and computing limitations. Recently, we have developed a rover capable of efficient obstacle avoidance and path planning. The rover uses binocular stereo vision to sense potentially cluttered outdoor environments. Navigation is performed by a combination of several modules that each "vote" for the next best action for the robot to execute. The key distinction of our system is that it produces globally intelligent behavior with a small computational resource - all processing and decision making are done on a single processor. These algorithms have been tested on our outdoor prototype rover, Bullwinkle, and have recently driven the rover 100 m at a speed of 15 cm/sec. In this paper we report on the extension on the systems that we have previously developed that were necessary to achieve autonomous navigation in this domain.

We suggest that planning for automated earthmoving operations such as digging a foundation or leveling a mound of soil, be treated at multiple levels. In a system that we have developed, a coarse-level planner is used to tessellate the volume to be excavated into smaller pieces that are sequenced in order to complete the task efficiently. Each of the smaller volumes is treated with a refined planner that selects digging actions based on constraint optimization over the space of prototypical digging actions. We discuss planners and the associated representations for two types of earthmoving machines: an excavator backhoe and a wheel loader. Experimental results from a full-scale automated excavator and simulated wheel loader are presented.

Mobile robots operating in vast outdoor unstructured environments often only have incomplete maps and must deal with new objects found during traversal. Path planning in such sparsely occupied regions must be incremental to accommodate new information, and, must use efficient representations. In previous work we have developed an optimal method D* to plan paths when the environment is not known ahead of time, but, rather is discovered as the robot moves around. To date, D* has been applied to a uniform grid representation for obstacles and free space. In this paper we propose the use of D* with framed quadtrees to improve the efficiency of planning paths in sparse environments. The new system has been tested in simulation as well on an autonomous jeep, equipped with local obstacle avoidance capabilities. We show how the use of framed quadtrees improves performance in terms of path length, computation speed, and memory requirements.

In the process of automating an earthmoving machine, we have developed a model of soil-tool interaction that predicts resistive forces experienced at the tool during digging. The predicted forces can be used to model the closed loop behavior of a controller that servoes the joints of the excavator so as to fill the bucket. In this paper, we extend the state of the art in two ways. First, we present a reformulated version of the classical fundamental equation of earthmoving often used to model soil-tool interaction. The new model includes consideration of previously unaccounted phenomena in the interaction of an excavator bucket as it moves through soil. Secondly, given that soil properties can vary even within a work site, we present an online method to estimate soil parameters from measured force data. Finally, we show how the predicted resistive force is used to estimate bucket trajectories.

Excavators are used for the rapid removal of soil and other materials in mines, quarries, and construction sites. The automation of these machines offers promise for increasing productivity and improving safety. To date, most research in this area has focused on selected parts of the problem. In this paper we present a system that completely automates the truck loading task. The excavator uses two scanning laser rangefinders to recognize and localize the truck, measure the soil face, and detect obstacles. The excavator's software decides where to dig in the soil, where to dump in the truck, and how to quickly move between these points while detecting and stopping for obstacles. The system was fully implemented and was demonstrated to load trucks as fast as human operators.

This paper reports on recent progress in the development of system to group populations of vegetative cuttings. The system is required to assign a classification to cuttings such that they appear uniform after a growing period using single two-dimensional monochrome images. We have developed a fast segmentation technique that is able to measure plant features and a supervised learning scheme that learns a mapping from the features to a scalar classification. We report results based on segmentation of over 2000 geranium cuttings. The system is able to process images at 2 Hz and has an accuracy of over 90%. Both metrics exceed human performance.

Several researchers in robotics and artificial intelligence have found that the commonly used method of planning in a state (configuration) space is intractable in certain domains. This may be because the C-space has very high dimensionality, the "C-space obstacles" are too difficult to compute, or because a mapping between desired states and actions is not straightforward. Instead of using an inverse model that relates a desired state to an action to be executed by a robot, we have used a methodology that selects between the feasible actions that a robot might execute, in effect, circumventing many of the problems faced by configuration space planners. In this paper we discuss the implications of such a method and present two examples of working systems that employ this methodology. One system drives an autonomous cross-country vehicle while the other controls a robotic excavator performing a trenching operation.

Few robot tasks require as forceful an interaction with the world as excavation. In order to effectively plan its actions, a robot excavator requires a method to predict the resistive forces experienced as it scoops soil from the terrain. This paper presents methods for a robot to predict resistive forces and to improve its predictions based on experience, using "learning" methods. A simple analytical model of a flat blade translating through soil is extended to account to for phenomena specific to motions of an excavator. In addition, the paper examines how representation and methodology affect prediction performance.

We have developed an autonomous system for the retrieval of buried objects. It is designed to detect, locate and retrieve buried objects. The system is equipped with a hydraulic robot, laser range finder and a subsurface sensor. First, subsurface sensing is used to detect and locate buried objects. If an object can be reached with one dig, the excavator retrieves it directly. Otherwise a layer of soil above the object is removed and another subsurface scan is made to get a more accurate estimate of the object location. This loop is repeated until the object is retrieved. The paper presents some recent results in sensing and excavation from experiments conducted on our testbed. There are numerous potential applications for this system-hazardous waste removal, maintenance of subsurface structure, construction, and removal of unexploded buried ordnance.>

We propose a methodology to automatically generate plans for a robot excavator like a bucket loader or a backhoe. The task is formulated as one of constrained optimization in an actkm space that is spanned by the parameters of a prototypical digging plan. We show how geometric and force constraints are lmposed on the action space to build the set of feasible plans, and discuss methods to optimize a cost function within this set. We discuss recent simulation results that demonstrate this method in action.

An automated path planning algorithm for a mobile robot in a structured environment is presented. An algorithm based on the Quine-McCluskey method of finding prime implicants in a logical expression is used to isolate all the largest rectangular free convex areas in a specified environment. The free convex areas are represented as nodes in a graph, and a graph traversal strategy that dynamically allocates costs to graph paths is used. Complexity of the algorithm and a strategy to trade optimality for smaller computation time are discussed.

This paper deals with an automated path planning algorithm for a mobile robot in a structured enviornment. The algorithm is based upon finding all the largest (prime) free convex areas in the environment and representing this information in the form of a graph. A graph traversal algorithm which exploits back-tracking as well as dynamic cost allocation to graph arcs is presented and simulated. A strategy to trade of the optimality of the results for a smaller computation time is described.