启发式路径搜索算法研究综述
维普资讯 doc.guandang.net
电脑知识与技术
。
。究开发。研
启发式路径搜索算法研究综述 吕太之。伟李 (南京理工大学,苏南京 2 09 )江 10 4
摘要:述了一类在真实世界中用于路径规划的启发式路径搜索算法。述了这些算法的异同,类算法主要包括静态算法( A )描论这如, 动态算法 ( D )A yi如 , nt me算法 ( A *。本文的目的在于讨论它们在现实机器人系统中的应用,及各自的优缺点。如 RA )以 关键词:动机器人;局路径规划;移全 A; D Lt; yi p in i An t e meRe ar gA i
中图分类号: P 4 T 22
文献标识码: A
文章编号:0 9 3 4 (0 61一 P P C 1 0— 0 42 0 )4 P P— O A iet u it— a e t a nn Gud o He i b s d Pah Pln ig r c s LV i hi e Ta—z,LIW i
( mp t stt o@n iesyo c n e n eh o g, Nig2 9, ia Co ue I tue f r n i Na gUnvrt f i c dT cn l y Na n 10 4 n) i S e a o 0 Ch Ab ta t e d sr e a fmi f e e t e eo e e r t— ae l o t msu e o ah p a n n n t e r a wo l, W e ds u st e s r c: ec b a l o c n l d v lp d h u i i b s d ag r h s d f rp t l i g i h e l W i y r y sc i n r d i s h c
fn a na s l ie bt e t i a oi ms(g A ) y af loi ms e ., n t lo tms(. A _ ) a dayi l— u dme t i a t s ewens t l rh l miri ac g t e .,dnn ca rh (.D ) ayi a rh . i g t g me g i e . RA, n n t a o g me g rh (. AD ) W eit d c h t ao eidec ls f lo tms i us hi ueo e o oi ss ms adhgl h e i ms e . r u et moi t nb hn ahc s o g rh,d cs te s nra rb t yt, n i i thi
t g no e vi a a i s r l c e hg t r p a t a e e t a d d sd a tg s rci l c b n f s n i v n a e . i a
K y wo d: b er b t go a p t ln ig A D Lt An t eR e ar; e r s mo i o o; lb l ah pa nn;: l i e: yi p i A m
1引言 自主移动机器人就是具有感知能力,以布有障碍物的环境可中面向日标自主运动,而完成一定任务的机器人系统。近年来。从 机器人系统在各个领域的研究应用极大的改善了人们的生活。它不仅应用于.业系统 . 1:同样在家务活动,医疗保健等领域也开始发挥作用在移动机器人相关技术研究巾 .径规划是一个重要的研究路领域。所谓路径规划是指移动机器人存有障碍的环境中,找一寻
探测器检测到实际的环境和已知的环境信息存在差异时,更新则
原有的环境地图信息,么原先规划的路径也许就是不可通的或那 者不是最优的。此时,以根据更新的环境信息重新规划一条从可机器人当前所在位置到目标点的新的路径,是代价很大。据于但 此,nh n tnz提出的动态 A}算法或者叫 D A toySet¥算法, ong和 K ei Lk ah v出了 D i算法『,。 ihc e提 Lt e 56 1 C n uchrs a 0 o ̄ t o ̄Pt S tt h 0 . hl(∈0 E )≠s 1 w i s P N( ) l e p 0 . a v tr 2 Rcno ̄sa ̄sfo tefo t f r m h r n ' o OPE N;
条从起始点到终点的路径,这条路径不仅要使机器人躲避障碍, 而且要在一定指标卜如距离、 I能量等 )可能的优化 I o f时训、尽 1
o.0. C d ho( 3f I EN gbr) rl , 0 .fg 9 g 4 i( ( ( s) 0 0+c’' I
2静态算法 Djsa2算法可以说是最为经典、用最为广泛的路径搜索 i t[ kr]应 方法该算法计算图中每个结点到目标点的路径。它的主要特点
0.’ g+c 0; 5 O ( ) 0 .n e i oO E 6 i,r n P Nwi a ̄ ( ,t t t l f 9: hv u s Ma 0 n i 0
. o n0∈ S 7 fra
是以初始结点为巾心向外层层扩展 .直到扩展到目标结点为止。 Djsa算法能得出最短路径的最优解,但由于它遍历计算的结 i t kr
点很多,以效率低。其算法的时问复杂度是 On )所 (2。 A算法其计算方法基本上等同于 Djs a法 .是在扩展 i t算 kr只 结点时加入丁砰价函数【,】A 34。算法为搜索过程中所涉及到的每
0.窖 )。 8 (。 。; 0.( ) 0 9gⅢ=; 1. 0 OPE q; a:
个节点 S定义一个评价甬数:s g )hs )示表示从起始节 v ) (+ (,s:s )表点 st t节点 s s r经 a V到目标节点 sol ga的最短路径的估计值。其中 g( S从起始节点 s at当前节点 S的实际可行最短路径的长 )是 s r到 t度。(依赖于问题的启发式信息,为启发函数,当前节点 s hs 1称是到目标节点 sol ga的最短路径的估计。首先令所有节点的 gs。。 (=。然 )后令 g( tr= s at 0并将其放人 O E s ) P N表巾,人 O E放 P N表中的每个节点按照“)值排序,节点“) s的将 s最小的放在队首。接 F来,次每取出 O E表中队首的节点 s如果其相邻节点 s的 gs大于当 PN, ()
1 . s' s t t O E wt v u ( 5+ l h 1 i t l i o P n a sm n t N i M ̄ g. h (Ⅻ) l一 ( ) 1 . o u ̄h r s a 0 2 C mp tSot t t; ̄Ph 图 1正向 A 算法 (起始节点向目标节点 )从
D和 D t算法是对 A e算法的扩充,以此来处理环境信息的改变。这两种算法是比较接近的,文只讨论 I e算法。本 ) i It 首先用反向 A算法构造一条从起始节点到目标节点的最优路径。当环境信息改变时,新路径代价,将受影响节点放人更并
前节点 g )l ( ̄上两节点之间边的代价 cs就更新 g。这个过 s/ l (S,,) () s 群持续去,到队首节点 s是目标节点的 sol具体算法见直 ga。 图 l。
O E P N表中,并将影响传播给相关节点,因此只处理部分节点,效
率提高很多。具体算法见罔 2。。 但是在有的情况下,当环境信息改变时。新路径代价是多余更
同样的 . A在算法中也可以改变搜索的方向,可以从目标节点向起始节点搜索 .作反向 A称算法。
3动态算法 上面提到的两种算法在环境信息完全已知的情况下,以运可行良好。但是在实际情况中,这种情况是不大可能的,器人所拥机有的信息 是不完整或不准确的。这时如果装备在机器人上的般 收稿日期:0 6 0—0 20— 3 9
的。比如说所有路径代价增长的节点之间边都在当前规划路径以 外且没有任何节点之间的边代价减少时。但是为了保证路径在未来仍然是最优的,管当前路径还是最优的, Lt法照样更新尽 D i e算其路径代价。为了克服 D i算法的这个缺点,eg sn和 Set Lt e F ruo t z n提出了 D l e 算法【】个算法的核心就足当环境信息改变 e ydD a 7。这时,是马上更新路径,是积累到一定程度时才更新路径。不而
作者简介:吕太之,,士研究生,男硕高级工程师,究方向模式识别与人工智能;伟,,士研究生,究方向模式识别与研李男硕研 人工智能。
13 O
doc.guandang.net
基于增量启发式搜索的动态车辆路径规划算法的研究与实现_机械/仪表_工程科技_.....21.3路径规划算法研究现状………31.3.1静态路径规划算法研究现状……….31...
地图中最短路径的搜索算法研究综述_学习总结_总结/汇报_应用文书。关于深度优先...至于A*算法,它是一种启发式搜索算法, 也是一种最好优先的算法,它适合于小...
对于更大规模的 VRP, 研究者主要通过构造启发式算 法来求解。本文综述了近...VRP 建立了一个确定的动态规划模型并设计了一个基于最短路径搜索算法的精确算法...
启发式最短路径算法研究 ——以庐山路网寻径为例 摘要:最短路径算法的效率是...[7]吕太之,李伟.启发式路径搜索算法研究综述..1009—3044(2006)14一PPPP— ...
车辆路径问题的模型及算法研究综述_理学_高等教育_... 启发式算法 0 引言 车辆路径问题 (Vehicle Routing... 线性搜 索技术 、 列生成技术 、 拉格朗日松弛...
清华大学自动化系,北京 100084) 摘要:车辆路径调度问题是一类具有重大研究意义及... 启发式算法主要是基于直观或者凭借经验, 开发出能够朝着最优解的方向搜索或...
游戏中路径搜索算法研究_专业资料。路径搜索是游戏中非常重要的一部分,A21第10 2年 0期 计算机与现代化 JUNIYUXADIU IAJS INAHA 总第 26期 0 文章编号 :0627...
“ 相关技术” 研究项目 (No . 20036040) ) 作者简介 : 王景存 (1963 — ,男 ,副教授 ,博士研究生 1 HOPA 算法 111 启发式路径搜索( heuristic pathf ...
最后展望了该领域的未来研究方向。 关键词 启发式; 分层; 大规模网络; 最优化...2.3 双向搜索 在经典最短路径算法中搜索是单方向的,算法 的执行时间取决于...
最后展望了该领域的未来研究方向。 关键词 启发式; 分层; 大规模网络; 最优化...2.3 双向搜索 在经典最短路径算法中搜索是单方向的,算法 的执行时间取决于...
热门文档