一种多机器人服务圆形区域搜索算法

本发明涉及云机器人服务领域，具体涉及一种多机器人服务圆形区域搜索算法。

多自主移动机器人服务调度是在服务能够被调度的情况下选择出最优服务，在服务足够多、服务密度很大的情况下能够快速推送最优服务是人工智能和多机器人领域研究的重要话题。而且，待调度机器人工作在动态的、非结构化的环境中，由于机载能力低、成本高、无法进行高性能计算等问题，限制了多机器人发展。卡耐基梅隆大学的Kuffer博士于2010年在Humanoids会议上首次提出了“云机器人(cloud robotics)”的概念，将机器人学与云计算进行结合，将数据处理、轨迹规划、数据存储、最优决策等繁重的计算任务卸载到云端，机器人只需携带各种传感器和执行机构就能完成复杂的动作，这样既能降低机器人负载又能充分利用云计算资源。在这之后，云机器人的概念被广泛使用。2013年，Ben Kehoe和Akihiro Matsukawa等人提出了“基于云的机器人抓取谷歌对象识别引擎”，它集成了一个Willow Garage PR2机器人和机载彩深度相机、谷歌的专有对象识别引擎、点云库(PCL)来实现三维机器人的抓取。2015年，Gajan Mohanaraja等人基于RoboEarth提出了一种新的云机器人平台——Rapyuta，它是RoboEarth云引擎的在线数据库，旨在允许机器人查询数据库以了解其环境构建以及提供指导；中国科学技术大学的姜媛媛等人提出了仿人机器人理论，她们团队设计的仿人机器人有类人的动作并且具有独立的环境感知和自适应能力，它能像AlphaGo那样通过不断地学习环境信息并自主完成一些非凡的任务。

然而在现有机器人研究的基础上进行的通用集成面临着硬件异构性、软件异构性等许多技术问题。为了解决异构性和异质性问题，1996年Gartner Group最早提出了面向服务的架构(Service Oriented Architecture，SOA)，之后此服务架构被广泛采用。2016年，Cai Y F等人为了解决多机器人合作中异构性问题，提出了一种多机器人协作的多层SOA面向服务体系结构。2017年，Skarzynski，Kamil等人基于SOA提出了一种分布式机器人系统的通用体系结构和用于执行组合服务的通用协议以及用于监视执行和从失败中恢复的简单协议。

上述研究主要是对云机器人体系架构和多机器人SOA接口层的讲解，但尚未对实际场景的多机器人服务调度问题进行介绍。

本发明设计开发了一种多机器人服务圆形区域搜索算法，本发明的发明目的是通过圆形区域搜索算法实现从大密度、多数量的特定功能机器人服务中选择出最优服务。

本发明提供的技术方案为：

一种多机器人服务圆形区域搜索算法，包括如下步骤：

步骤一、服务申请者发出服务申请后获取所述服务申请者的位置，并且以服务申请者为中心，确定搜索区域，过滤掉不在所述搜索区域内的服务类型；

步骤二、如果在所述搜索区域内有所需服务，并且如果所述所需服务被占用，则跳过被占用服务搜索直至所述所需服务结束进入到搜索范围，如果所述所需服务未被占用，选择距离最近且评分参数最优的服务同时停止该服务的搜索；如果在所述搜索区域内没有所述所需服务，则扩大所述搜索区域的搜索半径；

步骤三、如果在所述搜索区域内搜索到全部服务，并且如果服务提供者的服务调度时间小于所述服务申请者的最大容忍时间，则所述服务提供者为所述服务申请者提供服务；如果服务提供者的服务调度时间不小于所述服务申请者的最大容忍时间，则所述服务提供者作为第二服务申请者重新提出服务申请，并且重复上述步骤搜索到服务调度时间小于所述服务申请者的最大容忍时间，确定为所需要的服务提供者。

优选的是，在所述步骤一中还包括：在所述搜索区域内将服务类型设定为二维数组，所述服务申请通过最小化原则拆分成三种服务类型，以所述服务申请者为圆心，确定搜索的半径范围，过滤掉不在圆形区域内的二维数组。

优选的是，在所述步骤三中，所述服务调度时间计算过程为：

或者

式中，xu为服务提供者到服务申请者的最短距离，vsu为服务申请者的自主移动速度，vsv为服务提供者的自主移动速度。

优选的是，所述最大容忍时间为90s。

优选的是，在所述步骤二中，计算所述距离包括如下步骤：

步骤1、创建起始节点距离集合和其他相邻节点距离集合，并且创建点集合，初始化为只有起始节点；

步骤2、计算所述初始节点到其他节点的最短距离，并将最短距离记录在所述起始节点距离集合中，计算其他节点与其相邻节点间的距离并记录在所述其他相邻节点距离集合中；

步骤3、获取所述其他相邻节点距离集合中最短距离对应的节点，将加入到所述点集合中；

步骤4、以所述步骤3中获取的节点为中间点，获取所述中间点到相邻节点距离，如果相邻节点到初始点距离大于所述中间点到初始点距离与所述中间点到所述相邻节点的距离和，则对所述起始节点距离集合中的距离值进行更新；

步骤5、重复进行所述步骤3、所述步骤4，直到所有节点都包含在所述点集合中。

优选的是，计算所述距离函数为：

式中，α＝0.1。

优选的是，在所述步骤二中，所述评分参数计算过程为：

y＝wscore×Rscore+wsuccess×Usuccess；

式中，wscore、wsuccess为各个参数的权重值，并且wscore+wsuccess＝1。

优选的是，所述评分参数的函数为：

式中，β＝5.5。

本发明与现有技术相比较所具有的有益效果：

1、本发明主要研究了一种SOA云平台的多机器人服务圆形区域搜索算法(CASA)，CASA是将各种特定功能自主移动机器人看成一种服务，以服务申请者为服务搜索圆心，服务的类型和经纬度为服务搜索指标，最短距离和评分参数为最优服务筛选指标，采用逐渐扩大搜索范围的方式获取最优服务的一种服务搜索算法；

2、本发明采用Django作为Web框架，搭建了由SOA服务模型及接口层、云平台基础层、服务资源层组成的多机器人组合服务的SOA基础云平台；使用CASS在MySQL现有的注册服务中进行最优服务筛选，并应用Dijkstra算法在高德地图上进行最短距离计算和最短路径规划，以服务提供时间最短为目标，为服务申请者提供最优服务，同时对SOA云平台的多机器人服务CASA工作性能进行了仿真测试；

3、本发明中以申请自驾游服务为实例，对汽车、聊天、翻译服务机器人的服务调度进行了仿真，从仿真结果可以看出：相对于全局搜索，多机器人服务云平台的CASA避免搜索的盲目性，缩小了搜索服务的时间，具有实用性；并与贪婪算法对比，CASA在服务搜索时间上减少了约58％，具有高效性。

图1为本发明所述的云平台总体设计示意图。

图2为本发明所述的圆形区域搜索算法流程示意图。

图3为本发明所述的距离函数图像示意图。

图4为本发明所述的评分参数函数图像示意图。

图5为本发明所述的服务参数筛选流程图。

图6为本发明所述的满足要求服务示意图。

图7为本发明所述的申请者A圆形区域筛选示意图。

图8为本发明所述的圆形区域筛选流程图。

图9为本发明所述的最优服务行走路线示意图。

图10a本发明所述的服务数量示意图。

图10b本发明所述的服务数量示意图。

下面结合附图对本发明做进一步的详细说明，以令本领域技术人员参照说明书文字能够据以实施。

如图1所示，本发明搭建的SOA多机器人服务云平台架构总共分为三层：SOA服务模型及接口层、云平台基础层、机器人服务资源层。

如图2所示，本发明提供的一种多机器人服务圆形区域搜索算法(CASA)，CASA是将各种特定功能自主移动机器人看成一种服务，以服务申请者为服务搜索圆心，服务的类型和经纬度为服务搜索指标，最短距离和评分参数为最优服务筛选指标，采用逐渐扩大搜索范围的方式获取最优服务的一种服务搜索算法，若一个地区有成千上万种机器人提供的服务，每次有服务申请时(可能同一时间会有多个请求)，如何从大量的服务里面选择最优服务推送给申请者这是本文需要解决的问题，具体包括如下步骤：

步骤一、服务申请者发出服务申请后获取所述服务申请者的位置，并且以服务申请者为中心，确定搜索区域，过滤掉不在所述搜索区域内的服务类型；

步骤二、如果在所述搜索区域内有所述所需服务，并且如果所述所需服务被占用，则跳过被占用服务搜索直至所述所需服务结束进入到搜索范围，如果所述所需服务未被占用，选择距离最近且评分参数最优的服务同时停止该服务的搜索；如果在所述搜索区域内没有所述所需服务，则扩大所述搜索区域的搜索半径；

步骤三、如果在所述搜索区域内搜索到全部服务，并且如果服务提供者的服务调度时间小于所述服务申请者的最大容忍时间，则所述服务提供者为所述服务申请者提供服务；如果服务提供者的服务调度时间不小于所述服务申请者的最大容忍时间，则所述服务提供者作为第二服务申请者重新提出服务申请，并且重复上述步骤搜索到服务调度时间小于所述服务申请者的最大容忍时间。

在本发明中，选择距离较小且评分参数较高的服务，且如果对距离和评分参数不做处理，则服务选取对两者的敏感度会很高。基于服务选择时对距离和评分参数的特殊要求，可以选择距离函数和评分参数函数对两者进行归一化处理，选择最优服务函数是为了表示距离函数和评分参数函数值在不同的距离范围所占的比重。

目标服务的选择原则：选择距离较小且评分参数较高的服务，且如果对距离和评分参数不做处理，则服务选取对两者的敏感度会很高。基于服务选择时对距离和评分参数的特殊要求，可以对距离和评分参数进行归一化处理。

如图3所示，距离函数选择：服务选择时距离越大被选到的机会越小、距离越小被选到几率越大；本发明中选择高斯衰减函数为距离函数，选取α＝0.1；

随着用户和服务之间距离x的增大，用户选择该服务的概率f(x)随之降低，当距离不断增大时，即服务和用户之间的相关度趋于零。

如图4所示，评分参数函数选择：与距离函数相反，评分参数越大被选到的几率越大；本文选取评分参数函数如下：

式中，选取β＝5.5。

当评分参数y较大时，评分参数函数g(y)增速较大，服务选择优越度区别较大，反之服务选择优越度区别较小，符合服务选取要求。

最优服务函数确定：选取F(x，y)＝λf(x)+ηg(y)作为最优服务选取函数，式中λ、η为f(x)、g(y)的比列系数，即在不同搜索区域两者所占的比重，其值通过实验摸索求得。综上，最优服务函数如下：

当距离在不同范围时，选取不同的比例系数λ、η，0≤x≤2.5时距离函数f(x)所占的比重较大，2.5＜x≤4.5时评分参数函数g(y)所占的比重较大。最后，以F(x，y)的最大值为最优目标。

在另一种实施例中，在步骤二中，采用Dijkstra算法和高德地图进行最短距离计算和最短路径规划。Dijkstra算法是以高德地图某个节点(服务提供者)为起点到达目标节点(服务申请者)所经过节点间边的距离值和最小的算法。Dijkstra算法所需的节点、道路和距离数据是调用高德地图API通过Python爬虫程序获取的。Dijkstra算法在最短距离计算时需要声明三个集合：起始节点距离集合BDIS、其他相邻节点距离集合ODIS和点集合PIO。起始节点距离集合BDIS存放起始节点与其他节点之间的最短距离，当两节点不相邻时，距离为∞；其他相邻节点距离集合ODIS存放其他节点与其相相邻节点之间的距离；点集合PIO存放已求得最短距离的节点。假设起始节点为bdisa，目标节点为bdisb，Dijkstra算法的包括：

步骤1、创建起始节点距离集合BDIS，初始化为空；

步骤2、创建其他相邻节点距离集合ODIS，初始化为空；

步骤3、创建点集合PIO，初始化为只有起始节点bdisa；

步骤4、计算节点bdisa到其他节点的最短距离，并将最短距离记录在BDIS中，使得BDIS＝{′bdis1′：da1，...，′bdism′：inf，...，′bdisb′：dab}(bdis表示节点，d为前一节点到后一节点间的距离，inf表示距离值无穷大)；计算其他节点与其相邻节点间的距离并记录在ODIS中，使得ODIS＝{′bdisI′：{′bdis2′：dI2，...，bdisI′：dIl}，...，′bdisk′：′{′bdiso′：dko，...，′bdisp′：dkp}}(其中)；

步骤5、获取BDIS中最短距离对应的节点bdisn，将bdisn加入到PIO中；

步骤6、以bdisn为中间点，获取bdisn到相邻节点(不包括集合PIO中的节点)距离，若BDIS[bdish]＞BDIS[bdisn]+ODIS[bdisn][bdish]；

(bdish是某个与bdisn相邻的节点)，则更新BDIS中bdish节点的距离值，使得dh＝dn+dnh；

步骤7、重复步骤5、6，直到所有节点都包含在集合PIO中。

综上，节点bdisa到节点bdisb的最短距离x＝BDIS[bdisb]，最短路径为PIO中节点的顺序。

同时，在本实施例中，为了算法的可靠性，现做以下假设：

1、服务申请者所在区域服务很多且服务密集度较大，即在有限次服务搜索后就能定位服务；

2、服务申请者所在区域网络信号良好；

3、服务申请者所在区域交通便利；

4、服务的类型、经纬度、服务编号等都事先存储在数据库里，且每个服务上面都装有GPRS定位器和联网设备，服务结束后都能上传自己的服务结束位置。

在另一种实施例中，本次服务评分参数的选取原则包括两个方面：服务申请者的服务满足度评分、服务调度成功率指标。

1、服务申请者的服务满意度评分Rscore是服务申请者在服务结束后对各个服务提供者在本次服务中的评分；

2、服务调度成功率指标Usuccess是服务提供者在包括本次服务在内的已被调度成功的几率，成功率指标对最优服务函数的影响较大，综上所述可得评分参数y为：

y＝wscore×Rscore+wsuccess×Usuccess； (4)

式中，wscore、wsuccess为各个参数的权重值，且werocs sseccus+w＝1；作为一种优选，在本实施例中，取wscore＝0.4，wsuccess＝0.6；得到本次服务评分参数后和上一次的评分参数取平均数可得该服务等待被调度的评分参数。

在另一种实施例中，在步骤一～步骤三中进行圆形区域服务筛选具体包括：

步骤1、我们把每种服务都看成一个二维数组[Stype，Llon-lat]，其中，Stype表示服务类型，Llon-lat表示服务类型为Stype对应的经纬度；在本实施例中，假设数据库里有很多服务，按照二维数组的形式表示成表1的数组表；

表1 S-L数组表

步骤2、某服务申请者(经纬度为(Lon0，Lat0))申请的父服务通过逻辑最小化原则拆分成服务类型是Sk-1、Sk、Sk+1的三种子服务(其中，父服务可以根据自己需要选择多种)；首先，云平台选出服务类型为Sk-1、Sk、Sk+1的二维数组，如表1中第4～6行的单元格；

其中，逻辑最小化原则指的是服务管理中心在接收到服务请求后，依据服务分配数量最少、服务利用率最大的原则将父服务(块服务)拆分成多个逻辑状态的子服务，不同的子服务又有多个具有该子服务类型的分散于不同区域的服务实体与之对应。

步骤3、以服务申请者为圆心，R为半径确定圆形区域，过滤掉不在圆形区域内的二维数组，譬如，得到在圆形区域内的数组[Sk-1，L2]、[Sk-1，Ls]、[Sk-1，Ll](其中1≤s，l≤m)；

步骤4、由步骤3得到的落在圆形区域内的二维数组，分别取第k-1行的Lμ(μ＝2，s，l)通过Dijkstra算法计算到申请者经纬度(Lon0，Lat0)的最短距离并规划最短路径；

对于Sk-1有三种经纬度L2(LonL2，LatL2)、Ls(LonLs，LatLs)、Ll(LonLl，LatLl)，分别得到最短距离x1、x2、x3，三者对应的评分参数为y1、y2、y3，得到三组解(x1，y1)、(x2，y2)、(x3，y3)，分别带入公式(3)得到评分参数F1、F2、F3。若F1＞F2＞F3，则可以确定F1对应的服务类型Sk-1的经纬度为L2(LonL2，LatL2)，同时将经纬度为L2(LonL2，LatL2)对应服务的最短路径信息传输给该服务提供者解析，然后向服务申请者移动，此时停止服务类型为Sk-1的搜索；

步骤5、由于服务类型Sk和Sk+1不在半径为R的圆形区域内，所以在原半径的基础上增大nΔR(n≥1)，现圆形区域半径R+nΔR(n≥1)，重复步骤(2)、(3)、(4)，到服务类型Sk和Sk+1的经纬度Lh(LonLh，LatLh)、Lj(LonLj，LatLj)(其中1≤h，j≤m)；

步骤6、获得服务类型Sk-1、Sk、Sk+1的经纬L2(LonL2，LatL2)、Lh(LonLh，LatLh)、Lj(LonLj，LatLj)后，将这三种服务的接口信息和行走路径发送给服务申请者；

步骤7、由于很多服务机器人的移动速度较为缓慢且当服务调度距离较远时(比如服务申请者申请的Sk服务和Sk+1服务)，增加了服务调度时间，减少了服务的循环调度率。为了缩短服务调度时间，某服务提供者Su根据到服务申请者Ru的最短距离xu和自主移动速度vsu可有服务调度时间Tsu和Tsu′计算如下(式(6)中vsv为Su申请的服务自主移动速度)：

若服务调度时间Tsu大于人的最大忍受时间T＝90s，则作为服务申请者Rv(为前述的服务提供者Su)重复步骤2～6调度其它服务Sv(自主移动速度为vsv)；若Tsu′+Tsv≥Tsu(Tsv为服务提供者Sv的服务调度时间)，则放弃调度服务Sv，本身作为服务提供者Su到达服务申请者Ru。

实施例

在本实施例中，SOA多机器人服务云平台选用笔记本AMD A6-5350M处理器，8GB内存，AMD Radeon HD(8450G+8570M)双显卡。云平台部分采用Nginx作为云端反向代理服务器，结合Lua实现并行计算，Django作为Web框架，MySQL作为后台管理数据库，PyCharm作为编程器，Python作为编程语言，采用Restful软件架构风格，实验用经纬度是从高德地图获取的。

如图5所示，目前数据库中有30000条服务数据，服务申请者(经纬度为[117.2390864，39.2209323])需要自驾游服务，首先根据逻辑最小化原则将自驾游服务拆分后包括汽车服务(具有载物能力)、聊天服务、翻译服务三种服务，然后执行命令筛选出满足这三种服务类型要求的服务的经度、维度、服务编号，最后将所有满足服务要求的服务数据打包成JSON格式传输到前端。

如图6所示，满足服务类型要求的服务点在高德地图上显示，其中圆表示以A为中心的区域搜索圆。

如图7、图8所示，由于满足要求的服务点太多且距离太远，所以先确定半径为1km的搜索圆，显示在圆内满足要求的服务点，过滤掉圆外的服务点，分别计算每个服务点到服务申请者的最短距离x，并将最短距离赋值给该服务点对应的服务，若在1km范围内没有满足要求的，则逐渐扩大搜索范围，直至搜索到所有的服务类型数据。

通过圆形区域筛选出的服务点在云平台进行最优服务函数值计算，筛选结果如表2。

表2 服务申请者1000米范围内的服务筛选结果

从上面数据可得汽车服务中满足条件的服务经纬度是[117.2350593，39.2249956]，由式(3)计算最优服务函数值为0.955208；同理，聊天服务中满足条件的最优服务经纬度是[117.2340694，39.2192569]，最优服务函数值为0.876785。

由于在1km的范围内没有搜索到翻译服务，所以增大搜索半径(R＝R+ΔR，ΔR每次增加0.5km)，当搜索半径为1.5km，如图7，获得翻译服务的筛选结果如表3。

表3 服务申请者1.5km范围内的服务筛选结果

与汽车服务和聊天服务一样，翻译服务的最优服务取经纬度为[117.2422294，39.2316456]、最优服务函数值为0.744387。

如图9所示，得到最优服务的经纬度后，将最优服务的基本信息、接口参数、最短路径信息发送给服务申请者，在图9中1为服务申请者，2、3、4分别为汽车服务、聊天服务、翻译服务。

通过高德地图获得汽车服务、聊天服务、翻译服务到服务申请者的最短距离x分别为0.432306km、0.418km、1.170km，假定三者的自主移动速度分别为5m/s、0.5m/s、0.5m/s，由公式(5)得三者的服务调度时间Ts分别为86.46s、836s、2340s，可知聊天服务和翻译服务的服务调度时间Ts大于90s，且汽车服务有较快的自主移动速度和载物能力，所以为了缩短服务调度时间，聊天服务和翻译服务作为服务申请者(经纬度分别为[117.2340694，39.2192569]，[117.2422294，39.2316456])申请汽车服务。

1、聊天服务的筛选结果如表4。

表4 聊天服务作为服务申请者申请汽车服务的结果

取经纬度为[117.2350694，39.2212569]，最优服务函数值为0.974561的汽车服务，到聊天服务的最短距离x为0.232km，自主移动速度为5m/s，由公式(5)得服务调度时间Ts为46.4s，到达聊天服务所在地后，载上聊天服务后行驶完0.418km后到达最终目的地，用时83.6s，所以聊天服务到达最终目的地的最终用时为130s，较申请服务之前节约用时706s。

2、翻译服务的筛选结果如表5。

表5 翻译服务作为服务申请者申请汽车服务的结果

取经纬度为[117.2431652，39.2331326]，最优服务函数值为0.986571的汽车服务，到翻译服务的最短距离x为0.257km，自主移动速度为5m/s，由公式(5)得服务调度时间Ts为51.4s。到达翻译服务所在地后，载上翻译服务后行驶完1170m后到达最终目的地，用时234s。若汽车服务载上翻译服务后，行驶到一半时自带导航系统出现故障，需要原地申请导航服务，筛选结果如表6。

表6 汽车服务作为服务申请者申请导航服务的结果

取经纬度为[117.2435642，39.2343565]，最优服务函数值为0.984271的导航服务，到汽车服务的最短距离x为0.166km，假定自主移动速度为1.5m/s，由公式(5)得服务调度时间Ts为110.67s，若抛去服务请求和数据处理时间，只算服务提供者到服务请求者的行驶时间，则翻译服务到达最终服务申请者的时间为279.07s，较申请服务之前节约用时2060.93s。

如图10a、图10b所示，按上述算法，假定服务申请数量是三个，现有服务数量在0～30000范围内，将CASA和常用的贪婪算法(Greedy Algorithm)进行服务搜索时间对比，在图10a中，随着注册服务的数量的不断增多，服务搜索时间呈现不断上升的趋势，当服务注册数量为10000时，CASA较贪婪算法节约用时近53％，当服务注册数量不断增加30000时，两者的服务搜索时间虽然都有所增加，但CASA较贪婪算法平均节约用时也大于50％；同理，假定现有服务数量为30000，服务申请数量在0～8变化时，将CASA和贪婪算法进行服务搜索时间对比，在图10b中，随服务申请数量的不断增多，服务搜索时间也呈现不断上升的趋势，当服务申请数量达到8个时，CASA较贪婪算法平均节约用时近63％，因此，本发明提出的CASA较贪婪算法在调度最优服务时的等待时间相对较小，云平台服务的实时性较好。

尽管本发明的实施方案已公开如上，但其并不仅仅限于说明书和实施方式中所列运用，它完全可以被适用于各种适合本发明的领域，对于熟悉本领域的人员而言，可容易地实现另外的修改，因此在不背离权利要求及等同范围所限定的一般概念下，本发明并不限于特定的细节和这里示出与描述的图例。