TY - GEN

T1 - Randomized robot navigation algorithms

AU - Berman, Piotr

AU - Blum, Avrim

AU - Fiat, Amos

AU - Karloff, Howard

AU - Rosén, Adi

AU - Saks, Michael

N1 - Funding Information:
iI Department of Mathematics, Rutgers University, New Brunswick, NJ 08903. Supported in part by NSF contract CCR-9215293 and by DIMACS, which is funded through NSF grant STC-91-19999 and the NJ Commission on Science and Technology. saks@dimacs .rutgers . edu
Funding Information:
of Technology, At- in part by NSF grant
Funding Information:
tSchoo1 of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213-3891. Supported in part by NSF National Young Investigator grant CCR-9357793 and a Sloan Foundation Research Fellowship. avrim@cs . emu .edu *Dept. of Computer Science, Tel-Aviv 69978, Israel. fiatQmath.tau.ac .il f+College of Computing, Georgia Institute lanta, GA 30332-0280. Research supported CCR-9319106. howard@cc.gatech.edu TDept. of Computer Science, Tel-Aviv 69978, Israel. adiro@math. tau. ac. il

PY - 1996/1/28

Y1 - 1996/1/28

N2 - We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot has no prior knowledge about the positions or sizes of the obstacles, and acquires such knowledge only when obstacles are encountered. Our goal is to minimize the distance the robot must travel, using the competitive ratio as our measure. We give a new randomized algorithm for this problem whose competitive ratio is O(n 4/9 log n), beating the deterministic Ω(√n) lower bound of [PY], and answering in the affirmative an open question of [BRS] (which presented an optimal deterministic algorithm). We believe the techniques introduced here may prove useful in other on-line situations in which information gathering is part of the on-line process.

AB - We consider the problem faced by a mobile robot that has to reach a given target by traveling through an unmapped region in the plane containing oriented rectangular obstacles. We assume the robot has no prior knowledge about the positions or sizes of the obstacles, and acquires such knowledge only when obstacles are encountered. Our goal is to minimize the distance the robot must travel, using the competitive ratio as our measure. We give a new randomized algorithm for this problem whose competitive ratio is O(n 4/9 log n), beating the deterministic Ω(√n) lower bound of [PY], and answering in the affirmative an open question of [BRS] (which presented an optimal deterministic algorithm). We believe the techniques introduced here may prove useful in other on-line situations in which information gathering is part of the on-line process.

UR - http://www.scopus.com/inward/record.url?scp=84966888626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84966888626&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84966888626

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 75

EP - 84

BT - Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

PB - Association for Computing Machinery

T2 - 7th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1996

Y2 - 28 January 1996 through 30 January 1996

ER -