Path Planning Of Mobile Robot Based On Triangulation Tracing

A path planning method of mobile robot based on triangulation tracing is proposed for the purpose of dealing with high complication and low security during traditional path planning method based on Voronoi diagram. A optimization path of robot is produced by value-points tracing strategy of triangulation, which combined with Dijkatra algorithm. This method needn't to restructure the triangulation along with the motion of obstacles, and optimizes the path by selecting feature values, which decided in the size of obstacles. Simulation result shows that the method reduced calculation complexity and enhanced the security of the path effectively.Quantify the obstacles into circles with different radius, according to circumcircle of each obstacles' cross-section, put the centers of circle into point set, and constructe trianglation by Delaunay triangle partition method. Determine a value-point according to eigenvalue of two vertex on each edge. Triangulation value-points tracing means find a path by some kind of algorithm, and go through value-points on all edges, including initial point.Choose initial edge correctly when value-points tracing line go into triangulation. One method is that making the edge on which the value-point nearest to initial point is as the initial edge. If there are two value-points have equal and nearest distance to initial point, priority choose the edge which is nearest to initial point as the initial edge. The other method is that choosing initial edge by traditional dynamic programming method. This method can resolve the problem that two value-points have equal distance to initial point and the distance between initial point and these two edges are also equal.After the tracing line goes into triangulation, choose the value-points on the other edges as the export. There are two kinds of methods to trace next value-point: One is that using traditional Dijkstra algorithm, for determining a robot walking stable path accurately. The other method is that choose a value-point on the other edges, which is more near to target point, as the next value-point to be traced.Experiment results show that the method of robot path planning based on triangulation tracing could reduce the computational complexity of algorithm, improve the security of path planning, and meet the requirement of real-time path planning, which can ensure the sum of the corner points are appropriate.