Voronoi Diagram Robot Path Planning How to Draw
Robot Path Planning Using Generalized Voronoi Diagrams
Introduction
In this page, I give a brief overview of my piece of work on the evolution of an efficient and robust algorithm for calculating safety paths for a mobile robot. I have specifically designed the algorithm for apply in the Autonomous Vehicle for Exploration and Navigation in Urban Environments (AVENUE) project. The environment currently beingness investigated is the Morningside Heights campus of Columbia University, but will eventually exist expanded to other urban areas. In the general problem, one is given a two-dimensional map of the complicated region in which a robot will be operating. Such a map includes a multifariousness of polygonal obstacles that are to be avoided. To determine paths along which the robot can safely move through this environment, I use an arroyo based on the generalized Voronoi diagram for a planar region with specified obstacles. Once this diagram has been constructed, I tin can search information technology to find robot paths that pass, with maximal clearance, around the obstacles.
The ii-dimensional map of the robot's test expanse,
the northern one-half of Columbia's Morningside Campus.
The Method
The 2-dimensional region in which the robot moves will contain buildings and other types of barriers, each of which can be represented by a convex or concave polygonal obstacle. To find the generalized Voronoi diagram for this collection of polygons, one can either compute the diagram exactly or use an approximation based on the simpler problem of computing the Voronoi diagram for a set up of detached points. In my piece of work, I use the latter method. Offset, I approximate the boundaries of the polygonal obstacles with the large number of points that result from subdividing each side of the original polygon into small segments. 2d, I compute the Voronoi diagram for this collection of approximating points. One time this complicated Voronoi diagram is synthetic, I then eliminate those Voronoi edges which take ane or both endpoints lying inside any of the obstacles. The remaining Voronoi edges class a good approximation of the generalized Voronoi diagram for the original obstacles in the map. In this Voronoi diagram, I locate the robot'southward starting and stopping points and and so compute the Voronoi vertices which are closest to these ii points. I and then apply direct lines to connect the robot's starting and stopping points to these closest vertices. Special consideration is given to those situations in which i or both of the connecting direct lines pass through an obstacle. In one case I have determined the starting and stopping vertices on the Voronoi diagram; I can implement a standard search, such every bit Dijkstra's Algorithm, to observe a "all-time" path which is a subset of the Voronoi diagram and which connects the starting and stopping vertices. This path tin and so be expanded to a path between the robot's original starting and stopping points. The method generates a route that for the near part remains equidistant betwixt the obstacles closest to the robot and gives the robot a relatively condom path along which to travel.
An Instance
The following is a Java applet that demonstrates the path planning algorithm in action and gives an example of the user interface. In crimson is the campus map, and in green is the generalized Voronoi diagram computed for this map (which the applet precomputed). To compute a path, outset click on a starting signal and then click on a stopping signal. Finally click "Compute Path". Despite its small appearance, this map is really equanimous of thousands of points. Therefore it can take upward to 30 seconds to compute a path, depending on the speed of your computer.
Click here for the applet.
Paul Blaer
pblaer@cs.columbia.edu
Source: https://www.cs.columbia.edu/~pblaer/projects/path_planner/
0 Response to "Voronoi Diagram Robot Path Planning How to Draw"
Post a Comment