论文部分内容阅读
摘要：自动引导车（AGV）作为柔性制造系统中的一个重要组成部分，在现代物流生产中获得了广泛的应用。为解决传统人工势场法在路径规划中出现的局部最小点问题，本文提出了预规划路径的方法，通过在局部最小点处添加中间点，使自动引导车顺利避障到达目标点。利用MATLAB进行仿真，其结果证明该方法有效地改善了传统势场法存在的缺陷。
关键词：人工势场法，AGV, 路径规划, 中间点, 预规划路径.
Abstract: Automatic Guided Vehicle (AGV) is an important component in a flexible manufacturing system, has gained wide application in the modern production. To solve the local minimum point question of traditional artificial potential field method. This paper is presented a pre-optimized path planning method, by add the middle point at the local minimum, Automatic Guided Vehicle is successfully guided avoid obstacles to reach the target point. Simulation with MATLAB, The results show that the traditional potential field defect is effective improved.
Keywords: Artificial Potential Field Method, AGV, Path Planning, The Middle Point, Pre-planning Path.
中图分类号：TU74文献标识码：A 文章编号：
1．前言
现代生产物流先进运输设备自动引导车AGV（Automated Guided Vehicle），以其自动化程度高，灵活性强，智能化等在仓储、汽车制造、医疗及烟草等行业具有广泛的应用[1-2]。与传统的运输方式相比，降低了工人的劳动强度，提高了生产效率。AGV在运输物料时躲避环境中的障碍物是其工作任务中的重要环节，AGV根据获取环境信息程度的不同可分为环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划[3]。而局部路径规划主要方法有人工势场法[4]、模糊逻辑法[5]和神经网络法等[6]。人工势场法因其在数学描述上简单明了而被广泛应用，但在进行路径规划时容易陷入局部最小值，使AGV无法顺利到达目标点。为解决这个缺点，本文通过优化势场函数和利用Dijkstra进行预规划两种方法对传统势场法进行改进，确保AGV最终达到目标点。
收稿日期：
基金项目：陕西省科技基金（SJ08E206）
作者简介：章植栋（1986-） 男 山东淄博人长安大学工程机械学院硕士研究生 研究方向：现代生产物流与控制。
2. 势场法模型及目标不可达问题
人工势场法最初由Khatib提出[7]，其基本思想是用人工势场的数值函数来描述环境空间，目标位姿产生的吸引力与障碍物产生的排斥力二者叠加构成作用在自动引导车上的合力，这个合力将“推动”小车向目标做避障运动。
引力势场函数定义为：（2.1）
斥力势场函数定义为：（2.2）
式中从 到 的欧氏距离；相应的正比例系数；
表示障碍物区域对自动引导车的运动产生影响的最大距离；
障碍物区域 到位姿 的最小距离，对所有的 ，有
小车所受吸引力和排斥力分别为[8]：
（2.3）
由于人工势场法在路径规划时会出现局部最小值的情况，即小车向目标靠近时引力场迅速减弱而斥力场不断增强，当合力 ， 时受力为零而停止不动。
3. 预规划路径的人工势场法
3.1 Dijkstra算法
Dijkstra算法是一个按权值大小递增的次序产生最短路径的算法，它可以用来计算从有向图中任意一节点到其它节点的最优路径[9]。对于上文中描述的情况应用Dijkstra算法寻找中间点构建有向图，如图1所示。假设小车从障碍物上方通过，首先应沿切线L1的方向到达顶点B，再沿切线L2的方向到达目标点；或者从障碍物的下方通过顶点C到达目标点。四边形ABCD便为所求的有向图。设带权有向图G={V,E},V={A,B,C,D},图G用邻接矩阵arcs来表示; ares[i][j]表示弧（ ）上的权值;将从A出发的最短路径点放入集合S中;分量D[i]表示从起始点到每个目标点的最短路径长度。算法过程为[10]：
（1）初始化集合 ：
（2）选择 ，使 令 ；
（3）修改从A出发到集合 上任一结点 的最短路径长度。若 ，则修改 为 ；
（4）重复（2）（3）操作 次，即可求得从A到其余各顶点的最短路径长度。
图1 Dijkstra算法有向图
Fig.1 Dijkstra algorithm direction graph
3.2 预规划的人工势场法
由上文可知传统的人工势场法在引力与斥力相等时会陷入局部最小点，因此本文提出了当自动引导小车陷入局部最小点时先由Dijkstra算法预规划路径，在障碍物旁边设立中间点的方式来对小车进行引导，使小车经中间点绕过障碍物到达目标点。如图2所示。
图2 中间点添加图
Fig.2 Adding the mid-point graph
图中虚线表示预规划路线，加入中间点后自动引导小车会先被中间点产生的引力吸引，然后绕过障碍物，最终小车在目标点引力的作用下到达终点。
3.2.1中间点的添加方法[11]：
（1）计算路径总斥力影响 ，（3.1）
（2）遍历所有的预规划路径点，将其划分为斥力影响相同的 段子路径。
（3）计算子路径的斥力影响分布密度 ，根据每段子路径的斥力影响分度密度添加中间点。中间点为子路徑的 等分点， 。 用式（4.2）计算。其中 是子路径起点， 是子路径终点。
（3.2）
3.2.2算法流程如下：
（1）初始化各项参数；
（2）搜索障碍物位置，建立势场模型用人工势场法进行避障，同时判断是否到达目标点，到达目标点后停止规划[12]。
（3）根据小车与障碍物之间的距离关系判断自动引导车是否陷入局部最小值点，若陷入最小值点则启用预规划算法，在预规划线路中设置中间点，引导小车靠近中间点，然后判断是否走出最小值点，走出后继续向目标点移动。
（4）根据势场力，得出避开下一个障碍物的路径方向。
（5）转到（2）执行。
4. 仿真实验
仿真环境基于MATLAB R2009a开发，对上文所述的优化人工势场法和预规划人工势场法进行仿真。设定环境中障碍物数量n=7，自动引导小车起始点为（0，0）目标点为（9.8，8.5），引力系数k=200，斥力系数m=50，障碍物影响距离p0=2.1，步长l=0.2，循环迭代次数j=150。优化仿真结果如图3所示。传统人工势场法进行路径规划时容易陷入局部最小值，小车受到的引力与斥力相等出现停止不前的状态无法进一步规划路径。而本文用预规划人工势场法进行路径规划，在添加中间点后小车成功脱离局部最小值点到达目标。仿真结果显示该方法有效地改善了传统势场法存在的缺陷，能合理有效地为AGV规划路径。
图3 预规划路径仿真结果
Fig.3 Pre-planning path simulation results
5．结束语
本文针对传统人工势场法存在的局部最小问题提出了预规划路径的人工势场法，通过用Dijkstra算法预规划路径并添加中间点，吸引小车经过中间点从而顺利到达目标。经仿真实验验证这种方法能够达到良好的路径规划效果,为进一步精确控制AGV打下了良好的基础。
参考文献
[1] 沈治，朱丽霞.基于自动仓储技术的自动导向小车（AGV）的研究[J].自动化博览，2009，( 6): 84- 86.
[2] 苏健凌，梁健.AGV技术及在卷烟厂的应用[J].机电工程技术，2008， 37( 11): 96- 98.
[3] 黄炳强，曹广益.基于人工势场法的移动机器人路径规划研究[J].计算机工程与应用.2006, 42(27):26-28
[4] Hwang Y K, Ahuja N. A potential field approach to path planning[J].IEEE Transactions 0n Rohotics and Automation, 1992，8:23-37.
[5] Nedungadi A.A fuzzy robot controller一hardware implementation[C].IEEE International Conference on
Robotics and Automation, 1992, 11:1325-1331.
[6] 曹有辉，王良曦.基于虚拟口标的AGV局部路径规划研究[J]. 机算机仿真，2009， 26（1）: 162- 165.
[7] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[C]//Proceedings of IEEE International Conference on Robotics and Automation. Washington, DC: IEEE, 1990: 500-505.
[8] 張毅，罗元，郑太雄，等.移动机器人技术及其应用[M].北京：电子工业出版社，2007.
[9] 陈圣群，董林飞.Dijkstra和A-star算法在智能导航中的应用分析[J].重庆科技学院学报，2010，（6）：159-161.
[10] 严蔚敏，吴伟民.数据结构(c语言版)[M].北京:清华大学出版社，1997:187-190.
[11] 姚远，周兴社，张凯龙，董冬.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用，2010，27（7）：953-959
[12] 罗胜华，刘国荣，蒋燕.一种基于改进人工势场法的移动机器人路径规划[J].机器人技术，2009， 25（10）：188-190.
姓名：章植栋出生年月：1986.9.16
学位、职称：长安大学工程机械学院硕士研究生
研究方向：现代生产物流与控制
注：文章内所有公式及图表请以PDF形式查看。
关键词：人工势场法，AGV, 路径规划, 中间点, 预规划路径.
Abstract: Automatic Guided Vehicle (AGV) is an important component in a flexible manufacturing system, has gained wide application in the modern production. To solve the local minimum point question of traditional artificial potential field method. This paper is presented a pre-optimized path planning method, by add the middle point at the local minimum, Automatic Guided Vehicle is successfully guided avoid obstacles to reach the target point. Simulation with MATLAB, The results show that the traditional potential field defect is effective improved.
Keywords: Artificial Potential Field Method, AGV, Path Planning, The Middle Point, Pre-planning Path.
中图分类号：TU74文献标识码：A 文章编号：
1．前言
现代生产物流先进运输设备自动引导车AGV（Automated Guided Vehicle），以其自动化程度高，灵活性强，智能化等在仓储、汽车制造、医疗及烟草等行业具有广泛的应用[1-2]。与传统的运输方式相比，降低了工人的劳动强度，提高了生产效率。AGV在运输物料时躲避环境中的障碍物是其工作任务中的重要环节，AGV根据获取环境信息程度的不同可分为环境信息完全知道的全局路径规划和环境信息完全未知或部分未知的局部路径规划[3]。而局部路径规划主要方法有人工势场法[4]、模糊逻辑法[5]和神经网络法等[6]。人工势场法因其在数学描述上简单明了而被广泛应用，但在进行路径规划时容易陷入局部最小值，使AGV无法顺利到达目标点。为解决这个缺点，本文通过优化势场函数和利用Dijkstra进行预规划两种方法对传统势场法进行改进，确保AGV最终达到目标点。
收稿日期：
基金项目：陕西省科技基金（SJ08E206）
作者简介：章植栋（1986-） 男 山东淄博人长安大学工程机械学院硕士研究生 研究方向：现代生产物流与控制。
2. 势场法模型及目标不可达问题
人工势场法最初由Khatib提出[7]，其基本思想是用人工势场的数值函数来描述环境空间，目标位姿产生的吸引力与障碍物产生的排斥力二者叠加构成作用在自动引导车上的合力，这个合力将“推动”小车向目标做避障运动。
引力势场函数定义为：（2.1）
斥力势场函数定义为：（2.2）
式中从 到 的欧氏距离；相应的正比例系数；
表示障碍物区域对自动引导车的运动产生影响的最大距离；
障碍物区域 到位姿 的最小距离，对所有的 ，有
小车所受吸引力和排斥力分别为[8]：
（2.3）
由于人工势场法在路径规划时会出现局部最小值的情况，即小车向目标靠近时引力场迅速减弱而斥力场不断增强，当合力 ， 时受力为零而停止不动。
3. 预规划路径的人工势场法
3.1 Dijkstra算法
Dijkstra算法是一个按权值大小递增的次序产生最短路径的算法，它可以用来计算从有向图中任意一节点到其它节点的最优路径[9]。对于上文中描述的情况应用Dijkstra算法寻找中间点构建有向图，如图1所示。假设小车从障碍物上方通过，首先应沿切线L1的方向到达顶点B，再沿切线L2的方向到达目标点；或者从障碍物的下方通过顶点C到达目标点。四边形ABCD便为所求的有向图。设带权有向图G={V,E},V={A,B,C,D},图G用邻接矩阵arcs来表示; ares[i][j]表示弧（ ）上的权值;将从A出发的最短路径点放入集合S中;分量D[i]表示从起始点到每个目标点的最短路径长度。算法过程为[10]：
（1）初始化集合 ：
（2）选择 ，使 令 ；
（3）修改从A出发到集合 上任一结点 的最短路径长度。若 ，则修改 为 ；
（4）重复（2）（3）操作 次，即可求得从A到其余各顶点的最短路径长度。
图1 Dijkstra算法有向图
Fig.1 Dijkstra algorithm direction graph
3.2 预规划的人工势场法
由上文可知传统的人工势场法在引力与斥力相等时会陷入局部最小点，因此本文提出了当自动引导小车陷入局部最小点时先由Dijkstra算法预规划路径，在障碍物旁边设立中间点的方式来对小车进行引导，使小车经中间点绕过障碍物到达目标点。如图2所示。
图2 中间点添加图
Fig.2 Adding the mid-point graph
图中虚线表示预规划路线，加入中间点后自动引导小车会先被中间点产生的引力吸引，然后绕过障碍物，最终小车在目标点引力的作用下到达终点。
3.2.1中间点的添加方法[11]：
（1）计算路径总斥力影响 ，（3.1）
（2）遍历所有的预规划路径点，将其划分为斥力影响相同的 段子路径。
（3）计算子路径的斥力影响分布密度 ，根据每段子路径的斥力影响分度密度添加中间点。中间点为子路徑的 等分点， 。 用式（4.2）计算。其中 是子路径起点， 是子路径终点。
（3.2）
3.2.2算法流程如下：
（1）初始化各项参数；
（2）搜索障碍物位置，建立势场模型用人工势场法进行避障，同时判断是否到达目标点，到达目标点后停止规划[12]。
（3）根据小车与障碍物之间的距离关系判断自动引导车是否陷入局部最小值点，若陷入最小值点则启用预规划算法，在预规划线路中设置中间点，引导小车靠近中间点，然后判断是否走出最小值点，走出后继续向目标点移动。
（4）根据势场力，得出避开下一个障碍物的路径方向。
（5）转到（2）执行。
4. 仿真实验
仿真环境基于MATLAB R2009a开发，对上文所述的优化人工势场法和预规划人工势场法进行仿真。设定环境中障碍物数量n=7，自动引导小车起始点为（0，0）目标点为（9.8，8.5），引力系数k=200，斥力系数m=50，障碍物影响距离p0=2.1，步长l=0.2，循环迭代次数j=150。优化仿真结果如图3所示。传统人工势场法进行路径规划时容易陷入局部最小值，小车受到的引力与斥力相等出现停止不前的状态无法进一步规划路径。而本文用预规划人工势场法进行路径规划，在添加中间点后小车成功脱离局部最小值点到达目标。仿真结果显示该方法有效地改善了传统势场法存在的缺陷，能合理有效地为AGV规划路径。
图3 预规划路径仿真结果
Fig.3 Pre-planning path simulation results
5．结束语
本文针对传统人工势场法存在的局部最小问题提出了预规划路径的人工势场法，通过用Dijkstra算法预规划路径并添加中间点，吸引小车经过中间点从而顺利到达目标。经仿真实验验证这种方法能够达到良好的路径规划效果,为进一步精确控制AGV打下了良好的基础。
参考文献
[1] 沈治，朱丽霞.基于自动仓储技术的自动导向小车（AGV）的研究[J].自动化博览，2009，( 6): 84- 86.
[2] 苏健凌，梁健.AGV技术及在卷烟厂的应用[J].机电工程技术，2008， 37( 11): 96- 98.
[3] 黄炳强，曹广益.基于人工势场法的移动机器人路径规划研究[J].计算机工程与应用.2006, 42(27):26-28
[4] Hwang Y K, Ahuja N. A potential field approach to path planning[J].IEEE Transactions 0n Rohotics and Automation, 1992，8:23-37.
[5] Nedungadi A.A fuzzy robot controller一hardware implementation[C].IEEE International Conference on
Robotics and Automation, 1992, 11:1325-1331.
[6] 曹有辉，王良曦.基于虚拟口标的AGV局部路径规划研究[J]. 机算机仿真，2009， 26（1）: 162- 165.
[7] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots[C]//Proceedings of IEEE International Conference on Robotics and Automation. Washington, DC: IEEE, 1990: 500-505.
[8] 張毅，罗元，郑太雄，等.移动机器人技术及其应用[M].北京：电子工业出版社，2007.
[9] 陈圣群，董林飞.Dijkstra和A-star算法在智能导航中的应用分析[J].重庆科技学院学报，2010，（6）：159-161.
[10] 严蔚敏，吴伟民.数据结构(c语言版)[M].北京:清华大学出版社，1997:187-190.
[11] 姚远，周兴社，张凯龙，董冬.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用，2010，27（7）：953-959
[12] 罗胜华，刘国荣，蒋燕.一种基于改进人工势场法的移动机器人路径规划[J].机器人技术，2009， 25（10）：188-190.
姓名：章植栋出生年月：1986.9.16
学位、职称：长安大学工程机械学院硕士研究生
研究方向：现代生产物流与控制
注：文章内所有公式及图表请以PDF形式查看。