#一种进化算法的移动机器人

一种进化算法的移动机器人摘要—-本文提出了一种新算法同时定位和绘图（SLAM）技术的移动机器人。这种算法，被称为进化的SLAM，是基于一个岛屿模型遗传算法（IGA）。该算法寻找最有可能的图形，基于机器人的姿势提供给机器人最佳定位信息。通过探索自然选择学说，这种算法的通信问题得到解决，那就是适者生存。该算法不遵循任何明确的启发式回路关闭，而是保持多个假设解决闭环问题。该算法递增地处理传感器数据，因此有在线工作的能力。在不同的室内环境的实验结果验证了算法的鲁棒性。I简介同时定位和绘图算法利用传感器收集到的机器人在某一环境下一系列的运动轨迹来生成空间描述过程地址。一个综合性的研究成果已经报告了SLAM，其中大部分来源于斯密斯［见索引1］早期工作成果。他的早期的工作为解决ALSM提供了一种基于卡尔曼滤波（KF）的统计框架。这种基于SLAM算法的滤波器需要提取和和鉴别传感器数据的特性和遵循传感器测量中的高斯噪声假设。粒子滤波下概率技术它已经在SLAM文献获得普及。该混合算法提出了在［2］采用粒子滤波技术基于机器人的姿态来做出估计，能以此绘出大循环环境。然而，一个成功的事后估计的机器人的构成需要一些粒子始终包括一个粒子的盆地吸引力的真实姿势［3］。此外，该算法需要后传播匹配误差沿循环回路关闭，时间复杂度随环的长度而增加。该FastSLAM算法［4］不需要明确的闭环算法。该算法采用标志选择和识别的复杂度来缓解在数据关联方面［5］的一些挑战。此外，FastSLAM算法需要大量粒子来使循环结束，尽管该算法的效率取决于较少粒子数［3］需求量。分布式particle-slam（DP-SLAM）［5］不需要从传感器数据中特征提取或识别。它提出了一种巧妙的数据结构来有效地存储关联到不同粒子的地图。然而，该算法的存储效率和数据检索的复杂度有关。在SLAM环境中，粒子滤波器的普及在于其保持多个假设机器人的姿态和地图的能力，从而提供一个解决通信问题的办法。在基于SLAM算法的粒子滤波器中，重复采样步骤仅选择当前粒子的一个子集，它的历史支持当前传感器测量［2］［4］［5］。其余的从竞争中删除。这种重复采样策略对SLAM有以下影响。在一个给定的时间点，如果粒子提供的分支的支持区域不包括机器人的实际位姿（这总是发生在闭环时，和/或开始任何意外打滑时），重复采样不能从执行电流测量的错误解释中挽救算法。地图中产生的不一致性，甚至单次测量错误的解释，只能通过错误的反向传播进行修改。重复采样后，多个类似的粒子随着相关的地图而保存。它涉及到大量的内存要求。最近的一项工作，对移动机器人的定位［6］试图解决这一问题，第一取样援引的概念，共同进化的标准蒙特卡洛定位（MCL）的方法。DPSLAM［5］通过提

出一中记忆效应的数据结构处理来第二个问题。在SLAM文献中一个相对较新的概念是遗传算法（GA）［7］［8］的使用。第一算法基于遗传算法［7］，把SLAM全球优化问题去寻求机器人的最优姿势。作为一个全局优化问题搜索优化构成的机器人。该算法需要处理整个数据集在一起（批处理算法）和假设很小的误差量测程法。然而，该算法关闭一个环时复制大量积累错误的能力不明显。本文提出一种进化算法和解决主要问题，即通信问题，闭环问题，和增量处理传感器数据。类似于基于SLAM⑷⑸的粒子滤波器，该进化算法也提出了机器人的位置的不确定性。每个样品提出了一个关于客观世界的假设。利用进化原则和遗传算子处理处理这些假设。该算法的新颖性在于以下几个方面。1）进化SLAM算法利用自然选择（适者生存）设计一个通信问题的迭代法解决方案。2）进化SLAM算法不遵循任何明确的启发式回路关闭，而通过一个岛屿模型（IGA）遗传算法保持关于世界的多假设，自然地支持并行处理。3）进化SLAM算法保持粒子的多样性，特别是在闭环时间点，通过变异算子（能在后代中产生有利的变异）。不像粒子滤波器的重复采样阶段，IGA执行一个精英式采样（选择，遗传算法中的术语），种群中不会出现几

个个体的几个复制体。该算法以递增的方式处理数据，即在任何时间点只有可用的传感器检测是用来产生环境的局部地图。人口规模，后代的数量，以及其他IGA的参数可以按要求调整优化算法的时间复杂度。II问题的定义一套符号将在本节中定义用来描述上文提到的进化SLAM算法。机器人的姿态x(t)是一个3元组{x,y,0}这里{x,y}是机器人相对于一个假想的坐标系统的空间位置,0是机器人的方向。里程计数据(这和传送到机器人中的控制指令相同)，激光测量分别用u(t)和s(t)代表。下标t代表离散时间指数。这两个传感器测量(u,s)收集在：{S0,u0,S1,U1}。当接收到tth信号时会产生遗传图mt传感器测量St在Xt定义为TOC\o"1-5"\h\zMt=f(x0:t,s0:t) (1)其中，x0:t={x0,xi, ,xt},s={s0,si7 ,st} (2)f:R(t).st+(xt，yt) (3)R(t)是循环矩阵定义为R((((((((() (4)*)=((((((((((() ⑷公式(1)能写成递归的形式如下mt=f(x0,s0)Uf(x1,s1)U...Uf(xt,st)=f(x0：t1，s0：t1)Uf(xt，st

=mt-1uf(xt,stt)=mt1Umxt根据（2）,mxt是当地的地图代从单一传感器扫描。构成文本的相应的局部地图及扩展全球地图机器翻译最小不确定是最好的估计机器人的当前位置。因此，SLAM是减少的问题，搜索机器人的位姿，接到新的传感器（激光）测量。IGA是用来评价地图的质量,最后评估出机器人定位的最优解。作为机器人的姿态是一个三维连续变量，详尽的搜索在大姿态空间。可以从里程计数据中近似得出机器人姿态。里程计的移动机器人受到错误和长时间无限制地。数学模型，试图在里程计中预测不确定性，通常在机器人中称为运动模型。在这项工作中通常分布位置不确定性模型提出的几项SLAM的研究[1][2][4]已通过。在本文的其余部分，这一概率模型将称为运动模型。III岛屿模型GA（2人）和SLAM岛模型是实现并行遗传算法（PGAs）[9]的有效方式。这种方法中种群被分成许多小的亚种群或岛屿。所有这些岛屿独立自主进化，尽管他们遵循基本相似的演化规则。只能在同一岛屿中进行繁殖。不同的岛屿的个体，偶尔通过迁移进行基因交流。搜索性能的免疫方面的解决方案的质量和总人数的评价来得到最好的解决方案已被证明是优于标准遗传算法的若干计算问题[10]。然而，基因算法有助于保持种群遗

传多样性，从而最大限度地减少过早收敛的可能性。每个岛屿上的种群根据选择自由的聚居在一起，但不能保证每个岛将有独特的搜索轨迹［11］。该算法提给第二部分中提到的SLAM问题一个巧妙的解决办法。激光测量对称环境特色，例如长走廊，可能产生明显的相似质量地图对应于几个机器人姿态。因此，搜索算法快速集聚这些解决办法，尽管他们可能都是是次优的。它有一个灾难性的影响，而测绘循环对称环境中的积累误差呈现在时间周期关闭大地图上的拓扑不一致。因此，而不是收敛到一个最佳的解决方案（标准遗传算法［12］），该算法可以聚焦到几个适宜方案。此属性有几个收敛点是很有帮助的，而映射对称环境，特别是循环的环境。它消除了需要中保持独立的启发式回路关闭。此外，重突变（称为大变异在［13］）有助于保持种群的多样性。W 推荐算法一套符号将特定用于描述免疫遗传算法。岛上的种群用Pt,m（n）来表示，从第n代进化到第n+1代，下标m代表第个岛，m=1,2,3……，NI,其中，NI代表岛的总数。种群中的成员用基因变量字符串来xut,m，M代表种群中第p个成员，其中。M迁移规模的大小表明一些成员在一个岛将迁移到不同的岛屿，迁徙的间隔pinterval在两个连续迁移种群后代数。一个完全连接拓扑的偏移，即迁移个体岛将被复制到每个其他岛屿。xy图1遗传染色体结构A:染色体编码:基因型和表型染色体是实数编码。图1显示了一个染色体基因型。映射到表型的基因型是非线性的如式(2)。只有当基因型和一个传感器测量相联系时表型才被发现。因此，染色体有类似的基因型可能有不同的表型。这些表型的每一个实际上是当地的地图(换句话说，一个传感器测量的表述)如式(4)表述。遗传算子使用于基因型虽然合适的评价是表现在表型。因此，相对于SLAM问题，最好的个体，它的基因是解决机器人的定位问题，表型是最小不确定性图给予现有的传感器测量。B.适应度函数适应度函数的设计是受查询路径［14］和概率综合讨论［2］的启发。适应度函数用于表示当地地图扩大到目前全球地图的最小不确定度。在这样做时，它扩展了现有的全球地图和当地的地图和测量过所有的不确定性在生成的地图。对于每个uU5(n)G 概率mt-i,mU1 作为不确定量来计算。因而，适度函数用下式表示F(mxt,m,xt,m)(mtH,mxt,mxt,m(n),t)()F用来计算测量不确定度。在每个障碍点整合后，当地

的地图，假定的电流传感器测量，概率的个人传感器测量，高斯中心零的不确定性的结果。这一假设进行为高精度传感器［1］。空间视为自由在一个传感器扫描可以被视为不在被占领的连续扫描。假设条件独立性之间的个别传感器测量的概率，计算不同障碍点相乘得到国际测量不确定度。较低的价格，更高的不确定性，反之亦然。真实世界环境的景观，虽然功能可以是相当复杂的（和一些局部极大值或全球最大值遵循深谷）SLAM的范围内。C.选择进化算子1）选择:。一小部分的个体选择执行交叉的基础上虽然在一个岛。后代产生交叉维持种群的多样性而充分的外汇储备从以下限制：让我们假定，这个体包含染色体，会出现早熟收敛。突变：在免疫遗传算法，变异中起着重要作用，是保持遗传多样性的引入新的等位基因的人口。双变异算子，提出的算法是：空间变异和东方型突变。空间变异：变异的染色体在这样一种方式的后代是不同的空间位置，方向是相同的父母。定向变异：变异染色体增加多样性取向的同时保将从祖先在三维空间。一个染色体突变（无论是空间或定向突变）添加每一行对应的突变阵列。因此，和传统的遗传算法，一个以上的后代可以通过木站。我的价值观和确定确切人数的后代。只有一小部分，你的人口，允许突变。资格的染色体突变取决于其相对虽然在个别岛屿。为选择过程是跨

代和精英，低-没有后代，如果产生变异，没有生存的机会下一代。探索能力的大大严重的选择££1,2,和中。总之，参数的设置，可以调整改进建议的算法是：人口规模，一些岛屿镍，M大小，M区间，最大数量的后代算法。目前的执行情况进行定值，这些参数。有范围调整，使用智能算法，如模糊逻辑，被认为是未来的工作。V进化算法的变革为了描述了进化算法我们假设，而不丧失概括性，使机器人传感器扫描S0在执行控制命令u0之前。运动模型使用于描述和它相关预测的不确定性。一批样品随机选择的不确定区域。它代表了一套质量好的关于世界的假设他们已经出现在当地不同的岛屿。整合这些地方的地图和全球地图。步骤2到4迭代直至收敛。在达成一项运算时间，人口在不同的岛屿开始变得稠密的无性系的成员，~箭靶，M重复同样的最大虽然几代和单调减少多样性的人口被视为停止条件。最佳~文本，是对不同岛屿的收敛，提出了一套本地地图~机器翻译，它代表了一套质量好的关于世界的假设他们已经出现在当地不同的岛屿。W试验结果该算法的测试和真实世界的数据在不同的室内环境在加拿大纽芬兰纪念大学。实验上进行了activmediaP3AT移动机器人配备了激光测距系统生病200下(图2(a))。映射，机

器人操作的控制杆不同的室内环境和新的传感器测量记录后约50厘米的旅行或20度改变方向。传感器测量仪器取得了跨越180度，0.5o间隔分开，和一个有效距离可达10米。计算时间的算法是确定好所需的时间，虽然评价的总样本数。在每一代人，总样本数需要虽然评价是确定的突变率，交叉率和人口规模，其中的选择是乌尔=10%=10%,铬和唱片心500。其他参数的抗体是倪=8,M大小=4,M间隔=1和吴=10。在大多数情况下，该算法收敛速度在7至8代。在实验中，然而，测量是保存在一个传感器产生的日志乐activmediaP3AT和处理的线快速PC陀螺仪校正机器人关闭获得里程计读数只有。入住栅格地图的环境提出的决议2公分。在栅格地图，白细胞表明地区被认为是空的，黑色细胞表明占领区，和灰色细胞表明未知领域。结果从不同的测试环境是这里。原为计划的测试环境，从蓝打印建筑如图2所示。发达的地图不同，从为计划由于存在不同的物体，如桌子，椅子，盒，和临时分区中存在的环境。4)1：测试的复位测试环境是一个循环hall-way约2200x2000万瓦喔。180激光测量surements已记录。该hall-way非常对称和不包含许多探测功能帮助机器人的位置。止匕外，终结点的无法可靠地从另一端测量。这些增加的可能性，误差积累而结合当地的地图。激光测量绘制根据里程计显示在图3(a)。积累误差的里程计结果大拓扑不一致的地图的时候，闭回路。

此外，打滑的机器人造成频繁的错误。在这八个岛屿的地图中，由第八岛（m=8）具有最大的Q是被视为最小不确定环境地图观察180激光扫描。动态在不同的岛屿如图4所示（小时）。地图质量的基本上是相似的几个传感器测量。这是显示在图4,这表明地图生成从七个不同的岛屿。地图对应的第八个岛屿，如图3所示（b）。该算法成功地消除了不一致在封闭循环中的错误。第六和第七个岛屿也产生了良好的质量图（图4）。虽然他们不能达到接近全局最优解的遗传算法运行时接收后通过第一百五十二个传感器测量第一百四十五。相应的本地地图集成错