文档库

最新最全的文档下载
当前位置:文档库 > 基于环境模型的路径规划算法研究

基于环境模型的路径规划算法研究

2008 NO.09

Science and Technology Innovation Herald工 程 技 术科技创新导报

1 引言

路径规划技术是移动机器人技术研究中的一个重要领域。所谓路径规划是指移动机器人按照某一性能指标(如距离、时间、能量等)搜索一条从起始状态到目标状态的最优或近似最优的路径[1]。基于环境模型的路径规划流程通常包含环境建模和路径搜索两步,首先根据所获取的全局或局部的环境信息建立环境模型,如图、树、栅格、网络等,然后依据一定的路径搜索算法,在环境模型上寻找一条运动控制所需的最优或近似最优路径。

本文首先分析移动机器人路径规划所常用的环境模型,然后介绍一些主要的路径规划算法,最后对其研究趋势进行展望。

2 环境模型

对基于环境模型的路径规划算法来说,其性能和所用的环境模型密不可分,许多路径规划算法的突出优势即体现在其所用的环境模型上。

环境模型大致可分为两类:网络/图模型、网格/树模型。前者如可视图、切线图、Voronoi图、拓扑网络等,利用它们在进行路径规划时可得到比较精确的解,但计算量大,不适于实时应用;后者如栅格、四叉树、八叉树等,简单易用,应用广泛。

环境模型是路径规划算法的基础,能否充分反映环境信息、能否有效建立环境模型,关系到整个路径规划算法的性能优劣。环境信息完全已知时,可建立全局环境模型。在实际应用中,移动机器人的工作环境常常具有不确定性(包括非结构性、动态性等),使得机器人无法预先建立全局环境模型,只能根据传感器信息实时地建立局部环境模型。

建立环境模型通常需要考虑两个问题:

一是环境模型的结构和数据量,结构越复杂、数据越多,反映的环境信息越详细和完整,但导致用于保存环境信息的内存增大,难以实时更新环境信息和规划路径;相反,若模型结构简单、数据量小,则占用内存较小,易于实时更新和快速规划,但可能会遗失某些有用的环境细节信息。

二是建模过程的复杂度,建模复杂导致耗时较长,难以及时反映环境变化。

全局路径规划中环境信息完全预知,建模一次即可满足规划要求,对环境建模的要求较低;相反,局部路径规划中环境信息完全未知或部分未知,移动机器人主要依靠传感器感知环境,因此对路径规划的环境建模阶段提出了较高要求:既要保

留尽可能多的环境信息满足路径规划的可

靠性,又要尽量使环境模型结构简单、数

据量小、易于建模,满足局部路径规划的

实时性。如何同时满足可靠性(信息完整

性)和实时性(模型简单化)要求,是局部路

径规划环境建模首先要考虑的问题。

3 路径规划

根据移动机器人掌握环境信息的完整

程度,路径规划可分为两种类型,一种是

基于环境完全先验信息的全局路径规划,

另一种是基于视觉、激光、超声波等传感

器信息的局部路径规划。

局部路径规划和全局路径规划并没有

本质区别,前者只是把全局路径规划的全

局目标分成多个阶段性子目标,在每个阶

段性的局部环境中做小范围的“全局路径

规划”。很多适用于全局路径规划的方法

经过改进都可以用于局部路径规划,而适

用于局部路径规划的方法都可以适用于全

局路径规划。

全局路径规划的方法主要有可视图

法,栅格法,距离转换法,拓扑法,自由

空间法等[1-4]。可视图法视移动机器人为一

点,将机器人、目标点和多边形障碍物的

各顶点进行组合连接,并保证这些直线均

不与障碍物相交,即每条直线均“可视”,

这就形成了一张图,称为可视图。其改进

方法包括切线图法和Voronoi 图法等方

法。栅格法(也称为单元分解法)将移动机

器人工作环境分解成一系列网格单元,采

用四叉树或八叉树表示工作环境,并通过

搜索树算法完成路径搜索。栅格法最初应

用于全局路径规划,改进后也广泛应用于

局部路径规划,文献[5]设计了基于栅格法

的实时避障和导航控制算法,文献[6]将改

进栅格法与回归预测结合,应用于具有静

态和动态障碍物的移动机器人规划路径问

题,均取得了较为理想的效果。距离转换

法是基于栅格环境模型的路径规划算法,

与栅格法的区别在于其路径搜索方式不

同,其优点是支持多机器人、多目标和多

种类型的路径搜索,缺点是栅格环境分辨

率较高时计算量较大。拓扑法将规划空间

分割成具有拓扑特征的子空间,根据彼此

连通性建立拓扑网络,在网络上寻找起始

点到目标点的拓扑路径,最终由拓扑路径

求出几何路径。自由空间法采用预先定义

的基本形状如广义锥形和凸多边形等构造

自由空间,并将自由空间表示为连通图,通

过搜索连通图来进行路径规划。

局部路径规划包括人工势场法,模糊

逻辑算法,神经网络法,遗传算法,启发

式搜索等[1-4,7]。人工势场法是由Khatib提

出的一种虚拟力法,其基本思想是将移动

机器人在环境中的运动视为一种虚拟人工

受力场中的运动,障碍物对移动机器人产

生斥力,目标点产生引力,由一定的算法

产生相应的合力,形成抽象力的势场,机

器人在势场中受到抽象力作用而绕过障碍

物。模糊逻辑算法根据模糊的环境信息,

通过查表得到规划信息,完成局部路径规

划,克服了势场法易产生的局部极小问

题,对处理未知环境下的规划问题显示出

很大优越性。神经网络法将传感器数据作

为网络输入,由人给定相应场合下期望运

动方向角增量作为网络输出,由多个选定

位姿下的一组数据构成原始样本集,经过

剔除重复或冲突样本等加工处理,得到最

终样本集。遗传算法以自然遗传机制和自

然选择等生物进化理论为基础,构造了一

类随机化搜索算法,通过多点搜索,更有

可能搜索到全局最优解。启发式搜索在路

径搜索时加入启发信息,利用启发信息选

择下一个要扩展的节点。启发式方法的最

初代表是A*算法,而其新发展是D*和

Focussed D*这两种增量式图搜索算法(又

称Dynamic A*算法),此外还出现了一些

基于A*算法的改进算法[8],它们一般都是

通过修改A*算法中的估价函数和图搜索

方向而实现的,可以较大地提高路径规划

的速度,具有一定的复杂环境自适应能

力。

4 研究趋势

随着计算机、传感器及控制技术的发

展,特别是各种新算法不断涌现,移动机

器人路径规划技术已经取得了丰硕研究成

果。特别是周围环境已知的全局路径规

划,其理论研究已比较完善,目前比较活

跃的领域是研究在环境未知情况下的局部

路径规划。从已有的研究成果看,有以下

趋势[1-4]:

(1)多传感器信息融合用于路径规划。

多传感器所获得的信息具有冗余性、互补

性、实时性和低代价性,且可以快速并行

分析现场环境。目前多传感器信息融合技

术在移动机器人导航中的应用已取得许多

重大成果。

(2)全局路径规划与局部路径规划的结

合。全局规划一般是建立在已知环境信息

的基础上,适应范围相对有限;局部规划

能适用于环境未知的情况,但有时反应速

度不快,对规划系统的要求较高,因此如

果把两者结合就可以达到更好的规划效

果。

(3)传统规划方法与新的智能方法之间

基于环境模型的路径规划算法研究

常继科 赵建辉

(河南大学计算机与信息工程学院 河南开封 475001)

摘 要:路径规划技术是移动机器人技术研究中的一个重要领域。本文分析了路径规划中所常用的环境模型,介绍了一些主要的全局和局部路径规划算法,并对其研究趋势进行展望。

关键字:环境模型 全局路径规划 局部路径规划

中图分类号:TP311文献标识码:A文章编号:1674-098X(2008)03(c)-0046-02

46科技创新导报 Science and Technology Innovation Herald

工 程 技 术

2008 NO.09

Science and Technology Innovation Herald

科技创新导报

电视的历史不足百年,而她对人类生存方式的影响却不可估量。尤其是20世纪80年代以来,以数字化技术为代表的信息传播新技术的迅猛发展,使电视的功能更加多元化,电视与人们的工作生活将更加密不可分。

随着电视技术数字化和DV的流行,普及,视频编辑技术的发展也越来越受关注。对视频进行编辑的方式分为:线性编辑和非线性编辑。

线性编辑,是指在摄影机、录像机、编辑机、特技机等设备上,以原始的录像带作为素材,以线性搜索的方法找到想要的视频片段,然后将所有需要的片断按照顺序录制到另一盘录像带中。在这个过程中,需要工作人员必须使用播放、暂停、录制等功能来完成基本的剪辑。如果在编辑时出现失误,或者需要在已经编辑好的录像带上插入或删除视频片段,那么在插入点或删除点以后的所有视频片段都要重新移动一次,因此在操作上很不方便。由此可见,线性编辑需要耗费很多时间,并且录像带在经过了反复地录制、剪辑、添加特效与字幕等操作后,画面质量也会变得越来越差。

非线性编辑是编辑多个视频素材的一种方式,它使用户在编辑过程中在任意时刻均能随机访问所有素材。非线性编辑技术融入了计算机和多媒体这两个领域的前端技术,集录像、编辑、特技、动画、字幕、同步、切换、调音、播出等多种功能于一体,改变了人们剪辑素材的传统观念,克服了传统编辑的缺点,提高了视频编辑的效率。相对于线性编辑的制作途径,非线性编辑可以在电脑中利用数字信息进行视频\音频编辑,只需使用鼠标和键盘就可以完成视频编辑的操作。

比较而言,非线性编辑技术有如下几个特点:

①高质量的图像信号

使用传统的录像带编辑节目,编辑过程中需反复搜索、播放,素材磁带要磨损多次,而机械磨损也是不可弥补的。另外,为了制作特技效果,还必须“翻版”,每“翻版”一次,就

会造成一次信号损失,导致图像质量不高。最

终,为了质量的考虑,你往往不得不忍痛割爱,

放弃一些很好的艺术构思和处理手法。而在非

线性编辑系统中,素材是以数字信号的形式存

入到计算机硬盘中的,采集的时候,一般用分

量采入,或用SDI采入,信号基本上没有衰减。

无论你如何处理或者编辑。拷贝多少次,信号

质量将是始终如一的。当然,由于信号的压缩

与解压缩编码,多少存在一些质量损失,但与

“翻版”相比,损失大大减小。一般情况下,采

集信号的质量损失小于转录损失的一半。由于

系统只需要一次采集和一次输出。因此,非线

性编辑系统能保证你得到相当于模拟视频第二

版质量的节目带,而使用模拟编辑系统,绝不

可能有这么高的信号质量。

②强大的制作编辑功能

使用传统的编辑方法,为制作一个十来分

钟的节目,往往要面对长达四五十分钟的素材

带,反复进行审阅比较,然后将所选择的镜头

编辑组接,并进行必要的转场、特技处理。这

其中包含大量的机械重复劳动。

而非线性编辑系统往往集录制、编辑、特

技、字幕、动画等多种功能于一身,而且可以

不按照时间顺序编辑,它可以非常方便地对素

材进行预览、查找、定位、复制、剪切、粘贴、

设置出点入点等,具有丰富的特技功能,可以

充分发挥编辑人员的创造力和想像力。非线性

编辑系统在实际编辑过程中只是编辑点和各种

效果的记录,因此任意的剪辑、修改、复制、

调动画面前后顺序等操作,都不会引起画面质

量的下降,克服了传统线性编辑设备的致命弱

点。它编辑节目的精度高,可以做到正负0帧,

便于节目内容的交换与交流,对任何一台计算

机中TAG,BMP,FLC,JPG,WAV等格式

的文件,都可以在非线性编辑系统中调出使

用。同时,多种多样、花样翻新、可自由组合

的特技方式,使制作的节目丰富多彩,将制作

水平提高到了一个新的层次。

③运行可靠

从非线性编辑系统的作用来看,它能集录

像机、切换台、数字特技机、编辑机、多轨录

音机、调音台、MIDI创作、时基等设备于一

身,几乎包括了所有的传统后期制作设备。这

种高度的集成性,使得非线性编辑系统的优势

更为明显。因此它能在广播电视界占据越来越

重要的地位,一点也不令人奇怪。非线性编辑

系统对传统设备的高度集成,使后期制作所需

的设备降至最少,有效地节约了投资。

随着技术的发展,非线性编辑系统设备日

趋小型化,且功能集成度高,线路结构简化,

故障率大大降低,运行可靠性大大提高。易于

与其他非线性编辑系统或普通个人计算机联网

形成网络资源共享,使节目制作周期大大缩

短。

④系统功能拓展方便

影视制作水平的提高,总是对设备不断地

提出新的要求,这一矛盾在传统编辑系统中很

难解决,因为这需要不断投资。而使用非线性

编辑系统,则能较好地解决这一矛盾。非线性

编辑系统所采用的,是易于升级的开放式结

构,支持许多第三方的硬件、软件。通常,功

能的增加只需要通过软件的升级就能实现。

⑤网络化优势

网络化是计算机的一大发展趋势,非线性

编辑系统可充分利用网络方便地传输数码视

频,实现资源共享,还可利用网络上的计算机

协同创作,对于数码视频资源的管理、查询,

更是易如反掌。目前在一些电视台中,非线性

编辑系统都在利用网络发挥着更大的作用。

概括地说,非线性编辑系统具有信号质量

高、制作水平高、节约投资、保护投资、网络

化这方面的优越性。

浅谈非线性视频编缉技术

李明君 李艳

(烟台南山学院 计算机应用技术学院 山东龙口 265713)

摘 要:随着电视技术数字化和DV的流行,普及,视频编辑技术的发展也越来越受关注。对视频进行编辑的方式分为:线性编辑和非线性编辑。

关键词:线性 非线性 视频编辑

中图分类号:TP311文献标识码:A文章编号:1674-098X(2008)03(c)-0047-01

的结合。近年来,一些新的智能技术逐渐被引入到路径规划中来,也促使了各种方法的融合发展,例如人工势场与神经网络、模糊控制的结合等。

参考文献

[1]李磊,叶涛,谭民,等.移动机器人技术研究现状与未来.机器人,2002,24(5):475-480.

[2]戴博,肖晓明,蔡自兴.移动机器人路径规划技术的研究现状与规划.控制工程,2005,12(3):199-202.[3]张捍东,郑睿,岑豫皖.移动机器人路径

规划技术的现状和展望.系统仿真学

报,2005,17(2):439-443.

[4]庄慧忠,杜树新,吴铁军.机器人路径规

划及相关算法研究.科技通报,2004,20

(3):210-215.

[5]马兆青.基于栅格方法的移动机器人实

时导航避障.机器人,1996,18(6):344

-348.

[6]袁曾任,高明.在动态环境中移动机器

人导航和避障的一种新方法.机器人,

2000,22(2):81-88.

[7]石鸿雁,孙茂相,孙昌志.未知环境下移

动机器人路径规划方法.沈阳工业大学

学报,2005,27(1):63-69.

[8]L.Podsedkowski,J.Nowakowski,M.

Idzikowski,et al."A new solution for

path planning in partially known or

unknown environment for nonholonomic

mobile robots".Robotics and Autono-

mous Systems,2001,34(2-3):145-152.

47 科技创新导报 Science and Technology Innovation Herald