Online Searching with an Autonomous Robot

We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video.

• Publication year

  2004

• Venue

  Workshop on the Algorithmic Foundations of Robotics

• Publication date

  2004-04-16

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1007/10991541_11arXiv cs/0404036
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Searching with an autonomous robot

  2004cited by this paper
• Online searching with turn cost

  2004cited by this paper
• Optimal strategies to track and capture a predictable target

  2003cited by this paper
• An autonomous mobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments

  2003influential reference
• Local exploration: online algorithms and a probabilistic framework

  2003influential reference
• Automatic Classification of Objects in 3D Laser Range Scans

  2003cited by this paper
• The Polygon Exploration Problem

  2002cited by this paper
• Robust Real-Time Face Detection

  2001cited by this paper
• Robust Real-time Object Detection

  2001cited by this paper
• A 3D laser range finder for autonomous mobile robots

  2001cited by this paper
• Exploring Unknown Environments with Obstacles

  1999cited by this paper
• Provable strategies for vision-guided exploration in three dimensions

  1994cited by this paper
• An Optimal Competitive Strategy for Looking Around a Corner

  1994cited by this paper
• Finding the Shortest Watchman Route in a Simple Polygon

  1993cited by this paper
• Constructing Competitive Tours from Local Information

  1993cited by this paper
• How to Look Around a Corner

  1993cited by this paper
• A Method for Registration of 3-D Shapes

  1992cited by this paper
• Corrigendum to "An Incremental Algorithm for Constructing Shortest Watchman Routes"

  1991cited by this paper
• Closed-form solution of absolute orientation using unit quaternions

  1987cited by this paper
• Art gallery theorems and algorithms

  1987cited by this paper

• Task-Driven Graph Attention for Hierarchical Relational Object Navigation

  2023cites this paper
• Motion Planning: Recent Developments

  2018cites this paper
• Competitive Searching for a Line on a Line Arrangement

  2018cites this paper
• Environment Exploration in Sensing Automation for Habitat Monitoring

  2017cites this paper
• Wireless Evacuation on m Rays with k Searchers

  2017cites this paper
• Research on calibration technology of vehicle laser scanning system

  2017cites this paper
• Mapping and coverage with a particle swarm controlled by uniform inputs

  2017cites this paper
• Quickest Linear Search over Correlated Sequences

  2016cites this paper
• Quickest search over correlated sequences with model uncertainty

  2016cites this paper
• Intelligent Mobile System for Improving Spatial Design Support and Security Inside Buildings

  2016cites this paper
• Study on Spatial Data Acquisition and Processing Based on Vehicle-Mounted Mobile Measurement System

  2015cites this paper
• Experimental data driven robot for pattern classification

  2015cites this paper
• Quickest linear search over correlated sequences

  2015cites this paper
• A competitive online algorithm for exploring a solar map

  2014cites this paper
• Intensity-based navigation with global guarantees

  2013cites this paper
• Multi-Robot Exploration and Mapping with a Rotating 3D Scanner

  2012cites this paper
• Mapping and Pursuit-Evasion Strategies For a Simple Wall-Following Robot

  2011cites this paper
• Navigation in an unfamiliar environment using signal intensity

  2011cites this paper
• Exploration Strategies for a Robot with a Continously Rotating 3D Scanner

  2010cites this paper
• Generalized Watchman Route Problem with Discrete View Cost

  2010cites this paper
• Searching and mapping among indistinguishable convex obstacles

  2010cites this paper
• An optimal solution to the linear search problem for a robot with dynamics

  2010cites this paper
• Planning Under Sensing Uncertainty

  2010cites this paper
• Alternative Measures for the Analysis of Online Algorithms

  2010cites this paper
• Optimal strategies for maintaining a chain of relays between an explorer and a base camp

  2009cites this paper
• Guarding Rectangular Partitions

  2009cites this paper
• Structured tracking for safety, security, and privacy: algorithms for fusing noisy estimates from sensor, robot, and camera networks

  2009cites this paper
• Polygon exploration with time-discrete vision

  2008cites this paper
• Polygon Exploration with Discrete Vision

  2008cites this paper
• SYLVESTER-GALLAI RESULTS AND OTHER CONTRIBUTIONS TO COMBINATORIAL AND COMPUTATIONAL GEOMETRY

  2008cites this paper
• Adaptive Searching in One and Two Dimensions

  2008cites this paper
• View Planning Problem with Combined View and Traveling Cost

  2007cites this paper
• Metric View Planning Problem with Traveling Cost and Visibility Range

  2007cites this paper
• Models and algorithms for online exploration and search

  2006cites this paper
• Planning algorithms

  2006cites this paper
• Sensitivity Analysis for Intruder Tracking Using Particle Filtering and a Network of Binary Sensors

  2006cites this paper
• Minimum-cost coverage of point sets by disks

  2006cites this paper
• An application of virtual reality for training and ranking operators of mobile robot

  2006cites this paper
• Detecting changes in environment of mobile robot

  2006cites this paper
• Automated Intruder Tracking using Particle Filtering and a Network of Binary Motion Sensors

  2006cites this paper
• Analiza porównawcza metod sygnaturowania obrazów

  2005cites this paper
• Embedding Point Sets into Plane Graphs of Small Dilation

  2005cites this paper
• Searching with an autonomous robot

  2004cites this paper
• Online searching with turn cost

  2004cites this paper