基于蚁群算法与人工势场法的机器人路径规划-研究生选题报告

机器人是一种可编程和多功能的，用来搬运材料、零件、工具的操作机;或是为了执行不同的任务而具有可改变和可编程动作的专门系统。机器人作为人类的一种新型的生产工具在提高生产效率、降低劳动强度、扩展工作区域，从危险、复杂、恶劣的情况下将人类的劳动力解放出来的过程中显示出了极大的优越性。随着机器人的研究的逐步深入，现代的机器人更是感知、决策、行动和交互技术的高度有效结合的产物。根据应用领域的不同，机器人可以分为移动机器人、医疗机器人、空中机器、水下机器人、军用机器人等各种智能机器人，它们在外形上己远远不再是最初仿人形机器人和工业机器人，而是根据不同的特殊应用领域而制定的。移动机器人自主导航包含的问题有：机器人定位，机器人路径规划以及机器人的运动控制。移动机器人的路径规划在其中占据着主导的地位，也是各领域各学科研究的重点，是衡量机器人性能指标的一大主要研究方向。移动机器人路径规划具体是指在环境中存在障碍物的情况下，机器人按照一定的评价标准在一定时间内获得一条从运动起点到目标终点的没有碰撞的较优路径。机器人的路径规划问题从上世纪70年代就得到了诸多学者和专家的重点关注。路径规划规划算法的运算复杂度、稳定性，间接影响着机器人的工作效率，结果的优劣同样影响着机器人动作的准确性和实时性。所以说，路径规划是实现机器人自主导航问题中最至关重要的一部分。一个好的路径规划应该能在较短的时间内找到一条较优的路径，该路径不但可以避开环境中的障碍物而且还能处理环境中未知情况。早在20世纪就有科学家预测：20世纪的核心作战武器是坦克，21世纪的核心作战武器重心则会转移向无人作战系统发展。从上个世纪60年代末开始，以美国为首的发达国家就已经对智能机器人展开了着重的研究工作，NilsNilsson和CharlesRosen等[2]人，于1966年至1972年间在斯坦福研究院(SRI)研制了名为Shakey的自主移动机器人，用于在复杂环境下的自主推理、规划和控制。在此期间著名的GeneralElectricQuadruped[3]的步行机器人也被研制成功，开辟了步行机器人的研究领域。进入70年代，随着计算机和传感器领域的迅速发展，移动机器人的研究进入了一个新的高潮，日本早稻田大学研制出具有仿人功能的两足步行机器人。为适应原子能利用和海洋开发的需要，极限作业机器人和水下机器人也以较快的速度发展起来。美国国防高级研究计划局(DARPA)专门立项，制定了地面无人作战平台的战略计划，揭开了室外移动机器人研究的序幕。如DARPA的“战略计算机”计划中的自主地面车辆(ALV)计划(1983-1990);能源部制定的为期10年的机器人和智能系统计划RIPS(1986-1995)，以及后来的空间机器人计划;欧洲尤里卡中的机器人计划和日本通产省组织的极限环境下作业的机器人计划等[4]。进入20世纪以后以美国为代表在军用和民用领域对于机器人的研究处于迅猛发展的阶段，机器人被广泛应用于各个领域之中。在移动机器人路径规划方面，W.E.Howden于1968年提出了栅格法来对路径规划进行研究[2]。在进行路径规划的时候将地图划分成为大小相同的若干个小的栅格，将存在障碍物的栅格均划分出来，在处理不规则障碍物的时候就有良好的适应性。在划分栅格的时候，划分的栅格越多，障碍物的表示会越精确，但同时占用的存储空间也会相应增加,算法的搜索范围将按指数增加。栅格的粒度太大，规划的路径会很不精确。所以栅格粒度大小的确定,是栅格法在实际应用中的主要问题。人工势场法是Khatib于1986年首次提出的，由于其计算简便，实时性强等优点，许多学者都先后研究发展这一方法，并将其应用于机器人的实时路径规划和运动控制中。人工势场法路径规划技术的基本思想是把机器人在环境中的运动视为一种机器人在虚拟的人工受力场中的运动。障碍物对机器人产生斥力，目标点对机器人产生引力，引力和斥力的合力作为机器人的控制力，从而使机器人避开障碍物而达到目标位置[4]。人工势场法,具有反应速度快、计算量小和实时性等优点，但同时这种方法也存在弊端，比如当障碍物与目标点处于机器人的同一连线上时容易产生局部极值点,导致机器人停止移动,无法到达目标区域，其另一个重要缺点就是它只根据障碍物和机器人的位置生成作用力,而无法考虑机器人的速度，在机器人快速移动时可能会出现计算失败的情况[5]。2.1.2本课题国内研究进展路径规划是移动机器人自动寻径问题中需要解决的最为关键也最为重要的问题，本课题的设计任务就是研究如何利用蚁群算法以及人工势场法为移动机器人进行路径优化，在起始点与目标点直接找到一条路径较短，用时最快的避障路线。主要研究内容包括：了解目前常用移动机器人路径规划算法的基本思想及其特点。

（2）弄清蚁群算法的基本原理及具体实现方法。

（3）对蚁群算法进行必要的改进。

（4）用C（或MATLAB）语言编制程序，进行路径规划算法的仿真研究。3.2研究方法3.2.1蚁群算法概述现阶段越来越多的学者专家对仿生智能算法进行研究探讨，如模拟生物界中的遗传规律和自然选择的遗传算法、模拟蚂蚁群体觅食行为的蚁群算法等。意大利学者MarcoDorigo和他的同事受自然界中真实蚂蚁群体行为的启发，于1991年首次提出蚁群算法(AntColonyOptimizationACO)这个新型的启发式路径搜索算法概念。经过长期研究发现每只蚂蚁在外出寻找食物源、搬家等行为过程中都能够在所经过的路径上释放一种称之为信息素的分泌物，蚁群之间通过这种信息素相互通信和路径选择，同时蚁群会自发的向信息素浓度高的方向移动。随着时间的推移，蚁群之间的集体行为表现出正反馈现象，当某一条路径上走过的蚂蚁数量越多，积累的信息素浓度越大，随后越多的蚂蚁选择该路径，释放的信息素浓度进一步增强，从而能很快的找到最优路径。目前该算法被广泛的应用于求旅行商问题(TSP)、作业调度、二次分配、车辆路径、多选择背包及网络路由等问题，取得了良好的实验效果。3.2.2蚁群算法基本原理现实生活中蚂蚁们能通过相互协调、分工合作来完成一系列活动如迁徙、筑巢寻找食物以及清扫等活动。其中蚁群可以在可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随着环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的抽象，提出了人工蚁的概念。人工蚁和真实蚂蚁有如下相同点:(1)人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种解决方案，整个蚁群相互合作在全局范围内找出问题的较优的解决方案。(2)人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。(4)人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。(5)在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况，(6)不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局部信息，而没有前瞻性的预测未来的状态。

针对人工势场法和蚁群算法各自的特点，部分学者利用势场力改变蚁群算法状态转移规律，将蚁群算法与人工势场力巧妙地结合在了一起。本课题将蚁群算法与人工势场力结合起来，蚂蚁在栅格环境区域内移动，不仅受到了信息素浓度和距离启发信息的作用，同时还受到了人工势场力的影响。人工势场力的作用使移动机器人在移动过程中迅速的规避障碍物，向着目标位置前行，它可以作为势场蚁群算法的另一种启发信息。一般在路径规划初期由于路径信息素浓度较弱，蚁群的正反馈作用效果不明显，因此需要侧重于势场信息作用，而随着蚂蚁迭代次数的增加，路径上信息素浓度增多，正反馈作用增强，此时需要降低势场力作用，势场力启发信息影响系数的引入很好的平衡了蚁群算法和人工势场算法在整个路径规划过程中的作用。势场蚁群算法在路径规划时利用蚁群全局路径搜索机制，综合势场力启发信息和距离启发信息的作用，能有效的避开己知环境中障碍物，寻找到一条从起始位置到目标位置的最优路径。[12011，30（2）：5-8[2]2011，7（4）：348-351[3]2009，20（4）：70-74[4]2006，42（27）：26～28[5]2011，（23）：50[6]2010，s1：814-816[7]2010，（11）：24-25[8]..2011，24（5）：81-82[9]..2005[10]..2004，33（2）