基于云模型的农业移动机器人人机合作路径规划

张欣欣，薛金林

(南京农业大学 工学院，江苏 南京，210031)

基于云模型的农业移动机器人人机合作路径规划

张欣欣，薛金林

(南京农业大学 工学院，江苏 南京，210031)

【目的】实现农业移动机器人在复杂动态的农业环境中实时准确地无碰撞行驶。【方法】基于云模型的不确定性在线推理方法，提出一种基于云模型的动态引导A*(CDGA*)算法进行人机合作路径规划，将人的专业知识和喜好等引入DGA*优化中，实现机器人更快速的路径规划。利用Matlab软件对CDGA*算法与DGA*算法进行仿真对比分析。【结果】静态路径规划中，DGA*算法与CDGA*算法的close的点数分别为158和96，人员规划时间分别为8.8和4.0 s，规划总时间分别为15.6和8.9 s；动态路径规划中，DGA*算法与CDGA*算法的人员规划时间分别为12.5和5.8 s，规划总时间分别为23.3和14.6 s。【结论】提出的CDGA*算法能够大大减少产生的节点数，缩短规划时间，提高搜索效率。

农业移动机器人；人机合作；云模型；DGA*算法；CDGA*算法；路径规划

农业移动机器人的应用是农业向现代化智能化发展的标志。随着现代高新技术发展，很多学者都致力于对农业移动机器人更高智能化控制的研究工作中。其中，移动机器人在行驶中能够绕过障碍物从起始点到达目标点的路径规划问题，是移动机器人研究领域一个非常重要的方面。

神经网络[1]、遗传算法[1]、概率路径法[2]、SPRM 法[3]、蚁群算法[4-5]、模糊控制算法[6]、人工势力场[7]等路径规划方法与智能算法之间的多次改进或组合设计，实现了移动机器人在多种复杂条件下的路径避障规划。而A*算法灵活，适用性强，在路径搜索中更是受到了众多学者的热捧。王殿君[8]对A*算法进行改进设计，减少了生成的轨迹点数目，简化了路径，实现了移动机器人拐点处的自身姿态调整，以满足其在室内的全自主行走。Dong等[9]对A*算法进行改进，提出了稀疏A*(SAS)算法，大大缩小了搜索空间，提高了静态路径规划效率。近年来，基于机器智能化水平的局限性，国内外学者提出了“人机交互、人机合作”的理念，充分发挥人与机器的长处，共同协作，使机器发展更加智能化[10-12]。在 Robohub 的时事通讯[13]中，Eldert指出，农业机器人的推广应用，要做到“快速、准确、100%成功并节约成本”，才能保证农业产量与可持续性发展的要求。同时，人与机器人并肩完成工作，将会提高农业机器人进行农业作业任务时的被动接受程度和灵活度，便于迎接更多具有挑战性的农业作业任务，是目前农业机器人的发展趋势。

我们以一个具有一定智能水平的农业移动机器人为研究对象，在不改变硬件成本的条件下，对SAS算法改进设计，提出动态引导A*(DGA*)算法，以满足机器人在复杂非结构性农业动态环境下的路径规划需求；同时引入云模型[14]的在线推理方法将人的专业知识与偏爱等加入提出的算法中，进行人机协同作业，以保证机器人动态路径规划时的效率与可靠性。

1 农业移动机器人的规划空间模型

农业移动机器人在自主行走时，若周围环境无新的障碍物，会按照原先设定的航线行驶。在行驶过程中出现动态障碍物，机器人需要暂停行驶并重新进行路径规划。设(x，y)为规划空间某一点的坐标，规划空间模型为：

考虑二维空间，将规划空间已存在或后来新增的障碍物(威胁区域)都看作圆形，设(xi，yi)为第i个威胁区域的中心坐标，ri为第i个威胁的半径，m，则第i个威胁区域模型可表示为：

2 动态引导A*(DGA*)算法的实现

2.1 节点的扩展

A*算法是路径规划中应用广泛的启发式搜索算法。传统的A*算法受栅格限制，搜索范围过广，导致很多无用节点被扩展，搜索效率较低，并且不能预先感知规划空间的威胁区域，很容易陷入地图死角进而导致路径规划失败。为了解决传统A*算法的弊端，本研究提出一种基于稀疏A*(SAS)算法的动态A*(DGA*)路径规划算法，以期提高搜索效率。

规划空间中第i个节点的信息(Ii)可以表示为[15]：

式中，xi，yi是节点 i的坐标；θi为节点 i的水平角度；Lsi是起始点到节点i的实际距离；fatheri为节点 i的父辈节点；gi，hi，fi为节点 i的代价值。

为保证机器人前进的航线，以节点i的水平方向角为中心线向左右两边各扩展至车轮的最大转弯角，将所形成的扇形面积作为下一个节点i+1的扩展范围。

式(4)～式(6)中，α为节点i的扩展子节点的单位角度，M为节点i产生的子节点的总数，θmax为机器人的最大转弯角，l为扩展步长，(xi+1，yi+1)为子节点i+1的坐标值。

2.2 代价函数的确定

A*算法代价函数f(i)由起点到当前节点i的实际代价值g(i)和当前节点到目标点的预估代价值h(i)组成，其一般表达式[16]为：

为解决农业移动机器人在未知环境中的实时动态无碰撞路径规划，不仅需要最大转弯角、最大扩展节点数、搜索步长等约束条件，把人工在线干预的方式形成的以引导点为中心、引导半径为大小的引导场设置为子目标作为新增约束条件，更能进一步优化SAS算法，提高搜索效率[17]。

利用引导场对机器人的路径进行规划时，一个合理的代价函数能更有效地引导路径规划器探寻顺序通过引导场的最优路径。

2.2.1 实际代价函数 设路径规划的起点坐标为S，目标点坐标为 D，节点 i的坐标为 Ci=(xi，yi)，机器人从起点到达节点i的路径Z用节点形式可以描述为 Z=(S，C1，C2，…，Ci)，考虑路径长度、风险和光滑度的影响，则节点i的实际代价为：

式中，ω1、ω2和ω3是距离、风险和光滑度成本各自对应的权重系数；Jlength、Jrisk和Jsmooth分别是路径的距离成本、风险成本和光滑度成本。

Jlength代表路径的距离成本，用于测量从起始点到当前节点i的长度，d(Cj，Cj+1)表示两节点间的距离，则：

Jrisk代表路径的风险成本，用于近似计算路径规避危险源的风险总代价。路径的风险成本主要受路径长度和路径所处的环境状况影响，用Fj代表第j段路径的风险成本，仅考虑一段路径的1/6、1/2和5/6这3个特定位置[18]，则：

参照雷达计算公式[19]，对障碍物的检测概率(p)进行计算：

式中，c1和c2是与雷达杀伤力和模型有关的常数；σ为雷达扫射的实际面积；R为农业移动机器人到障碍物之间的实际距离。

Jsmooth代表路径的光滑度成本，用于计算路径所有节点转向角之和。一般移动机器人因物理条件限制，通常需要避免极速大转弯的情况，为两相邻有向路径段的夹角之和，则：

2.2.2 预估代价函数 路径的预估代价值要小于路径的实际成本。仅考虑从当前节点i到目标点D的已存在的静态障碍物和路径长度成本，利用算法规划带有引导场的可行性路径Z '，其预估代价函数h(i)可以设计为[20]：

式中，ω1为距离权重系数；N为当前节点m到目标点D之间引导点的总数；G是引导场的中心点；r是引导场的半径；d表示两节点之间的直线距离。结合以上公式，可以求得农业移动机器人到达当前节点i的代价值。

2.3 DGA*算法具体步骤

将起始点到目标点生成的引导点按升序排列，目标点看成引导半径为0的最后1个引导点，使机器人按算法顺序通过各个引导场，探寻高效最优路径。

为保证探寻的路径能够顺序通过引导场，给探寻树的每个节点设置1个引导属性，以便于扩展该节点到指定引导场[20]。图1中，红色箭头模拟规划的最佳路径，设置起始坐标点S的引导数为1，表示S点应扩展至第1个引导场G1。取每步扩展的后续节点中最小代价点作为下一步要扩展的节点，当节点n的引导数为k，探寻继任节点n'时，路径能够通过引导场Gk，则节点n'的引导数为k+1，表明探寻树通过引导场Gk。否则，继任节点n'的引导数仍为k，表明探寻树中的计算路径仍然没有通过引导场Gk。

图1 利用引导场进行节点扩展的示意图Fig. 1 Diagram of node expansion with guide fields

算法具体流程：

1) 载入当前可观测环境，根据环境信息确定引导场生成位置；

2) 设置起始点的引导号码为1，将其置于open表中；

3) 利用公式(4)～(6)将生成的起始点的各个后续节点放入open表中，公式(8)～(15)计算生成的节点的代价值；

4) 从open表中移除最小成本节点n，将其置于close表中；

5) 生成节点n的所有后续节点；

6) 节点n的引导号码为k，若与它的后续节点的连线段能通过Gk的引导场中，则设置它的后续节点的引导号码为k+1，否则它的后续节点的引导号码仍为k；

7) 计算通过引导场的各个后续节点n'的代价值：

若节点n'不在open表和close表中，将它置于open表中；

若节点n'已在open表或者close表中，并且它的新扩展方向与原来的扩展方向不同，将它置于open表中；

若节点n'已在open表或者close表中，并且它的新扩展方向与原来的扩展方向相同，将新的代价值f(n')与原来的f(n')相比较。若新的代价值f(n')较小，则节点n'的父辈节点为节点n，并改变它的总成本为新的f(n')。若节点n'已在close表中，将它移回open表中；

8) 重复步骤4)～7)，直至从open表中提取的最小成本节点为目标节点，通过追溯搜索树生成最终路径。

3 基于云模型的引导场的确定

3.1 云模型推理知识规则库

云模型[14]利用云发生器算法，研究定性定量转换的认知模型。在实际应用中，农业移动机器人周围的环境都是动态的、非结构化的，当突然遇到威胁源，很难提前指定合适的引导点。操作人员通过暂停操作，利用云模型进行人机合作路径规划，将人的认知、经验和喜好加入决策中，为规划路径提供合理的瞬时引导点，引导搜索树改变原始启发式路径，顺利绕过突发威胁源到达下一个引导场，能大大减少许多无用节点的生成，也避免了路径规划进入死循环。

用If-then规则提取人的认知形成云模型规则库，具体形式为:If A1and A2and …An, then B，其中A1, A2, …, An是通过正态云建模的语言变量，n为输入推理参数[21]。

农业移动机器人的规划路径，主要受障碍物的危险程度和人对任务判定的重要性程度的影响。预定义一个安全距离d，确定规划路径与给定障碍物的危险程度之间的关系[22]。d越大表明离障碍物越远，障碍物的危险程度越低，规划路径越短；d越小，规划的路径越长，障碍物危险程度越大。任务的重要性也影响d的大小，一般任务越重要，越要保证以更短的路径更短的时间到达目的地。

云模型推理规则库中的输入参数有：障碍物的致命性程度(DT)和任务的重要性(DM)。其中DT受障碍物的形状、大小、生命特征及运动状态等因素的影响；DM是基于任务需求进行判断。如图2所示，用以描述DT的语言项 “很低” (VL)、“低”(L)、“中等”(M)、“高”(H)、“很高”(VH)转换为 (1, 0.5, 0.06)、(3, 0.5, 0.05)、(5, 0.5,0.05)、(7, 0.5, 0.05)、(9, 0.5, 0.06)的正态云。同理，DM的取值范围也为[0, 10]，语言项为“非常不重要”(VU)、“一般不重要”(MU)、“重要” (I)、“一般重要”(MI)、“非常重要”(VI)这5项。输出参数为安全距离(DB)，语言变量也分为“很近”(VN)、“近”(N)、“中等”(M)、“远”(F)、“很远”(VF)这5个尺度。

特定推理规则可以描述为：“If DT and DM,then DB”。基于已有的经验和知识，形成1个包含If DT1(VH) and DM1(VU), then DB1(VF); If DT1(VH) and DM2(MU), then DB1(VF); If DT1(VH)and DM3(I), then DB2(F)等25个规则的知识库。

图2 描述障碍物危险程度的正态云Fig. 2 Normal clouds for describing obstacle lethality

3.2 引导场的确定方法

利用知识库规则获得安全距离d，同时，利用逆向云发生器可以提供引导半径[23]。图3为引导场确定方法的示意图。引导场的具体位置与尺寸确定后，重新规划的路径只要通过引导场，即可顺利规避障碍物，定量地表明需扩展的节点的不确定性。

图3 引导场的确定方法Fig. 3 Determination method of guide fields

综上， CDGA*算法在DGA*算法的基础上，利用云模型推理知识库将人的经验、专业、知识等有效融入路径规划中，优化了引导场的确定方法，实现了人机协同控制的理念。

4 试验仿真

本文采用Matlab R2012a对DGA*算法和基于云模型的CDGA*算法进行仿真分析。仿真规划区域空间的大小为1 000 m×1 000 m，考虑农业移动机器人的基本尺寸后，确定安全距离d的取值范围为[0.5, 5.0] m 。将机器人看成一个质点，机器人的搜索步长l=10 m，机器人最大转弯角θmax=30°，每个节点能够扩展的最大子节点数M=7，即α=10°。雷达扫射的半径长度为10 m，扫描范围是0°～180°。基于路径长度是影响代价值的首要直接因素，而路径风险及路径光滑度会因路径长度而变化，取权重系数 ω1=0.50，ω2=ω3=0.25。

4.1 人机合作静态路径规划的试验论证

通过试验仿真分析有静态不规则分布障碍物存在的1 000 m×1 000 m规划空间中，DGA*算法与CDGA*算法的路径规划结果如图4所示。确定本次试验仿真，规划起点为(50, 0)，规划目标点为(500,1 000)。从图中可以看出，若按照最短的黑色虚线行走时，会碰到障碍物；而按照人工指定引导场的方式(DGA*)规划出的路径A1行走时，很好地进行了避障规划；同样地，按照人员干预机器人左转以及基于云模型的自动引导场的生成的方式(CDGA*)规划出的路径A2行走时，也实现了避障。

图4 DGA*算法与CDGA*算法静态路径规划的比较Fig. 4 Comparison of static path planning by DGA* and CDGA* algorithms

表1将原始A*算法，DGA*算法和CDGA*算法的路径规划结果进行了对比分析。发现A*算法规划的路径成本最小，是全局最优解，但相比另外2种算法，产生了大量的无用节点，规划时间也过长，严重影响了机器人运行的实时控制。CDGA*算法与DGA*算法进行对比发现，人员规划时间减少了一半，导致总的规划时间也减少了一半，产生的节点数也有减少，能大大提高规划的效率，代价值、路径长度都略高，但差别不大。

表1 静态路径规划中3种算法的性能比较Tab. 1 Performance comparison of three algorithms in static path planning

4.2 人机合作动态路径规划的试验论证

当突然出现动态障碍物时，基于DGA*算法生成的路径A1和基于CDGA*算法生成的路径A2均重新规划，分别产生了基于DGA*算法生成的路径A3和基于CDGA*算法生成的路径A4，成功避开了动态障碍物(图5)。

分析图5发现，基于云模型的CDGA*算法，根据障碍物的大小危险程度等自动产生的引导场符合障碍物越大越危险，引导场越远的规律，符合引导场的确定原则。说明基于云模型的CDGA*算法很好地融合了操作人员的专业知识，能产生出符合实际应用规则的较优解。CDGA*算法在路径动态规划过程中，人员只需要指定转向命令就可以实现路径再规划。而DGA*算法不仅要及时判定机器人的转向，还要快速设定引导场的大小与位置，这往往会导致规划的时间更长，路线成本更高。

图5 DGA*算法与CDGA*算法动态路径规划的比较Fig. 5 Comparison of dynamic path planning by DGA*and CDGA* algorithms

对DGA*算法和CDGA*算法在动态环境中实现路径再规划的性能进行比较(表2)。当突然出现2处动态障碍物时，DGA*算法规划的A3路径的人员规划时间增加到12.5 s，比原来的A1路径耗费的8.8 s多出3.7 s；而CDGA*算法规划的A4路径的人员规划时间变为5.8 s，比A2路径的4.0 s仅仅多了1.8 s，是DGA*算法的一半。CDGA*算法总的规划时间也比DGA*算法快了8.7 s。显然，随着路径再规划过程中，障碍物的数量越多，CDGA*算法的规划时间越优于DGA*，能大大提高规划的效率。DGA*算法的路径成本和光滑度略好于CDGA*算法，但区别不大。考虑到农业环境的复杂动态性，CDGA*算法明显优于DGA*算法。

表2 动态路径规划中DGA*与CDGA*算法的性能比较Tab. 2 Performance comparisons of DGA* and CDGA*algorithms in dynamic path planning

5 结论

本文以农业移动机器人为研究对象，通过将云模型的在线不确定性推理方法与人机协同路径规划方法DGA*算法进行结合，实现了机器人的快速避障。提出的CDGA*算法规划的路径虽然不是全局最优解，路径的光滑度成本也略高，但产生的路径节点数大大减少，规划时间也大大降低，使得机器人自主路径规划的效率更高，实时性更好。对比A*算法、DGA*算法和 CDGA*算法发现，CDGA*算法对于静态、以及突发动态障碍物的避障也都有着较好的工作性能，能满足机器人的复杂农业环境作业要求。

[1]NOGUCHI N, TERAO H. Path planning of an agricultural mobile robot by neural network and genetic algorithm[J]. Comput Electron Agr, 1997, 18(2/3): 187-204.

[2]马建光, 方敦原. 一种基于概率方法的车型机器人路径规划方法[J]. 计算机工程与应用, 2003, 39(34): 93-95.

[3]孙凤池, 黄亚楼, 康叶伟, 等. 车型移动机器人SPRM路径规划[J]. 机器人, 2005, 27(4): 325-329.

[4]赵百轶, 张立军, 贾鹤鸣. 基于四叉树和改进蚁群算法的全局路径规划[J]. 应用科技, 2011, 38(10): 23-28.

[5]史恩秀, 陈敏敏, 李俊, 等. 基于蚁群算法的移动机器人全局路径规划方法研究[J]. 农业机械学报, 2014, 45(6): 53-57.

[6]李擎, 张超, 韩彩卫, 等. 动态环境下基于模糊逻辑算法的移动机器人路径规划[J]. 中南大学学报(自然科学版), 2013, 44: 104-108.

[7]孟蕊, 苏维均, 连晓峰. 基于动态模糊人工势场法的移动机器人路径规划[J]. 计算机工程与设计, 2010, 31(7): 1558-1561.

[8]王殿君. 基于改进A*算法的室内移动机器人路径规划[J]. 清华大学学报(自然科学版), 2012, 52(8): 1085-1089.

[9]DONG Z, CHEN Z J, ZHOU R, et al. A hybrid approach of virtual force and A*search algorithm for UAV path replanning[J]. Industrial Electronics amp; Applications, 2011,49(20): 1140-1145.

[10]HSU W Y. Brain-computer interface: The next frontier of telemedicine in human-computer interaction[J]. Telemat Inform, 2015, 32(1): 180-192.

[11]WINCK C R, ELTON M, BOOK J W. A practical interface for coordinated position control of an excavator arm[J]. Automat Constr, 2015, 51: 46-58.

[12]ZHONG H, WACHS J P, NOF S Y. Telerobot-enabled HUB-CI model for collaborative lifecycle management of design and prototyping[J]. Comput Ind, 2014, 65(4):550-562.

[13]SPARC. Farming with robots[EB/OL]. [2016-05-04]. http://robohub.org/farming-with-robots/.

[14]苗夺谦. 不确定性与粒计算[M]. 北京: 科学出版社,2011:1-6.

[15]谭雁英, 胡淼, 祝小平, 等. 基于人机合作策略下SAS算法的多无人及路径再规划[J]. 西北工业大学学报,2014, 32(5): 688-692.

[16]马飞, 杨皞屾, 顾青,等. 基于改进A*算法的地下无人铲运机导航路径规划[J]. 农业机械学报, 2015, 47(10):303-309.

[17]ZHENG C W, XU F J, HU X H, et al. Online route planner for unmanned air vehicle navigation in unknown battlefield environment[C]//IMACS multiconference on computational engineering in systems applications, Oct 4-6, 2006, Beijing. New York: IEEE, 2006, 1:814-818.

[18]DUAN H B, YU Y X, ZHANG X Y, et al. Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm[J]. Simul Model Pract Th, 2010,18(8): 1104-1115.

[19]BESADA-PORTAS E, DE LA TORRE L, DE LA CRUZ J M, et al. Evolutionary trajectory planner for multiple UAVs in realistic scenarios[J]. IEEE T Robot, 2010,26(4): 619-634.

[20]DECHTER R, PEARL J. Generalized best-first search strategies and the optimality of A*[J]. J Acm, 1985,32(3): 505-536.

[21]SUN X, CAI C, SHEN X. A new cloud model based human-machine cooperative path planning method[J]. J Intell Robot Syst, 2015, 79(1): 3-19.

[22]MARLER R T, ARORA J S. The weighted sum method for multi-objective optimization: New insights[J]. Struct Multidiscip O, 2010(41): 853-862.

[23]BOSKOVIC J, KNOEBEL N, MOSHTAGH N, et al.Collaborative mission planning amp; autonomous control technology (CoMPACT) system employing swarms of UAVs[C]//AIAA guidance, navigation, and control conference, August 10-13, 2009, Chicago, Illinois. Reston:AIAA. doi.org/10.2514/6.2009-5653.

Human-machine cooperative path planning of an agricultural mobile robot based on a cloud model

ZHANG Xinxin, XUE Jinlin
(College of Engineering, Nanjing Agricultural University, Nanjing 210031, China)

【Objective】To make an agricultural robot accurately find a path without collision in complex and dynamic environment in real time.【Method】Using online uncertainty reasoning based on a cloud model, a dynamic guidance A*algorithm based on the cloud model (CDGA*) was proposed to realize human-machine cooperative path planning. Human’s expertise and preferences were incorporated into the DGA*optimization process to implement a faster path planning. Matlab software was used to simulate and analyze the CDGA*and DGA*algorithms.【Result】In static path planning, the numbers of close points of the DGA*and CDGA*algorithms were 158 and 96, human planning time was 8.8 and 4.0 s, the total planning time was 15.6 and 8.9 s,respectively. In dynamic path planning, human planning time of the DGA*and CDGA*algorithms was 12.5 and 5.8 s, the total planning time was 23.3 and 14.6 s, respectively.【Conclusion】The proposed CDGA*algorithm can largely decrease the number of nodes, reduce computation time and improve planning efficiency.

agricultural mobile robot; human-machine cooperation; cloud model; DGA*algorithm; CDGA*algorithm; path planning

TP242

A

1001-411X(2017)06-0105-07

张欣欣, 薛金林. 基于云模型的农业移动机器人人机合作路径规划[J]. 华南农业大学学报, 2017, 38(6): 105-111.

2017-01-03 优先出版时间：2017-11-06

优先出版网址：http://kns.cnki.net/kcms/detail/44.1110.S.20171106.1412.030.html

张欣欣 (1991—)，女，硕士研究生，E-mail: zxx_njau@163.com； 通信作者： 薛金林 (1974—)，男，教授，博士，E-mail:xuejinlin@njau.edu.cn

江苏省科技计划项目(SBK2015022003)

【责任编辑 庄 延】