Simple, Efficient and Robust Strategies to Traverse a Street


[.ps] [.pdf]

Abstract

We present a family of strategies for the problem of searching in an unknown street for a target of unknown location. We show that a robot using a strategy from this family follows a path that is at most π + 1 times longer than the shortest possible path. Although this ratio is worse than the ratio of the best previously known strategy, which achieves a detour of at most 2sqrt(2) ~ 2.8284 times the length of a shortest path, the simplicity of the analysis is interesting in its own. We use this new strategy as part of a hybrid method to obtain an equally simple strategy of slightly more complex analysis with a competitive ratio of 1/2 sqrt(π2+4 π+8) ~ 2.75844. The π+1-competitive strategy is very similar in spirit to the first published strategy of which the best analysis is very involved and gives a bound of ~ 4.44. More importantly, we show that the π+1 strategy is robust under small navigational errors


Bibtex Entry