CN103926930A - 一种基于Hilbert曲线探测的多机器人协作地图构建方法 - Google Patents

Abstract

本发明提出一种基于MAPSO算法的多机器人地图构建方法，该方法采用MAPSO全局优化方法与Hilbert曲线探测方法相结合，可有效提高多机器人环境探测精度，减少重复探测次数。综合运用Hilbert曲线特性以及机器人的探测半径，并采用MAPSO算法对机器人待测子区域分配问题进行全局优化，可以避免重复探测，提高探测效率。在Hilbert曲线探测过程中，每个机器人只会在自己的子区域进行探测，避免了机器人发生碰撞的情况。

Description

一种基于Hilbert曲线探测的多机器人协作地图构建方法

技术领域

本发明涉及一种多移动机器人的地图构建方法，尤其涉及一种基于多Agent粒子群优化(MAPSO)算法和Hilbert曲线探测的多移动机器人协作地图构建方法。

背景技术

地图构建是一个具有典型性和通用性的多机器人协调问题，是多机器人协调问题的基础。地图构建技术已广泛应用于国防、工农业、柔性制造业以及无人探险等领域。目前常用的地图表示方法分为三类：栅格法、拓扑法以及几何信息表示法。基于栅格的方法仅需决定每个栅格是空(及栅格的值为0)还是存在障碍物(即栅格的值为1)，对环境的其他特征不感兴趣，且栅格地图容易建立、维护；拓扑法适用于结构化环境，不适用于非结构化环境；基于几何信息表示的方法较为紧凑，便于目标识别以及位置估计。

多Agent粒子群优化算法(MAPSO)需要调整的参数较少，易于实现，且可进行并行计算和无梯度计算，有较好的全局搜索能力。在MAPSO系统中，采用竞争、运动搜索模型，每个备选解被称为“粒子”，该粒子为解空间候选解，解的优劣程度由适应度函数决定。其中，适应度函数根据优化目标定义。多个粒子并存，通过和选取的邻居粒子竞争、合作而得到最优值，速度决定粒子在搜索空间单位迭代次数的位移。

Hilbert曲线探测方法配合机器人的可探测半径，可以避免重复探测相同的区域。多机器人之间协同对未知环境的探测，较大地提高了探测精度，节省探测时间。

发明内容

本发明提出一种基于MAPSO的Hilbert曲线探测构建地图的方法，在对子区域进行Hilbert曲线探测的实现中，引入MAPSO算法对机器人待测子区域分配问题进行全局优化，实现多机器人协作建图，达到减少多机器人在协作建图中的重复探测次数，提高探测效率的目的。

本发明的总体解决方案是：用多机器人完成Hilbert曲线探测，并使用MAPSO算法进行全局优化，使机器人找到近似最优目标区域进行探测。采用栅格法进行地图建模，根据未知环境的整体大小设定正方形区域作为待探测区域。根据机器人的探测半径将待探测区域分割为一些子区域，即其中每个子区域的边长均为机器人探测半径的整数倍。而每个子区域再分割即为传统的栅格，栅格的大小相当于机器人的可探测范围，并采用MAPSO算法为多个机器人分配优选的子区域，而在子区域内部采用Hilbert曲线探测。

本发明所述的方法具体包括如下步骤：

步骤1：将所需探测的环境划分为若干子区域。

步骤2：通过MAPSO算法使处于当前位置的四个机器人找到近似最优目标区域。如果每个机器人都找到有效探测区域，则转到步骤3；如果每个机器人都没有找到有效探测区域，则转到步骤5，即任务结束；如果只有部分机器人没有找到有效探测区域，则按照当前的位置进行下一轮MAPSO算法规划，即返回到步骤2，直到每个机器人都找到有效探测区域。

步骤3：四个机器人采用分布式结构对目标区域进行一步Hilbert曲线探测。

步骤4：判断是否四个机器人全部都完成Hilbert曲线探测过程，如果是，则机器人将进行信息融合，绘制探测的结果图，并转到步骤2；否则，返回步骤3，进行下一步Hilbert曲线探测。

步骤5：任务结束。

本发明主要针对标准的Hilbert曲线探测进行改进，引入MAPSO算法进行全局优化，

本发明提出的基于MAPSO算法的多机器人环境探测方法采用MAPSO全局优化方法与Hilbert曲线探测方法相结合，使得多个机器人尽量避免重复探测，保持相互远离，距离原来的位置最近，实现多机器人协作建图。本方法可有效提高多机器人环境探测精度，减少重复探测次数。综合运用Hilbert曲线特性以及机器人的探测半径，可以避免重复探测，提高探测效率。在Hilbert曲线探测过程中，每个机器人只会在自己的子区域进行探测，避免了机器人发生碰撞的情况。

附图说明

图1基于多Agent粒子群优化和Hilbert曲线探测的多机器人协作建图方法的流程图。

具体实施方式

下面结合附图对本发明进行进一步的说明。

如图1所示，本发明运用MAPSO算法与Hilbert曲线探测的方法相结合，具体实现步骤如下：

步骤1：根据机器人的探测半径，将所需探测的环境划分为若干子区域，为MAPSO全局优化做准备。

步骤2：通过MAPSO算法使处于当前位置的四个机器人找到近似最优目标子区域。当算法结束时，如果每个机器人都找到有效探测区域，则执行下一步的Hilbert曲线探测，即转到步骤3；如果每个机器人都没有找到有效探测区域，则转到步骤5，即任务结束；如果只有部分机器人没有找到有效探测区域，则根据当前的位置进行下一轮MAPSO算法规划，即返回到步骤2，直到每个机器人都找到有效探测区域。

具体地，多Agent粒子群优化算法兼有进化计算和群智能的特点，利用该算法使多个机器人尽量保持相互远离，距离原来的位置最近，并且保证探测区域尽量不重复。

在多Agent粒子群优化算法过程主要包括以下几个部分：

(1)初始化粒子群体：MAPSO首先随机地初始化一群粒子，其中第i个粒子在d维解空间的位置为X_i＝(X_i1,X_i2,X_i3,...,X_id)，初始化粒子的两个极值个体最优值(p_best)和全局最优值(g_best)。

(2)竞争：每个粒子从环境中选取离自己最近的8个粒子作为邻居粒子，并根据计算适应度值调整自己的位置信息。

(3)更新：粒子通过动态跟踪p_best和g_best来更新其速度和位置，其公式如下：

v_id(t+1)＝wv_id(t)+c₁r₁[p_best(t)-x_id(t)]+c₂r₂[g_best(t)-x_id(t)]     (1)

x_id(t+1)＝x_id(t)+v_id(t+1     )(2)

式中，v_id(t+1)表示t+1时刻第i个粒子在d维解空间的速度，x_id(t+1)表示t+1时刻第i个粒子在d维解空间的位置，c₁＝c2＝2，为加速因子，w＝0.7298为惯性因子，r₁和r₂是介于[0,1]之间的随机数，t代表时刻t。

(4)计算适应度值：根据适应度函数计算每个粒子的适应度值，其公式如下：

f_fitness＝w₁D₁-w₂D₂+w₃S₁     (3)

式中，D₁代表机器人的下一个探测目标与当前位置的距离总和，实验中，希望该值越小；D₂代表下一个目标区域中，各机器人的距离总和；当机器人处于下一个目标位置进行探测的时候，S₁正比于已探测区域面积与目标区域的比值。w₁,w₂,w₃为前三个条件函数的加权因子w₁+w₂+w₃＝1。

根据适应度函数更新粒子的全局最优值。当计算所得的最优值到达设计要求时或者算法到达最大迭代次数时，退出MAPSO寻优算法；否则返回到(2)。

步骤3：四个机器人采用分布式结构对目标区域进行一步Hilbert曲线探测。

本发明对探测环境做一下假设：

(1)环境采用栅格法进行建模和描述，各栅格cell(i,j)值cell[i][j]∈{0,1},0表示没有被障碍物占据，1表示被障碍物占据。

(2)机器人已知其初始位置。机器人可以依据其当前所在的位置坐标计算下一步的位置，在仿真中不计因机器人和任意物理因素而导致的定位误差。机器人可以探测障碍物的范围即为传感器可以感知的范围。

(3)环境对机器人来讲是未知的，当其对环境进行探测之后，才能构建环境地图。

(4)每个机器人都可以保存局部地图，在整个地图构建完成之前，每个机器人都保存自己所探测的地图。结束仿真时，机器人将其保存的局部地图传给多机器人系统，这时，完成整个地图的构建，而每个机器人所保存的环境地图被再次置空。

Hilbert曲线探测的原理是机器人沿着四条首尾相连的Hilbert曲线对环境进行探测，每一步Hilbert曲线探测都有两种可能状态：flag＝0即探测、flag＝1即避障。

探测：机器人在初始时刻或者退出避障时，机器人自动进入探测状态。

避障：当机器人遇到障碍物的时候，就进入避障状态，机器人沿障碍物的左侧进行探测，当机器人回到发现障碍的点时，机器人自动退出避障状态，进入探测状态。如果障碍物处跨越了两个子区域时，每个机器人遵循只在自己的子区域探测原则，在子区域的边界处沿原方向返回。当机器人再一次到达子区域的边界是，就理解为已经完成自己区域的探测任务，机器人退出避障状态。机器人根据flag的值进行相应的运动。

步骤4：判断是否四个机器人全部都完成Hilbert曲线探测过程，如果是，则机器人将进行信息融合，绘制探测的结果图，并转到步骤2；否则，返回步骤3，进行下一步Hilbert曲线探测。

步骤5：任务结束。

以上结合附图对本发明的具体实施方式作了说明，但这些说明不能被理解为限制了本发明的范围，本发明的保护范围由随附的权利要求书限定，任何在本发明权利要求基础上的改动都是本发明的保护范围。

Claims (5)

1.一种基于多Agent粒子群优化和Hilbert曲线探测的多机器人协作地图构建方法，其特征在于，所述方法包括以下步骤：

步骤1：根据机器人的探测半径，将所需探测的环境划分为若干子区域，为MAPSO进行全局优化做准备；

步骤2：采用多Agent粒子群算法进行全局优化，使处于当前位置的四个机器人找到近似最优目标区域；如果每个机器人都找到有效探测区域，则继续执行步骤3；如果每个机器人都没有找到有效探测区域，则转到步骤5；如果只有部分机器人没有找到有效探测区域，则按照当前的位置进行下一轮MAPSO算法规划，即返回步骤2，直到每个机器人都找到有效探测区域；

步骤3：四个机器人采用分布式结构对目标区域进行一步Hilbert曲线探测；

步骤4：判断是否四个机器人全部都完成Hilbert曲线探测过程，如果是，则机器人将进行信息融合，绘制探测的结果图，并转到步骤2；否则，返回步骤3，进行下一步Hilbert曲线探测。

步骤5：任务结束。

2.根据权利要求1所述的多机器人协作地图构建方法，其特征在于，所述步骤1具体是采用栅格法进行地图建模，根据未知环境的整体大小设定正方形区域作为待探测区域，把待探测区域分割为一些子区域，其中每个子区域的边长均为机器人探测半径的整数倍，而每个子区域再分割即为传统的栅格，栅格的大小相当于机器人的可探测范围。

3.根据权利要求1所述的多机器人协作地图构建方法，其特征在于，所述步骤2中的采用多Agent粒子群算法进行全局优化的过程包括以下几个部分：

(1)初始化粒子群体：MAPSO首先随机地初始化一群粒子，其中第i个粒子在d维解空间的位置为X_i＝(X_i1,X_i2,X_i3,...,X_id)，初始化粒子的两个极值个体最优值(p_best)和全局最优值(g_best)；

(2)竞争：每个粒子按照从环境中选取离自己最近的8个粒子作为选取邻居粒子，并根据计算适应度值调整自己的位置信息；

(3)更新：粒子通过动态跟踪p_best和g_best来更新其速度和位置，其公式如下：

v_id(t+1)＝wv_id(t)+c₁r₁[p_best(t)-x_id(t)]+c₂r₂[g_best(t)-x_id(t)]     (1)

x_id(t+1)＝x_id(t)+v_id(t+1)     (2)

式中，v_id(t+1)表示t+1时刻第i个粒子在d维解空间的速度，x_id(t+1)表示t+1时刻第i个粒子在d维解空间的位置，c₁＝c2＝2，为加速因子，w＝0.7298为惯性因子，r₁和r₂是介于[0,1]之间的随机数，t代表时刻t；

(4)计算适应度值：根据适应度函数计算每个粒子的适应度值，其公式如下：

f_fitness＝w₁D₁-w₂D₂+w₃S₁     (3)

式中，D₁代表机器人的下一个探测目标与当前位置的距离总和，实验中，希望该值越小；D₂代表下一个目标区域中，各机器人的距离总和；当机器人处于下一个目标位置进行探测的时候，S₁正比于已探测区域面积与目标区域的比值。w₁,w₂,w₃为前三个条件函数的加权因子w₁+w₂+w₃＝1；

根据适应度函数更新粒子的全局最优值，当计算所得的最优值到达设计要求时或者算法到达最大迭代次数时，退出MAPSO寻优算法；否则返回到(2)。

4.根据权利要求1所述的多机器人协作地图构建方法，其特征在于，所述步骤3的Hilbert曲线探测过程如下：机器人沿着四条首尾相连的Hilbert曲线对环境进行探测，机器人根据flag的值进行相应的运动，每一步Hilbert曲线探测都有两种可能状态：flag＝0即探测、flag＝1即避障；

探测：机器人在初始时刻或者退出避障时，机器人自动进入探测状态；

避障：当机器人遇到障碍物的时候，就进入避障状态，机器人沿障碍物的左侧进行探测，当机器人回到发现障碍的点时，机器人自动退出避障状态，进入探测状态；如果障碍物处跨越了两个子区域时，每个机器人遵循只在自己的子区域探测原则，在子区域的边界处沿原方向返回；当机器人再一次到达子区域的边界是，就理解为已经完成自己区域的探测任务，机器人退出避障状态。

5.根据权利要求4所述的多机器人协作地图构建方法，其特征在于，步骤3中，需要对环境进行构建：已知障碍物的位置、大小，通过机器人探测器获取全局信息，存储于机器人内部信息库，为所有机器人共享，当进入机器人需要采取避障行为的范围时，提取相应障碍物或其它机器人信息。