基于神经网络和遗传算法的移动机器人路径规划摘要：提出一种基于神经网络和遗传算法的路径规划算法。采用神经网络模型对机器人的环境信息进行描述，利用神经网络的输出建立遗传算法的适应度函数；然后使用遗传算法优化路径。在该算法中将需规划路径的二维编码简化成一维编码。仿真结果表明提出的路径规划方法是正确和有效的。??关键词：路径规划；神经网络；遗传算法；移动机器人中图法分类号：TP18文献标识码：A：1001―3695(2007)02―0264―02路径规划是移动机器人导航的最基本环节之一，它是依据某个或某些优化准则(如工作代价最小、行走路线最短及时间最短等)，在其工作空间中找到一条从起始状态到目标状态能避开障碍物的最优路径[1]。将人工神经网络[2，3]和遗传算法[4]等智能方法应用于机器人运动轨迹自动生成和移动机器人路径规划是一种有效的方法。文献[5]给出了一种神经网络路径规划算法，引入了神经网络结构和模拟退火算法，计算简单，能避免某些局部极值情况，且具有并行性及易于从二维空间推广到三维空间等优点。但在该算法中，路径搜索运动方向受各参数影响大，因此，当具体环境结构改变时，各个加权参数及模拟退火初始温度和降温速度都必须重新调整。针对这一问题对以上方法进行改进，仍然采用神经网络对机器人的运动环境进行描述，但不再采用模拟退火算法而是采用遗传算法进行路径搜索。神经网络作为一个高度并行的分布式系统，为解决机器人系统实时性要求很高的问题提供了可能性，并应用于智能自主移动机器人导航与路径规划等方面。遗传算法优越性[4]在于它不需要采用确定性的搜索策略，只利用结构化和随机性信息，使满足目标的决策获得最大的生存可能。因此，在改变具体环境结构时，不需要大范围变动参数，只需对遗传群体规模和遗传代数稍加改动即可。??1机器人运动环境的神经网络描述??移动机器人工作在具有静态障碍物的环境中，要求从起始地点无碰撞地移动到目标点。为研究方便，对工作空间作如下假设：①移动机器人在有限二维空间中能朝各个方向移动并且不考虑高度信息；②把障碍物边界向外扩展机器人本体在长、宽方向上最大尺寸的1/2，机器人可看作质点忽略不计；③障碍物用凸多边形（如长方形）逼近，一个凹多边形可以用几个凸多边形的组合来表示。??图1给出了一个代表障碍物的长方形及其四个不等式的约束条件。由图1可知，通过判断一个点的坐标是否同时满足四个不等式的要求即可知道该点是否位于障碍物内部。环境内一点Pi(xi,yi)与障碍物长方形的位置可用图2所示的神经网络模型来表示。此网络结构采用三层结构，输入层的两个节点分别表示给定路径点Pi的横坐标xi和纵坐标yi；顶层节点的输出为障碍物的碰撞罚函数（碰撞罚函数是对路径点与障碍物碰撞程度的量化）；中间层节点的阈值为不等式中的常数项。中间层到顶层的连接权系数均为1，输入层到中间层的连接权系数为不等式中变量x，y的系数，顶层节点的阈值取为不等式的个数减去0.5后的负数。??移动机器人的工作环境往往有多个障碍物，而且一条路径也由多个路径点组成，所以把一个路径点的碰撞罚函数定义为路径上所有中间路径点的碰撞罚函数之和。一个点的碰撞罚函数是通过它对各个障碍物的神经网络表示得到的。图3表示多个障碍物环境的神经网络模型。图中每一层表示一个中间路径点。??2遗传算法路径规划??遗传算法（GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合于并行处理以及应用范围广等显著特点，奠定了它作为21世纪关键智能计算方法之一的地位。选择、交叉和变异是遗传算法的三个主要操作算子，它们构成了所谓的遗传操作，使遗传算法具有了其他传统方法所没有的特性。遗传算法中包含了如下五个基本要素：①参数编码；②出示群体的设定；③适应度函数的设计；④遗传操作设计；⑤控制参数设定（主要是指群体大小和使用遗传操作的概率等）。遗传算法的基本处理流程如图4所示。...