Two-dimensional robot navigation among unknown stationary polygonal obstacles

The authors describe an algorithm for navigating a polygonal robot, capable of translational motion, in an unknown environment. The environment contains stationary polygonal obstacles and is bounded by polygonal walls, all of which are initially unknown to the robot. The environment is learned during the navigation process by use of a laser range-finding device, and new knowledge is integrated with previously acquired information. A partial map of the environment, containing parts of the obstacles that were seen by the robot and the free space between them, is obtained. The obstacles in the map are transformed into a new set of expanded polygonal obstacles, allowing the robot to be treated as a point, and the navigation problem is reduced to point navigation among unknown polygonal obstacles. A navigation graph is built from the transformed obstacles and used to search for a piecewise linear path to the destination. The algorithm is proved to converge to the desired destination in a finite number of steps provided a path to the destination exists