INTRODUCTION
The path-planning problem was originally studied extensively in robotics, and, through this research, it has gained more relevance in areas such as computer graphics, simulations, geographic information systems (GIS), very-large-scale integration (VLSI) design, and games. Path planning still remains one of the core problems in modern robotic applications, such as the design of autonomous vehicles and perceptive systems . The basic path- planning problem is concerned with finding a good-quality path from a source point to a destination point that does not resulting collision with any obstacles.
Depending on the amount of the information available about the environment, which can be completely or partially known or unknown, the approaches to path planning vary considerably.
Also, the definition of a good-quality path usually depends on the type of a mobile device (a robot) and the environment (space), which has fostered the development of a rich variety of
path-planning algorithms, each catering to a particular set of needs.

[attachment=7221]


PPP usually has
 Well defined set of objectives
 Optimization of path based on certain criteria
 Specific functions to describe robotic movement
 To solve problems involving swarm intelligence.
Application of pathplanning
 Robotics
 Geographic information systems(GIS)
 Computer graphics & simulations
 Very-large-scale-integration

 

COMPUTATIONAL GEOMETRY

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Computational geometry plays a special role in path-planning developments. Extensive methodologies that rely on geometric representation of the space, reveal topological properties of the agents (robots and/ or obstacles), and allow the efficient dynamic position tracking and updates have been brought forward from computational geometry to solve a specific set of path-planning problems .Such problems usually have a well-defined and deterministic set of objectives, regular geometric space representation, and
specific functions that describe robotic movements. The problems also include planning a path and optimizing it (based on selected criteria such as the length, the smoothness, the cost, etc.) solving problems involving evolutionary algorithms and swarm intelligence ,and studying the behaviour of a network of mobile robot agents .

Important applications
 Robotics(motion planning and visibility problems),
 Geographic information systems (GIS) (geometrical location and search, route planning),
 Integrated circuit design (IC geometry design and verification),
 Computer-aided engineering (CAE) (programming of numerically controlled (NC) machines


Computational geometry and path planning
 Cell decomposition method
 Potential Field method
 Roadmap method

 



CELL DECOMPOSITION
The cell decomposition method uses non overlapping cells to represent the free-space (Cf ) connectivity. The decomposition can be exact or approximate. An exact decomposition divides
Cf exactly . An approximation scheme Kambhampati discretizes Cf with cells. It decomposes the free space recursively, stopping when a cell is entirely in Cf or entirely inside an obstacle. Otherwise,
the cell is further divided. Because of memory and time constraints, the recursive process stops when a certain degree of accuracy has been reached. The cell decomposition method,
although simple to implement, seldom yields high-quality paths. The exact cell decomposition technique is faster than the approximate one, but the path obtained is not optimal. The approximate cell decomposition can yield near-optimal path by increasing the grid resolution, but the computation time will increase drastically. There is also the known problem of digitization bias associated with using a grid. This stems from the fact that while searching for the shortest path in a grid, the grid distance is measured and not the Euclidean distance.




POTENTIAL FIELD METHOD
The idea behind the potential field method is to assign a function similar to the electrostatic potential to each obstacle and then derive the topological structure of the free space in the
form of minimum potential valleys. The robot is pulled toward the goal configuration as it generates a strong attractive force. In contrast, the obstacles generate a repulsive force to keep the robot from colliding with them. The path from the start to the goal can be found by following the direction of the steepest descent of the potential toward the goal . The strength of this approach is that path planning can be done in real time by considering only the obstacles close to the robot. Information on the locations of all obstacles is not required beforehand. However, as only local properties are used in planning, the robot may get stuck at local minima and never reach the goal. 
THE ROADMAP METHOD
The roadmap method attempts to capture the free-space connectivity with a graph. This approach has several variations. The probabilistic roadmap method (PRM) represents the free-space connectivity with a graph whose vertices are generated randomly in free space and connected to the
k-nearest neighbouring vertices such that the connecting edges do not cross any obstacle. To expedite the graph creation, several sampling-based methods such as Ariadne’s Clew algorithm , expansive space planner , random walk planner, rapidly exploring random tree have been proposed. Some of the other popular roadmap-based approaches are based on computational geometry structures such as the visibility graph for the shortest path and the Voronoi diagram for a maximum clearance path.
This method captures the free space connectivity with a graph.
 Probabilistic approach
 Visibility graph
 Voronoi diagram

 
 VORONOI DIAGRAM
Definition : consists of a set of points S in a plane, which are called the Voronoi sites. Each site s has a Voronoi cell, V(s) consisting of all points closer to s than to any other site.
























Voronoi diagram in pathplanning
 Provides a maximum clearance path
 Path obtained not optimal as path length and clearance contradict each other
Need of an algorithm that produces shortest path for different minimum clearance requirement (as an input parameter)
In this method the roadmap approach is used and the Voronoi diagram is utilized to obtain a path that is a close approximation of the shortest path satisfying the required clearance value set by the user. A Voronoi diagram (a fundamental computational geometry structure) is defined as the partitioning of a plane with n points (generators) into convex polygons such that each polygon contains exactly one generator and every point in a given polygon is closer to its generator than to any other. The Voronoi diagram and its dual structure, the Delaunay triangulation, have been used in a wide variety of applications such as collision detection, extraction of crust and skeleton, swarm intelligence optimization, cluster analysis, and mobile robot agent network.
The Voronoi diagram is also a well-known roadmap in the path-planning literature, which has edges that provide a maximum clearance path among a set of disjoint polygonal obstacles. However, a path obtained directly from the Voronoi diagram may be far from optimal. It usually has many unnecessary turns, and the length of the path may be undesirably long at regions where the obstacles are far apart. In fact, it is worth noting that minimizing the path length and maximizing the clearance seemingly contradict each other, as increasing the clearance results in a longer path whereas reducing the path length necessarily reduces the clearance from obstacles. It would be highly beneficial for many applications if an algorithm could be developed that would accept the minimum clearance required as an input parameter and produce a path that would be shortest while satisfying the minimum clearance requirement. The shortest path problem on its own can be viewed as only a special case when the clearance required set to zero. The practical usefulness of this kind of an algorithm is apparent for many applications, including marine GIS, ship route planning, VLSI design, oil drill path planning, etc.

Figure 1 illustrates the output of the proposed algorithm on a spatial dataset. Figure 1(a) is the path obtained directly from the Voronoi diagram. Figure 1(b) shows the shortest path obtained with Cmin ¼ 0. Figure 1© shows the final optimal path with a user specified clearance value of two units (20 m).  
The advantage of the proposed technique versus alternative path-planning methods is in its simplicity, versatility, and efficiency. For example, for planning the path for translational robots of varied dimensions, it has the capability to set the minimum clearance to a proportional value and the algorithm will find an optimal path for that minimum clearance, if one exists. The reported path is of more practical value because it is optimal with respect to both length and clearance. A high-quality approximation of the shortest path can also be obtained by the developed algorithm in much less time than by the popular and very well-performing visibility graph approach when we set Cmin equal to 0. To prove this claim, we experimentally compared the lengths of the paths obtained by these techniques and presented results in the experimental section. The planning algorithms vary in the nature of the desired path and the information on the environment. Recently, path planning in dynamic and complex environments has received considerable attention from researchers. In a dynamic environment, obstacles are allowed to move, and so, the environment can change dramatically over a period of time. An adaptive path-planning technique that takes cue from the previous situation can be found . In this , the authors use an adaptive mesh for dynamic path planning based on a combination of graph- and grid-based representation of the environment. The PRM is very promising for dynamic path planning, as a big advantage of the PRM is that its complexity depends mostly on the difficulty of the path and to a much lesser extent on the global complexity of the environment or the dimension of the configuration space . A recent algorithm based on the PRM for a dynamic environment can be found . However, in general, PRM-based approaches, being probabilistic in nature, do not meet any optimality criteria. There has been research on planning algorithms coordinating motion of multiple robots . The idea is to perceive multiple robots as a single composite robot and then to determine a roadmap for this composite robot. A highly interesting research on the utilization of computational geometry methods for coordination problems in dynamic systems was conducted by Cortes and Bullo . They capitalize on the properties of geometric constructs (disk covering and sphere packing), non smooth analysis, and dynamic system approaches, studied in the context of networked robot interactions. In this the roadmap-based path planning is focused and a powerful computational geometry data structure, the Voronoi diagram, is utilised to obtain a clearance-based shortest path. The advantage of using a Voronoi diagram as a roadmap over alternative methods, among which the visibility graph prevails, is its efficiency. The Voronoi diagram can be constructed in just O(nlogn) time, whereas even the fastest known algorithm for constructing visibility graph [15] can take O(n2 ) time in the worst case when the visibility graph has O(n2 ) edges. Since a Voronoi diagram has O(n) edges, querying for a path in a Voronoi diagram based roadmap is also much faster than querying in a visibility graph. However, as mentioned before, the quality of path obtained directly from the Voronoi diagram may be far from optimal. Thus, improving the quality of the path (refining the path) is an important direction of research.
A general method for refining a path obtained from a road- map based on classical numerical optimization techniques can be found were costs to each edge is applied and
an augmented Dijkstra’s algorithm is used to determine an optimal path. The edges that are nearer to obstacles are assigned higher costs. However, there is no guarantee that the method will
generate an optimal path, as the path is constrained to the edges in the roadmap. To improve the smoothness of the path obtained from a roadmap, a B-Spline approximation has been
used were the authors combine the Voronoi diagram, visibility graph, and potential field approaches to path planning into a single algorithm to obtain a trade off between the optimal by
safe and the shortest paths. The algorithm is fairly complicated, and although the path length is shorter than those obtained from the potential field method or the Voronoi diagram, it is still not optimal. The path exhibits bumps and rudimentary turns and is not smooth.
Another recent work on reducing the length of the path obtained from a Voronoi diagram involves constructing polygons at the vertices in the roadmap where more than two Voronoi edges meet. The path is smoother and shorter than that obtained directly from the Voronoi diagram, but there has been no attempt to reach optimality.
VVdiagram (the Visibility-Voronoi diagram for clearance c) evolves from the visibility graph to the Voronoi diagram as the value of c increases. Unfortunately, as the method is visibility based, the processing time is O(n2 logn), which renders it impractical for large spatial datasets.
A method is proposed were the paths are the shortest possible while maintaining just the amount of clearance required .Also the obtained path is satisfactory in the homotopy sense, i.e., it can be continuously transformed to the true-optimal path without crossing any obstacles. Thus, the obtained approximation can be always refined to a near-optimal path. Experimental results support this conjecture. Another interesting property of the path is that it can be extraordinarily smooth when going around smooth obstacles. The smoothness only seems to help reduce the path length in such cases


OUTLINE OF METHOD
The cornerstone of the methodology is the utilization of a powerful computational geometry data structure: the Voronoi diagram. We start by building the Voronoi diagram of the obstacles. The source and destination are dynamically inserted into the diagram, and they are connected to all Voronoi vertices of their Voronoi cells, respectively. Inserting the source and destination dynamically has two major advantages over simply connecting them to the nearest Voronoi vertex. There is no
Possibility of the connecting edges crossing an obstacle, as they are contained inside the Voronoi cell. Also, if we want to perform multiple queries, we can do so by simply dynamically deleting the old source and destination from the Voronoi diagram instead of rebuilding the diagram. We next remove all those edges in the resulting diagram that have a clearance less than the minimum clearance required (Cmin). The resulting graph represents the roadmap used by our algorithm. Any path obtained directly from this roadmap between the source and the destination is guaranteed to have a clearance greater than or equal to Cmin .We apply Dijkstra’s algorithm to determine the shortest path in the roadmap, but as mentioned before, the path is far from optimal. Our algorithm then refines the obtained path by removing unnecessary turns, so that the path has a minimum number of links but at the same time satisfies the minimum clearance criterion. This path, however, is still not optimal and has sharp corners. We next add Steiner points along the edges of this path and use a novel corner-cutting paradigm to convert it to an optimal path. The flowchart in Figure 2 illustrates the steps involved. We next discuss each stage in detail.


 













ALGORITHM














METHODOLOGY IN DETAIL

As established earlier, a powerful computational geometry data structure has been proposed to solve the problem of an optimal path generation between a source and a destination in the presence of simple disjoint polygonal obstacles. This method has a number of unique features, such as a novel application of the Voronoi diagram in the specified clearance context, the iterative refinement technique based on Steiner points for path optimization, and the possibility of performing dynamic updates on the structure during the path computation process. The main steps of the developed path generation algorithm are detailed next.




Voronoi Diagram Construction
The construction of the Voronoi diagram of a set of polygons in the plane is both complex and time consuming. Instead, we approximate the obstacles with points on the boundary edges and generate the Voronoi diagram of the approximating points. The approximation of generalized Voronoi diagrams was first proposed by Sugihara . Removal of the Voronoi edges that cross obstacles from this diagram provides a nice approximation of the Voronoi diagram of the original obstacles. We first create the Delaunay triangulation and then generate the Voronoi diagram from it in O(n)time. We use the winged-edge data structure to represent the triangulation, as we found it more intuitive to use and update than the half-edge or quad-edge data structures. This structure is also more flexible, as the direction of the edges can be fixed arbitrarily. It maintains three collections—one for vertices, one for edges, and one for triangles. Each vertex stores the coordinates and the index of any one edge incident on it. A triangle stores the index of any one of the three bounding edges. Most of the topological information is stored inside an edge. It contains the indices of the end vertices, indices of triangles on left and right, and the clockwise and counter- clockwise predecessors and successors of the edge. The randomized incremental algorithm for construction of the Delaunay triangulation proved helpful for the path planning problem, as it allows dynamic insertion of new points in O(1) time without having to rebuild the entire triangulation. The incremental construction starts by creating a triangle that contains all the datapoints inside it. However, just containing the points is not a sufficient condition. The three corner points of this triangle should not lie inside the circumcircle of any of the tri- angles of the triangulation of the dataset. This is to ensure that the enclosing triangle does not influence the triangulation. Once the enclosing triangle is constructed, the datapoints are added to the triangulation one by one, and after each insertion, the required topological changes are performed to restore the Delaunay properties. A new datapoint pi can lie inside a triangle or on a triangle edge of the current triangulation. On the basis of this, two kinds of topological updates are required.













In Figure 4(a), the data point lies inside a triangle. The topological update involves the addition of three new edges. In Figure 4(b), the data point lies on an edge. In this case, the old edge is deleted, and four new edges are created. The new triangles created as a result of the topology update may not satisfy the empty circle property. If an edge is found to be illegal, it is flipped so that the Delaunay properties are restored.





Generation of Roadmap
Before generating the roadmap, we add the source and the destination to the Voronoi diagram dynamically. We dynamically delete the old source and destination and insert the new ones. Details on point location and dynamic point deletion are provided in next section. The roadmap is generated by removing the edges from the Voronoi diagram that have an obstacle clearance < Cmin. There is one issue, however. If we consider the obstacles only for the Voronoi diagram construction, the resulting roadmap will not be complete.

This is evident in Figure (a). This can be resolved by determining the minimum bounding box (mbb) of all obstacle vertices in linear time and expanding the mbb in all four directions by at least twice the minimum clearance required. The Voronoi diagram is then constructed from the points approximating the obstacles and this expanded mbb. The roadmap obtained from such a diagram is shown in Figure (b). The quality of the diagram depends on the spacing between approximation points. As can be observed in , if the spacing is too large, the Voronoi edges
exhibit a zigzag pattern. However, it has been observed in that a finer initial approximation yields results practically indistinguishable from the original Voronoi diagram. The proof was the utilization of the results of the approximating generalized Voronoi diagrams by ordinary Voronoi diagrams in the framework of path planning. Thus, it is possible to find the fine approximation (in our case established experimentally) so that the path obtained for the set of approximation points always satisfies the clearance requirement for the original obstacle set.

Fig 1 Fig 2
In Figure1 (a), the roadmap is generated using an expanded mbb. It can be observed that because of the concavity of the obstacle, there is a large deviation in the shortest path obtained from the
roadmap. There are two main disadvantages to this. The first one is that the unnecessarily large deviation may make a shorter path appear longer, and this may result in the selection of a longer path from the roadmap as the shortest path. The second disadvantage is that the optimization step will take longer to execute. To eradicate this problem, we retract the approximation points on the mbb toward the nearest obstacle point so that the distance is a little greater than 2 *Cmin. The Voronoi diagram is then constructed from the obstacle approximation points and the points on this retracted boundary. This results in a much improved shortest path obtained from the roadmap as evident in Figure1 (b).

Figure 2(a) shows the Voronoi diagram obtained from the point approximation of an obstacle and the retracted boundary for a dataset. Figure 2(b) shows the roadmap extracted from the Voronoi diagram. In practice, to reduce the computation time for the clearance check, we first build a quad tree of the mbbs of the obstacle edges. When checking for clearance of a Voronoi edge e, we first determine in O(logn) time all the obstacle edge indices whose mbbs overlap with the mbb of expanded in all four directions by Cmin. This yields a constant
number of edges against which the actual clearance check is carried out. As the expanded mbbs of the Voronoi edges constituting the medial axis of the obstacle and some of the outer
edges do not overlap with the mbb of any obstacle edge, they are not removed and remain in the roadmap. These edges do not influence the determination of the shortest path in any way.

Dynamic Insertion and
Deletion of Source and Destination

To insert the source and destination into the triangulation, we perform a walk in the triangulation to locate the triangle containing the point. Algorithmic details about walking in a triangulation have been presented by Devillers . To allow requerying, we delete the old source and destination dynamically from the Voronoi diagram and dynamically insert the new ones.
For dynamic deletion of points from the Delaunay triangulation, we followed the algorithm outlined in with a little modification. Because of limitations of the floating-point arithmetic, the
number of neighbours of the point (P) to be deleted may never get reduced to three, resulting in an infinite loop. To avoid this problem, we consider the circumcircle to be shrunk by
a small amount while performing the Incircle test. We adopt a different approach. Even if some of the remaining neighbours of P fall inside the circumcircle of the potential triangle, we flip the edge.
This guarantees that the number of neighbouring vertices of P will always be reduced to three. We then perform a normal Incircle test on the flipped edges to ensure that the triangulation remains
Delaunay.

Figure 8 shows a program snapshot of the topological events in deleting the encircled point from a simple dataset.


Removal of Redundant Vertices and Obtaining a Path with Minimum Number of Links
The shortest path obtained in the previous step has many unnecessary turns and redundant vertices. This step removes all redundant vertices and generates a path that has a minimum
number of links or edge connections. A minimum number of links ensures that the iterative refinement in next step consumes less time. The method is simple.
For a vertex vi on the path (i=1 ... n - 2), we check whether the line segment ( ViVi+2 )*has a clearance greater than equal to Cmin .If so, we remove Vi+1 from shortest path and repeat the process from vertex Vi+2. If not, we retain viþ1 and consider it as the next vertex for processing. We provide the pseudo code in Algorithm1. To efficiently determine the clearance of an edge (e), we
build a quad tree of the mbbs of the obstacle edges. We determine the mbb of e and expand it by Cmin in all four directions. In O(logn) time, it is possible to determine the edges whose mbbs overlap with the expanded mbb of e, and the clearance check is carried out for only these constant number of edges. This ensures the complexity of this step for all edges is O(nlogn).

Iterative Refinement Using a
Corner-Cutting Technique
The main idea behind the iterative refinement of the path is the utilization of the Steiner points. We first add the Steiner points along the edges of the path at regular interval , d . For our experiments, we set d to roughly one fourth the average obstacle edge length. This is two times the resolution we used to approximate the obstacles with points. Let V be a vertex on the shortest path other than source and destination. Let e1 and e2 be the two edges incident on V. We define the first Steiner point along e1 as a Steiner point that lies on e1 at d distance away from V, the second
Steiner point is 24 away from V, and so on. We try to connect the first Steiner point on e1 with that on e2. If the connecting edge satisfies the minimum clearance, we move to the second
Steiner point along both edges and try to connect these. The process continues until an intersection is detected, or the clearance from obstacles falls below the required minimum clearance, or the end point of one of the incident edges on V is reached. We then replace V with the last Steiner points that we could successfully connect with an edge. If we failed to connect even the first Steiner points along the two incident edges, we retain V. The path cannot be shortened any further at point V at this resolution. When no more reduction in path length is possible for any of the vertices, we double the resolution (i.e., set the interval between Steiner points along the edges to d=2) and repeat the process. The iteration continues until the resolution reaches a maximum precalculated value (Figure 2). Figure 9 shows a sample path obtained after the different stages.
for a specified value of minimum clearance (Cmin). The refined path is also smooth.We also show that the proposed algorithm outperforms the popular (and efficient) visibility graph-based
approach with regard to both speed and quality of the path. We have put our algorithm to test on a real-world data from the large spatial datasets. The spatial datasets considered are mostly represented in the form of Environmental Systems Research Institute (ESRI) shapefiles. When dealing with a spatial data, it is often required to substantially increase the resolution of the data so that extraordinary cases such as polygons degenerating into points can be avoided. After perform-
ing the computations, we scale down the result to display scale.


 

Users can zoom in on any part to see magnified view of a selected portion. All experiments have been carried out on a 1.6-GHz Intel Centrino Duo processor with 0.99-GB RAM.
The programs have been implemented in Visual C++. The source and target are indicated with S and T in all figures. In Figure 10, we visually compare the path obtained directly fromthe Voronoi diagram-based roadmap to that obtained after iterative refinement (Cmin ¼ 0) on a portion of the real-world data. The shortest path in Figure 10(b) can be observed to wrap around the obstacles very similar to a path obtained from a visibility graph. The result shows that our algorithm is effective even in complicated environments.
We provide time estimates in Figure 11. The number of vertices for the six datasets for Figure 11(a) and 11(b) are mentioned in the first and second rows of Table 1, respectively. Figure 11(a) shows the time consumed by our algorithm and the visibility graph approach on a number of spatial datasets. The time (in seconds) includes the time to build the roadmap and determine the path between the source and the destination. The time estimated for our method includes the time for path optimization. It can be observed that the time difference becomes more pronounced as the number of vertices in the dataset increases. In Figure 11(b), we show the breakup of roadmap construction time and optimization time for some large datasets. The time consumed by the visibility graph approach for these datasets is extremely high, and therefore, we do not mention it here.
 
Conclusions
In this article, a computational geometry data structure has been proposed to solve the problem of an optimal path generation between a source and a destination in the presence of simple disjoint polygonal obstacles. The method has a number of unique features, such as a novel application of the Voronoi diagram in the specified clearance context, the iterative refinement technique based on the Steiner points for path optimization, and the possibility of performing dynamic updates on the structure during the path computation process. The obtained path is optimal with respect to length and clearance from the obstacles for a specified value of minimum clearance (Cmin). The refined path is also observed to be smooth. The proposed algorithm outperforms the popular (and efficient) alternative approach with regard to speed as well as the quality of the path and is flexible to allow various required clearance settings and source/ destination location changes. Future studies will involve porting the algorithm to other platforms and applications (including ArcGIS compatibility and direct shape file visualization options) and extending the algorithm to work with three-dimensional data.