Motion planning in an unknown polygonal environment with sounded performance guarantee

Abstract

We consider the navigation problem of a robot from a starting point S to a target point T inside an unknown polygonal environment. The robot knows the directions of the points S and T and it can detect the walls of the environment through its tactile sensors. We present a competitive strategy for the robot to reach the target T. The path length generated by the robot is /spl les/4.5d(/spl kappa/-1)(/spl kappa/+2)/spl times/d, where, /spl kappa/=3/sup (d/2-1)/ and d is the L/sub 1/ distance between S and T.