description
Previous articleHybrid A* Algorithm Explained in Detail (1) Path Search
The path loss function uses a Voroni potential energy diagram
According to the analysis of the previous article, there are two factors that determine the length of the A* path: the length of the path and the distance from the obstacle. The Voroni diagram is used to weigh the two. I briefly introduced the Wielet diagram when I recorded the alpha shape algorithm for 2D point clouds, which is linked here.
C++ implementation of the alpha shape algorithm with 2D point clouds
A Wienod diagram can use each obstacle as the center of a polygon. Obstacles are divided by equally divided line segments, so that the whole environment forms a Wienod diagram. It has the following properties:
1. There is only one node in each polygon;
2. Nodes in adjacent polygons reach their common edges at equal distances;
3. Points within a polygon are closer to their center than to the centers of other polygons
Based on the Wiener diagram, the Voroni Field is proposed. Its formula is as follows:
(,)pv(x,y) represents the potential energy of the node at a certain position, α represents the descent rate, dO represents the distance from the node to the nearest obstacle, and dV represents the distance from the node to the edge of the Wino diagram polygon. dOmax represents the maximum effective range of potential energy values. Based on this potential energy, a Generalized Voronoi Diagram (GVD) is generated.
This potential energy has the following characteristics:
1. The potential energy beyond the range of potential energy value is 0;
2. The potential energy value (,) is ⊆ [0,1]pV(x,y)⊆[0,1], and is continuous in the range of (,)(x,y);
3. The maximum value will be reached only inside the obstacle;
4. Reach the minimum on the edge of the GVD.
The key advantage of the Voronoi field over the traditional potential field is that the potential energy value is scaled proportionally to the total available navigation gap. As a result, even narrow openings are still navigable, which is not always the case in standard potential fields. In a traditional potential field, the field values around the obstacle are usually set to infinity, which means that the vehicle cannot traverse these areas. In contrast, the Voronoi field adjusts the potential energy value based on the available navigation gaps, which means that vehicles can find traversable paths even in confined spaces.
The paper gives several diagrams, as follows:
Figure a shows a Voroni potential energy diagram for a simulated parking lot, and Figure b is its corresponding GVD diagram. Notice that the narrow gaps between the obstacles are not blocked by potential energy, and there will always be a path between them with a potential energy of 0 = 0pV = 0. Figure c shows a counter-example, when the potential energy formula is (,)=(+(,))−1p(x,y)=α(α+dO(x,y))−1, there is still a relatively high potential energy between the obstacles.
The image below shows a driving track from a Vino map of a real parking lot.
Click on the Mixed A* algorithm for detailed explanation (2) Path smoothing - Gu Yueju can view the full text