A new 2-D world representation system for mobile robots

A method is proposed that divides the collision free space into convex polygons that can be considered as path segments. A path segment is generated for each pair of free edges on the same polygon. The path segments sharing a common free edge are then linked. This leads to a connective graph indicating the collision free paths between the free edges. When new data about the world are obtained, it is only necessary to update the convex polygons and their path segments on which new information is available and to modify the links connecting these path segments to others