智能體Petri 網(wǎng)融合的多機(jī)器人-多任務(wù)協(xié)調(diào)框架

李 勇 李坤成 孫柏青 張秋豪 王義娜 楊俊友

在照顧失能老人時(shí)需要花費(fèi)大量的人力,像養(yǎng)老院這樣的場(chǎng)所,需要大量的人力資源來(lái)完成這項(xiàng)工作.隨著老齡化的發(fā)展[1]以及人工成本的不斷上漲,這個(gè)問(wèn)題會(huì)愈加凸顯.機(jī)器人技術(shù)的發(fā)展使得一些服務(wù)型機(jī)器人已經(jīng)能夠在一定程度上幫助人們完成對(duì)老人日常生活起居和康復(fù)訓(xùn)練等活動(dòng)的照顧.因此,使用服務(wù)型機(jī)器人來(lái)對(duì)老人進(jìn)行照顧將會(huì)成為一個(gè)必然趨勢(shì).而面對(duì)一定數(shù)量的、功能不盡相同的服務(wù)型機(jī)器人,如何讓它們能夠協(xié)同起來(lái)幫助老人完成任務(wù)并保證該過(guò)程中老人的滿意度就成為了一個(gè)必須要解決的問(wèn)題.

Petri 網(wǎng)[2]是一種離散并行系統(tǒng)的數(shù)學(xué)描述方法,于20 世紀(jì)60 年代由卡爾·A·佩特里提出.它既有嚴(yán)格的數(shù)學(xué)表述方式,也有直觀的圖形表達(dá)形式,因其便于描述系統(tǒng)中進(jìn)程或部件的順序、并發(fā)、沖突以及同步等關(guān)系,Petri 網(wǎng)在多機(jī)器人系統(tǒng)的研究中一直占有一席之地.文獻(xiàn)[3]提出了一個(gè)機(jī)器人軟件系統(tǒng)的編程框架,使用信號(hào)解釋Petri 網(wǎng)來(lái)描述任務(wù)并將其存儲(chǔ)在XML 文件中,調(diào)度器加載這些文件并根據(jù)需要執(zhí)行不同的Petri 網(wǎng).文獻(xiàn)[4]提出了一種基于Petri 網(wǎng)的新型表示框架,用于描述單機(jī)器人和多機(jī)器人行為,該框架形式上允許對(duì)編程認(rèn)知機(jī)器人所必需的復(fù)雜動(dòng)作交互進(jìn)行高級(jí)描述.以上兩篇文獻(xiàn)均使用Petri 網(wǎng)對(duì)機(jī)器人的任務(wù)過(guò)程以及動(dòng)作交互進(jìn)行建模,由于機(jī)器人的操作對(duì)象與本文不同,二者僅對(duì)系統(tǒng)中機(jī)器人的狀態(tài)以及動(dòng)作進(jìn)行描述,缺少被操作對(duì)象的狀態(tài)以及機(jī)器人與被操作對(duì)象之間的交互過(guò)程,機(jī)器人相當(dāng)于脫離了整個(gè)系統(tǒng)獨(dú)自進(jìn)行任務(wù).

本文意在協(xié)調(diào)異構(gòu)的服務(wù)機(jī)器人團(tuán)隊(duì)為老人服務(wù),因此本文所建立的模型中既包含機(jī)器人的狀態(tài)以及動(dòng)作流程,也包含被操作對(duì)象的狀態(tài)以及機(jī)器人與被操作對(duì)象之間的交互過(guò)程.由于養(yǎng)老院情境的特殊性,為了清晰地描述系統(tǒng)狀態(tài),需要使用含有時(shí)間因素的Petri 網(wǎng)以及顏色Petri 網(wǎng)來(lái)對(duì)系統(tǒng)進(jìn)行建模.例如,時(shí)延Petri 網(wǎng)所提供的時(shí)間信息可對(duì)系統(tǒng)的狀態(tài)進(jìn)行時(shí)間上的預(yù)測(cè),比如計(jì)算老人完成任務(wù)需要的大致時(shí)間、判斷機(jī)器人何時(shí)回到空閑狀態(tài)等;顏色Petri 網(wǎng)可以對(duì)系統(tǒng)中不同的 “資源”進(jìn)行分類,即實(shí)現(xiàn)對(duì)網(wǎng)系統(tǒng)的折疊,從而更清晰地描述多個(gè)機(jī)器人和多位老人情況下的協(xié)調(diào)過(guò)程.即便如此,在使用Petri 網(wǎng)對(duì)養(yǎng)老院情境進(jìn)行建模時(shí)仍無(wú)法解決 “老人們各行其道互不干擾” 以及 “隨時(shí)調(diào)整老人對(duì)任務(wù)的執(zhí)行權(quán)限” 等問(wèn)題.因此,為解決以上問(wèn)題,本文結(jié)合時(shí)延Petri 網(wǎng)和顏色Petri網(wǎng)提出了一種改進(jìn)的Petri 網(wǎng)—可擴(kuò)展時(shí)延-顏色Petri網(wǎng)(STdCPN)對(duì)養(yǎng)老院情境下機(jī)器人照顧老人的過(guò)程進(jìn)行建模.但本文的研究?jī)?nèi)容不限于此,構(gòu)建的STdCPN 模型將作為多機(jī)器人-多任務(wù)協(xié)調(diào)框架的基礎(chǔ),而如何在任務(wù)過(guò)程中提高被服務(wù)對(duì)象的滿意度是本文的另一個(gè)重點(diǎn).

目前,針對(duì)多機(jī)器人協(xié)調(diào)的研究主要集中在解決多機(jī)器人的任務(wù)分配[5-7]、路徑規(guī)劃[8-9]、編隊(duì)控制[10]、勘探制圖[11-13]等問(wèn)題上,該領(lǐng)域中絕大部分的研究都不涉及 “人的因素”,也不需要考慮協(xié)調(diào)過(guò)程中人的感受和情緒.在機(jī)器人領(lǐng)域中,有少量研究涉及到了最基本的人的安全性.文獻(xiàn)[14]從減少焊接過(guò)程中重型零件的手動(dòng)操作密度的角度來(lái)提高人的安全性.文獻(xiàn)[15-16]從保證機(jī)器人與人之間適當(dāng)?shù)木嚯x的角度來(lái)提高人的安全性.文獻(xiàn)[17]通過(guò)調(diào)節(jié)機(jī)器人與人潛在碰撞期間內(nèi)的沖擊力因素的方法來(lái)提高人的安全性.而機(jī)器人領(lǐng)域中進(jìn)一步考慮人的滿意度的研究甚少.文獻(xiàn)[18]為最大化團(tuán)隊(duì)效率和人類成員與機(jī)器人成員的合作意愿,將任務(wù)分配的權(quán)利交給工人,結(jié)果表明工人寧愿將控制權(quán)交給機(jī)器人,他們寧愿成為高效團(tuán)隊(duì)中的一員,而不是在調(diào)度過(guò)程中發(fā)揮作用.文獻(xiàn)[19]為將人與機(jī)器人之間的相互作用系統(tǒng)化,以減少人的工作量并最大化用戶滿意度,開(kāi)發(fā)了幾種認(rèn)知模型,這些模型可以根據(jù)任務(wù)來(lái)管理和啟動(dòng)交互,并通過(guò)使用交互結(jié)果修改機(jī)器人的活動(dòng).以上兩篇文獻(xiàn)分別從賦予人機(jī)混合團(tuán)隊(duì)中人一定的決策權(quán)和調(diào)整人機(jī)交互中人的工作量的角度來(lái)提高人的滿意度.而本文完全將人類作為被服務(wù)的對(duì)象,從服務(wù)對(duì)象的角度出發(fā),提出了服務(wù)對(duì)象滿意度模型.將老人的滿意度作為任務(wù)執(zhí)行情況的一個(gè)重要指標(biāo),在協(xié)調(diào)多個(gè)機(jī)器人為多位老人服務(wù)的基礎(chǔ)上,通過(guò)調(diào)整機(jī)器人在任務(wù)執(zhí)行過(guò)程中的各項(xiàng)參數(shù)以及多個(gè)任務(wù)沖突時(shí)的任務(wù)執(zhí)行順序來(lái)最大化老人的總體滿意度.

由于養(yǎng)老院中環(huán)境復(fù)雜,其中老人的身體情況、個(gè)人偏好、床位位置等都各不相同,需要根據(jù)老人的 “個(gè)人因素” (即性格急躁程度、被機(jī)器人拉起時(shí)的舒適速度、被機(jī)器人運(yùn)載時(shí)的舒適速度、當(dāng)前所處位置、自提出需求后的已等待時(shí)間以及所執(zhí)行任務(wù)的優(yōu)先級(jí)等)來(lái)對(duì)任務(wù)進(jìn)行個(gè)性化的規(guī)劃,同時(shí)需要根據(jù)各個(gè)機(jī)器人的實(shí)時(shí)狀態(tài)、位置等信息來(lái)合理地分配系統(tǒng)資源.面對(duì)這些靈活的決策,智能體是一個(gè)合適的選擇.文獻(xiàn)[20]提出了一種自動(dòng)建議智能體,該智能體通過(guò)分析系統(tǒng)當(dāng)前狀態(tài),對(duì)系統(tǒng)接下來(lái)所有可執(zhí)行動(dòng)作的 “回報(bào)” 進(jìn)行預(yù)測(cè),然后找出 “回報(bào)” 最大的一種決策提供給人類操作員,從而提高系統(tǒng)效率并減輕人類操作員的工作負(fù)荷.但該文中機(jī)器人的操作對(duì)象是貨架,并不涉及人的滿意度,且使用該方法將帶來(lái)巨大的計(jì)算負(fù)荷,因此一般情況下該智能體僅考慮系統(tǒng)接下來(lái)3 步之內(nèi)的狀態(tài)來(lái)計(jì)算得出當(dāng)前時(shí)刻的最佳決策.

而養(yǎng)老院情境中雖然任務(wù)種類繁雜,但每個(gè)任務(wù)的流程是大致固定的,因此對(duì)系統(tǒng)中任意時(shí)刻所有機(jī)器人可執(zhí)行的每個(gè)動(dòng)作的 “回報(bào)” 進(jìn)行預(yù)測(cè)是不必要的,且在執(zhí)行如 “送老人去衛(wèi)生間” 這樣比較緊急的任務(wù)時(shí),僅能預(yù)測(cè)系統(tǒng)接下來(lái)幾步的狀態(tài)是不能接受的.相反,在該情境下更加需要的是對(duì)機(jī)器人的任務(wù)執(zhí)行過(guò)程有一個(gè)宏觀的規(guī)劃,這正是Petri 網(wǎng)的優(yōu)勢(shì)所在.因此本文使用STdCPN 對(duì)系統(tǒng)底層的運(yùn)行情況進(jìn)行建模,智能體只在必要時(shí)給出決策,這樣就同時(shí)發(fā)揮了Petri 網(wǎng)的宏觀規(guī)劃能力和智能體的靈活決策能力,在協(xié)調(diào)多個(gè)機(jī)器人為多位老人服務(wù)的基礎(chǔ)上,保持了系統(tǒng)的實(shí)時(shí)性.

本文結(jié)合時(shí)延Petri 網(wǎng)和顏色Petri 網(wǎng)提出了可擴(kuò)展時(shí)延-顏色Petri 網(wǎng)(STdCPN)并對(duì)養(yǎng)老院情境下服務(wù)機(jī)器人團(tuán)隊(duì)照顧老人的過(guò)程進(jìn)行建模.為提高該過(guò)程中老人即機(jī)器人所服務(wù)對(duì)象的滿意度,提出了服務(wù)對(duì)象滿意度模型,將老人的滿意度作為任務(wù)完成情況的重要指標(biāo).設(shè)計(jì)了智能體對(duì)該協(xié)調(diào)框架進(jìn)行調(diào)度,該智能體對(duì)老人的任務(wù)進(jìn)行個(gè)性化的規(guī)劃,合理分配系統(tǒng)資源,最大化老人總體滿意度.

本文內(nèi)容安排如下:第1 節(jié)介紹了STdCPN 子模型,并以此模型為例對(duì)改進(jìn)的Petri 網(wǎng)—STd-CPN 進(jìn)行詳細(xì)闡述;第2 節(jié)建立了服務(wù)對(duì)象滿意度模型;第3 節(jié)提出了基于智能體的協(xié)調(diào)框架;第4節(jié)對(duì)不同情況下智能體的決策進(jìn)行仿真與分析;第5 節(jié)為結(jié)論.

1 養(yǎng)老院情境下基于STdCPN 的任務(wù)建模

要完成養(yǎng)老院情境下多個(gè)服務(wù)型機(jī)器人照顧多位老人的協(xié)調(diào),對(duì)機(jī)器人照顧老人的過(guò)程進(jìn)行建模是基礎(chǔ).由于養(yǎng)老院中任務(wù)復(fù)雜多樣,因此應(yīng)先對(duì)其中一個(gè)或相聯(lián)系的幾個(gè)任務(wù)進(jìn)行子模型構(gòu)建,之后便可根據(jù)該子模型推演出其他子模型,并根據(jù)實(shí)際需要將它們組合成完整的模型.現(xiàn)以機(jī)器人送老人去衛(wèi)生間以及送回這兩個(gè)相聯(lián)系的任務(wù)為例,進(jìn)行STdCPN 子模型搭建,并以此模型為例對(duì)STdCPN進(jìn)行闡述.為說(shuō)明該模型在多機(jī)器人多人情況下模擬能力的同時(shí)方便描述,令該模型中包含老人4 位、步行支援機(jī)器人2 臺(tái)(記為SR,如圖1 (a)所示,其主要功能是攙扶老人站起、坐下和移動(dòng))、智能輪椅機(jī)器人2 臺(tái)(記為CR,如圖1 (b)所示,其主要功能是運(yùn)載老人從起始點(diǎn)到達(dá)目的地),構(gòu)建的STdCPN 子模型如圖2 所示.

圖1 送老人去衛(wèi)生間及送回過(guò)程中使用的機(jī)器人Fig.1 Robots for send the elderly to the toilet and return

圖2 SR 和CR 協(xié)同送老人去衛(wèi)生間及送回STdCPN 模型Fig.2 STdCPN model for SR and CR work together to send the elderly to the toilet and return

該模型中p1到p16為SR 與CR 協(xié)同將老人從床位送到衛(wèi)生間的過(guò)程,p16到p1為SR 與CR 協(xié)同將老人從衛(wèi)生間送回到床位的過(guò)程,這兩個(gè)過(guò)程是不同的任務(wù),即老人被送到衛(wèi)生間后任務(wù)結(jié)束,經(jīng)過(guò)不定長(zhǎng)的時(shí)間后,當(dāng)老人想要返回時(shí),需要再次提出需求.該STdCPN 模型的具體數(shù)學(xué)表達(dá)式及運(yùn)行過(guò)程見(jiàn)附錄A.模型中庫(kù)所的含義如表1 所示,變遷的含義如表2 所示.

表1 送老人去衛(wèi)生間及送回STdCPN 模型中庫(kù)所含義Table 1 The mean of spaces in the STdCPN model of send the elderly to the toilet and return

表2 送老人去衛(wèi)生間及送回STdCPN 模型中變遷含義Table 2 The mean of transitions in the STdCPN model of send the elderly to the toilet and return

可擴(kuò)展時(shí)延-顏色Petri 網(wǎng)是一個(gè)七元組,STdCPN=(P,T;F,D,C,W,M0),其中:P={p1,p2,···,pm}是庫(kù)所的有限集,表示系統(tǒng)的資源、操作或狀態(tài)等,當(dāng)庫(kù)所p內(nèi)含有令牌時(shí),庫(kù)所p代表的意義生效;T={t1,t2,···,tn} 是變遷的有限集,代表系統(tǒng)狀態(tài)間的轉(zhuǎn)換,當(dāng)變遷t的每個(gè)輸入庫(kù)所中的令牌量都大于等于該庫(kù)所與變遷t間的權(quán)重時(shí),變遷t可以觸發(fā),t的觸發(fā)會(huì)從每個(gè)輸入庫(kù)所中移除對(duì)應(yīng)權(quán)重的令牌量,并在每個(gè)輸出庫(kù)所中生成對(duì)應(yīng)權(quán)重的令牌量;F?(P×T)∪(T×P) 是有向弧的有限集,連接庫(kù)所與變遷;D是時(shí)延Petri 網(wǎng)中的概念,是定義在庫(kù)所集P上的時(shí)間函數(shù),即當(dāng)令牌進(jìn)入某一庫(kù)所后,需要停留該庫(kù)所時(shí)延量的時(shí)間才可以離開(kāi)該庫(kù)所;C={c1,c2,···,ck} 是顏色Petri網(wǎng)中的概念,是顏色的有限集,表示系統(tǒng)中資源的種類,當(dāng)顏色集的維度改變后,系統(tǒng)中的令牌和權(quán)重等的維度都需要相應(yīng)的改變;W是映射在有向弧集上的權(quán)函數(shù),控制著變遷的發(fā)生規(guī)則;M0是映射在庫(kù)所集上的初始標(biāo)識(shí),表示系統(tǒng)的初始狀態(tài).

STdCPN 模型利用庫(kù)所上的時(shí)延量對(duì)系統(tǒng)狀態(tài)進(jìn)行時(shí)間上的預(yù)測(cè),STdCPN 的時(shí)延量D不同于傳統(tǒng)的附著于變遷上的時(shí)延量,而是附著于庫(kù)所之上.如果將時(shí)延量附著于變遷之上,由于標(biāo)識(shí)M映射在庫(kù)所上,當(dāng)變遷正在發(fā)生時(shí),它的前集中的令牌會(huì)消失,而后集中的令牌需要等到變遷結(jié)束后才會(huì)出現(xiàn),因此系統(tǒng)此刻的狀態(tài)無(wú)法明確表示,而將時(shí)延量附著于庫(kù)所之上,使所有變遷的時(shí)延量為零,則可以準(zhǔn)確地通過(guò)標(biāo)識(shí)描述系統(tǒng)任意時(shí)刻所處狀態(tài).

在該模型的時(shí)延因素D中,d為由傳感器實(shí)時(shí)采回的機(jī)器人位置信息計(jì)算得出的機(jī)器人與老人床位間的路徑長(zhǎng)度,若任務(wù)所需機(jī)器人數(shù)量大于1,則d取其中最大值,vmax為機(jī)器人的最大移動(dòng)速度,v為老人被分配的CR 運(yùn)載速度,tup為預(yù)設(shè)的機(jī)器人以老人舒適速度攙扶老人站起所用時(shí)間,tdown為預(yù)設(shè)的機(jī)器人以老人舒適速度攙扶老人坐下所用時(shí)間,m為老人床位與衛(wèi)生間內(nèi)馬桶之間的路徑長(zhǎng)度,含有以上量的各項(xiàng)時(shí)延量均是確定的.含有 “x”的時(shí)延量代表該時(shí)間具有不確定性,x1為老人在床位上停留的時(shí)間,x16為老人如廁的時(shí)間,這2 項(xiàng)時(shí)間取決于老人的實(shí)際需求.x2為SR 保持 “空閑狀態(tài)” 的時(shí)間,x3為CR 保持 “空閑狀態(tài)” 的時(shí)間,這2 項(xiàng)時(shí)間取決于實(shí)際情況下機(jī)器人的使用情況.x4和x17為從老人呼叫后至機(jī)器人響應(yīng)請(qǐng)求的用時(shí),這2 項(xiàng)時(shí)間取決于實(shí)際情況下機(jī)器人的使用情況以及智能體對(duì)機(jī)器人資源的分配情況.以上6 項(xiàng)時(shí)延量對(duì)應(yīng)的6 個(gè)庫(kù)所均處于任務(wù)開(kāi)始之前,因此該6 項(xiàng)具有不確定性的時(shí)延量對(duì)系統(tǒng)狀態(tài)的預(yù)測(cè)沒(méi)有影響.x6、x12、x19和x25為SR 拉起老人之前老人的準(zhǔn)備時(shí)間,x8和x21為SR 與CR 對(duì)接的時(shí)間,x14為SR 與馬桶的對(duì)接時(shí)間,x27為SR 與床位的對(duì)接時(shí)間,這8 項(xiàng)時(shí)延量會(huì)受到老人個(gè)人情況的影響,但在實(shí)際應(yīng)用中可以測(cè)出一個(gè)大致的值.這些時(shí)延量將僅做預(yù)測(cè)使用,實(shí)際以機(jī)器人每次完成動(dòng)作后傳回的信號(hào)為準(zhǔn),機(jī)器人每完成一個(gè)動(dòng)作STdCPN 模型即可向前運(yùn)行一步并為機(jī)器人指明下一步動(dòng)作,同時(shí)刷新預(yù)測(cè)時(shí)間,這樣就可以利用時(shí)延量對(duì)系統(tǒng)的狀態(tài)進(jìn)行預(yù)測(cè).例如在老人出發(fā)后,可以預(yù)測(cè)老人距某一狀態(tài)的大致時(shí)間,也可以預(yù)測(cè)大致多久后老人可以完成任務(wù)以及機(jī)器人何時(shí)可以回到空閑狀態(tài)等.這些時(shí)間信息可以提供給智能體,作為多機(jī)器人-多任務(wù)規(guī)劃的依據(jù).

可靈活地對(duì)系統(tǒng)規(guī)模和系統(tǒng)中相同種類資源的數(shù)量進(jìn)行擴(kuò)展而不影響已搭建好的模型結(jié)構(gòu)是Petri 網(wǎng)具備的特點(diǎn).由于養(yǎng)老院這一系統(tǒng)的特殊性,其內(nèi)所有任務(wù)的運(yùn)行均是以被服務(wù)對(duì)象即老人為中心展開(kāi)的,且各對(duì)象之間互不干擾,同時(shí)由于養(yǎng)老院的人員流動(dòng)性以及不同養(yǎng)老院的機(jī)器人數(shù)量可能不同,因此構(gòu)建的模型要能夠隨時(shí)調(diào)整資源種類,適應(yīng)于不同的老人與機(jī)器人的組合.因此可擴(kuò)展時(shí)延-顏色Petri 網(wǎng)的 “可擴(kuò)展” 指的是通過(guò)對(duì)權(quán)函數(shù)中各項(xiàng)權(quán)重的 “矩陣化” 使得模型可以在不改變其結(jié)構(gòu)的基礎(chǔ)上任意增減資源種類,隨時(shí)改變各資源對(duì)各子模型的執(zhí)行權(quán)限.

使用傳統(tǒng)的顏色Petri 網(wǎng)對(duì)系統(tǒng)建模時(shí),會(huì)將系統(tǒng)中的 “資源” 進(jìn)行分類,以該STdCPN 模型為例,系統(tǒng)中有4 位老人,2 臺(tái)SR 和2 臺(tái)CR,這8個(gè) “資源”會(huì)被分為3 類,即顏色集C={MAN,SR,CR},令牌、權(quán)函數(shù)W的每項(xiàng)以及標(biāo)識(shí)M的每項(xiàng)都為1 個(gè)三維向量.當(dāng)需要增減老人或機(jī)器人時(shí),僅需改變令牌向量相應(yīng)位的大小;當(dāng)變遷的規(guī)則變化時(shí),權(quán)函數(shù)的改變會(huì)影響一整類 “資源” 的權(quán)限.而在養(yǎng)老院情境中,不能將老人和機(jī)器人視為如同“待加工的零部件”那樣進(jìn)行分類,因?yàn)槊课焕先撕兔颗_(tái)機(jī)器人都攜帶著他們的 “個(gè)人信息”,老人所攜帶的如床位所在位置、性格急躁程度、被機(jī)器人拉起時(shí)的舒適速度、被機(jī)器人運(yùn)載時(shí)的舒適速度、當(dāng)前所處位置、已等待時(shí)間以及所要執(zhí)行任務(wù)種類等信息會(huì)影響智能體對(duì)該老人任務(wù)執(zhí)行過(guò)程的規(guī)劃,機(jī)器人攜帶的如是否處于 “空閑” 狀態(tài)、當(dāng)前所處位置以及該機(jī)器人種類等信息會(huì)影響智能體對(duì)該機(jī)器人的任務(wù)規(guī)劃.因此在養(yǎng)老院情境下,不能將這些 “資源” 進(jìn)行如上的分類,而是要將每位老人和每臺(tái)機(jī)器人都區(qū)分開(kāi),因此需令顏色集C={MAN1,MAN2,MAM3,MAM4,SR1,SR2,CR1,CR2},即每個(gè) “資源” 都是一類獨(dú)特的 “資源”,因此該模型中令牌的每一位只能是0 或者1,當(dāng)增減老人和機(jī)器人時(shí),實(shí)際上都是在增加或者減少 “資源” 的種類,即令牌的維度.同時(shí)也需要權(quán)函數(shù)有能力為增加(減少)的 “資源” 提供(解除)權(quán)限,因此本文在結(jié)合時(shí)延Petri 網(wǎng)和顏色Petri 網(wǎng)的基礎(chǔ)上,改進(jìn)了權(quán)函數(shù)的形式并調(diào)整了網(wǎng)絡(luò)的運(yùn)行規(guī)則.改進(jìn)后的權(quán)函數(shù)映射到有向弧上的每一位權(quán)重可以是向量也可以是矩陣,當(dāng)權(quán)函數(shù)的某位權(quán)重為矩陣時(shí),意味著該權(quán)重的每一行都為變遷的發(fā)生提供了一種可能.附錄A 中給出的權(quán)函數(shù)W基于的條件是4 位老人均可以執(zhí)行該任務(wù)且可以使用任意的SR 與CR 的組合.

使用改進(jìn)權(quán)函數(shù)的STdCPN 運(yùn)行規(guī)則:1) 當(dāng)變遷具有1 個(gè)輸入庫(kù)所和1 個(gè)輸出庫(kù)所時(shí),若變遷輸入庫(kù)所中的令牌不少于輸入庫(kù)所到變遷間權(quán)重的某一行,則變遷有發(fā)生權(quán).變遷發(fā)生后,輸入庫(kù)所中的令牌減去該行權(quán)重生成新令牌,輸出庫(kù)所中的令牌加上變遷到輸出庫(kù)所間權(quán)重對(duì)應(yīng)的同一行,生成新的令牌.2) 當(dāng)變遷具有多個(gè)輸入庫(kù)所和1 個(gè)輸出庫(kù)所時(shí),如果每個(gè)輸入庫(kù)所中的令牌都不少于該輸入庫(kù)所與變遷間權(quán)重中的某一行,則變遷有發(fā)生權(quán).變遷發(fā)生后,這些行權(quán)重相加的結(jié)果等于變遷與輸出庫(kù)所間權(quán)重的哪一行,則輸出庫(kù)所內(nèi)的令牌加上哪一行.3) 當(dāng)變遷具有1 個(gè)輸入庫(kù)所和多個(gè)輸出庫(kù)所時(shí),如果輸入庫(kù)所滿足條件則變遷可以發(fā)生,變遷到多個(gè)輸出庫(kù)所的權(quán)重中,每個(gè)權(quán)重選出一行對(duì)它們求和,哪幾行相加的結(jié)果等于輸入庫(kù)所減去的那一行權(quán)重,則在變遷發(fā)生后將這幾行權(quán)重分別加到對(duì)應(yīng)輸出庫(kù)所的令牌上.

需要強(qiáng)調(diào)的是:1) 由于STdCPN 的權(quán)重為變遷的發(fā)生提供了多種可能,若變遷具有多個(gè)輸入庫(kù)所和多個(gè)輸出庫(kù)所,會(huì)造成變遷發(fā)生時(shí)權(quán)重選擇混亂,因此在使用STdCPN 建模時(shí)應(yīng)避免這種情況的發(fā)生,可以通過(guò)如增加中間庫(kù)所等方式實(shí)現(xiàn).2) 為了使標(biāo)識(shí)可以明確地表示系統(tǒng)當(dāng)前狀態(tài)以及防止老人之間相互影響,當(dāng)多塊令牌處于同一庫(kù)所內(nèi)時(shí),除任務(wù)開(kāi)始前(p1、p4)和結(jié)束后(p16)以及存儲(chǔ)機(jī)器人的庫(kù)所(p2、p3)內(nèi)的令牌可以疊加外,在任務(wù)執(zhí)行過(guò)程中,令牌均不可以疊加,而是按照各自的進(jìn)度前進(jìn).

該STdCPN 子模型建立后,模型的運(yùn)行會(huì)指示SR 和CR 需要完成的動(dòng)作以及它們之間動(dòng)作的順序,從而協(xié)調(diào)2 臺(tái)異構(gòu)的服務(wù)機(jī)器人幫助老人完成任務(wù).通過(guò)該STdCPN 子模型可以清楚地了解任意時(shí)刻系統(tǒng)中每位老人與每臺(tái)機(jī)器人所處的狀態(tài)以及他們間的聯(lián)系,即可以清楚地知道哪一(幾)臺(tái)機(jī)器人正在為哪一位老人服務(wù)到哪一個(gè)階段,這樣就可以對(duì)整個(gè)系統(tǒng)有一個(gè)精準(zhǔn)的把控,并可對(duì)系統(tǒng)狀態(tài)進(jìn)行時(shí)間上的預(yù)測(cè),這些信息都將作為智能體進(jìn)行任務(wù)規(guī)劃時(shí)的依據(jù).且STdCPN 模型的 “可擴(kuò)展性”能夠滿足實(shí)際應(yīng)用中老人和機(jī)器人數(shù)量的擴(kuò)展以及對(duì)他們權(quán)限的限制,由于STdCPN 運(yùn)行過(guò)程中并不涉及似矩陣求逆般耗時(shí)的計(jì)算,因此由老人和機(jī)器人數(shù)量擴(kuò)展導(dǎo)致的模型中向量和矩陣維度的增加對(duì)模型的運(yùn)行不會(huì)造成很大的影響.可以組合多個(gè)STdCPN 子模型來(lái)構(gòu)成完整的養(yǎng)老院運(yùn)行模型,作為養(yǎng)老院情境下多機(jī)器人-多任務(wù)協(xié)調(diào)的基礎(chǔ).

2 服務(wù)對(duì)象滿意度建模

當(dāng)STdCPN 模型搭建完成后,在機(jī)器人資源充足時(shí),老人們均可以按照自己的需求隨時(shí)進(jìn)行各種任務(wù).但在現(xiàn)實(shí)情況中難免會(huì)有短時(shí)間內(nèi)多位老人接連提出需求甚至同時(shí)提出需求的情況,按此情形配置機(jī)器人數(shù)量會(huì)造成大量冗余.但如果機(jī)器人資源不夠充足,系統(tǒng)將陷入僵局.由于每位老人的身體狀況不同,所執(zhí)行的任務(wù)緊急程度也不同,盲目地按照老人提出需求的順序來(lái)執(zhí)行任務(wù)可能會(huì)造成一些不良后果.同時(shí)由于該過(guò)程服務(wù)于人,那么應(yīng)該從人的角度出發(fā)考慮,找出能夠讓老人們整體更滿意的解決方案.因此通過(guò)對(duì)養(yǎng)老院情境的模擬以及該情境下老人心理的分析,提出了如下服務(wù)對(duì)象滿意度模型.在該模型中,將任務(wù)分為不同的優(yōu)先級(jí),并將老人的性格急躁程度分為不同等級(jí).假設(shè)在機(jī)器人幫助老人完成一項(xiàng)任務(wù)后,老人會(huì)根據(jù)此次任務(wù)的執(zhí)行情況得出一個(gè)他心中的滿意度.認(rèn)為在該情境下,任務(wù)的優(yōu)先級(jí)、老人的性格急躁程度、老人呼叫后的等待時(shí)間以及機(jī)器人運(yùn)載老人的速度與老人的舒適速度之差都會(huì)對(duì)老人的滿意度造成影響.建立的滿意度模型如式(1)所示:

式(1)中Satf為老人的滿意度,X代表老人,ex代表該老人要做的事件是事件x,k代表在當(dāng)前隊(duì)列中該老人排在第k位,n代表共有n位老人在隊(duì)列中.Prior代表事件優(yōu)先級(jí),這里將所有事件分成五個(gè)等級(jí),Prior∈{0,1,2,3,4},其中 “4” 為優(yōu)先級(jí)最高的等級(jí).Impat代表老人性格急躁系數(shù),由于目前無(wú)法對(duì)性格急躁程度進(jìn)行定量測(cè)量,假設(shè)性格急躁程度最低的人急躁系數(shù)為 “1.0”,該系數(shù)隨著老人急躁程度的提升而增加,暫定為五個(gè)等級(jí),Impat∈{1.0,1.1,1.2,1.3,1.4},twait為老人從提出需求開(kāi)始直至機(jī)器人到達(dá)老人所在位置之間的總等待時(shí)間,v為老人被分配的運(yùn)載速度,v*為老人預(yù)設(shè)的舒適運(yùn)載速度.

對(duì)于式1 中第1 項(xiàng),假設(shè)高優(yōu)先級(jí)的任務(wù)在完成時(shí)會(huì)得到更大的滿意度;對(duì)于式1 中第2 項(xiàng),假設(shè)性格急躁系數(shù)Impat會(huì)被總等待時(shí)間twait以指數(shù)的形式影響,從而降低老人滿意度;對(duì)于式1 中第3 項(xiàng),假設(shè)機(jī)器人運(yùn)載老人的速度v與老人舒適速度v*之差會(huì)以指數(shù)的形式對(duì)老人的滿意度造成負(fù)面影響.

其中總等待時(shí)間twait由式(2)求得,由預(yù)計(jì)等待時(shí)間tew和已經(jīng)等待時(shí)間taw兩部分構(gòu)成(taw產(chǎn)生原因是:當(dāng)多位老人的任務(wù)產(chǎn)生沖突時(shí),智能體會(huì)給出老人的任務(wù)執(zhí)行順序,當(dāng)按照某種順序執(zhí)行后,在完成所有的任務(wù)之前若有新的老人加入隊(duì)列或有任意種類機(jī)器人重回空閑狀態(tài),則需要重新計(jì)算得出基于當(dāng)前時(shí)刻的任務(wù)執(zhí)行順序,因此需要一個(gè)已經(jīng)等待時(shí)間來(lái)描述老人的真實(shí)等待時(shí)間).

預(yù)計(jì)等待時(shí)間tew由式(3)求得.當(dāng)k=1 時(shí),預(yù)計(jì)等待時(shí)間tew等于所派出機(jī)器人距離老人的初始距離中的最大值d與機(jī)器人最大行駛速度vmax的商;當(dāng) 1＜k ≤n時(shí),預(yù)計(jì)等待時(shí)間tew等于排在該老人前面一位的老人的預(yù)計(jì)等待時(shí)間tew,k-1加上前一位老人的任務(wù)執(zhí)行時(shí)間(包括以老人預(yù)設(shè)的舒適方式將老人拉起的用時(shí)與拉起次數(shù)nup的乘積、以老人預(yù)設(shè)的舒適方式將老人放下的用時(shí)與放下次數(shù)ndown的乘積以及任務(wù)路程m與機(jī)器人運(yùn)載老人速度v的商)再加上機(jī)器人到達(dá)所需用時(shí)dk/vmax.

運(yùn)載速度v由式(4)求得,它等于老人的最舒適速度v*加上該老人的加速系數(shù)a在加速系數(shù)變化范圍(amax－amin)內(nèi)所占比例與該老人運(yùn)載速度最大變化范圍(vmax－v*)的乘積.

加速系數(shù)a由式(5)求得.當(dāng) 1 ≤k＜n時(shí),該老人的加速系數(shù)a等于該老人所執(zhí)行任務(wù)的優(yōu)先級(jí)的平方根加上排在該老人之后所有老人的任務(wù)優(yōu)先級(jí)總和的平方根;當(dāng)k=n時(shí),加速系數(shù)a等于該老人所執(zhí)行任務(wù)的優(yōu)先級(jí)的平方根.

式(6)中Satfm為隊(duì)列中所有老人的總體滿意度,包括所有老人的個(gè)人滿意度之和以及一個(gè)表示“優(yōu)先級(jí)高的任務(wù)被先執(zhí)行”程度的量f(prior1,prior2,···,priorn),其值為每一項(xiàng)分別減去其后各項(xiàng)再對(duì)所有正的結(jié)果求和.這樣做的目的是適當(dāng)提高優(yōu)先級(jí)高的任務(wù)被先執(zhí)行時(shí)的總體滿意度,因?yàn)楝F(xiàn)實(shí)情況中高優(yōu)先級(jí)的任務(wù)往往更緊急,需要優(yōu)先被執(zhí)行.

該滿意度模型建立后,智能體對(duì)系統(tǒng)中的任務(wù)進(jìn)行規(guī)劃時(shí)除了考慮老人和機(jī)器人的實(shí)時(shí)信息外,還會(huì)考慮老人的滿意程度,將滿意程度的高低作為衡量任務(wù)完成情況的一個(gè)指標(biāo),在協(xié)調(diào)多個(gè)機(jī)器人為多位老人服務(wù)的基礎(chǔ)上最大化老人的總體滿意程度.

3 基于智能體的考慮人的因素的協(xié)調(diào)框架

該協(xié)調(diào)框架由STdCPN 模型和智能體兩部分組成,STdCPN 模型作為該協(xié)調(diào)框架的基礎(chǔ),指示機(jī)器人如何協(xié)同完成任務(wù),智能體作為該協(xié)調(diào)框架的 “調(diào)度者”,對(duì)系統(tǒng)資源進(jìn)行分配,并根據(jù)老人的“個(gè)人因素” 對(duì)機(jī)器人的任務(wù)執(zhí)行過(guò)程進(jìn)行規(guī)劃,其結(jié)構(gòu)如圖3 所示.

圖3 基于智能體的考慮人的因素的協(xié)調(diào)框架結(jié)構(gòu)示意圖Fig.3 Diagram of coordination framework considering human factors based on intelligent agent

當(dāng)老人提出任務(wù)需求后,STdCPN 模型的標(biāo)識(shí)會(huì)產(chǎn)生對(duì)應(yīng)變化,智能體根據(jù)STdCPN 模型提供的老人任務(wù)信息結(jié)合老人的個(gè)人信息以及滿意度模型對(duì)老人的任務(wù)過(guò)程進(jìn)行規(guī)劃,并根據(jù)實(shí)時(shí)環(huán)境信息和STdCPN 模型提供的機(jī)器人實(shí)時(shí)狀態(tài)信息派出合適的機(jī)器人,將此方案作為最佳方案輸入到STdCPN 模型中,使機(jī)器人依據(jù)該方案按照STdCPN 模型執(zhí)行任務(wù);當(dāng)多位老人的任務(wù)發(fā)生沖突且機(jī)器人資源不足時(shí),智能體通過(guò)調(diào)整老人的任務(wù)執(zhí)行順序得出多個(gè)任務(wù)執(zhí)行方案,并將這些任務(wù)執(zhí)行方案輸入到STdCPN 模型內(nèi)進(jìn)行模擬運(yùn)行,從而得出計(jì)算滿意度所需的時(shí)間信息,再通過(guò)滿意度模型計(jì)算得出使得總體滿意度最大的任務(wù)執(zhí)行方案(由于目前系統(tǒng)規(guī)模較小,這里暫且使用窮舉法,當(dāng)老人、機(jī)器人和任務(wù)大量增加后,需要使用快速優(yōu)化方法進(jìn)行求解),然后將該方案作為最佳方案輸入到STdCPN 模型中,使機(jī)器人依據(jù)該方案執(zhí)行任務(wù).

以上文搭建的STdCPN 子模型(圖2) 為例,在不限制老人和機(jī)器人的數(shù)量、狀態(tài)的條件下給出該協(xié)調(diào)框架的算法流程圖,如圖4 所示.圖4 相當(dāng)于智能體的 “思維方式” 智能體通過(guò)該 “思維方式”決定當(dāng)前系統(tǒng)中的任務(wù)能否同時(shí)執(zhí)行,如果不能,那么哪(幾)個(gè)任務(wù)應(yīng)該先被執(zhí)行,如果執(zhí)行應(yīng)該派出哪(幾)個(gè)機(jī)器人前往,在拉起和放下該老人時(shí)應(yīng)該以什么樣的速度,在運(yùn)載該老人時(shí)應(yīng)該以什么樣的速度等問(wèn)題.

圖4 基于智能體的考慮人的因素的協(xié)調(diào)框架算法流程圖Fig.4 Algorithm flow chart of coordination framework considering human factors based on intelligent agent

下面對(duì)該協(xié)調(diào)框架的算法流程圖做一些解釋:1) 由于 “等待區(qū)” 內(nèi)新增老人和在 “等待區(qū)” 非空的前提下任意種類機(jī)器人重回空閑狀態(tài)這兩種情況都可能造成有新的具備出發(fā)條件的老人產(chǎn)生,所以每當(dāng)這兩種情況發(fā)生,智能體對(duì)當(dāng)前時(shí)刻系統(tǒng)所處狀態(tài)進(jìn)行判斷.2) “等待區(qū)” 內(nèi)存在多位老人可能是由于先提出需求的老人不具備出發(fā)條件而隨時(shí)間推移不斷有新的老人加入從而堆積造成的,也有可能是多位老人在同一瞬間提出需求造成的.3) 當(dāng)排在第1 位的老人被轉(zhuǎn)移到 “等待機(jī)器人到來(lái)” 狀態(tài)(p5或p18)內(nèi)之后,智能體重新判斷剩下的老人是否具備出發(fā)條件,然后再次對(duì)其中具備出發(fā)條件的老人進(jìn)行排列組合,選出能夠得到最大總體滿意度的出發(fā)順序執(zhí)行.這樣做的原因是:雖然最初多位老人都具備出發(fā)條件,但不同的任務(wù)需要的機(jī)器人種類和數(shù)量可能不同,所以當(dāng)前機(jī)器人的種類和數(shù)量可能滿足一位老人出發(fā),也可能滿足多位老人同時(shí)出發(fā),因此當(dāng)排在第1 位的老人進(jìn)入下一狀態(tài)后,排在第2 位的老人是否依然具備出發(fā)條件不明,同時(shí)也存在排在第2 位的老人不具備出發(fā)條件而排在第3 位的老人具備出發(fā)條件等多種可能,因此智能體需要重新判斷.4) 將 “等待機(jī)器人到來(lái)” 狀態(tài)內(nèi)的老人返回 “等待區(qū)”并將對(duì)應(yīng)機(jī)器人返回 “空閑狀態(tài)”是因?yàn)?“等待機(jī)器人到來(lái)” 狀態(tài)內(nèi)的老人雖然任務(wù)已被規(guī)劃但還未出發(fā),而此時(shí)可能有新的具備出發(fā)條件的老人產(chǎn)生,因此需要根據(jù)這些老人的任務(wù)優(yōu)先級(jí)、個(gè)人信息、機(jī)器人的實(shí)時(shí)狀態(tài)、位置等信息重新規(guī)劃任務(wù)方案.5) 將 “等待機(jī)器人到來(lái)”狀態(tài)內(nèi)的老人返回 “等待區(qū)” 后,不存在沒(méi)有老人具備出發(fā)條件這種情況的原因是:被返回的老人正是因?yàn)榫邆涑霭l(fā)條件才會(huì)存在于 “等待機(jī)器人到來(lái)”狀態(tài)(p5或p18)內(nèi).

4 仿真與分析

對(duì)該協(xié)調(diào)框架進(jìn)行了仿真,現(xiàn)對(duì)多位老人任務(wù)沖突且機(jī)器人資源不充足的情況下智能體給出的決策進(jìn)行分析.

圖5 是一個(gè)模擬的養(yǎng)老院場(chǎng)景平面圖,從北至南分別是衛(wèi)生間、A、B、C、D 4 位老人的房間以及餐廳.為方便計(jì)算,令相鄰房間的門(mén)間距離為3 m,由房間的門(mén)口到老人床邊的距離為3 m.該養(yǎng)老院擁有2 臺(tái)SR (圖5 中三角形)和2 臺(tái)CR (圖5 中矩形),它們可以將老人拉起、放下以及運(yùn)載老人到達(dá)目的地,行駛最大速度vmax為1.2 m/s.假設(shè)該養(yǎng)老院當(dāng)前有3 種任務(wù):從床位去衛(wèi)生間、從床位去餐廳和在機(jī)器人的幫助下站起.表3 為任務(wù)信息.

圖5 養(yǎng)老院模擬場(chǎng)景平面圖Fig.5 Nursing home simulation scene plan

表3 任務(wù)信息Table 3 Task information

4.1 不同個(gè)人信息情況下仿真與分析

考慮第1 種情況,多位老人在機(jī)器人資源不充足的情況下想要完成同一任務(wù).如圖6 所示,假設(shè)當(dāng)前時(shí)刻老人D 占用了1 臺(tái)SR 和1 臺(tái)CR 正在執(zhí)行 “去餐廳” 任務(wù)(圖中未表示),僅剩1 臺(tái)SR 和1 臺(tái)CR 處于空閑狀態(tài)且它們停在老人C 的房間門(mén)前,此時(shí)A、B、C 3 位老人同時(shí)想去衛(wèi)生間,圖7 為這一時(shí)刻的STdCPN 模型.

圖6 機(jī)器人初始位置Fig.6 Initial position of the robots

圖7 中,p1到p41為SR 和CR 幫助老人從床位去餐廳的過(guò)程,p41到p1為SR 和CR 幫助老人從餐廳回到床位的過(guò)程,p1到p16為SR 和CR 幫助老人從床位去衛(wèi)生間的過(guò)程,p16到p1為SR 和CR 幫助老人從衛(wèi)生間回到床位的過(guò)程,p1到p58為SR 幫助老人從坐到站的過(guò)程,p58到p1為SR 幫助老人從站到坐的過(guò)程.庫(kù)所p36代表CR 運(yùn)載老人從床位去餐廳的過(guò)程,其中的令牌[0,0,0,1,0,1,0,1]代表該狀態(tài)中涉及到老人D、第2 臺(tái)SR 和第2 臺(tái)CR.庫(kù)所p4為從床位去衛(wèi)生間任務(wù)的 “等待區(qū)”,其中的令牌[1,1,1,0,0,0,0,0]代表A、B、C 3 位老人都有去衛(wèi)生間的需求.庫(kù)所p2和p3中的令牌分別代表第1 臺(tái)SR 和第1 臺(tái)CR 處于空閑狀態(tài).

圖7 養(yǎng)老院運(yùn)行情況STdCPN 模型Fig.7 STdCPN model of nursing home situation

現(xiàn)保持機(jī)器人初始位置和老人所執(zhí)行任務(wù)種類不變,通過(guò)改變3 位老人的個(gè)人信息如表4,5,6 所示,來(lái)觀察在個(gè)人信息不同時(shí)智能體給出的任務(wù)執(zhí)行順序.

案例1 中,圖8 為不同任務(wù)執(zhí)行順序下智能體預(yù)測(cè)的3 位老人的個(gè)人滿意度,圖9 為不同任務(wù)執(zhí)行順序下智能體預(yù)測(cè)的3 位老人的總體滿意度.圖10,12 為案例2,3 老人的個(gè)體滿意度.圖11,13 為案例2,3 老人的總體滿意度.如圖9 所示,以CAB 的順序幫助老人完成任務(wù)將會(huì)得到最大的總體滿意度.

圖8 案例1 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.8 Personal satisfaction of the elderly under different task execution sequences in case 1

圖9 案例1 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.9 Overall satisfaction of the elderly under different task execution sequences in case 1

圖10 案例2 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.10 Personal satisfaction of the elderly under different task execution sequences in case 2

如表4 所示,在案例1 中,3 位老人的個(gè)人信息是相同的,這種情況下智能體給出的任務(wù)執(zhí)行順序?qū)⑼耆? 位老人和機(jī)器人的位置信息.當(dāng)機(jī)器人經(jīng)過(guò)C 的房間時(shí)幫助C 是順路的,如果不幫助C,之后需要返回,這樣會(huì)增加總路程,導(dǎo)致老人們的總體等待時(shí)間增加,因此它選擇了先幫助C.幫助完C 之后,此時(shí)先幫助A 再幫助B 和先幫助B再幫助A 的總路程是相同的,但先幫助A 可以更快地將1 位老人送入衛(wèi)生間,從而減少A 的等待時(shí)間以及A 和B 的總等待時(shí)間,因此智能體決定以CAB 的順序執(zhí)行任務(wù).

表4 案例1 中老人的個(gè)人信息Table 4 Personal information of the elders in case 1

表5 案例2 中老人的個(gè)人信息Table 5 Personal information of the elders in case 2

案例2 中,如圖11 所示,以BAC 的順序幫助老人完成任務(wù)將會(huì)得到最大的總體滿意度.在案例2 中,通過(guò)提高B 的舒適運(yùn)載速度使B 成為了第1 位.因?yàn)锽 具有較高的舒適運(yùn)載速度,在被分配更高的速度時(shí),由于速度差造成的不適相比于其他人會(huì)更小,且由于B 的舒適速度較高,其被分配的運(yùn)載速度也會(huì)較高,因此先幫助B 進(jìn)行任務(wù)可以適當(dāng)減小后面2 位老人的等待時(shí)間.以上的優(yōu)勢(shì)已經(jīng)大于機(jī)器人需要返回C 的房間所造成的劣勢(shì),因此智能體決定以BAC 的順序執(zhí)行任務(wù).

圖11 案例2 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.11 Overall satisfaction of the elderly under different task execution sequences in case 2

表6 案例3 中老人的個(gè)人信息Table 6 Personal information of the elders in case 3

圖12 案例3 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.12 Personal satisfaction of the elderly under different task execution sequences in case 3

案例3 中,如圖13 所示,以ABC 的順序幫助老人完成任務(wù)將會(huì)得到最大的總體滿意度.在案例3 中,提高了A 的性格急躁程度、舒適運(yùn)載速度和已等待時(shí)間,并降低了其舒適拉起時(shí)間和舒適下坐時(shí)間,智能體選擇接受總路程和總體等待時(shí)間的增加而先幫助了A.由于B 距離衛(wèi)生間較近且舒適運(yùn)載速度較高,智能體決定以ABC 的順序執(zhí)行任務(wù).

圖13 案例3 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.13 Overall satisfaction of the elderly under different task execution sequences in case 3

4.2 不同任務(wù)種類情況下仿真與分析

現(xiàn)保持機(jī)器人初始位置不變(如圖6)、人員信息不變(如表4),改變老人所要執(zhí)行任務(wù)種類,觀察智能體給出的決策.

如表7 所示,在案例4 中,老人A 想執(zhí)行 “站起” 任務(wù),老人B 想執(zhí)行 “去餐廳” 任務(wù),老人C想執(zhí)行 “去衛(wèi)生間” 任務(wù).圖14,15 分別為案例4中老人的個(gè)體與總體滿意度,圖15 表明以CAB 的順序幫助老人執(zhí)行任務(wù)會(huì)得到最大的回報(bào).因?yàn)镃的任務(wù)優(yōu)先級(jí)最高,需要更快地被執(zhí)行,且機(jī)器人距離C 最近,先幫助C 可以更快地到達(dá)其中一位老人的床邊,通過(guò)減少C 的等待時(shí)間來(lái)減少3 位老人的總等待時(shí)間.當(dāng)機(jī)器人將C 送到衛(wèi)生間之后,先幫助A 是順路的,可以減少A 的等待時(shí)間以及A 和B 的總等待時(shí)間,且A 所執(zhí)行的任務(wù)用時(shí)很短,能夠很快地完成,不會(huì)讓下一位老人有很長(zhǎng)的等待時(shí)間.若先幫助B,由于B 的任務(wù)終點(diǎn)是餐廳,再返回幫助A 的話會(huì)造成路程的大量增加.因此智能體給出的任務(wù)執(zhí)行順序是CAB.

圖14 案例4 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.14 Personal satisfaction of the elderly under different task execution sequences in case 4

圖15 案例4 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.15 Overall satisfaction of the elderly under different task execution sequences in case 4

表7 案例4 中老人的任務(wù)信息Table 7 Task information of the elders in case 4

表8 為案例5 中老人的任務(wù)需求,圖16,17 分別為案例5 中老人的個(gè)體與總體滿意度,圖17 表明以BCA 的順序幫助老人執(zhí)行任務(wù)可以得到最大的回報(bào).因?yàn)锽 所要執(zhí)行任務(wù)優(yōu)先級(jí)最高,先幫助B 再返回幫助C 所造成的劣勢(shì)小于先幫助B 所造成的優(yōu)勢(shì).當(dāng)機(jī)器人將B 送到衛(wèi)生間后,由于C 的任務(wù)用時(shí)遠(yuǎn)小于A 的任務(wù)用時(shí),先幫助C 再幫助A 造成的總體等待時(shí)間減少的優(yōu)勢(shì)大于了先幫助任務(wù)優(yōu)先級(jí)更高的A 所造成的優(yōu)勢(shì),因此智能體決定以BCA 的順序執(zhí)行任務(wù).

圖16 案例5 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.16 Personal satisfaction of the elderly under different task execution sequences in case 5

圖17 案例5 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.17 Overall satisfaction of the elderly under different task execution sequences in case 5

表8 案例5 中老人的任務(wù)信息Table 8 Task information of the elders in case 5

表9 為案例6 中老人的任務(wù)需求,圖18,19 分別為案例6 中老人的個(gè)體與總體滿意度,圖19 表明以ABC 的順序幫助老人執(zhí)行任務(wù)可以得到最大的回報(bào).從案例4、5、6 的結(jié)果可以看出:當(dāng)其他條件不變時(shí),優(yōu)先級(jí)高的任務(wù)往往能被更早地執(zhí)行,在真實(shí)情況中,這樣的結(jié)果也是較為合理的.

圖18 案例6 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.18 Personal satisfaction of the elderly under different task execution sequences in case 6

圖19 案例6 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.19 Overall satisfaction of the elderly under different task execution sequences in case 6

表9 案例6 中老人的任務(wù)信息Table 9 Task information of the elders in case 6

4.3 隨機(jī)情況下仿真與分析

現(xiàn)隨意改變機(jī)器人初始位置信息、老人所執(zhí)行的任務(wù)種類以及老人的個(gè)人信息來(lái)觀察智能體給出的決策.

案例7 中,機(jī)器人的初始位置如圖20 所示,老人的個(gè)人信息如表10 所示,老人的任務(wù)需求如表11所示,圖21,22 分別為案例7 中老人的個(gè)體與總體滿意度.圖22 表明以CAB 的順序幫助老人執(zhí)行任務(wù)可以得到最大的回報(bào).由于A 和C 的任務(wù)緊急程度都為最高級(jí)別,C 的性格急躁程度和已等待時(shí)間均高于A,再加之C 的舒適運(yùn)載速度與舒適拉起和下坐時(shí)間均比A 更具優(yōu)勢(shì),這些優(yōu)勢(shì)戰(zhàn)勝了先幫助C 所造成的總體等待時(shí)間增加的劣勢(shì),因此智能體選擇先幫助C.另一方面,當(dāng)機(jī)器人將C 送入衛(wèi)生間后,A 在任務(wù)優(yōu)先級(jí)、地理位置、任務(wù)執(zhí)行所需時(shí)間以及舒適運(yùn)載速度這些方面均具有優(yōu)勢(shì),B 的性格急躁程度較高,但不足以戰(zhàn)勝A,因此智能體給出的任務(wù)執(zhí)行順序是CAB.

表10 案例7 中老人的個(gè)人信息Table 10 Personal information of the elders in case 7

表11 案例7 中老人的任務(wù)信息Table 11 Task information of the elders in case 7

圖20 案例7 中機(jī)器人初始位置Fig.20 Initial position of the robots in case 7

圖21 案例7 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.21 Personal satisfaction of the elderly under different task execution sequences in case 7

圖22 案例7 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.22 Overall satisfaction of the elderly under different task execution sequences in case 7

案例8 中,機(jī)器人的初始位置如圖23 所示,老人的個(gè)人信息如表12 所示,老人的任務(wù)需求如表13所示,圖24,25 分別為案例8 中老人的個(gè)體與總體滿意度.圖25 表明以CBA 的順序幫助老人執(zhí)行任務(wù)可以得到最大的回報(bào).在該案例中,C 的任務(wù)優(yōu)先級(jí)、性格急躁程度以及舒適運(yùn)載速度均具有很大優(yōu)勢(shì),因此C 成為了第1 名.B 的舒適運(yùn)載速度、舒適拉起時(shí)間以及任務(wù)執(zhí)行所需時(shí)間均具有優(yōu)勢(shì),這些優(yōu)勢(shì)戰(zhàn)勝了A 的已等待時(shí)間所造成的滿意度下降,且A 的任務(wù)地點(diǎn)較遠(yuǎn),若先幫助A 會(huì)增加老人們的總體等待時(shí)間,因此智能體給出的任務(wù)執(zhí)行順序是CBA.

圖23 案例8 中機(jī)器人初始位置Fig.23 Initial position of the robots in case 8

表12 案例8 中老人的個(gè)人信息Table 12 Personal information of the elders in case 8

表13 案例8 中老人的任務(wù)信息Table 13 Task information of the elders in case 8

圖24 案例8 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.24 Personal satisfaction of the elderly under different task execution sequences in case 8

圖25 案例8 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.25 Overall satisfaction of the elderly under different task execution sequences in case 8

案例9 中,機(jī)器人的初始位置如圖26 所示,老人的個(gè)人信息如表14 所示,老人的任務(wù)需求如表15所示,圖27,28 分別為案例9 中老人的個(gè)體與總體滿意度.圖28 表明以ABC 的順序幫助老人執(zhí)行任務(wù)可以得到最大的回報(bào).在該案例中,A 的任務(wù)優(yōu)先級(jí)最高,且A 在任務(wù)很緊急的情況下有著較長(zhǎng)的已等待時(shí)間,這是智能體最不能接受的情況,因此智能體選擇讓機(jī)器人先幫助A.對(duì)于B 和C,機(jī)器人將A 送到衛(wèi)生間后,先幫助B 再幫助C 是順路的,且B 在性格急躁程度、舒適運(yùn)載速度以及任務(wù)所需時(shí)間這些方面都具有優(yōu)勢(shì),加之C 所要執(zhí)行的“去餐廳” 任務(wù)受等待時(shí)間影響所造成的滿意度下降不是非常明顯,因此智能體給出的任務(wù)執(zhí)行順序是ABC.

圖26 案例9 中機(jī)器人初始位置Fig.26 Initial position of the robots in case 9

表14 案例9 中老人的個(gè)人信息Table 14 Personal information of the elders in case 9

表15 案例9 中老人的任務(wù)信息Table 15 Task information of the elders in case 9

圖27 案例9 中不同任務(wù)執(zhí)行順序下老人的個(gè)人滿意度Fig.27 Personal satisfaction of the elderly under different task execution sequences in case 9

圖28 案例9 中不同任務(wù)執(zhí)行順序下老人的總體滿意度Fig.28 Overall satisfaction of the elderly under different task execution sequences in case 9

在案例1、2、3 中,使3 位老人同時(shí)執(zhí)行 “去衛(wèi)生間” 任務(wù),保持機(jī)器人初始位置不變,改變老人們的個(gè)人信息來(lái)觀察智能體給出的決策.案例1 中,由于3 位老人的個(gè)人信息相同,因此智能體根據(jù)3位老人的地理位置給出了最優(yōu)的任務(wù)執(zhí)行順序CAB.案例2 中,B 的舒適運(yùn)載速度增加了0.4 m/s,這導(dǎo)致B 可以以更快的速度執(zhí)行任務(wù)、減少總體等待時(shí)間以及減少速度差造成的滿意度下降,這些優(yōu)勢(shì)大于了需要返回幫助C 造成的路程增加和總體等待時(shí)間增加,因此智能體給出的任務(wù)執(zhí)行順序是BAC.案例3 中,為使A 成為第1 名,需要大幅度增加A 的優(yōu)勢(shì),因?yàn)橄葞椭鶤 將造成很多路程和總體等待時(shí)間的增加.因此在A 的性格急躁程度增加0.3、舒適運(yùn)載速度增加0.7 m/s、舒適拉起時(shí)間減少2 s、舒適下坐時(shí)間減少2 s、已等待時(shí)間增加15 s 后,智能體終于將A 排到了第1 名.這是在A的優(yōu)勢(shì)已經(jīng)遠(yuǎn)遠(yuǎn)大于其他人之后智能體不得不做出的決定.可以看出,在案例1、2、3 中智能體給出的決策是較為合理的.在案例4、5、6 中,保持機(jī)器人初始位置和老人個(gè)人信息不變,通過(guò)改變老人所要執(zhí)行任務(wù)種類來(lái)觀察智能體給出的決策.案例4 中,C 執(zhí)行 “去衛(wèi)生間” 任務(wù),由于該任務(wù)優(yōu)先級(jí)最高且機(jī)器人距離C 最近,因此C 被排在的第1 名.A與B 的任務(wù)優(yōu)先級(jí)均較低,雖然B 的任務(wù) “去餐廳”的優(yōu)先級(jí)較A 的任務(wù) “站起” 高1 級(jí),但A 的地理位置較好且任務(wù)耗時(shí)較短,因此智能體在權(quán)衡后給出了CAB 的任務(wù)執(zhí)行順序.案例5 中,B 執(zhí)行 “去衛(wèi)生間”任務(wù),雖然C 距離機(jī)器人最近且其任務(wù)“站起” 耗時(shí)較短,但由于B 的任務(wù)緊急,因此B 被排在第1 名.A 的任務(wù) “去餐廳” 的優(yōu)先級(jí)略高于C,但C 具有較短的任務(wù)執(zhí)行時(shí)間,智能體經(jīng)過(guò)權(quán)衡后給出了BCA 的任務(wù)執(zhí)行順序.案例6 中,雖然A 距離機(jī)器人最遠(yuǎn),但由于A “去衛(wèi)生間” 的任務(wù)具有最高的優(yōu)先級(jí),智能體選擇冒著增加總路程和總等待時(shí)間的風(fēng)險(xiǎn)將A 排在第1 名.機(jī)器人將A 送入衛(wèi)生間后,由于先幫助B 是順路的且B 的“站起” 任務(wù)耗時(shí)非常短,因此智能體給出的任務(wù)執(zhí)行順序是ABC.由案例4、5、6 可以看出,在面對(duì)非常緊急的任務(wù)時(shí),智能體不會(huì)被其他較小的優(yōu)勢(shì)所影響,而是堅(jiān)持先幫助任務(wù)優(yōu)先級(jí)有絕對(duì)優(yōu)勢(shì)的老人.案例7、8、9 中,同時(shí)改變機(jī)器人初始位置信息、老人所執(zhí)行的任務(wù)種類以及老人的個(gè)人信息來(lái)觀察智能體給出的決策.由于這3 個(gè)案例中的變量較多,智能體給出的決策是否是最合理的,以人的主觀意識(shí)無(wú)法準(zhǔn)確判斷.需要通過(guò)實(shí)驗(yàn)對(duì)象的滿意度反饋不斷地調(diào)整滿意度模型中的各項(xiàng)參數(shù),從而使智能體的決策越來(lái)越合理,最終達(dá)到能夠滿足絕大部分人需求的程度.

真實(shí)情況中,往往不會(huì)有如此多的沖突出現(xiàn).一般情況下,老人提出需求后,智能體結(jié)合老人的個(gè)人信息對(duì)其任務(wù)進(jìn)行規(guī)劃并派出合適的機(jī)器人,然后機(jī)器人便可依據(jù)該規(guī)劃按照STdCPN 模型幫助老人完成任務(wù).當(dāng)多個(gè)任務(wù)沖突時(shí),智能體會(huì)給出當(dāng)前時(shí)刻最佳的任務(wù)執(zhí)行順序,并按照該順序執(zhí)行老人的任務(wù).而在這些任務(wù)按照該順序完成之前,有極大的可能會(huì)有其他機(jī)器人重新回到空閑狀態(tài),也有可能會(huì)有新的老人加入到隊(duì)列中,此時(shí)智能體會(huì)根據(jù)新的系統(tǒng)狀態(tài)來(lái)重新規(guī)劃系統(tǒng)中的任務(wù).

5 結(jié)論

本文為解決養(yǎng)老院情境下多個(gè)異構(gòu)服務(wù)機(jī)器人照顧多位老人的建模問(wèn)題,結(jié)合時(shí)延Petri 網(wǎng)與顏色Petri 網(wǎng)并加以改進(jìn)提出了一種可擴(kuò)展時(shí)延-顏色Petri 網(wǎng)(STdCPN),并使用STdCPN 對(duì)養(yǎng)老院情境下多個(gè)異構(gòu)服務(wù)機(jī)器人照顧多位老人的過(guò)程進(jìn)行建模.STdCPN 的特點(diǎn)是可以在不改變網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上隨時(shí)調(diào)整系統(tǒng)中資源的種類(不僅限于數(shù)量),應(yīng)用于養(yǎng)老院情境中,既可以增減老人和機(jī)器人的數(shù)量(該情境中,由于老人和機(jī)器人都攜帶著各自的信息,因此數(shù)量的增加即是種類的增加)也可以對(duì)老人的任務(wù)執(zhí)行權(quán)限加以限制.為保證任務(wù)過(guò)程中老人的滿意度,提出了基于養(yǎng)老院情境的服務(wù)對(duì)象滿意度模型.該模型考慮老人的性格急躁程度、已等待時(shí)間、機(jī)器人運(yùn)載速度與老人舒適速度之差以及老人所要執(zhí)行任務(wù)種類等因素來(lái)評(píng)估老人的滿意度,該滿意度將作為系統(tǒng)中任務(wù)完成情況的重要指標(biāo).設(shè)計(jì)了智能體作為該協(xié)調(diào)框架的 “調(diào)度者”.當(dāng)老人提出任務(wù)需求后,智能體根據(jù)機(jī)器人的實(shí)時(shí)狀態(tài)、位置等信息派出合適的機(jī)器人執(zhí)行任務(wù),并根據(jù)老人的 “個(gè)人因素” 結(jié)合滿意度模型對(duì)老人的任務(wù)過(guò)程進(jìn)行個(gè)性化的規(guī)劃,機(jī)器人將按照該規(guī)劃以及對(duì)應(yīng)的STdCPN 模型執(zhí)行任務(wù).當(dāng)多個(gè)任務(wù)沖突時(shí),智能體會(huì)對(duì)所有的任務(wù)執(zhí)行方案進(jìn)行預(yù)測(cè),選出能夠使得老人總體滿意度最大的任務(wù)執(zhí)行方案來(lái)執(zhí)行.對(duì)該協(xié)調(diào)框架進(jìn)行了仿真.通過(guò)仿真結(jié)果可以看出,在僅改變老人個(gè)人信息和僅改變老人任務(wù)種類這兩種情況下,智能體均能給出較為合理的決策.在同時(shí)改變老人個(gè)人信息、老人任務(wù)種類以及機(jī)器人初始位置的情況下,智能體的決策仍具有其合理性.本文接下來(lái)的工作,將搭建基于VR虛擬場(chǎng)景和生理信號(hào)采集的滿意度獲取系統(tǒng).通過(guò)實(shí)驗(yàn)對(duì)象的滿意度反饋不斷地調(diào)整滿意度模型中的各項(xiàng)參數(shù),從而使智能體的決策更加合理,使該協(xié)調(diào)框架更好的應(yīng)用于養(yǎng)老院情境.

附錄

在STdCPN 中,由于映射在有向弧F上的權(quán)重可以是矩陣,且該模型中含有多達(dá)60 個(gè)有向弧,同時(shí)權(quán)重只由 “0”或 “1” 組成,因此,為方便表示,現(xiàn)用一種簡(jiǎn)化的方式來(lái)描述權(quán)重.每項(xiàng)權(quán)重由兩部分組成,第1 部分為權(quán)重的 “行數(shù)×列數(shù)”,第2 部分為該權(quán)重中所有 “1”的坐標(biāo),其余未標(biāo)出的坐標(biāo)均為 “0”.例如,[4×8,((1,1),(2,2),(3,3),(4,4))] 與

對(duì)應(yīng).則權(quán)函數(shù)W如式(A8)所示.

該STCPN 子模型的運(yùn)行過(guò)程如下:當(dāng)庫(kù)所p1內(nèi)的老人產(chǎn)生去衛(wèi)生間的需求時(shí),他會(huì)對(duì)機(jī)器人進(jìn)行呼叫(通過(guò)遙控器或語(yǔ)音控制等方式,即變遷t1觸發(fā)),隨即該老人進(jìn)入一個(gè)虛擬的 “等待區(qū)” (p4).這時(shí)系統(tǒng)判斷該任務(wù)所需機(jī)器人是否處于空閑狀態(tài)(p2和p3).如果該任務(wù)對(duì)應(yīng)的機(jī)器人(一個(gè)或多個(gè))不全處于空閑狀態(tài) (即變遷t2的觸發(fā)條件不滿足,無(wú)法觸發(fā)),則老人繼續(xù)在 “等待區(qū)” 內(nèi)等候,直到有所需機(jī)器人重回空閑狀態(tài);如果有對(duì)應(yīng)機(jī)器人處于空閑狀態(tài),則派出對(duì)應(yīng)機(jī)器人(變遷t2觸發(fā)),SR 和CR 趕往老人的床位,p2內(nèi)的SR 和p3內(nèi)的CR 隨即消失(退出 “空閑” 狀態(tài)),同時(shí)老人由在 “等待區(qū)” 內(nèi)等待的狀態(tài) (p4) 進(jìn)入到 “等待機(jī)器人到來(lái)” 的狀態(tài)(p5).機(jī)器人就位的瞬間,變遷t3觸發(fā),系統(tǒng)進(jìn)入 “老人準(zhǔn)備” 狀態(tài)(p6).待老人準(zhǔn)備好之后,變遷(t4)觸發(fā),步行支援機(jī)開(kāi)始將老人拉起,系統(tǒng)進(jìn)入 “老人正在被拉起” 的狀態(tài)(p7).在拉起動(dòng)作結(jié)束的瞬間t5觸發(fā),系統(tǒng)進(jìn)入到SR 與CR 對(duì)接的狀態(tài)(p8).對(duì)接完成后t6觸發(fā),SR 開(kāi)始攙扶老人下坐到CR 上,系統(tǒng)進(jìn)入 “老人正在下坐”的狀態(tài)(p9).動(dòng)作完成后t7觸發(fā),老人坐在CR 上(p10).隨即變遷t8觸發(fā),CR 載著老人進(jìn)入行駛狀態(tài)(p11),此時(shí)SR 需跟隨CR 以幫助老人完成之后的動(dòng)作,當(dāng)該狀態(tài)結(jié)束時(shí),CR 已載著老人到達(dá)目的地且兩機(jī)器人已調(diào)整好位姿.隨即變遷t9觸發(fā),系統(tǒng)進(jìn)入 “老人準(zhǔn)備” 的狀態(tài)(p12),老人準(zhǔn)備好之后變遷t10觸發(fā),SR 再次對(duì)老人進(jìn)行拉起(p13),該動(dòng)作完成后t11觸發(fā),SR 帶著老人調(diào)整位姿(p14),同時(shí)本次任務(wù)中CR 的所有動(dòng)作已完成,CR 回到空閑狀態(tài)(p3),重新在p3中出現(xiàn).老人的任務(wù)繼續(xù)進(jìn)行,SR 調(diào)整好后t12觸發(fā),SR 攙扶老人坐到馬桶上(p15).該動(dòng)作完成后t13觸發(fā),老人坐在馬桶上(p16),同時(shí)SR 的所有動(dòng)作完成,回到 “空閑” 狀態(tài)(p2).此時(shí) “去衛(wèi)生間” 任務(wù)完成,當(dāng)老人需要返回床位時(shí),他將再次提出需求,重新進(jìn)入到虛擬的 “等待區(qū)”(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)