A COMPETITIVE ANALYSIS OF ALGORITHMS FOR SEARCHING UNKNOWN SCENES

We consider problems involving robot motion planning in an initially unknown scene of obstacles. The two specific problems that we examine are mapping the scene and searching the scene for a recognizable target whose location is unknown. We use competitive analysis as a tool for comparing algorithms. In the case of convex polygonal obstacles, we show a tight THETA(min(k, square-root kalphaBAR)) bound on the competitive factor for these problems, where alphaBAR and k are the average aspect ratio and the number of objects, respectively. We also consider the competitive factor for the Nearest Neighbor heuristic.