CVD算法如何应用于Voronoi图实现多机器人路径规划，Matlab代码如何编写？

本文共计964个文字，预计阅读时间需要4分钟。

1. 简介：在CVDs中，我们仅使用结点顶点而非所有顶点来保持GVD的紧凑版本。为确保当前的CVD是初始GVD的良好近似，我们可以维护局部证书（详见前文）。

1 简介

In CVDs we use only junction vertices instead of all vertices to maintain the compact version of the GVD.To keep a check that current CVD is a good approximation of initial GVD, we can maintain local certificates (explained in Previous Studies section) such as junction triangles being locally Delaunay. When robot moves we keep track of the junction vertices which are the centers of circles touching 3 polygonal obstacles. As these junctions change position, we observe with which polygons the triangle touchesnext.

This way only a small portion of the map is updated instead of modifying the whole map. Thus, maintaining CVD takes less space in memory than GVD and suits the multi-robot path planning problem. We use CVD to make sure there are no collisions. If adjacent corridors overlap, it means there is a collision between objects. We also utilize for Retraction Motion Planning by determining narrowest passage between two convex chains in the corridor.

​

编辑

Reference paper[1] proposes Compact Voronoi Diagrams over Generalised Voronoi Diagrams. To understand the results few key terminologies are important to understand:

1.Local Certificate They are certain local conditions which need to be met at all times to guarantee that CVD is a good approximation of GVD. At regular intervals, they are

2. Junction Points Point of intersection of three or more Voronoi edges. Junction points location is critical for maintenance of CVD.

3. Witness Circles A circle drawn from junction point which touches three polygons and does not include any other polygon.

4. Junction Triangles It is a triangle inscribed in Witness Circle. Junction triangles are critical for maintaining the local certificates for compact Voronoi diagrams.

5. Cocircularity Events Circumcircles of two or more junction triangles are coincident. So these two junction triangles share a common edge. Taking reference from the above definitions, following text explains implementation details in MATLAB: For finding the junction vertices (fig. 6), we use branchpoints morphological operation on the GVD of Minkowski dilated obstacle space. At every junction, we draw a witness circle (fig. 7) tangent to three obstacle polygons. This is followed by creating a Delaunay triangulation (fig. 8) of junction triangles associated with three features (points lying on polygons). Points within corridor (free space excluding junction triangles and obstacles) space that lie on the line bisecting closest pairs of features (edges or vertices) of two obstacles are stored to find routes that are maximally distant from obstacles.

​

编辑

​

编辑

​

编辑

In general Voronoi diagram, the local certificateinvolves drawing witness circles and making sure thatno other polygon than 3 adjacent polygons coincidewith the circle. In compact version, instead of witnesscircles, junction triangles need to meet this property atall instance.In case of local certification property not beingmet, i.e. a co-circularity event arises, we delete theedge that is common to both triangles and join thediagonal formed by other two points on quadrangle.This is more clear from the figure 11.[1]This operationis known as Edge-Flip.Throughout the motion of robots, at everytimestep, we make sure that if any local certificate iscompromised, we do edge-flip operation(fig. 11) andmaintain the quality of the compact Voronoi diagrams.Using Deformation retract, robots trace the whole mapwithout collision.

​

编辑

2 部分代码

function [mink_map] = minkowski(side_length, clearance, map)
[m,n] = size(map);
robotRad = side_length/sqrt(2) + clearance;
% Enlarging the boundaries of the map.
map(2+ round(side_length/2),round(side_length/2)+10:n-round(side_length/2)-10)=0;
map(m - round(side_length/2)-1,round(side_length/2)+10:n-round(side_length/2)-10)=0;
map(round(side_length/2)+10:m-round(side_length/2)-10,2+round(side_length/2))=0;
map(round(side_length/2)+10:m-round(side_length/2)-10,n-round(side_length/2)-1)=0;
%map(:,n-round(side_length/2))=0;
mink_map = map;
for i=1+round(side_length/2):m - round(side_length/2)
for j=1+round(side_length/2):n - round(side_length/2)
if map(i,j) == 0
%mink_map = insertShape(mink_map,'FilledCircle',[j, i, robotRad], 'Color', 'black');
%rectangle('Position',[j-(side_length/2),i-(side_length/2),side_length, side_length],'Edgecolor', [0,0,0]);
mink_map(i-round(side_length/2):i+ round(side_length/2),j-round(side_length/2):j+round(side_length/2))=0;
end
end
end
end

3 仿真结果

​

编辑

4 参考文献

[1]许松清, 吴海彬, 林宜,等. 基于Voronoi图法的移动机器人路径规划[J]. 中国工程机械学报, 2005(3):5.

博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。

​

编辑