一种进化算法移动机器人.docx

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

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

一套符号将在本节中定义用来描述上文提到的进化SLAM算法。机器人的姿态x(t)是一个3 元组{x,y,θ}这里{x,y}是机器人相对于一个假想的坐标系统的空间位置,θ是机器人的方向。里程计数据(这和传送到机器人中的控制指令相同),激光测量分别用u(t)和s(t)代表。下标t代表离散时间指数。这两个传感器测量(u , s)收集在:{