智能體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)