Space representation and map building-A triangulation model to path planning with obstacle avoidance

Abstract

Presents a triangulation modelling algorithm for representing the working environment of a mobile robot such that planning a collision-free path on the corresponding constructed road map (a graph) is simplified. Both the nodes and the edges of the graph can be exactly calculated by expressions F/sub n/(V,B) and F/sub B/(V,B), where V and B represent the total numbers of vertices and obstacles respectively, and both F/sub n/(V,B) and F/sub e/(V,B) are of complexity O(V). The solution path planned on the resulting graph keeps the robot at some clearance from the obstacles.