移动机器人路径规划研究现状及展望
摘 要：移动机器人路径规划技术是机器人研究领域中的核心技术之一。通过对全局路径规划和局部路径规划中各种方法的分析，指出了各种方法的优点和不足以及改进的办法，并对移动机器人路径规划技术的发展趋势进行了展望。
关键词：移动机器人； 路径规划； 遗传算法
移动机器人是装备了机械腿、轮子、关节、抓握器等执行器以及控制器来完成特定任务的一种实体智能体。近年来，随着科学技术的飞快发展，移动机器人在工业、农业、医疗、服务、航空和军事等领域得到了广泛的应用，已成为学术研究的重点。在移动机器人的研究中，导航研究是核心，而路径规划是机器人导航研究的重要环节之一。在机器人执行任务时，要求机器人在工作环境中（有障碍物或无障碍物）能根据一定的评价标准搜索一条从起始地点到目标地点的最优或次优路径[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人工势场法
