Sanjiv Singh

IROS Conference 2019 Conference Paper

Maximum Likelihood Path Planning for Fast Aerial Maneuvers and Collision Avoidance

• Ji Zhang 0003
• Chen Hu
• Rushat Gupta Chadha
• Sanjiv Singh

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

IROS Conference 2018 Conference Paper

P-CAP: Pre-Computed Alternative Paths to Enable Aggressive Aerial Maneuvers in Cluttered Environments

• Ji Zhang 0003
• Rushat Gupta Chadha
• Vivek Velivela
• Sanjiv Singh

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.

ICRA Conference 2017 Conference Paper

Enabling aggressive motion estimation at low-drift and accurate mapping in real-time

• Ji Zhang 0003
• Sanjiv Singh

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

IROS Conference 2016 Conference Paper

Long-range GPS-denied aerial inertial navigation with LIDAR localization

• Garrett Hemann
• Sanjiv Singh
• Michael Kaess

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.

ICRA Conference 2016 Conference Paper

On degeneracy of optimization-based state estimation problems

• Ji Zhang 0003
• Michael Kaess
• Sanjiv Singh

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.

ICRA Conference 2015 Conference Paper

Visual-lidar odometry and mapping: low-drift, robust, and fast

• Ji Zhang 0003
• Sanjiv Singh

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.

IROS Conference 2014 Conference Paper

Guaranteed road network search with small unmanned aircraft

• Michael Dille
• Ben Grocholsky
• Sanjiv Singh

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

IROS Conference 2014 Conference Paper

Real-time depth enhanced monocular odometry

• Ji Zhang 0003
• Michael Kaess
• Sanjiv Singh

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.

IROS Conference 2013 Conference Paper

3D perception for accurate row following: Methodology and results

• Ji Zhang 0003
• Andrew Chambers
• Silvio M. Maeta
• Marcel Bergerman
• Sanjiv Singh

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.

ICRA Conference 2013 Conference Paper

Infrastructure-free shipdeck tracking for autonomous landing

• Sankalp Arora
• Sezal Jain
• Sebastian A. Scherer
• Stephen T. Nuske
• Lyle Chamberlain
• Sanjiv Singh

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.

ICRA Conference 2013 Conference Paper

RRT*-AR: Sampling-based alternate routes planning with applications to autonomous emergency landing of a helicopter

• Sanjiban Choudhury
• Sebastian A. Scherer
• Sanjiv Singh

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.

ICRA Conference 2013 Conference Paper

Sparse Tangential Network (SPARTAN): Motion planning for micro aerial vehicles

• Hugh Cover
• Sanjiban Choudhury
• Sebastian A. Scherer
• Sanjiv Singh

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.

IROS Conference 2012 Conference Paper

A practical obstacle detection system for autonomous orchard vehicles

• Gustavo Medeiros Freitas
• Bradley Hamner
• Marcel Bergerman
• Sanjiv Singh

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.

ICRA Conference 2012 Conference Paper

First results in autonomous landing and obstacle avoidance by a full-scale helicopter

• Sebastian A. Scherer
• Lyle Chamberlain
• Sanjiv Singh

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.

ICRA Conference 2012 Conference Paper

Global pose estimation with limited GPS and long range visual odometry

• Joern Rehder
• Kamal Gupta
• Stephen T. Nuske
• Sanjiv Singh

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.

IROS Conference 2012 Conference Paper

Monocular visual navigation of an autonomous vehicle in natural scene corridor-like environments

• Ji Zhang 0003
• George Kantor
• Marcel Bergerman
• Sanjiv Singh

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.

ICRA Conference 2012 Conference Paper

Results with autonomous vehicles operating in specialty crops

• Marcel Bergerman
• Sanjiv Singh
• Bradley Hamner

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

ICRA Conference 2011 Conference Paper

Distributed coordination and data fusion for underwater search

• Geoffrey A. Hollinger
• Srinivas Yerramalli
• Sanjiv Singh
• Urbashi Mitra
• Gaurav S. Sukhatme

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.

IROS Conference 2011 Conference Paper

Multiple-objective motion planning for unmanned aerial vehicles

• Sebastian A. Scherer
• Sanjiv Singh

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.

IROS Conference 2011 Conference Paper

Perception for a river mapping robot

• Andrew Chambers
• Supreeth Achar
• Stephen T. Nuske
• Joern Rehder
• Bernd Kitt
• Lyle Chamberlain
• Justin Haines
• Sebastian A. Scherer

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.

ICRA Conference 2011 Conference Paper

Self-supervised segmentation of river scenes

• Supreeth Achar
• Bharath Sankaran
• Stephen T. Nuske
• Sebastian A. Scherer
• Sanjiv Singh

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.

IROS Conference 2011 Conference Paper

Yield estimation in vineyards by visual grape detection

• Stephen T. Nuske
• Supreeth Achar
• Terry Bates
• Srinivasa G. Narasimhan
• Sanjiv Singh

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.

ICRA Conference 2010 Conference Paper

Multi-robot coordination with periodic connectivity

• Geoffrey A. Hollinger
• Sanjiv Singh

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.

ICRA Conference 2010 Conference Paper

Robust robotic assembly through contingencies, plan repair and re-planning

• Frederik W. Heger
• Sanjiv Singh

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.

ICRA Conference 2009 Conference Paper

Combining search and action for mobile robots

• Geoffrey A. Hollinger
• Dave Ferguson 0001
• Siddhartha S. Srinivasa
• Sanjiv Singh

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.

ICRA Conference 2009 Conference Paper

Efficient C-space and cost function updates in 3D for unmanned aerial vehicles

• Sebastian A. Scherer
• Dave Ferguson 0001
• Sanjiv Singh

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.

IROS Conference 2009 Conference Paper

Mobile robotic dynamic tracking for assembly tasks

• Bradley Hamner
• Seth Koterba
• Jane Shi
• Reid G. Simmons
• Sanjiv Singh

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.

IROS Conference 2009 Conference Paper

Modeling mobile robot motion with polar representations

• Joseph Djugash
• Sanjiv Singh
• Ben Grocholsky

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.

ICRA Conference 2008 Conference Paper

Decentralized mapping of robot-aided sensor networks

• Joseph Djugash
• Sanjiv Singh
• Ben Grocholsky

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.

IROS Conference 2008 Conference Paper

Overcoming sensor noise for low-tolerance autonomous assembly

• Brennan Sellner
• Frederik W. Heger
• Laura M. Hiatt
• Nik A. Melchior
• Stephen N. Roderick
• Dave Akin
• Reid G. Simmons
• Sanjiv Singh

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.

ICRA Conference 2008 Conference Paper

Tracking a moving target in cluttered environments with ranging radios

• Geoffrey A. Hollinger
• Joseph Djugash
• Sanjiv Singh

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.

ICRA Conference 2007 Conference Paper

Flying Fast and Low Among Obstacles

• Sebastian A. Scherer
• Sanjiv Singh
• Lyle Chamberlain
• Srikanth Saripalli

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.

ICRA Conference 2007 Conference Paper

Probabilistic Strategies for Pursuit in Cluttered Environments with Multiple Robots

• Geoffrey A. Hollinger
• Athanasios Kehagias
• Sanjiv Singh

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.

IROS Conference 2006 Conference Paper

Learning to Drive Among Obstacles

• Bradley Hamner
• Sebastian A. Scherer
• Sanjiv Singh

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

ICRA Conference 2006 Conference Paper

Range-only SLAM for Robots Operating Cooperatively with Sensor Networks

• Joseph Djugash
• Sanjiv Singh
• George Kantor
• Wei Zhang 0023

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

IROS Conference 2004 Conference Paper

Omnidirectional visual odometry for a planetary rover

• Peter Corke
• Dennis Strelow
• Sanjiv Singh

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.

IROS Conference 2004 Conference Paper

Preliminary results in sliding autonomy for assembly by coordinated teams

• Jonathan Brookshire
• Sanjiv Singh
• Reid G. Simmons

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.

IROS Conference 2003 Conference Paper

Experimental results in range-only localization with radio

• Derek Kurth
• George Kantor
• Sanjiv Singh

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.

IROS Conference 2003 Conference Paper

Motion planning for a mobile manipulator with imprecise locomotion

• Dong Hun Shin
• Bradley Hamner
• Sanjiv Singh
• Myung Hwangbo

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.

IROS Conference 2002 Conference Paper

An empirical comparison of methods for image-based motion estimation

• Henele Adams
• Sanjiv Singh
• Dennis Strelow

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.

IROS Conference 2002 Conference Paper

Autonomous coverage operations in semi-structured outdoor environments

• Parag H. Batavia
• Stephan Roth
• Sanjiv Singh

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.

ICRA Conference 2002 Conference Paper

Obstacle Detection in Smooth High Curvature Terrain

• Parag H. Batavia
• Sanjiv Singh

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.

ICRA Conference 2002 Conference Paper

Preliminary Results in Range-Only Localization and Mapping

• George Kantor
• Sanjiv Singh

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.

IROS Conference 2001 Conference Paper

Extending shape-from-motion to noncentral onmidirectional cameras

• Dennis Strelow
• Jeffrey Mishler
• Sanjiv Singh
• Herman Herman

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.

ICRA Conference 2001 Conference Paper

Obstacle Detection Using Adaptive Color Segmentation and Color Stereo Homography

• Parag H. Batavia
• Sanjiv Singh

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.

ICRA Conference 2000 Conference Paper

Recent Progress in Local and Global Traversability for Planetary Rovers

• Sanjiv Singh
• Reid G. Simmons
• Trey Smith
• Anthony Stentz
• Vandi Verma
• Alex Yahja
• Kurt Schwehr

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.

IROS Conference 1998 Conference Paper

A robotic excavator for autonomous truck loading

• Anthony Stentz
• John Bares
• Sanjiv Singh
• Patrick Rowe

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.

ICRA Conference 1998 Conference Paper

Framed-Quadtree Path Planning for Mobile Robots Operating in Sparse Environments

• Alex Yahja
• Anthony Stentz
• Sanjiv Singh
• Barry Brumitt

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.

IROS Conference 1998 Conference Paper

Modeling and identification of soil-tool interaction in automated excavation

• Oscar Luengo
• Sanjiv Singh
• Howard Cannon

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.

ICRA Conference 1998 Conference Paper

Multi-Resolution Planning for Earthmoving

• Sanjiv Singh
• Howard Cannon

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.

IROS Conference 1997 Conference Paper

Recent results in the grading of vegetative cuttings using computer vision

• Sanjiv Singh
• Mike Montemerlo

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.

ICRA Conference 1996 Conference Paper

Robot planning in the space of feasible actions: two examples

• Sanjiv Singh
• Alonzo Kelly

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.

ICRA Conference 1995 Conference Paper

Learning to predict Resistive Forces During Robotic Excavation

• Sanjiv Singh

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.

ICRA Conference 1994 Conference Paper

First Results in the Autonomous Retrieval of Buried Objects

• Herman Herman
• Sanjiv Singh

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

IROS Conference 1992 Conference Paper

Task Planning For Robotic Excavation

• Sanjiv Singh
• Reid G. Simmons

IROS Conference 1989 Conference Paper

Position Based Path Tracking for Wheeled Mobile Robots

• Sanjiv Singh
• Dong Hun Shin

ICRA Conference 1986 Conference Paper

Robot path planning using intersecting convex shapes

• Sanjiv Singh
• Meghanad D. Wagh

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.