智能体Petri 网融合的多机器人-多任务协调框架

李 勇 李坤成 孙柏青 张秋豪 王义娜 杨俊友

在照顾失能老人时需要花费大量的人力,像养老院这样的场所,需要大量的人力资源来完成这项工作.随着老龄化的发展[1]以及人工成本的不断上涨,这个问题会愈加凸显.机器人技术的发展使得一些服务型机器人已经能够在一定程度上帮助人们完成对老人日常生活起居和康复训练等活动的照顾.因此,使用服务型机器人来对老人进行照顾将会成为一个必然趋势.而面对一定数量的、功能不尽相同的服务型机器人,如何让它们能够协同起来帮助老人完成任务并保证该过程中老人的满意度就成为了一个必须要解决的问题.

Petri 网[2]是一种离散并行系统的数学描述方法,于20 世纪60 年代由卡尔·A·佩特里提出.它既有严格的数学表述方式,也有直观的图形表达形式,因其便于描述系统中进程或部件的顺序、并发、冲突以及同步等关系,Petri 网在多机器人系统的研究中一直占有一席之地.文献[3]提出了一个机器人软件系统的编程框架,使用信号解释Petri 网来描述任务并将其存储在XML 文件中,调度器加载这些文件并根据需要执行不同的Petri 网.文献[4]提出了一种基于Petri 网的新型表示框架,用于描述单机器人和多机器人行为,该框架形式上允许对编程认知机器人所必需的复杂动作交互进行高级描述.以上两篇文献均使用Petri 网对机器人的任务过程以及动作交互进行建模,由于机器人的操作对象与本文不同,二者仅对系统中机器人的状态以及动作进行描述,缺少被操作对象的状态以及机器人与被操作对象之间的交互过程,机器人相当于脱离了整个系统独自进行任务.

本文意在协调异构的服务机器人团队为老人服务,因此本文所建立的模型中既包含机器人的状态以及动作流程,也包含被操作对象的状态以及机器人与被操作对象之间的交互过程.由于养老院情境的特殊性,为了清晰地描述系统状态,需要使用含有时间因素的Petri 网以及颜色Petri 网来对系统进行建模.例如,时延Petri 网所提供的时间信息可对系统的状态进行时间上的预测,比如计算老人完成任务需要的大致时间、判断机器人何时回到空闲状态等;颜色Petri 网可以对系统中不同的 “资源”进行分类,即实现对网系统的折叠,从而更清晰地描述多个机器人和多位老人情况下的协调过程.即便如此,在使用Petri 网对养老院情境进行建模时仍无法解决 “老人们各行其道互不干扰” 以及 “随时调整老人对任务的执行权限” 等问题.因此,为解决以上问题,本文结合时延Petri 网和颜色Petri网提出了一种改进的Petri 网—可扩展时延-颜色Petri网(STdCPN)对养老院情境下机器人照顾老人的过程进行建模.但本文的研究内容不限于此,构建的STdCPN 模型将作为多机器人-多任务协调框架的基础,而如何在任务过程中提高被服务对象的满意度是本文的另一个重点.

目前,针对多机器人协调的研究主要集中在解决多机器人的任务分配[5-7]、路径规划[8-9]、编队控制[10]、勘探制图[11-13]等问题上,该领域中绝大部分的研究都不涉及 “人的因素”,也不需要考虑协调过程中人的感受和情绪.在机器人领域中,有少量研究涉及到了最基本的人的安全性.文献[14]从减少焊接过程中重型零件的手动操作密度的角度来提高人的安全性.文献[15-16]从保证机器人与人之间适当的距离的角度来提高人的安全性.文献[17]通过调节机器人与人潜在碰撞期间内的冲击力因素的方法来提高人的安全性.而机器人领域中进一步考虑人的满意度的研究甚少.文献[18]为最大化团队效率和人类成员与机器人成员的合作意愿,将任务分配的权利交给工人,结果表明工人宁愿将控制权交给机器人,他们宁愿成为高效团队中的一员,而不是在调度过程中发挥作用.文献[19]为将人与机器人之间的相互作用系统化,以减少人的工作量并最大化用户满意度,开发了几种认知模型,这些模型可以根据任务来管理和启动交互,并通过使用交互结果修改机器人的活动.以上两篇文献分别从赋予人机混合团队中人一定的决策权和调整人机交互中人的工作量的角度来提高人的满意度.而本文完全将人类作为被服务的对象,从服务对象的角度出发,提出了服务对象满意度模型.将老人的满意度作为任务执行情况的一个重要指标,在协调多个机器人为多位老人服务的基础上,通过调整机器人在任务执行过程中的各项参数以及多个任务冲突时的任务执行顺序来最大化老人的总体满意度.

由于养老院中环境复杂,其中老人的身体情况、个人偏好、床位位置等都各不相同,需要根据老人的 “个人因素” (即性格急躁程度、被机器人拉起时的舒适速度、被机器人运载时的舒适速度、当前所处位置、自提出需求后的已等待时间以及所执行任务的优先级等)来对任务进行个性化的规划,同时需要根据各个机器人的实时状态、位置等信息来合理地分配系统资源.面对这些灵活的决策,智能体是一个合适的选择.文献[20]提出了一种自动建议智能体,该智能体通过分析系统当前状态,对系统接下来所有可执行动作的 “回报” 进行预测,然后找出 “回报” 最大的一种决策提供给人类操作员,从而提高系统效率并减轻人类操作员的工作负荷.但该文中机器人的操作对象是货架,并不涉及人的满意度,且使用该方法将带来巨大的计算负荷,因此一般情况下该智能体仅考虑系统接下来3 步之内的状态来计算得出当前时刻的最佳决策.

而养老院情境中虽然任务种类繁杂,但每个任务的流程是大致固定的,因此对系统中任意时刻所有机器人可执行的每个动作的 “回报” 进行预测是不必要的,且在执行如 “送老人去卫生间” 这样比较紧急的任务时,仅能预测系统接下来几步的状态是不能接受的.相反,在该情境下更加需要的是对机器人的任务执行过程有一个宏观的规划,这正是Petri 网的优势所在.因此本文使用STdCPN 对系统底层的运行情况进行建模,智能体只在必要时给出决策,这样就同时发挥了Petri 网的宏观规划能力和智能体的灵活决策能力,在协调多个机器人为多位老人服务的基础上,保持了系统的实时性.

本文结合时延Petri 网和颜色Petri 网提出了可扩展时延-颜色Petri 网(STdCPN)并对养老院情境下服务机器人团队照顾老人的过程进行建模.为提高该过程中老人即机器人所服务对象的满意度,提出了服务对象满意度模型,将老人的满意度作为任务完成情况的重要指标.设计了智能体对该协调框架进行调度,该智能体对老人的任务进行个性化的规划,合理分配系统资源,最大化老人总体满意度.

本文内容安排如下:第1 节介绍了STdCPN 子模型,并以此模型为例对改进的Petri 网—STd-CPN 进行详细阐述;第2 节建立了服务对象满意度模型;第3 节提出了基于智能体的协调框架;第4节对不同情况下智能体的决策进行仿真与分析;第5 节为结论.

1 养老院情境下基于STdCPN 的任务建模

要完成养老院情境下多个服务型机器人照顾多位老人的协调,对机器人照顾老人的过程进行建模是基础.由于养老院中任务复杂多样,因此应先对其中一个或相联系的几个任务进行子模型构建,之后便可根据该子模型推演出其他子模型,并根据实际需要将它们组合成完整的模型.现以机器人送老人去卫生间以及送回这两个相联系的任务为例,进行STdCPN 子模型搭建,并以此模型为例对STdCPN进行阐述.为说明该模型在多机器人多人情况下模拟能力的同时方便描述,令该模型中包含老人4 位、步行支援机器人2 台(记为SR,如图1 (a)所示,其主要功能是搀扶老人站起、坐下和移动)、智能轮椅机器人2 台(记为CR,如图1 (b)所示,其主要功能是运载老人从起始点到达目的地),构建的STdCPN 子模型如图2 所示.

图1 送老人去卫生间及送回过程中使用的机器人Fig.1 Robots for send the elderly to the toilet and return

图2 SR 和CR 协同送老人去卫生间及送回STdCPN 模型Fig.2 STdCPN model for SR and CR work together to send the elderly to the toilet and return

该模型中p1到p16为SR 与CR 协同将老人从床位送到卫生间的过程,p16到p1为SR 与CR 协同将老人从卫生间送回到床位的过程,这两个过程是不同的任务,即老人被送到卫生间后任务结束,经过不定长的时间后,当老人想要返回时,需要再次提出需求.该STdCPN 模型的具体数学表达式及运行过程见附录A.模型中库所的含义如表1 所示,变迁的含义如表2 所示.

表1 送老人去卫生间及送回STdCPN 模型中库所含义Table 1 The mean of spaces in the STdCPN model of send the elderly to the toilet and return

表2 送老人去卫生间及送回STdCPN 模型中变迁含义Table 2 The mean of transitions in the STdCPN model of send the elderly to the toilet and return

可扩展时延-颜色Petri 网是一个七元组,STdCPN=(P,T;F,D,C,W,M0),其中:P={p1,p2,···,pm}是库所的有限集,表示系统的资源、操作或状态等,当库所p内含有令牌时,库所p代表的意义生效;T={t1,t2,···,tn} 是变迁的有限集,代表系统状态间的转换,当变迁t的每个输入库所中的令牌量都大于等于该库所与变迁t间的权重时,变迁t可以触发,t的触发会从每个输入库所中移除对应权重的令牌量,并在每个输出库所中生成对应权重的令牌量;F⊆(P×T)∪(T×P) 是有向弧的有限集,连接库所与变迁;D是时延Petri 网中的概念,是定义在库所集P上的时间函数,即当令牌进入某一库所后,需要停留该库所时延量的时间才可以离开该库所;C={c1,c2,···,ck} 是颜色Petri网中的概念,是颜色的有限集,表示系统中资源的种类,当颜色集的维度改变后,系统中的令牌和权重等的维度都需要相应的改变;W是映射在有向弧集上的权函数,控制着变迁的发生规则;M0是映射在库所集上的初始标识,表示系统的初始状态.

STdCPN 模型利用库所上的时延量对系统状态进行时间上的预测,STdCPN 的时延量D不同于传统的附着于变迁上的时延量,而是附着于库所之上.如果将时延量附着于变迁之上,由于标识M映射在库所上,当变迁正在发生时,它的前集中的令牌会消失,而后集中的令牌需要等到变迁结束后才会出现,因此系统此刻的状态无法明确表示,而将时延量附着于库所之上,使所有变迁的时延量为零,则可以准确地通过标识描述系统任意时刻所处状态.

在该模型的时延因素D中,d为由传感器实时采回的机器人位置信息计算得出的机器人与老人床位间的路径长度,若任务所需机器人数量大于1,则d取其中最大值,vmax为机器人的最大移动速度,v为老人被分配的CR 运载速度,tup为预设的机器人以老人舒适速度搀扶老人站起所用时间,tdown为预设的机器人以老人舒适速度搀扶老人坐下所用时间,m为老人床位与卫生间内马桶之间的路径长度,含有以上量的各项时延量均是确定的.含有 “x”的时延量代表该时间具有不确定性,x1为老人在床位上停留的时间,x16为老人如厕的时间,这2 项时间取决于老人的实际需求.x2为SR 保持 “空闲状态” 的时间,x3为CR 保持 “空闲状态” 的时间,这2 项时间取决于实际情况下机器人的使用情况.x4和x17为从老人呼叫后至机器人响应请求的用时,这2 项时间取决于实际情况下机器人的使用情况以及智能体对机器人资源的分配情况.以上6 项时延量对应的6 个库所均处于任务开始之前,因此该6 项具有不确定性的时延量对系统状态的预测没有影响.x6、x12、x19和x25为SR 拉起老人之前老人的准备时间,x8和x21为SR 与CR 对接的时间,x14为SR 与马桶的对接时间,x27为SR 与床位的对接时间,这8 项时延量会受到老人个人情况的影响,但在实际应用中可以测出一个大致的值.这些时延量将仅做预测使用,实际以机器人每次完成动作后传回的信号为准,机器人每完成一个动作STdCPN 模型即可向前运行一步并为机器人指明下一步动作,同时刷新预测时间,这样就可以利用时延量对系统的状态进行预测.例如在老人出发后,可以预测老人距某一状态的大致时间,也可以预测大致多久后老人可以完成任务以及机器人何时可以回到空闲状态等.这些时间信息可以提供给智能体,作为多机器人-多任务规划的依据.

可灵活地对系统规模和系统中相同种类资源的数量进行扩展而不影响已搭建好的模型结构是Petri 网具备的特点.由于养老院这一系统的特殊性,其内所有任务的运行均是以被服务对象即老人为中心展开的,且各对象之间互不干扰,同时由于养老院的人员流动性以及不同养老院的机器人数量可能不同,因此构建的模型要能够随时调整资源种类,适应于不同的老人与机器人的组合.因此可扩展时延-颜色Petri 网的 “可扩展” 指的是通过对权函数中各项权重的 “矩阵化” 使得模型可以在不改变其结构的基础上任意增减资源种类,随时改变各资源对各子模型的执行权限.

使用传统的颜色Petri 网对系统建模时,会将系统中的 “资源” 进行分类,以该STdCPN 模型为例,系统中有4 位老人,2 台SR 和2 台CR,这8个 “资源”会被分为3 类,即颜色集C={MAN,SR,CR},令牌、权函数W的每项以及标识M的每项都为1 个三维向量.当需要增减老人或机器人时,仅需改变令牌向量相应位的大小;当变迁的规则变化时,权函数的改变会影响一整类 “资源” 的权限.而在养老院情境中,不能将老人和机器人视为如同“待加工的零部件”那样进行分类,因为每位老人和每台机器人都携带着他们的 “个人信息”,老人所携带的如床位所在位置、性格急躁程度、被机器人拉起时的舒适速度、被机器人运载时的舒适速度、当前所处位置、已等待时间以及所要执行任务种类等信息会影响智能体对该老人任务执行过程的规划,机器人携带的如是否处于 “空闲” 状态、当前所处位置以及该机器人种类等信息会影响智能体对该机器人的任务规划.因此在养老院情境下,不能将这些 “资源” 进行如上的分类,而是要将每位老人和每台机器人都区分开,因此需令颜色集C={MAN1,MAN2,MAM3,MAM4,SR1,SR2,CR1,CR2},即每个 “资源” 都是一类独特的 “资源”,因此该模型中令牌的每一位只能是0 或者1,当增减老人和机器人时,实际上都是在增加或者减少 “资源” 的种类,即令牌的维度.同时也需要权函数有能力为增加(减少)的 “资源” 提供(解除)权限,因此本文在结合时延Petri 网和颜色Petri 网的基础上,改进了权函数的形式并调整了网络的运行规则.改进后的权函数映射到有向弧上的每一位权重可以是向量也可以是矩阵,当权函数的某位权重为矩阵时,意味着该权重的每一行都为变迁的发生提供了一种可能.附录A 中给出的权函数W基于的条件是4 位老人均可以执行该任务且可以使用任意的SR 与CR 的组合.

使用改进权函数的STdCPN 运行规则:1) 当变迁具有1 个输入库所和1 个输出库所时,若变迁输入库所中的令牌不少于输入库所到变迁间权重的某一行,则变迁有发生权.变迁发生后,输入库所中的令牌减去该行权重生成新令牌,输出库所中的令牌加上变迁到输出库所间权重对应的同一行,生成新的令牌.2) 当变迁具有多个输入库所和1 个输出库所时,如果每个输入库所中的令牌都不少于该输入库所与变迁间权重中的某一行,则变迁有发生权.变迁发生后,这些行权重相加的结果等于变迁与输出库所间权重的哪一行,则输出库所内的令牌加上哪一行.3) 当变迁具有1 个输入库所和多个输出库所时,如果输入库所满足条件则变迁可以发生,变迁到多个输出库所的权重中,每个权重选出一行对它们求和,哪几行相加的结果等于输入库所减去的那一行权重,则在变迁发生后将这几行权重分别加到对应输出库所的令牌上.

需要强调的是:1) 由于STdCPN 的权重为变迁的发生提供了多种可能,若变迁具有多个输入库所和多个输出库所,会造成变迁发生时权重选择混乱,因此在使用STdCPN 建模时应避免这种情况的发生,可以通过如增加中间库所等方式实现.2) 为了使标识可以明确地表示系统当前状态以及防止老人之间相互影响,当多块令牌处于同一库所内时,除任务开始前(p1、p4)和结束后(p16)以及存储机器人的库所(p2、p3)内的令牌可以叠加外,在任务执行过程中,令牌均不可以叠加,而是按照各自的进度前进.

该STdCPN 子模型建立后,模型的运行会指示SR 和CR 需要完成的动作以及它们之间动作的顺序,从而协调2 台异构的服务机器人帮助老人完成任务.通过该STdCPN 子模型可以清楚地了解任意时刻系统中每位老人与每台机器人所处的状态以及他们间的联系,即可以清楚地知道哪一(几)台机器人正在为哪一位老人服务到哪一个阶段,这样就可以对整个系统有一个精准的把控,并可对系统状态进行时间上的预测,这些信息都将作为智能体进行任务规划时的依据.且STdCPN 模型的 “可扩展性”能够满足实际应用中老人和机器人数量的扩展以及对他们权限的限制,由于STdCPN 运行过程中并不涉及似矩阵求逆般耗时的计算,因此由老人和机器人数量扩展导致的模型中向量和矩阵维度的增加对模型的运行不会造成很大的影响.可以组合多个STdCPN 子模型来构成完整的养老院运行模型,作为养老院情境下多机器人-多任务协调的基础.

2 服务对象满意度建模

当STdCPN 模型搭建完成后,在机器人资源充足时,老人们均可以按照自己的需求随时进行各种任务.但在现实情况中难免会有短时间内多位老人接连提出需求甚至同时提出需求的情况,按此情形配置机器人数量会造成大量冗余.但如果机器人资源不够充足,系统将陷入僵局.由于每位老人的身体状况不同,所执行的任务紧急程度也不同,盲目地按照老人提出需求的顺序来执行任务可能会造成一些不良后果.同时由于该过程服务于人,那么应该从人的角度出发考虑,找出能够让老人们整体更满意的解决方案.因此通过对养老院情境的模拟以及该情境下老人心理的分析,提出了如下服务对象满意度模型.在该模型中,将任务分为不同的优先级,并将老人的性格急躁程度分为不同等级.假设在机器人帮助老人完成一项任务后,老人会根据此次任务的执行情况得出一个他心中的满意度.认为在该情境下,任务的优先级、老人的性格急躁程度、老人呼叫后的等待时间以及机器人运载老人的速度与老人的舒适速度之差都会对老人的满意度造成影响.建立的满意度模型如式(1)所示:

式(1)中Satf为老人的满意度,X代表老人,ex代表该老人要做的事件是事件x,k代表在当前队列中该老人排在第k位,n代表共有n位老人在队列中.Prior代表事件优先级,这里将所有事件分成五个等级,Prior∈{0,1,2,3,4},其中 “4” 为优先级最高的等级.Impat代表老人性格急躁系数,由于目前无法对性格急躁程度进行定量测量,假设性格急躁程度最低的人急躁系数为 “1.0”,该系数随着老人急躁程度的提升而增加,暂定为五个等级,Impat∈{1.0,1.1,1.2,1.3,1.4},twait为老人从提出需求开始直至机器人到达老人所在位置之间的总等待时间,v为老人被分配的运载速度,v*为老人预设的舒适运载速度.

对于式1 中第1 项,假设高优先级的任务在完成时会得到更大的满意度;对于式1 中第2 项,假设性格急躁系数Impat会被总等待时间twait以指数的形式影响,从而降低老人满意度;对于式1 中第3 项,假设机器人运载老人的速度v与老人舒适速度v*之差会以指数的形式对老人的满意度造成负面影响.

其中总等待时间twait由式(2)求得,由预计等待时间tew和已经等待时间taw两部分构成(taw产生原因是:当多位老人的任务产生冲突时,智能体会给出老人的任务执行顺序,当按照某种顺序执行后,在完成所有的任务之前若有新的老人加入队列或有任意种类机器人重回空闲状态,则需要重新计算得出基于当前时刻的任务执行顺序,因此需要一个已经等待时间来描述老人的真实等待时间).

预计等待时间tew由式(3)求得.当k=1 时,预计等待时间tew等于所派出机器人距离老人的初始距离中的最大值d与机器人最大行驶速度vmax的商;当 1＜k ≤n时,预计等待时间tew等于排在该老人前面一位的老人的预计等待时间tew,k-1加上前一位老人的任务执行时间(包括以老人预设的舒适方式将老人拉起的用时与拉起次数nup的乘积、以老人预设的舒适方式将老人放下的用时与放下次数ndown的乘积以及任务路程m与机器人运载老人速度v的商)再加上机器人到达所需用时dk/vmax.

运载速度v由式(4)求得,它等于老人的最舒适速度v*加上该老人的加速系数a在加速系数变化范围(amax－amin)内所占比例与该老人运载速度最大变化范围(vmax－v*)的乘积.

加速系数a由式(5)求得.当 1 ≤k＜n时,该老人的加速系数a等于该老人所执行任务的优先级的平方根加上排在该老人之后所有老人的任务优先级总和的平方根;当k=n时,加速系数a等于该老人所执行任务的优先级的平方根.

式(6)中Satfm为队列中所有老人的总体满意度,包括所有老人的个人满意度之和以及一个表示“优先级高的任务被先执行”程度的量f(prior1,prior2,···,priorn),其值为每一项分别减去其后各项再对所有正的结果求和.这样做的目的是适当提高优先级高的任务被先执行时的总体满意度,因为现实情况中高优先级的任务往往更紧急,需要优先被执行.

该满意度模型建立后,智能体对系统中的任务进行规划时除了考虑老人和机器人的实时信息外,还会考虑老人的满意程度,将满意程度的高低作为衡量任务完成情况的一个指标,在协调多个机器人为多位老人服务的基础上最大化老人的总体满意程度.

3 基于智能体的考虑人的因素的协调框架

该协调框架由STdCPN 模型和智能体两部分组成,STdCPN 模型作为该协调框架的基础,指示机器人如何协同完成任务,智能体作为该协调框架的 “调度者”,对系统资源进行分配,并根据老人的“个人因素” 对机器人的任务执行过程进行规划,其结构如图3 所示.

图3 基于智能体的考虑人的因素的协调框架结构示意图Fig.3 Diagram of coordination framework considering human factors based on intelligent agent

当老人提出任务需求后,STdCPN 模型的标识会产生对应变化,智能体根据STdCPN 模型提供的老人任务信息结合老人的个人信息以及满意度模型对老人的任务过程进行规划,并根据实时环境信息和STdCPN 模型提供的机器人实时状态信息派出合适的机器人,将此方案作为最佳方案输入到STdCPN 模型中,使机器人依据该方案按照STdCPN 模型执行任务;当多位老人的任务发生冲突且机器人资源不足时,智能体通过调整老人的任务执行顺序得出多个任务执行方案,并将这些任务执行方案输入到STdCPN 模型内进行模拟运行,从而得出计算满意度所需的时间信息,再通过满意度模型计算得出使得总体满意度最大的任务执行方案(由于目前系统规模较小,这里暂且使用穷举法,当老人、机器人和任务大量增加后,需要使用快速优化方法进行求解),然后将该方案作为最佳方案输入到STdCPN 模型中,使机器人依据该方案执行任务.

以上文搭建的STdCPN 子模型(图2) 为例,在不限制老人和机器人的数量、状态的条件下给出该协调框架的算法流程图,如图4 所示.图4 相当于智能体的 “思维方式” 智能体通过该 “思维方式”决定当前系统中的任务能否同时执行,如果不能,那么哪(几)个任务应该先被执行,如果执行应该派出哪(几)个机器人前往,在拉起和放下该老人时应该以什么样的速度,在运载该老人时应该以什么样的速度等问题.

图4 基于智能体的考虑人的因素的协调框架算法流程图Fig.4 Algorithm flow chart of coordination framework considering human factors based on intelligent agent

下面对该协调框架的算法流程图做一些解释:1) 由于 “等待区” 内新增老人和在 “等待区” 非空的前提下任意种类机器人重回空闲状态这两种情况都可能造成有新的具备出发条件的老人产生,所以每当这两种情况发生,智能体对当前时刻系统所处状态进行判断.2) “等待区” 内存在多位老人可能是由于先提出需求的老人不具备出发条件而随时间推移不断有新的老人加入从而堆积造成的,也有可能是多位老人在同一瞬间提出需求造成的.3) 当排在第1 位的老人被转移到 “等待机器人到来” 状态(p5或p18)内之后,智能体重新判断剩下的老人是否具备出发条件,然后再次对其中具备出发条件的老人进行排列组合,选出能够得到最大总体满意度的出发顺序执行.这样做的原因是:虽然最初多位老人都具备出发条件,但不同的任务需要的机器人种类和数量可能不同,所以当前机器人的种类和数量可能满足一位老人出发,也可能满足多位老人同时出发,因此当排在第1 位的老人进入下一状态后,排在第2 位的老人是否依然具备出发条件不明,同时也存在排在第2 位的老人不具备出发条件而排在第3 位的老人具备出发条件等多种可能,因此智能体需要重新判断.4) 将 “等待机器人到来” 状态内的老人返回 “等待区”并将对应机器人返回 “空闲状态”是因为 “等待机器人到来” 状态内的老人虽然任务已被规划但还未出发,而此时可能有新的具备出发条件的老人产生,因此需要根据这些老人的任务优先级、个人信息、机器人的实时状态、位置等信息重新规划任务方案.5) 将 “等待机器人到来”状态内的老人返回 “等待区” 后,不存在没有老人具备出发条件这种情况的原因是:被返回的老人正是因为具备出发条件才会存在于 “等待机器人到来”状态(p5或p18)内.

4 仿真与分析

对该协调框架进行了仿真,现对多位老人任务冲突且机器人资源不充足的情况下智能体给出的决策进行分析.

图5 是一个模拟的养老院场景平面图,从北至南分别是卫生间、A、B、C、D 4 位老人的房间以及餐厅.为方便计算,令相邻房间的门间距离为3 m,由房间的门口到老人床边的距离为3 m.该养老院拥有2 台SR (图5 中三角形)和2 台CR (图5 中矩形),它们可以将老人拉起、放下以及运载老人到达目的地,行驶最大速度vmax为1.2 m/s.假设该养老院当前有3 种任务:从床位去卫生间、从床位去餐厅和在机器人的帮助下站起.表3 为任务信息.

图5 养老院模拟场景平面图Fig.5 Nursing home simulation scene plan

表3 任务信息Table 3 Task information

4.1 不同个人信息情况下仿真与分析

考虑第1 种情况,多位老人在机器人资源不充足的情况下想要完成同一任务.如图6 所示,假设当前时刻老人D 占用了1 台SR 和1 台CR 正在执行 “去餐厅” 任务(图中未表示),仅剩1 台SR 和1 台CR 处于空闲状态且它们停在老人C 的房间门前,此时A、B、C 3 位老人同时想去卫生间,图7 为这一时刻的STdCPN 模型.

图6 机器人初始位置Fig.6 Initial position of the robots

图7 中,p1到p41为SR 和CR 帮助老人从床位去餐厅的过程,p41到p1为SR 和CR 帮助老人从餐厅回到床位的过程,p1到p16为SR 和CR 帮助老人从床位去卫生间的过程,p16到p1为SR 和CR 帮助老人从卫生间回到床位的过程,p1到p58为SR 帮助老人从坐到站的过程,p58到p1为SR 帮助老人从站到坐的过程.库所p36代表CR 运载老人从床位去餐厅的过程,其中的令牌[0,0,0,1,0,1,0,1]代表该状态中涉及到老人D、第2 台SR 和第2 台CR.库所p4为从床位去卫生间任务的 “等待区”,其中的令牌[1,1,1,0,0,0,0,0]代表A、B、C 3 位老人都有去卫生间的需求.库所p2和p3中的令牌分别代表第1 台SR 和第1 台CR 处于空闲状态.

图7 养老院运行情况STdCPN 模型Fig.7 STdCPN model of nursing home situation

现保持机器人初始位置和老人所执行任务种类不变,通过改变3 位老人的个人信息如表4,5,6 所示,来观察在个人信息不同时智能体给出的任务执行顺序.

案例1 中,图8 为不同任务执行顺序下智能体预测的3 位老人的个人满意度,图9 为不同任务执行顺序下智能体预测的3 位老人的总体满意度.图10,12 为案例2,3 老人的个体满意度.图11,13 为案例2,3 老人的总体满意度.如图9 所示,以CAB 的顺序帮助老人完成任务将会得到最大的总体满意度.

图8 案例1 中不同任务执行顺序下老人的个人满意度Fig.8 Personal satisfaction of the elderly under different task execution sequences in case 1

图9 案例1 中不同任务执行顺序下老人的总体满意度Fig.9 Overall satisfaction of the elderly under different task execution sequences in case 1

图10 案例2 中不同任务执行顺序下老人的个人满意度Fig.10 Personal satisfaction of the elderly under different task execution sequences in case 2

如表4 所示,在案例1 中,3 位老人的个人信息是相同的,这种情况下智能体给出的任务执行顺序将完全基于3 位老人和机器人的位置信息.当机器人经过C 的房间时帮助C 是顺路的,如果不帮助C,之后需要返回,这样会增加总路程,导致老人们的总体等待时间增加,因此它选择了先帮助C.帮助完C 之后,此时先帮助A 再帮助B 和先帮助B再帮助A 的总路程是相同的,但先帮助A 可以更快地将1 位老人送入卫生间,从而减少A 的等待时间以及A 和B 的总等待时间,因此智能体决定以CAB 的顺序执行任务.

表4 案例1 中老人的个人信息Table 4 Personal information of the elders in case 1

表5 案例2 中老人的个人信息Table 5 Personal information of the elders in case 2

案例2 中,如图11 所示,以BAC 的顺序帮助老人完成任务将会得到最大的总体满意度.在案例2 中,通过提高B 的舒适运载速度使B 成为了第1 位.因为B 具有较高的舒适运载速度,在被分配更高的速度时,由于速度差造成的不适相比于其他人会更小,且由于B 的舒适速度较高,其被分配的运载速度也会较高,因此先帮助B 进行任务可以适当减小后面2 位老人的等待时间.以上的优势已经大于机器人需要返回C 的房间所造成的劣势,因此智能体决定以BAC 的顺序执行任务.

图11 案例2 中不同任务执行顺序下老人的总体满意度Fig.11 Overall satisfaction of the elderly under different task execution sequences in case 2

表6 案例3 中老人的个人信息Table 6 Personal information of the elders in case 3

图12 案例3 中不同任务执行顺序下老人的个人满意度Fig.12 Personal satisfaction of the elderly under different task execution sequences in case 3

案例3 中,如图13 所示,以ABC 的顺序帮助老人完成任务将会得到最大的总体满意度.在案例3 中,提高了A 的性格急躁程度、舒适运载速度和已等待时间,并降低了其舒适拉起时间和舒适下坐时间,智能体选择接受总路程和总体等待时间的增加而先帮助了A.由于B 距离卫生间较近且舒适运载速度较高,智能体决定以ABC 的顺序执行任务.

图13 案例3 中不同任务执行顺序下老人的总体满意度Fig.13 Overall satisfaction of the elderly under different task execution sequences in case 3

4.2 不同任务种类情况下仿真与分析

现保持机器人初始位置不变(如图6)、人员信息不变(如表4),改变老人所要执行任务种类,观察智能体给出的决策.

如表7 所示,在案例4 中,老人A 想执行 “站起” 任务,老人B 想执行 “去餐厅” 任务,老人C想执行 “去卫生间” 任务.图14,15 分别为案例4中老人的个体与总体满意度,图15 表明以CAB 的顺序帮助老人执行任务会得到最大的回报.因为C的任务优先级最高,需要更快地被执行,且机器人距离C 最近,先帮助C 可以更快地到达其中一位老人的床边,通过减少C 的等待时间来减少3 位老人的总等待时间.当机器人将C 送到卫生间之后,先帮助A 是顺路的,可以减少A 的等待时间以及A 和B 的总等待时间,且A 所执行的任务用时很短,能够很快地完成,不会让下一位老人有很长的等待时间.若先帮助B,由于B 的任务终点是餐厅,再返回帮助A 的话会造成路程的大量增加.因此智能体给出的任务执行顺序是CAB.

图14 案例4 中不同任务执行顺序下老人的个人满意度Fig.14 Personal satisfaction of the elderly under different task execution sequences in case 4

图15 案例4 中不同任务执行顺序下老人的总体满意度Fig.15 Overall satisfaction of the elderly under different task execution sequences in case 4

表7 案例4 中老人的任务信息Table 7 Task information of the elders in case 4

表8 为案例5 中老人的任务需求,图16,17 分别为案例5 中老人的个体与总体满意度,图17 表明以BCA 的顺序帮助老人执行任务可以得到最大的回报.因为B 所要执行任务优先级最高,先帮助B 再返回帮助C 所造成的劣势小于先帮助B 所造成的优势.当机器人将B 送到卫生间后,由于C 的任务用时远小于A 的任务用时,先帮助C 再帮助A 造成的总体等待时间减少的优势大于了先帮助任务优先级更高的A 所造成的优势,因此智能体决定以BCA 的顺序执行任务.

图16 案例5 中不同任务执行顺序下老人的个人满意度Fig.16 Personal satisfaction of the elderly under different task execution sequences in case 5

图17 案例5 中不同任务执行顺序下老人的总体满意度Fig.17 Overall satisfaction of the elderly under different task execution sequences in case 5

表8 案例5 中老人的任务信息Table 8 Task information of the elders in case 5

表9 为案例6 中老人的任务需求,图18,19 分别为案例6 中老人的个体与总体满意度,图19 表明以ABC 的顺序帮助老人执行任务可以得到最大的回报.从案例4、5、6 的结果可以看出:当其他条件不变时,优先级高的任务往往能被更早地执行,在真实情况中,这样的结果也是较为合理的.

图18 案例6 中不同任务执行顺序下老人的个人满意度Fig.18 Personal satisfaction of the elderly under different task execution sequences in case 6

图19 案例6 中不同任务执行顺序下老人的总体满意度Fig.19 Overall satisfaction of the elderly under different task execution sequences in case 6

表9 案例6 中老人的任务信息Table 9 Task information of the elders in case 6

4.3 随机情况下仿真与分析

现随意改变机器人初始位置信息、老人所执行的任务种类以及老人的个人信息来观察智能体给出的决策.

案例7 中,机器人的初始位置如图20 所示,老人的个人信息如表10 所示,老人的任务需求如表11所示,图21,22 分别为案例7 中老人的个体与总体满意度.图22 表明以CAB 的顺序帮助老人执行任务可以得到最大的回报.由于A 和C 的任务紧急程度都为最高级别,C 的性格急躁程度和已等待时间均高于A,再加之C 的舒适运载速度与舒适拉起和下坐时间均比A 更具优势,这些优势战胜了先帮助C 所造成的总体等待时间增加的劣势,因此智能体选择先帮助C.另一方面,当机器人将C 送入卫生间后,A 在任务优先级、地理位置、任务执行所需时间以及舒适运载速度这些方面均具有优势,B 的性格急躁程度较高,但不足以战胜A,因此智能体给出的任务执行顺序是CAB.

表10 案例7 中老人的个人信息Table 10 Personal information of the elders in case 7

表11 案例7 中老人的任务信息Table 11 Task information of the elders in case 7

图20 案例7 中机器人初始位置Fig.20 Initial position of the robots in case 7

图21 案例7 中不同任务执行顺序下老人的个人满意度Fig.21 Personal satisfaction of the elderly under different task execution sequences in case 7

图22 案例7 中不同任务执行顺序下老人的总体满意度Fig.22 Overall satisfaction of the elderly under different task execution sequences in case 7

案例8 中,机器人的初始位置如图23 所示,老人的个人信息如表12 所示,老人的任务需求如表13所示,图24,25 分别为案例8 中老人的个体与总体满意度.图25 表明以CBA 的顺序帮助老人执行任务可以得到最大的回报.在该案例中,C 的任务优先级、性格急躁程度以及舒适运载速度均具有很大优势,因此C 成为了第1 名.B 的舒适运载速度、舒适拉起时间以及任务执行所需时间均具有优势,这些优势战胜了A 的已等待时间所造成的满意度下降,且A 的任务地点较远,若先帮助A 会增加老人们的总体等待时间,因此智能体给出的任务执行顺序是CBA.

图23 案例8 中机器人初始位置Fig.23 Initial position of the robots in case 8

表12 案例8 中老人的个人信息Table 12 Personal information of the elders in case 8

表13 案例8 中老人的任务信息Table 13 Task information of the elders in case 8

图24 案例8 中不同任务执行顺序下老人的个人满意度Fig.24 Personal satisfaction of the elderly under different task execution sequences in case 8

图25 案例8 中不同任务执行顺序下老人的总体满意度Fig.25 Overall satisfaction of the elderly under different task execution sequences in case 8

案例9 中,机器人的初始位置如图26 所示,老人的个人信息如表14 所示,老人的任务需求如表15所示,图27,28 分别为案例9 中老人的个体与总体满意度.图28 表明以ABC 的顺序帮助老人执行任务可以得到最大的回报.在该案例中,A 的任务优先级最高,且A 在任务很紧急的情况下有着较长的已等待时间,这是智能体最不能接受的情况,因此智能体选择让机器人先帮助A.对于B 和C,机器人将A 送到卫生间后,先帮助B 再帮助C 是顺路的,且B 在性格急躁程度、舒适运载速度以及任务所需时间这些方面都具有优势,加之C 所要执行的“去餐厅” 任务受等待时间影响所造成的满意度下降不是非常明显,因此智能体给出的任务执行顺序是ABC.

图26 案例9 中机器人初始位置Fig.26 Initial position of the robots in case 9

表14 案例9 中老人的个人信息Table 14 Personal information of the elders in case 9

表15 案例9 中老人的任务信息Table 15 Task information of the elders in case 9

图27 案例9 中不同任务执行顺序下老人的个人满意度Fig.27 Personal satisfaction of the elderly under different task execution sequences in case 9

图28 案例9 中不同任务执行顺序下老人的总体满意度Fig.28 Overall satisfaction of the elderly under different task execution sequences in case 9

在案例1、2、3 中,使3 位老人同时执行 “去卫生间” 任务,保持机器人初始位置不变,改变老人们的个人信息来观察智能体给出的决策.案例1 中,由于3 位老人的个人信息相同,因此智能体根据3位老人的地理位置给出了最优的任务执行顺序CAB.案例2 中,B 的舒适运载速度增加了0.4 m/s,这导致B 可以以更快的速度执行任务、减少总体等待时间以及减少速度差造成的满意度下降,这些优势大于了需要返回帮助C 造成的路程增加和总体等待时间增加,因此智能体给出的任务执行顺序是BAC.案例3 中,为使A 成为第1 名,需要大幅度增加A 的优势,因为先帮助A 将造成很多路程和总体等待时间的增加.因此在A 的性格急躁程度增加0.3、舒适运载速度增加0.7 m/s、舒适拉起时间减少2 s、舒适下坐时间减少2 s、已等待时间增加15 s 后,智能体终于将A 排到了第1 名.这是在A的优势已经远远大于其他人之后智能体不得不做出的决定.可以看出,在案例1、2、3 中智能体给出的决策是较为合理的.在案例4、5、6 中,保持机器人初始位置和老人个人信息不变,通过改变老人所要执行任务种类来观察智能体给出的决策.案例4 中,C 执行 “去卫生间” 任务,由于该任务优先级最高且机器人距离C 最近,因此C 被排在的第1 名.A与B 的任务优先级均较低,虽然B 的任务 “去餐厅”的优先级较A 的任务 “站起” 高1 级,但A 的地理位置较好且任务耗时较短,因此智能体在权衡后给出了CAB 的任务执行顺序.案例5 中,B 执行 “去卫生间”任务,虽然C 距离机器人最近且其任务“站起” 耗时较短,但由于B 的任务紧急,因此B 被排在第1 名.A 的任务 “去餐厅” 的优先级略高于C,但C 具有较短的任务执行时间,智能体经过权衡后给出了BCA 的任务执行顺序.案例6 中,虽然A 距离机器人最远,但由于A “去卫生间” 的任务具有最高的优先级,智能体选择冒着增加总路程和总等待时间的风险将A 排在第1 名.机器人将A 送入卫生间后,由于先帮助B 是顺路的且B 的“站起” 任务耗时非常短,因此智能体给出的任务执行顺序是ABC.由案例4、5、6 可以看出,在面对非常紧急的任务时,智能体不会被其他较小的优势所影响,而是坚持先帮助任务优先级有绝对优势的老人.案例7、8、9 中,同时改变机器人初始位置信息、老人所执行的任务种类以及老人的个人信息来观察智能体给出的决策.由于这3 个案例中的变量较多,智能体给出的决策是否是最合理的,以人的主观意识无法准确判断.需要通过实验对象的满意度反馈不断地调整满意度模型中的各项参数,从而使智能体的决策越来越合理,最终达到能够满足绝大部分人需求的程度.

真实情况中,往往不会有如此多的冲突出现.一般情况下,老人提出需求后,智能体结合老人的个人信息对其任务进行规划并派出合适的机器人,然后机器人便可依据该规划按照STdCPN 模型帮助老人完成任务.当多个任务冲突时,智能体会给出当前时刻最佳的任务执行顺序,并按照该顺序执行老人的任务.而在这些任务按照该顺序完成之前,有极大的可能会有其他机器人重新回到空闲状态,也有可能会有新的老人加入到队列中,此时智能体会根据新的系统状态来重新规划系统中的任务.

5 结论

本文为解决养老院情境下多个异构服务机器人照顾多位老人的建模问题,结合时延Petri 网与颜色Petri 网并加以改进提出了一种可扩展时延-颜色Petri 网(STdCPN),并使用STdCPN 对养老院情境下多个异构服务机器人照顾多位老人的过程进行建模.STdCPN 的特点是可以在不改变网络结构的基础上随时调整系统中资源的种类(不仅限于数量),应用于养老院情境中,既可以增减老人和机器人的数量(该情境中,由于老人和机器人都携带着各自的信息,因此数量的增加即是种类的增加)也可以对老人的任务执行权限加以限制.为保证任务过程中老人的满意度,提出了基于养老院情境的服务对象满意度模型.该模型考虑老人的性格急躁程度、已等待时间、机器人运载速度与老人舒适速度之差以及老人所要执行任务种类等因素来评估老人的满意度,该满意度将作为系统中任务完成情况的重要指标.设计了智能体作为该协调框架的 “调度者”.当老人提出任务需求后,智能体根据机器人的实时状态、位置等信息派出合适的机器人执行任务,并根据老人的 “个人因素” 结合满意度模型对老人的任务过程进行个性化的规划,机器人将按照该规划以及对应的STdCPN 模型执行任务.当多个任务冲突时,智能体会对所有的任务执行方案进行预测,选出能够使得老人总体满意度最大的任务执行方案来执行.对该协调框架进行了仿真.通过仿真结果可以看出,在仅改变老人个人信息和仅改变老人任务种类这两种情况下,智能体均能给出较为合理的决策.在同时改变老人个人信息、老人任务种类以及机器人初始位置的情况下,智能体的决策仍具有其合理性.本文接下来的工作,将搭建基于VR虚拟场景和生理信号采集的满意度获取系统.通过实验对象的满意度反馈不断地调整满意度模型中的各项参数,从而使智能体的决策更加合理,使该协调框架更好的应用于养老院情境.

附录

在STdCPN 中,由于映射在有向弧F上的权重可以是矩阵,且该模型中含有多达60 个有向弧,同时权重只由 “0”或 “1” 组成,因此,为方便表示,现用一种简化的方式来描述权重.每项权重由两部分组成,第1 部分为权重的 “行数×列数”,第2 部分为该权重中所有 “1”的坐标,其余未标出的坐标均为 “0”.例如,[4×8,((1,1),(2,2),(3,3),(4,4))] 与

对应.则权函数W如式(A8)所示.

该STCPN 子模型的运行过程如下:当库所p1内的老人产生去卫生间的需求时,他会对机器人进行呼叫(通过遥控器或语音控制等方式,即变迁t1触发),随即该老人进入一个虚拟的 “等待区” (p4).这时系统判断该任务所需机器人是否处于空闲状态(p2和p3).如果该任务对应的机器人(一个或多个)不全处于空闲状态 (即变迁t2的触发条件不满足,无法触发),则老人继续在 “等待区” 内等候,直到有所需机器人重回空闲状态;如果有对应机器人处于空闲状态,则派出对应机器人(变迁t2触发),SR 和CR 赶往老人的床位,p2内的SR 和p3内的CR 随即消失(退出 “空闲” 状态),同时老人由在 “等待区” 内等待的状态 (p4) 进入到 “等待机器人到来” 的状态(p5).机器人就位的瞬间,变迁t3触发,系统进入 “老人准备” 状态(p6).待老人准备好之后,变迁(t4)触发,步行支援机开始将老人拉起,系统进入 “老人正在被拉起” 的状态(p7).在拉起动作结束的瞬间t5触发,系统进入到SR 与CR 对接的状态(p8).对接完成后t6触发,SR 开始搀扶老人下坐到CR 上,系统进入 “老人正在下坐”的状态(p9).动作完成后t7触发,老人坐在CR 上(p10).随即变迁t8触发,CR 载着老人进入行驶状态(p11),此时SR 需跟随CR 以帮助老人完成之后的动作,当该状态结束时,CR 已载着老人到达目的地且两机器人已调整好位姿.随即变迁t9触发,系统进入 “老人准备” 的状态(p12),老人准备好之后变迁t10触发,SR 再次对老人进行拉起(p13),该动作完成后t11触发,SR 带着老人调整位姿(p14),同时本次任务中CR 的所有动作已完成,CR 回到空闲状态(p3),重新在p3中出现.老人的任务继续进行,SR 调整好后t12触发,SR 搀扶老人坐到马桶上(p15).该动作完成后t13触发,老人坐在马桶上(p16),同时SR 的所有动作完成,回到 “空闲” 状态(p2).此时 “去卫生间” 任务完成,当老人需要返回床位时,他将再次提出需求,重新进入到虚拟的 “等待区”(p17).

W:F→{[4×8,((1,1),(2,2),(3,3),(4,4))],[2×8,((1,5),(2,6))],[2×8,((1,5),(2,6))],[2×8,((1,7),(2,8))],[2×8,((1,7),(2,8))],[4×8,((1,1),(2,2),(3,3),(4,4))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6))],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6))],[4×8,((1,1),(2,2),(3,3),(4,4))],[4×8,((1,1),(2,2),(3,3),(4,4))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[4×8,((1,1),(2,2),(3,3),(4,4))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[2×8,((1,7),(2,8))],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[2×8,((1,7),(2,8))],[4×8,((1,1),(2,2),(3,3),(4,4))],[4×8,((1,1),(2,2),(3,3),(4,4))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[16×8,((1,1),(1,5),(1,7),(2,1),(2,5),(2,8),(3,1),(3,6),(3,7),(4,1),(4,6),(4,8),(5,2),(5,5),(5,7),(6,2),(6,5),(6,8),(7,2),(7,6),(7,7),(8,2),(8,6),(8,8),(9,3),(9,5),(9,7),(10,3),(10,5),(10,8),(11,3),(11,6),(11,7),(12,3),(12,6),(12,8),(13,4),(13,5),(13,7),(14,4),(14,5),(14,8),(15,4),(15,6),(15,7),(16,4),(16,6),(16,8))],[2×8,((1,7),(2,8))],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[8×8,((1,1),(1,5),(2,1),(2,6),(3,2),(3,5)),(4,2),(4,6),(5,3),(5,5),(6,3),(6,6),(7,4),(7,5),(8,4),(8,6)],[4×8,((1,1),(2,2),(3,3),(4,4))],[2×8,((1,5),(2,6))]} (A8)