（控制理论与控制工程专业论文）基于蚁群算法的机器人路径规划及其在港口上的应用探讨.pdf

武汉理工大学硕士学位论文 摘要 由于我国经济的持续快速发展，对外贸易越来越频繁，给港口物流业带来 了前所未有的机遇和挑战。这就需要港口提高效率，加快发展，这就对港口的 自动化作业提出了很高的要求。港口机器人的研究正是基于此背景提出的。 因此，作为机器人智能的一个重要因素路径规划就显得尤为重要。路 径规划是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优 的无碰路径。 移动机器人的路径规划是一种比较典型的优化问题，本身具有复杂性、约 束性、非线性等特点。而港口自身的状况也很复杂，因此要想实现港口机器人 的自主行进，就需要采用一种高效的路径规划算法。 蚁群算法是基于生物界群体启发行为的一种随机搜索寻优方法，它的正反 馈性和协同性使其可用于分布式系统，它在解决组合优化问题上有着良好的适 应性，隐含的并行性更使其具有极强的发展潜力。因此将其应用到智能机器人 路径规划中将有很大的潜力。 本文首先对蚁群算法做了概述，总结了算法的特点和发展趋势。专门编写 了蚁群算法的软件来研究算法中各参数的变化对算法性能的影响。通过大量的 试验，总结出e i l 5 1 t s p 问题取得最优解的最佳参数范围。 然后对目前应用较好的蚁群算法一最大最小蚁群算法做了介绍，重点研 究了算法的收敛性问题，应用极限的思想得到算法在有限次的迭代后，其收敛 概率将达到l ，解决了算法的收敛性问题。 在研究蚁群算法的基础上，利用栅格法建立环境地图，编写了利用蚁群算 法解决机器人路径规划的软件。通过该软件可以在环境地图已知的情况下，快 速规划出一条最优路径。该软件对港口机器人的路径规划做了基础性的工作。 关键词：机器人，路径规划，蚁群算法，收敛性，t s p 武汉理工大学硕士学位论文 a b s t r a e t w i t ht h ec o n t i n u o u sr a p i dd e v e l o p m e n to fo u rc o u n t r y se c o n o m y , t h ef o r e i g n t r a d ei sm o r ea n dm o r ef r e q u e n t l y ，t h i sh a sb r o u g h tt h eu n p r e c e d e n t e do p p o r t u m t y a n dt h ec h a l l e n g ef o rh a r b o rf l o w i n gi n d u s t r y 砘sr e q u i r e st h eh a r b o rt oi m p r o v e t h ee f f i c i e n c y , s p e e du pt h ed e v e l o p m e n t 砸ss e t sav e r yh i 曲r e q u e s tt ot h eh a r b o r a u t o m a t e do p e r a t i o n t h eh a r b o rr o b o tr e s e a r c hi sp r e c i s e l yp r o p o s e db a s e do nt h e b a c k g r o l l i l d t h e r e f o r e ，p a t hp l a n n i n g a sa ni m p o r t a n tf a c t o ri n i n t e l l i g e n tr o b o t 钾e l l l s p a r t i c u l a r l yi m p o r t a n t p a t hp l a n n i n gi st os e a r c hac o l l i s i o n f r e ep a t hf r o mt h es t a r t t ot a r g e tw h i c hi so p t i m a lo rn e a r - o p t i m a lb a s e do ns o m e p e r f o r m a n c ei n d e x p a t hp l a n n i n go f r o b o ti sav e r yt y p i c a lo p t i m i z a t i o np r o b l e mw h i c hh a sm a n y t y p i c a lc h a r a c t e r ss u c ha sc o m p l e x i t y ，r e s t r i c t i o n , n o n - l i n e a ra n ds oo i l b u tt h e h a r b o r sc o n d i t i o ni s v e r yc o m p l e x i no r d e rt o a c h i e v et h eh a r b o rr o b o t i n d e p e n d e n t l yt om a r c hf o r w a r d ，i tn e e d sah i g h l ye f f i c i e n tp a t h p l a n n i n ga l g o r i t h m a na n tc o l o n ya l g o r i t h mi sas t o c h a s t i cs e a r c h i n go p t i m i z a t i o na l g o r i t h mw h i c h i sb a s e do nt h eh e u r i s t i cb e h a v i o ro ft h eb i o l o g i cc o l o n y i t sp o s i t i v ef e e d b a c ka n d c o o r d i n a t i o nm a k ei tp o s s i b l et ob ea p p l i e dt oad i s t r i b u t e ds y s t e m i th a sf a v o r a b l e a d a p t a b i l i t yi ns o l v i n gc o m b i n a t o r i a lo p t i m i z a t i o na n dh a sg r e a td e v e l o p m e n t p o t e n t i a lf o ri t sc o u n o t a l i v ep a r a l l e lp r o p e r t y s oi th a sg r e a tp o t e n t i a lt oa p p l y i n gt h e a l g o r i t h mt ot h ep a t h p l a n n i n go f r o b o t f i 硎孔t h i sp a p e rp r o v i d e sas n l l i n a r yo f a n tc o l o n ya l g o r i t h m ，a n ds u m m a r i z e s t h ec h a r a c t e r i s t i c sa n dt r e n d so ft h ea l g o r i t h m t h es o f t w a r ei sm a d et os t u d yt h e c h a n g e s i nt h e p a r a m e t e r so ft h ea l g o r i t h mp e r f o r m a n c e t h r o u g h al o to f e x p e r i m e n t s s u m m a r i z e st h eb e s t p a r a m e t e ra r e af o rt h ee i l - 5 1 t s p q u e s t i o n t h e nt h i sp a p e ri n d i c a t e st h em a x - m i na n tc o l o n ya l g o d t h mw h i c hi so n eo f t h em o r ee x c e l l e n ta n t c o l o n ya l g o r i t h m s a t p r e s e n t i t s t u d i e s m a i n l y t h e c o n v e r g e n c eo f t h ea l g o r i t h mu s i n gu t m o s tw a y a f t e rf i n i t ei t e m t i v e , t h ep r o b a b i l i t y o f t h ea l g o r i t h mw i l lr e a c h1 s o ，t h ec o n v e r g e n c eo f t h ea l g o r i t h mi ss o l v e d b a s e do nt h es t u d yo fa n tc o l o n ya l g o r i t h m , t h ee n v i r o n m e n tm a pi se s t a b l i s h e d i l 武汉理工大学硕士学位论文 u s i n g 鲥dm e t h o d t h i sp a p e rc o m p i l e st h es o f t w a r et os o l v et h ep a t hp l a n n i n go f r o b o t i f t h ee n v i r o n m e n tm a pi sk n o w n , t h eo p t i m a lp a t ho a nb eb u i l tq u i c k l yb yt h i s s o f t w a r e t h es o f t w a r ed o e saf o u n d a t i o n a lj o bf o rt h eh a r b o rr o b o tp a t hp l a n n i n g k e yw o r d s ：r o b o t , p a t hp l a n n i n g ，a n tc o l o n ya l g o r i t h m , c o n v e r g e n c e ，t s p i i i 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题研究的背景及意义 智能移动机器人是一类能够通过传感器感知环境和自身状态，实现在有障 碍物的环境中面向目标的自主运动，从而完成一定作业功能的机器人系统。近 年来，移动机器人技术在工业、农业、航天及空间探测等许多领域都起到了重 要的作用，同时又显示了广泛的应用前景，因而成为国际学术界研究和关注的 热点问题。 移动机器人主要研究内容包括体系结构、环境建模与定位、路径规划、运 动控制、故障诊断与容错控制掣“。路径规划问题是移动机器人研究领域的重 要内容。对己知静态环境中机器入路径规划的研究已经进行了将近4 0 年，多年 的研究工作在取得进展的同时，愈加证明了路径规划是一个复杂的难题。 所谓路径规划是指移动机器人按照某一性能指标( 如距离、时间、能量等) ， 搜索一条从起始状态到目标状态的最优或近似最优的无碰路径。路径规划主要 涉及的问题包括：利用获得的移动机器人环境信息建立较为合理的模型，再用 某种算法寻找一条从起始状态到目标状态的最优或近似最优的无碰撞路径；能 够处理环境模型中的不确定因素和路径跟踪中出现的误差，使外界物体对机器 入的影响降到最小；如何利用已知的所有信息来引导机器入的动作，从而得到 相对更优的行为决策。 根据机器人对环境信息知道的程度不同，可分为两种类型：环境信息完全 已知的全局路径规划和环境信息完全未知或部分未知，通过传感器在线地对机 器人的工作环境进行探测，以获取障碍物的位置、形状和尺寸等信息的局部路 径规划。全局路径规划包括环境建模和路径搜索策略两个子问题。其中环境建 模的主要方法有：可视图法( v - g r a p h ) 、自由空间法( f r e es p a c e a p p r o a c h ) 和栅格 法( g r i d s ) 等。路径搜索策略主要有：a + 算法、d 最优算法等。局部路径规划的 主要方法有：人工势场法( a r t i f i c i a lp o t e n t i a lf i e l d ) 、遗传算法( g e n e t i ca l g o r i t h m ) 和模糊逻辑算法( f u z z yl o g i ca l g o r i t h m ) 等。 路径规划主要涉及的问题包括：利用获得的移动机器人环境信息建立较为 合理的模型，再用某种算法寻找一条从起始状态到目标状态的最优或近似最优 武汉理工大学硕士学位论文 的无碰撞路径；能够处理环境模型中的不确定因素和路径跟踪中出现的误差， 使外界物体对机器人的影响降到最小；如何利用已知的所有信息来引导机器人 的动作，从而得到相对更优的行为决策。 路径规划算法的计算量取决于任务、环境的复杂性以及对规划路径质量的 要求，一个好的路径规划算法应该兼顾对规划速度和路径质量的期望。随着研 究的深入，各种新的路径规划方法层出不穷，使路径规划研究一直活跃在机器 人学领域。 目前，在移动机器人的路径规划研究领域，除了业已得到公认的遗传算法、 模拟退火法、人工神经网络等热门算法，新加入这个领域的蚁群算法正在开始 崭露头角，为复杂困难的系统优化问题提供了新的具有竞争力的求解算法。尽 管一些思想尚处于萌芽时期，但人们已经隐隐约约地认识到，人类诞生于大自 然，解决问题的灵感似乎也应该来自于大自然。这种由欧洲学者提出并加以改 进的新颖系统优化思想，正在吸引着越来越多的学者的关注和研究，应用范围 也开始遍及到许多科学技术及工程领域。蚁群算法是基于生物界群体启发行为 的一种随机搜索寻优方法，它的正反馈性和协同性使其可用于分布式系统，隐 含的并行性使其具有极强的发展潜力，灵活性使它在解决组合优化问题上具有 良好的适应性，因此将蚁群算法应用于智能移动机器人避障的路径规划问题研 究，能够探索与改进一种新的路径优化算法，促进优化理论与实践的发展，并 且为经济领域以及工程领域的优化问题( 如生产调度、系统控制、物流配送等) 提供借鉴。 港口状况很复杂，作业环境很危险，人车很多，稍有不慎极易发生事故。 而机器人能够始终集中精力，不会出现注意力分散和疲劳的情况，定位精确， 作业效率高。如果港口的各种作业机械改用机器人，利用机器人的这些优势， 必将为港口争取到更大的发展空间。 港口机器人是一种用于自动化或半自动化集装箱码头的集装箱堆场自动搬 运机械，它不需要人员驾驶，所有动作，包括起制动、转弯、减速、道路选择 等功能，都可在远程无线控制下自动完成。由于集装箱码头环境复杂、噪声干 扰大、光线强度变化大、道路相对固定等特殊性，对港口机器人的性能要求也 与一般用途的机器人不尽相同。 目前我国港口的机器人系统应用率很低，主要还是依靠传统的人工决策和 指挥调度方式。随着业务的发展，国内的许多港口企业也在积极的进行自动化 2 武汉理工大学硕士学位论文 改造。在港口实施机器人系统，可以实现港口企业以更低的成本获得更高的生 产效率，同时能营造一个更安全更科学的物流体系，使其在激烈的市场竞争中 全方位地发挥足够的能力从而取得最好的经济效益。机器人系统在港1 2 1 运输中 的应用，还可以改变我国传统的港口运输模式，使其向统筹调度、科学决策的 先进物流模式转化。 丙要实现港口机器人的应用，路径规划就显得十分重要。路径规翔质量的 优劣直接关系到机器人能否安全准确到达预定目标点。蚁群算法是近年来出现 的新型生物算法，它具有很强的鲁棒性且是正反馈机制，自适应性强，通过信 息素的不断更新最终收敛于最优路径上。对解决港口环境的复杂性和多变性很 有针对性，同时能提高港口的生产效率，也能提高国内对研究新型生物算法的 兴趣，因此具有重要的实际意义。 1 2 国内外研究现状及发展趋势 1 2 1 国内外研究现状 ( 1 ) 国外移动机器人的研究现状 自上世纪9 0 年代以来，各国学者尤其是欧美和日本各国的学者，对移动机 器人的研究十分活跃。目前，各种类型和智能水平的移动机器人也已经在工业 生产、日常生活和军事中获得实际应用。 自1 9 6 2 年美国推出世界上第一台u n i m a t e 型和v e r s a t r a 型工业机器人 以来，机器人在工业发达国家得到了迅速发展。尤其是日本发展更为迅猛，拥 有量占全世界机器人总数的5 0 左右，一直保持“机器人王国”地位 2 1 。例如： 安川电机和富士通公司联合开发的送餐机器人可以在医院分送饮食到各个病 床，并在病人用完餐后收回餐具；日本静甲株式会社的清水工厂开发出一种自 动清扫机器人可用于工厂中的清扫工作，采用了光纤陀螺来自主控制机器人的 方向，对地面没有任何要求1 3 l 。除日本外，世界上还有许多工业发达国家，如 美国、俄罗斯和西欧一些国家的机器人产业也发展得很快。尽管美国拥有的机 器人在台数上不如日本，但其技术水平较高，占有一定的优势。从6 0 年代开始， 美国开始研究火星探索用移动机器人，以便在火星上软着陆后进行移动并收集 数据。自1 9 6 5 年美国成功发射水手4 号行星探测器以来，人类就从没放过对火 3 武汉理工大学硕士学位论文 星的探索。1 9 7 6 年7 月和8 月美国的“海盗l 号”和“海盗2 号”，在火星成 功着陆。1 9 9 6 年1 2 月4 日火星探路者登陆器在肯尼迪航天中发射，1 9 9 7 年7 月，在火星上成功着陆后，“索杰纳”漫游车离开登陆器在火星表面漫游，行驶 了几千米，完成了预定的科学探测任务。荷兰鹿特丹港的集装箱码头( e c t ) 、 德国汉堡港a l t c n w c r d c r 集装箱码头( c t a ) 的码头装卸工作均由智能移动机器 人完成【3 】，实现了无入化的码头装卸作业，确保了最高的装卸效率，又维持了 最低的运营成本。 ( 2 ) 国内移动机器人研究现状 与发达国家相比，我国的机器人技术与产业有很大差距，但是随着我国国 民经济的持续发展，适应加快实现经济结构调整和产业升级，提高整个工业的 自动化水平和满足人民生活的需要，我国机器人技术将取得更大的发展。我国 的工业机器人从8 0 年代“七五”科技攻关开始起步，在国家的支持下，通过 “七五”、“八五”，科技攻关，目前己基本掌握了机器人操作机的设计制造技术、 控制系统硬件和软件设计技术、运动学和轨迹规划技术，生产了部分机器人关 键元器件，开发出喷漆、弧焊、点焊、装配、搬运等机器人。但总的来看，我 国的工业机器人技术及其工程应用的水平和国外比还有一定的距离，如：可靠 性低于国外产品；机器人应用工程起步较晚，应用领域窄，生产线系统技术与 国外比有差距；在应用规模上，我国己安装的国产工业机器人约2 0 0 台，约占 全球己安装台数的万分之四【2 】。我国的智能机器人和特种机器人在“8 6 3 ”计划 的支持下，也取得了不少成果。其中最为突出的是水下机器人，6 0 0 0 米水下无 缆机器人的成果居世界领先水平，还开发出直接遥控机器人、双臂协调控制机 器人、爬壁机器人、管道机器人等机种；在机器人视觉、力觉、触觉、声觉等 基础技术的开发应用上开展了不少工作，有了一定的发展基础。国内很多研究 机构如哈尔滨工业大学机器人研究所，东北大学人工智能与机器人研究所，上 海交通大学机器人研究所，北京航空航天大学机器人研究所，西安交通大学人 工智能与机器人研究所，中科院自动化研究所，清华大学，中南大学，浙江大 学等，也重点开展了针对自主移动机器人技术的研究，并在理论研究和实际应 用中都取得了令人瞩目的成果 4 - 6 1 。例如，浙江大学、清华大学、国防科技大 学和南京理工大学等联合研制的a l v l a b 可以在道路环境下高速行进叼；清华 机器入t h m r - v 采用了g p s 、光码盘和磁罗盘等定位技术，从而保证了 t h m r - v 的定位系统精度和可靠性【3 】：上海交大的机器人f r o n t i e ri 自主移 4 武汉理工大学硕士学位论文 动机器人和s m a r tv i s i o n 实时视觉系统 s 】可以作为智能机器人研究和教学的实 验平台，具有良好的稳定性、开放性和可扩展功能。而在服务机器人方面，中 科院自动化所研制的移动机器人c a s i a - - i 由超声和红外传感器、摄像机等组 成，能实现一定的自主性导航。中国海洋大学研制成功的新型导医机器人“导 医小姐”海福利和“护士助手”海乐福，全都采用了红外导航、机器人环境模 式识别的导航技术，达到局部的自主性。哈尔滨工业大学机器入研究所开发的 爬壁机器人，则可用于高空极限作业。 但是在多传感器信息融合技术、遥控加局部自主系统遥控机器人、智能装 配机器人、机器人化机械等的开发应用方面则刚刚起步，与国外先进水平差距 较大，需要在原有成绩的基础上，有重点地系统攻关，才能形成系统配套可供 实用的技术和产品，以期在“十五”后期立于世界先进行列之中【9 1 。 ( 3 ) 蚁群算法研究概况 1 9 9 1 年，m d o r i g o 等提出了一种新型的智能优化算法蚂蚁系统( a n t s y s t e m ，简称a s ) o o l ，该算法首先用于求解著名的旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) ，并取得了较好的效果。近年来，m d o d g o 等 人将蚂蚁算法进一步发展成一种通用的优化技术蚁群优化( a n tc o l o n y o p t i m i z a t i o n , 简称a c 0 ) ，并将所有符合a c o 框架的蚂蚁算法称为蚁群优化算 法( a c oa l g o r i t h m ) ，从而为a c o 的理论研究和算法设计提供了一个统一的框 架i l l 】。实验结果表明a s 算法具有较强的鲁棒性和发现较好解的能力，但同时也 存在一些缺陷，如收敛速度慢、易出现停滞现象等。该算法的出现引起了学者 们的广泛关注，并提出了一些改进的a c o 算法。lm g a m b a r d e l l a ，m d o f i g o 提出了a n t - q 算法，该算法用伪随机比例状态转移规则( p s e u d or a n d o m p r o p o r t i o n a ls t a t e t r a n s i t i o n r u l e ) 替换a s 算法中的随机比例选择规则( s t o c h a s t i c p r o p o r t i o n a lc h o i c er u l e ) ，从而使a n t q 算法在构造解的过程中能够更好地保持 知识探索( e x p l o r a t i o n ) 与知识利用( e x p l o i t a t i o n ) 之间的平衡。除此之外， 该算法中还引入了局部信息素更新机制和全局信息素更新中的精英策略。m d o f i g o 等在a n t q 算法的基础上提出了蚁群系统( a n tc o l o n ys y s t e m ， 简称 a c s ) ，该算法作为a n t - q 算法的特例实现起来更为简单，但在求解t s p 问题 时具有相同的性能。s t t i t z l e 和h o o s 提出了最大一最小蚂蚁系统( m a x m i n a n t s y s t e m ，简称m m a s ) ，该算法的主要特点是为信息素设置上下限来避免算法 出现停滞形象。b u l l n h e i m e r 等提出了基于排序的蚂蚁系统( r a n k - b a s e dv e r s i o n 5 武汉理工大学硕士学位论文 o f a n ts y s t e m ，a s r a n k ) i l l 】，该算法在完成一次迭代后，将蚂蚁所经路径的长度 按从d , n 大的顺序排列，并根据路径长度赋予不同的权重，路径较短的权重较 大，如全局最优解的权重为w ，第r 个最优解的权重为m a x 0 ，w - r 。 国内直到上个世纪末才有学者开始关注a c o 算法，目前对该算法的研究主 要停留在算法的改进和应用方面。吴庆洪和张纪会等【l 通过向基本蚁群算法中 引入变异机制，充分利用2 一交换法简洁高效的特点，提出具有变异特征的蚁群 算法。吴斌和史忠植【l2 】首先在蚁群算法的基础上提出了相遇算法，提高了蚂蚁 一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合，提出一 种基于蚁群算法的t s p 问题分段求解算法。王颖和谢剑英l 通过自适应地改变 算法的挥发度等系数，提出种自适应的蚁群算法以克服限于局部最小的缺点。 覃刚力和杨家本l l ”根据人工蚂蚁所获得解的情况，动态地调整路径上的信息素， 提出了自适应调整信息素的蚁群算法。 随着人们对a c o 研究的不断深入，近年来m d o r i g o 等人1 1 3 】提出了蚁群优 化元启发式( a n tc o l o n yo p t i m i z a t i o nm e t ah e u r i s t i c ，简称a c o m h ) 这一求 解复杂问题的通用框架。a c o m h 为a c o 的理论研究和算法设计提供了技术 上的保障。在a c o 的收敛性方面，w 3 g u t j a l r t “】作了开创性的工作，提出了基 于图的蚂蚁系统元启发式( g r a p h - b a s e d a n t s y s t e m m e t a h e u r i s t i c ) 这一a c o 的 通用模型，该模型在一定的条件下能以任意接近1 的概率收敛到最优解。文献 证明了与模拟退火( s i m u l a t c da n n e a l i n g ，简称s a ) 相似的结果，即算法能以 概率1 收敛到最优解。t s t i l t z l e 和m d o d g o 1 5 】对一类a c o 算法的收敛性进行 了证明，其结论可以直接应用到两类实验上证明是最成功的a c o 算法 m m a s 和a c s 。n m e u l c a l l 和m d o r i g o 1 6 1 研究了随机梯度下降( s t o c h a s t i c g r a d i e n td e s c e n t ，简称s g d ) 和a c o 之间的关系，将a c o 看成是一种近似 的s g d 算法，并根据s g d 实现了理论上收敛的a c o 算法。 对a c o 的应用研究一直非常活跃。继m d o r i g o 首先将a s 算法应用于 t s p 问题之后，v m a n i e z z o 等人将a s 算法应用于指派问题( q u a d r a t i c a s s i g n m e n tp r o b l e m ，简称q a p ) 。最近几年，g a m b a r d e l l a ，t a l l l a r d 和s t i i t z l e ! 1 1 1 也发表了一些用a c o 算法求解q a p 问题的文章。目前，a c o 已是求解q a p 问题最有效的算法之一。 6 武汉理工大学硕士学位论文 表1 1 蚁群优化算法及其应用f l l 】 面向连接豹孵络路由 ( c a n n e c t i a n - l e s sm t w o c k z o u 纽g ) s e c l u e 碰a la r d a i n g s c h a u n d e z w c 目de tl l w l i t e p s 再z e k o p p a c k a d i c a o d c 匝g o b u m b ) a ue t 吐 g m n b s x d e l l s & d m i b o s h 耐。t c 4 。蛳c h e l 腼d d 耐d l f s 嶙o e r s e q u m c e f r e c y e n c y m 斟n e n t m a n e z z o c b u n o 7 a 日c a 3 g a a “时e t - f s a b c 皿n i tt 目血 h ss o p s s c s a n t 譬e a p l 刃6 l 舛8 l 卵8 l 妇8 l 孵7 i g 鳐 1 9 站 武汉理工大学硕士学位论文 续表1 1 蚁群优化算法及其应用【l l 】 g 匝廿a l i z e d u 匝昏孤e t r a m a l h n h o l m 芷m c o s 缸-9 d 鲥a s - g a p 多背包目题叫血t p 扯l i g u i z a 6 n km i c h a l c r i c g a s - 砥 k n a p s a c kp f o b l e m , m 腰) o l 拒c a l 埔锄r a f k - r m i n g l q a v a 曩n y a ：e l a & s 证d - i fa c o - w c v p r e 矗i 丑曲唧| l l 口c 吐l i a a g & s m i t h a c o - r a p c j 虹a i ms a t i l f a c 啪5 0 l n a n 球p - l v h 机器人路径槐匍4 问题金飞毙激炳熔等a c a 数摧挖藕( d a t a m i 血垴 ? m 。1i ：呷妇啦h | 1 t a x 曩a n t - m m h l ，印i - n m 连续蕊数锐化菠锚吴趋追a c a 幕鲵帮 识扛镶，雯胞照a g a c o l o m i 等入【l7 1 首先将a s 算法应用于车间作业调度问题( j o b - s h o p s c h e d u l i n gp r o b l e m ，简称j s p ) 。实验结果表明，该算法虽然能解决j s p 问题， 但同s t a t e - o f - t h e a r t 相比较，并没有任何优势。但在用m m a s 算法求解流动车 间调度问题( f l o ws h o ps c h e d u l i n gp r o b l e m ，简称f s s p ) 时，实验结果显示 m m a s 算法优于模拟退火和禁忌搜索算法。 c o s t a 和h e r z i s 提出增强的a s 算法，并将其应用于分配问题。该算法在求 解图的着色问题时，得到了完全可以和其它启发式算法相媲美的结果。 b u l l n h e i m e r ，h a r t l 和s t r a u s s h 佣算法a s r a n k 来求解车辆路径问题( v e h i c l e r o u t i n gp r o b l e m s ，简称v r p ) ，取得了和最优解非常相近的结果。近几年， g a m b a r d e l l a ，t a i l l a r d 和a g a z z i l l l j 对v l 冲问题的研究，对一些基准问题 ( b e n c h m a r kp r o b l e m ) 的最优解有所提高。 a c o 在通讯网络领域( 特别是解决网络路由问题) 的应用受到越来越多的 学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与a c o 非 常相似，如利用局部信息发现解，间接的通讯方式和随机状态的转换。1 ) ic a r o 和d o t i g o i 】己在相关的文献中将a c o 应用于网络路由问题，并称这种算法为 a n t n e t 。 除了各种组合优化问题之外，a c o 算法还在函数优化、系统辨识、机器人 路径援划、数据挖掘、大规模集成电路中的综合布线设计等领域取得了弓1 人注 目的成果，表1 1 列举了有代表性的蚁群算法及其应用情况。 8 鲫 脚 嘞 嘲 姗 凇 凇 嬲 姗 武汉理工大学硕士学位论文 1 2 2 发展趋势 移动机器入领域近些年有以下发展趋势： ( 1 ) 工业机器人性能不断提高( 高速度、高精度、高功能性，便于操作和 维修) ，而单机价格不断下降。 ( 2 ) 机械结构向模块化、可重构化发展。 ( 3 ) 控制系统向基于p c 机的开放性控制器方向发展，其成本低，具有 标准网络功能，大大提高了系统的可靠性、易操作性和可维修性。 ( 4 ) 有视觉、声觉、听觉、触觉等传感器的融合技术的传感器数量呈上升 趋势，多传感器融合配置技术，在产品化系统中已有成熟应用。 ( 5 ) 虚拟现实技术在机器人中的作用，从仿真预演发展到用于过程控制。 ( 6 ) 移动机器人的多机协调，从策略角度共同完成分配的任务一直是研究 的热点。多机器人协调控制也是发展方向，由予同时有多个相互协作机器人的 参与，这就对创建地图、定位、路径规划和多机器人协调控制提出了更高的要 求。目前多机器人系统的研究尚处于理论研究阶段，多机器人系统体系结构与 协作机制、信息交互以及冲突消除等方面将是多机器人系统的进一步研究方向。 ( 7 ) 机器人化机械开始兴起。从1 9 9 4 年美国开发出“虚拟轴机床”以来， 各国纷纷探索开拓其实际应用的领域。 生物算法近年来发展迅速，发展潜力很大。然而不少算法在一定程度上存 在搜索空间大、算法复杂、效率不高等问题。特别是当障碍物的数目增加或地 形障碍趋于复杂时，不少路径规划算法的复杂度会大大增加，甚至无法求解。 如基于遗传算法的机器人路径规划方法，该方法对规划环境中的路径进行编码 构成遗传个体，在进行选择、交叉、变异等遗传操作时要加很多的约束条件。 当环境趋于复杂、障碍物数目增加时，约束条件就会很复杂，甚至对有些问题 无法求解。如何降低算法的复杂度，提高效率就是需要继续研究的方向。 对蚁群算法来说，虽然蚁群算法在理论和实际应用方面均取得了较大的成 果，但是算法的数学基础仍不牢固，如算法的收敛性问题还没有完全解决；另 外，对算法中各参数之间的关系还没有定量的结论，因此在对算法进行仿真时， 只能依靠经验对参数不断尝试来得出较优的解，这就大大影响了算法的效率。 在这些方面还是值得继续加以研究的。 9 武汉理工大学硕士学位论文 1 3 本论文课题来源、研究内容和主要内容 在机器人学的诸多研究领域中，路径规划是十分重要的。它直接关系到机 器人能否到达目标位置，是实现运动和其他任务的基础，并且有较强的工程背 景，涉及较多的领域，是个具有重要研究价值的课题。本课题正是基于这一 背景提出的，课题来源于学科建设科研项目。 本论文主要是研究蚁群算法及其在智能移动机器人路径规划技术方面的应 用及其相关领域的一些问题。在研究蚁群算法的基础上，重点研究蚁群算法的 收敛性问题，特别针对m m a s ，编写了专门软件来研究并总结了要使算法得到 最优解，所需设定的最佳参数对范围。最后开发了采用蚁群算法解决机器人路 径规划问题的软件，通过设置最佳参数，快速计算出最优的规划路径，能使机 器人沿较优的路径到达目标点。 本文的主要结构如下： 第l 章：阐述了本文研究工作的意义，移动机器人及其路径规划的一些概 念、方法和发展趋势，并对蚁群算法做了概述，介绍了本课题的背景来源。 第2 章：蚁群算法研究，介绍了蚁群算法的起源、发展及存在的问题，并 归纳了目前主要的蚁群优化算法，特别针对目前最好的蚁群优化算法m m a s 进 行研究，编写了研究蚁群算法的软件，研究了各参数对算法性能的影响，总结 归纳了e i l 5 1 t s p 问题取得最优解的最佳参数范围。 第3 章：利用概率的方法详细研究了m m a s 的收敛性问题。 第4 章：机器人路径规划概述，介绍了机器人路径规划的分类，所采用的 方法，并对各种方法进行了比较。 第5 章：基于蚁群算法的机器人路径规划仿真研究，针对前面对蚁群算法 的研究，编写了机器人路径规划软件，特别针对港口的对象要求做了试验，试 验结果表明，该软件可以快速规划出较优的路径。 第6 章：最后对全文进行总结，给出下一步研究方向。 1 0 武汉理工大学硕士学位论文 2 1 概述 第2 章蚁群算法研究 入工智能在经历了上个世纪8 0 年代整整l o 年的繁荣后，由于方法论上始 终没有突破经典计算思想的藩篱，再次面临着寒冬季节的考验f 1 9 】。以p e n r o s e 等为代表的各种反思和批驳论著纷纷涌现，人工智能的研究前景又一次变得暗 淡无光。与此同时，随着人们对生命本质的不断了解，生命科学却以前所未有 的速度迅猛发展，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索 起新的非经典计算途径。正如人工智能先驱m i n s k y 所认为的“我们应该从生 物学而不是物理学受到启示”【1 9 】那样，对生物启发式计算( b i o i n s p i r e d c o m p u t i n g ) 的研究，成为人工智能迎接新曙光而开启的又一个春天。 在这种背景下，社会性动物( 如蚁群、蜂群、鸟群等) 的自组织 ( s e l f - o r g a n i z a t i o n ) 行为引起了人们的广泛关注，许多学者对这种行为进行数 学建模并用计算机对其进行仿真，这就产生了所谓的“群集智能”( s w a r m i n t e l l i g e n c e ，简称s i ) 。社会性动物的妙处在于：个体的行为都很简单，但当它 们一起协同工作时，却能够“突现”( e m e r g e ) 出非常复杂( 智能) 的行为特征。 例如，单只蚂蚁的能力极其有限，但当这些简单的蚂蚁组成蚁群时，却能完成 像筑巢、觅食、迁徙、清扫蚁巢等复杂行为；一群行为显得盲目的蜂群能造出 精美的蜂窝；鸟群在没有集中控制的情况下能够同步飞行等。 在这些自组织行为中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物 源的最短路径最为引人注目。受其启发，意大科学者m ，d o r i g o ，vm a n i e z z o 和a ，c o l o m i 于2 0 世纪9 0 年代初提出了一种新型的智能优化算法一蚂蚁系 统( a n ts y s t e m ，简称a s ) ，该算法首先用于求解著名的旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ，简称t s p ) 并获得了较好的效果。在上个世纪9 0 年代中 期，这种算法逐渐引起了许多研究者的注意，并对该算法作了各种改进或将其 应用于更为广泛的领域，取得了一些令人鼓舞的成果 2 0 1 。近几年，m d o r i g o 等 人将蚂蚁算法进一步发展成一种通用的优化技术蚁群优化( a n tc o l o n y o p f i m i z a t i o 也简称a c o ) ，并将所有符合a c o 框架的蚂蚁算法称为蚁群优化 算法( a c oa l g o r i t h m ) ，从而为a c o 的理论研究和算法设计提供了一个统一 武汉理工大学硕士学位论文 的框架。w j g u t j a h r 首先对a c o 的收敛性进行了探讨，取得了一些初步的结 果，目前已有少量文献涉及a c o 的收敛性【2 1 啦】，但还很不成熟。对a c o 的 应用研究一直非常活跃，目前该算法已在求解组合优化、函数优化、系统辨识、 机器人路径规划、数据挖掘、网络路由等问题时取得了较好的效果田】。 目前，a c o 在启发式方法范畴内已逐渐成为一个独立的分支，在有关国际 会议上多次作为专题加以讨论，如t 9 9 8 年、2 0 0 0 年、2 0 0 2 在比利时布鲁塞 尔大学召开了三届a c o 国际研讨会( a n t s 9 8 ，a n t s 2 0 0 0 ，a n t s 2 0 0 2 ) ， 第四届a c o 国际研讨会于2 0 0 4 年9 月在同一地点举行【l l 】，会上就s i 算法、 a c o 算法和群集机器人技术( s w a r mr o b o t i c s ，简称s r ) 进行了讨论。另外 a n t s 2 0 0 6 也将于2 0 0 7 年9 月4 7 日在布鲁塞尔大学举行。 尽管目前对a c o 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已 隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然， 因此，越来越多入开始关注和研究a c o ，初步的研究结果已显示出该算法在求 解复杂优化问题( 特别是离散优化问题) 方面的优越性。虽然a c o 的严格理 论基础尚未奠定圈，国内外的有关研究仍停留在实验探索阶段，但从当前的应 用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景。 2 2 蚁群算法原理及算法描述 2 2 1 蚁群的自组织行为 自然界中蚁群的自组织行为很早就引起了昆虫学家的注意。d e n e u b o u r g 等 通过“双桥实验”对蚁群的觅食行为进行了研究。如图2 1 ( a ) 所示，对称双 桥( 两座桥的长度相同) a 、b 将蚁巢与食物源分隔开，蚂蚁从蚁巢自由地向 食物源移动。图2 1 ( b ) 是经过a 、b 两桥的蚂蚁百分比随时间的变化情况。 实验结果显示，在初始阶段出现一段时间的震荡( 由于某些随机因素，使通过 某座桥上的蚂蚁数急剧增多或减少) 后，蚂蚁趋向于走同一条路径。在该实验 中，绝大部分蚂蚁选择了a 桥。 在实验初期，a 、b 两座桥上都没有外激素存在，蚂蚁将以相同的概率选 择a 、b 两座桥，故此时蚂蚁在两座桥上留下的外激素量相等。经过一段时间 后，由于随机波动致使大部分蚂蚁选择了a