移动机器人自动巡径浅析

胡斐

【摘要】全局路径规划则是智能移动机器人开发的重要环节之一。文章对几种常用路径规划方法进行了分析，提出了改进的A*angle算法，并通过仿真实验证明了改进A*算法进行全局路径规划的有效性。

【关键词】全局路径规划 移动机器人 A*angle算法 全局地图建模 四又树建模

全局路径规划技术是移动机器人学研究领域中一个重要的部分，机器人路径规划就是依据某个或某些优化标准，在空间中找到一条从起始状态到目标状态的最优路径，因而路径规划问题又可以称为避碰规划问题。本文对全局路径规划进行了研究，并设计了一种基于肿angle算法的全局路径规划实验，验证算法的可行性。

一、全局路径规划分析

路径规划包含如下方面z在移动障碍物之间计算出无碰路径：获取物体之间的精确关系：分析基于传感信息所做的运动策略的不稳定性：处理物理模型的特性以及机器人对物体的抓取。

路径规划用数学语言可描述为：C为一个机器人，W就是机器人C的工作空间，定义为RN，N=2或3：设B1川Bq是空间W中分布的静态障碍物。如果C..，Bq的几何特性以及B;的位置己知的话。机器人C在W中从起始点到目标点并且不碰到B，的一系列连续的线段就是C的运动规划问题。

（一）路径规划的分类及现状

从到目前为止的研究来看，移动机器人路径规划方法主要可以分为以下三种类型：

1.基于事例的学习规划方法。基于事例的学习规划方法依靠过去的经验进行学习及问题求解，一个新的事例可以通过修改事例库中与当前情况相似的旧的事例来获得。将其应用于移动机器人的路径规划中可以描述为：首先，利用路径规划所用到的或己产生的信息建立一个事例库，库中的任一事例包含每一次规划时的环境信息和路径信息，这些事例可以通过特定的索引取得：随后，将由当前规划任务和环境信息产生的事例与事例库中的事例进行匹配，以寻找出一个最优匹配事例，然后对该事例进行修正，并以此作为最后的结果。

2.基于环境模型的规划方法。该方法首先需要建立一个关于机器人运动环境的环境模型。在很多时候由于移动机器人的工作环境具有不确定性（包括非结构性、动态性等），使得移动机器人无法建立全局环境模型，而只能根据传感器信息实时地建立局部环境模型，因此局部模型的实时性、可靠性成为影响移动机器人是否可以安全、连续、平稳运动的关键。环境建模的方法基本上可以分为两类：网络/图建模方法、基于网格的建模方法。前者主要包括自由空间法、顶点图像法、广义锥法等，利用它们在进行路径规划时可得到比较精确的解，但所耗费的计算量相当大，不适合于实际的应用。而后者在实现上要简单许多，所以应用比较广泛，其典型代表就是四叉树建模法及其扩展算法（如基于位置码四叉树建模法、Framed-quad trees建模法等）。

3.基于行为的路径规划方法。基于行为的方法由Brooks在他著名的包容式结构中建立，它是一门从生物系统收到启发而产生的用来设计自主机器人的技术，它采用类似动物进化的自底向上的原理体系，尝试从简单的智能体来建立-个复杂的系统。将其用于解决移动机器人路径规划问题是一种新的发展趋势，它把导航问题分解为许多相对独立的行为单元，比如跟踪、避碰、目标制导等。这些行为单元是一些由传感器和执行器组成的完整的运动控制单元，具有相应的军航功能，各行为单元所采用的行为方式各不相同，这些单元通过相互协调工作来完成导航任务。

（二）常用的路径规划算法

Dijkstra算法是由荷兰数学家E.W.Dijkstra于1959年提出的一种适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从指定结点到图中所有其他结点的最短路径。

A*算法，启发式搜索（Heuristic Search）是基于知识的搜索策略，即从初始状态和当前状态到目标状态搜索时具有与步骤数或费用相关的信息。该搜索法包括最佳优先搜索、存储界限搜索和迭代渐近算法，如：爬山搜索和模拟方法等。

Floyd算法又称插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法是在1962年由Floyd提出的。它可以直接求出图中所有顶点对之间的最短路径和最短路径长度。

（三）全局地图建模方法

全局规划的第一步就是要建立全局地图，其构建方法分为自由空间法和构造空间法。构造空间又进一步划分为可视图法（Visibility Graph）、沃罗诺伊图法（Voronoi Diagram）和栅格法（Grids）。

本文采用栅格法构建地图，并运用四叉树方法是对栅格法的改进，考虑移动机器人系统运行在一个平面正方形区域内（若不满足，可以对原来平面做拓展，并把拓展部分设置为障碍区域），基于位置码的四叉树法把环境划分为2n*2n个基本元素。每个基本元素的形状也是正方形，其边长不小于机器人的步长。基本元素的取值为0或1，0表示自由区域，1表示障碍区域或包含障碍的区域。然后模型递归地把环境分为4个大小相等的子区域，直到每个区域中所包含的基本元素全为0或全为lo

四叉树模型的图形表达中，用黑结点表示障碍区域，用白结点表示自由区域，这两类结点均为叶子结点：非叶子结点则可以使用灰结点表示，该结点可以一进步递归分解。

二、改进的A*算法

Mangle是对启发式算法肿的改进：

1.用后向链表代替了原始A*算法中的Closed歹Ll表，在实现过程中主要是多定义了父亲节点这样一个变量，按照指针指向就可以找到路径。优化了路径链表。

2.在启发式函数上，我们不再用Manhattan函数来计算距离，而是改用最佳栅格距离来表示。所谓最佳栅格距离是指机器人遵循栅格移动准则限制下的理想最小距离。更一般化的h（町，sz）=Mi旧（欲，今）+0.4142×Min（dx，dy）。

3.在原始A*算法的基础上，对其评估函数进行了改进，加入了转向角度和转次数这两个约束条件：f（n）=W1×/+w2×α+W3×n。在编程过程中需建立两个列表Vfather和OPEN，其中Vfather列表以存放被扩展的节点n，OPEN列表中存放待扩展的节点，且在OPEN中启发式函数f最小的节点始终在表尾，以便每次扩展后建立的后项列表总是指向f值最小的方向。

三、仿真实验结果

环境地图被构造成栅格地图，符号“0”所在栅格表示障碍物所在位置：符号“口”所在柵格为起始节点：符号“V”所在栅格表示目标节点：空白栅格表示可穿越地区，将栅格数据表示为以Morton码为下标一的维数组。

参考文献：

[1]许心德.环境部分未知情况下的服务机器人导航研究[D].中国科学技术大学，2009.

[2]陈西博.家庭环境只能空间中服务机器人导航技术研究[D].山东大学，2010.

[3]严蔚敏，吴伟民数据结构[M].北京：清华大学出版社，2002.

[4]P.E.Hart，N.J.Nilsson，B.Raphael.A Formal Basis for the Heuristic Detenninations of Minimum Cost PathsW. IEEE Trans Syst Cybemetics， 1968，4 （2）.

[5]Floyd R W.Algorithm 97：Shortet Path. Communica-tions oftheACM，1962，5 （6）.