基于云计算之温室移动机器人的路径规划
王伟+褚凌慧+李超艺+李昕达
摘 要： 以高新技术解决温室作业问题，将一种基于云计算的温室移动机器人路径规划应用于农间巡视任务，而行走路径的选择则选用改进蚁群算法来进行完成。首先，该云端运算利用网络使电脑与移动机器人彼此合作，由伺服器端收集温室环境相关数据信息；再通过云中的存储与计算资源，结合优化后的蚁群算法计算出机器人的行走路径；最终发送至移动机器人完成温室环境的路径规划。实验结果表明，通过利用云计算后台资源使该算法在信息素更新路径变更的情况下能够找到最短的路径数据，同时对路径的各项性能都有所提高，其中包括折弯次数、跳数、路径长度等。从而满足了移动机器人在温室环境下完成可避障的最优路径选择任务。
关键词： 云端运算； 移动机器人； 蚁群算法； 路径规划
中图分类号： TN911?34； TP39 文献标识码： A 文章编号： 1004?373X（2017）04?0053?04
Clould computing based path planning for greenhouse mobile robot
WANG Wei， CHU Linghui， LI Chaoyi， LI Xinda
（Northeast Forestry University， Harbin 150040， China）
Abstract： In order to adopt a high technology to solve the problem of greenhouse operations， cloud computing based path planning for the greenhouse mobile robot is used to implement the path selection for the patrol task in the field by means of the improved ant colony algorithm. Cloud computing is used to realize cooperation between computer and the mobile robot by means of network. A server is employed to collect the related data of the greenhouse environment. In combination with the optimized ant colony algorithm， the walking path of the robot is calculated by means of the cloud storage and computing resources， and transmitted to the mobile robot to complete the path planning of greenhouse environment. The experimental results show that the algorithm can find the shortest path by taking advantage of the clould background resources under the condition of the path change due to pheromone update， the mobile robot can complete the optimal path selection and avoid obstacles in the greenhouse， and the various performance of the path are improved， including the bending times， hop times and path length.
Keywords： cloud computing； mobile robot； ant colony algorithm； path planning
隨着科学技术的日新月异和市场竞争环境的加剧，机器人的应用范围也从军事及医疗逐步向农产业进军，并在其领域内分担着许多工作[1]。对于解决温室农田作物问题，现已出现很多不同性质的农业机器人，如：日本科技人员研制的自行走番茄收获机器人、美国伊利诺伊大学研究的用于田间巡视蚂蚁机器人等。这些机器人虽然有着各自特有的特异功能，但涉及到所选的行走路线会影响工作效率及运作成本的问题时，却使人们产生深省。温室移动机器人要在田间进行检测与作业，必须对农田环境具有全局和局部搜索能力。全方位的巡视任务下至机器人操作系统使之高效地完成全域路径规划。本研究将采用云端计算（Cloud Computing）的概念来指挥机器人在农田间的巡视和路径选择，以满足机器人在温室环境存在障碍物的情况下，通过后台的改进蚁群算法输入来规划一条从起始点到目标点可避障的最短路径。
1 云计算服务
云计算[2]是一种在互联网笼罩下虚拟的计算服务模式。这种模式将客户所需的信息和软硬件资源以共享的方式按需分配给管理设备和计算机。它是一种将多态计算和网络技术发展融合的“新一代的信息服务模式”。“云”可看作是一些巨大的服务器聚集，其自我管理和系统维护的性能为存储服务器，计算服务器提供有序的监管。云计算无需人为参与，是由软件来自行操作管理。因此可支持推动农业在温室环境层面和应对变化层面上的敏捷性，在激烈动态变化的农业中生存和发展。
在本设计中，若温室机器人要完成行走路径问题时，无需该机器人盲目地、无规则地巡航，而是机器人通过将高清摄像头安放在云台上使之360°无死角地获取温室环境及植被照片，再将其上传到服务器端，检索出环境信息的相关图片，由云数据库中强大的计算功能来算出机器人避开障碍物的行走路径，在利用数据库庞大的存储功能将信息保存在共享数据库中，以便机器人循环检索，减少开发人员的日后开发时间，如图1所示。
2 温室环境及建模
云可看作是一个规模庞大无比的资源池，池中有操控机器人在温室环境下作业的不同池层，如存储层、计算层、共享层等物理资源，它作为后台服务的主要方式，首先，纵观温室地形及植被分部情况；其次，通过联网数据处理得知温室环境构造来判断行走路径。
2.1 栅格模拟环境模型
栅格法是将实体三维环境空间虚拟化为二维独立栅格空间[3]，如图2所示。
栅格单元的大小决定了反馈给后台地理数据的精度。一般将含有植被的领域归为障碍区，传感器则会将感测到障碍区域位置报告给后台服务器端，并命这些栅格为禁止栅格，用黑色栅格表示（其中边界区域可看为障碍区域）；没有植被的领域则归为自由区域，可以自由通行，用白色栅格表示，如图3所示。图3中，S为机器人出发的起始位置；T为所要到达的目的地。温室移动机器人需在环境空间内完成从S到T的无碰最优路径。设该二维空间由u行v列组成，障碍物所在的位置可用一个二维数组矩阵map（u，v）表示，如下：
（1）
栅格化之后的移动机器人工作环境是将每个单元格视为一个质点，机器人可沿其所在位置临界的8个单元格移动，如图4所示。机器人所经路径穿过的单元格视为路径节点，所以栅格的大小会影响最优路径的精确值。为了使机器人每次的运动方向都更加接近寻优路径直至到达目标点，而不是背道而驰，即路线迂回。预先以禁忌表的方式对蚂蚁选择下一节点的概率进行限制，即除去经过节点和迂回节点。假设在第i条路径中搜索当前节点为u，在数据库中可快速地找到所需节点资源。令u的下一个可行节点集合为V，那么v为V中的任意节点。所以一个链路节点可以有多种连接方式到达下一链路，在云数据库的流动性、可伸缩性、大范围性等特点下契合运用。
3 路径规划方法
本研究所提出路径规划方法的整个流程是读取摄像头拍摄到的地图信息，至规划导航的阶段时再利用已经训练好的蚁群算法网络。整体的结构是以优化蚁群算法的判断为主，伺服器端将从起点到终点避开障碍物的所有路径完成后会派给机器人，机器人从中选择最近路径，最终依据这个规划好的路径工作即可。
3.1 蚁群优化算法
蚁群算法（Ant Colony Optimization，ACO）结合温室环境而言，是一种用来在农田间中寻求最优路径的概率型算法[4?5]。它是由意大利学者M.Dorigo等人提出的一种基于信息正反馈原理的新型模拟进化算法，其灵感来源于蚁群在寻找食物过程时，通过分泌一种名为信息素的交流觅食信息，从而使群体蚂蚁快速找到目标所在。如图3所示，令蚂蚁的巢窝为S点，食物所在地为T点位置，在S，T点之间存在一些障碍物。从蚂蚁出发觅食一刻就注定不同蚂蚁在各条路径下所留下的信息素浓度各有差异，而随着时间的变化和路径的长短也会使浓度下降的大小产生差异，最终整个蚁群依赖信息素浓度选择出两点的最优路径[6]。
考虑到蚂蚁在释放信息素的同时，会涉及到信息素浓度随时间挥发的问题，不妨令（0<<1）表示信息素消失程度。这样，在t时刻蚂蚁满足一次循环后，将各条连接路径上的信息变量作以下调整：
（2）
（3）
式中：为第只蚂蚁在本次循环中留在路径上的信息素；为在本次循环中路径上的信息素增量。为第只蚂蚁经过路径的总长度，为常数，如下：
（4）
对于式（2）～式（4）而言，可以看出蚁群算法在开始搜索时，由于各路径几率平等、信息素分布均匀，会使该算法在起初具有一定的盲目搜索性，容易陷入局部最优情况。
3.2 改进蚁群算法搜索策略
传统算法在云端服务器中存在大量搜索、计算等问题，为避免陷入局部最优达到全局搜索的目的，本研究将信息素存储在模型离散节点中，每个离散节点都有信息素的值与之对应，将上面信息素的更新分为局部更新和全局更新两部分。局部更新的目的是提高蚂蚁探寻未经途点的概率，以致完成全局搜索的任务。信息素更新公式为：
（5）
式中：为点（，）上所带的信息素值；为信息素的衰减系数。全局更新是指当蚂蚁完成一条路径的搜索时，以该路径的长度作为评价值，从数据库系统中通过计算、存储选择路径集合中最短路径，来增加最短路径上各个节点的信息数值。信息素更新公式为：
（6）
在信息素更新公式的基础上，对信息素衰减系数采用自适应调节策略。通过改变的值来提高算法的全局性。
4 云计算调用算法路径仿真
将“云”作为虚拟的管理服務模式，来掌控整个温室环境和机器人的运作，潜在的模式里面包括了由若干节点和数据信息组成的云数据库，来提供计算和调用。本研究结合云端计算是将多种互联的应用、位置坐标、蚁群算法优化数值等资源信息有效的结合起来实现不同层次阶梯的虚拟化，仅需连接上网络即可快速地从中找到实验所需资源，即从起点S到终点T的一条无障碍最优路线。将仿真结果进行对比显示，如图5、图6所示。
由局部最优和全局最优路径的信息素更新代替之前机器人所经路径的全部更新，这不但减少了局部最优的概率、增加了反馈效果，从图5、图6可看出机器人在障碍环境下的跳数与转折次数也随之减少；同时根据目标点适当的调整基本启发函数，通过图7、图8可看出此改进方法对算法的收敛速度也有一定的提高，与标准蚁群算法相比，优化后的算法收敛的代数在17代左右，此后最短距离将不再发生变化，这并不是该算法收敛过早，而是在最初将信息素传送至服务器端时，就提供了相对可靠的数据使得前期搜索加快。
综合图7、图8，本文对标准蚁群算法和改进蚁群算法进行了比较，两种算法的最优性能见表1。
仿真结果与数据证明了云数据库调用改进蚁群算法的有效性，快速地解决了移动机器人在温室中的路径规划问题。
5 结 论
就一种基于云计算的温室移动机器人路径规划而言，主要通过伺服器端的资料运算处理，运用改进后的蚁群算法调用最优行走路径，最终将演算好的数据传送到温室移动机器人。通过对信息素更新的改进及启发函数的调整，使蚂蚁前期搜索时间缩短，改善了行走路径的质量。将云计算技术与蚁群算法结合起来，优化了搜索性能，提高机器人在温室环境下的工作效率，为农田业的发展提供了新思路。
参考文献
[1] 徐扬生，阎镜予.机器人技术的新发展[J].集成技术，2012（1）：1?5.
[2] 张建勋，谷志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429?433.
[3] 鲁庆.基于栅格法的移动机器人路径规划研究[J].电脑与信息技术，2007，15（6）：24?27.
[4] DORIGO M， STUTZLE T. Ant colony optimization [M]. Cambrige： MIT Press， 2009： 29?41.
[5] 史恒亮，唐振民，刘传领，等.基于蚁群优化算法的云数据库动态路径规划[J].计算機科学，2010，37（5）：143?147.
[6] Wang J，Cho J，Lee S， et al. Real Time Services for Future Cloud Computing Enabled Vehicle Networks[C].Wireless Communications and Signal Processing.Nanjing，2011：1?5.
[7] 文明波，丁治明.适用于云计算的面向查询数据库数据分布策略[J].计算机科学，2010，37（9）：168?172.
[8] 李磊，叶涛，谭民.移动机器人技术研究现状与未来[J].机器人，2002，24（5）：475?480.
[9] 邓高峰，张学萍，刘彦萍.一种障碍物环境下机器人路径规划的蚁群粒子群算法[J].控制理论与应用，2009，26（8）：879?883.
[10] BI Xiaojun， LUO Guangxin. The improvement of ant colony algorithm based on the inver?over operator [C]// Proceedings of IEEE International Conference on Mechatronics and Automation. Harbin： IEEE Press， 2007： 2383?2387.
[11] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562?2567.
摘 要： 以高新技术解决温室作业问题，将一种基于云计算的温室移动机器人路径规划应用于农间巡视任务，而行走路径的选择则选用改进蚁群算法来进行完成。首先，该云端运算利用网络使电脑与移动机器人彼此合作，由伺服器端收集温室环境相关数据信息；再通过云中的存储与计算资源，结合优化后的蚁群算法计算出机器人的行走路径；最终发送至移动机器人完成温室环境的路径规划。实验结果表明，通过利用云计算后台资源使该算法在信息素更新路径变更的情况下能够找到最短的路径数据，同时对路径的各项性能都有所提高，其中包括折弯次数、跳数、路径长度等。从而满足了移动机器人在温室环境下完成可避障的最优路径选择任务。
关键词： 云端运算； 移动机器人； 蚁群算法； 路径规划
中图分类号： TN911?34； TP39 文献标识码： A 文章编号： 1004?373X（2017）04?0053?04
Clould computing based path planning for greenhouse mobile robot
WANG Wei， CHU Linghui， LI Chaoyi， LI Xinda
（Northeast Forestry University， Harbin 150040， China）
Abstract： In order to adopt a high technology to solve the problem of greenhouse operations， cloud computing based path planning for the greenhouse mobile robot is used to implement the path selection for the patrol task in the field by means of the improved ant colony algorithm. Cloud computing is used to realize cooperation between computer and the mobile robot by means of network. A server is employed to collect the related data of the greenhouse environment. In combination with the optimized ant colony algorithm， the walking path of the robot is calculated by means of the cloud storage and computing resources， and transmitted to the mobile robot to complete the path planning of greenhouse environment. The experimental results show that the algorithm can find the shortest path by taking advantage of the clould background resources under the condition of the path change due to pheromone update， the mobile robot can complete the optimal path selection and avoid obstacles in the greenhouse， and the various performance of the path are improved， including the bending times， hop times and path length.
Keywords： cloud computing； mobile robot； ant colony algorithm； path planning
隨着科学技术的日新月异和市场竞争环境的加剧，机器人的应用范围也从军事及医疗逐步向农产业进军，并在其领域内分担着许多工作[1]。对于解决温室农田作物问题，现已出现很多不同性质的农业机器人，如：日本科技人员研制的自行走番茄收获机器人、美国伊利诺伊大学研究的用于田间巡视蚂蚁机器人等。这些机器人虽然有着各自特有的特异功能，但涉及到所选的行走路线会影响工作效率及运作成本的问题时，却使人们产生深省。温室移动机器人要在田间进行检测与作业，必须对农田环境具有全局和局部搜索能力。全方位的巡视任务下至机器人操作系统使之高效地完成全域路径规划。本研究将采用云端计算（Cloud Computing）的概念来指挥机器人在农田间的巡视和路径选择，以满足机器人在温室环境存在障碍物的情况下，通过后台的改进蚁群算法输入来规划一条从起始点到目标点可避障的最短路径。
1 云计算服务
云计算[2]是一种在互联网笼罩下虚拟的计算服务模式。这种模式将客户所需的信息和软硬件资源以共享的方式按需分配给管理设备和计算机。它是一种将多态计算和网络技术发展融合的“新一代的信息服务模式”。“云”可看作是一些巨大的服务器聚集，其自我管理和系统维护的性能为存储服务器，计算服务器提供有序的监管。云计算无需人为参与，是由软件来自行操作管理。因此可支持推动农业在温室环境层面和应对变化层面上的敏捷性，在激烈动态变化的农业中生存和发展。
在本设计中，若温室机器人要完成行走路径问题时，无需该机器人盲目地、无规则地巡航，而是机器人通过将高清摄像头安放在云台上使之360°无死角地获取温室环境及植被照片，再将其上传到服务器端，检索出环境信息的相关图片，由云数据库中强大的计算功能来算出机器人避开障碍物的行走路径，在利用数据库庞大的存储功能将信息保存在共享数据库中，以便机器人循环检索，减少开发人员的日后开发时间，如图1所示。
2 温室环境及建模
云可看作是一个规模庞大无比的资源池，池中有操控机器人在温室环境下作业的不同池层，如存储层、计算层、共享层等物理资源，它作为后台服务的主要方式，首先，纵观温室地形及植被分部情况；其次，通过联网数据处理得知温室环境构造来判断行走路径。
2.1 栅格模拟环境模型
栅格法是将实体三维环境空间虚拟化为二维独立栅格空间[3]，如图2所示。
栅格单元的大小决定了反馈给后台地理数据的精度。一般将含有植被的领域归为障碍区，传感器则会将感测到障碍区域位置报告给后台服务器端，并命这些栅格为禁止栅格，用黑色栅格表示（其中边界区域可看为障碍区域）；没有植被的领域则归为自由区域，可以自由通行，用白色栅格表示，如图3所示。图3中，S为机器人出发的起始位置；T为所要到达的目的地。温室移动机器人需在环境空间内完成从S到T的无碰最优路径。设该二维空间由u行v列组成，障碍物所在的位置可用一个二维数组矩阵map（u，v）表示，如下：
（1）
栅格化之后的移动机器人工作环境是将每个单元格视为一个质点，机器人可沿其所在位置临界的8个单元格移动，如图4所示。机器人所经路径穿过的单元格视为路径节点，所以栅格的大小会影响最优路径的精确值。为了使机器人每次的运动方向都更加接近寻优路径直至到达目标点，而不是背道而驰，即路线迂回。预先以禁忌表的方式对蚂蚁选择下一节点的概率进行限制，即除去经过节点和迂回节点。假设在第i条路径中搜索当前节点为u，在数据库中可快速地找到所需节点资源。令u的下一个可行节点集合为V，那么v为V中的任意节点。所以一个链路节点可以有多种连接方式到达下一链路，在云数据库的流动性、可伸缩性、大范围性等特点下契合运用。
3 路径规划方法
本研究所提出路径规划方法的整个流程是读取摄像头拍摄到的地图信息，至规划导航的阶段时再利用已经训练好的蚁群算法网络。整体的结构是以优化蚁群算法的判断为主，伺服器端将从起点到终点避开障碍物的所有路径完成后会派给机器人，机器人从中选择最近路径，最终依据这个规划好的路径工作即可。
3.1 蚁群优化算法
蚁群算法（Ant Colony Optimization，ACO）结合温室环境而言，是一种用来在农田间中寻求最优路径的概率型算法[4?5]。它是由意大利学者M.Dorigo等人提出的一种基于信息正反馈原理的新型模拟进化算法，其灵感来源于蚁群在寻找食物过程时，通过分泌一种名为信息素的交流觅食信息，从而使群体蚂蚁快速找到目标所在。如图3所示，令蚂蚁的巢窝为S点，食物所在地为T点位置，在S，T点之间存在一些障碍物。从蚂蚁出发觅食一刻就注定不同蚂蚁在各条路径下所留下的信息素浓度各有差异，而随着时间的变化和路径的长短也会使浓度下降的大小产生差异，最终整个蚁群依赖信息素浓度选择出两点的最优路径[6]。
考虑到蚂蚁在释放信息素的同时，会涉及到信息素浓度随时间挥发的问题，不妨令（0<<1）表示信息素消失程度。这样，在t时刻蚂蚁满足一次循环后，将各条连接路径上的信息变量作以下调整：
（2）
（3）
式中：为第只蚂蚁在本次循环中留在路径上的信息素；为在本次循环中路径上的信息素增量。为第只蚂蚁经过路径的总长度，为常数，如下：
（4）
对于式（2）～式（4）而言，可以看出蚁群算法在开始搜索时，由于各路径几率平等、信息素分布均匀，会使该算法在起初具有一定的盲目搜索性，容易陷入局部最优情况。
3.2 改进蚁群算法搜索策略
传统算法在云端服务器中存在大量搜索、计算等问题，为避免陷入局部最优达到全局搜索的目的，本研究将信息素存储在模型离散节点中，每个离散节点都有信息素的值与之对应，将上面信息素的更新分为局部更新和全局更新两部分。局部更新的目的是提高蚂蚁探寻未经途点的概率，以致完成全局搜索的任务。信息素更新公式为：
（5）
式中：为点（，）上所带的信息素值；为信息素的衰减系数。全局更新是指当蚂蚁完成一条路径的搜索时，以该路径的长度作为评价值，从数据库系统中通过计算、存储选择路径集合中最短路径，来增加最短路径上各个节点的信息数值。信息素更新公式为：
（6）
在信息素更新公式的基础上，对信息素衰减系数采用自适应调节策略。通过改变的值来提高算法的全局性。
4 云计算调用算法路径仿真
将“云”作为虚拟的管理服務模式，来掌控整个温室环境和机器人的运作，潜在的模式里面包括了由若干节点和数据信息组成的云数据库，来提供计算和调用。本研究结合云端计算是将多种互联的应用、位置坐标、蚁群算法优化数值等资源信息有效的结合起来实现不同层次阶梯的虚拟化，仅需连接上网络即可快速地从中找到实验所需资源，即从起点S到终点T的一条无障碍最优路线。将仿真结果进行对比显示，如图5、图6所示。
由局部最优和全局最优路径的信息素更新代替之前机器人所经路径的全部更新，这不但减少了局部最优的概率、增加了反馈效果，从图5、图6可看出机器人在障碍环境下的跳数与转折次数也随之减少；同时根据目标点适当的调整基本启发函数，通过图7、图8可看出此改进方法对算法的收敛速度也有一定的提高，与标准蚁群算法相比，优化后的算法收敛的代数在17代左右，此后最短距离将不再发生变化，这并不是该算法收敛过早，而是在最初将信息素传送至服务器端时，就提供了相对可靠的数据使得前期搜索加快。
综合图7、图8，本文对标准蚁群算法和改进蚁群算法进行了比较，两种算法的最优性能见表1。
仿真结果与数据证明了云数据库调用改进蚁群算法的有效性，快速地解决了移动机器人在温室中的路径规划问题。
5 结 论
就一种基于云计算的温室移动机器人路径规划而言，主要通过伺服器端的资料运算处理，运用改进后的蚁群算法调用最优行走路径，最终将演算好的数据传送到温室移动机器人。通过对信息素更新的改进及启发函数的调整，使蚂蚁前期搜索时间缩短，改善了行走路径的质量。将云计算技术与蚁群算法结合起来，优化了搜索性能，提高机器人在温室环境下的工作效率，为农田业的发展提供了新思路。
参考文献
[1] 徐扬生，阎镜予.机器人技术的新发展[J].集成技术，2012（1）：1?5.
[2] 张建勋，谷志民，郑超.云计算研究进展综述[J].计算机应用研究，2010，27（2）：429?433.
[3] 鲁庆.基于栅格法的移动机器人路径规划研究[J].电脑与信息技术，2007，15（6）：24?27.
[4] DORIGO M， STUTZLE T. Ant colony optimization [M]. Cambrige： MIT Press， 2009： 29?41.
[5] 史恒亮，唐振民，刘传领，等.基于蚁群优化算法的云数据库动态路径规划[J].计算機科学，2010，37（5）：143?147.
[6] Wang J，Cho J，Lee S， et al. Real Time Services for Future Cloud Computing Enabled Vehicle Networks[C].Wireless Communications and Signal Processing.Nanjing，2011：1?5.
[7] 文明波，丁治明.适用于云计算的面向查询数据库数据分布策略[J].计算机科学，2010，37（9）：168?172.
[8] 李磊，叶涛，谭民.移动机器人技术研究现状与未来[J].机器人，2002，24（5）：475?480.
[9] 邓高峰，张学萍，刘彦萍.一种障碍物环境下机器人路径规划的蚁群粒子群算法[J].控制理论与应用，2009，26（8）：879?883.
[10] BI Xiaojun， LUO Guangxin. The improvement of ant colony algorithm based on the inver?over operator [C]// Proceedings of IEEE International Conference on Mechatronics and Automation. Harbin： IEEE Press， 2007： 2383?2387.
[11] 陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562?2567.
