沈阳工业大学硕士学位论文摘要机器人学的一个最终目标是能制造出自治型机器人，如果将机器人看作是一种能够 扩展人类工作能力的有效工具，那么人类在认识和改造世界的过程中就不能没有机器人。工业机器人是机器人家族中的一个重要分支，是机器人领域的重要研究发展方向。因此，对工业机器人运动路径规划的研究，一直受到人们的普遍关注。基于最少时间、最少能量和避障等的不同目标，许多研究学者对路径规划问题进行 了探索。本文针对近年来在工业机器人路径规划的热点问题一机器人作业中避障的快速性与路径的最优性一进行了系统而深入的研究。前者由于机器人构型空间的复杂性与机器人作业的快速性要求，而使路径规划问题具有极大的挑战性；后者则因为机器人作业的精确性要求，所以从此角度对路径的最优性进行了探索与研究。本文主要研究如下几个问题：１ ．针对６自由度的工业机器人，建立了工业机器人的运动学模型。本文中，建立了两类工业机器人的运动模型：其一为ＡＢＢ ＩＲＢ１４００型工业机器人：另一为ＲＫ１ ０Ｓ型工业机器人，这两类机器人皆是典型的ＳＣＡＲＡ型工业机器人。２．为避免繁琐的机器人示教过程，从避障快速性的角度出发，提出了离线的基于 波扩散方法的工业机器人路径规划算法。首先对机器人的工作空间离散化，针 对工作空间中的障碍点和自由点进行二值标记；然后用波扩散方法对自由点进 一步标记，并进行了路径搜索；最后，以波扩散法与深度优先算法路径搜索进 行了比较。针对６一自由度的工业机器人验证所提出的算法，得到了满意的效 果。以ＡＢＢ ＩＲＢ １４００型６－ＤＯＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶＩ ＳＩＯＮ仿真环境下进行仿真。从仿真结果看，所研究算法在机器人路径规划方面是可行的。 ３．针对机器人作业中的精确性的要求，本文基于孤岛搜索策略，提出了在机器人 的构型空间中采用遗传算法进行路径规划找出最优路径的方法。以ＲＫ１ ０Ｓ型６－ＤＯＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶＩ ＳＩＯＮ仿真环境下进行沈阳工业大学硕士学位论文仿真。从理论分析和仿真实验结果的一致性，证明了算法的有效性和合理性，因而该方法在路径规划方面是可行的。本课题得到国家自然科学基金（课题号：６９９７５０２０）的资助关键词：工业机器人，路径规划，波扩散方法，深度优先算法，孤岛搜索策略，遗传算法 沈阳工业大学硕士学位论文Ｐａｔｈ－ｐｌａｎｎｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｒｅｓｅａｒｃｈ ｏｆ Ｉｎｄｕｓｔｒｉａｌ ＲｏｂｏｔｓＡｂｓｔｒａｃｔＯｎｅ ｏｆ ｔｈｅ ｕｌｔｉｍａｔｅ ｇｏａｌｓ ｉｎ Ｒｏｂｏｔｉｃｓ ｉｓ ｔｏ ｃｒｅａｔｅ ａｕｔｏｎｏｍｏｕｓ ｏｒｂｏｔｓ． Ｓｉｎｃｅ ｏｒｂｏｔ ｃａｎ ｂｅｖｉ ｅｗｅｄ ｓａａ ｎ ｅｆｅｃｔｉｖｅ ｅｘｔｅｎｓｉｏｎ ｏｆ ｈｕｍａｎ＇ｓ ｍｏｔｏｒ ａｂｉｌｉｔｙ， ｉｔ ｉｓ ｓｕｅｒｔ ｏ ｂｅ ｉｎｄｉｓｐｅｎｓａｂｌｅ ｉｎ ｔｈｅｃｏｕｒｓｅ ｏｆ ｅｒｃｏｇｎｉｔｉｏｎ ａｎｄ ｅｘｐｌｏｒａｔｉｏｎ ｏｆ ｔｈｅ ｗｏｒｌｄ． Ｄｕｅ ｔｏ ｉｔｓ ｉｍｐｏｒｔａｎｔ ｏｒｌｅ ｉｎ ｔｈｅｏｒｙａ ｎｄ ａｐｐｌｉ－ｃａｔｉｏｎ， ｔｈｅ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ ｏｆ ｉｎｄｕｓｔｒｉｌａｏｒ ｂｏｔ ｈａｓ ｂｅｅｎ ｇｉｖｅｎ ｅｎｏｕｇｈ ａｔｔｅｎｔｉｏｎ勿ｒｅｓｅａｒｃｈｅｒｓｉ ｎ ｔｈｅ ｗｏｒｌｄ． Ｍａｎｙ ｅｒｓｅａｒｃｈｅｒｓ ｈａｖｅ ｂｅｅｎ ｉｎｖｅｓｔｉｇａｔｅｄ ｏｎ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ｖａｒｉｏｕｓ ｏｂｊｅｃｔｉｖｅｓ ｓｕｃｈａｓ ｍｉｎｉｍｕｍ ｔｉｍｅ， ｍｉｎｉｍｕｍ ｅｎｅｒｇｙ， ａｎｄ ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ． Ｔｗｏ ｍａｉｎ ｐｒｏｂｌｅｍｓ ｈａｖｅ ｂｅｅｎｓｔｕｄｉｅｄ ｏｎ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ｉｎｄｕｓｔｒｉｌａｒｏ ｂｏｔ ｉｎ ｅｒｃｅｎｔ ｙｅａｒｓ． Ｏｎｅ ｐｒｏｂｌｅｍ ｉｓ ｔｈｅ ｏｂｓｔａｃｌｅａｖｏｉｄａｎｃｅ ｓｐｅｅｄｉｎｅｓｓ ｏｆ ｔｈｅ ｏｒｂｏｔ ｄｕｒｉｎｇ ｉｔ＇ｓ ｗｏｒｋｉｎｇ； ｔｈｅ ｏｔｈｅｒ ｐｒｏｂｌｅｍ ｉｓ ｈｏｗ ｔｏ ｇｕａｒａｎｔｅｅｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｐａｔｈ ｗｅ ｓｅａｒｃｈｅｄ． Ｏｗｉｎｇ ｔｏ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅａｎｄ ｔｈｅ ｓｐｅｅｄｉｎｅｓｓ ｏｆ ｔｈｅ ｏｒｂｏｔ＇ｓ ｗｏｒｋｉｎｇ ｄｅｍａｎｄ， ｔｈｅ ｆｏｒｍｅｒ ｈａｓ ｈｕｇｅ ｃｈａｌｌｅｎｇｅ ｆｏｒ ｔｈｅ ｐａｔｈｐｌａｎｎｉｎｇ ｏｆ ｔｈｅ ｒｏｂｏｔ； ｔｈｅ ｌａｔｅｒ ｈａｓ ｍｕｃｈ ｄｉｆｉｃｕｌｔｙ ｆｏｒ ｔｈｅｅｒａ ｅｒｌ ｏｔｓ ｏｆ ｌｉｍｉｔｓ ｅｒｌａｔｉｎｇ ｔｏ ｔｈｅｔｉｍｅ ｕｓｅｄ ｔｏ ｓｅａｒｃｈ ｔｈｅ ｏｐｔｉｍｉｚｉｎｇ ｐａｔｈ． Ｔｈｅ ｍａｉｎ ｅｒｓｕｌｔｓ ａｓ ｔｈｅ ｆｏｌｌｏｗｉｎｇ：１ ． Ｂｕｉｌｄ ｔｈｅ ｍｏｔｉｏｎ ｍｏｄｅｌ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ６ ＤＯＦ ｉｎｄｕｓｔｒｉｌａｏｒ ｂｏｔｓ． Ｏｎｅ ｉｓ ｔｈｅ ｍｏｔｉｏｎｍｏｄｅｌ ｏｆ ｔｈｅ ＡＢＢ ＩＲＢ１４００ ｉｎｄｕｓｔｒｉｌａｏｒ ｂｏｔ ｗｈｏｓｅ ｊｏｉｎｔｓ ａｅｒａｌ ｌ ｏｒｔａｔｉｎｇ； ｔｈｅ ｏｔｈｅｒ ｉｓ ｔｈｅ ｍｏｄｅｌｏｆ ｔｈｅ ＲＫ ｌ ＯＳ ｉｎｄｕｓｔｒｉｌａ ｏｒｂｏｔ ｗｈｉｃｈ ｉｓ ｓｉｍｉｌａｒ ｔｏ ｔｈｅ ＡＢＢ ＩＲＢ １４００ ｉｎｄｕｓｔｒｉｌａｒ ｏｂｏｔ．２． Ｉｎｓｔｅａｄ ｏｆ ｕｓｉｎｇ ｔｈｅ ｔｅｄｉｏｕｓ ｐｒｏｃｅｓｓ ｏｆ ｒｏｂｏｔ ｔｅａｃｈｉｎｇ， ａｎ ｏｆｆ－ｌｉｎｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｌａｇｏ－ｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｗａｖｅ ｅｘｐａｎｓｉｏｎ ｍｅｔｈｏｄ ｈａｓ ｂｅｅｎ ｄｅｖｅｌｏｐｅｄ ｆｏｒ ｉｎｄｕｓｔｒｉｌａｏｒ ｂｏｔｓ． Ｔｈｅ ｃｏｎｔｉ－ｎｕｏｕｓ Ｃａｒｔｅｓｉａｎ Ｗ－ｓｐａｃｅ ｉｎ ｗｏｒｌｄ ｃｏｏｒｄｉｎａｔｅｓ ｉｓ ｄｉｓｃｅｒｔｉｚｅｄ ｉｎｔｏ ａｎ ｅｑｕｉｄｉｓｔａｎｔ ３Ｄ－ｇｒｉｄ ａｎｄｔｈｅｎ ｔｈｅ ｆｅｒｅ ｐｏｉｎｔｓ ａｎｄ ｏｂｓｔａｃｌｅ ｐｏｉｎｔｓ ａｒｅ ｉｎｄｉｃａｔｅｄ ｂｙ ｄｉｆｅｒｅｎｔ ｎｕｍｂｅｒｓ． Ｂｙ ｕｓｅ ｏｆ ｔｈｅ ｗａｖｅｅｘｐａｎｓｉｏｎ ｍｅｔｈｏｄ， ｔｈｅ ｆｒｅｅ ｐｏｉｎｔｓ ａｅｒｆ ｕｒｔｈｅｒ ａｓｓｉｎｇｅｄ ｍａｒｋｅｄ ｎｕｍｂｅｒ． Ｔｈｅ ｐａｔｈ ｉｓ ｉｆｎｄｅｄ ｂａｓｅｄｏｎ ｔｈｅ ａｓｓｉｎｇｅｄ ｍａｒｋｅｄ ｎｕｍｂｅｒ ｖｉａ ｗａｖｅ ｅｘｐａｎｓｉｏｎ ｍｅｔｈｏｄ． Ａｓ ｃｏｍｐａｒｉｓｏｎ， ｄｅｐｔｈ－ｉｆｒｓｔ ｓｅａｒｃｈｍｅｔｈｏｄ ｉｓ ｐｒｅｓｅｎｔｅｄ． Ｔｈｅ ｐｒｏｐｏｓｅｄ ｌａｇｏｒｉｔｈｍ ｉｓ ｔｅｓｔｅｄ ｏｎ ａ ＡＢＢ ＩＲＢ１４００ ６－ＤＯＦ ｉｎｄｕｓｔｒｉｌａｏｒｂｏｔ ｕｎｄｅｒ ＥＮＶＩＳＩＯＮ ｃｉｒｃｕｍｓｔａｎｃｅ ａｎｄ ｔｈｅ ｅｘｐｅｃｔｅｄ ｅｒｓｕｌｔｓ ａｒｅｏ ｂｔａｉｎｅｄ． ３． Ｂａｓｅｄ ｏｎ ｉｓｌａｎｄ－ｄｒｉｖｅｎ ｓｅａｒｃｈ ｓｔｒａｔｅｇｙ， ｇｅｎｅｔｉｃ ｌａｇｏｒｉｔｈｍ ｉｓ ｐｒｅｓｅｎｔ ｔｏ ｐｌａｎ ｐａｔｈ ｉｎｏｒｂｏｔ＇ｓ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅ ｉｎ ｄｅｍａｎｄ ｏｆ ｔｈｅ ｒｏｂｏｔ＇ｓ ｗｏｒｋ． Ｔｈｅ ｐｒｏｐｏｓｅｄ ｌａｇｏｒｉｔｈｍ ｉｓ ｔｅｓｔｅｄ ｏｎ・３・沈阳工业大学硕士学位论文ａＲＫ１０Ｓ６一ＤＯＦｉｎｄ比侧ａｌｒｏｂｅｔ四ｄｅｒＥＮＶＩＳＩ《〕ＮＣ】ｒＣＵｎ节ｔ日ｎ伴．Ｔｈｅｅｆｅｃｆｉｖｅｎｅｓｔｓａｎｄ丫ａｌｌｉｄｙｏｔｆ面ｓａＰＰｒｏａｃｈａｅＰｒｒｏｖｅｄ衍山ｅｏｒｅｔｉａｌａｃｎａｌｓｉｙｓａｎｄｓ加ｕ】成ｌｏｎｒｅｓｕｌｓｔ．Ｋ叮ｗｏｒｄ引Ｉｎｄｓｕ州ａｉｏｒｏｂ屯ｐａｈｐｌｔｎｎａｉｎｇ，ｅｅｖａｗｘａＰｓｎｉｎｍｅｏｈｔｏｄ，ｄｅＰｔｈ币ｒｓｔｓｅｒａｃｈｍｅｔ ｈｄｏ，ｉｌｓａｎｄ．ｄ对ｖｅｎｓｅｅｒａｈｓＯａｔｅ罗，ｇｅｎｅｔｉｃａｌｇｏｒｉｈｔｍ一４・独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。签名：里卫土丝红日期：夕沪夺，名关于论文使用授权的说明本人完全了解沈阳工业大学有关保留、学校有权保留送交论文的复印件，使用学位论文的规定，即：允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵循此规定）签名：３ｉｊ也式导师签名：命冷形日期？．ｏ沈阳工业大学硕士学位论文１绪论路径规划是机器人导航中最重要的任务之一。机器人的路径规划问题可以分为两大 类：一类是基于环境先验信息的全局路径规划；另一类是基于不确定环境的传感器信息的局部路径规划。本文的主要工作是对路径规划算法进行理论的研究，解决工业机器人全局路径规划问题。１．１机器人技术的发展历程与定义机器人的诞生，无疑是２０世纪人类科学技术的重大成就。近４０年的时间，机器人 从无到有，在世界经济各个领域和人民生活的众多方面忠诚的为人类服务，作出不可磨灭的贡献。在工业机器力发展及应用日益广泛的今天，机器人已被人们看作是一种生产工具，在制造、装配及服务行业，机器人的应用取得了明显的进步。世界上第一台工业机器人是在２０世纪６０年代初诞生的。此后，工业机器人应用于 汽车制造业取得成功，并被广泛应用于其他制造行业。这一时期的机器人被称为顺序控制机器人，由预先编制好的程序控制运行，缺少感知自身和环境状态的能力，所以只能运行于固定环境中，缺乏对环境的适应性。为了让机器人有一定的感知能力，人们给机器人装上了许多不同功能的传感器，形 成了具有传感器信息反馈的第二代机器人。借助于传感器，机器人能通过“视觉”、“触觉”等传感器对外部环境进行实际探测，从而由这些反馈信息在事先编好的算法和 程序指导下对操作过程进行调整。与第一代机器人相比，第二代机器人更加具有柔性和安全性。然而，该类机器人的自身状态和环境状态信息是非数值化的，人们希望机器人能像人类一样自主接受和解释这些非数值信息，由此开始了第三代机器人，即智能机器人的研制．目前，由于机器人在国民经济及人们生活中有极大的应用潜力，世界各国的机器人 的研究都极为重视，但各国对机器人的定义却各有差异，且有一定的局限性和不够确切之处。如英国机器人协会田ＲＡ）的定义是：“一种可以重复编程的装置，用以加工和搬运零件、工具、特殊的加工器具，通过可变的程序流程以完成特定的加工任务。”美国国家标准局（ＮＢＳ）的定义是：“一种可编程的自动控制下完成某些加工任务或动作的机沈阳工业大学硕士学位论文械装置。”最近联合国标准化组织定义为：“一种可重复编程的多功能操作手，用以搬运材料、零件、工具或者是一种为了完成不同操作任务，可以有多种程序流程的专门系统。”分析以上的各种定义，可以发现大部分是针对工业机器人而言的。由此可见，工业机器人在机器人领域的地位极其重要，有待进一步研究。１．２本课题的研究意义及国内夕！研究动态未来的机器人应该具有感知、规划和控制等高层能力。它们能从周围的环境中收集 知识，构造一个关于环境的符号化的世界模型，并使用这些模型来规划、执行由应用者下达的高层任务，其目标是实现机器人的使用者在较高的层次给机器人下达一些较宏观的任务，由机器人系统自身来填充那些较底层的细节问题。因此，机器人的路径规划是规划模块中的一个重要组成部分。在机器人领域，目前国内外研究机构正在研究的内容有以下几个方面： 开展对未知环境下机器人导航问题的研究。在未知环境下自主导航的重要问题是对 环境的感知。Ｂｏｓｏｔｎ大学利用立体视觉及超声距离传感器实现了对物理世界的标图。Ｏｈｉｏ州立大学采用不同的机器，以协调的方式来进行绘制地图等。Ｃａｌｆｏｎ五ａ大学等利用Ｋｏｈｏｎｎｅ神经网络来表示机器人工作环境的自由空间，其方法比较独特。更普遍采用的方法是用栅格法来表示未知环境。未知环境下的自主导航，对机器人的避碰能力提出了更高的要求，国外在这方面的 研究中一个明显的趋向是采用势场法、模糊控制、神经网络、遗传算法等综合技术手段来达到目的，尤其是在不同程度上采用神经网络、遗传算法的方法是当前研究的重点。在未知环境逐步被探测的基础上，全局路径规划依然是自主导航中的一项关键技 术。国内外对路径规划技术的研究己有很多成果，值得指出的是Ｃｌｓａｕｉｓ与Ｍｉｉｌｓｏ等学者效仿神经网络技术提出的一些并行规划方法，思想较新颖，在相应的硬件支持下，将会在规划程度上有较大提高。智能机器人体系结构的研究依然是机器人领域的一个受人关注的课题。随着对智能 和实现智能途径的看法不同，产生了不同的体系结构。比较典型的是基于功能模块划分的分层递阶体系结构和面向行为划分的包容体系结构。从智能的手段上，基于联结主义的人工神经网络技术也在某些方面取得很大的成功，所以在传统的人工智能研究的方沈阳工业大学硕士学位论文法基础上，如何与人工神经网络技术相结合也成为国内外学者在体系结构研究中探索的 方向。 １ ．３机器人路径规划研究的研究综述路径规划技术是机器人研究领域中的一个重要分支。机器人路径规划的基本问题是 在空间中确定自初始点至目标点的一条无碰撞的运动路径，即无碰撞路径规划１ ］１。蒋新松为路径规划作出了这样的定义：路径规划的任务就是在具有障碍物的环境内按照一定 的评价标准，寻找一条从起始状态（包括位置和姿态）到达目标状态（包括位置和姿 态）的无碰撞路径。障碍物在环境中的不同分布情况当然直接影响到规划的路径，而目 标位置的确定则是由更高一级的任务分解模块提供的。 根据对环境的了解情况，路径规划可以分为全局规划和局部规划。其中，全局规 划需要知道关于环境的所有消息；而局部路径规划则只需要距离机器人较近的障碍物信息。如果从静态或动态地获取障碍物信息角度看，全局路径规划属于静态规划，而局部路径规划则是动态规划。一般的路径规划算法都会涉及到以下几个问题：位姿空间、环境表示、规划方法 和搜索方法等问题。１．３．１位姿空间（Ｃｏｎ五即以１佣ＳｐａｅＣ）一个物体或机器人的位姿是指能完全地确定该物体或机器人上所有点的一个相互独 立的参数集，不仅描述了运动的位置，而且考虑了它的姿态。一个由物体的所有位姿所组成的位姿空间则代表了该物体的所有可能的运动，成为路径规划领域中的一个基本问题。由于障碍物的存在，运动物体在该空间中就有一个相应的禁区，称为“位姿空间障碍域”，运动物体与障碍物发生碰撞的所有状况都属于这个域。这实际上是把运动物体、障碍物及其几何约束关系作了等效的变换，简化了问题的解决．位姿空间最初是由ＬＯ乙川０一Ｐｅｒｅｚ和ｗｅｓｅｌｙ提出来的ＩｊＺ，它将路径规划问题转变为位姿空间中的起始位姿和终止位姿之间找到一个连续的位姿节点序列。通常说来，位姿空间的维数是机器人的自由度数ＤｏＦ（ｅ孚ｅＤｅｏｆ斤以刘ｏｍ）。沈阳工业大学硕士学位论文１． ３．２环境表示法对机器人活动空间的有效描述称为环境模型。机器人在规划前首先要做的就是将环 境的描述有外部的原始形式通过一系列处理转化为适合规划的内部的世界模型，这个过 程称为环境建模，其中主要的是障碍物的表示方法。合理的环境表示才能有利于规划中 搜索量的减少，才能有利于时空开销的减少。不同的规划方法正是基于这种不同的环境 建模。以下是几种常用的环境表示方法：１． ３．２．１栅格表示法栅格表示法就是使用大小相同的栅格划分机器人的工作空间，并用栅格数组来表示 环境１３－６１。每个栅格点以两种状态之一表示，或者在自由空间中，或者在障碍物空间中。如可将障碍物在栅格数组中标为一１，自由空间标为０。路径是通过搜索栅格图得到的。为了提高搜索效率，栅格通常分为若干层次，这种方法特点是简单，易于实现，从而为路径规划器的实现带来了很多方便，具有表示不规则障碍物的能力。其缺点是表示效率不高，存在着时空开销与求解精度之间的矛盾。１．３．２．２单元树法单元树法是为了克服栅格法的缺点而设计的。这种方法把机器人工作空间划分为几 个较大的单元【”１（一般来说，二维空间划分成４部分，称为四叉树；三维空间划分为８部分，成为八叉树）。划分得到的每个单元所占用的工作空间可能是下面三种情况之一：都为自由空间；都为障碍物空间；混合型空间，即既包含了障碍物区域，又包含了自由区域。对于最后一种类型的单元按照前面的方法继续进行划分，直到一个预先设计好的精度为止。该方法的主要缺点是计算单元之间的邻接关系时的损失较大。１．３．２．３多边形（多面体）表示法多边形（多面体）表示法也是常用的方法之一【 １０１［＇１１１。二维情况下，该方法用多边形来逼近障碍物；三维情况下，则用多面体来逼近障碍物．同时，使用了很多成熟了的求交叉点和测距等方面的解析几何算法。１．３．３规划方法为了解决路径规划问题，人们己探索出很多有效的求解方法。机器人路径规划方法 大致可以分为两类：传统方法和智能方法。沈阳工业大学硕士学位论文Ｌ３３． １传统路径规划方法［Ｊｌ１ 卜３３．１．１自由空间法为了简化问题，通常采用“位姿空间”来描述机器人及其周围的环境。这种方法将 机器人缩小成点，将其周围的障碍物及边界按比例相应地扩大，使机器人能够在障碍物空间中移动到任意一点，而不与障碍物及边界发生碰撞。 １． ．３３．１．２图搜索法图搜索方法中的路径图由捕捉到的存在于机器人一维网络曲线（ 称为路径图）自由空间中的节点组成。建立起来的路径图可以看作是一系列的标准路径，而路径的初始状态和目标状态同路径图中的点相对应，这样路径规划问题就演变为在这些点间搜索路径的问题。通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点， 使某点与其周围的某可视点相连（即使相连接的两点间不存在障碍物或边界）。然后机器人沿着这些点在图中搜索最优路径。１３．３．１．３栅格解拐法栅格解祸法是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解祸为 多个简单的区域，一般称为栅格。由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径，这条路径是用栅格的序号来表示的。栅格解祸法包括确切的和不确切的两种。确切的解祸法用来描述整个自由空间，这将使复杂环境的解祸速度变慢，其原因是 许多复杂的多边形可能需要与障碍物的边界相匹配。这种方法可以保证只要起始点到目标点之间存在路径，就完全能搜索到这条路径。在不确切的解祸法中，所有的栅格都是预定的形状，为了研究方便假设全部为矩 形。整个图被分割成多个较大的矩形，每个矩形之间都是连续的。如果大矩形内部包含障碍物或者边界，则又被分割成４个小矩形，对所有稍大的栅格都进行这种划分，然后在划分的最后界限内形成的小栅格间重复执行程序，直到达到解的界限为止。这种解祸的结构称为“四叉树”。在进行下一层更细的划分之前，应在每一层上的起点和目标点间找到一条路径，如果该路径满足起点到目标点间无障碍物的要求，则停止搜索。＿——一一一逃ｍ工业ｔ学硕士学位论文不确切的栅格解祸方法比确切的栅格解祸方法在数学计算上要简单的多，因此也比 较容易实现。 １． ３．３．１．４人工势场法传统的人工势场法把机器人在环境中的运动视为一种在抽象的人造受力场中的运 动，目标点作为吸引点对机器人产生“引力”，而障碍物作为排斥点对机器人产生“斥 力”，机器人沿吸引点和排斥点产生的合力方向运动。该方法构造一个叫做势函数的标 量函数，使机器人的目标位姿对应于其最小值，障碍物区域对应于一些较大的值，在任 何其它位置，势函数都是向机器人目标位姿单调递减的。这样，不论机器人处于自由空 间的任何位置，只要有路径存在，它都能通过势能值的负梯度方向找到目标位姿。该方 法的优点是可以使机器人迅速避开障碍物，实时性好．但是，由于势场法把所有信息压 缩为单个合力，这样就存在把有关障碍物分布的有价值的信息抛弃的缺陷，且易陷入局 部最小值。另外一个困难是很难找到一种适合于凹形障碍物的势函数。这些不利因素限 制了人工势场法在全局路径规划中的应用。 大部分机器人路径规划中的全局规划都是基于上述几种方法进行的，但是以上这些 传统方法在路径搜索效率及路径优化方面尚有待于进一步改善。而现在通常使用的搜索技术包括：梯度法、Ａ’等图搜索方法、枚举法、随机搜索法等。这些方法中梯度法易陷入局部最小点，图搜索方法、枚举法不能用于高维的优化问题，因此随机搜索算法受到人们的青睐。１．３．３．２智能路径规划方法近年来，随着遗传算法等智能方法的广泛应用，机器人路径规划方法也有了长足的 进展，许多研究者把目光放在了基于智能方法的路径规划研究上。其中，应用较多的算法主要有：模糊方法、神经网络和遗传算法。１．３．３．２．１基于模糊逻辑的机器人路径规划模糊方法是在线规划中常采用的一种规划方法，包括建模和局部规划。庄晓东等［ Ｉ２１提出一种基于模糊概念的动态环境模型，参照物体的位置和运动信息构造二维隶属度函数；然后通过模糊综合评价对各个方向进行综合考察，得到搜索结果。该方法在移动障碍物和移动目标的环境中能有效地实现机器人避碰和导航。Ｈａｒｔｍｌｌｔ Ｓｕｒｉｎａｍ等［Ｉ３］提出沈阳工业大学硕士学位论文了一种未知环境下的高级机器人模糊导航方法，由５个不同的超声传感器来提供环境信 息，然后利用基于模糊控制的导航器来计算这些信息，规划机器人路径。 该方法在环境未知或发生变化的情况下，能够快速而准确地规划机器人路径，对于 要求有较少路径规划时间的机器人是一种很好的导航方法。但是，其缺点是当障碍物数 目增加时，该方法的计算量会很大。影响规划结果。 １３． ３２２基于神经网络方法的机器人路径规划禹建丽等州魄出了一种基于神经网络的机器人路径规划算法，研究了障碍物形状和 位置已知情况下的机器人路径规划算法，其能量函数的定义利用了神经网络结构，根据 路径点位于障碍物内外的不同位置选取不同的动态运动方程，规划出的路径达到了折线 形的最短无碰撞路径，计算简单，收敛速度快。陈宗海等１ １５１提出一种在不确定环境中移动机器人的路径规划方法，将全局路径规划分解为局部路径规划的组合，为了提高规划的效率，在避障规划中采用了基于案例的学习方法，以ＡＲＩ、２神经网络实现案例的匹配学习和扩充，满足了规划的实时性要求。１３．３２．３基干遗传算法的机器人路径规划遗传算法是目前机器人路径规划研究中应用较多的一种方法，无论是单机器人静态 工作空间，还是多机器人动态工作空间，遗传算法及其派生算法都取得了良好的路径规划结果。孙树栋等１ １１６用遗传算法完成了离散空间下机器人的路径规划，并获得了较好的仿真结果。但是，该路径规划是基于确定环境模型的，即工作空间中的障碍物位置是已知的、确定的。Ｋ斑见ＯＳ ｕ乡ｂｒａａ等１７１１在采用离散空间进行路径规划的同时，将问题更深入化，栅格序号采用二进制编码，统一确定其个体长度，随机产生障碍物位置及数目，并在搜索到最优路径后，再在环境空间中随机插入障碍物，模拟环境变化，通过仿真结果验证了算法的有效性和可行性。但是，规划空间栅格法建模还存在缺陷，即若栅格划分过粗，则规划精度较低；若栅格划分太细，则数据量又会太大。在多移动机器人协调作业方面，遗传算法也得到了应用，景兴建等，愧出一种基于理性遗传算法的协调运动行为合成算法，针对特定环境下的多机器人协调运动问题，基沈阳工业大学硕士学位论文于调速避碰的思想，借助ＣＭＡＣ神经网络，描述各机器人的运动行为与环境状态之间复杂的、非线性映射关系，利用理性遗传算法来合成与优化各机器人的运动行为，从而实现多机器人已知环境下，运动行为的相互协调与优化。１．３．３．２．４基于混合方法的机器人路径规划方法Ｔｓ ｏｕｋａｌａｓ ＬＨ等［１９］提出一种用于半自主移动机器人路径规划的模糊神经网络方法。所谓半自主移动机器人就是具有在人类示教基础上，增加了学习功能的器件的机器人。这种方法采用模糊描述来完成机器人行为编码，同时重复使用神经网络自适应技术。由机器人上的传感器提供局部的环境输入，由内部模糊神经网绍进行环境预测，进而可以在未知环境下规划机器人路径。综上所述，遗传算法等智能方． 法在机器人路径规划技术中已受到广泛的重视及研究，在障碍物环境己知或未知情况下，均己取得一定的研究成果。１．３．４搜索方法给定一种机器人工作空间的表示方法和标识自由位姿空间的能力后，路径规划问题 就转变为从给定的表示中找到一个从起始位姿到终止位姿的连续的位姿序列的问题了。大体说来，搜索技术可分为以下三类：１．３．４．１基于微积分的搜索技术该技术使用由优化问题的解来满足的一组充分必要条件。这些技术一般只能用于解 较简单的问题。用Ｈｏｐｆｉｅｌｄ神经网络方法求解优化问题是这类技术的一个实例。１．３．４．２有指导的随机搜索技术该技术以枚举技术为基础，但附加了一些指导搜索过程的信息。它们的应用范围很 广，并能解决十分复杂的问题，其两个主要的构成部分是模拟退火算法。它们本身都是进化，但前者使用热力学模型的演化过程来寻找最低能量状态。而进化算法则是以自然选择过程为指导。遗传算法（Ｇｅｎｅｉｔｃ Ａｌｇｏｒｉｔｈｍ）为特例之一。从上世纪９０年代以来，用有指导的随机搜索技术，尤其是遗传算法进行路径规划是国内外学者进行研究的重点。１．３．４．３枚举技术该技术是搜索目标函数的域空间的每一个节点，它们的实现简单，但可能会需要很 大的计算量。动态规划是其中一种很好的方法。路径规划技术中常用的深度优先搜索、沈阳工业大学硕士学位论文广度优先搜索、Ａ＊ 搜索都是其特例。机器人路径规划是机器人应用中的一项重要技术，例如，在执行装配、焊接及抢险 救灾等任务时，采用良好的机器人路径规划技术可以节省大量机器人作业时间、减少机 器人磨损，同时也可以节约人力资源，减小资金投入，为机器人在多种行业中的应用奠定良好的基础。将遗传算法、模糊逻辑以及神经网络等方法相结合，可以组成新的智能 型路径规划方法，从而提高机器人路径规划的避障精度，加快规划速度，满足实际应用 的需要。同时，多机器人协调作业环境下的路径规划技术也将是研究的热点及难点问 题，越来越受到人们的重视，这将是一个有意义的研究课题。１．４本文的主要工作本文对机器人的路径规划进行了较为系统的研究。在对大量相关文献进行深入分析 的基础上，在对机器人路径规划算法理论研究和实践过程中，提出了不同的机器人路径规划算法和思想。ｌ（ ）针对６自由度的工业机器人，建立了工业机器人的运动学模型。本文中，建立了两类工业机器人的运动模型：其一为ＡＢＢ」ＲＢ１４００型工业机器入；另一为ＲＫ卫５型０工业机器人。）针对机器人避障快速性的要求，提出了的基于波扩散方法的工业机器人路径规２（ 划算法・对６・自由度的工业机器人仿真验证所提出的算法，得到了满意的效果・以ＡＢＢＩＲＢ１０Ｏ型６一４ＤＯＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶ】Ｓ１０Ｎ仿真环境下进行仿真。从仿真结果看，所研究算法在机器人路径规划方面是可行的。３（ ）针对机器人作业中的精确性的要求，基于孤岛搜索策略，提出了在机器人的构型空间中采用遗传算法进行路径规划找出最优路径的方法。以ＲＫ１ｓ型６一０ＤｏＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶＩＩｓＯＮ仿真环境下进行仿真。从理论分析和仿真实验结果的一致性，证明了算法的有效性和合理性，因而该方法在路径规划方面是可行的。沈阳工业大学硕士学位论文２工业机器人的运动学模型典型ＳＣＡＲＡ型工业机器人是关节机器人，６个关节都是转动关节。因此，可以把 任何机器人的机械手看作是一系列由关节连接起来的连杆构成的。２．１ ＲＫ１０Ｓ型工业机器人ＲＫＩ ＯＳ机器人是典型的ＳＣＡＲＡ型工业机器人，６个关节都是转动关节。前３个关节确定手腕参考点的位置，后３个关节确定手腕的方位。后３个关节轴线交于一点，该点选作为手腕的参考点。关节１的轴线为铅直方向，关节２和３的轴线水平，且平行。关节１和２的轴线垂直相交，关节３和４的轴线垂直交错。２．１， Ｉ机器人坐标系的建立为机械手的每一连杆建立一个坐标系，并用齐次变换来描述这些坐标系间的相对位 置和姿态。选ＲＫ１０Ｓ机器人的基坐标系作为参考坐标系，即为该机器人关节０的坐标系。其他关节的坐标系，以基坐标系为基准，通过平移和旋转而得到。如图２．１为机器人连杆坐标系图，其中，ｄ，－ｄ５为机器人连杆参数，０１－－６６为关节转动的角度及其方向，箭头所指方向定义为转动正方向。０６跳，－－－－－ｄ－，－－－－－－图２．１ ＲＫ１０Ｓ型机器人坐标系的建立沈阳工业大学硕士学位论文２．１．２机器人连杆参数要对机器人进行规划与控制，必须对其连杆参数清楚了解。表２． １列出了机器人的连杆参数。表２． １ ＲＫ１０８机器人的连杆参数连杆ｉ变量０ｉｄ（ｔ－ｎ）变量范围１０１２００－１７０’－１７０２０２６００－１５０一９０３０３１１５－７０ －９０４０４７７０－１８０ －１８０５ｅ５１００－１３５‘－１３５６０６－２００＇ －２００２．１．３通常把描述一个连杆与下一个连杆间相对关系的齐次变换叫做Ａ矩阵。一个Ａ矩 阵就是一个描述连杆坐标系间相对平移和旋转的齐次变换。如果Ａ，表示第一个连杆对于基系的位置和姿态，Ａ２表示第二个连杆相对于第一个连杆的位置与姿态，那么第二个连杆在基系中的位置和姿态可由下列矩阵的乘积给出。爪＝Ａ，Ａ，同理，对于六连杆机械手，有下列Ｔ矩阵ＯＴ６＝Ａ，ＡＺＡ３Ａ，Ａ，Ａ６（２．１）根据机械手各连杆之间的关系及其连杆参数，可求得各连杆变换矩阵如下：姆一ＳＯ，０Ｄ７，二Ａ，＝Ｒｏｒ（Ｚ， ｅ， ） －Ｔｒａｎｓ（ｙ， ａ， ） 喊ＣＢ，１１１ 一￣ ００ ，．二（２．２） ００ 卜Ｕ 自伙０ ０ ，几＝！１２＝Ｒｏｔ（ｘ，么）－Ｔｒａｎｓ（ｚ，鸽） 四 一一 ．旧Ｃ０２一ｓ０２ ｜Ｓ久ＣＯ，（２．３） 旧 」０ ０ 沈阳工业大学硕士学位论文２．２ ＡＢＢ ＩＲＢ１４００型工业机器人本文中建立的另一个机器人模型为ＡＢＢ ＩＲＢ １４００型工业机器人，其结构与ＲＫ１０Ｓ型机器人类似。因此，只对其简单介绍。２．２．１机器人连杆参数下表为机器人连杆参数： 连杆ｉ１２表２． ２机器人的连杆参数变量０ｉ０ｌ０２ａ－１（ｎｉｍ）０１８８９５０２２５００ｄｉ（－）９０００变量范围－１８０＇ －１８０＇－７０＇刀０＇－３０＇ －１３５＇－３００＇－３００＊－１２０＇－－１２０＇－３００＇ －３００＇３４５６ｅ３０４ｅ５ｅ６０１３００００２．２．２机器人运动学模型机械手的Ｔ变换矩阵形式与式（ （２．８）同，其具体元素如下：ｎ， ＝Ｃ ＩＩＣ２３（Ｃ４ＣＳＣ。一Ｓ４Ｓ６）一Ｓ２３Ｓ５Ｃ６５ ＋ ＳＩ（Ｓ４Ｃ５Ｃ６ ＋ Ｃ４Ｓ６）ｎｙ＝ＳｌＩＣ２３（Ｃ４Ｃ５Ｃ‘一Ｓ４Ｓ６）一Ｓ２３Ｓ５Ｃ６］一Ｃｌ （Ｓ４Ｃ５Ｃ６ ＋ Ｃ４Ｓ６）ｎ，＝－Ｓ２３（ｃ４ｃ，ｃ‘一Ｓ４Ｓ６）一Ｃ２３Ｓ５Ｃ６０｝＝ＣＩ Ｉ－Ｃ２３ （Ｃ４Ｃ５Ｓ６ ＋Ｓ４Ｃ６） ＋Ｓ２３Ｓ５Ｓ６］一Ｓｌ（Ｓ４ｃ５ｃ。一Ｃ４Ｃ６）Ｏｙ ＝ ＳＩ［－Ｃ２３（Ｃ４Ｃ５Ｓ６ ＋Ｓ４Ｃ６） ＋ Ｓ２３Ｓ５Ｓ６］＋ ＣＩ（Ｓ４Ｃ５Ｓ‘一Ｃ４Ｃ６）０ｚ ＝Ｓ ２３（Ｃ４ＣＳＳ６ ＋ Ｓ４Ｃ６） ＋ Ｃ２３Ｓ５Ｓ６ａ．＝－ＣＩ （Ｃ２３Ｃ４Ｓ５ ＋ Ｓ２３Ｃ５）一ＳＩＳ４Ｓ５ａｙ＝ －ＳＩ（Ｃ２３Ｃ４Ｓ５ ＋ Ｓ２３Ｃ５） ＋ ｃｌｓ４Ｓ５ａ，＝Ｓ２３Ｃ４Ｓ５一Ｃ２３Ｃ５（２．１０）Ｐｘ ＝ Ｃｌ （ａ３ｃ二一ｄ４Ｓ２３ ＋ａ２Ｃ２ ＋ａ，）Ｐｙ＝ＳＩ（ａ３Ｃ二一ｄ４Ｓ２３ ＋ａ２Ｃ２ ＋ａ，） Ｐ｝ ＝ －ａ３Ｓ２３一ｄ４Ｃ２３－ａ２Ｓ２ ＋ｄ， Ｊ２．２．３机器人运动学综合由于本文所提出的波扩散方法的实现中，要用到机器人的逆运动学的解。用到的 一１４－沈阳工业大学硕士学位论文３基于波扩散方法的工业机器人路径规划３．１引言２ ０世纪８０年代初，Ｌｏｚａｎ－ｏＰｅｅｒｚ提出了构形空间（（Ｃｏｎｉｆｇｕｒａｉｔｏｎ Ｓｐａｃｅ）的概念［２０１机器人的一种位姿状态可以用构形空间上的一个点—构ＷＣｏｎｆｉｇｕｒａｉｔｏｎ）来描述。与此相对应，一些研究者将人类生存的三维空间称作世界空间（ＷｏｒｌｄＳｐａｃｅ）２［Ｑ。关于关节式机器人路径规划的研究多数是使用完整的构形空间信息的精确规划方法［２２－２５１。但是，由于关节式机器人构造的特点，这种方法存在下面的问题：１ ）具有旋转关节时，自由构形空间的计算比较复杂。２ ）基于完整信息的规划法通常计算量随机器人自由度的增加而呈指数增加，多自由度的情况下有可能无法计算。为了克服上述问题，直接使用世界空间（又称为笛卡儿空间）的信息，而且只使用 机器人周围的信息的启发式规划法引起了研究者们的注意．这种规划方法回避了自由构形空间显式描述的复杂计算。基于机器人周围信息的规划法只考虑与当前机器人运动关系最密切的机器人周围的信息，基于某种启发式的规则探索路径。基于有效的启发式规则的探索可以大大地缩短计算时间。当然，在不幸的情况下这种方法有可能比精确方法还要慢，甚至导致探索失败而找不到结果。考虑到实际的关节式机器人（特别是工业机器人）的作业环境通常不会过分复杂狭窄，可以认为研究能够适用于一般环境（例如对于人类规划者不会感到非常复杂）的启发式规划法是一种实用的方向。近年来，在工业机器人研究领域，基于Ｃ一 空间法许多学者作了大量的工作。对于３－ＤＯＦ的工业机器人，路径规划研究方法已经成熟［２６１． ［２７１． Ｈｗａｎｇ等人所提出的机器人路径规划是也只是面向３－ＤＯＦ的机器人［２８１。然而，随自由度的增加，Ｃ一空间呈指数型增长。因此，基于离散化Ｃ一空间表示的路径规划方法对于３－ＤＯＦ以上的机器人并不适用。对于多自由度机器人，Ｂａｒｒａｑｕａｎｄ和Ｌａｔｏｍｂｅ提出了分散表示方法［２９１，其缺点是常陷入势场函数的局部极小点中。Ｄ．ｚｈｕ和Ｊ． Ｌａｔｏｍｂｅ提出了用启发式函数的方法，但该方法不能保证找到路径ＰＯ］． Ｙ．Ｔｉｎｇ等人也是基于Ｃ一空间方法提出工业机器人的路径沈阳工业大学硕士学位论文规划算法［Ｉ３Ｉ，该算法是先把机器人的工作空间离散化为３个二维的距离图，然后将其ＺＪ映射到机器人的Ｃ一空间，用深度优先算法规划出机器人运动路径。针对一般机器人路径规划采用关节坐标，本文提出了一种基于工业机器人的笛卡尔 工作空间的路径规划算法，从理论上简化了路径规划方法。首先，对机器人的工作空间进行离散化，用波扩散法对离散点进行标记，然后进行搜索找出合适路径。并使用该方法与深度优先算法进行了比较，从路径搜索效率来看，波扩散法能在较短时间内找到合适路径，因而优于深度优先算法。最后，以ＡＢＢ】ＲＢ１４００型吞ＤＯＦ工业机器人作为仿真对象，在ＥＮＶｌｌｓ０Ｎ仿真环境下进行仿真。从仿真结果看，所研究算法在避障和机器人路径规划方面是可行的。３．２１作空间离散化假定以ｗ表示机器人的工作空间，Ｂ ｉ（１月，…，）ｒ表示工作空间中的ｒ个障碍物，因而可知Ｕ‘１一Ｉｉ为障碍空间，则机器人自由空间ｗ触定义为：ＢＷ脉＝Ｗ・Ｕｒ 。一ＩＢｉ径。（３．１）机器人路径规划就是在Ｗ五“中绕过障碍物搜索一条自起始点到目标点的无碰撞路工作空间离散化具体方法为：世界空间坐标系下，将ｘ，ｙ，２轴的工作空间中 的区域段等分（定义等分长度为单位距离），因此整个空间离散化为若干等分，将离散的交叉点为作为研究对象．定义障碍空间ｕｒ：ｉＩｉ中的点为障碍点，而自由空间ＢＷ阮。中的点为自由点。对工作空间中的离散点进行二值化，即对障碍点和自由点分别标记以不同数字（如：障碍点可标记为一１，而自由点标记为０），依此来区分工作空间中的障碍点和自由点。工作空间离散化的目的是把连续的世界空间离散化为等距的栅格，便于路径的搜索。．波扩散法（３Ｗ淤ｅｅＰｘ田”ｌｎｍｅｏｈｔｄ）路径搜索ｏ．３３１波扩散算法工作空间离散化后，对离散点进行二值化以区别障碍点和自由点。为进行路径 搜索，需对自由点进一步标记，此标记说明了离散点距初始点的远近。所以，用波扩散法标记工作空间中的自由点并搜索路径。波扩散算法步骤如下：沈阳工业大学硕士学位论文４基于遗传算法（Ｇｅｎｅｉｔｃ Ａｌｇｏｒｉｔｈｍ）的工业机器人路径规划为解决机器人路径规划中的全局最优问题，并针对机器人作业中的精确性的要求， 本文基于孤岛搜索策略，提出了在机器人的构型空间中采用遗传算法进行路径规划找出最优路径的方法。在构型空间（（Ｃｏｎｆｉｇｕｒａｔｉｏｎ Ｓｐａｃｅ）中，可以采用如下的一种算法：将路径考虑成一系列的路径点，用人工势场法进行规划，用网络结构并行实现。在实时性方面，此算法具有很大的优势。然而，此算法对于全局最优解的寻找却为力［［３５，１［３６１因此，引入遗传算法来帮助寻找全局的最优解。在机器人的作业过程中，有时需要其所走过的路径精度较高，即路径趋于全局最优，此时便可以用本章所提出的基于遗传算法的路径规划方法。近年来，随着遗传算法等智能方法的广泛应用，许多研究者把目光放在了基于智能 方法的路径规划研究上［３７，４５１４．１引言遗传算傲ＧＡ） 是一种新发展起来的优化算法，它产生于美国的密执根大学。从上世纪６０年代起，密执根大学的Ｈｏｌｌｓｉｔｅｎ， Ｂａｇｌｅｙ和Ｒｏｓｅｎｂｅｒｇ等人的博士论文即与遗传算法密切相关，而Ｊｏｈｎ Ｈ． Ｈｏｌｌａｎｄ教授１９７５年出版的“Ａｄａｐｔａｉｔｏｎ ｉｎ Ｎａｔｕｒａｌ ａｎｄＡｒｔｉｉｆｃｉａｌ Ｓｙｓｔｅｍｓ＂ ［４６１一书通常认为是遗传算法的经典之作，因为该书给出了遗传算法的基本定理，并给出了大量的数学理论证明。Ｄａｖｉｄ Ｅ． Ｇｏｌｄｂｅｒｇ教授１９８９年出版的＂Ｇｅ ｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ”一书通常认为是对遗传算法的方法、理论及应用的全面系统的总结。遗传算法已经成为人们用来解决高度复杂问题的一个新思路和新方法。目前遗传算法已被广泛应用于许多实际问题，如函数优化、自动控制、图象识别、机器学习、人工神经网络、分子生物学、优化调度等许多领域中的问题［４７－４９１，遗传算法是基于自然选择和基因遗传学原理的搜索算法。它将“适者生存”这 一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着算法的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。这一过程就如生物进化那样，好的特征被不断地继承下来，坏的特性被逐渐淘汰。新一代个体中包含着上一代个体的大量信息，新一代的个体不断在总体特沈阳工业大学硕士学位论文性上胜过旧的一代，从而使整个群体向前进化发展。对于遗传算法，也就是不断地接近于最优解。研究遗传算法的目的主要有两个：一是通过它的研究进一步解释自然界的适应过程；二是为了将自然生物系统的重要机理运用到人工系统的设计中。遗传算法一般经过这样几个过程：首先，随机产生一定数目的初始染色体，这 些随机产生的染色体组成一个种群。种群中染色体的数目称为种群的大小或种群规模。然后，用评价函数来评价每一个染色体的优劣，即染色体对环境的适应程度（称为适应度），用来作为以后遗传操作的依据。接着，进行选择过程，选择过程 的目的是为了从当前种群中选出优良的染色体，使它们成为新一代的染色体。判断染色体优良与否的准则就是各自的适应度，即染色体的适应度越高，其被选择的机会就越多。通过选择过程，产生一个新的种群．对这个新的种群进行交叉操作，交叉操作是遗传算法中主要的遗传操作之一。接着进行变异操作，变异操作的目的是挖掘种群中个体的多样性，克服有可能陷入局部解的弊病。这样，经过上述运算产生的染色体称为后代。然后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解．．４２遗传算法的优点遗传算法的中心问题是鲁棒性伽ｂｕ ｓｍｅｓ）Ｓ，所谓鲁棒性是指能在许多不同的环境中通过效率及功能之间的协调平衡以求生存的能力。遗传算法吸取了自然生物系统“适者生存”的进化原理，从而使它能够提供一个在复杂空间中进行鲁棒搜索的方法，它对于搜索空间基本上不需要什么性的假设（如连续、导数存在及单峰等）。４２．１寻优方法的分类及其特点常规的寻优方法主要有三种类型：解析法、枚举法和随机法。 ．４２．１，１解析法解析法寻优通常可分为间接法和直接法。间接法是通过让目标函数的梯度为零，进 而求解一组非线性方程来寻求局部极值。直接法是按照梯度信息按最陡的方向逐次运动来寻求局部极值。上述两种方法的主要缺点是：一是它们只能寻找局部极值而非全局的极值；二是它们要求目标函数是连续光滑的，并且需要导数信息。这两个缺点，使得解析寻优方法的鲁棒性能较差。沈阳工业大学硕士学位论文．４２１．２枚举法枚举法可以克服解析法的两个缺点，即它可以寻找到全局的极值，而且也不需 要目标函数是连续光滑的。它的最大缺点是计算效率太低，对于一个实际问题，常常由于太大的搜索空间而不可能将所有的情况都搜索到，它对于中等规模和适度复杂性的问题，也常常为力。．４２１．３随机法鉴于上述两种寻优方法有严重缺陷，随机搜索算法受到人们的青睐。随机搜索 通过在搜索空间中随机地漫游并随时记录下所取得的最好结果。出于效率的考虑，搜索到一定程度便终止。然而，所得结果一般尚不是最优值。本质上，随机搜索仍然是一种枚举法。４２．２迪传算法的优点遗传算法用到了随机技术，但它不同于上述的随机搜索。它通过对参数空间编 码并随机选择作为工具来引导搜索过程向着更高效的方向发展。因此，随机地搜索并不一定意味着一种无序的搜索。总的说来，遗传算法比其它寻优算法的优点是鲁棒性能比较好，可归纳为如下 几点：（ ）１遗传算法是对参数的编码进行操作，而不是对参数的本身；２（ ）遗传算法是从许多初始点开始并行操作，可有效的防止搜索过程收敛于局部最优解，而且有较大的可能求的全部最优解；３（ ）遗传算法通过目标函数来计算适配值（适应度），不需要其它的推导和附属信息，从而对问题的依赖性较小；４（ ）遗传算法使用概率的转变规则，而不是确定性的规则；５（ ）遗传算法在解空间不是盲目地穷举或完全随机测试，而是一种启发式搜索，其搜索效率往往优于其它方法：６（ ）遗传算法对于待寻优的函数基本无，它既不要求函数连续，更不要求可微；既可是数学解析式所表达的显函数，又可是映射矩阵甚至是神经网络等隐函数，因而应用范围较广：・２９－沈阳工业大学硕士学位论文７（ ）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度；８（ ）遗传算法更适合大规模复杂问题的优化。．４３遗传算法的工作原理４３．１表示结构最优化问题的解有两种表示方法：二进制向量或浮点向量。使用二进制向量作 为一个染色体来表示决策变量的真实值，向量的长度依赖于要求的精度。在求解复杂优化问题时，二进制向量表示结构有时不太方便。另一种表示方法是用浮点向量，每一个染色体由一个浮点向量表示，其长度与解向 量相同。用向量ｘ气ＸＩ，ｘＺ，…，ｘｎ）表示最优化问题的解，其中ｎ是维数．则相应的染色体也是Ｖ＝（ｘ；，ｘＺ，・，幼。．４３２处理约束条件处理约束条件的关键在于： ）ａ（ 删除约束条件中的所有等式：（ ）ｂ设计恰当的遗传操作以保证所有新产生的染色体在可行集中。为了保证染色体是可行的，必须对遗传操作过程中得到的每一个染色体进行检查。 对每个最优化问题，最好设计一个Ｃ语言子函数，其输出值１表示染色体是可行的，０表示不可行。同时，设计程序时，应当注意到一些隐含约束，即有些点虽然是可行解，但不可能是最优解。为减少程序的搜索空间，应尽可能地增加隐含条件，从而可以大大加快问题的进化过程。．４３．３个体编码方法由于路径规划问题的复杂性，对于二进制串编码， 有以下缺点①若路径中途点个数较多，则编码非常长，降低了算法搜索的效率； ②采用二进制串编码， 相邻整数存在如巧和１６的二进制表示分别为０１１１和１０。，因此从１５到１６将改变所有的位，导致进化效率过低；③采用二进制串表示路径坐标有一定的冗余度，因此变异会产生非法个体。 一３０。沈阳工业大学硕士学位论文鉴于二进制编码的以上缺点，因此采用浮点向量表示法，即用ｖ＝（ ｘｌ，ｘＺ，…，ｘ心表示相应的染色体。为研究问题方便起见，本文只考虑机器人的前三关节，因此，用 ｖ钊沐： ，ｘＺ，ｘ３）表示相应的染色体。其中，ｘ．，撇，ｘ３表示前三关节的关节角，皆为浮点量。 ４注４遗传算法中的适应度函数（‘加ｅｓｓ）ｖ（）遗传算法进化过程中，必须对每个染色体进行检验，符合适应度函数要求的为可行 集中的解。适应度函数的选择在遗传算法中是相当重要的，它是引导遗传算法向问题最 优解逼近的关键因素。对于具有约束性能指标的最优问题，可以取性能指标或性能指标的变换作为适应度函数。 本文讨论的问题是求一条最短路径，约束条件是路径与障碍物不交，并且要求与障 碍物有一定的距离。由于搜索点逐渐逼近目标点，所以，可取所搜索到的点与目标点的距离作为适应度函数，即刀ｔ ｓｅｎ（Ｆ）＝丫（‘一ｘ），＋（，：一，），＋（２：一矛伊．，）其中，、，介，、表示目标点的世界坐标；ｘ，ｙ，２表示搜索到的点的世界坐标。 初始种群的染色体生成后，可分别求得相应适应度函数的值。然后，按距离由小到大的顺序对染色体进行重排，为遗传操作作准备。．４．３５迪传算法的操作步骤．４３．５．１初始化过程初始化过程是遗传算法进化计算的起点， 其目的是找到初始种群。初始种群由一定数目（称种群大小）的个体组成。为了保证遗传算法的全局最优性，初始种群应尽可能随机分布在搜索空间中每一个区域。路径规划时，从初始点出发，在各关节变量步长范围内，随机产生种群数目为Ｎ 的染色体，即找到范围内的对应各染色体表示的点。同时，对每个点进行检验，看其是否在可行集内，即满足一定的约束条件，使机器人不与障碍物相撞。若在可行集内，则将其作为初始种群的一员；否则，重新随机生成，直到染色体种群数目达到Ｎ。具体初始化过程如下：沈阳工业大学硕士学位论文定义整数ｐ ｏｐ二ｓｌｅ作为染色体的个数，并且随机产生因ｐ声ｉｚｅ个初始染色体。设决ｚ策者可给出可行集的一个内点，记为ＶＯ．定义一个足够大的数Ｍ，保证遗传操作遍及整个可行集。在Ｒｎ中，随机选择一个方向ｄ，如果Ｖｏ＋Ｍｄ满足不等式约束，则将ｖ＝ｖ七十Ｍｄ作为一个染色体，否则，置Ｍ为０和Ｍ之间的一个随机数，直到Ｖｏ＋Ｍｄ可行为止。由于ＶＯ是内点，所以在有限步内，可以找到满足不等式约束的可行解。重复以上过程ｐｏｐ‘，ＩｅＺ次，从而产生卯ｐ‘５泳个初始染色体ｖｏ，ｖｌ，…，ｖ冈ｃｓ－二。，４３：５选择过程４汉５．２．１评价（选择）函数的选择选择机制在遗传算法中起着重要的作用，选择策略主要有：赌轮选择、正比选择、 标度选择、级别选择以及求和截断法等。选择机制的出发点就是以某种方式保留那些具有较好适应性的个体，淘汰适应性差的个体。最一般的方法就是赌轮选择，即对每个染色体Ｖ ｉ，计算累积概率ｑｉ，由第三节提出的方法决定哪些染色体被选择。经过选择过程，可以复制得到Ｎ个染色体。选择过程是对样本基因的选优。其是根据个体串的适应度进行复制，以产生新的种群。适应度越大的串，在下一代中将有更多的机会提供一个或多个子孙。因此，体现了“优胜劣汰”的自然选择机制。评价函数（ 用ｅｖｌａ冈表示）用来对种群中的每个染色体ｖ设定一个概率，以使该染色体被选择的可能性与其种群中其它染色体的适应度成比例，即通过轮盘赌，适应性强的染色体被选择产生后代的机会要大。 设目前该代中的染色体为ｖｌ，叭，…，ｖ哪。可以根据染色体的序进行再生分配，而不是根据其实际的目标值。在染色体ｖ：，叭，…，ｖ娜二中，决策者可以给出一个序的关系，使染色体由好到坏进行重排，也就是说，一个染色体越好，其序号越、。设参数ａ‘（ ０）ｌ，给定，定义基于序的评价函数为ｅ ａｖｌ（Ｋ）二ａ（１一ａ）‘一，，１＝１，２，…，尸印＿ｓｅｚｌ４（．）２月意味着染色体是最好的，厂，叩Ｊｌ ｅｚ说明是最差的。沈阳工业大学硕士学位论文４．３．５．２．２选择过程选择过程是以旋转赌轮ｐｏ ｐ ｓｉｚｅ次为基础的。每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。选择过程可写成如下形式：步骤１对每个染色体Ｖ； ，计算累积概率４ｊ９ａ＝０（４．３）。，＝艺ｅｖａｌ（Ｖｊ ），ｉ＝１，２， ＊， ｐｏｐ＿ｓｉｚｅ步骤２从区间（ （Ｏ，Ｑ＂＿ｓｉｍ）中产生一个随机数：；步骤３若９ｊ －，‘；‘４ｊ，则选择第ｉ个染色体Ｖｉ（Ｉ＜－ｉ－＜ｐｏｐ ｓｉｚｅ）；步骤４重复步骤２和步骤３共ｐｏ ｐ ＳＩＭ次，这样可以得到ｐｏｐ ｓｉｚｅ个复制的染色体。４．３．５．３交叉操作交叉操作是对样本基因的重组，以产生更优良的后代。交叉体现了自然界中信息交 换的思想。交叉就是在复制后产生的Ｎ个个体中，以一定的概率（Ｐ｝）随机地进行两两配对。每对染色体根据下式（（４．４）进行交叉，产生新的染色体对。本文中对选择进行交叉的染色体（ 父代）随机配对，即对机器人Ｃ－空间中的两点进行处理产生新的两点，使其更优于原来的父代。首先定义参数Ｐ。 作为交叉操作的概率，这个概率说明种群中有期望值为Ｐ．． ｐｏｐ ｓｉｚｅ个染色体来进行交叉操作。为确定交叉操作的父代，从ｉ ＝１到ｐｏｐ ｓｉｚｅ重复以下过程：从（０， １）中产生随机数ｒ，如果：＜Ｐ｝，则选择Ｖ；作为一个父代．用丫．，Ｖ２， Ｖ＇３ｒ…表示选择的父代，并把它们随机分成下面的对（ ｖ＇，， Ｖ＇Ｚ）， （Ｖ３， Ｖ＇４）， （Ｖ＇Ｓ， Ｖ＇６），以柑丫Ｖ＇ ｚ）为例说明交叉操作的过程。首先，从开区间（（０， １）中产生一个随机数。，然后，按下列形式在ｖ＇，和Ｖｚ之间进行交叉操作，并产生两个后代ｘ和ＹＸ＝ ；Ｃ． Ｖ，＋（１－ｃ） ． Ｖ２， Ｙ＝（１－ｃ）． Ｖ＇ｉ＋ｃ．Ｖ＇２ （４．４）沈阳工业大学硕士学位论文检验每一个后代的可行性。如果两个后代均可行，则用它们代替其父代，否则，保 留其中可行的（如果存在的话），然后，产生新的随机数ｃ，重新进行交叉操作，直到得到两个可行的后代或循环给定次数为止。总之，仅用可行的后代取代其父代。．４．３５．４变异操作变异模拟了生物进化过程中的偶然基因突变现象。变异为新点的产生提供了机会， 保证了算法能够搜索到问题解空间的第一点，从而使算法具有全局最优，它进一步增强了遗传算法的能力。遗传算法能力主要是由选择和交叉赋予的，变异则保证了搜索的全面性。类似于交叉的父代染色体的选择过程，父代选定后，由下式（４５）得出变异操作产生的新一代个体。变异操作的目的是挖掘种群中个体的多样性，克服有可能陷入局部解的弊病。因 此，用遗传算法进行路径规划可以克服传统的人工势场法的缺陷，从全局上尽可能地接近最优点。定义参数Ｐｍ作为遗传系统中的变异概率，这个概率表明，总体中有期望值为 Ｐｍ．即几ｓｌｅ个染色体用来进行变异操作。ｚ类似于交叉操作中选择父代的过程，由拼１到卯ｎ，ｚ ｅ重复以下过程：从区间（，０）１中产生随机数ｒ，如果ｒ＜Ｐｍ，则选择Ｖｉ作为变异的父代。对每一个选择的父代，用ｖ＝（ｘｌ，ｘＺ，…，叼表示，按下列方法进行变异。在Ｒｎ中随机选择变异方向ｄ，如果ｖ十Ｍｄ是不可行的，则置Ｍ为０和Ｍ之间的随机数，直到其可行为止。其中Ｍ为初始化过程定义的一个足够大的数。如果在预先给定的迭代次数之内没有找到可行解，则置Ｍ＝０。无论Ｍ为何值，总用 Ｘ＝犷十Ｍ・ｄ４（．）５代替Ｖ．如下图为遗传算法的操作流程图沈阳工业大学硕士学位论文图４．１遗传算法的操作流程４．３．６优化问题的解遗传算法程序运行过程中，最好的染色体不一定出现在最后一代中，所以在进化开 始，必须把最好的染色体保留下来，记为Ｖｐ，如果在新的种群中又发现了更好的染色体，则用它代替原来染色体Ｖｐ。在进化完成之后，这个染色体就可以看作是优化问题的解。４．４ Ｃ一空间中的障碍物检则４．４．１ ＲＫ１０Ｓ机器人运动模型的简化研究机器人路径规划问题前，首先应对机器人的几何结构进行分析。典型ＳＣＡＲＡ 型工业机器人的６个关节全为转动关节，机器人的运动主要靠１至３手臂关节，其转动对机器人的姿态影响作用很大；而４至６关节为腕关节，对机器人的姿态影响不大。为研究问题方便起见，在机器人路径规划中，略去４至６关节的作用的影响，即假定后三个关节不运动（（０ ４＝ｅ５＝０６＝０），只考虑前三关节的运动。在假定机器人后三关节不转动的前提下，前面所提到的运动学模型可进行简化。由 。４＝ ９ ｓ＝。ｆｉ｝，模型进一步简化为：沈阳工业大学硕士学位论文ｒ．，．飞叭气Ｐ Ｘ． １ ０ ．Ｐ 凡 才‘ 、，．巧马马ｙ 氏 久 么 ． ． －－ ． Ｐ（５６）．气０２ａｚ名 ． Ｉ Ｌ。０ｏ Ｉ 气＝ｃｌ ａ二＝一ｓ１Ｃ２３ｎ夕＝ｓｌ ａｙ＝ｃｌｃ２３气＝ｏ ａ：＝５２。０ 二＝一５１５２，夕二＝５１（姚５２３一么ｃ２３＋ＪＺｓＺ一试）＋。二“，（５７）０ ，＝“．ｓ２３ｐ，＝一ｃ，（姚５２，一么ＣＺ，＋丸５２一试）＋ａｙ姚０：＝一ｃ２ ３户：＝姚ｃ２３＋峨５２３＋ｄＺｃ：＋ａｚ姚其中：５ １，ｃｌ，又，Ｑ，几，几的定义与以前完全相同。这样，机器人的运动就简化为只与机器人前三关节的转角相关的运动。．４４２Ｃ－空间中的障碍物４４．２．ＩＣ一空间中机器人的路径规划环境中具有障碍物的机器人的运动，需要以无碰撞路径规划算法为前提。否则，在 运动过程中，机器人可能与障碍物发生碰撞。而要进行路径规划，必须事先清楚以下几方面的信息：①机器人的运动学描述、几何结构及参数； ②机器人运动环境的几何模型； ③机器人的初始位置与目标位置。 以上几方面作为运动规划算法的输入，即进行机器人运动规划的前提条件。 机器人的Ｃ －空间由其的自由度进行定义，该空间的每个点描述了机器人手臂的某确定状态。因此，通常在机器人的Ｃ一空间中进行路径规划。路径规划的结果是得出初始位置与目标位置间一系列点，而自初始点绕过障碍物依次通过规划点到达目标点，即为机器人的无碰撞路径规划。近年来，在工业机器人研究领域，基于Ｃ一空间法许多学者作了大量的研究工作１５间，ｏｌ沈阳工业大学硕士学位论文局部搜索图４．５孤岛驱动搜索．４５１．２局部采用遗传算法进行搜索自初始点以一定步长向目标点搜索时，采用遗传算法进行搜索。找到一定范围内的 路径的最好点，即离最终目标点、距离最近的点认为是一定范围内的最优点。再以该点为新的初始点，重复以上过程，直至到达最终目标点飞。．４６仿真实验仿真实验使用ＳＧ Ｉ工作站，ＥＮＶＩＳ１０Ｎ环境，以ＲＫ１ｓ型工业机器人为研究对０象，来验证本文所提出的遗传算法。以机器人的基坐标系为参考坐标系，取一个长方体（ ４ｏｏｘ４００ｘｓｏｎｌｎｌｂ作为障碍物，其坐标原点在（２０，１－０００，礴００）。在机器人的ｃ－空间中进行路径规划，机器人进行路径搜索的初始点和目标点分别设定为５（４’，一００３・，一０’）和Ｇ（一０’，２０・，一３０’）。由４ ．４节所述障碍物检测的方法，并且同时考虑各关节角的运动极限，得到以下四个Ｃ一空间中的障碍空间Ｑｌ＝碘卜２７３‘巩蕊２７．｝自｛３风卜１４．０６‘认‘一５０６｝自｛风｝一７０。０‘么‘６０刀｝０：＝｛只卜２７・３‘巩‘２７．｝门俱卜１３０．５０‘凡‘一１４０．６｝门｛ 已｝一７０．０‘烤‘６０乃｝（５２３）５２４）（・４２沈阳工业大学硕士学位论文５结论本论文在工业机器人的运动规划方面，从机器人作业要求一避障的快速性和路径的 最优性一的不同，分针对工业上两类机器人ＡＢＢ ＩＲＢ１４００和ＲＫ１０Ｓ，采用两种方法：波扩散方法和遗传算法，对机器人的路径规划问题，进行了深入而系统地探讨和研究。 本文的研究结果如下： 其一，针对６自由度的工业机器人，建立了工业机器人的运动学模型。本文中，建 立了两类工业机器人的运动模型：其一为ＡＢＢ ＩＲＢ１４００型工业机器人；另一为ＲＫＩ ＯＳ型工业机器人。这是进行路径规划的基础。其二，为避免繁琐的机器人示教过程，提出了离线的基于波扩散方法的工业机器人 路径规划算法。首先对机器人的工作空间离散化，针对工作空间中的障碍点和自由点进行二值标记；然后用波扩散方法对自由点进一步标记，并进行了路径搜索；最后，以波扩散法与深度优先算法路径搜索进行了比较。针对６一自由度的工业机器人验证所提出的算法，得到了满意的效果。以ＡＢＢ ＩＲＢ１４００型６－ＤＯＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶＩＳＩＯＮ仿真环境下进行仿真。从仿真结果看，所研究算法在机器人路径规划方面是可行的。其三，针对机器人作业中的精确性的要求，本文基于孤岛搜索策略，提出了在机器 人的构型空间中采用遗传算法进行路径规划找出最优路径。以ＲＫ１０Ｓ型６－ＤＯＦ工业机器人作为仿真对象，用ＳＧＩ工作站，在ＥＮＶＩＳＩＯＮ仿真环境下进行仿真。理论分析和仿真实验结果的一致性，证明了算法的有效性和合理性，因而该方法在路径规划方面是可行的。通过对上述问题的研究，使作者在工业机器人的运动规划方面有了较深的认识和把 握，也使作者深深地体会到了科学研究所特有的艰辛和快乐。作者相信，上述研究工作必将为今后的研究及个人思想认识的发展打下坚实的基础。在信息化、网络化的社会高速发展的今天，人工智能、机器人学等都发展到了前所未有的程度，但同时又面临着巨大的挑战，如何抓住机遇，使自己能够有一个更大的发展和飞跃，将是该领域学者们所面临的一个重大课题。沈阳工业大学硕士学位论文参考文献１１１Ｌａｔｏｍｂｅ， Ｊ． Ｃ． Ｒｏｂｏｔ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ． Ｄｏｒｄｒｅｃｈｔ： Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ Ｐｕｂｌｉｃａｔｉｏｎ １９９１１２］Ｔ．Ｌｏｚａｎｏ－Ｐｅｅｒｚ， Ｍ． Ａ． Ｗｅｓｌｅｙ． Ａｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐｌａｎｎｉｎｇ ｃｏｌｌｉｓｉｏｎ ｒｆｅｅ ｐａｔｈｓ ａｍｏｎｇＰｏｌｙｈｅｄｒａｌ ｏｂｓｔａｃｌｅｓ． Ｃｏｍｍｕｎ， ＡＣＭ ２２（１９７９） ５６０－５７０［３ｌＹａｏ Ｚｈｅｎｇ，凡Ｗ． Ｌｅｗｉｓ， Ｄ． Ｔ． Ｇｅｔｈｉｎ． Ｔｈｒｅｅ－ｄｉｍｅｎｓｉｏｎａｌ ｕｎｓｔｒｕｃｔｕｒｅｄ ｍｅｓｈｇｅｎｅｒａｔｉｏｎ．Ｃｏｍｐｕｔ． Ｍｅｔｈｏｄｓ Ａｐｐｌ． Ｍｅｃｈ． Ｅｎｇ． １３４（１９９６） ２４９－２６８１４］Ｍ． Ｂ． Ｊｏｓｈｉ． Ｄｏｍａｉｎ ｍａｐｐｉｎｇ ｆｏｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ｉｎ ３Ｄ． Ｍａｓｔｅｒ＇ｓ Ｄｉｓｓｅｒｔａｔｉｏｎ Ｔｈｅｓｉｓ，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍｅｃｈａｎｉｃａｌ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｍａｎ Ｉｎｓｉｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ Ｋａｎｐｕｒ， Ｉｎｄｉａ，２０００［５１Ｓ． Ｓ． Ｍａｋｈｎｏｖ， Ｓ．Ａ． Ｉｖａｎｅｎｋｏ． Ｇｒｉｄ ｇｅｎｅｒａｔｉｏｎ ａｓ ａｐｐｌｉｅｄ ｔｏ ｏｐｔｉｍｉｚｅ ｃｕｔｔｉｎｇ ｏｐｅｒａｔｉｏｎｓｏｆ ｔｈｅ ｉｆｖｅ－ａｘｉｓ ｍｉｌｌｉｎｇ ｍａｃｈｉｎｅ． Ａｐｐｌｉｅｄ Ｎｕｍｅｒｉｃａｌ Ｍａｔｈｅｍａｔｉｃｓ ４６， （２００３）３３１－３５１［６１Ａｎｉｌ Ｂ． Ｓｕｒｙａｗａｎｓｈｉ， Ｍｉｌｉｎｄ Ｂ． Ｊｏｓｈｉ， Ｂｈａｓｋａｒ Ｄａｓｇｕｐｔａ， Ａｒｐａｎ Ｂｉｓｗａｓ． Ｄｏｍａｉｎｍａｐｐｉｎｇ ａｓ ａｎ ｅｘｐｅｄｉｔｉｏｎａｙｒｓ ｔｒａｔｅｇｙ ｆｏｒ ｆａｓｔ ｐａｔｈ ｐｌａｎｎｉｎｇ． Ｍｅｃｈａｎｉｓｍ ａｎｄ ＭａｃｈｉｎｅＴｈｅｏｒｙ３ ８（２００３），１－２０ｆ７］Ｐ． Ａｄｏｌｐｈｓ． Ａ ｍｅｔｈｏｄ ｆｏｒ ｆａｓｔ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｃｏｌｌｉｓｉｏｎ－ｒｆｅｅ ｏｒｂｏｔ ｍｏｖｅｍｅｎｔｓ ｉｎｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅ． Ｐｒｏｃ． ｏｆ ＩＥＥＦ／ＲＳＪ ＩＲＯＳ，ｐｐ． ５－１２， １９９０１８１Ｒ．Ｂｒｏｏｋｓ ａｎｄ Ｔ． Ｌｏｚａｎｏ－Ｐｅｅｒｚ． Ａ ｓｕｂｄｉｖｉｓｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅ ｆｏｒ ｆｉｎｄｐａｔｈ ｗｉｔｈ ｏｒｔａｔｉｏｎ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｓｙｓｔｅｍｓ， ｍａｎ ａｎｄ ｃｙｂｅｎｒｅｔｉｃｓ， ＳＭＣ－１５（２）：２２４－２３３，１９８５［９］ Ａ．Ｂａｄｄｅｒ， Ｇ． Ｈｉｒｚｉｎｇｅｒ． Ａ ｓｅｌｆ－ｏｒｇｎｉｚｉｎｏｒｏ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｕｌｔｉｓｅｎｓｏｒｙｓ ｕｒｆａｃｅ Ｒｅｃｏｎ－ｓ ｔｒｕｃｔｉｏｎ． Ｐｒｏｃ． ｏｆ ＩＥＥＥＪＲＳＪ ＩＲＯＳ， Ｍｕｎｉｃｈ， Ｇｅｒｍａｎｙ， １： ８１－８８， Ｓｅｐ． １２－１６， １９９４［１０］ Ｌ． Ｇｏｕｚｅｎｅｓ． Ｓｔｒａｔｅｇｉｅｓ ｆｏｒ ｓｏｌｖｉｎｇ ｃｏｌｌｉｓｉｏｎ－ｒｆｅｅ ｔｒａｊｅｃｔｏｒｉｅｓ ｐｒｏｂｌｅｍｓ ｆｏｒ ｍｏｂｉｌｅ ａｎｄ ｍａｎｉｐｕｌａｔｏｒ ｏｒｂｏｔｓ． Ｉｎｔ． Ｊ Ｒｏｂｏｔｉｃｓ Ｒｅｓｅａｒｃｈ， ｖｏｌ． ３， ｐｐ． ５１－６５， １９８４［１１１ Ｂ． Ｆａｖｅｒｊｏｎ． Ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｕｓｉｎｇ ａｎ ｏｃｔｒｅｅ ｉｎ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅ ｏｆｍａ ｎｉｐｕｌａｔｏｒ． Ｐｒｏｃ． ＩＥＥＥ Ｉｎｔ． Ｃｏｎｆ． Ｒｏｂｏｉｔｃｓ Ａｔｌａｎｔａ／ＧＡ， ｐｐ． ５０４－５１２， １９８４［１２１庄晓东，孟庆春，殷波等．动态环境中基于模糊概念的机器人路径搜索方法．机器人． ２００１， ２３（５）： ３９７－３９９［１３１ Ｈａｒｔｍｕｔ Ｓｕｍｕｕｍ， Ｊｒｇ Ｈｕｓｅｒ． Ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ａ ｆｕｚｚｙ ｃｏｎｔｏｒｌｌｅｄ ａｕｔｏｎｏｍｏｕｓ ｍｏｂｉｌｅｏｒ ｂｏｔ． ５ａ＇ ＩＥＥＥ ｈｉｔ． Ｃｏｎｆ． ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ． ＵＳＡ： Ｎｅｗ Ｏｒｌｅａｎｓ， １９９６－４８－沈阳工业大学硕士学位论文１１４禹建丽，韩平一种基于神经网络的机器人路径规划算法．洛阳工学院学报２００１，２２（ １）：３１一３４１］５陈宗海，陈锋．一种不确定环境下移动机器人避障规划算法．机器人，加０２，２４（ ）４，３５９一３６１【６１１孙树栋，曲彦宾．遗传算法在机器人路径规划中的应用研究．西北工业大学学报，１ ９９８，１６（１）：７９一８３１１刀Ｋａｚｕｏｓｕｇｉｂ即旧，ＪｏｈｏＳ而山．ｅＧｎｔｅｉｃｌａｇｏｒｉｔｉｈｌ招ｆｒｏａ山甲ｔｉｅｖｎｌｏｔ１０ｎＰｌａｎｎｌｎｇｏｆａｎ ａｕｔｏｎｏｍｏＵ旧ｍｏｂｌｉｅｒｏｂｅｔｓ．正ＥＥＴｎ汀招．ＳＭＣ．ＵｓＡ：ＳＭＩ，１９７９１８１景兴建，王越超一种基于理性遗传算法（ＲＧＡ）的协调运动行为合成算法．机器人，２００ ２，２４（１）：礴今一５４１］９ＴｓｏｕｋａｌｓａＬＨ，ＨｏｕｓＵｓＥＮ，Ｊｏｎｅｓ０Ｖ．Ｎｅｕｒ－ｏ伽恻ｍｏｔｉｏｎＰｌｎａｅｓｒｆｏｒｉｎｔｅｌｉｌｇｅｎｔｏｒ ｅｂｔｓ．」。叨ｍａ１ｏｆ１ｎｔｅｌ１１ｇｅｎｔａｎｄＲｏｂｅｔｉｃＳｙｓ１ｅｍｓ，１９９７，１９：３３９一３５６２［１０助左川０・ＰｅｒｅｚＴ．ＳＰａｌｌｉａＰＩ肛ｍｉｎｇ：ａｃｏｎ五ｇＵｔａｒｌｎｏｓａＰ伪ａＰＰｒｏａｃｈ．ＥＩＥＴｒｎａ涨犯ｔｉｎｏｓｎｏ ＣｏｍＰｕｔｅｒｓ，１９８３，Ｃ・３２（２）：１０８￣１２０２１ｌＨｗａｎｇＹＫ，Ａｌｌｌ习ａＮ，ＧｒｏｓｓｍｏｔｉｏｎＰ】题而１１９一ａｓ切即ｅｒ．ＡＣＭＣｏｍＰｕｔｉｎｇＳＵＶｒｅｙｓ，１９９ ２，２４（３）：２１９一２９２２１ｌ２ｏＬｚａｎｏ月ＰｅｒｅｚＴ．ＡｌｌｔｏｍａｔｉｃＰｌｎａｉｎｇｏｆｎｌ田旧ｐｕｌｔａｏｒｔｒ田招ｆｅｒｍｏｖｅｎｌｅｔｎｓ．ＩＥＥＥ Ｔ庄ｍｓａｔｉｏｎｓｏｎｓｙｔｓｅｍｓ，Ｍａｎ，朗ｄＣｙｅｂｍｅ石ｃｓ，１９８１，ＳＭＣ一１１（１０）：６８１￣６９８２１３ｌＬｏｚａｎｏ．ＰｅｒｅｚＴ．ＡｓｉＰｍｌｅｍｏｔｌｏｎ．Ｐｌ肚ｍｍｇａｉｇ０ｒｉｈｔｍｆｏｒｇｅｎｅｒｌａＯ’ＩＯｂｔｍａｊｎＰｕＩｏｔａｒ．ｓＩ ＥＥＥＪ．ＲｏｂｅｔｃｉｓａｎｄＡＬｔｌｏｍａｔｉｏｎ，１９８７，ＲＡ白３（３）：２２斗一２３８２１ｌ４ＲｉｎｌｏｎＥ，ｏＫｄｉｌｓｃｈｅｋＤＥ．Ｅｘａｃｔｒｏｔｏｂｎａｖｉｇａｔｉｎｏｕｓ吨州伍ｃｉｌａｏｐｌｅｎｔ认】允朋ｔｉｓｎｏ． ＩＥＥＥＴｒａ几劝ｃｉｔｏｓｎｏｎＲｏｂｏｔｉｃｓａｎｄＡｕｔｏｍａｔｉｏ几１９９２，８５（）：５０１一５１８２１５ｌＭａｃｌｊｅｅｗｓｉｋＡＡ，ＦｏｘＪＪ．Ｐ川五Ｐｌ别田山叮ｇａｎｄｔｅｈｔｏｐｏ】０盯。ｆｃｏｎｆｉｒＵｇａｔｉｎｏｓＰａｃｅ．Ｉ ＥＥＥＴｒ别肚妞ｃｌｌｏｎｓｏｎＲｏｂｏｌｉｃｓａｎｄＡｕｔｏｎｌｔａｉ叽１９３，９（）４：科４￣４５６２１ｌ６．ＫＡＺａｎｌｌａｎｄＧ．ｃＳｈｍｌｔｄ．Ｉｎｔｅ孚ａｔｄｅｍｏｂｉｌｅｒｏｔｅｂｍｏｔ１０ｎＰｌｎａｌ飞朋ｄｅｘｃｅｉｔｕｏｎｉｎｃ ｈａｎｇ吨Ｉｎｄｏｏｒｅｖｎｉｍｎｍｅｎｔｓ．Ｐｒｏｃ．ｏｆＩＥＥＤ叹ＳＪＩＲＯＳ，Ｍ切苗也Ｇｅｒｍａｎｙ，１：２９８－３０５， ＳｅＰ．１２一１６，１９９４２１］７Ｊ．Ｑ幻ｍ，Ｐ．Ｋ五ｏｓａｌＲｅａｌ．ｔ面ｅｏｂｓ住‘ｌｅａｏｖｉｉｄｍｃｅｕｓ吨恤而。ｎｌｃｐｏｔｅｎｔｉｌａ丘川ｃ ｔｉｓｎｏ．１ＥＥＥＴｒｎａｓａｃｉｔｎｏｓｏｎｒｏｂｅｔ１ｃｓａｎｄａｕｔｏｎ１ｉｔａｏｎ．ＲＡ一８（３：）３８一３４９，Ｊｕｎｅ１９９２一４９・沈阳工业大学硕士学位论文［２８］ Ｙ．Ｈｗａｎｇ． Ａ ｐｏｔｅｎｔｉａｌ ｉｆｅｌｄ ａｐｐｒｏａｃｈ ｔｏ ｐａｔｈ ｐｌａｎｎｉｎｇ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｏｒｂｏｔｉｃｓａ ｎｄ ａｕｔｏｍａｔｉｏｎ，ＲＡ－８（１）：２３－３２， １９９２［２９］ Ｊ．Ｂａｒｒａｑｕａｒｄ， Ｊ．Ｃ．Ｌａｔｏｍｂｅ． Ｒｏｂｏｔ ｍｏｔｉｏｎ ｐｌａｎｎｉｎｇ： ａ ｄｉｓｔｉｒｂｕｔｅｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ａｐｐｒｏａｃｈ． Ｔｈｅ ｉｎｔｅｎｒａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｏｒｂｏｔｉｃｓ ｒｅｓｅａｒｃｈ， １０（６）：６２８－６４９，Ｄｅｃｅｍｂｅｒ， １９９１［３０］ Ｄ．Ｚｈｕ ａｎｄ Ｊ．Ｌａｔｏｍｂｅ． Ｎｅｗ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｈｉｅｒｒａｃｈｉｃａｌ ｐａｔｈ ｐｌａｎｎｉｎｇ． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｏｒｂｏｔｉｃｓ ａｎｄ ａｕｔｏｍａｔｉｏｎ， ｖｏｌ．７， ｎｏ． ｔ， ９－２０， Ｆｅｂｒｕａｙ１ｒ ９９１［３１］ Ｙ．Ｔｉｎｇ， Ｗ．Ｉ．Ｌｃｉ ＆ Ｈ．Ｃ．Ｊａｒ． Ａ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｄｕｓｔｒｉａｌ ｏｒｂｏｔｓ． Ｃｏｍｐｕｔｅｒ＆ Ｉｎｄｕｓｔｉｒａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ４２ （２００２）， ２９９－３０８［３２］ Ｔｉｎｇ丫，Ｌｅｉ Ｗ． Ｉ． （１９９９）． Ｕｓｉｎｇ ｔｈｅ ｈｉｅｒａｒｃｈｙ ｔｒｅｅ ｍｅｔｈｏｄ ｆｏｒ ｏｒｂｏｔ ｐａｔｈ ｐｌａｎｎｉｎｇ．Ｉ ＡＳＴＥＤ Ｉｎｔ． Ｃｏｎｆ． ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， Ｓａｎｔａ Ｂａｒｂａｒａ， ＵＳＡ， ｐｐ． １５３－１５７［３３］ Ｅ．Ｒａｌｌｉ ａｎｄ Ｇ．Ｈｉｒｚｉｎｇｅｒ． Ｆａｓｔ ｐａｔｈ ｐｌａｎｎｉｎｇ ｆｏｒ ｒｏｂｏｔ ｍａｎｉｐｕｌａｔｏｒｓ ｕｓｉｎｇ ｎｕｍｅｒｉｃａｌｐｏｔ ｅｎｔｉａｌ ｉｆｅｌｄｓ ｉｎ ｔｈｅ ｃｏｎｆｉｇｕｒａｔｉｏｎ ｓｐａｃｅ． Ｐｒｏｃ． ｏｆ ＩＥＥＥ／ＲＳＪ ，Ｍｕｎｉｃｈ，Ｇｅｒｍａｎｙ，１９２２－１ ９２９，１９９４［３４］ Ｒａｌｌｉ Ｅ．， Ｈｉｒｚｉｎｇｅｒ Ｇ，（１９９６）． Ａ ｇｌｏｂａｌ ａｎｄ ｅｒｓｏｌｕｔｉｏｎ ｃｏｍｐｌｅｔｅ ｐａｔｈ ｐｌａｎｎｅｒ ｆｏｒ ｕｐ ｔｏ ６ＤＯＦ ｏｒｂｏｔ ｍａｎｉｐｕｌａｔｏｒｓ． ＩＥＥＥ Ｉｎｔ． Ｃｏｎｆ． ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ， ｐｐ． ３２９５－３３０２［３５］吴晓涛，孙增折．用遗传算法进行路径规划．清华大学学报（自然科学版），１ ９９５， ５ （１）： １４－１９［３６］孙增沂，张再兴，邓志东．智能控制理论与技术．清华大学出版社，广西科学技术出版社，１ ９９７［３刀Ｄｅｖｅｎｄｒａ Ｐ． Ｇａｒｇ， Ｍａｎｉｓｈ Ｋｕｍａｒ． Ｏｐｔｉｍｉｚａｔｉｏｎ ｔｅｃｈｎｉｑｕｅｓ ａｐｐｌｉｅｄ ｔｏ ｍｕｌｔｉｐｌｅｍａ ｎｉｐｕｌａｔｏｒｓ ｆｏｒ ｐａｔｈ ｐｌａｎｎｉｎｇ ａｎｄ ｔｏｒｑｕｅ ｍｉｎｉｍｉｚａｔｉｏｎ． Ｅｎｇｉｎｅｅｒｉｎｇ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆａ ｒｔｉｉｆｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ １５（２００２）： ２４１－２５２［３８］ Ａｎａｎｔｈｒａｍａｎ Ｓ． ａｎｄ Ｇａｒｇ， Ｄ．， １９９３ａ． Ｔｒａｉｎｉｎｇ ｂａｃｋｐｒｏｐａｇａｔｉｏｎ ａｎｄ ＣＭＡＣ ｎｅｕｒａｌｎｅ ｔｗｏｒｋｓ ｆｏｒ ｃｏｎｔｏｒｌ ｏｆ ａ ＳＣＡＲＡ ｏｒｂｏｔ． Ｉｎｔｅｎｒａｔｉｏｎａｌ Ｊｏｕｎｒａｌ ｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ａｐｐｌｉｃａ－ ｔｉｏｎｓ ｏｆ Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ６（２），１０５－１１５［３９］ Ａｎａｎｔｈｒａｍａｎ Ｓ． ａｎｄ Ｇａｒｇ Ｄ．， １９９３ｂ． Ｎｅｕｒｏｃｏｎｔｏｒｌ ｏｆ ｃｏｏｐｅｒａｔｉｖｅ ｄｕａｌ ｏｒｂｏｔ ｍａｎｉｐｕ－ｌ ａｔｏｒｓ． Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ， ＡＳＭＥ Ｓｐｅｃｉａｌ Ｐｕｂｌｉｃａｔｉｏｎ Ｎｕｍｂｅｒ ＤＳＣ ４８， ５７－６５［４０］ Ｃａｒｒｅｔｅｒｉｍ Ｊ．Ａ．， Ｎａｈｏｎ Ｍ．Ａ．， Ｍａ Ｏ．， ２００１． Ｓｏｌｖｉｎｇ ｄｉｓｔａｎｃｅ ｐｒｏｂｌｅｍｓ ｗｉｔｈ ｃｏｎｃａｖｅｂｏ ｄｉｅｓ ｕｓｉｎｇ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌ吨．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ／ＲＳＪ ＩｎｔｅｎｒａｔｉｏｎａｌＣｏ ｎｆｅｒｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｓ ａｎｄ Ｓｙｓｔｅｍｓ， Ｈａｗａｉ， ＵＳＡ， ｐｐ． １５０７－１５１２・５０－沈阳工业大学硕士学位论文［４ｌｌＧｏｌｄｂｅｇＤ．ｒ，１９８９．ＧｅｎｅｔｌｃＡｌｇｏｒｉｈｔｍｓｉｎｓｅＣｈ，ＯＰｔｒａｎｉ山以ｉｎ＆ＭａｏｃｈｉｎｅＬｅ田刀Ｉｎｇ．Ａｄｄ ｉｏｓ－ｎＷｅｓｙＬｅｌｏｎｇｍａ，ｈｎｃ．ｉ，Ｒｅａｄ吨，ＭＡ，ｅｗｙＮｏｒｋ４１ｌｉ２ｎｇｂｅｒＬ，１９％流山甲ｔｉＶｅｓｉｍｕｌｔａｄａｅｅａｎｌｇ（ｎｉＡＳＡ）：ｓｓｅｌｏｓｌｎ已ａＪ刀ｅｄ．Ｃｏｎｔｌ℃ｌｓｎｄｃａ－ｙ忱ｎｌ ｅｔｉｃｓ２５，３３一５４１３】Ｍｏｎ４ｅ而Ｄ．ｔ，Ｍ司ｒｉｄＭ．，１９９９．Ｐｌ剐川１月ｇｏｆｒｏｂｏｔ叫“ｔｏｒｉｅｓ初ｔｈｇｅｎｅｔｉｃａｌｇｏｒｉｎ”ｈｔＰｒ ｏｃｅｅｄｉｎｇｓｏｆｔｅ３ｈ８ｈＡ几ｌｔｕａ１Ｃｏ刊反ｒｅｎｅｏｆｔＣｅＳＩｈＣＥ，Ｍｏｒｉｏｋ氏」叩阴，１９９９，ｐ．９５９． ９６２４１Ｂａ１ｎｄｅｒＪ．Ｌａｎｄ从七ｉｔｅＣ．Ｃ．，１９９８．Ｐｒｉｍａｌａｎｄｄｕａｌｅ切旧】ｎｅｎ仁刀ｏｒｓｆｋｒｓｏｈｏｒｔｅｓｔＰａｈｔｏｒ ｉｎｔｕｇ．ＥＥＥＴ屁口５Ｉ．ｏｎｓｙｓｔｅｍｓ，Ｍａｎ，即ｄＣｙｂｅｍｅｔｌｃｓ，ＰａｒｔＡ，２８（１）：１３１一１３４４１匀ＲａｎｇａＮａｒａｙｎａＳａｎｉｌａＷ，ＪｎＵｈｕａｐａｎｇ．Ｍｕｌｔ吮ｓｏｌｕｔｉｏｎａｎａ】ｙｓｌｓａｓａｎａＰｐｒｏ毗ｆｒｔｏｏｌＰａ ｈＰＩｔ别田旧口ｇｉｎＮＣｍａｃｈｉｎｇ．ＣｏｍＰｕｔｅｒ．川ｄｅｄＤｅｓｉｎ３５（ｇ２００３）１６７一１７８１６１Ｈｏ４ｆｌｎｄＪＨ．ａＡｄｉ甲ｔｔ１ａ０ｎｉｎＮａｔ也司阴ｄＡｒｔｉｉｆｉｃｌｓｙｓａｔｅｍｓ．ＡＪＩＪＩ户Ｌｒｏｒｂ：丁五ｅＵｎｉｅｖ卜 ｓｌｙｏｔｆＭｉｉｇ明Ｐｒｈｃｓｓｅ，１９７５４１７ＤａｌｉｄＥＧ．ｖＧｅｅｔｎｌｃＡｌｇｏｒｉｈｔｍｓｉｎ，芝理ｃｈ，叩石ｍｉ乙ａｔｌｏｎ，明ｄｍａｃｉｈｎｅｌｅ旧”ｉｇ．ｎＭａｓａｓＣ ｈｕｓｅＳ：ｔＡｄｄｌｓ－Ｗ七ｓｎｏｌｙＰｕｂｌｅｉｓｈｉｎｇＣｏｍＰａｎｙ，Ｉｃ，１ｎ９８９拼匆ｅＬｅｓｕｌ山团１，ＢｅｋｅｙＧＡ．ＡＰＰｌｌｃｔａｌｓｏｎｏｆｎｅ切ｒａｌｎｅｔｗｏｋｔｒｏｒｏｅｔｂｓ．Ｃｏｎｔｒ０１ｎａｄＤ扣ａ－ｍｉ ｃｓｙｓｔｅｌｎｓ，１９１，３９：１荀９４［ｌｊｇｅａｎＣＬ．助喊ｍｏｔｌｎＰｏｌｎｇ．ＢｏｓＵＩａｏｎ：心ｕｔｒＡｃｅｗａｄｅｍｌｃＰｕｌｌｂｓｈｅｒｓ，１９１１５０】Ｊｅａｎ，ＦｒａｎｃｏｌｓＰｅｔｌ叭ＰａｔｉｒｃｋＣｈｅ山叮由１，Ｊｅ阶ＹｖｅｓＨａｃｏｓｃｔ．ＣｏｎｔｉｒｂｕｌｉｏｎｔｏｔｈｅＳＣｈｅｄ．Ｌ吨。 ｆ咧ｅｃｔｏｒｉｓｉｅｎｍｂｏｉｔｃｓ．ｏ切ｔＲｉｓａｅｎｄＣｏ哪ｕｔｅ－ｒｎＩ加ｇｌｔａｅｄＭ阴ｕｆＣｔａｕｒｎｉｇｌ４（ １９９８）２３７．２５１５１１５肠的ＫＧ，ＭｃＫａｙＮＤ．ＳｅｌＣｅｔｉｎｏｏｆｎｅｒａｍｉＩ１ｉｍａｌｔ１ｍｅｇｅ０ｍｅｉｒｔｃＰａｈｓｆｔｒｒｏ０加ｌｉｃｍ田肚－ｌａｕＰ ｏｒｔｓ．ＩＥＥＥＴｒｒ‘ＡｕｔａｏｍａｔｉｃＣｏｎｔｏｒｌ，１９８６，３１（）６：５０１一５１１５［ＩＤｕｂＺｏｗｓｋｉＳ，ＢｌｕｂａｕｈＴＤ．ｇＰｌ助面ｎｇｔｌｍｅ刃Ｐｔｉｍａ１ｒ０ｂｏ１ｉｃｎ１ｎａｉｐｕ１ｔａＯｒｍｏｔｉｏｎｓａｎｄＷｏｒ ｋＰｌｅｓｆｃａｏｒｐｏｉｎｔ．ｔｏ．Ｐｏｉｔ七招ｋｎｓ．】ＥＥＥＴ侧招．Ｒｏ比ｔｌｃｓＡｕｔｏｍａｔｉｏｎ１９８９，５（３）：３７７一３８１ 伟３」Ｗ・Ｅ．Ｒｅ氏Ｈ．Ｖ．Ｔｒｕｏｎｇ．Ｃａｏ，Ｋ．Ｈ．儿ｍ．ＲＯｂｏｔＰａｔｈＰＩ侧山山叮ｇｉｎｔｈ代ｅｄｉｍｅｓｉｎｏｓｎ 璐ｍｇ阮ｄｉ代兄ｔｓｕｂｓＰ朗ｅ．ＡＳＭＥＴｎ叮巧ａＣｔｉｏｎｓ，ｏｌｖ．１０９，Ｐ．２３８一４４，１９８７１４】ＪＲ．５Ｋｅｎｔ，Ｗ．Ｅ．Ｃａｘｏｓｎ，Ｒ．Ｅ．Ｐａｒｅｉｎ．ＳｈａｅｔｐｒＳｆｎａｏｍａｒＩｉｎｆｏｒｐｏｏ１ｙｈｅｄｒａ１ｏｊｅｂＳ．ｔＣＣｏｍＰｕｔ 刀哪ｈ．２６（２Ｘ１９２）：４７一５４・５１－沈阳工业大学硕士学位论文ｌ５５ｌＢ． Ｆｉｎｋ， Ｈ． Ｄ． Ｗｅｎｄ． Ａ ｆａｓｔ ｐａｔｈ－ｐｌａｎｎｉｎｇ ｌａｇｏｒｉｔｈｍ ｆｏｒ ｉｎｄｕｓｔｒｉｌａｒ ｏｂｏｔｓ． Ｕｎｉｖｅｒｓｉｔｙ ｏｆＤｕｉｓｂｕｒｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｏｎｔｏｒｌ Ｅｎｇｉｎｅｅｒｉｎｇ． ４１００ Ｄｕｉｓｂｕｒｇ Ｉ （ＦＲＧ）， １－６Ｉ５６］Ｐａｒｋ Ｍ．Ｇ．， Ｊｅｏｎ Ｊ．Ｈ．， Ｌｅｅ Ｍ．Ｃ．， ２００１． Ｏｂｓｔａｃｌｅ ａｖｏｉｄａｎｃｅ ｆｏｒ ｍｏｂｉｌｅ ｏｒｂｏｔｓ ｕｓｉｎｇａｒｔｉｉｆｃｉａｌ ｐｏｔｅｎｔｉａｌ ｉｆｅｌｄ ａｐｐｒｏａｃｈ ｗｉｔｈ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌ吨．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒ－ｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ ＩｎｄｕｓｔｒｉｌａＥｌ ｅｃｔｒｏｎｉｃｓ ３， Ｐｕｓａｎ， Ｋｏｒｅａ， １５３０－１５３５［５７１Ｓｉｍｏｎ Ｘ． ｙａｎｇ， Ｍａｘ Ｍｅｎｇ． Ｒｅｌａ－ｉｔｍｅ Ｃｏｌｌｉｓｉｏｎ－ｒｆｅｅ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｏｆ Ｒｏｂｏｔ Ｍａｎｉｐｕ－ｌａｔｏｒｓ ｕｓｉｎｇ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ Ａｐｐｒｏａｃｈｅｓ． Ａｕｔｏｎｏｍｏｕｓ Ｒｏｂｏｔｓ ９， ２７－３９，２０００１５８１Ｒ． Ａ． Ｂｒｏｏｋｓ． Ｐｌａｎｎｉｎｇ ｃｏｌｌｉｓｉｏｎ－ｒｆｅｅ ｍｏｔｉｏｎｓ ｆｏｒ ｐｉｃｋ－ａｎｄ－ｐｌａｃｅ ｏｐｅｒａｉｔｏｎｓ． Ｉｎｔ． Ｊ． Ｒｏ－ｂｏｔｉｃｓ Ｒｅｓｅａｒｃｈ， ｖｏｌ． ２， ｐｐ． １９－４４， １９８３１５９１Ｎｉｌｓ Ｊ． Ｎｉｌｓｓｏｎ． ＡｒｔｉｉｆｃｉｌａＩ ｎｔｅｌｌｉｇｅｎｃｅ－Ａ Ｎｅｗ Ｓｙｎｔｈｅｓｉｓ． Ｃｈｉｎａ Ｍａｃｈｉｎｅ Ｐｒｅｓｓ， ２０００１６０１Ｔｈｏｍａｓ Ｄｅａｎ， Ｊａｍｅｓ Ａｌｌｅｎ， Ｙｉａｎｎｉｓ Ａｌｏｉｍｏｎｏｓ． ＡｒｔｉｉｆｃｉｌａＩ ｎｔｅｌｉｇｅｎｃｅ－Ｔｈｅｏｙｒａ ｎｄＰｒａｃｔｉｃｅ． Ｐｕｂｌｉｓｈｉｎｇ Ｈｏｕｓｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ Ｉｎｄｕｓｔｒｙ， Ｂｅｉｊｉｎｇ， ２００３・５２－沈阳工业大学硕士学位论文在学研究成果在学期间发表的论文［１］． Ｌｉｕ Ｓｈｉｃｈｅｎｇ， Ｄｏｎｇ ７ａｉｌｉ，Ｓｕｎ Ｍａｏｘｉａｎｇ，Ｃｕｉ Ｍａｏｙｕａｎ．Ｐａｔｈ－Ｐｌａｎｎｉｎｇ Ｒｅｓｅａｒｃｈ ｏｆＲｏ ｂｏｔｓ Ｂａｓｅｄ ｏｎ Ｗａｖｅ Ｅｘｐａｎｓｉｏｎ Ａｌｇｏｒｉｔｈｍ．Ｔｈｅ ５ｓ＇ ｗｏｒｌｄ ｃｏｎｇｒｅｓｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔｃｏｎｔｒ ｏｌ ａｎｄ ａｕｔｏｍａｔｉｏｎ． ２００４．６沈阳工业大学硕士学位论文致 谢本文是在导师孙茂相教授的指导下完成的，论文的字里行间无不凝聚着孙老师的心 血。在进入课题之初，孙老师指导我抓住国内外机器人领域的最新动态与发展方向，使我能够针对课题有的放矢，而不是盲目地陷在资料堆中，少走了不少弯路。在论文的研究过程中，每当遇到难题时，他总是不厌其烦地讲解，直到明白为止。不仅如此，在攻读学位期间，孙老师还在生活上对我关怀备至。在此，谨向导师表示深深的谢意。作为一名学校的学生，我有幸在中国科学院沈阳自动化研究所进行课题研究，机器 人学开放实验室诸位老师和学友给了我许多热情的指导和帮助，没有他才门的帮助我无法完成我的学业。在论文的选题、撰稿和完成过程中，实验室的董再励研究员，都提出了许多宝贵的建议，给予了我无私的指导和帮助。同时，董老师严谨的治学态度、渊博的知识以及敏锐的思维给我留下了深刻的印象，使我受益匪浅。在此表示感谢。感谢自动控制与系统工程研究所的徐进学、王向东、吴海、崔宝侠老师对作者的指 导、关怀与教育。同时，在做课题期间，崔茂源、化建宁博士为我的日常工作提供了许多无私的帮助 与方便，在此我向他们表示最衷心的感谢。我还要感谢这几年与我朝夕相处、在学习上、生活上给了我许多支持和帮助的诸位 同学，是他们使我能够愉快的度过这段难忘的时光。一５４－
