基于多算法结合的机器人路径规划算法

摘要： 机器人的路径规划目前已有多种解决方案，如模拟物理学中场概念的人工势场算法，以及智能算法中的遗传算法。但每一种算法都有一定的局限性，每一种算法只在一定条件下才能达到最好的效果。本文着眼于对各个算法适应的条件进行分类，在相应的条件下使用相应的算法，开发出CPP（Combination Path Planning）算法，从而克服的各个算法的缺点，让每种算法的优点得到充分发挥。

关键词：路径规划；条件适应；遗传算法；人工势场算法

中图分类号：TP242 文献标识码：A 文章编号：1009-3044（2016）17-0174-03

Abstract： There are variety of solutions of Robot path planning， such as the algorithm called artificial potential field algorithm， which simulation the potential form physics concept and genetic algorithm. But some limitations with these algorithm， which only gets the best result under certain conditions. So it is necessary for us to use one algorithm under the conditions match it best， by which every algorithm can work more effective.

Key words： path planning； condition match；genetic algorithm； artificial potential algorithm

为了更加深入的学习多智能体系统，开创了RoboCup项目，即机器人世界杯。近几年来，机器人足球的国际赛事越来越普及。RoboCup是其中影响最大的。而路径规划问题又是RoboCup3D项目中的一个热点研究领域。所谓路径规划，就是在仿真环境中找到一条从起点到终点的最优，即最短路径。不仅要考虑到路径长度，还要考虑到障碍物的干扰。这样，路径规划问题就涉及了实时避障问题，这两个问题是反映智能双足机器人的自主能力的关键性问题。如何在各种复杂的环境中找到无碰撞的最优路径本身就是一个高度智能的过程。基于此问题的算法近年来也是层见叠出，新的算法和对传统算法的改进算法不断涌现出来。有以模拟退火算法，人工势场算法和模糊逻辑算法为代表的传统算法；还有图形化的算法，如C空间图形法，自由空间法，以及栅栏法；而最新研究的智能仿生学算法从生物处的得到启示，从蚁群觅食中得到的蚁群算法，从动物神经网络行为中学到的神经网络算法，还有模拟达尔文遗传选择和自然淘汰的遗传算法。以上的每种算法都有其优缺点，栅栏算法在一定的条件下可以得到最优解，但是解的质量取决于栅栏大小的选择，栅栏越小，所需要的储存空间也更大。而可视图法每经过一定周期，就需要重新计算路径，寻找效率较低，以上两种方法求得的路径为折线，不适于机器人的运动控制；人工势场算法虽然克服了上述算法的缺点，但是存在局部最优解的问题，即规划路径非全局最优。而发展火热的智能仿生学算法却因为其需要大量的存储空间以及相当高的时空复杂度而不能在实时避障问题中大显身手，还需要我们不断地研究发展才能应用到实际问题中。既然每种算法都有其适用范围和不适用范围，那我们可以就环境条件进行分类，在每种环境下使用其适用的算法，可以让每种算法的缺点得到最大程度的缩小，而优点得到充分放大。本文就采用能够得到全局最优解的遗传算法和存在局部最优问题的人工势场算法。两种方法结合，在RoboCup3D的仿真平台上测试。3D仿真平台是采用C/S模式设计的机器人足球比赛平台，平台实现对真实的物理三维世界模型的模拟，该系统主要用于研究服务器的通信，基本动作及决策系统，对球员的感知等基本功能模块。

1 遗传算法

1.1遗传算法路径规划的具体方法

遗传算法（Genetic Algorithm，GA）启发于自让进化的模型， 是一种在自然选择和遗传基础上发展来的全局优化算法。编码、适应度函数、初始群体、控制参数和遗传操作过程是遗传算法的五个基本要素；而遗传操作又包括选择、交叉复制、变异。

障碍物的描述：

在综合考虑障碍物的搜索范围和搜索效率等条件的情况下，以机器人的起始点S与目标点D的连线长度|SD|为长，以|SD|/2位宽确定障碍物区域α，则区域α为障碍物搜索范围。用集合Obstacle{}表示障碍物集合，元素为On，如第一个元素为O1，第二个元素为O2。且α内On的表示为On（xn，yn）∈α，其中xn和yn分别为第n个元素在球传平面的横坐标和纵坐标。

将区域α的长分为m+1等分，宽分为n+1等分，这样α内就有了m*n个路径点，在每一条平行于宽线的线（我们暂且称之为横线，m条）上有n个路径点，在每一条横线上取一个路径点，这样便形成了一条由各个横线上的路径点连成的一条路径线β，我们这样表示β：

其中Ln表示从开始点S开始第n条横线上的一个路径点P，xn、yn表示相应的二维坐标。

1.2建立启发函数

启发函数关系到遗传迭代的方向，在最优路径的规划中，我们要考虑到路径长短，距离障碍物距离以及路径平滑度三个因素。

路径长度启发函数为：

[f1=|LiLi+1|] （其中i从1到m-1）

距离障碍物启发函数 ：

[f2=DistanceL，Oi]（其中i从1到m-1），其中Distance表示障碍物集合中的任一障碍物到路径的垂直距离。