移动机器人运动规划应用研究综述_刘华军.pdf

2006年 1月第 8卷第 1期中国工程科学 EngineeringScience Vol1 8No1 1 综合述评[收稿日期] 2004-09-21;修回日期 2004-12-23 [作者简介] 刘华军(1978- ),男,湖北黄冈市人,南京理工大学博士研究生移动机器人运动规划研究综述刘华军,杨静宇,陆建峰,唐振民,赵春霞,成伟明(南京理工大学计算机科学与技术系,南京 210094 ) [摘要] 机器人运动规划是移动机器人导航的核心技术之一。 40多年来,运动规划技术发展迅速,涌现出了许多规划算法,但因为环境描述方式差异巨大,技术差别大,实验比较难度较大。在总结机器人发展史上具有典型意义的规划算法的基础上,提出了路径规划算法的评价标准和形式化描述方式,介绍了每种算法的原理或技术,从搜索策略和环境建模的角度将它们分为四大类,分别是基于自由空间几何构造的规划算法、前向图搜索算法、基于随机采样的运动规划算法以及智能化规划算法,并按照提出的标准比较它们的性能。[关键词] 移动机器人;运动规划;机器人导航;几何构造;空间搜索;随机采样;人工智能[中图分类号] TP24 [文献标识码] A [文章编号] 1009-1742 (2006 )01-0085-10 1 概述美国 MIT著名机器人科学家认为自主机器人导航应该回答三个问题[1], “ WhereamI?”, “ WhereIamgoing?”,“ HowshouldIgothere?”, 分别描述了机器人定位,规划和控制三个问题,机器人运动规划是解决机器人导航的三个核心问题之一。对机器人运动规划的研究是 20世纪 60年代出现的[2]。 1978年 Lozano2 Perez和 Wesley首次引入构型空间(C-空间)的概念构造规划器[3],对于现代的运动规划问题是一次划时代的革命。在 C- 空间中,每一个位姿代表着机器人在物理空间中的位置和方位,机器人被当作一个点,运动规划问题就变成在位姿空间中寻找一条从起始位姿点到目标位姿点的连续路径。 1987年, [4]将机械系统中的非完整性引入到机器人运动规划中解决自动泊车问题。自此,非完整运动规划成为一个新的研究热点一直延续到今天。移动机器人路径规划可以当作运动规划的一个简单特例。所谓”路径”是指在位姿空间中机器人位姿的一个特定序列,而不考虑机器人位姿的时间因素;而“轨迹”与何时到达路径中的每个部分有关,强调了时间性[4,5]。机器人运动规划就是对“轨迹”的规划,按照环境建模方式和搜索策略的异同,可将规划方法大致上分成三类,分别是基于自由空间几何构造的规划,前向图搜索算法和近年兴起的以解决高维姿态空间和复杂环境中运动规划为目的的基于随机采样的运动规划。基于几何构造的规划方法有可视图[6]、切线图[7]、 Voronoi图[8]以及精确(近似)栅格分解[9,10]等方法。路径规划是搜索的过程[11]。不管何种规划算法,最终都将归结到在某个空间中搜索一条满足某准则的连续路径问题。利用几何构造的手段描述环境的自由空间,一般都会构成图(栅格被当作一类特殊的图),最终完成轨迹的规划需要图搜索这个很重要的步骤。前向图搜索算法是从起始点出发向目标点搜索的算法,常用的包括贪心算法[12]、 Dijkstra算法[13]、 A 3算法[