列车用送餐机器人路径规划研究及软件设计

2019-10-18严文娟费树岷

软件导刊 2019年9期

严文娟费树岷

摘要：研究列车环境下送餐机器人路径规划与软件控制方案，为更好地满足实际需求，提出一种改进的蚁群算法，以加快收敛速度、缩短路径长度及减少转弯次数。实验中根据当前环境构建栅格图，通过编写的路径规划程序计算起始位置到目标位置的路径，完成当前环境下的路径规划。上位机软件平台采用C#语言编写，主要包括运动控制、订单管理、通讯传输等功能。实验结果表明，与基本蚁群算法相比，改进蚁群算法具有更好的规划效果，上位机软件平台与下位机可以实现有效的数据交换，并实现对送餐机器人的运动控制及系统管理等功能。

关键词：送餐机器人;路径规划;C#;蚁群算法

DOI：10. 11907/rjdk. 182848 开放科学（资源服务）标识码（OSID）：

中图分类号：TP302文献标识码：A 文章编号：1672-7800（2019）009-0026-04

Path Planning and Software Design Based on Dining Robot on Trains

YAN Wen-juan，FEI Shu-min

（Automated Institute，Southeast University，Nanjing 210096，China）

Abstract：In this paper， the path planning and software control scheme of the dining robot in the train environment are studied. To meet the actual demand， an improved ant colony algorithm is proposed， which makes the algorithm improve the convergence speed， path length and turning times. In the experiment， the raster map is constructed according to the current environment， and the path planning program calculates the path of the starting position and the target position， and completes the path planning in the current environment. The PC software platform is written in C# language， which mainly includes motion control， order management， communication transmission and other functions. The experimental results show that compared with the basic ant colony algorithm， the improved ant colony algorithm has better planning effect， the upper computer software platform and the lower computer can realize effective data exchange， and the functions of control and management of the dining robot.

Key Words：dining robot; path planning; C#; ant colony algorithm

0 引言

送餐机器人作为一种服务型机器人，可为用户提供更高效、便捷的服务[1]，因此越来越多的研究人员针对送餐机器人进行研究。国内外卖公司饿了么联合万科推出送餐机器人“万小饿”，主要应用场景为住宅、办公、商业等场所[2]，送餐人员进入建筑物后将食物放入送餐机器人，然后由送餐机器人将食物送至用户指定位置;上海交通大学研发了一款在餐厅使用的送餐机器人，顾客到店后可以使用送餐机器人订餐，机器人会自动完成送餐与取餐等工作[3];澳洲外卖披萨连锁店达美乐（Domino）联合澳洲Marathon Robotics公司研发出世界上第一个快递机器人DRU（Domino's Robotic Unit），作为一个可以独立送餐的机器人，其使用GPS（全球定位系统）导航，并配置激光避障设备，能够胜任在城市街道上的送餐任务[4];英国外卖订购网站Just Eat曾推出一款送餐机器人[5]，操作人员可通过智能手机APP控制机器人到达指定地点，用户通过订餐APP解锁机器人获取外卖。如今送餐机器人在各种场合出现得越来越频繁，为人们生活带来了便利。本文创新点在于通过改进路径规划算法，将送餐机器人运用于列车环境中，并设计上位机软件系统，以方便管理员对送餐机器人进行管理。目前列车上通常是由列车员手动推送餐车进行送餐服务，本文提出的送餐机器人旨在改变当前的送餐方式，将工作人员从繁琐的送餐工作中解放出来，并为乘客带来更好的乘车体验。乘客可通過手机APP与机器人操作面板完成订餐，下单完成并确认后，送餐机器人可将食物送至指定位置。因此，送餐机器人行驶路线的合理性是确保高质量完成送餐任务的前提。

路径规划研究分为两部分：环境信息获取与算法实现[6]。列车环境参数主要参考和谐号动车组，每节车厢长约25m，主要分为8节和16节两种车型。机器人相关路径算法种类较多，主要包括Floyed算法、动态路径规划方法和蚁群算法等。Floyed算法实现过程简单，但若两点互为对方连接距离矩阵中的最小点，则可能出现死锁现象，无法跳出局部最优[7];动态路径规划方法的最优解需要基于每个子问题的最优解[8]，以此获取最优策略，其本质上采用的是迭代思想，所以当划分情况增多、计算压力太大则无法得出最优解;蚁群算法通过模拟蚁群觅食过程中信息素的变化，通过正反馈调控得出最佳觅食路径。该算法易于与其它算法相结合进行优化，每次模拟得出的最优路径不易陷入最优陷阱，所以该算法可以结合其它算法进行性能优化与功能扩展，例如加快收敛速度、实现动态避障功能等[9]。

利用C#语言优秀的封装特性，自定义算法实现过程中所需的数据体成员和成员函数，并将环境地图建模转换成计算机可以理解的结构体，在此基础上寻找最优路径。

1 路径规划

1.1 基于栅格法的环境地图建模

环境地图建模方式主要有栅格法、可视图法与拓扑法，其中栅格法是首先将机器人所处环境划分为相同尺寸的网格[10-11]，其次按照物理空间标志出障碍物格子。如图1所示，白色格子可以通行，黑色格子不能通行。特殊情况为：本文规定如果在机器人路径选择时发生了斜穿，则需要判断当前位置到斜穿点两边是否是障碍栅格，如果是，该段路径则是非法的。

1.2 蚁群算法思想

蚁群算法是由意大利学者DORIGO M等[12]于1991年根据蚂蚁觅食特点首次提出的一种仿生算法，蚂蚁在觅食时会在经过的路径上留下一种随时间推移不断减少的信息素，后来的蚂蚁可以接收到这种信息素，并根据信息素浓度选择路径，在迭代一段时间后算法收敛于最短路径。

单只蚂蚁行为需要依靠环境进行选择，蚂蚁个体的路径转移概率[pkij（t）]计算公式为[13]：

1.3 蚁群算法参数设置

公式（1）-（3）中出现的参数[14]对最优解与收敛速度影响很大。信息启发因子[α]与收敛速度呈正相关关系，且[α]越大时，蚂蚁在选择路径时则越容易选择之前的路径;期望启发式因子[β]越小，将导致蚂蚁陷入随机搜索，越不容易找到最优解;信息素挥发因子[ρ]与收敛速度呈正相关关系，与全局搜索能力呈负相关关系。

在仿真实验中，采用20*20的栅格地图，参数默认值为：m=20，[α]=1，[β]=3，[ρ]=0.3。测试[α]、[β]、[ρ]对路径长度的影响，每组进行10次仿真实验，[α]取值为{0.1，0.5，1，1.5，2，2.5，3，3.5，4，4.5，5，5.5，6，6.5，7，7.5，8}，[β]取值为{0.1，0.5，1，1.5，2，2.5，3，3.5，4，4.5，5，5.5，6，6.5，7，7.5，8}，[ρ]取值为{0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8}。对每组进行10次模拟实验，并对结果取平均，各参数与平均路径长度之间的关系通过仿真实验得出结论。实验结果表明，当[α∈1，3.5]，[β∈1，3]，[ρ∈0.5，0.8]时，蚁群算法效果较好。

由于蚁群算法中各参数之间存在关联性，通常根据实际情况，按照实验结果选取合适的参数组合。通过仿真实验，本文将参数设置为：[α]=1，[β]=2，[ρ]=0.5。

2 改进蚁群算法

2.1 能见度信息调整

能见度[η]反映了在路径搜索过程中对路径选择的影响，一般将能见度[η]设置为[1Dij]或[1Dig]，其中[1Dij]表示相邻节点距离，[1Dig]表示当前节点到目标节点之间距离。当[η]设置为[1Dij]或[1Dig]时，其对路径选择有不同倾向，分别表现为收敛路径倾向于直线和斜线。为了防止因收敛路径倾向的影响，在某些环境地图中使算法效果变差，将能见度[η]设置为[1Dij*Dig]时可以平衡其对算法的影响。

2.2 蚂蚁“夭折”策略改进

在基本蚁群算法中，当一组蚂蚁在某个栅格点上计算下个路径转移的栅格点时，发现此时无路可走，尤其在U型栅格图中容易出现该情况，基本蚁群算法则按照“夭折”策略，将该组蚂蚁设置为死亡状态，该组蚂蚁信息素也将停止更新，并将该组蚂蚁所在栅格点加入禁忌表中，以防其它组蚂蚁进入该栅格点[15]。该策略解决了算法停滞问题，但需要强行将蚂蚁设置为死亡，减少了蚂蚁群体中继续搜索路径的蚂蚁数量。

为解决该问题，本文针对蚂蚁陷入无后继路径的情况时，将当前栅格点加入禁忌表，返回上一栅格点，重新按照路径转移策略计算新的栅格点，从而使该组蚂蚁能跳出当前栅格点，并继续进行路径搜索，避免了在基本蚁群算法中因蚂蚁死亡导致的路径搜索能力下降。

2.3 直达判断

在实际工作环境中，可通行的区域远远大于不可通行区域。在很多情况下，蚂蚁当前位置与目标栅格之间的直线连接中并没有障碍栅格阻挡，蚂蚁可通过某个方向直达目标栅格。但根据蚁群算法路径转移公式中的转移策略，蚁群算法在运行过程中，蚂蚁无法判断能否从当前栅格直达目标栅格。在图4、图5中，起始点坐标是（0，19），目标点坐标是（9，10），黑色栅格代表有障碍、不可通行的栅格，黑色直线表示蚁群算法计算出的路线。未加入直达判断的蚁群算法中可能会出现图4的情况，在加入直达判断的算法中可以避免该情况出现（见图5）。

2.4 实验结果及分析

根据环境建立栅格地图（见图1），黑色栅格代表有障碍、不可通行，白色栅格代表可通过的栅格，起始点坐标是（0，19），目标坐标是（19，0）。两组实验各进行10次，并对结果取平均值。将基本蚁群算法与改进蚁群算法进行对比，结果如表1所示。

由实验结果可知，相比于基本蚁群算法，改进蚁群算法的平均路径长度和平均转弯次数都得到了明显优化，从而有效提高执行效率，降低送餐机器人行进过程中的误差。

3 上位机软件平台设计

根据送餐机器人的功能需求设计合理、可靠的上位机软件系统，系统采用C#語言编写[16]。上位机软件系统具备路径规划功能和设备管理功能，结合现有定位系统，完成上位机与下位机的通讯，并根据订单需求规划出合理路径，管理员可以通过上位机软件系统随时了解送餐机器人运行情况。

下位机控制器选用英国Trio Motion公司开发的基于微处理技术的高密度数字运动控制器Trio MC4N，MC4N基于最新版532MHz ARM处理器[17-18]，支持MODBUS TCP/IP协议，在多轴设备中应用广泛。C#是一种由微软开发的面向对象编程语言，可运行于微软的.NET Framework平台上[19]。作为由C/C++衍生出来的编程语言，在继承C/C++强大功能的同时，还在其基础上实现了突破，对于大型与小型系统都可以胜任，且在设计程序界面时十分迅速、便利。C#由于具有易学易用的特点，可以在较短时间内帮助程序人员设计出界面友好、功能强大的软件平台。数据库选择SQL Server 2008，其是一个基于C/S模型的关系型数据库，可以有效实现对数据的存储与管理[20]。

3.1 数据库模块

数据库模块设计直接影响上位机软件平台的实现，本文针对自主送餐机器人的上位机进行数据库设计。数据库需要管理用户信息、订单信息、订单完成情况等，并根据管理员需要，导出已完成的订单信息。

3.2 服务器设计

服务器端处理与存储环境信息，根据客户端指令进行路径规划，并能实现与客户端的通信，将路径规划结果传输给客户端。

3.3 客户端设计

客户端通过MODBUS TCP/IP协议实现与下位机的通讯[21-22]，主要功能包括：设备连接、环境初始化、运动控制、订单管理与订单信息导出。客户端根据机器人IP进行设备连接，并确定寄存器起始地址。根据服务器端对环境信息的处理，客户端需要设定环境初始化信息，接收下位机采集的视频信息，并根据路径规划结果对送餐机器人进行运动控制。送餐机器人控制界面如图8所示。

4 结语

本文研究了列车环境下送餐机器人路径规划与软件控制方案，本文设计的送餐机器人路径规划系统采用改进蚁群算法，该算法较传统蚁群算法缩短了路径长度，减少了转弯次数，加快了算法收敛速度。实验结果表明，改进后的路径规划算法性能得到了有效提升，上位机软件系统可辅助管理人员随时了解送餐机器人运行情况，并与其实现有效通讯。由于送餐机器人的工作环境路况比较单一，基于栅格地图的路径规划系统对于环境相对固定的情况较为适用。实际运用过程中会出现多个机器人共同完成任务的情况，另外机器人在运行过程中可能会探测到动态障碍物，未来可对基于蚁群算法的任务调度与动态避障作进一步研究。

参考文献：

[1] 卢川. 美国服务机器人技术路线图（下）[J]. 机器人产业，2016（5）：86-97.

[2] 搜狐新闻. 饿了么携手万科再推出外卖机器人[EB/OL]. www.sohu.com/a/197675763_99983474.html，2017.

[3] YU Q X，YUAN C，FU ZH，et al. Research of the localization of restaurant service robot [J]. International Journal of Advanced Robotic Systems，2010， 7（3）： 227-238.

[4] 环球网. 全球首创！澳大利亚Domino推出送餐机器人，萌萌哒！[EB/OL].http：//www.huanqiu.com/www/mobilenews/hot/2016-03/873 8434.html.

[5] 搜狐新闻. 英食物外送机构将在欧洲四城市试用机器人送餐[EB/OL]. http：//www.sohu. com/a/102335913_162522.html.

[6] 王丽. 移动机器人路径规划方法研究[D]. 西安：西北工业大学，2007.

[7] 石为人，王楷. 基于Floyd算法的移动机器人最短路径规划研究[J]. 仪器仪表学报，2009，30（10）：2088-2092.

[8] 金小平，何克忠. 移动机器人的动态路径规划及控制[J]. 机器人，1990（6）：10-17.

[9] 王哲，孙树栋，曹飞祥. 动态环境下移动机器人路径规划的改进蚁群算法[J]. 机械科学与技术，2013， 32（1）：48-52.

[10] 王娟娟，曹凯. 基于栅格法的机器人路径规划[J]. 农业装备与车辆工程，2009（4）：14-17.

[11] 郝宗波，洪炳镕，黄庆成. 基于栅格地图的机器人覆盖路径规划研究[J]. 计算机应用研究，2007，24（10）：56-58.

[12] DORIGO M. Ant colony optimization[M]. California：Bradford Company，2004.

[13] 周磊. 改进蚁群算法在机器人路径规划中的应用研究[D]. 上海：华东理工大学，2013.

[14] 段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社， 2005.

[15] 郑勇. 基于蚁群算法的移动机器人动态路径规划[D]. 成都：电子科技大学，2008.