Publications

• Target Tracking Without Line of Sight Using Range from Radio
  G. Hollinger, J. Djugash, and S. Singh
  Autonomous Robots, 2011, doi: 10.1007/s10514-011-9239-y.
  Download: Details
  Summary:We propose a framework for utilizing fixed ultra-wideband ranging radio nodes to track a moving target radio node in an environment without guaranteed line of sight or accurate odometry. Our algorithm is successful at tracking a moving target node without odometry and mapping the locations of fixed nodes using radio ranging data that are both noisy and intermittent.

• Distributed Coordination and Data Fusion for Underwater Search
  G. Hollinger, S. Yerramalli, S. Singh, U. Mitra, and G. Sukhatme
  IEEE International Conference on Robotics and Automation, Shanghai, China, May 2011, pp. 349-355.
  Download: pdf
  Summary: We discuss underwater search with limited communication. We provide a fully distributed algorithm capable of operating at any level of communication. We also give theoretical analysis of data fusion techniques in the search domain.

• Improving the Efficiency of Clearing with Multi-agent Teams
  G. Hollinger, A. Kehagias, and S. Singh
  International Journal of Robotics Research, Vol. 29, No. 8, pp. 1088-1105, Jul. 2010.
  Download: Details
  Summary:We combine the adversarial and non-adversarial search problems into a common framework and develop an algorithm that performs well under both assumptions. We validate our approach in two complex simulated environments.

• GSST: Anytime Guaranteed Search
  G. Hollinger, A. Kehagias, and S. Singh
  Autonomous Robots, Vol. 29, No. 1, pp. 99-118, Jul. 2010.
  Download: Details
  Summary:We present an anytime algorithm for clearing an environment of an adversarial target with multiple searchers. The algorithm utilizes spanning trees of the environment to guide search, and it improves performance as more trees are examined. This algorithm is demonstrated on two complex graphs derived from physical environments, and several methods for generating candidate spanning trees are compared.

• Towards Experimental Analysis of Challenge Scenarios in Robotics
  G. Hollinger and S. Singh
  International Symposium on Experimental Robotics, Delhi, India, Dec. 2010.
  Download: pdf
  Summary: Challenge scenarios in robotics (e.g., the grand challenge and urban challenge) provide opportunities to analyze the performance of systems. We examine the possibility of simulated analysis of such challenge scenarios in the context of the MAGIC multi-robot challenge.

• Multi-robot Coordination with Periodic Connectivity
  G. Hollinger and S. Singh
  IEEE International Conference on Robotics and Automation, Anchorage, AK, May 2010, pp. 4457-4462.
  Download: pdf
  Summary: We examine the problem of multi-robot coordination subject to periodic connectivity constraints. Relaxing the standard notion of continual connectivity allows us to improve information gathering performance while maintaining robustness.

• A Graph Search Algorithm for Indoor Pursuit/Evasion
  A. Kehagias, G. Hollinger, and S. Singh
  Mathematical and Computer Modeling, Vol. 50, No. 9-10, pp. 1305-1317, Nov. 2009.
  Download: Details
  Summary: We provide a heuristic algorithm for guaranteed capture of an adversarial target in a built environment. The algorithm outperforms prior methods in the literature.

• Efficient, Guaranteed Search with Multi-agent Teams
  G. Hollinger, A. Kehagias, and S. Singh
  Robotics: Science and Systems, Seattle, WA, Jun. 2009.
  Download: pdf
  Summary: We combine the adversarial and non-adversarial search problems into a common framework and develop an algorithm that performs well under both assumptions. We validate our approach in two complex simulated environments.

• Combining Search and Action for Mobile Robots
  G. Hollinger, D. Ferguson, S. Srinivasa, and S. Singh
  IEEE International Conference on Robotics and Automation, Kobe, Japan, May 2009, pp. 952-957.
  Download: pdf
  Summary: We examine the problem of searching for an object and then performing a subsequent action on that object. We present theoretical analysis and implement the technique on a mobile manipulator.

• Efficient Multi-Robot Search for a Moving Target
  G. Hollinger, S. Singh, J. Djugash, and A. Kehagias
  The International Journal of Robotics Research, Vol. 28, No. 2, February, 2009, pp. 201-219.
  Details | Video 1, Video 2
  Summary: We present an algorithm for locating a non-adversarial moving target with multiple robotic searchers. We give a detailed analysis of the benefit of finite-horizon search with implicit coordination in the efficient search domain. We demonstrate the performance of our algorithm using both simulated data and data from ultra-wideband ranging radios.

• Anytime Guaranteed Search using Spanning Trees
  G. Hollinger, A. Kehagias, S. Singh, D. Ferguson, and S. Srinivasa
  tech. report CMU-RI-TR-08-36, Robotics Institute, Carnegie Mellon University, August, 2008
  Details | pdf [425KB] | copyrighted
  Summary: We present an anytime algorithm for clearing an environment of an adversarial target with multiple searchers. The algorithm utilizes spanning trees of the environment to guide search, and it improves performance as more trees are examined. This algorithm is demonstrated on two complex graphs derived from physical environments, and several methods for generating candidate spanning trees are compared.

• Proofs and Experiments in Scalable, Near-Optimal Search by Multiple Robots
  G. Hollinger, and S. Singh
  Robotics: Science and Systems, June, 2008. [Abstract]
  Download: pdf[409 KB] -- [Accompanying Video: 9.2MB] copyrighted
  Summary: We present theoretical analysis and experimental results showing the performance of a linearly scalable sequential allocation algorithm for finding a non-adversarial target with multiple robotic searchers. We show that the non-adversarial search problem optimizes a submodular objective function, which immediately leads to theoretical bounds on the performance of sequential allocation. We complement these theoretical results with experimental trials using ultra-wideband ranging radio sensors to assist in search.

• A Robust Method of Localization and Mapping Using Only Range
  J. Djugash, and S. Singh
  International Symposium on Experimental Robotics, July, 2008. [Abstract]
  Download: pdf[1548 KB] copyrighted
  Summary: We present a new formulation that gains robustness without sacrificing accuracy. Specifically, our method is shown to have significantly better performance with poor and even no initialization, infrequent measurements, and incorrect data association. We present results from a mobile robot equipped with high accuracy ground truth, operating over several kilometers.

• Tracking a Moving Target in Cluttered Environments with Ranging Radios
  G. Hollinger, J. Djugash, and S. Singh
  IEEE International Conference on Robotics and Automation, 2008. [Abstract]
  Download: pdf [384 KB] -- [Accompanying Video: 3.42MB] copyrighted
  Summary: We focus on the problem of tracking a mobile target using ranging radios. We present techniques for tracking with known radio node locations using both Gaussian Processes and an offset Gaussian technique. We also discuss an algorithm for reconstructing unknown radio node locations using dimensionality reduction with Gaussian Process Latent Variable Models. We validate our methods on data from a Pioneer robot operating in Newell-Simon Hall.

• Decentralized Mapping of Robot-Aided Sensor Networks
  J. Djugash, S. Singh, and B. Grocholsky
  IEEE International Conference on Robotics and Automation, 2008. [Abstract]
  Download: pdf [280 KB] -- [Accompanying Video: 4.8MB, Extended Video: 10.2MB] copyrighted
  Summary: In this paper, we present a robust decentralized algorithm for mapping the nodes in a sparsely connected sensor network using range-only measurements and motion from a mobile robot. Our approach utilizes an Extended Kalman Filter (EKF) in polar space, which lets us model the nonlinearities within the rangeonly measurements using Gaussian distributions. We extend this unimodal centralized EKF to a multi-modal decentralized framework.

• Coordinated Search in Cluttered Environments Using Range from Multiple Robots
  G. Hollinger, J. Djugash, and S. Singh
  Sixth International Conference on Field and Service Robotics, July, 2007. [Abstract]
  Download: pdf [402 KB] copyrighted
  Summary: We examine the problem of unified estimation and control in the multi-robot coordinated search domain. We extend our previous coordinated search framework to include noisy measurements from ranging radios. We show both simulated results and results in a laboratory environment with a Pioneer robot.

• Probabilistic Strategies for Pursuit in Cluttered Environments with Multiple Robots
  G. Hollinger, A. Kehagias, and S. Singh
  IEEE International Conference on Robotics and Automation, April, 2007. [Abstract]
  Download: pdf [264 KB] copyrighted
  Summary: We discuss a framework for coordinating multiple robots to efficiently search for a non-adversarial target in cluttered environments. We use finite-horizon search with a cost heuristic along with decoupled path planning to achieve high-performance and scalable algorithms in this domain. We show simulated results to verify the performance of our framework.

• Parrots: A Range Measuring Sensor Network
  W. Zhang, J. Djugash, and S. Singh
  tech. report CMU-RI-TR-06-05, Robotics Institute, Carnegie Mellon University, March, 2007. [Abstract]
  Download: pdf [371 KB] copyrighted
  Summary: This paper presents the implementation and design of a wireless sensor network developed to facilitate indoor mobile robot localization. The sensor network consists of homogeneous nodes, termed the Parrot, that can measure range to other nodes within the network using ultrasonic signals. The system has been successfully tested to localize and map individual nodes within an office environment. We present experimental results of accurately mapping and localizing the network structure with the presence of a mobile node.

• Preliminary Results in Tracking Mobile Targets Using Range Sensors from Multiple Robots
  E. Liao, G. Hollinger, J. Djugash, and S. Singh
  The 8th International Symposium on Distributed Autonomous Robotic Systems, June, 2006, pp. 125-134. [Abstract]
  Download: pdf [222 KB] copyrighted
  Summary: We examine algorithms for controlling robots during range-only tracking of a mobile target. We derive a range-only particle filter for tracking, and we discuss how a known map can be used to improve performance. We present an algorithm for dynamically positioning robots to maintain high tracking accuracy. We show simulated experiments in Player/Stage in an office environment.

• Range-Only SLAM for Robots Operating Cooperatively with Sensor Networks
  J. Djugash, S. Singh, G.A. Kantor, and W. Zhang
  IEEE International Conference on Robotics and Automation, May, 2006, pp. 2078 - 2084. [Abstract]
  Download: pdf [272 KB] copyrighted
  Summary: Here we extend our previous work to consider the case where the landmarks (nodes of a sensor network) are able to measure range to each other. We show how this information is useful 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 also find that addition of a mobile node makes the SLAM feasible in a sparsely connected network of nodes.

• Range-only SLAM with Interpolated Range Data
  A. Kehagias, J. Djugash, and S. Singh
  tech. report CMU-RI-TR-06-26, Robotics Institute, Carnegie Mellon University, May, 2006. [Abstract]
  Download: pdf [496 KB] copyrighted
  Summary: In this report we explore the use of interpolation to generate data equally spaced in time, in order to improve the performance of SLAM algorithms. We test this idea on several (simulated and real) robot paths and two SLAM algorithms: an online Extended Kalman Filter (EKF) algorithm and an offline batch optimization algorithm.

• Further Results with Localization and Mapping using Range from Radio
  J. Djugash, S. Singh, and P.I. Corke
  International Conference on Field & Service Robotics (FSR '05), July, 2005. [Abstract]
  Download: pdf [500 KB] copyrighted
  Summary: We present recent results with using range from radio for mobile robot localization and mapping. We have extended previous work to consider robustness. In particular, we investigate the case where range readings are very noisy and available intermittently. We present results from a mobile robot that is equipped with GPS for ground truth, operating over several km.