《智能机器人创新设计》 课件 第9-14章 单机器人路径规划 -智能算法综合比较

第9章单机器人路径规划智慧物流系统：从设计到实现教学内容CONTENTS3启发式搜索2盲目式搜索4广度优先搜索算法5深度优先搜索算法6A*搜索算法1路径规划3

章节目标了解路径规划的定义和分类；了解单机器人路径规划的两大搜索方式；掌握三种搜索算法的原理和搜索方式。41路径规划单机器人路径规划路径规划：依据某种原则，在工作空间中找到一条从起始点到目标点且能避开障碍物的最优路径称为路径规划。将连接起点位置和终点位置的序列点或曲线称之为路径，路径规划也就是构成路径的策略。路径规划是运动规划的主要研究内容之一。51路径规划静态路径规划和动态路径规划在机器人工作的环境中，遇到的障碍物分为静态障碍物与动态障碍物。针对环境中的障碍物可将路径规划分为静态路径规划和动态路径规划。①静态路径规划是指机器人在有静态障碍物的工作环境中寻找一条从起点到目标点的运动路径，使机器人在运动过程中能够安全无碰撞地绕过所有障碍物。②动态路径规划是指机器人在有动态障碍物的环境中先寻找一条恰当的从起点到目标点的运动路径，然后在运动的过程中发现动态障碍物后，实时更新当前位置到目标点的路径。61路径规划移动机器人路径规划假设B为一机器人系统，并假设B在一个空间V中，有一组该机器人系统已知的障碍物，机器人可以进行无碰撞运动。那对于机器人B的路径规划为：在空间V中，给B一个初始位姿Z1、一个目标位姿Z2和一组已知的障碍物，寻找一条从Z1到Z2的连续的避碰最优路径，如果该路径存在，那么就规划出一条这样的路径。空间V初始位姿Z1目标位姿Z2障碍物71路径规划移动机器人路径规划主要解决三个问题：

①机器人从初始点运动到目标点。②通过算法规划路径，使机器人绕开障碍物并且经过某些必须经过的坐标点。使用算法规划机器人路径的时候，算法先去搜索地图，然后回溯搜索过的路径，找到目标点到起点较优的路径。③在完成以上任务的前提下尽量优化机器人运行轨迹。空间V初始位姿Z1目标位姿Z2障碍物8盲目式搜索与启发式搜索：机器人在未知区域探索时需要采用一定的搜索策略对其路径选择进行指导，在搜索的同时对当前区域进行地图建模，建立距离等高图，由此可以获得任意两点间的最短路径。根据搜索时是否依靠信息可以将搜索分为盲目式搜索和启发式搜索两种搜索方式。1路径规划92盲目式搜索盲目式搜索：盲目式搜索又叫无信息搜索，在搜索过程中按照预定的控制策略进行搜索，途中获得的路径信息不用来改变控制策略。常用算法主要包括广度优先搜索算法（BFS）和深度优先搜索算法（DFS）。这两种搜索算法在搜索时都按规定路线进行，不使用与问题相关的启发性信息，适用于其状态空间图是树状结构一类的简单问题。盲目式搜索会导致搜索效率低，会在计算时耗费过多的空间与时间。103启发式搜索启发式搜索：启发式搜索就是在搜索中键入启发性信息，用来指导搜索过程朝着最有希望的方向前进。启发性信息就是在搜索过程中获取到的控制前进方向的信息，其用途可分为三种：①用于确定要扩展的下一节点的位置，以免盲目地去扩展；②在扩展下一节点的过程中，用于决定要生成哪一个节点或哪几个后继节点，以免盲目地同时生成所有可能的节点；③用于确定某些应该从搜索树中抛弃或修剪的节点。主要的搜索算法为A*搜索算法。114广度优先搜索算法广度优先搜索算法：广度优先搜索算法（BreadthFirstSearch，BFS）目的是系统地展开并检查图中的所有节点，以找寻结果。该算法并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。1.算法原理依次从根节点开始，逐层对节点进行扩展并考察该节点能否成为目标节点，在第n层的节点没有全部扩展并考察结束之前，不扩展第n+1层的节点。树状结构的广度优先算法图124广度优先搜索算法广度优先搜索算法：1.算法原理广度优先算法一般是依靠先进先出的队列或堆栈实现，将相邻且未被搜索的节点放置在open容器中（队列或者一维列表），被搜索过的节点放置在close容器中，通常称之为open-close表。具体的搜索规则如下：①从根节点开始，先将根节点压入open队列中，如图所示：从根节点开始134广度优先搜索算法广度优先搜索算法：1.算法原理②访问根节点相邻的所有节点（A1、A2），并把相邻的所有节点压入open队列中，将根节点从open表中删除并将根节点压入到close堆栈中，操作过程如图所示。从A1节点开始144广度优先搜索算法广度优先搜索算法：1.算法原理③将open队列中当前的队首节点作为新的节点，开始搜索与其相邻的节点，重复上一步操作，操作过程如图所示。从A2节点开始154广度优先搜索算法广度优先搜索算法：从B1节点开始从B2节点开始164广度优先搜索算法广度优先搜索算法：从C2节点开始从C1节点开始174广度优先搜索算法广度优先搜索算法：1.算法原理④直到所有节点全部搜索完毕，open队列中没有节点，结束搜索，如图所示。全部压入close堆栈中184广度优先搜索算法广度优先搜索算法：2.算法实例将树状图映在地图上，以4×*4尺寸的地图环境为例，演示BFS算法的逐步搜索过程。假设机器人存在多个前进方向时的优先顺序为：上>右>下>左（绝对方向），在该例子中定义open表为一个队列，close表为一个堆栈。或者用0和1两种状态分别表示该坐标在open表或close表中，所有坐标的标志位事先初始化为0，表示未访问过或存在未访问相邻坐标。194广度优先搜索算法广度优先搜索算法：2.算法实例机器人每向前移动一步记录机器人的移动步数，每当机器人出现转向时，机器人的移动步数增加0.5，机器人的初始化与队列的初始化如图1所示。广度优先搜索示例示意图1204广度优先搜索算法广度优先搜索算法：2.算法实例第1步，先将起始坐标(0,0)加入open表；访问起始坐标，检测出当前坐标(0,0)有不在close表中的相邻坐标(0,1),将(0,1)加入open表，如图2所示。广度优先搜索示例示意图2214广度优先搜索算法广度优先搜索算法：2.算法实例第2步，机器人向前移动一步，记录移动步数；将open表首位(0,0)压入close表；访问新open表首位坐标(0,1),检测出当前坐标(0,1)有不在close表中的相邻坐标(0,2)和(1,1),将(0,2)和(1,1)加入open表，如图3所示。广度优先搜索示例示意图3224广度优先搜索算法广度优先搜索算法：2.算法实例第3步，先搜索第一个节点，记录机器人移动步数；将open表首位(0,1)压入close表；访问新open表首位坐标(0,2),检测出当前坐标(0,2)有不在close表中的相邻坐标(0,3),将(0,3)加入open表，如图4所示。广度优先搜索示例示意图4234广度优先搜索算法广度优先搜索算法：2.算法实例第4步，继续搜索第二个移动节点，并记录移动步数，同时添加转向数值；将open表首位(0,2)压入close表；访问新open表首位坐标(1,1),检测出当前坐标(1,1)有不在close表中的相邻坐标(2,1),将(2,1)加入open表，如图5所示。广度优先搜索示例示意图5244广度优先搜索算法广度优先搜索算法：2.算法实例后续第5-10步同理第2-4步，如图6到11不断重复第2-4步之间的搜索操作。图6图7254广度优先搜索算法广度优先搜索算法：图8图9264广度优先搜索算法广度优先搜索算法：图10图11274广度优先搜索算法广度优先搜索算法：2.算法实例第11步：搜索终点坐标(3,3)，可以停止搜索。最终根据起点到终点移动数值，从终点到起点开始反推出最短路径。搜索过程与搜索结果如图12与13所示。图12284广度优先搜索算法广度优先搜索算法：2.算法实例从终点到起点根据数值反推：8→6.5→5→3.5→2.5→1最终，从起点到终点的最短路径坐标顺序为：（0,0）→（0,1）→（1,1）→（2,1）→（2,2）→（3,2）→（3,3）图13广度优先搜索示例结果295深度优先搜索算法深度优先搜索算法：深度优先搜索算法（DepthFirstSearch，DFS）是与广度优先搜索算法具有同等地位的另一种盲目搜索算法。“一条路走到黑“，更适合机器人对于未知领域的探索任务。1.算法原理在一条路上一直走下去，如果遇到分岔路口，就任意选择其中一条继续走下去，如果走到头，就返回到上一个分岔路口走另外一条路，然后再一直走下去，直到搜索完全地图后就停止搜索。深度优先搜索算法示意图30深度优先搜索算法：1.算法原理深度优先搜索算法用到计算机程序中的递归思想，搜索规则如下：（1）访问指定的根节点A，发现有三条分支路线，如图所示。5深度优先搜索算法从根节点开始访问31深度优先搜索算法：1.算法原理（2）随机选择一个节点（B1）访问，发现有两条分支线路，如图所示。5深度优先搜索算法随机选择一个支路节点进行访问32深度优先搜索算法：1.算法原理（3）随机选择一个节点（C1）访问，发现有一条线路，继续访问节点（C2），发现没有路线。5深度优先搜索算法将支线走到头33深度优先搜索算法：1.算法原理（4）返回最近的有分支线路的节点（B1）继续访问另外一条线路的节点（C3）5深度优先搜索算法返回最近的多直线节点悬着的另外一条线路34深度优先搜索算法：1.算法原理（5）当该路线访问完毕，没有分支线路，重复上一步，直到与根节点相通的全部节点都访问完毕，结束搜索。这一重复搜索过程如下图即可完成所有路线的搜索任务。5深度优先搜索算法B1已经没有未访问的支线了，返回A任选一条未访问的节点35深度优先搜索算法：5深度优先搜索算法随机选择一个支路节点D1进行访问，并访问到头随机选择一个支线节点B2进行访问36深度优先搜索算法：5深度优先搜索算法返回根节点并选择另一条未访问的支线节点B3进行访问返回最近的还有未访问支线的节点并选择另一条支线访问37深度优先搜索算法：5深度优先搜索算法返回最近的还有未访问支线的节点并选择另一条支线访问随机选择一条支线节点E1进行访问38深度优先搜索算法：2.算法实例同样映射到一个4×4尺寸的地图环境中，演示DFS算法的逐步行进过程。假设机器人存在多个前进方向时的优先顺序为：右>上>左>下（绝对方向），用0和1分别表示坐标是否返回节点，所有坐标的标志位事先初始化为0，表示未访问过或存在未访问相邻坐标，初始化状态如图所示。从根节点开始访问，发现有一个相邻的节点5深度优先搜索算法39深度优先搜索算法：2.算法实例第1步，将(0,0)作为根节点，机器人从(0,0)开始访问，发现有相邻的节点(0,1)，将相邻节点(0,1)添加到子节点中，如图所示访问相邻的子节点，发现两个相邻的子节点5深度优先搜索算法40深度优先搜索算法：2.算法实例第2步，机器人向前移动，访问坐标节点(0,1)，发现有两个相邻的节点(0,2)和(1,1)，将(0,2)和(1,1)添加到(0,1)子节点中，如图所示。根据绝对方向优先顺序选择子节点，发现两个相邻子节点5深度优先搜索算法41深度优先搜索算法：2.算法实例第3步，依照方向的优先顺序，机器人转弯向右移动，访问坐标节点(1,1)，发现有两个相邻的节点(1,2)和(2,1)，将(1,2)和(2,1)添加到(1,1)的子节点中，如图所示。依照优先顺序访问子节点，发现一个相邻的子节点5深度优先搜索算法42深度优先搜索算法：2.算法实例第4步，依照方向的优先顺序，机器人继续向右移动，访问坐标节点(2,1)，发现有一个相邻的节点(2,0),将(2,0)添加到(2,1)的子节点中，如图所示。访问子节点，发现有一个未访问的相邻节点5深度优先搜索算法43深度优先搜索算法：2.算法实例第5步，机器人转弯向右移动，访问坐标节点(2,0)，发现有一个相邻的节点(3,0)，将(3,0)添加到(2,0)的子节点中，如图所示。访问子节点，发现没有未访问的子节点，标记位置5深度优先搜索算法44深度优先搜索算法：2.算法实例第6步，机器人转弯向右移动，访问坐标节点(3,0)，未发现相邻的坐标节点，标记位置，如图所示。返回上一坐标节点(2,0)未发现相邻节点，标记位置5深度优先搜索算法45深度优先搜索算法：2.算法实例第7步，机器人掉头向左移动，返回上一坐标节点(2,0)，未发现未访问的相邻坐标节点，标记位置，如图所示。返回上一节点(2,1)，发现没有未访问的子节点，标记位置5深度优先搜索算法46深度优先搜索算法：2.算法实例第8步，机器人转弯向上移动，返回上一坐标节点(2,1)，未发现未访问的相邻坐标节点，标记位置，如图所示。返回上一节点(1,1)，发现有未访问的子节点5深度优先搜索算法47深度优先搜索算法：2.算法实例第9步，机器人转弯向左移动，返回上一坐标节点(1,1)，还有一个相邻坐标节点未访问，不做操作，如图所示。选择未访问的相邻子节点，发现有两个相邻子节点5深度优先搜索算法48深度优先搜索算法：2.算法实例第10步，机器人转弯向上移动，访问坐标节点(1,2)，发现有两个相邻的坐标节点(1,3)和(0,2)，将(1,3)和(0,2)添加到(1,2)的子节点中，如图所示。任意选择一个相邻子节点进行访问，发现两个相邻子节点5深度优先搜索算法49深度优先搜索算法：2.算法实例第11步，依照方向的优先顺序，机器人向上移动，访问坐标节点(1,3)，发现有两个相邻的坐标节点(0,3)和(2,3),将(0,3)和(2,3)添加到(1,3)的子节点中，如图所示。访问相邻子节点，发现两个相邻子节点5深度优先搜索算法50深度优先搜索算法：2.算法实例第12步，依照方向的优先顺序，机器人转弯向右移动，访问坐标节点(2,3)，发现有一个相邻的坐标节点(3,3),将(3,3)添加到(2,3)的子节点中，如图所示。访问子节点，发现一个相邻子节点，标记终点位置5深度优先搜索算法51深度优先搜索算法：2.算法实例第13步，机器人继续向右移动，访问坐标节点(3,3)，找到终点，标记位置；若只是为了求取一条起点到终点的可行路径，程序到此就结束了。从终点开始反向记录机器人的移动步数，直到到达起点的位置，就会得出一条从终点到起点的路径，求解起点到终点的可行性路线如图所示。5深度优先搜索算法52深度优先搜索算法：2.算法实例从(3,3)开始找其上一节点直至根节点(0,0)，可以得到一个可行解：(3,3)→(2,3)→(1,3)→(1,2)→(1,1)→(0,1)→(0,0)5深度优先搜索算法53深度优先搜索算法：2.算法实例但如果要搜索全图确定全局最优解，程序需要继续执行：坐标(3,3)有未访问过的相邻坐标，将(3,2)添加到(3,3)的子节点中，如图所示。访问终点(3,3)，发现有一个相邻坐标5深度优先搜索算法54深度优先搜索算法：2.算法实例后续若干步骤同理第6-10步的过程，最后所有可行的节点都被访问，标志位都被置1，机器人也正好返回起点(0,0)，全图搜索完成。针对全图其余节点的搜索过程如教材配图9-50到9-62所示，按顺序方式阅读教材P107即可查看深度优先搜索算法的搜索路径。5深度优先搜索算法556A*搜索算法A*搜索算法：深度优先算法可以快速搜索到一条能到达目的地的路径，但是无法保证得到的这一条路径是最短路径；广度优先算法可以保证搜索到一条最短路径但搜索所用到的时间会比较长。A*(A-star)算法结合了二者优点的算法，是静态网路求解最短路径最有效的直接搜索算法。可以说DFS是A*算法效率最低的一个特例，BFS是依次展开每一层坐标（或者说是等高图中同一数值的坐标）进行搜索。如果对于每层坐标只选定一个方向去搜索它的下一层坐标，而非依次搜索所有可到达的下一层坐标的话，就可以大大节省计算时间。A*算法也是许多其他问题的常用启发式算法。566A*搜索算法A*搜索算法：1.算法原理A*算法给出了一种估值函数，给每个坐标附上一个估值函数，用于下一步被访问坐标的价值。估值函数为：F(n)=G(n)+H(n)G(n)表示从起始点坐标到节点坐标的距离；H(n)表示从该节点坐标到终点坐标的曼哈顿距离；F(n)表示从起始点坐标经由节点坐标到终点坐标的最小代价估计；无论地图信息未知还是已知，终点坐标我们总是可以确定的，由此可以采取多种方法来拟定估计值H(n)，如采用曼哈顿距离（城市街区距离）、对角线距离、欧几里得距离、平方后欧式距离等，这里不做详细介绍。总得来说，就是利用终点坐标和当前坐标的差距拟合出终点距离当前点的偏好方向。572.算法实例第一步，当机器人位于坐标（0，0）时，计算起点坐标的估计值：将该坐标距离起点的距离记为G_((0,0))=1，计算起点(0,0)与终点（4，4）的曼哈顿距离为H_((0,0))=|0-4|+|0-4|=8，则其估值函数：F_((0,0))=G_((0,0))+H_((0,0))=96A*搜索算法A*搜索算法：582.算法实例第二步，可移动的方向仅有绝对向上的方向（以下描述均为绝对方向），机器人向上移动一步，G(0,1)=G(0,0)+1,计算节点(0,1)与终点（4，4）的曼哈顿距离为H_((0,1))=|0-4|+|1-4|=7，估值函数：6A*搜索算法A*搜索算法：F_((0,1))=G_((0,1))+H_((0,1))=(G_((0,0))+1)+(4+3)=9592.算法实例第三步，可移动的方向仅有绝对向上的方向（以下描述均为绝对方向），机器人向上移动一步，G(0,2)=G(0,1)+1,计算节点(0,2)与终点（4，4）的曼哈顿距离为H_((0,2))=|0-4|+|2-4|=6，估值函数：6A*搜索算法A*搜索算法：F_((0,2))=G_((0,2))+H_((0,2))=(G_((0,1))+1)+(4+2)=9602.算法实例第四步，可移动的方向仅有绝对向右的方向（以下描述均为绝对方向），机器人向右移动一步，G(1,2)=G(0,2)+1,计算节点(1,2)与终点（4，4）的曼哈顿距离为H_((1,2))=|1-4|+|2-4|=5，估值函数：6A*搜索算法A*搜索算法：F_((1,2))=G_((1,2))+H_((1,2))=(G_((0,2))+1)+(3+2)=9612.算法实例第五步，可移动方向有上和右两个方向，分别是（1,3）和（2,2），需要同时计算坐标(1,3)和(2,2)的估值函数：①机器人向右移动一步，G(2,2)=G(1,2)+1,计算节点(2,2)与终点（4，4）的曼哈顿距离为H_((2,2))=|2-4|+|2-4|=4，估值函数：F_((2,2))=G_((2,2))+H_((2,2))=(G_((1,2))+1)+(2+2)=9②机器人先转弯然后向上移动一步，G(1,3)=G(1,2)+1,计算节点(1,3)与终点（4，4）的曼哈顿距离为H_((1,3))=|1-4|+|3-4|=4，估值函数：F_((1,3))=G_((1,3))+H_((1,3))=(G_((10,2))+1)+(3+1)=96A*搜索算法A*搜索算法：626A*搜索算法A*搜索算法：F_((2,2))=G_((2,2))+H_((2,2))=(G_((1,2))+1)+(2+2)=9F_((1,3))=G_((1,3))+H_((1,3))=(G_((10,2))+1)+(3+1)=9632.算法实例在实际应用时可以引入转弯参数t，使得:H_((n))=终点与当前位置的曼哈顿距离+t_((n))由于向上移动需要先转弯再移动，所以需要增加转向t，假设转向权值为0.3重新计算坐标(1,3)的估值函数。6A*搜索算法A*搜索算法：642.算法实例机器人先转弯然后向上移动一步，G(1,3)=G(1,2)+1,计算节点与终点（4，4）的曼哈顿距离为H_((1,3))=|1-4|+|3-4|=4，估值函数：F_((1,3))=G_((1,3))+H_((1,3))+t_((1,3))=(G_1,2+1)+(3+1)+0.3=9.3因为F_((1,3))>F_((2,2))，即向上走比向右走要付出更大的代价，所以机器人优先选择向右走。6A*搜索算法A*搜索算法：652.算法实例第六步，机器人向右移动一步，现有向上和向下两个方向可移动，需要计算坐标(2,3)和(2,1)的估值函数。①机器人转弯向上移动一步，移动到(2,3)，G(2,3)=G(2,2)+1；计算(2,3)与终点(4,4)的曼哈顿距离H_((2,3))=2+1=3；则估值函数：F_((2,3))=G_((2,3))+H_((2,3))+t_((2,3))=(G_((2,2))+1)+3+0.3=9.3②机器人转弯向下移动一步，移动到(2,1)，G(2,1)=G(2,2)+1；计算(2,1)与终点(4,4)的曼哈顿距离H_((2,1))=2+3=5；则估值函数：F_((2,1))=G_((2,1))+H_((2,1))+t_((2,1))=(G_((2,2))+1)+(2+3)+0.3=11.36A*搜索算法A*搜索算法：666A*搜索算法F_((2,1))=G_((2,1))+H_((2,1))+t_((2,1))=(G_((2,2))+1)+(2+3)+0.3=11.3F_((2,3))=G_((2,3))+H_((2,3))+t_((2,3))=(G_((2,2))+1)+3+0.3=9.3672.算法实例第七步，继续计算未访问节点的估值函数。机器人优先向上移动一步，现有向上和向右两个方向可移动，需要计算坐标(2,4)和(3,3)的估值函数。：①机器人继续向上移动一步，G(2,4)=G(2,3)+1；计算(2,4)与终点(4,4)的曼哈顿距离H_((2,4))=2+0=2；则估值函数：F_((2,4))=G_((2,4))+H_((2,4))=(G_((2,3))+1)+2=9②机器人转弯向右移动一步，G(3,3)=G(2,3)+1；计算(3,3)与终点(4,4)的曼哈顿距离H_((3,3))=1+1=2，则估值函数：F_((3,3))=G_((3,3))+H_((3,3))+t_((3,3))=(G_((2,3))+1)+2+0.3=9.36A*搜索算法A*搜索算法：686A*搜索算法F_((3,3))=G_((3,3))+H_((3,3))+t_((3,3))=(G_((2,3))+1)+2+0.3=9.3F_((2,4))=G_((2,4))+H_((2,4))=(G_((2,3))+1)+2=9692.算法实例第八步，机器人优先向上移动一步，发现去终点方向的道路有障碍物，无法通过，因此机器人回到之前的位置，向右移动一步，需要计算坐标(4,3)的估值函数。机器人继续向右移动一步，G(4,3)=G(3,3)+1；计算(4,3)与终点(4,4)的曼哈顿距离H_((4,3))=0+1=1；则估值函数：6A*搜索算法A*搜索算法：F_((4,3))=G_((4,3))+H_((4,3))=(G_((3,3))+1)+1=9702.算法实例第九步，有向上和向下两个方向可移动，机器人向上移动一步，到达终点；根据计算出来的每个坐标的估值函数，从终点开始进行回溯，找到最短路径：6A*搜索算法A*搜索算法：(4,4)→(4,3)→(3,3)→(2,3)→(2,2)→(1,2)→(0,2)→(0,1)→(0,0)欢迎探讨！第10章多机器人路径规划智慧物流系统：从设计到实现教学内容CONTENTS3应用场景2多机器人路径规划问题4常见冲突5解决策略6D*算法1多机器人路径规划7协同调度74

章节目标了解如何为多个机器人规划路径；了解多条路径可能会出现冲突和解决冲突的策略；掌握给多个机器人进行路径规划的算法原理。75多机器人路径规划

多机器人路径规划，顾名思义，就是给多个机器人规划从起点到终点的最优的、无碰撞障碍物的多条路径。1多机器人路径规划单机器人路径规划多机器人路径规划76多机器人路径规划在同一工作环境下，存在着同一时间多个同时作业的移动机器人，并且要保证机器人彼此之间在任意时刻都保持安全距离，不发生碰撞。在以机器人与工作环境中障碍物不发生碰撞的要求条件下，需要各机器人在起点与终点之间合理规划出每个机器人的最优无碰撞的安全路径。2多机器人路径规划问题772多机器人路径规划问题多机器人路径规划主要涉及四个方面：

环境建模、碰撞检测、启发式规则设计、路径规划算法(1)环境建模：将移动机器人的工作环境通过一定的数据结构传到计算机上，并将环境信息准确地呈现出来。(2)碰撞检测：指判断机器人与环境中的障碍物或两机器人间是否会发生碰撞以及确定碰撞发生时机器人所处的位置。(3)启发式规则：指如何更好地消解移动机器人间的碰撞冲突，实现多移动机器人协同作业。(4)路径规划算法：指如何在当前工作环境中依据路径规划的相应要求快速地为移动机器人寻找到可避碰避障的最优或较优的可行路径。783应用场景多机器人路径规划：假设多个机器人在二维平面环境G中运行，环境中存在着若干静态障碍物，障碍物位置信息已知。机器人R1和R2的起点位置S1和S2和目标点E1和E2已知。多机器人路径规划时，会在不考虑其他机器人的基础上，先规划一条Ri从起点Si到终点Ei之间的无碰障碍的最优路径，然后在机器人的行进过程中再去考虑机器人的碰撞冲突问题。!!!!!!0123401234S1S2E1E2794常见冲突常见的碰撞冲突：多机器人系统不仅是机器人的数量增多，且各机器人都有自己的目标点，在按原始路径运行时极易发生碰撞冲突。在该情形下，路径规划不仅要考虑到避障问题还要考虑到机器人间的避碰问题。多机器人在运行时常见的几种冲突：(1)在地图环境G中，假设机器人R1和机器人R2在t时刻和t+1时刻的路径点重合，就会出现两台物流机器人面对面发生碰撞的现象；01230123R2R180常见的碰撞冲突：(2)在地图环境G中，假设机器人R1、R2在t时刻的路径点重合，就会发生碰撞，碰撞情况有两种情况：01230123R2R1情况一01230123R2情况二R1!!4常见冲突81常见的碰撞冲突：(3)在地图环境G中，机器人R1、R2在进入槽位时，路径点重合,面对面相遇会发生碰撞：01230123R1R2!!!4常见冲突825解决策略常见碰撞冲突的解决策略：明确机器人之间的优先级，优先级高的机器人按照原路径前进，优先级低的机器人重新规划路径。假设机器人R1优先级高于机器人R2的优先级。01230123R2R1(1)t时刻、t+1时刻路径点重合解决策略：根据机器人的优先级进行判断，让机器人R1在原地等待并按照原路径前进，给机器人R2重新规划前进路线(实际位置到目标点)83常见碰撞冲突的解决策略：(1)根据机器人的优先级进行判断，让机器人R1在原地等待并按照原路径前进，给机器人R2重新规划前进路线(实际位置到目标点位置)01230123R2R101230123R2R1R25解决策略84常见碰撞冲突的解决策略：(2)情况一：两个机器人直角相遇，这时如果利用物流机器人的优先级来控制机器人移动可能会发生剐蹭、碰撞。因此，需要通过两个机器人的位移来决定哪个机器人需要重新规划路线，距离重合点越远的机器人重新规划路线。01230123R2R1根据机器人的位移距离进行判断，机器人R1重新规划路线（实际位置到目标点），机器人R2等待并按照原路线前进。5解决策略85常见碰撞冲突的解决策略：(2)情况一：根据机器人的位移距离进行判断，机器人R1重新规划路线（实际位置到目标点），机器人R2等待并按照原路线前进。01230123R2R101230123R2R1R15解决策略86常见碰撞冲突的解决策略：(2)情况二：当机器人R2只能前进时与机器人R1的路径点重合，按照优先级控制机器人移动，由于机器人R2只能前进，无法规划出其他路线，只能由机器人R1重新规划路径。根据机器人的前进方向进行判断，机器人R1重新规划路线（实际位置到目标点），机器人R2等待并按照原路线前进。01230123R2R1!!5解决策略87常见碰撞冲突的解决策略：(2)情况二：根据机器人的前进方向进行判断，机器人R1重新规划路线（实际位置到目标点），机器人R2等待并按照原路线前进。01230123R2R1!!01230123R2R1!!R15解决策略88常见碰撞冲突的解决策略：(3)当机器人R1、R2进入槽位时，只能从前方进入，两个机器人面对面相遇，同样要是用优先级来控制机器人移动根据机器人的优先级进行判断，机器人R1等待并按照原来路径前进，让机器人R2重新规划路线(实际位置到目标点)。01230123R1R2!!!5解决策略89常见碰撞冲突的解决策略：(3)根据机器人的优先级进行判断，机器人R1等待并按照原来路径前进，让机器人R2重新规划路线(实际位置到目标点)。01230123R1R2!!!01230123R1R2!!!R25解决策略906动态路径规划利用上述的这些策略，可以有效的避免机器人之间的碰撞，但是使用这些策略，需要考虑很多种情况，且需要一一的列举出来，然后再进行解决。这样思考：在一个环境模型中，有多个可移动的机器人，在机器人在移动过程中，把突然出现的机器人作为移动的障碍，这样我们便可以给该机器人重新规划路径或者等待移动障碍离开原路径继续移动。在环境模型中出现可移动障碍时，给规划路径就要使用动态路径规划，动态路径规划的算法是D*算法。916动态路径规划926动态路径规划算法-D*算法D*(D-star)算法：

D*（D-Star,DynamicAStar）算法是典型的动态网路求解最短路径算法，用于计算一个节点到其他所有节点的最短路径，也是给多机器人动态规划路径的算法，当遇到其他机器人时，会将其他机器人当做障碍物，重新规划路径。主要特点是一起点为中心向外层层扩展，直到扩展到终点位置。D*算法的本质就是A*算法，能得出最短路径的最优解。93D*(D-star)算法原理：首先，在不考虑移动障碍的情况下，使用A*算法给每个机器人规划出一条起点距离终点的最优路径；其次，获取机器人某时刻移动障碍物(其他机器人)的位置，与已经规划好的路径进行碰撞监测；

①如果不发生冲突时，机器人正常在最优路径上移动；

②如果发生冲突时，其中一台机器人将另外一台机器人设置为障碍；

当i步发现冲突，将i,i+1步设置为障碍，从i-1步重新规划当前坐标到终点的最优路径；(3)从i-1步重新规划后，将起点到i-1步的路径点和i-1步到终点的路径点拼接，

得到从起点到终点避碰移动障碍物的最优路径；6动态路径规划算法-D*算法94D*算法

01230123终点以4*4的地图环境为例，规划出两个机器人R1、R2从起点到终点的路径，假设机器人R1的优先级高于机器人R2的优先级，演示D*算法的过程：终点R1R2(1)先在不考虑其他机器人的情况下，使用A*算法规划从起点到终点的最短路径6动态路径规划算法-D*算法01230123终点终点R1R295D*算法

(2)其次，获取机器人某时刻移动障碍物(其他机器人)的位置，与已经规划好的路径进行碰撞检测。12345124在i时刻(第二步)会发生碰撞，机器人R1的优先级高于机器人R2，由机器人R2在i-1时刻(第一步)重新使用A*算法规划路径36动态路径规划算法-D*算法01230123终点终点R1R2966D*算法-算法实例D*算法

(3)机器人R2在i-1时刻(第一步)重新规划路径机器人R1按照最初的路径执行机器人R2最终路径：起点~i-1+i-1~终点拼接路径就会多一步i-1,拼接的路径需要减去一个i-1步的路径点977协同调度协同调度：多机器人系统在各个领域已经有了广泛的应用。随着移动机器人数量和机器人任务的增加，怎样合理的调度机器人工作，避免发生碰撞和闲置，对提高机器人人的利用率具有重要意义。协同调度是一种为了最大化利用机器人完成任务，有效的机器人调度机制可以帮助我们寻找能够最小化完工时间的最佳调度方案。主要任务：多机器人协同调度旨在从系统的角度减少资源浪费，减小冲突概率，保证总体最优性。多机器人系统协同调度主要表现为任务分配问题。主要的解决方法有基于行为的分配方法、市场机制方法、群体智能方法、线性规划方法等。98评价方法：科学家们根据自然界中的群体智能研究出了多种仿生算法，并通过仿生算法将群体智能应用到多机器人系统的协同调度中，用来解决协同调度的任务分配问题，如遗传算法、粒子群算法、蚁群算法等。遗传算法：主要是模拟生物的遗传和进化机制，实现对于复杂系统的自适应优化，它主要包括三个核心进程：选择、交配、变异。它具有全局搜索能力强、鲁棒性强、灵活性可扩展性强、并行计算能力强的优点。7协同调度-评价方法99评价方法：科学家们根据自然界中的群体智能研究出了多种仿生算法，并通过仿生算法将群体智能应用到多机器人系统的协同调度中，来解决协同调度的任务分配问题，如遗传算法、粒子群算法、蚁群算法等。粒子群算法：主要是模拟鸟类觅食机制，将鸟作为粒子，鸟群作为粒子群，每个粒子在行进的过程中将自身的信息分享给同伴，它是一种更高效的并行搜索算法，非常适用于对复杂环境中的优化问题的求解。蚁群算法：模拟蚂蚁觅食的过程，当蚂蚁发现食物时，会对食物进行标记，然后在走过的路上留下信息素，根据路上留下信息素的浓度来选择路线。蚁群算法利用了正反馈机制，结合概率算法使得较短的路径能够有较大的机会得到选择，所以蚁群算法不局限于局部最优解。7协同调度-评价方法1007协同调度-算法欢迎探讨！第11章多机器人协同调度-遗传算法智慧物流系统：从设计到实现教学内容CONTENTS1遗传算法2遗传算法起源3遗传算法原理4遗传算法评价104

章节目标理解遗传算法的基本原理与起源；掌握遗传算法的核心进程与实现方法；了解与评估遗传算法的优点、缺点及应用场景。105遗传算法：遗传算法(GeneticAlgorithm,GA)于1975年由美国密歇根大学的Holland教授提出，是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的一种随机搜索算法。它是模拟达尔文生物进化论的自然选择和遗传学机理生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。1遗传算法遗传算法具有全局搜索能力强、鲁棒性强、灵活性和可扩展性强、并行计算能力强等优点，但求解过程中伴随着大量无为的冗余迭代、效率降低、易出现过早收敛与局部最优解等现象。106算法起源：遗传算法的思想源于“自然选择”和“优胜劣汰”的进化规律，它通过计算的方法类比并模拟了生物学中的遗传进化过程，主要包括三个核心进程，如下表所示：2遗传算法起源生物解释计算机解释选择物竞天择，适者生存。生物种群中环境适应度高的个体得以生存，适应度低的个体容易死亡。计算机种群中每个个体都拥有适应度，根据适应度的大小决定个体是否被遗传到下一代种群中。该个体遗传到下一代的概率与其适应度成正比。交配两个个体交配时，两个匹配的染色体可能进行基因交换。设置一个交叉概率，从种群中随机选择两个基因个体，这两个基因个体按照交叉概率进行基因交换，基因交换的位置随机选取。变异种群中任意个体的任意基因片段都有可能发生基因变异。设置一个变异概率，从种群中随机选择一个个体，该个体按照变异概率进行基因变异，变异的基因位置是随机的。1071.基因与个体在生物学中，用“AA”、“Aa”、“aa”来表示基因的性状。在标准的遗传算法中，使用二进制的符号集{0,1}和十进制来表示等位基因，A用二进制符号的0来表示，a用二进制符号的1来表示。2遗传算法起源一对等位基因二进制符号十进制AA000Aa/aA011102aa113遗传算法中的基因表示1081.基因与个体在解决实际问题时，根据实际问题的情况给等位基因赋予具体的性状，比如机器人的运动方向、目的地等。对于复杂的问题可以采用多位的二进制符号来表示一对等位基因，即如果用n位二进制符号表示一对等位基因，则有2n种表示性状。这与“自然界中大多数性状是由多对等位基因决定”的实际情况也是相吻合的。2遗传算法起源1091.基因与个体在标准遗传算法中，使用固定长度的二进制符号串来表示个体，即根据实际情况设置一个固定的基因长度，比如固定长度为6，则某一个体的基因序列可能为：011011011000或011001111000……一个固定长度的基因个体，理论上应当有4**6=4096种不同的排列方式。当固定长度增加1，长度从6变为7时，所有可能排列的总数就会迅速扩增到4**7=16384种，在这些排列组合中只有一种或几种基因序列是最适应自然环境的，即为最优解。当基因长度越长，基因库就越庞大，计算量就会呈指数增长。2遗传算法起源1102.种群在生物学中，在一定时间内占据一定空间的同种生物的所有个体，被称为种群。在计算机中，用固定基因长度的二进制符号表示个体，因此，用固定数量的具有固定基因长度的二进制符号串来表示种群。2遗传算法起源在自然界中，初代种群往往只有具体的数量，因此是无法包括所有的性状，它们只具备部分的性状。在生存过程中，种群中可能会有一部分适应度低的个体被自然界淘汰。因此，每一代种群都会根据适应度来判断是否削减种群中的个体；通过杂交的概率决定是否发生杂交去产生新的性状个体；通过变异的概率来决定是否发生变异去产生新的性状个体。1112遗传算法起源种群迭代的过程1123.适应度自然界中的“物竞天择，适者生存”在计算机中同样适用，在计算机中通过给定一个适应度的算子用来计算所有个体是否适应“自然”。根据实际问题，计算适应度S的表达式并不相同。例如在路径规划问题中，可以使用路径长度的倒数作为适应度S，路径越短对应适应度S就越大，即适应度S越高；或者相同步数下走得越远的个体，其适应度被认为更高。确定了适应度S表达式后还需要估计其取值范围，并制定合适的淘汰阈值，即适应度低于阈值的个体将被淘汰，适应度高于阈值的个体将被留下。2遗传算法起源113算法原理：在遗传算法中，包含五个“随机规则”：①初代种群包含的个体是随机的；②进行交配的个体是随机的；③交配时若发生基因交叉，交叉的基因片段是随机的；④发生变异的个体是随机的；⑤发生变异的基因片段是随机的。3遗传算法原理种群在每一次迭代过程中，通过选择、交配和变异得到的新种群个体数量和初代种群的个体数量相同。选择和交配体现了遗传算法的搜索能力，变异使遗传算法能搜索到问题的所有解。114在实际应用中，会设置一个最大迭代数让该种群迭代有限次数，即判断若干代以后种群中的全部个体或大部分个体的基因序列是否都相同。情况一：相同，则该基因序列就是本问题的最优解；情况二：不相同，需要反复调节各项参数使得最终结果收敛。遗传算法流程图如图所示。3遗传算法原理遗传算法流程图115遗传算法通常需要调节以下参数：①种群数目M：每代种群的数目都为M，一般设为基因序列长度的两倍；②杂交概率P_c：根据经验使用二进制编码的基因序列杂交率为0.7；③变异概率P_m：根据经验一般设为0.001；④最大迭代次数：根据经验一般设为20次。目前没有调节这些参数的有效规则，只能根据具体的应用情景和实际效果进行调整。3遗传算法原理遗传算法流程图116算法评价：遗传算法是一种模拟自然进化过程来寻找最优解的人工智能技术，是一种使用高效、鲁棒性强的优化技术。4遗传算法评价优点：遗传算法具有良好的全局搜索能力，可以快速的把空间中的全体解搜索出来，而不会陷入局部最优解的快速下降陷阱；并且利用它的内在并行性，可以方便的进行分布式计算，加速求解的速度。缺点：遗传算法的局部搜索能力较差，导致单纯的遗传算法比较费时，在进化后期搜索效率较低；在实际应用中，遗传算法容易产生早熟收敛的问题。117算法评价：在多机器人物流系统中，遗传算法在分配任务时，通过计算适应度来判断基因是否为最优。在物流机器人、货架、取货点的分配过程中，将计算路径规划算法的执行时间（从所有机器人执行开始直到最后一个机器人执行任务完成的持续时间）作为分配算法的适应度。时间越短对应路径就越短，路径越短执行越快完成，这样分配的组合比其他路径规划的组合更优。下图表示基于遗传算法进行任务分配，得到每一代中所有基因组合的适应度。4遗传算法评价118从上图中分析得出：每一代基因都有12个基因个体，因此在每一代列表都有12个基因适应度；基因的适应度从第0代开始，适应度(路径执行时间)偏大，接下来每一代基因的适应度都越来越小；适应度为0时，表示该分配组合无法规划出合适路径或者规划路径超时；4遗传算法评价119如下图所示，最后找到历史适应度中最小的基因组合(764,表示76.4s)，分配任务。4遗传算法评价欢迎探讨！第12章多机器人协同调度-粒子群算法智慧物流系统：从设计到实现教学内容CONTENTS3粒子群算法-信息迭代2粒子群算法-粒子与粒子群4粒子群算法原理5算法评价1粒子群算法起源123

章节目标了解粒子群算法的概念和作用；掌握粒子群算法的生物原理和在计算机中的原理。124粒子群算法(ParticleSwarmOptimization，PSO)：1995年，受到鸟群觅食行为的规律性启发，JamesKennedy和RussellEberhart建立了一个简化算法模型，经过多年改进最终形成了粒子群优化算法(ParticleSwarmOptimization,PSO)，也可称为粒子群算法或鸟群觅食算法。1粒子群算法起源一群鸟在某一区域中随机地搜寻一块食物，每只鸟都不知道这块食物的位置，但知道自身与食物的距离，每只鸟将自身的信息在鸟群中共享。所以要想找到这块食物，最快的方法就是在距离食物最近的那只鸟的周边进行搜寻。1251粒子群算法起源1262粒子群算法-粒子与粒子群同遗传算法类似，粒子群算法中也有一些特别的计算机“仿生定义”，其核心可概括为“两个对象两个过程”：对象指鸟（粒子）和鸟群（粒子群）；过程指食物搜寻和信息共享。对象属性行为粒子（鸟）速度、位置、历史位置最优搜寻（计算适应度）粒子群（鸟群）全局位置最优信息共享（迭代）用一串实数表示一个粒子群；用若干串实数表示粒子群；127每个粒子都具有3个属性：速度、位置、历史最优位置。属性符号描述速度vi当前粒子所具有的速度由两部分组成：由先前速度影响遗留下来的惯性速度w；若当前粒子不是粒子群中最接近目标的粒子时，该粒子有向着最优方向移动的趋势速度。位置xi当前粒子所在的位置，用以衡量粒子与目标的距离历史最优位置pi当前粒子在搜寻目标的过程中，距离目标最近时的位置。粒子在移动的过程中分享当前自身的位置，衡量粒子与目标的距离，根据自身的速度调整移动方向，向着最优方向移动。当粒子在移动过程中，自己位于距离目标最近的位置时，不改变方向和速度继续移动。2粒子群算法-粒子与粒子群128在搜索过程中，和遗传算法类似，粒子群算法中也需要定义一个适应度函数，用以评估每个解的优异度。在鸟群觅食的过程中，可以使用粒子（鸟）位置与目标（食物的曼哈顿距离作为适应度函数，假设粒子的坐标为(Xparticle，Ypartice)，目标点坐标为(Xtarget，Ytarget)，粒子坐标到目标点的适应函数（曼哈顿距离）为：

由上式可知，适应度S越接近于1，适应度越好，粒子的位置越好。2粒子群算法-粒子与粒子群129适应度最大的粒子会在粒子群中共享自己的位置，使得其他粒子向其靠近。在寻找全局最优解的过程中，粒子群中的粒子需要不断更新自己的速度和位置，计算粒子更新的速度，需要用到的参数：惯性因子w：用来控制继承粒子当前的速度的因子，越大则对于当前速度的继承程度越小，越小则对于当前速度的继承程度越大；当前粒子的速度vi：粒子当前移动的速度；学习因子c1、c2：c1粒子的加速因子，c2粒子群的加速因子；粒子历史最优位置pi：当前粒子在搜寻目标的过程中，距离目标最近时的位置；当前粒子的位置xi:当前粒子所在的位置；粒子群的历史最优位置pg：粒子群中当前最接近全局最优解的粒子的位置；3粒子群算法-信息迭代130更新粒子的速度：

更新粒子的速度：惯性因子w粒子当前速度vi粒子加速因子c1[0,1]之间的随机数粒子历史最佳位置pi粒子当前位置xi粒子群加速因子c2粒子群历史最佳位置pg3粒子群算法-信息迭代131更新粒子的位置：

更新粒子的位置：

结束迭代：通过信息的迭代，不断地更新粒子自身的位置和速度，向食物靠近。当粒子和食物的适应度(距离越短，适应度越高)，距离为0时，粒子到达食物的位置，结束迭代。3粒子群算法-信息迭代1324粒子群算法原理粒子群算法需要调节的常用参数：粒子群的规模m：粒子使用n位的实数串构成，粒子群是由m个长度为n的实数串构成；惯性因子w：惯性因子越大，全局搜索能力越强，局部搜索能力弱；惯性因子越小，则相反；粒子加速因子c1：代表粒子的个体认知，一般c1

范围在0和4之间；粒子群加速因子c2：代表粒子的社会认知，一般c2

范围在0和4之间；最大迭代次数：根据经验一搬设为20次；更新粒子的位置和速度体现了粒子群算法的搜索能力，更新粒子的历史最佳位置和粒子群的历史最佳位置防止粒子群算法收敛到局部最优解。133先设定一个粒子群规模m，即粒子群数量，再规定用于表示粒子的实数串长度n；在初始化时，随机生成m个粒子，即随机生成m个长度为n的实数串；给所有粒子设置固定或是随机的初始速度，也可全部设置为0；计算粒子的适应度，根据适应度更新粒子的移动速度和位置；然后进行反复的搜索和迭代过程，直到产生最优解或者超出最大迭代次数，结束迭代；4粒子群算法原理134以下用一个实例直观演示粒子群优化算法的迭代过程。假定目标位置坐标为(5,5)，即图中黑色“X”处；设定惯性系数w=0.6；设定学习因子c_1=1.2、c_2=1.5。01234567899876543210X(1)初始化粒子群，随机生成10个粒子的位置和初始速度，分布在10*10的范围内，初始速度于区间[-0.5,0.5]4粒子群算法实例13501234567899876543210X初代粒子及相关数据：粒子位置xi速度vi历史最优位置pi1[7.902,9.143][-0.158,0.112][7.902,9.143]2[3.793,4.72][-0.211,0.456][3.793,4.72]3[8.505,6.29][0.069,-0.473][8.505,6.29]4[0.3,5.237][0.319,-0.18][0.3,5.237]5[7.438,4.7][0.198,0.343][7.438,4.7]6[0.989,0.697][0.371,-0.476][0.989,0.697]7[0.998,1.706][0.426,0.496][0.998,1.706]8[0.573,6.524][0.353,-0.392][0.573,6.524]9[5.492,0.356][0.427,-0.174][5.492,0.356]10[1.881,3.0][-0.279,0.273][1.881,3.0]4粒子群算法实例136(2)搜寻最优位置：

01230123

4粒子群算法实例137(2)搜寻最优位置：根据适应度函数，找到距离目标点最近的粒子位置pg=[3.793,4.72]。01234567899876543210X粒子位置xi速度vi历史最优位置pi1[7.902,9.143][-0.158,0.112][7.902,9.143]2[3.793,4.72][-0.211,0.456][3.793,4.72]3[8.505,6.29][0.069,-0.473][8.505,6.29]4[0.3,5.237][0.319,-0.18][0.3,5.237]5[7.438,4.7][0.198,0.343][7.438,4.7]6[0.989,0.697][0.371,-0.476][0.989,0.697]7[0.998,1.706][0.426,0.496][0.998,1.706]8[0.573,6.524][0.353,-0.392][0.573,6.524]9[5.492,0.356][0.427,-0.174][5.492,0.356]10[1.881,3.0][-0.279,0.273][1.881,3.0]接下来，所有粒子向粒子2靠近，继续搜寻目标点4粒子群算法实例138(3)信息迭代：利用更新粒子位置、速度的公式进行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2为例)：粒子1：

初代粒子的历史最佳位置就是粒子的初始位置，因此可以省略更新粒子的历史最佳位置的步骤。4粒子群算法实例139(3)信息迭代：利用更新粒子位置、速度的公式进行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2为例)：粒子2：

根据适应度函数，粒子2为最佳粒子，因此可以省略更新粒子的历史最佳位置和粒子群的历史最佳位置两项步骤。4粒子群算法实例14001234567899876543210X第一次迭代初代粒子中，粒子2为最佳粒子，所有粒子都快速向粒子2的位置靠近，但因为每个粒子都还具有不小的速度，因此结果并没有收敛，历史最佳位置的粒子是紫色点，需要继续迭代，更新粒子的位置和速度。01234567899876543210X初代粒子4粒子群算法实例141第二代粒子，所有粒子的信息，如下：粒子位置xi速度vi历史最优位置pi1[5.163,6.364][-2.739,-2.779][7.902,9.143]2[3.667,4.993][-0.127,0.273][3.793,4.72]3[5.514,4.996][-2.99,-1.294][8.505,6.29]4[2.739,4.796][2.439,-0.441][0.3,5.237]5[5.211,4.918][-2.226,0.218][7.438,4.7]6[3.016,3.0][2.027,2.303][0.989,0.697]7[3.053,3.943][2.055,2.237][0.998,1.706]8[2.857,5.128][2.284,-1.396][0.573,6.524]9[4.655,3.06][-0.837,2.704][5.492,0.356]10[2.944,4.27][1.063,1.271][1.881,3.0]粒子群历史最佳位置pg[3.743,4.72]最佳距离1.239第二代粒子4粒子群算法实例14201234567899876543210X第二次迭代第二代粒子01234567899876543210X第二代粒子中，粒子5为最佳粒子，更新所有粒子的位置和速度。所有粒子都快速向粒子5的位置靠近，但是同样没有收敛到目标位置，需要继续迭代。4粒子群算法实例143经历20次迭代的结果，将迭代次数作为z轴，时间轴；底部二维坐标为设定的粒子运动范围10×10；最终粒子基本都聚集在一点，即结果收敛在目标坐标(5,5)。4粒子群算法实例144任意取其中单个粒子，其迭代轨迹为：4粒子群算法实例145(4)调节参数：将惯性系数从w=0.6改成w=0.2。观察发现，将惯性系数减小后，粒子群迅速收敛，大约在第7代后，粒子群都聚集在

(5,5)处，由此收敛排列成一条直线状。这样调整参数可以获得较快的收敛速度，但也容易使得收敛得到的是局部最优解，而非全局最优。4粒子群算法实例146PSO算法采用简单的速度位移模型，避免了复杂的遗传操作，同时它特有的记忆功能使其可以动态的跟踪当前的搜索情况并及时调整搜索策略，具有较强的全局搜索能力和鲁棒性。PSO算法有计算简单、易于实现、控制参数少的特点。在实际的多机器人物流系统中，粒子群算法分配任务的过程中，通过计算适应度来判断粒子位置是否为最优，在物流机器人、货架、取货点的分配过程中，将计算路径规划算法的执行时间(最后一个机器人执行完成后的时间)作为分配算法的适应度，时间越短对应路径就越短，对应路径越短执行就越快完成，分配的组合也就越优。5算法评价147输出每一代粒子位置(机器人-货架-取货点)的适应度：本次任务分配迭代了4代，每一代中都有12个粒子，从第0代开始，粒子位置的适应度偏大，下面的每一代粒子位置组合的适应度都变小；迭代到第4代时多数粒子的位置组合的适应度都为788(表示78.8s)，到第4代停止迭代表示粒子位置已经是较优解了，不再更新了。5算法评价148多数粒子位置组合的适应度都为788(表示78.8s)，表示此时的解已经是较优解了，将粒子位置的适应度作为预计执行时间。5算法评价欢迎探讨！第13章多机器人协同调度-蚁群算法智慧物流系统：从设计到实现教学内容CONTENTS1蚁群算法2蚁群算法原理3旅行商问题4蚁群算法评价152

章节目标了解蚁群算法的起源；理解蚁群算法的原理与机制；掌握蚁群算法的信息素更新与浓度计算；了解蚁群算法的优点、缺点及应用前景。153算法起源：蚁群算法（AntColonyOptimization,ACO）是意大利学者MarcoDorigo于1992年基于蚁群觅食的行为特征提出的一种模型进化算法。该算法在求解旅行商问题（TravelingSalesmanProblem,TSP）、分配问题、图着色问题等方面均取得了较好的结果。随着群体智能的研究发展，蚁群算法也被应用于多机器人系统的任务分配及调度协作等方面。1蚁群算法154算法起源：蚁群觅食是一种典型的群体智能行为，蚁群寻找食物时会分散探索，如果一只蚂蚁找到食物，它将返回巢中通知同伴并沿途留下“信息量”（Pheromone），作为蚁群前往食物所在地的标记。信息量会随时间挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕远的一条路上信息量的气味会比较淡，蚁群将倾向于选择另一条更近的路线前往食物所在地。1蚁群算法155算法起源：在旅行商问题中，蚁群算法会设计虚拟的“蚂蚁”摸索不同的路线，并留下虚拟“信息量”。虚拟的“信息量”也会挥发，每只蚂蚁每次随机选择要走的路径，但是它们倾向于选择路径比较短、信息量比较浓的路径。根据“信息量比较浓的路线更近”原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且采用概率算法，所以它能够不局限于局部最优解。1蚁群算法156算法原理：如图1所示，蚂蚁选路过程中较短路径上遗留的信息量会在短时间内大于较长路径，蚁群算法的原理不妨用一个例子来说明：假设A、E两点是蚁群的巢穴和食物源，从其间有两条路径A-B-H-D-E和A-B-C-D-E，其中B-H和H-D间距离为1m，B-C和C-D间距离为0.5m。2蚁群算法原理蚁群选择路径图1157算法原理：如图2所示，在A、E点分别分配30只蚂蚁从两点出发，在t=0时刻，30只蚂蚁走到分支路口B点或D点。因为初始时没有什么线索可供蚂蚁们选择，所以以相同的概率决定选择哪条路径，结果是15只蚂蚁走左边路径D-H、B-H；另外15只蚂蚁走右边的路径D-C、B-C，这些蚂蚁在行进过程中分别留下信息量。2蚁群算法原理蚁群选择路径图2158算法原理：如图3所示，假设蚂蚁都具有相同的移动速度（1m/s）和释放信息量的能力。在经过1s后，从D点出发的蚂蚁，有15只蚂蚁到达H点，还有15只蚂蚁经过C点到达B点（D-H=D-C+C-B）；同样在经过1s后，从B点出发的蚂蚁，有15只蚂蚁到达H点，还有15只蚂蚁经过C点到达D点（B-H=B-C+C-D）。2蚁群算法原理蚁群选择路径图3159算法原理：显然，在相等时间间隔内，路径D-H-B上共有15只蚂蚁经过并留下信息量，路径D-C-B上共有30只蚂蚁经过并留下信息量，其信息量强度是D-H-B路径上的2倍。因此，当再有30只蚂蚁从A、E