Triangulation-based path planning for a mobile robot

Abstract

A triangulation-based path planning algorithm for a mobile robot is presented. A circular robot operating in a planar polygonal environment cluttered with polygonal obstacles is considered. The free space of the 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 triangulated, resulting in an exact cell decomposition. This enables a triangulation graph to be constructed, representing the topological connectivity of the free space, from which safe paths from the start to the goal can be found. The paths are contained within free channels bounded by the obstacles and the environmental boundaries. An important feature of the process is that many segments of a selected path are parallel to the environmental boundaries. This would enable relatively simple sensing devices, such as ultrasonic sensors, to be used for correcting navigation errors. The algorithm is computationally efficient, being of O( n 2 ) complexity.