Cognition of free space for planning the shortest path: A framed free space approach

In this paper, an algorithm incorporating two novel ideas is proposed to improve the time performance of the quad tree-based method for planning the shortest path from a given source to any given destination. One of the novel ideas is to combine the free quads. The strength of this idea lies in the fact that the quads after the total division isolate the free space from the obstacle space. The free quads, which are normally small in size, along the boundary of the obstacles, are combined to form larger free areas. The boundary of every free area is thought of being fenced by a sequence of unit free area cells called frame cells. The size of such a cell is a pixel. The free area together with the frame cells is called framed free space. Thus the entire free space, isolated from the obstacle space, is cognized through the frame cells. The other idea is the adoption of the philosophy of the rectilinear propagation of light rays to trace the shortest path and employ dynamic programming as design strategy to compute the optimal/shortest path through the cognized free area. In the framed free space, all the frame cells hold the information about the shortest distance from it to the source point, computed using the notion of rectilinear propagation of light. The shortest distance from a destination point to a source point is computed using this information. Since the quads are combined to form larger free areas, the number of framed free spaces considered for finding the shortest path is reduced. This in turn reduces the total number of frame cells cognizing the free space so that the total number of frame cells that take part in the computation of the shortest path are drastically reduced. The proposed algorithm works in a 2D static environment with obstacles of any shape and practically unconstrained size of an autonomous vehicle.