移动机器人运动规划研究综述.pdf

2006 年 1 月 中国工程科学 Jan. 2006 第 8 卷第 1 期 Engineering Science Vol 8 No1 综 合 述 评 移动机器人运动规划研究综述 刘华军 , 杨静宇 , 陆建峰 , 唐振民 , 赵春霞 , 成伟明 (南京理工大学计算机科学与技术系 , 南京 　210094) [摘要] 　机器人运动规划是移动机器人导航的核心技术之一。40 多年来 , 运动规划技术发展迅速 , 涌现出了 许多规划算法 , 但因为环境描述方式差异巨大 , 技术差别大 , 实验比较难度较大。在总结机器人发展史上具有 典型意义的规划算法的基础上 , 提出了路径规划算法的评价标准和形式化描述方式 , 介绍了每种算法的原理或 技术 , 从搜索策略和环境建模的角度将它们分为四大类 , 分别是基于自由空间几何构造的规划算法、前向图搜 索算法、基于随机采样的运动规划算法以及智能化规划算法 , 并按照提出的标准比较它们的性能。 移动机器人 ; 运动规划 ; 机器人导航 ; 几何构造 ; 空间搜索 ; 随机采样; 人工智能 [ 关键词] 　 [ 中图分类号] TP24 　　 [文献标识码] A 　　 [文章编号] 1009 - 1742 (2006) 01 - 0085 - 10 位姿的一个特定序列 , 而不考虑机器人位姿的时间 1 　概述 因素; 而“轨迹”与何时到达路径中的每个部分有 美国 M IT 著名机器人科学家认为自主机器人 关 , 强调了时间性[4 , 5 ] 。机器人运动规划就是对 导航应该回答三个问题[1 ] , “Where am I ?”, “轨迹”的规划, 按照环境建模方式和搜索策略的 “Where I am going ?”, “How should I go there ?”, 异同 , 可将规划方法大致上分成三类 , 分别是基于 分别描述了机器人定位 , 规划和控制三个问题 , 机 自由空间几何构造的规划, 前向图搜索算法和近年 器人运动规划是解决机器人导航的三个核心问题 兴起的以解决高维姿态空间和复杂环境中运动规划 之一。 为目的的基于随机采样的运动规划。 对机器人运动规划的研究是 20 世纪 60 年代出 基于几何构造的规划方法有可视图[6 ] 、切线 现的[2 ] 。1978 年 LozanoPerez 和 Wesley 首次引入 图[7 ] 、Voronoi 图[8 ] 以及精确 ( 近似) 栅格分 构型空间 (C - 空间) 的概念构造规划器[3 ] , 对于 解[9 ,10 ]等方法。 现代的运动规划问题是一次划时代的革命。在 C - 路径规划是搜索的过程[11 ] 。不管何种规划算 空间中 , 每一个位姿代表着机器人在物理空间中的 法 , 最终都将归结到在某个空间中搜索一条满足某 位置和方位 , 机器人被当作一个点 , 运动规划问题 准则的连续路径问题。利用几何构造的手段描述环 ( 就变成在位姿空间中寻找一条从起始位姿点到目标