基于栅格模型机器人路径规划的改进蚁群算法

《基于栅格模型机器人路径规划的改进蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第２６卷第１０期计算机应用与软件Ｖｏｌ２６Ｎｏ．１０２００９年１０月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＯｃｔ．２００９基于栅格模型机器人路径规划的改进蚁群算法王沛栋冯祖洪（北方民族大学计算机科学与工程学院宁夏银川７５００２１）摘要提出了一种静态环境下机器人路径规划的改进蚁群算法。该算法使用栅格法对机器人的工作空间进行建模，通过模拟蚂蚁的觅食行为，采用折返的迭代方式对目标进行搜索；在搜索过程中，以移动方向一定范围内最大信息素和目标引导函数作为启发式因子；此外，根据蚁群算法处理本问题时信息素散播的特点，重构了信息素的更新策略和散播方式。仿真试验结果表明，改进措施使最

2、优路径的寻找快速而高效，即使在障碍物非常复杂的环境下，算法也能迅速地规划出一条最优路径。关键词机器人蚁群算法路径规划ＡＮＩＭＰＲＯＶＥＤＡＮＴＣＯＬＯＮＹＡＬＧＯＲＩＴＨＭＢＡＳＥＤＯＮＧＲＩＤＭＯＤＥＬＦＯＲＭＯＢＩＬＥＲＯＢＯＴＰＡＴＨＰＬＡＮＮＩＮＧＷａｎｇＰｅｉｄｏｎｇ　ＦｅｎｇＺｕｈｏｎｇ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮｏｒｔｈＮａｔｉｏｎａｌｉｔｙＵｎｉｖｅｒｓｉｔｙ，Ｙｉｎｃｈｕａｎ７５００２１，Ｎｉｎｇｘｉａ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ　　Ａｎｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｐｒｏｖｉｄｅｄｉｎｔｈｉ

3、ｓｐａｐｅｒｆｏｒｒｏｂｏｔｐａｔｈｐｌａｎｎｉｎｇｕｎｄｅｒａｓｔａｔｉｃｅｎｖｉｒｏｎｍｅｎｔ．Ｉｎｔｈｉｓａｌｇｏｒｉｔｈｍｔｈｅｍｏｄｅｌｏｆｒｏｂｏｔ’ｓｗｏｒｋｓｐａｃｅｉｓｅｓｔａｂｌｉｓｈｅｄｗｉｔｈｇｒｉｄｍｅｔｈｏｄ，ａｎｄｆｏｒｔａｒｇｅｔｓｅａｒｃｈｉｎｇｉｔｕｓｅｓｆｏｌｄｂａｃｋｉｔｅｒａｔｉｖｅｍｅｔｈｏｄａｎｄｓｉｍｕｌａｔｅｓｔｈｅｆｏｒａｇｉｎｇｂｅｈａｖｉｏｕｒｏｆｔｈｅａｎｔｃｏｌｏｎｙ．Ｄｕｒｉｎｇｔｈｅｓｅａｒｃｈｉｎｇｐｒｏｃｅｓｓｗｅｕｓｅｍａｘｉｍｕｍｐｈｅｒｏｍｏｎｅｉｎａｍｏｖｉｎｇｄｉｒｅｃｔｉｏｎｒａｎｇｅａｎｄａｇｏａｌｇｕｉｄｉ

4、ｎｇｆｕｎｃｔｉｏｎａｓｔｈｅｈｅｕｒｉｓｔｉｃｆａｃｔｏｒｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｆｅａｔｕｒｅｓｏｆｔｈｅｐｈｅｒｏｍｏｎｅｓｔｒｅｗｉｎｇｗｈｅｎｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｂｙａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｔｈｅｓｔｒｅｗｉｎｇｍｏｄｅａｎｄｕｐｄａｔｉｎｇｓｔｒａｔｅｇｙｏｆｔｈｅｐｈｅｒｏｍｏｎｅａｒｅｒｅｃｏｎｓｔｒｕｃｔｅｄ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｓｅｉｍｐｒｏｖｅｍｅｎｔｓｍａｋｅｔｈｅｓｅａｒｃｈｏｆｔｈｅｏｐｔｉｍａｌｐａｔｈｒａｐｉｄｌｙａｎｄｅｆｆｉｃｉｅｎｔｌｙ．Ｗｉｔｈｔｈｉ

5、ｓｍｅｔｈｏｄａｎｏｐｔｉｍｉｚｅｄｐａｔｈｃａｎｂｅｆｏｕｎｄｒａｐｉｄｌｙｅｖｅｎｉｆｔｈｅｏｂｓｔａｃｌｅｓａｒｅｅｘｃｅｅｄｉｎｇｌｙｃｏｍｐｌｉｃａｔｅｄ．Ｋｅｙｗｏｒｄｓ　　Ｒｏｂｏｔ　Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ　Ｐａｔｈｐｌａｎｎｉｎｇ机器人的起始点作为根节点，向目标点方向进行延伸，每次选取０　引言距离目标点最近的叶子节点进行扩展。这种方法简单、收敛速度快。但是它缺乏对整体环境的搜索，而且扩展原则单一，容易机器人路径规划是机器人学研究领域中的一个重要部分，使算法陷入“死锁”状态。本文提出一种基于栅格模型的改进其任务是在具有障碍物的环境内，按照一定的评价标准（工作蚁群

6、优化算法，通过模拟蚂蚁的觅食行为，采用折返的迭代方式代价最小、行走路线最短等）寻找一条从起始状态（包括位置和对目标进行搜索，在搜索过程中，以移动方向上一定范围内最大姿态）到目标状态（位置和姿态）与障碍物无碰的最短路径。信息素和目标引导函数作为启发式因子，此外，利用蚁群算法处栅格法是对平面移动机器人运动环境的一个抽象模型。它理本问题时信息素散播的特点，重构了信息素的更新策略和散把机器人的工作空间分割成规则而均匀的栅格，每个栅格可为播方式。试验结果表明，本文提出的算法与其它优化算法相比，两种状态，它们表示该栅格处是否存在障碍，没有障碍的栅格称在解的质量和收敛速度上都显示出了良好的性能。为自由栅格

7、，否则为障碍栅格。在机器人移动的过程中，栅格的尺寸和位置不变，并且栅格的尺寸通常与机器人的移动步长及１　问题描述及数学模型机器人的尺寸一致。栅格法直观且建模比较容易，因此得到了广泛的应用。基于栅格模型求解有许多方法，例如：随机树算基于栅格模型的机器人路径问题可以表示为一个约束优化法、遗传算法、神经网络等。这些方法几乎都存在搜索空间大、问题，它可简单地描述如下：算法复杂、效率不高等问题，特别是当障碍物的数目增加