（计算机软件与理论专业论文）避障路径规划的算法研究.pdf

华 中 科 技 大 学 博 士 学 位 论 文 摘要 避障路径规划问题是在具有障碍物的环境中，按照某个评价标准 ( 如最短路径 长度、最短行进时间、最小能量消耗等) ，规划一条从起始点位置到达目 标点位置最 优 ( 或次优)的无碰 ( 避障)路径。 避障路径规规划问题在机器人学、 v l s i 、地理信 息系统等众多领域有着广泛的应用，其主要内容涉及环境表达、规划方法、 路径搜索 以及人工智能等多 个学科。 关于避障路径规划高效算法的研究长期以来一直受到人们 的关注和重视， 人们从多方面进行了 探索和研究， 虽取得了一些成果， 但仍存在许多 问题有待深入研究。 以“ 可视图”模型为基础，应用 “ 智能计算” 、“ 两级动态规划”以及 “ 最小任 意四边形包围盒” 等方法从理论和应用两个层面研究避障路径规划算法。 取得的结果 不仅可直接应用于避障路径规划算法的设计与实现， 而且还可应用于计算几何中相关 问题的求解。因此，研究工作具有重要理论意义和实际应用价值。 采用 “ 可视图” 表达环境、建立环境模型，将避障路径规划中最优路径问题转 化成为从起始点到目 标点经过可视直线的最短路径问题，使之成为研究工作的基础。 在对求解t s p 问题的g t 算法进行了细致分析和对比了t s p问题与避障路径规划 问题的异同点之后，引入了 “ 基因库”概念，对g t算法进行了改造，成功地将其用 于求解避障路径规划问题。 此外， 给出了一个问题规模和初始种群规模关系的数学公 式，通过问题规模来确定种群规模;在初始染色体选择时，利用 “ 凸点法”的结论， 避免了无效和盲目 地选择。这一系列措施提高了演化的效率。 对在障碍物环境下求任意两点间的最短路径问题进行了剖析。 提出了一种与传统 f l o y e d 算法不同的不破坏障碍物整体信息的“ 两级动态规划求最短避障路径” 的 算法。 该算法从本质上反映了在这种较为复杂的环境下全局优化与局化优化的统一。此外， 在求解图的成本矩阵方面， 构造了一种新的算法， 算法过程更直观和易于理解。 经理 论 证明 和实 验计 算 表明 结 论正 确。 算 法的 时间 复 杂 度。 ( n 3 ) ( n 是 可视图 的 顶 点 数) 虽 和f l o y e d 算法相同， 但本算法新颖的设计思路是一种创新。 为了降低避障路径规划的算法复杂度，除研究新的高效算法外， 另一种有效途径 是在保证规划路径精度的前提下， 减小构成障碍物边界的点数。 障碍物常表达成封闭 轮廓线 ( 凸多边形) ，构造包围封闭轮廓最小面积包围盒就是解决这个问题的有效方 法。 包围盒是计算几何中的基本问 题之一。 除在路径规划方面的应用之外， 包围盒问 一-一一一 一 一 一 一 一. 一 . 一 一 晌 一 t 华 中 科 技 大 学 博 士 学 位 论 文 题在碰撞检测、实时漫游及视区裁剪等研究中也有着广泛的应用。 在分 析现 有算法 ( 1 9 7 5 年由n e w y o r k 大学的 两 位学 者h .f r e e m a n , p . s h a p i r a 提 出的方法)的基础上，对求封闭轮廓线的最小矩形包围盒的算法进行了研究。 提出了 封闭轮廓线最小矩形包围盒的数学分析方法。 在解的搜索域上也进行了研究并根据所 得到的结论对现行算法进行了改进。 凸多边形最小面积任意四边形包围盒问题在计算几何中是有更广泛意义的论题。 经过严格的数学推理演绎， 较为系统地得到了包括 “ 凸多边形的最小面积四边形包围 盒的四边都是多共点边，或三边是多共点边而另一边 ( 单共点边)中点与凸多边形的 一 顶点 重 合” 等一 系 列重 要结 论。 依 据 此 结论 设 计了 时 fa j 复 杂 性 为o ( m 4 ) ( m是问 题 规模，凸多边形的顶点数)的算法，解决了“ 凸多边形最小面积任意四 边形包围盒” 这个在理论上和实际应用中都具有重要意义的问题。 相关各类算法都经过了程序运行结果的验证，达到了预期的效果。 关 键词: 避 障 路 径 规 划， 遗 传 算 法， 两 级 动 态规 划， 凸 多 边 形， 可 视图 ， 包围 盒 一 一巨 一一. 一一-一 n 华 中 科 技 大 学 博 士 学 位 论 文 ab s t r a c t a v o i d a n c e o b s t a c l e p a t h p l a n n i n g p r o b l e m i s a b l e t o b e s t a t e d a s f o l l o w s : i n o b s t a c l e e n v i r o n m e n t , b a s e d o n a c e rt a i n e v a l u a t i o n c r i t e r i o n ( s u c h a s t h e s h o r t e s t l e n g t h o f p a t h , t h e s h o rt e s t t i m e o f m o v in g , t h e m i n i m a l c o n s u m in g o f e n e r g y , a n d s o o n ) , f r o m s t a rt p o i n t t o d e s t i n a t i o n p o i n t , p l a n s a o p t i m a l ( o r s u b - o p t i m a l ) c o l l i s i o n f r e e p a t h . i t h as u n i v e r s a l a p p l i c a t i o n s i n m a n y f i e l d s , s u c h a s r o b o t i c s , v l s i s d e s i g n , g i s , e t c . t h e m a i n c o n t e n t s r e l a t e t o m a n y s u b j e c t s , f o r e x a m p l e e n v i r o n m e n t r e p r e s e n t in g , p l a n n i n g m e t h o d , p a t h s e a r c h i n g a n d a r t i f i c i a l i n t e l l i g e n c e . r e s e a r c h e r s a r e a l w a y s c a r i n g f o r a n d t h i n k i n g m u c h o f t h e s t u d y o f h i g h - p o w e r e d a l g o r it h m f o r a v o i d a n c e o b s t a c l e p a t h p l a n n i n g . t h r o u g h e x p l o r a t i o n a n d r e s e a r c h i n m a n y a s p e c t s , s o m e f r u i t s a r e o b t a i n e d , b u t t h e r e a r e p l e n t y o f p r o b l e m s n e e d e d t o l u c u b r a t e b as e s o n t h e m o d e l o f v i s i b i l i t y g r a p h , u s e s t h e m e t h o d s o f i n t e l l i g e n t c a l c u l a t i o n , t w o l e v e l d y n a m i c p l a n n i n g , a n d t h e m i n i m a l a r b i t r a ry q u a d r a n g l e e n c a s i n g b o x , e t c ., s t u d i e s t h e a lg o r i t h m f o r p l a n n i n g p a t h o f a v o i d a n c e o b s t a c l e a t t w o l e v e l s o f t h e o ry a n d a p p l i c a t i o n . t h e o b t a i n e d r e s u l t s c a n n o t o n l y b e e n a p p l i e d t o t h e d e s i g n a n d i m p l e m e n t a t i o n o f a l g o r i t h m f o r a v o i d a n c e o b s t a c l e p a t h p l a n n in g , b u t a l s o b e e n u s e d t o s o l v e t h e p r o b l e m s o f c o m p u t a t i o n a l g e o m e t ry . s o , t h i s s t u d y h a s t h e i m p o r t a n t t h e o ry s i g n i f i c a n c e a n d t h e p r a c t i c a l a p p l i c a t i o n v a l u e t h e v i s ib i l i t y g r a p h i s u s e d t o r e p r e s e n t e n v i r o n m e n t a n d c o n s t r u c t t h e m o d e l o f e n v i r o n m e n t i n t h i s p a p e r , th e o p t i m a l p a t h p r o b l e m o f a v o i d a n c e o b s t a c l e i s t r a n s f o r m e d i n t o t h e p r o b l e m o f s h o rt e s t p a t h t h r o u g h v i s i b i l i t y l i n e f r o m s t a rt p o i n t t o d e s t i n a t i o n p o i n t , t h i s i s t h e b a s e o f t h e r e s e a r c h t h e d i f f e r e n c e o f g t s a l g o r i t h m f o r t s p i s c a r e f u l l y a n a l y z e d , c o m p a r e s t s p w i t h a v o i d a n c e o b s t a c l e p a th p l a n n in g p r o b l e m , i n t r o d u c e s g e n e b a s e i n t o t h e p r o b l e m , m e n d s t h e g t s a l g o r i t h m , a n d s u c c e s s f u l l y u s e s i t t o s o l v e t h e a v o i d a n c e o b s t a c l e p a t h p l a n n i n g p r o b l e m . a d d i t i o n a l l y , m a t h e m a t i c s f o r m u l a a b o u t t h e r e l a t i o n o f p r o b l e m s i z e a n d i n i t i a l p o p u l a t i o n s i z e i s p r e s e n t e d ; d u r i n g s e l e c t i n g t h e i n i t i a l c h r o m o s o m e , i n v a l i d a n d s i g h t l e s s s e l e c t i o n i s a v o i d e d b y u s i n g c o n v e x p o i n t m e t h o d . a l l t h e s e m e a s u r e s . i m p r o v e t h e e v o l v i n g e f f i c i e n c y . a n a n a l y s i s o f t h e s h o rt e s t p a t h p r o b l e m b e t w e e n tw o a r b i t r a r y p o in t s i n t h e o b s t a c l e e n v i r o n m e n t i s a l s o s u b m i tt e d . t h i s p a p e r p r e s e n t s a n a l g o r i t h m e n t i t l e d a s a t w o - l e v e l d y n a m i c s h o rt e s t p a t h p l a n n i n g a l g o r i t h m t o o b s t a c l e a v o i d a n c e , w h i c h d o e s n o t d e s t ro y th e in t e 幼t y i n f o r ma t i o n o f o b s t a c l e , a n d i s d i f f e r e n t fr o m t h e t r a d i t i o n a l f l o y e d a l g o r it h m . i i i 华 中 科 技 大 学 博 士 学 位 论 文 t h e a l g o r i t h m e s s e n t i a l l y r e fl e c t s u n i f i c a t i o n o f g l o b a l o p t i m i z a t i o n a n d l o c a l o p t i m i z a t i o n in t h i s v e ry c o m p l e x e n v i r o n m e n t . i n a d d i t i o n , a n e w a l g o r i t h m i s c o n s t r u c t e d t o s o l v e c o s t m a tr i x o f g r a p h , t h e c o u r s e o f t h a t a l g o r it h m i s m o r e i n t u i t i v e a n d e a s i e r t o u n d e r s t a n d . c o r r e c t n e s s o f t h e a l g o r i t h m s r e s u l t i s p r o v e d t h r o u g h t h e o r e t i c t e s t i 尔n g a n d e x p e r im e n t a l c o m p u ti n g . t i m e c o m p l e x it y o f a l g o r ith m p r e s e n t e d in th is p a p e r i s o ( n ) ( n is t h e n u m b e r o f o b s t a c l e s v e rt i c e s , i n c l u d i n g s t a rt i n g p o in t a n d d e s t i n a t i o n p o in t ) , s a m e a s f l o y e d a l g o r i t h m s t i m e c o m p l e x it y , b u t i d e a s o f t h e a l g o r i t h m i n t h i s p a p e r i s i n n o v a t iv e . i n o r d e r t o r e d u c e a l g o r i t h m s t i m e c o m p l e x it y o f a v o i d a n c e o b s t a c l e p a t h p l a n n i n g , o n e w a y i s t o s t u d y n e w mo r e e f f e c t i v e a l g o r i t h m , a n d t h e o t h e r e f f e c t i v e w a y i s t o d e c r e a s e v e rt i c e s o n b o u n d a ry o f o b s t a c l e s o n t h e p r e m i s e o f g u a r a n t e e i n g t h e p r e c i s i o n o f p a t h p l a n n i n g . o b s t a c l e i s u s u a l l y r e p r e s e n t e d a s c l o s e c o n t o u r l i n e ( i . e . c o n v e x p o l y g o n ) , c o n s t r u c t i n g m i n i m a l a r e a e n c a s i n g b o x b e s i e g i n g t h e c l o s e c o n t o u r i s o n e e f f e c t i v e m e t h o d t o s o l v e t h e p r o b l e m . e n c a s i n g b o x p r o b le m i s a b a s a l p r o b l e m o f c o m p u t a t i o n a l g e o m e t r y . b e s i d e s b e i n g a p p l i e d i n p a t h p l a n n i n g , e n c a s i n g b o x p r o b l e m h a s b r o a d a p p l i c a t i o n i n c o l l i s i o n d e t e c t i n g , r e a l t i m e r o a m i n g , v i s u a l r e g i o n c l i p p i n g , e t c . c u r r e n t l y , m e t h o d p r e s e n t e d b y h .f r e e m a n a n d p .s h a p i r a 1 9 7 5 , i n n e w y o r k u n i v e s i t y i s u s e d t o o b t a i n m i n i m a l a r e a r e c t a n g l e e n c a s i n g b o x o f c lo s e c o n t o u r l i n e . t h i s p a p e r a l s o r e s e a r c h e s t h e p r o b l e m , a n d p u t s f o r w a r d m a t h e m a t i c s a n a l y z i n g m e t h o d f o r o b t a i n i n g m in i m a l a r e a r e c t a n g l e e n c a s i n g b o x o f c l o s e c o n t o u r l i n e . a ft e r s t u d 如 n g s o l u t i o n s e a r c h i n g f i e l d , t h i s p a p e r i m p r o v e s t h e h .f r e e m a n a n d p .s h a p i r a a l g o r i t h m . r e s e a r c h i s e m p h a s i z e d o n a n y m i n i m a l a r e a r e c t a n g l e e n c a s i n g b o x o f c o n v e x p o l y g o n p r o b l e m , w h i c h i s a u n i v e r s a l p r o b l e m i n c o m p u t a t i o n a l g e o m e t ry . t h r o u g h s t r i c t r e a s o n i n g a n d d e d u c t i n g , s e r i e s o f i m p o rt a n t c o n c l u s i o n s , s u c h a s f o u r e d g e s o f c o n v e x p o l y g o n s m i n i m a l a r e a r e c t a n g l e e n c a s i n g b o x a r e a l l e d g e s s h a r e d b y m a n y v e rt i c e s , o r t h r e e e d g e s a r e e d g e s s h a r e d b y m a n y v e rt i c e s , m i d d l e p o in t o f a n o t h e r e d g e ( s h a r e d b y s i n g l e v e rt e x ) s u p e r p o s e s o n e v e rt e x o f c o n v e x p o l y g o n , a r e s y s t e m a t i c a l l y g a i n e d . b a s e d o n th e a b o v e c o n c lu s io n s , a l g o r ith m w it h o ( m ) t im e c o m p le x i t y , is p r e s e n t e d . t h is a l g o r i t h m s u c c e s s f u l l y s o l v e s a n y m i n i m a l a r e a r e c t a n g l e e n c a s i n g b o x o f c o n v e x p o l y g o n p r o b le m , w h i c h h a s i m p o rt a n t s i gni f ic a n c e b o t h i n t h e o ry a n d p r a c t i c a l a p p l i c a t i o n . r e l a t e d a l g o r i t h m s a r e v e r i f i e d b y t h e r e s u l t s o f p r o g r a m s , a t t a i n i n g t o t h e r e q u i r e m e n t . k e y wo r d s : a v o i d a n c e o b s t a c l e p a t h p l a n n i n g , g e n e t i c a l g o r i t h m , t w o l e v e l d y n a m i c p l a n n i n g , c o n v e x p o l y g o n , v i s i b i l i t y g r a p h , e n c a s i n g b o x i v 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的 研 究 感 一果 。 尽 我 所 知 ， 除 文 中 己 经 标 明 引 用 的 内 容 外 ， 本 论 文 不 包 含 任 何 其 他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体， 均己在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 学 位 论 文 作 二 名 :剑 2,t 日 期:2 0 4 年v-月 绍日 学位论文版权使用授权书 本学位论文作者完全了 解学校有关保留、使用学位论文的规定，即: 学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和 借阅 。 本 人授 权华中 科技 大 学 可以 将本 学 位论 文 的 全 部 或部 分内 容编 入 有关 数 据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在_年解密后适用本授权书。 本论文属于 不保密回a ( 请在以上方框内打 “ 学位论文作者签名: 日 期 : p o i 年华 月 z g a指 导 教 师 签 名 滩 峙 日 期: x 0 4 年伞月= s日 办 、肋戊、日 ”六钊表 户、 华 中 科 技 大 学 博 士 学 位 论 文 1绪论 1 . 1本文的研究目的 本文的研究目的在于: 1 、在有障碍物的环境中，从起始点到目 标点之间规划一条与环境障碍无碰路径 的问 题是 机器人设 计、 v l s i 设计和 地理 信息系 统中的 基本问 题 1 - 9 。 本文 将演化算 法 最新研究成果应用到避障路径规划问题中， 探索提高避障路径规划演化算法效率的途 径。 2 、 在凸多边形障碍物环境中， 求任意两点间 最短路径问 题， 通常是利用最优性 原 理 构 造 递 推关 系 式， 利 用f l o y e d 算 法 进行 求 解。 在 深 入分 析凸 多 边 形障 碍 物 环 境中 求任意两点间 最短 路 径问 题的 特点 基 础上， 对f lo y e d 算法进行了 改 造， 最终给出 了 一 个称为两级动态规划的算法。 两级动态规划算法原理是从局部优化结果产生全局最优 结果，能够有效求解凸多边形障碍物环境中的任意两点间最短路径。 3 .避障路径规划及多边形碰撞检测等问题的算法复杂性都与多边形障碍物的顶 点 数相 关 12 )6 7 )8 。 减 少 障 碍物 多 边形的 顶点 数， 成为 提 高 算法 效率的 一 种 途 径。 本 文在提出凸多边形障碍物最小面积四边形包围盒概念的基础上， 经过严格的数学推理 得到了关于凸多边形最小面积四边形包围盒的一个重要结论，并据此结论，设计了求 任意凸多边形最小面积四边形包围盒的算法，从而为实际应用提供了理论依据。 1 . 2选题的背景与意义 在有障碍时 求两 点间的 最短路径是机器人路 径规划、 v l s i 设计和 地理信息系统 等领域的基本问题p -9 1 避 障 路 径 规 划 是 机 器 人 应 用中 的 一 项 重 要 技 术 6 1 。 例 如: 在 执行 装 配、 焊 接 及 抢 险 救灾 等 任务时 ， 采 用良 好的 机 器人 路 径 规 划技 术 可以 节 省 大量 机 器人 作 业的 时 间 、 减 少 机 器 人 磨 损， 同 时 也 可以 节 约 人 力 资 源， 减 小 资 金 投 入， 为 机 器 人 在 多 种 行 业 的 -一一. 一一- 1 华 中 科 技 大 学 博 士 学 位 论 文 应用奠定理论基础。随机器人学发展，在上个世纪七十年代就提出了避障路径规划问 题。 到目 前为止已经提出了各种各样的v l s i 电路模型，但是它们绝大多数和普遍使 用的栅格模型( g r i d m o d e d 都具有很多共同 之处。在栅格模型中， 通常使用一个矩形 栅，电路的各种导线只能沿着栅线 ( 或称格边) 走线， 或水平走向， 或垂直走向。 这 样在v l s i 设计中，布线空间为m 、 的有限网格，电路元件和已布好的线成为新的布 线障碍。如何安排元件布局，即芯片的合法平面嵌入和布线问题，这本质上也是避障 路径规划问 题z 1 。因此对有障碍时两点间最短路径问 题的 求解对 v l s i 设计问 题的解 决有重要意义。在地理信息系统 ( g i s )中，规划两点间的避障最优路径也是其基本 应 用 之 一 3 14 1 由于路径规划问题的复杂性，不同的研究者从不同的角度研究某一方面的问题， 对具体问 题的提法也不完全相同 10 - 1 5 1 。 避障路径规划典型的 描述是: 在有障碍物的环 境中，如何寻找从起始点到目 标点的运动路径且无碰撞地通过所有障碍物。 路径规划问题涉及环境表达、 规划方法和路径搜索策略。 环境表达研究如何将环 境信息有效地表达出来; 规划方法关心的是在环境表达的基础上而进行的数学模型的 抽象;路径搜索策略指的是求解路径函数的方法技术。 路径规划属于组合优化的范畴。 在一定的环境表达和规划方法的基础上， 仅从路 径搜索策略上来分析，可将搜索策略区分为三大类。 第一类是局部优化算法， 它的做 法是牺牲解的搜索空间来获取解的搜索时间， 典型的方法有:最速下降法、部分贪婪 算法 ( 如凸点法 1 3 b等; 第二类是全局优化算法， 它以 获取全局最优解为目 的， 主要 的 算 法 有 16 1 : 单 源 最短 路 径的d ij k s t r a 算 法 d 7 l 、 任意两 点间 最短 路 径的f l o y e d 动 态 规 划算法、 a * 搜索算法等; 最后一类是计算智能方法口 “ 。 由于路径规划问题具有系统的复杂性、描述的不准确性、 环境变化的随机性及优 化的多 约束和多目 标的要 求，常常使得传统的 数学优化方法显得无能为力。 近 3 0年 来， 人们从不同的角度出发对生物系统及其行为特征进行了模拟， 产生了一些对现代 科技发展有重大影响的新兴学科，开发出了具有较强通用的计算、优化模式和方法。 这些方法包括: 遗传算法、 禁忌搜索、 模拟退火和人工神经网 络等算法; 及与模糊逻 辑相结合快速高效地追求计算结果的思想。 这些新的优化方法和思想目 前在理论上还 远不如传统优化方法完善， 往往也不能确保解的最优性，因而常常被视为“ 只是一些 启发式方法” 。但从观念上看，它们突破了传统优化思维的束缚，例如遗传算法模拟 生物种群繁殖中的竞争思想，以及不以数学上的精确解为目 标的思想等， 都是观念上 的创新， 非常有价值。从实际应用的 观点看， 这类新算法不要求目 标函数和约束的连 . - - - - - z 华 中 科 技 大 学 博 士 学 位 论 文 续性与凸性， 甚至连有没有解析表达式都不要求;对计算中数据的不确定性也有很强 的适应能力， 计算速度快， 这些宝贵的优点使这类算法在很短时间里得到了 广泛的应 用， 展 示出 方 兴 未 艾的 强 劲 发 展势头 1 9 遗传算法是一个群体优化过程，为了得到目 标函数的最小 ( 大) 值，它不是从一 个初始值出发，而是从一组初始值出发进行优化。这一组初始值好比一个生物群体， 优化的过程就是这个群体繁衍、 竞争、 遗传和变异的过程。 遗传算法的一个突出 优点 是有较好的稳健性。 事实上，遗传算法并不能保证达到全局优化，它仍然可能陷入局部极值的陷阱。 而实际上，由于遗传算法引入了多个自 变量，新的目 标函数是原来的目 标函数在单个 自 变量对应的函数值中的最小 ( 大) 值，从而使得陷入局部极值陷阱的机会相对变小 ( 其实，新的目 标函数达到最小值的点集相对于极值点集变大了) ，优化结果会有所 改进。 在进化策略上， 人们又提出了在父代和子代间也引入竞争，即不是简单地用子 代代替父代，而是选取它们中较优者作为下一步的父代。 在遗传算法中还可以引入变 异，即在优化过程中以小概率不按局部优化的方向进行。 从局部看，这种演化似乎反 而 “ 劣化”了目 标函数，但正是这种操作才为逃出局部极值的陷阱提供了可能性。又 由于可以 控制 “ 劣化”的变异只以很小的概率发生， 在计算了 很多步后，总趁势是向 优化发展的。 此外，由于遗传算法是一组结构 ( 变量) 一起演化，是群体的优化，可 适合并行处理。 在避障路径规划 ( 特别是机器人路径规划)中，由于某种原因，对周围环境和障 碍物的信息把握常常是局部的。 在这种情形下， 路径规划的结果就是局部优化的结果。 如何使局部优化的结果逼近全局优化的 解， 一种较为自 然的考虑就是在路径规划过程 中将每个障碍物做为一个整体对象进行分析。 分析全局最优解的结构，了解局部优化 的结果与全局优化结果的关系，以利于寻求路径规划新算法。 目前求封闭轮廓线矩形包围盒方法是 h .f r e e m a n . p . s h a p i r a算法。论文对 h .f r e e m a n . p .s h a p i r a 算法进行了 深入地分析， 缩小了 解域的 搜索空间。 据此设 计的 算法提高了求解封闭轮廓线矩形包围盒问题的效率。 避障路径规划与多边形碰撞研究有密切的关系。 多边形碰撞检测在机器人行走控 制、计算机图形学等众多领域中都有广泛的应用。因此研究确定它们的快速算法， 具 有理论和实际意义。 设p = ( p o ,p l , . . . ,p . - l ) 与q - ( q o , q , . . . q m - ) 是平 面内 任意两个互 不相交的凸 多 边形， 为 了 确定凸多边形p 与q的可碰撞区域， 依赖于求解凸多边形p 与q的斜支撑线。 文 献 2 0 等给出了 一 个复 杂 度为。 ( n l o g m ) 的 求斜支撑线 算法， 文献 2 1 等给出了 一个复 杂 3 华 中 科 技 大 学 博 士 学 位 论 文 度为o ( n + m ) 的 算 法， 而 文献 7 侧给出了 一 个 复 杂 度为o ( l o g z ( n + m ) ) 的 求 斜 支 撑 线 快 速算法。 从目前避障路径规划和多边形碰撞检测算法的研究来看， 算法的复杂度都与障碍 物多边形的顶点数密切相关。 在尽可能保持多边形包围盒精度的前提下， 在环境模型表达上，如何减少各障碍 物的顶点数，成为提高这类问题算法效率的另一途径。基于这样的考虑，激发了作者 对 “ 凸多边形最小面积四边形包围盒算法”的研究。 相信其中的研究成果同时对计算 儿何等相关研究也会有一定的理论和实际应用价值。 1 . 3本文的主要工作及结构安排 本文的研究工作是在导师李庆华教授指导下完成的。主要工作包括: 1 、按可视图的理论，首先讨论了 避障路径规划中的有关问题。较详细地给出了 将障 碍 物环境表 达转化为“ 可视图” 的 过 程， 用d ij k s t r a 算法进 行避障 路 径规划。 这 步工作是避障路径规划研究工作的基础。有了该方法的实验结果， 其它算法的实验结 论就有了对比的依据。 2 、利用遗传算法新的研究成果来解决避障路径规划问 题，包括种群规模、 初始 种群的选择、利用求解 t s p问题十分有效的演化算法 ( 郭涛 g t )算法)的思想进 行染色体演化。通过这些工作为遗传算法在避障路径规划中的深入研究莫定了基础。 3 、 传统的求任意两点间最短路径问 题的动态规划算法是f l o y e d 算法， 本文通过 避障问题的特殊性进行分析，提出了一种被称为两级动态规划的算法。这种算法和 f l o y e d 算法不同 之处在于，它将一个障 碍物看作一个整体。 保护了障 碍物的整体性， 理论和实例表明，算法思路新颖，结论正确。 4 、 封闭轮廓线最小面积矩形包围 盒算法一直沿用h .f r e e m a n , p .s h a p ir a 算法， 本 文在深入研究了这个问题后，改进了这个算法。同时，重点对凸多边形的任意四边形 最小面积包围盒进行了深入和系统的研究， 经过严格的数学推导，得出了一系列重要 结论。这些工作无论对丰富计算几何学内容还是在实际应用中都具有十分重要的意 义。 全文共分8 章，具体内容安排如下: 第1 章是绪论， 在本章中论述了避障路径规划问 题的涵义; 详细地讨论了选题的 背景及本文所做的研究工作的意义;介绍了论文的主要工作及论文结构安排。 4 华 中 科 技 大 学 博 士 学 位 论 文 第2 章首先给出了 论文中常见符号的约定: 然后重点介绍避障路径规划问 题的由 来、数学表述及避障路径规划问题的国内外研究现状。 第3 章对 “ 可视图” 法作了系统的表达和实现。 本章的工作是本文研究工作的起 点。 第4 章在分析了遗传算法后， 指出了用遗传算法解决避障路径规划时所存在的问 题。重点在群体规模、初始种群选择和演化策略等方面引用了遗传算法最新的成果。 这些工作为进一步深化遗传算法在避障路径规划中的应用有指导意义。 第5 章对障碍物环境中任意两点间最短路径问题展开研究。 提出了两级动态规划 算法，通过最优性原理分析和实验计算，表明算法的正确性。此外，在求取可视图的 成本矩阵时，提出了一个新颖的算法。本章的研究思路具有明显的创新。 第 6章在系统地介绍和分析了封闭轮廓线最小面积矩形包围盒算法后，对 h .f r e e m a n . p .s h a p ir a 算 法 进 行了 研究， 利 用 研 究 结 果改 进了 该 算 法。 第7 章重点讨论了凸多边形最小面积任意四边形包围盒问题。 通过严格的数学证 明， 得出了一系列重要结论， 从理论上根本解决了 这个计算几何学的问题。 不论在理 论上和实际应用中，本章研究所得到的结论都有重要意义。 第 8 章是论文主要工作总结，同时对近期进一步要开展的研究工作做了展望。 1 . 4小 结 本章是绪论部分， 着重介绍了论文的研究目的、研究背景、研究工作的意义， 对 论文的组织安排也做了说明。 第 1 节简要介绍了本文的研究目的。 第2 节介绍了本文的选题背景、依据及意义。 第 3 节简要的介绍了论文所完成的主要研究内容和论文的内容组织。 本章是本文的开篇。 . . . . . . 目. ，目 5 华 中 科 技 大 学 博 士 学 位 论 文 a预备知识 2 . 1符号约定 起始点s 及目 标点g ; v 。 是所有障碍物的顶点构成的 集合; 图g ( v ,e ) ， 顶点 集v = v o u s ,g ) , e 为 所 有弧 段 ( v ;,v ;) 即 边 集合 ， 其中 连 接g中 第i 和第j 个结点的线段与任何障碍物均不相交。因为图中 相邻的 顶点能相互看到， g ( v ,e ) 称为可视图。 v 二 ( v i ， 1 = 0 ， 1 ， n 一 1 ) ; n 为g的顶点总数; c o s t n n 为图g的成本矩阵; 图g的 边成本表示为d ( v ;,v j ) ( 简 记为d ;j ) ; o是多边形障碍物的集合，o ; 代表编号为i 的障碍物。 m ; 为编号为i 的障碍物的顶点数; k代表障碍物个数; v n ( x ;j ,y ij) 表 示 第i 个障 碍 物多 边 形的 第j 个 顶点 坐 标; s ;, s ， 表示染色体，s 为染色体集合; f ( 5 ;) 第i 条染色体的 适应度; g e n e d b 基因库数组; n为 种群s ( t ) 的大小; g * = ( v * , e * ) 是一种扩展的图结构， 一 其中v * = ( o ;lo ; e o , i = 1 ,2 , . . . k ) , k是图g * 的 结点数。又设c * 是g