Abstract: We revisit the linear search problem where a robot, initially placed at the origin on an infinite line, tries to locate a stationary target placed at an unknown position on the line. Unlike previous studies, in which the robot travels along the line at a constant speed, we consider settings where the robot's speed can depend on the direction of travel along the line, or on the profile of the terrain, e.g. when the line is inclined, and the robot can accelerate. Our objective is to design search algorithms that achieve good competitive ratios for the time spent by the robot to complete its search versus the time spent by an omniscient robot that knows the location of the target. We consider several new robot mobility models in which the speed of the robot depends on the terrain.These include 1) different constant speeds for different directions, 2) speed with constant acceleration and/or variability depending on whether a certain segment has already been searched, 3) speed dependent on the incline of the terrain. We provide both upper and lower bounds on the competitive ratios of search algorithms for these models, and in many cases, we derive optimal algorithms for the search time.
Recommendations
- Speeding up the search algorithm for the best differential and best linear trails
- Linear search by a pair of distinct-speed robots
- Linear search by a pair of distinct-speed robots
- An algorithmic approach to some problems in terrain navigation
- Optimal Exploration of Terrains with Obstacles
- scientific article; zbMATH DE number 3514759
- scientific article; zbMATH DE number 7271257
- Approximation algorithms for shortest descending paths in terrains
- A fast shortest path algorithm on terrain-like graphs
- Optimal search for moving objects in a discrete domain
Cites work
- A general framework for searching on a line
- An annotated bibliography on guaranteed graph searching
- Distributed computation in dynamic networks
- Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
- Group search on the line
- scientific article; zbMATH DE number 4209901 (Why is no real title available?)
- Linear search by a pair of distinct-speed robots
- Linear Search with Terrain-Dependent Speeds
- On the linear search problem
- Online searching with turn cost
- Revisiting the problem of searching on a line
- Search on a line with faulty robots
- Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
- Searching in the plane
- The return of the linear search problem
- The theory of search games and rendezvous.
Cited in
(10)- Weighted group search on a line \& implications to the priority evacuation problem
- Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract)
- Evacuating from \(\ell_p\) unit disks in the wireless model
- Linear rendezvous with asymmetric clocks
- Energy consumption of group search on a line
- Linear Search with Terrain-Dependent Speeds
- Wireless evacuation on \(m\) rays with \(k\) searchers
- Searching with increasing speeds
- Algorithms for \(p\)-Faulty Search on a half-line
- Linear search with probabilistic detection and variable speeds
This page was built for publication: Linear Search with Terrain-Dependent Speeds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283387)
