基于蚁群算法的移动机器人智能路径规划应用
摘要：随着机器人在各领域的广泛应用和人工智能的不断发展，路径规划研究作为机器人应用领域的重要课题受到越来越多的关注。文章分析了机器人发展现状以及路径规划算法，重点阐述了智能路径规划与传统路径规划的优缺点，利用蚁群算法对移动机器人路径规划中实际应用问题进行了研究，并提供一些实际解决方案。
关键词：蚁群算法；移动机器人；路径规划
中图分类号：TP249 文献标识码：A 文章编号：1673-1131（2015）10-0030-02.
0 引言
近年来，伴随着机器人在各行业各领域的广泛应用和深入研究，传统的路径规划方式已经难以满足某些领域中高精度高效率的路径规划要求，亦不能随着实际环境的变化而迅速适应，因此智能路径算法不断被发展和研究并应用到机器人路径规划算法中。
范路桥等[1]介绍了蚁群算法，该算法是意大利学者Dorigo和 Colorni 在 1991 年提出的一种受生物启发的全新启发式仿生优化算法，他们模拟了现实世界中蚂蚁种群的行为模式，借鉴其用以解决目标在各种分布环境下的组合优化问题 [2]。蚁群算法很适合解决复杂的路径规划，因此本文将采用蚁群算法来解决智能机器人路径规划问题[3]。
1 问题的设计
在一个 800cm×800cm 的正方形平面，从原点 O(0, 0)点处将有一个机器人开始作业，它只能在该平面上活动。平面中有 12 个不同形状的障碍物，在作业过程中机器人不能与障碍物发生碰撞，障碍物的位置和形状描述如下表： 在平面内指定一点为机器人要到达的目标点，为了避免碰撞要求目标点与障碍物的距离至少超过 10cm。该机器人由于设计原因，只能以直线段和圆弧构成运行路径，圆弧是机器人转弯时的路径。该机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为 10cm。为了避免与障碍物发生碰撞，要求机器人行走线路与障碍物间的最近距离为 10cm，否则将发生碰撞。
问题：机器人从O(0,0)出发需要到达目标点B（100，700），找出 O→B 的最短路径。 2 模型的建立与求解2.1 模型假设（1）假设机器人的自身宽度忽略不计。这样，机器人的运动可以看成是一个点的移动。
（2）假设障碍物始终是题目所给的 12 个不同形状的区域，且位置、大小等性质一直不变。
2.2 模型的求解
2.2.1 简化赋权图
在本文中，我们将路线图简化为一个赋权网络图，并利用蚁群算法，找出最短路径的大致路线。首先，构造赋权网络图如下：
我们把平面上的一些点编号，并将它们之间的距离关系简化为网络图（如图 1）。如果节点直接可以直线到达而不遇到障碍物，则它们之间的边的权重为直线距离，否则它们之间没有边，如图 2： 2.2.2 用蚁群算法求上述简化网络图中求的最短路径（1）蚁群算法模型。将点 1→15 是否在路径上分别取值为 0 到 1 ，这样就形成了 15 位的 0 ，1 序列，从而计算这条路 径的距离。将距离作为信息素的一个映射变量，由于要求最短路，所以可以使用倒数或者相对距离作为信息素浓度。这样就可以获得每只蚂蚁的转移概率，若转移概率大于全局转移因子，则进行全局转移；否则以一定的步长进行转移。这样就可以逐步向全局最优解靠近。
（2）执行步骤：①初始化 N 只蚂蚁。实际上就是 N 条道路，并计算当前的蚂蚁位置；②初始化运行参数，开始迭代；③在迭代补数范围内，计算转移概率，如果小于全局转移概率就进行小范围的搜索，否则进行大范围的搜索；④更新信息素，记录状态，准备进行下一次迭代；⑤转第三步；⑥输出结果。
（3）编程实现：具体步骤操作借助 matlab 数学软件实现。
（4）结果分析：50 只蚂蚁的初始状态是无序分布的，优化后蚂蚁移动后的最终位置实现了两级分化，这样我们就得到了最优解。
图 3 分别是平均和最优的变化曲线，从中可以知道，算法收敛速度很快，效果较好。
最短路是 1→4→8→9→11→14→15。染色体是：100100011010011，运行时间是 0.3910。 2.2.3 用优化模型求解中各分段路径的距离在上一部分中，我们已经确定了最短路的运行路线是按照图 1 中的节点 1→4→8→9→11→14→15 ，但是这个简化图中距离只考虑了直线，而没有考虑实际行走中的圆弧长度。因此，我们将这条路线进行分段，使得每段路线只绕开一个障碍物。
基于以上分析，将从 O→B 这条路线分为 L（1 O→B3）、L（2 B3→B6）、L（3 B6→B9）、L（4 B9→B12）、L（5 B12→B）五段路线，分别计算它们的长度，然后再相加，从而求出 O→B 的最短路径（如图 4） （1）求 O→B3 的最短路径的模型。在求 O→B3 的最短路 径时，我们将 O 点、B3 点、Q1 点的坐标作为路线起点（a,b）、终点(c,d) 为和圆弧圆心坐标(m,n) 的变量值。即：
将切点坐标为 B1(x1,y1) ，B2(x2,y2) 作为决策变量, 以 O→B3长度最短为目标函数，构造如下优化模型：
（5）求解上述模型，得到：
OB3 最短路径长度：Smin=397.0986
两个圆弧切点坐标：
（2）求 B3→B6 的最短路径模型。利用与上一段路线相同的优化模型，将 B3 点、B6 点、Q2 点的坐标作为路线起点(a,b) 、终点(c,d) 为和圆弧圆心坐标(m,n) 的变量值。即：
求解优化模型，得到 B3B6 最短路径长度。
同理，我们可以计算出其他分段路线的最短路径。
综上，我们得出 O→B 的最短路径（如表 3）：
表 3 O→B 的最短路径 3 结语
随着机器人研究的发展和人工智能领域的不断深入，运用蚁群算法能够解决实际工作中的机器人路径规划计算问题，本文希望提供利用蚁群算法对移动机器人路径规划中实际问题提供参考性的解决方案，但也存在着一些局限，如最短路径模型仍有待优化等，需要在今后的研究中进一步深入探讨。
参考文献：
[1] GUO Yu, LI Shi-yong.(2009) Path Planning for Robot Based on Improved Ant Colony Algorithm. Computer Measurement and Control, 17(1):pp.187-190.
[2] Zhu Qingbao. Ant Colony Optimization Parallel AlgorithmAnd Based On Coarse-grain Model[J].Computer Engineering,2005,31(1):157-159.
[3] Zhu Qingbao.Ants Predictive Algorithm For Path PlanningOf Robot In A Complex Dynamic Environment[J].ChineseJournal of Computers,2005,28(11):1898-1906.
作者简介：徐思（1983-），女，江西九江人，硕士，副教授，主要研究方向为数学模型应用。
