文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 避障问题最短路径的两级动态规划算法
侵权投诉

避障问题最短路径的两级动态规划算法

研究了任意点对的平面避障问题.用凸多边形表示障碍物,凸多边形的集合构成障碍环境.在此基础上,提出了一种新的路径规划思路:对图结构进行扩展,用传统的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 )

避障问题最短路径的两级动态规划算法

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email