Version 1.0, August 31, 2001, Copyright, Hugh Jack 1993-2001
E.Palma-Villalon and P.Dauchez [1988] came up with a method to do fast path planning for a mobile robot. Rectangles are used to represent obstacles, and the moving robot is represented with a circle. The obstacles are grown by the radius of the circle (into configuration space). A map is created with a course resolution is made to indicate which objects are present in a grid box.
Figure C.4 Grid Representation of Space
This map only indicates an objects presence, the remainder of the information is kept in a concurrent list. By finding and using a series of holes and walls within the grid an A* search is applied to find the best path. The cost function of the search is based on the path length and the number of turns made. The performance of this method is not stated, and thus no basis for comparison is available. This method provides straight line path segments. The mapping to configuration space could be convenient for the first pass of a path planner for general path finding.