移动机器人路径规划研究现状及展望移动机器人路径规划研究现状及展望
移动机器人路径规划技术是机器人研究领域中的核心技术之一。通过对全局路径规划和局部路径规划中各种方
法的分析,指出了各种方法的优点和不足以及改进的办法,并对移动机器人路径规划技术的发展趋势进行了展
望。
摘摘 要:要:
关键词:关键词: 移动机器人; 路径规划; 遗传算法
移动机器人是装备了机械腿、轮子、关节、抓握器等执行器以及控制器来完成特定任务的一种实体智能体。近年来,随着
科学技术的飞快发展,移动机器人在工业、农业、医疗、服务、航空和军事等领域得到了广泛的应用,已成为学术研究的重
点。在移动机器人的研究中,导航研究是核心,而路径规划是机器人导航研究的重要环节之一。在机器人执行任务时,要求机
器人在工作环境中(有障碍物或无障碍物)能根据一定的评价标准搜索一条从起始地点到目标地点的最优或次优路径[1]。移
动机器人的路径规划根据环境是否已知可分为基于地图的全局路径规划和基于传感器的局部路径规划。
1全局路径规划全局路径规划
1.1栅格分解法栅格分解法
栅格分解法是目前广泛研究的路径规划方法之一。该方法把移动机器人的运动环境分解为多个简单的栅格并根据它们是否
被障碍物占据来进行状态描述,障碍物栅格和非障碍物栅格具有不同的标识值,它能快速直观地融合传感器信息。但是为了得
到比较精确的规划结果,必须将环境划分为较小的栅格,这就导致存储空间增大,在大规模环境下路径规划的计算复杂程度将
加大。为了克服栅格表示的存储空间问题,邰宜斌提了一种四叉树分割方法[2],该算法递归地把环境分解为大小不一的矩形
区域,这些矩形区域或者完全被障碍物占据,或者是完全自由可行的。每次递归都将一个较大的栅格划分为4个较小的栅格,
取得了较好的计算效果。另外栅格分解法随着机器人自由度的增加会出现“维数灾难”问题,不适用于解决多自由度机器人在复
杂环境中的路径规划。Frank在2004年提出了概率栅格分解算法,在该算法中引入随机采样,可使多自由度机器人在复杂环境
中快速找到一条可行路径。2006年吕太之等在概率栅格分解算法的基础上引入了Anytime算法,将随机采样应用到栅格分解算
法中,使算法效率得到了提高,但是受环境信息和随机采样的影响比较大[3]。
1.2拓扑法拓扑法
拓扑法主要包括三部分:划分状态空间、构建特征网、在特征网上搜索路径。拓扑法的基本要素是节点和边,用节点表示
某个特定的位置,用边表示这些位置之间的联系,可以用G=(V,E)描述空间的特征,其中V表示顶点集合,E表示连接顶点的边
集合[4]。利用该方法可缩小搜索空间,使得存储需求小,适合于大规模环境的路径规划,但是构建特征网的过程比较复杂,
而且当障碍物增加时如何将增加的节点与已有节点进行节点匹配是一个难点。2005年,王力虎等提出了一种适用于清扫机器
人的区域充满拓扑算法,用传感器感知环境信息以建立环境的拓扑地图,机器人可以利用搜索图的方法搜索环境,可达到环境
的有效覆盖,但在搜索时没有具体体现节点间的距离、清扫覆盖率等信息,使得搜索效率不是很高[5]。2006年,种琤等提出
了一种基于扫描法的构造环境拓扑图方法,利用启发式函数法实现对所构建拓扑图的扩展,采用了逐步构建环境拓扑图的方
式,实现了在线构建,可应用于任意工作环境,且计算复杂度低,但此算法不能保证搜索到最优路径[6]。
1.3惩罚函数法惩罚函数法
在机器人运行环境中因为有障碍物,使得机器人的路径规划成为一个有约束的问题,惩罚函数法将这个有约束的问题转化
为一系列无约束极小化问题,再通过解决这些无约束问题获得原约束问题的最优解[7]。柳在鑫、王进戈等在2009年将机器人
的路径规划问题转化为一类带有不等式约束条件的非线性极小化问题,并采用惩罚函数法来求解此类问题,该方法原理简单,
算法易行,使用范围广[8]。
2 局部路径规划局部路径规划
2.1人工势场法人工势场法
人工势场法是机器人局部路径规划中最经典的方法,该方法是由Khatib在1986年提出的,它的基本原理是:把机器人在工
作环境中的运动看作是在一个人造受力场中的运动,其中目标对机器人产生引力,障碍物对机器人产生斥力,机器人在这两类
力的合力作用下向目标前进[9],该合力就是机器人的加速度力,可用来控制机器人的运动方向,利用人工势场法进行机器人
的路径规划,计算简单,所规划的路径光滑,有较好的实时性,但会因为局部最小值而导致目标点不能到达。近几年来国内陆
续有学者提出了一些改进方法。2006年,刘义等提出了修改斥力函数法,用来解决局部最小值问题[10]。哈尔滨工业大学的张
建英等提出了添加附加控制力的方法,即当机器人在障碍物附近振荡,无法离开障碍物时,给机器人施加一个控制力,使机器
人绕过障碍物向目标位置前进,但通过此方法规划的路径在障碍物边缘有抖动现象产生[11]。
2.2遗传算法遗传算法
(1)选择编码方式,并将路径用编码表示;
(2)产生初始群体;
(3)确定适应度函数并根据适应度函数计算初始群体的适应度值;
(4)如果不满足条件,{选择、交换、变异、计算新一代群体的适应性值};
(5)输出结果。
遗传算法直接对移动机器人的路径进行操作,采用概率化的寻优方法,自适应地调整搜索方向,不采用确定性搜索规则,
易于并行化,但对于未知复杂环境,利用遗传算法进行路径规划时运算速度慢,而且需要占据大量的存储空间。近几年许多研
究学者提出了一些改进后的遗传算法,例如王洲等提出了移动机器人在静态障碍物环境中路径规划的新方法,该方法设计了5
个遗传算子(选择、交叉、变异、删除、插入),并且提出了新的变异算子、插入算子和删除算子,加快了较好个体在群体中
的传播,提高了路径搜索速度和解的精度[12]。对于遗传算法的改进,王新杰等将其与图搜索法相结合,用Dijkstra算法王求得
初始路径,再利用遗传算法的一系列选择、交叉、变异操作来优化路径,这种方法减少了搜索的盲目性,不会产生无效路径
[13]。当机器人处于静动态障碍物同时存在的环境中时,卢瑾等在机器人路径规划时引入了双重遗传算法机制,第一重算法针
对静态障碍物环境,第二重算法针对动态障碍物环境,两重算法采用不同的适应度函数作为评价标准,通过改进操作算子、引
入优化算子,可快速有效地找到同时能避开静动态障碍物的最优路径,仿真结果验证了该方法的有效性。但对于动态的、未知
复杂环境下的路径规划没有进行验证[14]。
2.3模拟退火算法模拟退火算法
模拟退火算法(SA)依据固体退火原理,固体在加温时,内部粒子运动随温升增强,变为无序状,再进行退火,粒子运动
评论0