研究了任意点对的平面避障问题.用凸多边形表示障碍物,凸多边形的集合构成障碍环境.在此基础上,提出了一种新的路径规划思路:对图结构进行扩展,用传统的Floyed算法进行一级规划;对传统Floyed算法扩展后进行二级规划,很好地解决了任意点对的平面避障问题.利用矢量间夹角的关系来判断障碍环境中点对的连线是否交叉于多边形.经理论证明和算例验证,该算法方便简洁,容易实
维普资讯 doc.guandang.net
第3卷第 3 4期 2 0芷 3 06月
华中
科
技
大
学
学
报 (自然科学版)
Vo . 4 No 3 13 . M a. 2 6 r 00
J Hu z o g Unv fS i& Te h ( t r ce c io ) . ah n i.o c. c . Nau eS in eEdt n i
避障问题最短路径的两级动态规划算法 戴 杜 王茂 彭 光明安红才雷 ( 1中国地质大学计算机学院,湖北武汉 4 0 7; 3 0 4
2安徽师范大学数学计算机学院,安徽芜湖 21 0) 40 0
摘耍:研究了任意点对的平面避障问题.用凸多边形表示障碍物,凸多边形的集合构成障碍环境 .此基础在上,提出了一种新的路径规划思路:图结构进行扩展,对用传统的 Fo e算法进行一级规划; l d y对传统 Fo e算 lyd 法扩展后进行二级规划。好地解决了任意点对的平面避障问题 .用矢量间夹角的关系来判断障碍环境中很利
点对的连线是否交叉于多边形.经理论证明和算例验证,该算法方便简洁,容易实现,明了算法的正确性.表 关键词:多边形;态规划;前 ( )点 f级动态规划凸动后拐两 文献标识码: A文章编号:1 7—5 2 2 0 ) 30 2—3 6 14 1 (0 6 0—1 20中田分类号: P 9 . 7 T 3 17
Alo ih fa t -e e y m i a ni g o h g rt m o wo lv ld na cpl n n ft e s o t s a h i v i n b t c e h r e t p t n a o di g o s a l s Da a g n DuA n o g W a g M a c i Pe g Le i Gu n mi g h n n oa n i Ab t a t s r c:Th v i i g o s a l s o l n r p i t r t d e . Pl n r o s a l s we e e p e s d b e a o d n b t c e f p a a o n s we e s u id a a b t c e r x r s e y c n e o y o s a d t e ro s a l se v r n e twa o s r c e y c n e o y o e s On t e b— o v x p lg n n h i b tce n i m n sc n t u td b o v xp lg n s l.
o; h a ss o h d l e ag rt m sp e e t d t l n t e s o t s a h I h l o ih,t et a i i f emo e。a n w l o ih wa r s n e o p a h h r e tp t . n t e a g rt m t h r d— t n l o e l o ih wa s d t l n t e f s—e e p t y e t n i g t e g a h s r c u e Th i a y d a g rt m s u e o p a h i t lv l a h b x e d n h r p t u t r . o Fl r e
s c n—e e p t sp a n d b x e dn h o e lo ih . Th v ii g o sa lso ln r e o d lv l a h wa ln e y e t n i g t e Fly d ag rt m e a odn b tce fp a a p i t o l e c mp e e y t e ag rt m . Th n l o e t r s u e o e tma e wh t e h o n sc u d b o lt d b h l o ih e a g e fv c o s wa s d t s i t e h r t e l e b t e WO p i t n t eo s a l n io m e t r s e h o y o s i e we n t o n si h b t ce e v r n n o s d t e p l g n .Th t o ssm p e o— n c e me h d i i l,c n v n e ta d e s o i lm e t Th o r c n s f t e a g rt m n t p l a i n w e e p o e y e in n a y t mp e n . ec re t e so h lo i h a d is a p i t r r v d b c o t e re nd il s r to . h o is a lu t a i ns
Ke o d:c n e o y o y w r s o v x p l g n;d n mi l n i g;fo t l b c ) i fe i n;t—e e y a c p a n n y a c pa n n r n a ( a k n lxo wo l v l n mi l n i g d Da a g n i Gu n mi g P o . S h o f o r f; c o l o C mp t r Ch n Un v r iy f Ge s i n e, W u a 3 0 4, ue, i
a i e st o o c e c s hn 4 07 Ch n . i a
2…,且 P+=P ), m 是构成多边形的 m个顶点.
1基本概念 避障问题在机器人运动规划、维动画以及三 虚拟现实中都有着极重要的应用[ .文研究的 1本]
若线段 P 1P卜与PP所形成的内角 ( 即该多边
形围成的有界区域内所形成的角 )大于 10,不 8。 则称点 P为凸点, 否则称为凹点; m个顶点都若是凸点,则称该多边形为凸多边形 ( 3, m≥ )用 表示, O={ P,, . 0是凸多边形即 k P,… P}设的集合, 0一{ k 1 2…, )即 (一,, n . l
是任意点对的平面避障问题,凸多边形表示障用碍物,多边形的集合构成障碍环境,凸在此基础 上,出了一种新的路径规划思路.提 定义 1设 P一 (,,,∈R (一1 五 Y) ( Y)。f,
在本研究中,凸多边形逼近平面障碍物的用 边界 .某一直线障碍物, m一 2时可认为是凸对即
收稿日期:2 0—32. 0 50—4
作者简介:戴光明( 9 4)男, 16一,教授{武汉,中国地质大学计算机学院 ( 3 0 4 40 7 ) E ma: md i c g e u c - i g a@ u . d . n l
基金项目:湖北省自然科学基金资助项目 ( 0 3 A0 5 . 2 0 AB 4 )

2006 避障问题最短路径的两级动态规划算法戴光明 1 杜安红 2 王茂才 1 彭 雷 1 ( 1 中国地质大学 计算机学院, 湖北 武汉 430074; 2 安徽师范大学 数学...
障路径规划转化为一个多阶段决策问题,对于每一个阶段的子问题,应用改进可视图法和几何逼近算法 进行求解,得出各阶段的最短路径,最后对避障路径规划进行动态规划求解...
对在障碍物环境下求任意两点间的最短路径问题进行了剖析。 提出了一种与传统 Fy 算法不同的不破坏障碍物整体信息的“ dleo 两级动态规划求最短避障路径” ...
避障问题最短路径的两级... 3人阅读 3页 2.00 一种动态限制搜索区域...o42 Jl,01 uy20 求解最 短路径 问题 的D A动态规划算法 N 李步军 ,王...
10.期刊论文 戴光明.杜安红.王茂才.彭雷.Dai Guangming.Du Anhong.Wang Maocai.Peng Lei 避障问题最短路径 的两级动态规划算法 -华中科技大学学报(自然科学版)...
动态规划算法实现多段图的最短路径问题算法设计与分析实验报告_其它_高等教育_...问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。 2....
最短路径Floyd算法动态规划问题及其程序设计_计算机软件及应用_IT/计算机_专业资料。最短路径动态规划问题及其程序设计,Floyd算法最短路径动态规划问题及其程序设计 林...
利用动态规划算法求解最短路径_专业资料。动态规划是研究一类最优化问题的算法。... 避障问题最短路径的两级... 3人阅读 3页 2.00 一种动态限制搜索区域...
本文利 用遗传算法,对基于机器视觉的移动机器人的实时 动态避障路径规划进行了研究,将复杂的二维路径 编码问题简化为一维,并把路边约束、动态避障和最 短路径要求...
利用动态规划算法求解最短路径_梁娟_城乡/园林规划_工程科技_专业资料。第 14...2. 新乡市消防支队, 河南 新乡 453002) 摘要: 动态规划是研究一类 最优化问题...
热门文档