农业机器人路径优化及轨迹跟踪研究——基于遗传算法

陈顺立

(重庆工程职业技术学院，重庆 402260)



农业机器人路径优化及轨迹跟踪研究
——基于遗传算法

陈顺立

(重庆工程职业技术学院，重庆 402260)

随着我国信息化水平的不断提高，以及机械自动化、计算机控制系统和测试计量行业的不断发展，移动机器人达到了一个全新的高度，智能机器人被广泛应用到农业生产、工业生产和高等研究等各个领域。在机器人众多研究问题中，路径规划和轨迹跟踪一直是比较复杂并较难解决的问题。为此，基于遗传算法，根据移动机器人工作特点和运动特性，采用几何法建立了机器人工作空间的环境模型，并对路径进行了有效编码，为机器人实时规划出无碰撞、路线短的全局路径，对其运动轨迹进行有效跟踪。仿真实验表明：所设计研究的机器人全局路径规划和轨迹跟踪技术具有较好的效果，其在行进过程中能及时、有效地避开前方障碍，可靠性强，稳定性好，应用前景非常广阔。

移动机器人；全局路径规划；轨迹跟踪；遗传算法

0 引言

近年来，机器人的发展获得了较大突破，工业机器人技术相当成熟，各类工业制造都开始实现自动化生产，应用于农业的移动机器人也获得了很大进展。在机器人的研究中，全局路径优化和轨迹跟踪是比较关键的环节，其对机器人自主路径规划具有重要的研究意义，是对机器人行进中路径优化控制的基础。目前，对于移动机器人轨迹优化的研究方法很多，主要采用蚁群、遗传、BP网络神经及人工智能等方法。本文引入遗传算法，对移动机器人运动过程进行全局路径优化和轨迹跟踪，可以有效提高机器人自主控制能力，实现机器人路径规划的实时性。

1 遗传算法概述

遗传算法是模拟自然选择和遗传生物进化过程中的计算模型，是一种全局搜索最优解的方法。其模拟生物研究理论中进化和遗传的过程，将生物进化中的繁殖、杂交、变异、竞争和选择引入算法中。对于具体的优化问题，常常采用具有一定数量个体抽象表示的种群，根据“适者生存,优胜劣汰”的竞争规律向更好的解进化。生物进化过程中，常常从独立随机个体种群开始，然后一代代进化发展下去。在进化中，以种群适应度为评价标准，随机选择多个生存下来的个体，通过进化规律产生新的个体种群，然后根据算法一代代迭代下去。遗传算法其实是一种计算机模拟方法，具有适用面广、多点搜索、鲁棒性好、自适应强及并行性高的特点，从本质来讲,其是一种有着自适应能力的搜索优化方法。遗传算法解决机器人路径优化及轨迹跟踪问题的流程如图1所示。

图1 遗传算法流程图

2 移动机器人环境描述与路径编码

在研究环境信息的过程中，主要有栅格法、拓扑法和几何法3种建模方法。在机器人路径优化和轨迹跟踪的研究中，常常根据环境、机器人的运动方式及需要解决问题的具体特点来选择建模方法。栅格法和拓扑法首先需要先建立一个搜索图，再根据路径搜索方法求解路径最优解，过程较为复杂，灵活性低；而几何法则是以几何信息进行环境建模，采用几何法描述环境信息，直接可以求出路径规划的最优解，表达直接、精确。因此，本文采用几何法建立环境模型，搭建前需要对作业区域进行几种假设：

1)机器人在二维平面空间运动；

2)机器人的工作区域分布有限个障碍物，并可以用(X,Y)标注；

3)扩大障碍物边界，不考虑机器人自生形状和大小，将其看作为一个质点。

障碍物标注的方法是环境建模的核心，一般采用几何标量来描述障碍物。假设在机器人作业区域XOY存在m个障碍物(O1,O2,…,Om)，第s个障碍物有nj个顶点，则作业区域中障碍物Oj可表示为

Oj={(X1,Y1),(X2,Y2),…,(Xnj,Ynj)}

(1)

其中，(Xnj,Ynj)为障碍物的第nj个顶点坐标，则

XOY={WSB,O1,…,Om}

(2)

其中，WSB为作业区域的全部边界。

根据移动机器人全局路径规划和轨迹跟踪环境建模的分析，建立如图2所示的作业区域环境模型。

图2 机器人作业区域环境模型

图2中，移动机器人作业环境为150m×150m方形区域，深色不规则形状为障碍物，一共有13个。

遗传算法迭代优化中的个体都可以看作一条路径，并可以采用编码方式进行表示。为了表示形象化以及计算方便，把路径表示为可操作的路径，称之为个体编码。

编码长度决定遗传算法优化求解时间的长短，编码太长会让求解时间成几何倍数增长。因此，在进行路径编码时常常需要简化编码长度,用一维编码表示二维轨迹。个体路径编码简化如图3所示。

图3 个体路径编码简化

图3中，S为移动机器人运动起点；G为终点。路径优化方法是在起点和中点路线间选择最优路径的点坐标(xi,yi)。在作业区域XOY中，路径点为二维，为了优化编码长度，将XOY坐标系进行变换为X′O′Y′，X′轴为起末点之间连线，并将其分为x1，x2，… ，xn，即可以将二维路径点转换位Y′坐标编码。简化格式如图4所示。

图4 简化编码格式

3 遗传算法的适应度函数

适应度函数是影响遗传算法收敛速度及能否找到最优解的直接因素，移动机器人路径规划的一般需要考虑两点：躲避障碍物和移动距离最短。一般而言，适应度函数由目标函数通过映射变换而成，常常采用评价函数加权求和法的方法确定，这种方法比较难确定权值，稳定性差，权值常常因路径与障碍物特点变化而变化。因此，在选择目标函数时，需要将其变量最小化，同时与躲避障碍物和移动距离最短最优相结合。躲避障碍物是首要条件，是移动机器人在工作区域正常作业的保证，躲避障碍物条件需要确定最优路径没有任何障碍物。假设移动机器人在图4作业区域工作，则

1)优化路径不经过障碍物，根据遗传算法神经网络模式确定适应度函数Fit(1) 为

(3)

其中，i为路径点序号；n为作业区域的障碍物总数；当路径点不经过障碍物时，适应度函数值为1，反之为0。

2)设移动机器人某一段运动距离为didi+1,则与障碍物之间不相交的适应度函数Fit(2) 为

(4)

结合式(2)和式(3)，躲避障碍物条件的适应度函数为

Fi1t=Fit(1)×Fit(2)

(5)

3)最优路径以移动距离最短为标准时，其适应度函数表示为

(6)

其中，λ是一个可以根据仿真过程进行调整且与精度相关的常数。

综上所述，移动机器人最终适应度函数为

Fit=Fi1t×Fi2t

(7)

为了简化函数变量，式(7)将躲避障碍物和移动距离最短两个约束条件结合起来，计算方便，避免了不稳定因素。

4 移动机器人全局路径规划与轨迹跟踪

4.1 移动机器人的全局路径规划

在遗传算法实现过程中，可以将优化问题对应于抗原并求解。在路径规划问题上，抗体可以抽象为求最优路径，在所有从起点到终点中选择一条最优解。路径节点求优示意如图5所示。

图5 路径节点求优示意图

路径转折点为节点，可以用Pi=(xi,yi)来表示，那么抗体可以表示为

P={P1,P2,…Pn}={(X1,Y1),(X2,Y2),…,

(Xn,Yn)}

(8)

其中，P1和P2分别表示为移动机器人起点和终点。

为了简化编码长度，提高路径优化能力，可以减少空间维数，抗体可以表示为

P={y1,y2,…yn}

(9)

在计算求解中，将该抗体编码转化为如图6所示的基因串形式。

图6 抗体编码转化为基因串形式

选择初始个体是遗传算法进行迭代算法最重要的因素。首次迭代时，其任意产生，个体的抗体节点数为一整数；而在后面迭代运算中，则采用生物进化论规律，保存抗体强的个体。

4.2 移动机器人的轨迹跟踪

移动机器人轨迹跟踪是解决机器人在t时刻如何运动的问题。如果规划路径是一条随时间变化的连续曲线，移动机器人位姿误差如图7所示，则可以根据下面方法设计轨迹跟踪器。

图7 移动机器人位姿误差

如图7所示，模拟生成的机器人规划路径为

pd(t)=((xd(t),yd(t),θd(t))T

(8)

其中，θ为目标方向角。

设定移动机器人的位姿为

p(t)=(x(t),y(t),θ(t))T

(9)

则机器人实际运动的速度为

q=(v,w)T

(10)

其中，v为移动机器人的线速度；w为移动机器人的角速度。

移动机器人位姿误差矢量表达式为

(11)

式(11)可以变换为

(12)

由以上分析可知：移动机器人轨迹跟踪的问题可以转化为求解最优线速度v和线速度w，使得对于任何初始误差的状态(ex,ey,eθ)都可以稳定在(0,0,0)附近。

5 仿真实验

为了验证遗传算法在移动机器人全局路径规划和轨迹跟踪的可行性和有效性，本文在MatLab软件中进行路径规划仿真实验，移动机器人工作起点坐标为[0,0]，终点坐标为[150,0]。为了和传统一般算法做对比，同时进行遗传算法和传统算法两种优化模式。仿真过程中两组算法采用相同的参数：初始个体共有m=50个，设定进化代数N=60，仿真结果如图8所示。

图8 MATLAB仿真结果

由图8可以看出：传统和遗传算法都可以有效对路径进行优化；从路径长度和光滑度来看，遗传算法路径较短并且光滑度高，具有更好的优化效果，优势更加明显。

6 结论

为了实现移动机器人全局路径规划和轨迹跟踪的功能，利用遗传算法对路径规划进行有效优化，采用几何法对机器人工作空间进行环境建模，并对路径采用有效编码，简化了计算的复杂性，大大提高了优化的效率和实时性。

利用MatLab软件对机器人路径规划进行了仿真实验，结果表明：遗传算法比传统算法具有更明显的优化效果；从路径长度和光滑度来看，遗传算法的全局优化效果更为明显，大大提高了机器人的可行性、可靠性和工作效率，可以有效节省作业时间，降低机器人的能量消耗，实际应用前景宽广。

[1] 江斌.人工免疫算法的基础研究及其应用[D].长沙:中南大学,2008.

[2] 张颖.改进的免疫遗传算法在基于神经网络的多机器人协作搬运中的应用[D].长沙:中南大学,2008.

[3] 陈曦.基于免疫遗传算法的移动机器人路径规划研究[D].长沙:中南大学,2008.

[4] 王评.人工免疫算法研究及其在数据挖掘上的应用[D].福州:福州大学,2005.

[5] 刘传领.基于势场法和遗传算法的机器人路径规划技术研究[D].南京:南京理工大学,2012.

[6] 崔建军.基于遗传算法的移动机器人路径规划研究[D].西安：西安科技大学,2010.

[7] 伍洲,方彦军.基于智能路径规划算法的移动机器人系统设计[J].传感器与微系统,2008(9):93-96.

[8] 赵秀平,谭冠政.基于免疫遗传算法的多约束QoS组播路由选择方法[J].计算机应用,2008(3):591-595.

[9] 刘国联,谭冠政,何燕.基于改进人工免疫算法的PID参数优化研究[J].计算机工程与应用,2008(19): 84-86.

[10] 刘国联,谭冠政,何燕.一种改进的免疫遗传算法的性能分析[J].科学技术与工程,2008(14):3773-3776, 3782.

[11] 杜宗宗,刘国栋.基于遗传模拟退火算法的移动机器人路径规划[J].计算机仿真,2009(12):118-121,125.

[12] 贾亚军,丛爽.基于相似性矢量距选择的改进人工免疫算法[J].计算机工程与应用,2011(6):26-29.

[13] 张银玲,牛小梅.蚁群算法在移动机器人路径规划中的仿真研究[J].计算机仿真,2011(6):231-234.

[14] 杨献峰,付俊辉.移动机器人路径规划的仿真研究[J].计算机仿真,2012(7):223-226.

[15] 黎竹娟.人工蜂群算法在移动机器人路径规划中的应用[J].计算机仿真,2012(12):247-250.

[16] 奚茂龙.群体智能算法及其在移动机器人路径规划与跟踪控制中的研究[D].无锡:江南大学,2008.

[17] 朴松昊,洪炳熔.一种动态环境下移动机器人的路径规划方法[J].机器人,2003(1):18-21,43.

[18] 刘国栋,谢宏斌,李春光. 动态环境中基于遗传算法的移动机器人路径规划的方法[J].机器人,2003(4): 327-330,343.

[19] 吕冬梅.足球机器人路径规划算法的研究及其仿真[D].青岛:青岛科技大学,2006.

[20] 余炎峰.基于免疫遗传算法的移动机器人全局路径规划[D].合肥:合肥工业大学,2007.

[21] 王志文,郭戈.一种新的移动机器人路径跟踪控制策略[J].兰州理工大学学报,2006(4):90-92.

[22] 牛雪梅,高国琴,鲍智达,等.基于滑模变结构控制的温室喷药移动机器人路径跟踪[J].农业工程学报,2013(2):9-16.

[23] 杨星.改进的免疫遗传算法与人工神经网络在多机器人系统围捕问题的应用[D].长沙：中南大学,2007.

[24] 杨黎明.一种改进的免疫遗传算法及在PID控制器优化设计中的应用[D].长沙：中南大学,2007.

[25] 王曙霞,涂俊英,郑艳君.基于Elitism策略的改进免疫遗传算法求解TSP问题[J].电脑知识与技术,2010(1):193-195.

[26] 黄超.模块化移动机器人控制系统及运动算法的研究[D].哈尔滨:哈尔滨工业大学,2010.

Path Optimization and Trajectory Tracking of Agricultural Robot
——Based on Genetic Algorithm

Chen Shunli

(Chongqing Vocational Institute of Engineering, Chongqing 402260, China)

With the continuous improvement of the information-based level of our country, machinery automation, computer control system and test and measurement field and the development of the mobile robot has reached a new height, intelligent robots have been widely applied to agricultural production, industrial production and higher research in various fields. Many problems in robot research, path planning and trajectory tracking is more complicated and difficult to solve the problem. The based on genetic algorithm, according to the characteristics of mobile robot and motion characteristics by geometric method of robot work space environment model is established, and the path for the effective coding, for real-time robot planning a collision free, short routes for the global path, and the motion trajectory tracking. Simulation results show that in this paper, the design of robot global path planning and trajectory tracking technology of, with good effect, in the process of moving can be a timely and effective to avoid the obstacles ahead, its reliability, stability, application prospects very broad.

mobile robot; global path planning; trajectory tracking； genetic algorithm

2016-05-05

重庆市教委教改项目(142079)；重庆市社会科学基金项目(2014BS103)

陈顺立(1973-)，男，河南西平人，副教授，硕士，(E-mail)csl73@sina.cn。

S126；TP242

A

1003-188X(2017)08-0017-05