Paper Info
Title
Linear Search with Terrain-Dependent Speeds.
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.
Year
DOI
Venue
2017
10.1007/978-3-319-57586-5_36
ALGORITHMS AND COMPLEXITY (CIAC 2017)
Keywords
DocType
Volume
Search algorithm,Zig-zag algorithm,Competitive ratio,Linear terrain,Robot,Speed of movement
Conference
10236
ISSN
Citations 
PageRank 
0302-9743
2
0.39
References 
Authors
8
6
Name
Order
Citations
PageRank
Jurek Czyzowicz177874.35
Evangelos Kranakis23107354.48
Danny Krizanc31778191.04
Lata Narayanan461362.78
Jaroslav Opatrny548144.39
Sunil M. Shende621824.35