Linear Search with Terrain-Dependent Speeds
From MaRDI portal
Publication:5283387
DOI10.1007/978-3-319-57586-5_36zbMATH Open1486.68188arXiv1701.03047OpenAlexW2575734070MaRDI QIDQ5283387FDOQ5283387
D. Krizanc, Jurek Czyzowicz, Sunil Shende, Jaroslav Opatrny, Evangelos Kranakis, Lata Narayanan
Publication date: 21 July 2017
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.03047
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
- Searching in the plane
- The theory of search games and rendezvous.
- An annotated bibliography on guaranteed graph searching
- Distributed computation in dynamic networks
- Title not available (Why is that?)
- Online searching with turn cost
- On the linear search problem
- Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem
- The return of the linear search problem
- Group Search on the Line
- Search on a Line with Faulty Robots
- A General Framework for Searching on a Line
- Revisiting the Problem of Searching on a Line
- Linear Search by a Pair of Distinct-Speed Robots
- Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract)
- Linear Search with Terrain-Dependent Speeds
Cited In (10)
- Weighted group search on a line \& implications to the priority evacuation problem
- Linear rendezvous with asymmetric clocks
- Searching with increasing speeds
- Evacuating from \(\ell_p\) unit disks in the wireless model (extended abstract)
- Energy Consumption of Group Search on a Line
- Linear Search with Terrain-Dependent Speeds
- Algorithms for \(p\)-Faulty Search on a half-line
- Evacuating from \(\ell_p\) unit disks in the wireless model
- Time-energy tradeoffs for evacuation by two robots in the wireless model
- Wireless evacuation on \(m\) rays with \(k\) searchers
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)
