Robot path planning using intersecting convex shapes

This paper deals with an automated path planning algorithm for a mobile robot in a structured enviornment. The algorithm is based upon finding all the largest (prime) free convex areas in the environment and representing this information in the form of a graph. A graph traversal algorithm which exploits back-tracking as well as dynamic cost allocation to graph arcs is presented and simulated. A strategy to trade of the optimality of the results for a smaller computation time is described.