多机器人系统中基于环境侧信息的移动任务调度算法

叶 刚 周庆隆

1(埃森哲(中国)有限公司先进技术中心 上海 200072)2(佳能信息系统(上海)有限公司 上海 200235)

0 引 言

随着机器视觉﹑语音识别等人工智能技术和自动驾驶技术的快速发展，基于此类技术的服务型机器人也得到了飞速发展。近年来，我国适龄劳动人口数量开始逐步减少，劳动力成本不断增加，为企业带来了较高的成本压力。这些都为服务型机器人进入酒店宾馆服务业领域提供了应用场景的需求。目前在条件具备的酒店宾馆企业试验、测试和部署服务型机器人的商业机会越来越多，也促进了这一新技术研究和开发不断走向成熟[1]。

在为某国际知名酒店经营管理集团规划未来的企业发展战略的项目中，本文提出了基于智能服务型机器人驱动商业场景变革的计划，并对POC(Proof of Concept)系统及其对所规划的商业场景应用进行了验证性测试。以实用化为目标，基于分散型的环境侧信息获取手段，构筑并实现了应用于模拟酒店环境的智能移动机器人系统，并通过仿真机器人与实际机器人相结合的方法验证了系统性能能够满足实际产品工程化的需要。

1 智能机器人系统的应用场景

POC系统以酒店的客房服务为应用场景，客户通过手机或者房间内的智能音箱向系统请求客房服务。系统设计了一个任务分发器来接受和响应配送服务请求，在机器人允许承载条件下将一个或者多个服务任务动态分配给合适的机器人。机器人接受任务后，从待机位置移动到预先设置的配送源位置，装载配送货物后向配送任务目标位置移动，到达后系统通知客户自取配送物。机器人通过摄像机进行人脸识别确认客户，并通过搭载语音设备和客户交流，当客户取得配送物，命令机器人返回后，机器人返回待机位置等待下一次任务。

2 系统实验的基础设施

系统实验环境由模拟典型酒店的2个楼层和电梯组成，如图1所示。在每个楼层分别布置了多个超宽带UWB无线定位系统的锚点，采用6 GHz的频谱实现对机器人搭载的移动UWB标签的无线定位[2]。

图1 系统实验环境

同时，酒店中一般都设置有WLAN的无线通信环境，也可以用于移动机器人和系统控制之间的通信。由于机器人需要在不同楼层间移动，所以系统还集成了电梯控制器接受系统指令，通过电信号的旁路输入模拟电梯按键的楼层选择，以实现不同楼层之间的配送服务。

移动机器人和搭载设备如图2所示。采用了一套DC12V 37AH的电池作为机器人和搭载设备的供电电源；机器人搭载了一台WLAN无线路由器实现和后台系统的通信；机器人的移动由2个步进电机控制驱动轮和2个维持机器人平衡的万向从动轮，利用一套Arduino Mega 2560微控制器的控制板作为主动轮步进电机驱动控制器[3]；机器人前向具有3个超声波探测器，后向具有1个超声波探测器，并搭载了一套单线SLAM探测器用于环境扫描和地图构建[4]；机器人搭载了一套UWB移动定位标签和一套运行ROS Kinetic[5]版本的树莓派3B+嵌入式系统。由于UWB难于满足局部的精确定位和导航，所以在机器人定位和导航中，采用基于UWB无线定位技术来实现多台机器人全局路径规划。结合单台机器人自身基于SLAM、惯性导航和超声波避障的局部路径规划，设计了两层结构的路径规划器在复杂的人机共存环境中将多个移动机器人导航到各自的目的地。

图2 移动机器人和搭载设备

机器人搭载了一台嵌入式工控机作为视觉控制器，一套6自由度的机械手臂和一台高清云台摄像机。利用机器视觉技术在大场景中实现物体分类，以实现目标物体的发现，并初步估算目标物距离和方位以供全局移动路径规划。在机械手臂手爪的末端搭载了一台双眼同步摄像机和一个激光测距模块实现了一套眼在手(Eye In Hand)系统[6]。双眼同步摄像机结合激光测距模块实现近距离对目标物的几何尺寸和手臂与目标物之间空间距离的感知，以供手臂动作控制器实现抓取动作的规划。

另外，机器人搭载了一套6麦克语音矩阵和喇叭，实现360度声源定位和关键字语音唤醒。麦克风矩阵后端的语音控制器，利用其CUDA库实现语音到文字的高速识别和文字到语音的合成[7]。该控制器通过网络和后台的名为XBot的自然语言处理的对话应答系统进行通信实现语义理解，并产生应答文字的转换音频输出，实现和客户的语音交流。

3 多台移动机器人配送系统的构成

POC系统由多台移动机器人、各楼层的机器人UWB实时定位服务器、机器人位置管理服务器、机器人控制指令服务器、视频传输媒体服务器、人脸识别服务器(iFace)、语音对话应答服务器(XBot)、系统运行管理服务器、配送任务调度服务器、电梯控制装置等构成。各个服务器和设备通过WLAN无线网络和LAN连接成一个分布式系统。其构成如图3所示。

图3 配送系统的构成图

其中，任务调度服务器负责机器人移动和机械手臂的动作任务规划，iFace负责机器视觉和人脸识别，XBot负责语义理解和应答对话，机器人位置管理服务器负责机器人在全局地图中的坐标管理，机器人控制指令服务器负责不同楼层的路径规划和机器人控制指令的转换等工作。

4 移动任务调度器及其评价算法

POC系统中的配送任务调度服务器利用在预知环境中部署的环境侧传感器来定位机器人[8]。其调度方法采用全部机器人的总移动距离和用户任务从请求到实行完成所需要的时间作为评价函数的主要参量，实现了满足多个客户配送请求的多机器人任务动态分配和移动规划。

4.1 调度的评价要素和目标

在机器人数量足够的情况下，用户的配送请求可以按照请求的时间顺序向各个移动机器人按照先进先出调度策略进行任务分配。一台机器人执行一个客户的配送请求，任务完成的及时性非常高，但是机器人总移动距离最长，系统整体效率低下。如果能够调度一台机器人能在一次移动中同时尽可能承担多个客户配送请求，那么系统的整体效率就可以得到极大的提升。POC系统中采用的调度算法实现了从客户配送请求开始到任务执行完成所需时间尽可能短的同时，机器人移动效率尽可能高的效果。

4.1.1 评价要素1

机器人的作业领域按照图1的若干个区域进行粗粒度的网格化分割。POC系统调度考虑如下的区域重合度调度策略：对于分配了配送任务的机器人i，为了完成实行中的任务所必须通过的区域，以及新分配的任务所必须通过的区域，这两者之间的区域重合度是非常重要的一个考量。一般而言，向重合度高的机器人分配任务，系统全局效率可以得到较大提高。为了实现上述构想，考虑到算法搜索计算的实时性，可以将机器人实际作业空间和网格化分割的抽象作业空间作为2层的阶层化的搜索空间。本文将此粗粒度网格化[9]的搜索空间称为Meta Level的空间，此搜索空间的状态根据配送请求的到达时间而动态变化。采用深度优先图搜索算法[10]的机器人实际移动的空间称为Base Level空间，根据Meta Level空间状态的动态变化，Base Level的通过点的顺序也动态变化。这个阶层化的搜索空间如图4所示。

图4 阶层化的搜索状态空间

对于单个机器人，用户的配送请求到达时，通过区域的重合度如图5所示。

图5 多个配送任务的重合度

图5中，QA的灰色区域为机器人i分配的执行任务中已经通过的区域；在现在时刻t，新的客户配送请求到达移动任务调度器，QB为此新任务预定通过区域，QC为机器人i在时刻t的未通过区域；在时刻s，客户的配送请求任务如果被分配给机器人i，则QB和QC求和的集合QD就成为了机器人i的新的搜索空间。根据Meta Level中QD的通过区域的顺序，将其Meta Cell中所包含Base Level层中的通过点队列，在图4的搜索状态空间中向Base Level层投影，就可以确定Base Level通过点的顺序。

4.1.2 评价要素2

为方便起见，假定配送作业中，任何机器人的移动速度相同。图6给出了某配送任务的移动路径，按箭头指向的移动路径进行配送的话，配送任务从出发位置到目标位置移动所需要的时间和机器人的移动距离就成比例关系。所以，统计出机器人从出发位置到目标位置的移动时间，也就确定了其移动的距离。

图6 机器人移动路径图

4.2 调度器的评价函数

针对时刻t接收到的新配送请求向机器人进行移动任务分配时的评价函数进行说明。评价函数综合以下要素：(1) 通过区域的重合度，(2) 机器人现在位置到该任务的出发位置的移动步数，机器人的可配送重量，配送优先度等级等。可用以下的算法表示。

(1) 机器人i的顺序待通过区域的队列定义为:

Queue(l)={q[1],…,q[i],…,q[l]},where ∀i≥0q[i]∈Nandq[i]≤Amax

Queue(0) is a null Queue

q[i]是通过区域的ID编号，N是一个自然数，Amax表示通过区域ID编号的最大值。

(2) Meta Level搜索空间的定义为:

T=Queue(0)∪Queue(l)

(3) 通过区域队列的方向函数定义为:

Direction(Queue(l))=

(4) 机器人执行中的配送任务表示为:

Task(r,Q,s)=(r,Queue(l),s), whereQis a Queue,ris the robot, andsis the time when the task is viable

projection:

μQ(Task)=Q, Task projection on Queue

μr(Task)=r, Task projection on robot

μs(Task)=s, Task projection on s

Task(r,Q,s)为机器人r在时刻s被分配的任务的状态空间的通过区域。μQ(Task)为配送任务Task(r,Q,s)在Q上的投影，即Meta Cell的有向待通过队列。μr(Task)为配送任务Task(r,Q,s)在r上的投影，表示某一台机器人。μs(Task)为配送任务Task(r,Q,s)在s上的投影，这里的时刻s是指机器人r现在执行中的配送任务的被分配的时刻，即求取时刻s的函数。新配送请求到达时，执行中任务的未完成部分为：

Unexecuted(r,Task,t)=(φt(μQ(Task)),r)

∀t≥μs(Task)

where Task=(Queue(l),r)

Unexecuted(r,Task,t)表示新配送请求到达的时刻t，机器人r已经执行中任务的未通过区域的求解函数。其中函数:

φt(μQ(Task))=φt(Queue(m))=

where

len(t) is the Queue subscript to be executed at timetandlen(μs(Task))=l

φt(μQ(Task))表示新配送请求到达的时刻t，机器人r从当前位置开始的μQ(Task)中未通过区域的获取函数。len(t)表示新配送请求的到达时刻t，μQ(Task)中已通过区域长度的求解函数。新配送请求达到时刻t，机器人r的残留未通过区域的求解函数为:

Mexe(Unexecuted(r,Task,t))=φt(Queue(m))

Unexecuted(r,Task,t)=(φt(Queue(m),r)

新配送请求达到时刻t，机器人r的状态表示为:

0：机器人r待机中，无执行中的任务。

1：机器人r有一个或者多个任务执行中。

任务调度评价函数的计算表达式如下：

whenTaskAddas the queue for new planned task

ifTaskAdd=Queue(n) Then

式中:TaskAdd表示新配送任务，一个具有执行顺序的通过区域的队列。Sr(t,TaskAdd)表示在时刻t的机器人r，从当前位置到新配送任务的开始位置的距离。StepMax：正规化的定数，具有足够大的值。Cr()表示机器人r的新配送请求的通过区域，和新请求到达时机器人原有任务的未通过区域的重合度的求解函数。δr(t)表示新配送请求到达时刻t，机器人r的状态。α表示重合度系数。

约束条件如下：

r∈Ω(TaskAdd)

Ω(TaskAdd)=

式中:r为某台机器人。Ω(TaskAdd)为新配送请求被系统接收时的机器人的集合。Direction(Kr(t,Task,TaskAdd)×Direction(TaskAdd)表示机器人r的新配送请求的移动方向和该机器人现在执行中任务的移动方向是否一致的判断。NumberTask表示机器人r可以承受的负载量。Priority(Kr(t,Task))表示机器人r执行中的配送请求的紧急程度。

5 移动任务调度器的系统架构

为了验证调度算法的有效性，本文采用AOP(Agent Oriented Programming[11])的概念，设计了具有记忆能力的Multi-Agent反射型系统架构[12]，如图7所示。

图7 移动任务调度器系统架构图

调度器的战略层根据前述的评价函数，可以从多台移动机器人中，选取最合适的机器人执行客户的配送请求。这里的RA作为各个机器人的Agent运行在内存中实现对Meta Level的搜索。最后，将各自的移动步数和移动路径的重合度向战略层汇报。RA的内部处理如图8所示。

图8 Robot Agent模块的内部处理

配送任务管理层根据图5中QD=QB∪QC的计算公式，将机器人执行中配送任务的通过点和新配送任务的计划通过点进行匹配，所生成的通过点的队列作为机器人的新通过的队列，由机器人迭代后续执行。

6 实 验

由于只有一台移动机器人，为了验证调度算法在多台机器人情况下的有效性，本文参照移动机器人的参数，在图9所示实验系统中，通过机器人模拟程序向机器人位置管理服务器发送模拟实时位置信息的方式模拟了2台机器人，与移动机器人一起进行了实验。

图9 实验系统架构

为了验证不同重合度系数对于系统配送总时间的影响，向实验系统在短时间内输入了15个具有路径重合的配送请求。通过设置重合度系数的不同变化，对配送任务的执行平均时间进行了统计，其结果如表1所示。

表1 不同重合度系数的执行时间结果表

为了验证调度算法的效率，本文选取了一个典型的配送任务场景进行实验，使用如图10中的两个配送任务。分别对机器人采用：在资源无限情况下配送任务独占机器人，及时性最高的任务调度策略；在资源受限情况下单台机器人按照FIFO方式的任务调度策略；按照本文算法的任务调度策略在实验系统上进行了测试。最后，和本文算法的理论计算数据进行对比。

图10 配送任务位置图

表2是配送任务A→B和C→D的起始点坐标数据。机器人的待机位置如图6所示，其中待机位置A1配置实机机器人。

表2 配送任务位置表

机器人移动速度为100 mm/s的情况下，使用1台机器人和2台模拟机器人对设定的2个配送任务，按照上述三种调度策略分别进行了实验，得到的2个任务合计配送时间的实验结果如表3所示。

表3 基于三种调度算法2个任务的总执行时间结果表

7 结 语

为了解决设定场景中时间序列上的多个用户向多台移动机器人的配送系统不断发起配送请求下，实现系统整体效率的优化，提出了以合并相近时间序列上配送任务中移动路径重合度较高的多个配送任务为手法的任务调度算法。并在设定的目标应用场景的实验环境中进行了测试，对提出的任务调度算法的有效性进行了评价。