TRIANGULATION-BASED PATH PLANNING FOR A MOBILE ROBOT

A triangulation-based path planning algorithm for a mobile robot is pr esented. A circular robot operating in a planar polygonal environment cluttered with polygonal obstacles is considered. The free space of th e robot consists of a polygonal region with polygonal holes. A method called bridge building is presented for triangulating a simple polygon with polygonal holes. The free working space of the robot is thus tri angulated, resulting in an exact cell decomposition. This enables a tr iangulation graph to be constructed, representing the topological conn ectivity of the free space, from which safe paths from the start to th e goal can be found. The paths are contained within free channels boun ded by the obstacles and the environmental boundaries. An important fe ature of the process is that many segments of a selected path are para llel to the environmental boundaries. This would enable relatively sim ple sensing devices, such as ultrasonic sensors, to be used for correc ting navigation errors. The algorithm is computationally efficient, be ing of O(n(2)) complexity.