| Amos Fiat z (2007) | |||||||||||||||
Abstract | |||||||||||||||
| 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 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||