本发明涉及一种基于Voronoi‑APF算法的群组机器人路径规划方法，首先利用栅格法进行环境建模，并对障碍物进行预处理；然后采用匈牙利算法和替换策略为群组机器人进行目标指派；最后通过群组机器人的实时位置构建Voronoi图，各机器人各自使用人工势场算法进行路径规划，并对其运动空间进行划分，限制其路径在构建的Voronoi图的对应分割空间中，即机器人单次运动到终点或分隔空间的边界便停止；重复该步骤，直到所有群组机器人到达指定终点。本发明在时间消耗和路径长度上的改进效果，另外在通用性、时间消耗、路程消耗方面都有着一定程度的优化。
1.一种基于Voronoi‑APF算法的群组机器人路径规划方法，其特征在于，包括如下步骤：(1)利用栅格法进行环境建模，并对障碍物进行预处理；
(2)采用匈牙利算法和替换策略为群组机器人进行目标指派；
(3)通过群组机器人的实时位置构建Voronoi图，各机器人各自使用人工势场算法进行路径规划，并对其运动空间进行划分，限制其路径在构建的Voronoi图的对应分割空间中，即机器人单次运动到终点或分隔空间的边界便停止；重复该步骤，直到所有群组机器人到达指定终点；具体为：通过机器人当前位置集合S，采用Delaunay三角剖分法构建Voronoi图，将全空间UU划分为NN个单元V＝{V1，V2，...，Vn}，其与集合S元素一一对应，满足下式：Vi＝{p∈U|d(p，Xi)≤d(p，Xj)for all j≠i}
对于每个单元Vi，其均为凸多边形；采用一组离散结点P＝{p1，p2，...，pk}表示；假设该离散点集合按顺时针排序，对于单元内的任意一点Q，恒满足下式，则该点位于Vi中；
将群组中单个机器人看作节点，则基于机器人节点位置构建Voronoi图具有以下性质：Voronoi单元中任意一点到该单元机器人节点的距离均小于或等于该点到相邻单元机器人节点的距离，同时基于单个机器人节点的位置对空间平面进行剖分，所以生成Voronoi单元中有且仅有一个机器人节点；因此可利用Voronoi图中各个节点关系或者单元之间的几何特征来约束群组机器人路径规划中碰撞避免；每个机器人在对应单元中，使用人工势场算法进行路径规划，当机器人到达对应的终点或超出运动范围时，则机器人单次迭代运动结束；需要注意的是，机器人同时向Voronoi图中的边界运动时，有极小概率在边界上发生碰撞，此时机器人可采取少量回退操作，避免碰撞发生。
2.根据权利要求1所述的一种基于Voronoi‑APF算法的群组机器人路径规划方法，其特征在于：所述基于Voronoi‑APF算法的群组机器人路径规划方法还包括步骤(4)，对群组机器人的运动控制进行优化，实现群组机器人的运动控制。
3.根据权利要求1所述的一种基于Voronoi‑APF算法的群组机器人路径规划方法，其特征在于：所述步骤(1)具体如下：机器人在2D空间运动，已知：①所有机器人起点；②目标配置要求；③障碍物信息；则机器人自组装环境用有限空间存储以及表达，采用栅格法进行环境建模：选取适当的矩形空间，满足空间包含上述①②位置，再将环境划分成u×v个栅格；
最后采用直角坐标法表示栅格位置，则任意栅格均可用数据对{x，y}表示坐标；
在对障碍物进行预处理时，将机器人视作质点，对障碍物进行膨胀化处理，即保持障碍物形状不变，障碍物外围轮廓向外偏移一定距离；对障碍物进行了上述的膨胀化处理后，只保留膨胀后增加部分的障碍物信息，舍弃原障碍物信息；基于上述环境建模和障碍物处理后，后续工作将基于如下四种假设展开：2D平面除障碍物外均匀光滑；机器人可确定自身坐标与运动方向；机器人有足够能力完成任务；自组装任务可完成。
4.根据权利要求1所述的一种基于Voronoi‑APF算法的群组机器人路径规划方法，其特征在于：所述步骤(2)具体如下：假设群组机器人中有N个机器人，其位置集合为S＝{S1，S2，...，SN}，假设目标配置集合为T＝{T1，T2，...，TN}，为了获得最小代价完成一一对应的目标配置，则问题转化为指派问题；
对于成本矩阵 其中cij代表机器人Si到目标Tj的代价，需要找到最优
根据康尼格定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数，采用匈牙利算法计算指派矩阵流程如下：(i)成本矩阵C各行所有元素减去该行最小值，各列所有元素减去该列最小值；
(ii)若能找到N个独立的0元素，则可以进行指派，0元素对应位置的Xij＝1，其他位置Xi，j＝0，指派结束；
(iii)对于K个独立的0元素，其中K＜N，用K条直线覆盖所有0元素，找到最小的未覆盖元素a，未被覆盖的行所有元素都减a，被覆盖的列所有元素都加a；返回步骤(ii)；
考虑到代价矩阵无法在复杂环境下精准得出，设定了更新目标指派的时间阈值Δt，若当前时间距离上次目标指派时间超过阈值Δt，则重新进行目标指派；其次，传统的代价矩阵采用欧式距离或曼哈顿距离，如下式所示；
其中，ho代表欧式距离，hm代表曼哈顿距离，dx，dy分别代表起点与终点的横坐标、纵坐标之差；在此采用对角距离，如下式所示：hd＝D(dx+dy)+(D2‑2*D)*min(dx，dy)
其中，D表示机器人进行平行移动的移动代价，D2表示机器人进行对角移动的移动代价；
若选择指派矩阵X2，机器人S2将会阻挡机器人S1；考虑自组装的实际需求，应当选择指派矩阵X1，即S1→T1，S2→T2；类似情况下，匈牙利算法生成结果可能有多个相同最优解结果，引入替换策略：当匈牙利算法运行结束后，若存在两对目标指派Sa→Ty，Sb→Tz，同时满足下式，则交换两机器人的目标点，即修改指派矩阵：Ca，y+Cb，z＝Ca，z+cy，b
abs(Cα，z‑cy，b)＜abs(Ca，y‑Cb，z)。
5.根据权利要求2所述的一种基于Voronoi‑APF算法的群组机器人路径规划方法，其特征在于：所述步骤(4)机器人运动控制时，当机器人受到力的方向和运动方向一直成钝角时，会发生抖动现象，因此优化时，采用下式所示运动控制公式以解决抖动问题：
其中，x(t)，y(t)表示机器人现在所在位置，x(t+1)，y(t+1)表示机器人所要到达的位置；θ(t)表示机器人当前的运动方向，Δθ表示机器人到达下一步位置所要改变多少运动方向，l表示机器人的运动距离；当机器人改变运动方向为锐角时，不改变运动规则，当机器人改变运动方向为钝角时，限制改变方向至多为直角；τ表示调整参数；基于上述运动规则，机器人采用两步法进行运动：先通过旋转满足方向要求，再通过直线运动满足位移要求。
一种基于Voronoi‑APF算法的群组机器人路径规划方法
技术领域
[0001] 本发明涉及计算机人工智能技术领域，尤其涉及一种基于Voronoi‑APF算法的群组机器人路径规划方法。
背景技术
[0002] 自组装是群组机器人协作中的重要研究领域，为了达成目标配置，路径规划尤为关键。路径规划和障碍躲避是该领域的核心问题。而在复杂的实际应用环境中，保证机器人之间的碰撞避免和躲避地图障碍物问题则越来越受重视。人工势场算法(APF)及其改进在机器人路径规划中应用广泛但其在动态目标指派、迭代速度、机器人抖动等方面表现不尽如人意，其中在OAPF算法中，距离因子即指在原人工势场算法的斥力计算公式中添加距离要素，该方法的引入导致机器人路径规划与机器人运动终点高度紧密联系。而在复杂地图中单纯考虑距离要素并不一定达成最优规划。例如外围的机器人优先到达终点将导致内围机器人无法进入。当机器人在越过复杂地形后需要交换目标点时，若不考虑动态指派策略，势必会影响算法的鲁棒性和收敛性。
[0003] 在碰撞避免问题上，虽然OAPF算法将机器人自身以外的个体视作障碍物，很好地解决了碰撞问题。但是，这意味着在每一次迭代过程中，每个机器人都需要知道其他所有机器人当前位置以构建斥力场，考虑实际情况下的机器人通讯问题，这个问题极大程度地限制了模型的效率与实际应用。
[0004] 在OAPF算法中，通过限制机器人单次迭代中运动的步长来避免机器人同时运动时发生碰撞，大大增加算法复杂度，所以导致完成目标配置的时间开销提升同时群组机器人逐渐聚集导致机器人之间的斥力势增大，机器人则越不容易接近目标点，路程方面的开销势必增加。
[0005] 通过以上分析可知，人工势场改进算法OAPF不适应动态的目标指派策略，在该方面有较大的改进空间，其次，机器人之间的斥力势，虽然解决了机器人间的碰撞问题，但大大降低了算法的性能和实际应用的可行性。
发明内容
[0006] 本发明为克服上述的不足之处，目的在于提供一种基于Voronoi‑APF算法的群组机器人路径规划方法，本发明首先使用匈牙利算法和替换策略为各机器人指定目标点，然后通过群组机器人的实时位置构建Voronoi图，各机器人各自使用人工势场算法进行路径规划，限制其路径在构建的Voronoi图的对应分割空间中，即机器人单次运动到终点或分隔空间的边界便停止。重复以上步骤，直到所有机器人到达指定终点。VAPF算法既保留人工势场算法的优势，又实现了机器人间的碰撞避免。通过matlab仿真对比实验可证明其在时间消耗和路径长度上的改进效果。本发明在通用性、时间消耗、路程消耗方面都有着一定程度的优化。
[0007] 本发明是通过以下技术方案达到上述目的：一种基于Voronoi‑APF算法的群组机器人路径规划方法，包括如下步骤：
[0008] (1)利用栅格法进行环境建模，并对障碍物进行预处理；
[0009] (2)采用匈牙利算法和替换策略为群组机器人进行目标指派；
[0010] (3)通过群组机器人的实时位置构建Voronoi图，各机器人各自使用人工势场算法进行路径规划，并对其运动空间进行划分，限制其路径在构建的Voronoi图的对应分割空间中，即机器人单次运动到终点或分隔空间的边界便停止；重复该步骤，直到所有群组机器人到达指定终点。
[0011] 作为优选，所述基于Voronoi‑APF算法的群组机器人路径规划方法还包括步骤(4)，对群组机器人的运动控制进行优化，实现群组机器人的运动控制。
[0012] 作为优选，所述步骤(1)具体如下：机器人在2D空间运动，已知：①所有机器人起点；②目标配置要求；③障碍物信息；则机器人自组装环境用有限空间存储以及表达，采用栅格法进行环境建模：选取适当的矩形空间，满足空间包含上述①②位置，再将环境划分成u×v个栅格；最后采用直角坐标法表示栅格位置，则任意栅格均可用数据对{x，y}表示坐标；
[0013] 在对障碍物进行预处理时，将机器人视作质点，对障碍物进行膨胀化处理，即保持障碍物形状不变，障碍物外围轮廓向外偏移一定距离；对障碍物进行了上述的膨胀化处理后，只保留膨胀后增加部分的障碍物信息，舍弃原障碍物信息；基于上述环境建模和障碍物处理后，后续工作将基于如下四种假设展开：2D平面除障碍物外均匀光滑；机器人可确定自身坐标与运动方向；机器人有足够能力完成任务；自组装任务可完成。
[0014] 作为优选，所述步骤(2)具体如下：
[0015] 假设群组机器人中有N个机器人，其位置集合为S＝{S1，S2，...，SN}，假设目标配置集合为T＝{T1，T2，...，TN}，为了获得最小代价完成一一对应的目标配置，则问题转化为指派问题；
[0016] 对于成本矩阵 其中ci，j代表机器人Si到目标Tj的代价，需要找到最优指派矩阵X，需满足如下公式：
[0017]
[0018]
[0019] 根据康尼格定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数，采用匈牙利算法计算指派矩阵流程如下：
[0020] (i)成本矩阵C各行所有元素减去该行最小值，各列所有元素减去该列最小值；
[0021] (ii)若能找到N个独立的0元素，则可以进行指派，0元素对应位置的Xi，j＝1，其他位置Xi，j＝0，指派结束；
[0022] (iii)对于K(K＜N)个独立的0元素，用K条直线覆盖所有0元素，找到最小的未覆盖元素a，未被覆盖的行所有元素都减a，被覆盖的列所有元素都加a；返回步骤(ii)；
[0023] 考虑到代价矩阵无法在复杂环境下精准得出，设定了更新目标指派的时间阈值Δt，若当前时间距离上次目标指派时间超过阈值Δt，则重新进行目标指派；其次，传统的代价矩阵采用欧式距离或曼哈顿距离，如下式所示；
[0024]
[0025] hm＝dx+dy
[0026] 其中，ho代表欧式距离，hm代表曼哈顿距离，dx，dy分别代表起点与终点的横坐标、纵坐标之差；在此采用对角距离，如下式所示：
[0027] hd＝D(dx+dy)+(D2‑2*D)*min(dx，dy)其中，D表示机器人进行平行移动的移动代价，D2表示机器人进行对角移动的移动代价；指派矩阵 与 均为最优指派；
[0028] 若选择指派矩阵X2，机器人S2将会阻挡机器人S1；考虑自组装的实际需求，应当选择指派矩阵X1，即S1→T1，S2→T2；类似情况下，匈牙利算法生成结果可能有多个相同最优解结果，引入替换策略：
[0029] 当匈牙利算法运行结束后，若存在两对目标指派Sa→Ty，Sb→Tz，同时满足下式，则交换两机器人的目标点，即修改指派矩阵：
[0030] Ca，y+Cb，z＝Ca，z+Cy，b
[0031] abs(Ca，z‑Cy，b)＜abs(Ca，y‑Cb，z)。
[0032] 作为优选，所述步骤(3)具体为：通过机器人当前位置集合S，采用Delaunay三角剖分法构建Voronoi图，将全空间UU划分为NN个单元V＝{V1，V2，...，Vn}，其与集合S元素一一对应，满足下式：
[0033] Vi＝{p∈U|d(p，Xi)≤d(p，Xj)for all j≠i}
[0034] 对于每个单元Vi，其均为凸多边形；采用一组离散结点P＝{p1，p2，...，pk}表示；假设该离散点集合按顺时针排序，对于单元内的任意一点Q，恒满足下式，则该点位于Vi中；
[0035]
[0036] 将群组中单个机器人看作节点，则基于机器人节点位置构建Voronoi图具有以下性质：Voronoi单元中任意一点到该单元机器人节点的距离均小于或等于该点到相邻单元机器人节点的距离，同时基于单个机器人节点的位置对空间平面进行剖分，所以生成Voronoi单元中有且仅有一个机器人节点；因此可利用Voronoi图中各个节点关系或者单元之间的几何特征来约束群组机器人路径规划中碰撞避免；
[0037] 每个机器人在对应单元中，使用人工势场算法进行路径规划，当机器人到达对应的终点或超出运动范围时，则机器人单次迭代运动结束；需要注意的是，机器人同时向Voronoi图中的边界运动时，有极小概率在边界上发生碰撞，此时机器人可采取少量回退操作，避免碰撞发生。
[0038] 作为优选，所述步骤(4)机器人运动控制时，当机器人受到力的方向和运动方向一直成钝角时，会发生抖动现象，因此优化时，采用下式所示运动控制公式以解决抖动问题：
[0039]
[0040]
[0041] 90°≤|Δθ|≤180°
[0042] 其中，x(t)，y(t)表示机器人现在所在位置，x(t+1)，y(t+1)表示机器人所要到达的位置；θ(t)表示机器人当前的运动方向，Δθ表示机器人到达下一步位置所要改变多少运动方向，l表示机器人的运动距离；当机器人改变运动方向为锐角时，不改变运动规则，当机器人改变运动方向为钝角时，限制改变方向至多为直角；τ表示调整参数；基于上述运动规则，机器人采用两步法进行运动：先通过旋转满足方向要求，再通过直线运动满足位移要求。
[0043] 本发明的有益效果在于：(1)本发明引入了动态的目标指派策略，通过群组机器人实时位置和目标之间的对角距离构建成本矩阵，使用匈牙利算法进行最优指派，针对多最优解的情况，使用替换策略优化目标指派；(2)本发明引入了Voronoi约束保证机器人间的碰撞避免，通过群组机器人实时位置构建Voronoi图，限制单机器人的单次迭代运动范围在Voronoi图对应的cell中；该方法既保证了机器人之间的避免，又极大程度提升了机器人的单次迭代运动范围；(3)本发明引入了运动控制方法解决机器人抖动问题，通过机器人改变运动角度的大小划分运动策略，当角度过大发生抖动现象时，限制运动角度，并缩小运动步长。
附图说明
[0044] 图1是本发明的方法流程示意图；
[0045] 图2是本发明实施例的对障碍物处理示意图；
[0046] 图3是本发明实施例的目标指派的特殊情况示意图；
[0047] 图4是本发明实施例的VAPF算法实现直线型自组装示意图；
[0048] 图5是本发明实施例的VAPF算法实现H型自组装示意图；
[0049] 图6是本发明实施例的VAPF算法实现不规则型自组装示意图；
[0050] 图7是本发明实施例的算法时间消耗对比图；
[0051] 图8是本发明实施例的算法路程消耗对比图。
具体实施方式
[0052] 下面结合具体实施例对本发明进行进一步描述，但本发明的保护范围并不仅限于此：
[0053] 实施例：如图1所示，一种基于Voronoi‑APF算法的群组机器人路径规划方法，首先使用匈牙利算法和替换策略为各机器人指定目标点，然后通过群组机器人的实时位置构建Voronoi图，各机器人各自使用人工势场算法进行路径规划，限制其路径在构建的Voronoi图的对应分割空间中，即机器人单次运动到终点或分隔空间的边界便停止。重复以上步骤，直到所有机器人到达指定终点。VAPF算法既保留人工势场算法的优势，又实现了机器人间的碰撞避免。通过matlab仿真对比实验可证明其在时间消耗和路径长度上的改进效果。所述方法包括以下步骤：
[0054] 步骤一：环境建模和障碍物预处理
[0055] 机器人在2D空间运动，已知：①所有机器人起点；②目标配置要求；③障碍物信息。则机器人自组装环境可以用有限空间存储以及表达，本发明采用栅格法进行环境建模。
[0056] 选取适当的矩形空间，满足空间包含上述①②位置，再将环境划分成u×v个栅格。最后采用直角坐标法表示栅格位置，则任意栅格均可用数据对{x，y}表示坐标。
[0057] 为了简化问题，本发明将机器人视作质点，那么为了保证机器人和障碍之间的碰撞避免，需要对障碍物进行膨胀化处理，即保持障碍物形状不变，障碍物外围轮廓向外偏移一定距离。考虑到障碍物的不可预估性，膨胀化处理有助于机器人与障碍物保持安全距离，能及时规避风险。
[0058] 其次，障碍物无法跨越，且机器人初始位置不在障碍物中，那么障碍物只有外围轮廓信息是机器人路径规划的必要信息。所以本发明对障碍物进行了上述的膨胀化处理后，只保留膨胀后增加部分的障碍物信息，舍弃原障碍物信息。大大减少了环境信息的数据量，有利于机器人进行更高效的路径规划。对障碍物处理示例如图2所示。
[0059] 基于上述环境建模和障碍物处理，后续工作将基于如下四种假设展开：2D平面除障碍物外均匀光滑；机器人可确定自身坐标与运动方向；机器人有足够能力完成任务；自组装任务可完成。
[0060] 步骤二：目标指派
[0061] 假设群组机器人中有N个机器人，其位置集合为S＝{S1，S2，...，SN}，假设目标配置集合为T＝{T1，T2，...，TN}，为了获得最小代价完成一一对应的目标配置，则问题转化为指派问题。
[0062] 对于成本矩阵 其中ci，j代表机器人si到目标Tj的代价，要找到最优指派矩阵X，需满足式(1)、式(2)。
[0063]
[0064]
[0065] 根据康尼格定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数，本发明采用匈牙利算法计算指派矩阵流程如下：
[0066] 2.1)：成本矩阵C各行所有元素减去该行最小值，各列所有元素减去该列最小值。
[0067] 2.2)：若能找到N个独立的0元素，则可以进行指派，0元素对应位置的Xi，j＝1，其他位置Xi，j＝0。指派结束。
[0068] 2.3)：对于K(K＜N)个独立的0元素，用K条直线覆盖所有0元素，然后找到最小的未覆盖元素a，未被覆盖的行所有元素都减a，被覆盖的列所有元素都加a。返回步骤二。
[0069] 考虑到代价矩阵无法在复杂环境下精准得出，本发明算法设定了更新目标指派的时间阈值Δt，若当前时间距离上次目标指派时间超过阈值Δt，则重新进行目标指派。其次，传统的代价矩阵一般采用欧式距离或曼哈顿距离，如式(3)、式(4)所示。
[0070]
[0071] (3)
[0072] hm＝dx+dy
[0073] (4)
[0074] 其中，ho代表欧式距离，hm代表曼哈顿距离，dx，dy分别代表起点与终点的横坐标、纵坐标之差。欧式距离表示两点之间的直线距离，未考虑障碍物的影响，且平方根运算增大了计算量。曼哈顿距离则只考虑了四个方向的运动，未考虑对角运动，脱离实际，不利于目标指派。为了更为贴近实际情况，同时保证运算的简单高效，本发明采用对角距离，如式(5)所示。
[0075] hd＝D(dx+dy)+(D2‑2*D)*min(dx，dy)
[0076] (5)
[0077] 其中，D表示机器人进行平行移动的移动代价，D2表示机器人进行对角移动的移动代价。
[0078] 考虑图3所示特殊情况，指派矩阵 与 均为最优指派。
[0079] 若选择指派矩阵X2，机器人S2将会阻挡机器人S1。考虑自组装的实际需求，应当选择指派矩阵X1，即S1→T1，S2→T2。类似情况下，匈牙利算法生成结果可能有多个相同最优解结果，本发明提出了替换策略。
[0080] 当匈牙利算法运行结束后，若存在两对目标指派Sa→Ty，Sb→Ts，同时满足式(6)、式(7)，则交换两机器人的目标点，即修改指派矩阵。
[0081] Ca，y+Cb，z＝Ca，z+Cy，b
[0082] (6)
[0083] abs(Ca，zCy，b)＜abs(Ca，y‑Cb，z)
[0084] (7)
[0085] 通过以上策略，可以有效地均衡各机器人的运行距离，并解决上述特殊情况产生的问题。
[0086] 步骤三：运动空间划分与路径规划
[0087] 通过机器人当前位置集合S，使用Delaunay三角剖分法构建Voronoi图，将全空间U划分为N个单元V＝{V1，V2，...，Vn}，其与集合s元素一一对应，满足式(8)。
[0088] Vi＝{p∈U|d(p，Xi)≤d(p，Xj)for all j≠i}
[0089] (8)
[0090] 对于每个单元Vi，其均为凸多边形。因为单元Vi为凸多边形，所以可以用一组离散结点P＝{p1，p2，...，pk}表示。假设该离散点集合按顺时针排序，对于单元内的任意一点Q，恒满足式(9)，则该点位于Vi中。
[0091]
[0092] 将群组中单个机器人看作节点，那基于机器人节点位置构建Voronoi图具有以下性质：Voronoi单元中任意一点到该单元机器人节点的距离均小于或等于该点到相邻单元机器人节点的距离，同时基于单个机器人节点的位置对空间平面进行剖分，所以生成Voronoi单元中有且仅有一个机器人节点。因此可以利用Voronoi图中各个节点关系或者单元之间的几何特征来约束群组机器人路径规划中碰撞避免。
[0093] 每个机器人在对应单元中，使用人工势场算法进行路径规划，当机器人到达对应的终点或超出运动范围时，则机器人单次迭代运动结束。人工势场算法的具体算法(单机器人单次迭代运动流程)如表1所示。
[0094]
[0095] 表1
[0096] 需要注意的是，机器人同时向Voronoi图中的边界运动时，有极小概率在边界上发生碰撞，此时机器人可采取少量回退操作，避免碰撞发生。
[0097] 步骤四：群组机器人的运动控制
[0098] 在完成碰撞避免和障碍躲避后，本发明对群组机器人的运动控制进行了研究。人工势场算法中，当机器人受到力的方向和运动方向一直成钝角时，会发生抖动现象，尤其是在机器人与目标点之间存在障碍物的情况下。在实际应用中，机器人期望有一条相对平滑的路径，抖动现象并不利于机器人运动。本发明提出如式(10)、式(11)所示运动控制方法以解决抖动问题。
[0099]
[0100]
[0101] 其中，x(t)，y(t)表示机器人现在所在位置，x(t+1)，y(t+1)表示机器人所要到达的位置；θ(t)表示机器人当前的运动方向，Δθ表示机器人到达下一步位置所要改变多少运动方向，l表示机器人的运动距离；当机器人改变运动方向为锐角时，不改变运动规则，当机器人改变运动方向为钝角时，限制改变方向至多为直角；τ表示调整参数，当机器人可能发生抖动时，限制机器人运动步长，可以有效地缓解抖动现象。
[0102] 基于上述运动规则，机器人采用两步法进行运动：先通过旋转满足方向要求，再通过直线运动满足位移要求。采用此方法进行控制，不仅能有效降低机器人控制难度，还能控制单个机器人成本。
[0103] 本发明在matlab平台上进行了仿真实验。实验保证算法运行环境不变，且设置了良好的参数。表2展示了VAPF算法的参数列表。
[0104]
[0105] 表2
[0106] 机器人自组装环境设定为500*500的栅格图，图中不规则地分布着若干个圆形代表地图上的障碍物。机器人的初始位置为随机分布，但保证机器人不在障碍物内部，且目标点数量与机器人数量相同。
[0107] 本实验采用自组装问题中的直线型、H型和不规则型进行对比实验。其中，直线型和H型是最为简单常规的模型，能有效地测试算法正确性、稳定性与性能，而且这类简单模型的复合可以模仿动物的运动方式，有广泛的应用前景。本实验设计的直线型和H型模型分布均匀，而不规则型的目标点分布不均，但在一定程度上为包围型自组装配置，能有效考验算法在目标指派问题上的性能。上述三种模型实验示例如图4、图5、图6所示。图中，黑色的圆环代表预处理后的障碍物；黑色实线代表机器人各自规划的路径；实线终点的标记代表实验设定的目标点；不同的色块由Voronoi图构建，其代表机器人各自的运动范围，能有效地帮助机器人实现碰撞避免。
[0108] 通过上述结果可见，使用VAPF算法，机器人在不同自组装模型下均能高效、安全地到达各自的目标点。目标指派策略使得机器人各自到达目标点的消耗实现了最大程度上的均衡；运动空间划分能有效避免碰撞；运动控制方法能有效地抑制机器人在进行路径规划时发生抖动现象。
[0109] 针对上述实验模型，本实验通过不断增加机器人数量来对比VAPF算法和OAPF算法在时间和路程方面的表现。实验结果数据如图7和图8所示。从多组对比实验可以看出，时间消耗方面：两种算法的时间消耗均随着机器人数量的增加而增加，OAPF算法时间消耗呈近似指数增长趋势，而VAPF算法的时间消耗增速远低于OAPF算法。在机器人数量相对较少时，两种算法的性能差别尤为明显。VAPF通过Voronoi图划分运动空间，机器人数量相对较少意味着其分布也相对稀疏，则每个机器人在单次迭代中有更大的独立运动空间。高效的迭代性能使得少量群组机器人的加入对VAPF算法性能影响极小，所以在图7中，当机器人数量不足20个时，时间消耗基本没有变化。而OAPF算法每次迭代要考虑机器人之间斥力，且单次迭代运动空间极小，即使是少量群组机器人的加入也会严重加剧算法的时间消耗。H型自组装相对于直线型自组装更为复杂，不规则型自组装更甚之，复杂的自组装要求会大大增加OAPF算法的时间消耗，而VAPF算法在不同自组装要求下性能稳定，且远优于OAPF算法。平均路程长度方面：机器人的分布对结果有着相对重要的影响，随着机器人数量的增加，随机且均匀的分布会使得机器人平均路程愈发稳定。由于OAPF算法中机器人之间存在斥力，OAPF算法的平均路程长度均多于VAPF算法，在复杂类型的自组装实验中尤为明显。
[0110] 通过上述实验对比分析，VAPF算法无论是在时间消耗方面还是路程长度方面都有着显著的优势，且对不同的自组装要求以及群组机器人规模均有着良好的适应性。总的来说，VAPF算法达成了自组装过程中的碰撞避免和障碍躲避要求，在性能方面有着显著的优越性，有着一定的应用前景。
[0111] 以上的所述乃是本发明的具体实施例及所运用的技术原理，若依本发明的构想所作的改变，其所产生的功能作用仍未超出说明书及附图所涵盖的精神时，仍应属本发明的保护范围。
