第２６卷第１０期计算机应用与软件Ｖｏｌ２６Ｎｏ．１０２００９年１０月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＯｃｔ．２００９基于栅格模型机器人路径规划的改进蚁群算法王沛栋冯祖洪（北方民族大学计算机科学与工程学院宁夏银川７５００２１）收稿日期：２００８－０５－０５。宁夏自然科学基金项目（ＮＺ０６９７）。王沛栋，硕士生，主研领域：人工智能，计算机网络。摘要提出了一种静态环境下机器人路径规划的改进蚁群算法。该算法使用栅格法对机器人的工作空间进行建模，通过模拟蚂蚁的觅食行为，采用折返的迭代方式对目标进行搜索；在搜索过程中，以移动方向一定范围内最大信息素和目标引导函数作为启发式因子；此外，根据蚁群算法处理本问题时信息素散播的特点，重构了信息素的更新策略和散播方式。仿真试验结果表明，改进措施使最优路径的寻找快速而高效，即使在障碍物非常复杂的环境下，算法也能迅速地规划出一条最优路径。关键词机器人蚁群算法路径规划ＡＮＩＭＰＲＯＶＥＤＡＮＴＣＯＬＯＮＹＡＬＧＯＲＩＴＨＭＢＡＳＥＤＯＮＧＲＩＤＭＯＤＥＬＦＯＲＭＯＢＩＬＥＲＯＢＯＴＰＡＴＨＰＬＡＮＮＩＮＧＷａｎｇＰｅｉｄｏｎｇＦｅｎｇＺｕｈｏｎｇ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＮｏｒｔｈＮａｔｉｏｎａｌｉｔｙＵｎｉｖｅｒｓｉｔｙ，Ｙｉｎｃｈｕａｎ７５００２１，Ｎｉｎｇｘｉａ，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＡｎｉｍｐｒｏｖｅｄａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｉｓｐｒｏｖｉｄｅｄｉｎｔｈｉｓｐａｐｅｒｆｏｒｒｏｂｏｔｐａｔｈｐｌａｎｎｉｎｇｕｎｄｅｒａｓｔａｔｉｃｅｎｖｉｒｏｎｍｅｎｔ．Ｉｎｔｈｉｓａｌｇｏｒｉｔｈｍｔｈｅｍｏｄｅｌｏｆｒｏｂｏｔ’ｓｗｏｒｋｓｐａｃｅｉｓｅｓｔａｂｌｉｓｈｅｄｗｉｔｈｇｒｉｄｍｅｔｈｏｄ，ａｎｄｆｏｒｔａｒｇｅｔｓｅａｒｃｈｉｎｇｉｔｕｓｅｓｆｏｌｄｂａｃｋｉｔｅｒａｔｉｖｅｍｅｔｈｏｄａｎｄｓｉｍｕｌａｔｅｓｔｈｅｆｏｒａｇｉｎｇｂｅｈａｖｉｏｕｒｏｆｔｈｅａｎｔｃｏｌｏｎｙ．Ｄｕｒｉｎｇｔｈｅｓｅａｒｃｈｉｎｇｐｒｏｃｅｓｓｗｅｕｓｅｍａｘｉｍｕｍｐｈｅｒｏｍｏｎｅｉｎａｍｏｖｉｎｇｄｉｒｅｃｔｉｏｎｒａｎｇｅａｎｄａｇｏａｌｇｕｉｄｉｎｇｆｕｎｃｔｉｏｎａｓｔｈｅｈｅｕｒｉｓｔｉｃｆａｃｔｏｒｓ．Ｆｕｒｔｈｅｒｍｏｒｅ，ａｃｃｏｒｄｉｎｇｔｏｔｈｅｆｅａｔｕｒｅｓｏｆｔｈｅｐｈｅｒｏｍｏｎｅｓｔｒｅｗｉｎｇｗｈｅｎｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍｂｙａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｔｈｅｓｔｒｅｗｉｎｇｍｏｄｅａｎｄｕｐｄａｔｉｎｇｓｔｒａｔｅｇｙｏｆｔｈｅｐｈｅｒｏｍｏｎｅａｒｅｒｅｃｏｎｓｔｒｕｃｔｅｄ．Ｔｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｓｅｉｍｐｒｏｖｅｍｅｎｔｓｍａｋｅｔｈｅｓｅａｒｃｈｏｆｔｈｅｏｐｔｉｍａｌｐａｔｈｒａｐｉｄｌｙａｎｄｅｆｆｉｃｉｅｎｔｌｙ．Ｗｉｔｈｔｈｉｓｍｅｔｈｏｄａｎｏｐｔｉｍｉｚｅｄｐａｔｈｃａｎｂｅｆｏｕｎｄｒａｐｉｄｌｙｅｖｅｎｉｆｔｈｅｏｂｓｔａｃｌｅｓａｒｅｅｘｃｅｅｄｉｎｇｌｙｃｏｍｐｌｉｃａｔｅｄ．ＫｅｙｗｏｒｄｓＲｏｂｏｔＡｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍＰａｔｈｐｌａｎｎｉｎｇ０引言机器人路径规划是机器人学研究领域中的一个重要部分，其任务是在具有障碍物的环境内，按照一定的评价标准（工作代价最小、行走路线最短等）寻找一条从起始状态（包括位置和姿态）到目标状态（位置和姿态）与障碍物无碰的最短路径。栅格法是对平面移动机器人运动环境的一个抽象模型。它把机器人的工作空间分割成规则而均匀的栅格，每个栅格可为两种状态，它们表示该栅格处是否存在障碍，没有障碍的栅格称为自由栅格，否则为障碍栅格。在机器人移动的过程中，栅格的尺寸和位置不变，并且栅格的尺寸通常与机器人的移动步长及机器人的尺寸一致。栅格法直观且建模比较容易，因此得到了广泛的应用。基于栅格模型求解...
