Two-Dimensional Robot Navigation Among Unknown Stationary Polygonal Obstacles

An algorithm for navigating a polygonal-robot, capable of translational motion in an unknown environment is described. 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 sonar device, and new knowledge is integrated with previously acquired information. A partial map of the environment is thus obtained. The map contains parts of the obstacles that were "seen" by the robot, and the free-space between them. The obstacles in the map are transformed into a new set of enlarged polygonal obstacles. This enables treating the robot as a point instead of a polygon. The navigation problem is thus reduced to point navigation among unknown polygonal obstacles. A navigation graph is built from the transformed obstacles in the map. This graph is a partial visibility graph of the enlarged obstacles. A search is conducted on the graph for a path to the destination. The path is piecewise linear, and at its corners the robot stops, scans its environment, and updates the map, the enlarged obstacles, and the planned path. The algorithm is proved to converge to the desired destination in a finite number of steps provided a path to the destination exists. If such a path does not exist, then the navigation process terminates in a finite number of steps with the conclusion that the destination is unreachable. Application of the navigation scheme to two special cases of deteriorated polygons is also discussed: these are the case of a point robot and the case of a disk. In both cases the algorithm is shown to converge or terminate in a finite number of steps.