机器人算法专题介绍

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。

特征

一个算法应该具有以下五个重要的特征：

有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

确切性(Definiteness)

算法的每一步骤必须有确切的定义；

输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

要素

数据对象的运算和操作

计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，成为该计算机系统的指令系统。一个计算机的基本运算和操作有如下四类：

1、算术运算：加减乘除等运算

2、逻辑运算：或、且、非等运算

3、关系运算：大于、小于、等于、不等于等运算

4、数据传输：输入、输出、赋值等运算[1]

算法的控制结构

一个算法的功能结构不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

评定

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模n 的函数f(n)，算法的时间复杂度也因此记做。

T(n)=Ο(f(n))

因此，问题的规模n 越大，算法执行的时间的增长率与f(n) 的增长率正相关，称作渐进时间复杂度（Asymptotic Time Complexity）。

空间复杂度

算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

正确性

算法的正确性是评价一个算法优劣的最重要的标准。

可读性

算法的可读性是指一个算法可供人们阅读的容易程度。

健壮性

健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

方法

递推法

递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

递归法

程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：

(1) 递归就是在过程或函数里调用自身;

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

穷举法

穷举法，或称为暴力破解法，其基本思路是：对于要解决的问题，列举出它的所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解。它也常用于对于密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

贪心算法

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

用贪心法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

贪婪算法是一种改进了的分级处理方法，其核心是根据题意选取一种量度标准，然后将这多个输入排成这种量度标准所要求的顺序，按这种顺序一次输入一个量，如果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下最优解的分级处理方法称为贪婪算法。

对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。

一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。

分治法

分治法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征：

(1) 该问题的规模缩小到一定的程度就可以容易地解决；

(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

(3) 利用该问题分解出的子问题的解可以合并为该问题的解；

(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

动态规划法

动态规划是一种在数学和计算机科学中使用的，用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

分支界限法

分枝界限法是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。

分支定界法的基本思想是对有约束条件的最优化问题的所有可行解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。

与贪心算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。

回溯法

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

其基本思想是，在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不

包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

描述方式

描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图。

分类

算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法，厄米变形模型，随机森林算法。

算法可以宏泛的分为三类：

一、有限的，确定性算法 这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务，但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二、有限的，非确定算法 这类算法在有限的时间内终止。然而，对于一个（或一些）给定的数值，算法的结果并不是唯一的或确定的。

三、无限的算法 是那些由于没有定义终止定义条件，或定义的条件无法由输入的数据满足而不终止运行的算法。通常，无限算法的产生是由于未能确定的定义终止条件。

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

提出了一种新算法同时定位和绘图（SLAM）技术的移动机器人。 这种算法，被称为进化的SLAM，是基于一个岛屿模型遗传算法（IGA）。该算法寻找最有可能的图形，基于机器人的姿势提供给机器人最佳定位信息。通过探索自然选择学说，这种算法的通信问题得到解决，那就是适者生存。

同时定位和绘图算法利用传感器收集到的机器人在某一环境下一系列的运动轨迹来生成空间描述过程地址。一个综合性的研究成果已经报告了SLAM，其中大部分来源于斯密斯早期工作成果。他的早期的工作为解决ALSM提供了一种基于卡尔曼滤波（KF）的统计框架。这种基于SLAM算法的滤波器需要提取和和鉴别传感器数据的特性和遵循传感器测量中的高斯噪声假设。粒子滤波下概率技术它已经在SLAM文献获得普及。该混合算法提出了在采用粒子滤波技术基于机器人的姿态来做出估计，能以此绘出大循环环境。然而，一个成功的事后估计的机器人的构成需要一些粒子始终包括一个粒子的盆地吸引力的真实姿势。此外，该算法需要后传播匹配误差沿循环回路关闭，时间复杂度随环的长度而增加。该Fast SLAM算法不需要明确的闭环算法。该算法采用标志选择和识别的复杂度来缓解在数据关联方面 的一些挑战。此外，Fast SLAM算法需要大量粒子来使循环结束，尽管该算法的效率取决于较少粒子数需求量。分布式particle-slam（DP-SLAM）不需要从传感器数据中特征提取或识别。它提出了一种巧妙的数据结构来有效地存储关联到不同粒子的地图。然而，该算法的存储效率与数据检索的复杂度有关。在SLAM环境中，粒子滤波器的普及在于其保持多个假设机器人的姿态和地图的能力，从而提供一个解决通信问题的办法。在基于SLAM算法的粒子滤波器中，重复采样步骤仅选择当前粒子的一个子集，它的历史支持当前传感器测量。其余的从竞争中删除。这种重复采样策略对SLAM有以下影响。

在一个给定的时间点，如果粒子提供的分支的支持区域不包括机器人的实际位姿（这总是发生在闭环时，和/或开始任何意外打滑时），重复采样不能从执行电流测量的错误解释中挽救算法。地图中产生的不一致性，甚至单次测量错误的解释，只能通过错误的反向传播进行修改。

重复采样后，多个类似的粒子随着相关的地图而保存。它涉及到大量的内存要求。最近的一项工作，对移动机器人的定位试图解决这一问题，第一取样援引的概念，共同进化的标准蒙特卡洛定位（MCL）的方法。DPSLAM通过提出一中记忆效应的数据结构处理来第二个问题。在SLAM文献中一个相对较新的概念是遗传算法（GA）的应用。第一算法基于遗传算法，把SLAM全球优化问题去寻求机器人的最优姿势。作为一个全局优化问题搜索优化构成的机器人。该算法需要处理整个数据集在一起（批处理算法）和假设很小的误差量测程法。然而，该算法关闭一个环时复制大量积累错误的能力不明显。

本文提出一种进化算法和解决主要问题，即通信问题，闭环问题，和增量处理传感器数据。类似于基于SLAM[4][5]的粒子滤波器，该进化算法也提出了机器人的位置的不确定性。每个样品提出了一个关于客观世界的假设。利用进化原则和遗传算子处理处理这些假设。该算法的新颖性在于以下几个方面。

1）进化SLAM算法利用自然选择（适者生存）设计一个通信问题的迭代法解决方案。

2）进化SLAM算法不遵循任何明确的启发式回路关闭，而通过一个岛屿模型（IGA）遗传算法保持关于世界的多假设，自然地支持并行处理。

3）进化SLAM算法保持粒子的多样性，特别是在闭环时间点，通过变异算子（能在后代中产生有利的变异）。不像粒子滤波器的重复采样阶段，IGA执行一个精英式采样（选择，遗传算法中的术语），种群中不会出现几个个体的几个复制体。

该算法以递增的方式处理数据，即在任何时间点只有可用的传感器检测是用来产生环境的局部地图。人口规模，后代的数量，以及其他IGA的参数可以按要求调整优化算法的时间复杂度。

1.问题的定义

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

根据（2），mxt是当地的地图代从单一传感器扫描。构成文本的相应的局部地图及扩展全球地图机器翻译最小不确定是最好的估计机器人的当前位置。因此，SLAM是减少的问题，搜索机器人的位姿，接到新的传感器（激光）测量。IGA是用来评价地图的质量,最后评估出机器人定位的最优解。作为机器人的姿态是一个三维连续变量，详尽的搜索在大姿态空间。可以从里程计数据中近似得出机器人姿态。里程计的移动机器人受到错误和长时间无限制地。数学模型，试图在里程计中预测不确定性，通常在机器人中称为运动模型。在这项工作中通常分布位置不确定性模型提出的几项SLAM的研究已通过。在本文的其余部分，这一概率模型将称为运动模型。

2.岛屿模型GA（IGA）和SLAM

岛模型是实现并行遗传算法（PGAs）的有效方式。这种方法中种群被分成许多小的亚种群或岛屿。所有这些岛屿独立自主进化，尽管他们遵循基本相似的演化规则。只能在同一岛屿中进行繁殖。不同的岛屿的个体，偶尔通过迁移进行基因交流。搜索性能的免疫方面的解决方案的质量和总人数的评价来得到最好的解决方案已被证明是优于标准遗传算法的若干计算问题。然而，基因算法有助于保持种群遗传多样性，从而最大限度地减少过早收敛的可能性。每个岛屿上的种群根据选择自由的聚居在一起，但不能保证每个岛将有独特的搜索轨迹。

该算法提给第二部分中提到的SLAM问题一个巧妙的解决办法。激光测量对称环境特色，例如长走廊，可能产生明显的相似质量地图对应于几个机器人姿态。因此，搜索算法快速集聚这些解决办法，尽管他们可能都是是次优的。它有一个灾难性的影响，而测绘循环对称环境中的积累误差呈现在时间周期关闭大地图上的拓扑不一致。因此，而不是收敛到一个最佳的解决方案（标准遗传算法），该算法可以聚焦到几个适宜方案。此属性有几个收敛点是很有帮助的，而映射对称环境，特别是循环的环境。它消除了需要中保持独立的启发式回路关闭。此外，重突变（称为大变异在）有助于保持种群的多样性。

3.GLAM推荐算法IGA

一套符号将特定用于描述免疫遗传算法。岛上的种群用Pt,m(n)来表示，从第n代进化到第n+1代，下标m代表第个岛，m=1,2,3……，NI,其中，NI代表岛的总数。种群中的成员用基因变量字符串来xut,m，μ代表种群中第μ个成员，其中。μ迁移规模的大小表明一些成员在一个岛将迁移到不同的岛屿，迁徙的间隔μinterval在两个连续迁移种群后代数。一个完全连接拓扑的偏移，即迁移个体岛将被复制到每个其他岛屿。

A:染色体编码:基因型和表型

染色体是实数编码。图1显示了一个染色体基因型。映射到表型的基因型是非线性的如式（2）。只有当基因型与一个传感器测量相联系时表型才被发现。因此，染色体有类似的基因型可能有不同的表型。这些表型的每一个实际上是当地的地图（换句话说，一个传感器测量的表述）如式（4）表述。遗传算子应用于基因型虽然合适的评价是表现在表型。因此，相对于SLAM问题,最好的个体，它的基因是解决机器人的定位问题，表型是最小不确定性图给予现有的传感器测量。

F用来计算测量不确定度。在每个障碍点整合后，当地的地图，假定的电流传感器测量，概率的个人传感器测量，高斯中心零的不确定性的结果。这一假设进行为高精度传感器[ 1 ]。空间视为自由在一个传感器扫描可以被视为不在被占领的连续扫描。假设条件独立性之间的个别传感器测量的概率，计算不同障碍点相乘得到国际测量不确定度。较低的价格，更高的不确定性，反之亦然。真实世界环境的景观，虽然功能可以是相当复杂的（与一些局部极大值或全球最大值遵循深谷）SLAM的范围内。

C . 选择进化算子

1）选择：。一小部分的个体选择执行交叉的基础上虽然在一个岛。后代产生交叉维持种群的多样性而充分的外汇储备从以下限制：让我们假定，这个体包含染色体，会出现早熟收敛。突变：在免疫遗传算法，变异中起着重要作用，是保持遗传多样性的引入新的等位基因的人口。双变异算子，提出的算法是：空间变异和东方型突变。空间变异：变异的染色体在这样一种方式的后代是不同的空间位置，方向是相同的父母。定向变异：变异染色体增加多样性取向的同时保将从祖先在三维空间。一个染色体突变（无论是空间或定向突变）添加每一行对应的突变阵列。因此，与传统的遗传算法，一个以上的后代可以通过木站。我的价值观和确定确切人数的后代。只有一小部分，你的人口，允许突变。资格的染色体突变取决于其相对虽然在个别岛屿。为选择过程是跨代和精英，低-fi没有后代，如果产生变异，没有生存的机会下一代。探索能力的大大fl严重的选择εε1，2，和ψ。总之，参数的设置，可以调整改进建议的算法是：人口规模，一些岛屿镍，μ大小，μ区间，最大数量的后代算法。目前的执行情况进行定值，这些参数。有范围调整，使用智能算法，如模糊逻辑，被认为是未来的工作。

基于遗传算法和 Hilbert曲线的多机器人地图构建

机器人系统所面临的任务环境往往是未知的和非结构化的，而且有时因为危险和污染的存在，由人类进行环境探测往往不现实，因此为了完成复杂的任务，需要由机器人首先进行地图构建。与单机器人相比，采用多机器人进行地图构建既可以减少地图构建的时间，又可以利用多个机器人之间相对定位技术和信息融合技术增加地图构建的精确度。本文将遗传算法应用于地图构建过程中，多机器人之间探索区域的动态分配，减少了机器人之间的相互碰撞机会;同时将Hilbert曲线应用于固定区域的未知环境探测，减少了机器人重复探测相同区域的可能，提高了机器人的地图构建效率。

1.基于遗传算法的动态分区算法

本文对遗传算法进行了研究，设计了一个基于遗传算法的动态分区算法，并将该算法应用于多机器人地图构建的任务中。

以三个机器人为例，遗传算法在多机器人静态环境地图构建中的应用的具体方法为:

(1)将整个探测区域分成8x8共64个子方格，每个子方格的大小为64 x 64像素，以方格的行数和列数作为遗传算法的每条染色体中的一个参数，三个机器人的行数和列数共6个参数构成一条染色体，如073425代表第一个机器人的目标是第0行第7列、第二个机器人的目标是第3行第4列、以次类推。定义一个结构体Individual作为遗传算法计算的载体，每个结构体包含一个一维数组ch和一个整形变量fitness，分别代表一条染色体的编码和适应度。

(2)建立一个二维数组pass 来记录每一次三个机器人走过的点，在设定机器人初始位置之后，该位置会存入数组pass的前三个，如pass和pass代表第一个走过的格子的行数和列数。以后每进行一次遗传算法的规划，就将结果顺序存入这个数组中。

(3)适应度函数。设当前机器人所在的行数和列数为(t0,t51)，(t2,t3 )，(t4,t5 )，适应度函数应满足以下条件:

a)三个机器人当前点和下一个目标点之间的距离最短。取式3-1形式的函数来计算当前点和下一个目标点的距离，最终取这个函数的最小值。

(4)随机产生20条染色体作为第一代种群，每条染色体的编码都随机产生，并用每一条染色体的编码计算它的适应度，然后用冒泡算法将种群按适应度的大小进行排序，将适应度最高的四条染色体保留到下一代。

(5)交叉、变异。将排序后的第4到第19条染色体中相邻的两条中的某个编码进行交换，交换的概率为0.1，即完成交叉操作;将这16条染色体中每一位都以0.1的概率被其他的随机数代替，即完成变异操作。操作完成后，重新适应度排序。

(6)排序后用20条染色体的编码依次查询pass数组，如果某条染色体的某对值与pass数组中的相同，代表该点己走过，这条染色体被放弃，下面的染色体依次上调一个位置。

(7)用上一代计算后的染色体重新进行(5) , (6)操作，经过100代以后，选择留下的适应度最高的染色体的编码作为三个机器人下一个目标方格，机器人再对这个方格进行探测。以次类推，直至整个画面的方格被探测完毕。

图3-1为遗传算法的计算过程，圆、三角形和正方形分别代表三个不同的机器人，每一步与上一步用线连接，图右边的两列数字分别代表20条染色体和每条染色体对应的适应度，左上角的红色交叉线代表初始设置好的己走过的方格，机器人的初始位置可以通过菜单任意设置。这个基于遗传算法的区域动态分配的方法可以应用在不同数目的机器人系统中，有一定的通用性。

图3-2为遗传算法采用不同算子时的计算结果分析。实验归纳出当只做变异操作时，算法容易发生局部收敛现象，而这条染色体不是最理想的染色体;当只有交叉操作时，算法容易提前收敛到一条染色体而大大降低了其他更好的染色体出现的可能;而交叉和变异同时操作的时候结果比较理想，结果即不会提前收敛也不会局部收敛。

用遗传算法程序和随机选择的程序进行了对比，结果显示经过遗传算法规划以后，探测相同区域和机器人相互碰撞的几率几乎为零。图3-3 a)表示了经过遗传算法规划的地图构建过程，图3-3 b)代表随机选择子方格的构建过程，圆形和矩形相重叠的部分代表重复探测的区域图a)中应用遗传算法规划后的子方格有相互远离的趋势，这样对下一步子方格的选取和整个区域的构建时间上都有积极的作用;从图3-3中可以看出遗传算法进行规划后的地图构建没有重复的地区，而采用随机选择办法的地图构建存在重复的区域。

2.子区域内基于Hilbert曲线的地图构建算法的研究

Hilbert曲线源于经典的Peano曲线族。Peano曲线族是闭合间隔单元I={0,1}到闭合矩形单元S={0,1 }的连续映射，也是所有能够填满二维或更高维空间的连续分形曲线的总称，故又称为空间填充曲线，它是由意大利数学家Peano于1890年提出。德国数学家Hilbert于1891年首先给出了构造这种空间填充曲线的几何过程，并提出了所构造的空间填充曲线“处处连续，但处处不可导”的著名假设。Hilbert曲线己有广泛的应用，例如在图像存储和检索、空间数据库索引等领域得到了成功的应用。因此研究Hilbert曲线有重要的理论意义和应用价值。

在未知环境的探测过程中，各个机器人的搜索路径、搜索方式对于保证未知环境地图完整、快速地创建非常重要。借助一定的探测策略，机器人将局部信息累积扩展，直至环境地图构建完成。在机器人探测环境方面，一种直观的探测策略是让机器人走“Z”字形，通过“地毯式”的搜索实现环境区域的遍历。本文将Hilbert曲线应用在子区域的探测上。

如图3-4所示，a)为机器人在1个子方格内的探索路线，是由4条Hilbert曲线首尾相接组成的。右图显示机器人在子方格内遇到障碍物时的情况。机器人从方格的左上角的is点出发，按Hilbert曲线的路径进行探索，配合机器人本身可以探测的半径，就可以不重复的探测方格内的点。如图b)所示当机器人遇到障碍物的时候会自动启动单方向沿边缘走的行为，并记住发现障碍物时候的位置，当机器人绕着障碍运行一周回到记下的点时退出绕障行为，自动进入下一个Hilbert曲线的运行过程。为了避免其他机器人也对相同的障碍物进行围绕，在机器人绕障的每一步都会留下信息素，即改变当前点在地图Map中的值以标记走过的点，这样释放信息素的行为就可以通过改变当前地图值的办法来实现，在is到4e的8个点中如果某个或某几个点被障碍物挡住的话，机器人在运行90步以后会自动奔向下一个点，最终完成整个区域的探索。

免责声明：本文系网络转载，版权归原作者所有。如涉及版权，请联系删除！