论文部分内容阅读
摘 要：蚁群算法具有较强的鲁棒性和发现较优解的能力，但同时存在着限于局部最优解、收敛速度慢、容易出现停滞现象等缺点。本文针对球形机器人的特点，考虑球形机器人本身的尺寸影响，对其进行路径规划优化处理。并且在传统的蚁群算法基础上，采用了退回原则和信息素加强原则对该算法进行改进。通过仿真结果表明，该方法能以任意接近于1的概率收敛到全局最优解，并且提高了求解最优解的效率。
关键词：球形机器人；蚁群算法；路径规划
中图分类号：TP242
路径规划是机器人智能化程度的一个指标，其路径规划算法得出的路径越短，也就体现出了该机器人的智能化程度越高。由于球形机器人可以应用于危险环境的探测，管道内部焊缝的检测等方面，近年来国内外对于球形机器人路径规划的研究成为了一个越来越热门的话题。现在已提出的路径规划智能算法有BP神经网络算法、遗传算法、粒子群算法、模拟退火算法等，这些都是近几年比较热门的仿生启发式算法。
根据机器人对环境情况的了解程度不同，路径规划可分为三种类型：环境信息全部已知情况下的全局路径规划，环境信息部分已知情况下的局部路径规划，全局路径规划和局部路径规划相结合。局部路径规划主要依靠于机器人实时地对周围环境进行检测，从而获得机器人的位置以及周围障碍物的分布情况、尺寸大小、形状等信息，并通过这些信息规划出一条局部最优路径。因此，局部规划可以跟随环境的变化而发生改变，相对于全局规划具有较强的适应性和鲁棒性。
1 环境模型
环境模型的主要目的是将外部环境情况转变为数字、符号等可操作的一些数学量，便于为求解模型或计算机仿真提供数据。环境模型是环境状态到数学量的一个抽象映射过程，该过程在路径规划中占有重要的地位。
对于环境情况的表述有四种常用方法：（1）按照原始工作空间表示环境，（2）用栅格法表示环境，（3）空间划分（包含有三种空间：自由空间、障碍空间、混合空间）法表示环境，（4）多边形逼近法表示环境。
本文采用栅格法来表示机器人的工作环境，建立环境模型。在这里规定：（1）机器人每走一步的起始点和终止点都是栅格的中点；（2）机器人工作环境为已知且障碍物是静止的；（3）环境障碍物的数目是有限的。将工作空间的左下角定义为坐标原点O，以横向为X轴，纵向为Y轴建立直角坐标系。将工作空间划分为m*n个栅格大小相同的正方形，该边长为1。则机器人每斜走一步的步长为 ，水平和竖直方向的步长为1。其中栅格中的障碍物可能占了多个栅格，把其中不满一个栅格处理成一个栅格被占满来计算。
2 基于蚁群算法的路径规划模型
2.1 算法描述
蚁群算法可以看成是一种求解空间参数化概率分布模型的搜索算法框架，而求解空间参数化概率分布模型的参数就是信息素。本文中的路径规划的蚁群算法可以描述为：信息素模型用解构造图（栅格图）的形式表现出来，然后定义一种随机搜索的人工蚂蚁，这些蚂蚁根据构造图上的信息素的多少决定走的方向，某方向的信息素越多，人工蚂蚁将会选择走这个方向，当人工蚂蚁走过这条路，则在这条路上留下信息素。因此，根据概率分布，长度最短的路径上会留下最多的信息数，以后所有的蚂蚁将从这条路通过，最终得出在该构造图上的最优路径。
2.2 模型建立
4 结束语
本文针对球形运动器在已知环境信息情况下提出一种路径优化模型，并在此基础上考虑到球形移动器本身的尺寸，然后通过计算得出补偿后的障碍物尺寸，使得计算结果更加精确且符合实际情况。并针对蚁群算法的缺点，提出退回原则和信息素加强原则，并且对退回所经过的栅格点上的信息素去掉，从这几个方面对模型进行改进，提高了求解的收敛速度和最优解的精度，同时又不会在计算过程中出现停滞现象。根据仿真结果表明，本分提出的改进算法是有效的，并且具有较高的鲁棒性。
参考文献：
[1]史峰，王辉.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011（07）：217-228.
[2]黄席樾.现代智能算法理论及应用[M].北京：科学出版社，2005（04）：310-342
[3]覃刚力，杨家本.自适应调整信息素的遗传算法[J].信息与控制，2002（03）：198-201.
[4]王颖，谢剑英.一种自适应蚁群算法及仿真研究.系统仿真学报，2002（01）：32-33.
[5]DORIGO M，GAMBARDELLA L M. Guest Editoria： Special Section on Ant Colony Optimization[J].IEEE Transactions on Evolutionary Computation，2002（04）：317-319
[6]崔世钢，徐雪莲，赵丽，田立国，杨耿惶.蚁群优化在移动机器人路径规划上的研究[J].制造业自动化，2009（01）：5-8.
[7]王俊峰.基于改进蚁群算法的机器人路径规划[D].南京师范大学，2005.
[8]C Wongngamnit.D Angluin The robot，the grid，and the algorithm，Technical Report，YALE/DCS/TR-1188，1999.
[9]陈雄，袁杨.一种机器人路径规划的蚁群算法[J].系统工程与电子技术，2008（05）：952-955.
[10]牛晓丹，朱晓光.蚁群算法在复杂地形下的路径规划应用[J].软件导刊，2009（02）：50-51.
[11]Zhu Qingbao.Ant Colony Optimization Parallel Algorithm And Based On Coarse—grained Model[J].Computer Engineering，2005（01）：157-159.
作者简介：覃小峰，男，四川巴中人，研究方向；机械设计制造及自动化。
作者单位：西南交通大学，成都 610031
关键词：球形机器人；蚁群算法；路径规划
中图分类号：TP242
路径规划是机器人智能化程度的一个指标，其路径规划算法得出的路径越短，也就体现出了该机器人的智能化程度越高。由于球形机器人可以应用于危险环境的探测，管道内部焊缝的检测等方面，近年来国内外对于球形机器人路径规划的研究成为了一个越来越热门的话题。现在已提出的路径规划智能算法有BP神经网络算法、遗传算法、粒子群算法、模拟退火算法等，这些都是近几年比较热门的仿生启发式算法。
根据机器人对环境情况的了解程度不同，路径规划可分为三种类型：环境信息全部已知情况下的全局路径规划，环境信息部分已知情况下的局部路径规划，全局路径规划和局部路径规划相结合。局部路径规划主要依靠于机器人实时地对周围环境进行检测，从而获得机器人的位置以及周围障碍物的分布情况、尺寸大小、形状等信息，并通过这些信息规划出一条局部最优路径。因此，局部规划可以跟随环境的变化而发生改变，相对于全局规划具有较强的适应性和鲁棒性。
1 环境模型
环境模型的主要目的是将外部环境情况转变为数字、符号等可操作的一些数学量，便于为求解模型或计算机仿真提供数据。环境模型是环境状态到数学量的一个抽象映射过程，该过程在路径规划中占有重要的地位。
对于环境情况的表述有四种常用方法：（1）按照原始工作空间表示环境，（2）用栅格法表示环境，（3）空间划分（包含有三种空间：自由空间、障碍空间、混合空间）法表示环境，（4）多边形逼近法表示环境。
本文采用栅格法来表示机器人的工作环境，建立环境模型。在这里规定：（1）机器人每走一步的起始点和终止点都是栅格的中点；（2）机器人工作环境为已知且障碍物是静止的；（3）环境障碍物的数目是有限的。将工作空间的左下角定义为坐标原点O，以横向为X轴，纵向为Y轴建立直角坐标系。将工作空间划分为m*n个栅格大小相同的正方形，该边长为1。则机器人每斜走一步的步长为 ，水平和竖直方向的步长为1。其中栅格中的障碍物可能占了多个栅格，把其中不满一个栅格处理成一个栅格被占满来计算。
2 基于蚁群算法的路径规划模型
2.1 算法描述
蚁群算法可以看成是一种求解空间参数化概率分布模型的搜索算法框架，而求解空间参数化概率分布模型的参数就是信息素。本文中的路径规划的蚁群算法可以描述为：信息素模型用解构造图（栅格图）的形式表现出来，然后定义一种随机搜索的人工蚂蚁，这些蚂蚁根据构造图上的信息素的多少决定走的方向，某方向的信息素越多，人工蚂蚁将会选择走这个方向，当人工蚂蚁走过这条路，则在这条路上留下信息素。因此，根据概率分布，长度最短的路径上会留下最多的信息数，以后所有的蚂蚁将从这条路通过，最终得出在该构造图上的最优路径。
2.2 模型建立
4 结束语
本文针对球形运动器在已知环境信息情况下提出一种路径优化模型，并在此基础上考虑到球形移动器本身的尺寸，然后通过计算得出补偿后的障碍物尺寸，使得计算结果更加精确且符合实际情况。并针对蚁群算法的缺点，提出退回原则和信息素加强原则，并且对退回所经过的栅格点上的信息素去掉，从这几个方面对模型进行改进，提高了求解的收敛速度和最优解的精度，同时又不会在计算过程中出现停滞现象。根据仿真结果表明，本分提出的改进算法是有效的，并且具有较高的鲁棒性。
参考文献：
[1]史峰，王辉.MATLAB智能算法30个案例分析[M].北京：北京航空航天大学出版社，2011（07）：217-228.
[2]黄席樾.现代智能算法理论及应用[M].北京：科学出版社，2005（04）：310-342
[3]覃刚力，杨家本.自适应调整信息素的遗传算法[J].信息与控制，2002（03）：198-201.
[4]王颖，谢剑英.一种自适应蚁群算法及仿真研究.系统仿真学报，2002（01）：32-33.
[5]DORIGO M，GAMBARDELLA L M. Guest Editoria： Special Section on Ant Colony Optimization[J].IEEE Transactions on Evolutionary Computation，2002（04）：317-319
[6]崔世钢，徐雪莲，赵丽，田立国，杨耿惶.蚁群优化在移动机器人路径规划上的研究[J].制造业自动化，2009（01）：5-8.
[7]王俊峰.基于改进蚁群算法的机器人路径规划[D].南京师范大学，2005.
[8]C Wongngamnit.D Angluin The robot，the grid，and the algorithm，Technical Report，YALE/DCS/TR-1188，1999.
[9]陈雄，袁杨.一种机器人路径规划的蚁群算法[J].系统工程与电子技术，2008（05）：952-955.
[10]牛晓丹，朱晓光.蚁群算法在复杂地形下的路径规划应用[J].软件导刊，2009（02）：50-51.
[11]Zhu Qingbao.Ant Colony Optimization Parallel Algorithm And Based On Coarse—grained Model[J].Computer Engineering，2005（01）：157-159.
作者简介：覃小峰，男，四川巴中人，研究方向；机械设计制造及自动化。
作者单位：西南交通大学，成都 610031