基于多Agent機(jī)器人系統(tǒng)的圖書歸類解決方案

摘 要：現(xiàn)代圖書館的藏書量已成為衡量一個(gè)圖書館水平的重要指標(biāo)之一，而藏書量的增多也意味著圖書館日常管理任務(wù)的加重，圖書管理人員要耗費(fèi)巨大的精力去歸類、整理圖書。移動(dòng)機(jī)器人和多Agent 技術(shù)的迅猛發(fā)展給這個(gè)亟待解決的問(wèn)題帶來(lái)了一種新的、可能的解決途徑。我們提出一種基于多Agent 技術(shù)的機(jī)器人軟件實(shí)現(xiàn)模型，該機(jī)器人能自動(dòng)識(shí)別、歸類圖書，并通過(guò)改進(jìn)BUG 算法導(dǎo)航適宜的行走路線，快速、準(zhǔn)確地完成圖書館大量書籍的分類整理工作，極大地簡(jiǎn)化了傳統(tǒng)的人工操作，減輕了管理人員繁重的重復(fù)性勞動(dòng)。

　　隨著科學(xué)的進(jìn)步，現(xiàn)代圖書館的藏書量和報(bào)刊雜志的種類急劇增加。隨之而來(lái)的日益繁重的管理任務(wù)，僅憑傳統(tǒng)的人工操作，不僅耗費(fèi)越來(lái)越多的人力、物力、財(cái)力，也降低了圖書管理工作的可靠性，特別是有些讀者借了多本書后隔天就馬上歸還，這無(wú)形中加重了圖書館理人員的勞動(dòng)量，因而，讓機(jī)器代替人類實(shí)現(xiàn)圖書館管理的工作是圖書館管理的必然發(fā)展趨勢(shì)。

　　智能機(jī)器人是一類能夠通過(guò)傳感器感知環(huán)境和自身狀態(tài)，實(shí)現(xiàn)在有障礙物的環(huán)境中面向目標(biāo)的自主運(yùn)動(dòng)，從而完成一定作業(yè)功能的機(jī)器人系統(tǒng)。近年來(lái)，機(jī)器人技術(shù)在工業(yè)、農(nóng)業(yè)、航天及空間探測(cè)等許多領(lǐng)域都起到了重要的作用，同時(shí)又顯示了廣泛的應(yīng)用前景，成為人工智能學(xué)術(shù)界研究和關(guān)注的熱點(diǎn)問(wèn)題。而Agent 是處在某個(gè)環(huán)境中的計(jì)算機(jī)系統(tǒng)，該系統(tǒng)有能力在這個(gè)環(huán)境中自主行動(dòng)以實(shí)現(xiàn)其設(shè)計(jì)目標(biāo)。多Agent 系統(tǒng)是多個(gè)可運(yùn)作的Agent 的有機(jī)結(jié)合，通過(guò)多Agent 之間的交互將一個(gè)復(fù)雜的問(wèn)題簡(jiǎn)單化。

　　將多Agent 技術(shù)應(yīng)用于移動(dòng)機(jī)器人中使得機(jī)器人具有更高的智能性，實(shí)現(xiàn)自動(dòng)感知環(huán)境變化、智能識(shí)別、歸類、傳送圖書，讓機(jī)器完成重復(fù)、繁重的體力勞動(dòng)，減輕了圖書館工作人員的工作壓力，實(shí)現(xiàn)圖書館的智能化。

　　1 Agent與多Agent的機(jī)器人系統(tǒng)基本理論

　　1.1 Agent 理論

　　在人工智能研究的進(jìn)程中，研究者們逐漸認(rèn)識(shí)到應(yīng)該把人工智能各個(gè)領(lǐng)域的研究成果集成為一個(gè)具有智能行為概念的人,更重要的是人們認(rèn)識(shí)到了人類智能的本質(zhì)是一種社會(huì)性的智能，人類絕大部分的活動(dòng)都涉及多個(gè)人構(gòu)成的社會(huì)團(tuán)體，大型復(fù)雜問(wèn)題的求解需要多個(gè)專業(yè)人員或組織協(xié)作完成。人最重要的和最多的智能是在由眾多個(gè)體構(gòu)成的社會(huì)中進(jìn)行各種活動(dòng)時(shí)體現(xiàn)出來(lái)的。協(xié)作、競(jìng)爭(zhēng)、談判等等是人類智能行為的主要表現(xiàn)形式。要對(duì)社會(huì)性的智能進(jìn)行研究，構(gòu)成社會(huì)的基本構(gòu)件人的對(duì)應(yīng)物Agent理所當(dāng)然地就成為人工智能研究的基本對(duì)象。

　　一般認(rèn)為，Agent 是一種處于一定環(huán)境下包裝的計(jì)算機(jī)系統(tǒng)，為了實(shí)現(xiàn)設(shè)計(jì)目的，它能在那種環(huán)境下靈活地、自主地活動(dòng)。雖然目前還沒(méi)有一個(gè)大家都能接受的關(guān)于Agent 的定義，但幾乎所有被稱為Agent的軟件或硬件系統(tǒng)都具有以下的特征： 自治性（Autonomy ） 、社會(huì)性（Social Ability） 、反應(yīng)性（Reactivity）、主動(dòng)性（Proactivity）、智能性（Intelligence ）、合作性（Collaboration）。

　　1.2 基于多Agent 的機(jī)器人系統(tǒng)及其任務(wù)模型

　　多機(jī)器人系統(tǒng)并非一個(gè)簡(jiǎn)單的多機(jī)器人組合系統(tǒng)，而是一個(gè)以分布式人工智能為指導(dǎo)，結(jié)合計(jì)算機(jī)、分布式控制、多傳感器技術(shù)和理論，將多個(gè)機(jī)器人組織而成的分布式智能系統(tǒng)。多機(jī)器人系統(tǒng)在系統(tǒng)功能、并行性、柔性、穩(wěn)定性以及容錯(cuò)性等方面具有單機(jī)器人系統(tǒng)不可比擬的優(yōu)勢(shì)，其正得到深入研究和廣泛應(yīng)用。多個(gè)機(jī)器人在共同的復(fù)雜環(huán)境中協(xié)同工作時(shí)，不僅和環(huán)境之間有復(fù)雜的交互作用，而且相互之間既有分工又有協(xié)作，既有合作又有競(jìng)爭(zhēng)。多機(jī)器人系統(tǒng)的研究存在許多與單機(jī)器人系統(tǒng)所不同的問(wèn)題：（1）如何在各機(jī)器人間表達(dá)、描述問(wèn)題，分解和分配任務(wù)；（2）如何使機(jī)器人間相互通訊和相互作用；（3）如何保證各機(jī)器人行為協(xié)調(diào)一致；（4）機(jī)器人間如何識(shí)別和解決沖突等等。

　　這些問(wèn)題主要涉及分布式問(wèn)題的求解，用傳統(tǒng)的集中控制理論和機(jī)器人理論已難以解決。當(dāng)前MAS理論的發(fā)展及其在分布式系統(tǒng)中的應(yīng)用給多機(jī)器人系統(tǒng)的研究帶來(lái)了新的思路，并已在一些試驗(yàn)系統(tǒng)的開發(fā)中得到了驗(yàn)證。

　　1.3 機(jī)器人Agent 的任務(wù)模型

　　機(jī)器人的行為總是帶有一定目的性，即與一定的任務(wù)或任務(wù)目標(biāo)相聯(lián)系任務(wù)目標(biāo)。根據(jù)其是抽象的還是具體的，可分為隱式任務(wù)和顯式任務(wù)兩類：隱式任務(wù)一般是指可用自然語(yǔ)言描述的，沒(méi)有明確數(shù)學(xué)形式的抽象任務(wù)，例如，將圖書放到書柜上,或放到推車.顯式任務(wù)則一般是具有精確的數(shù)學(xué)形式描述或量化指標(biāo)的具體任務(wù)，如移動(dòng)到目標(biāo)點(diǎn)（3, 7）,或保持加工精度為土0. 003mm .可以看到，隱式任務(wù)一般是高層任務(wù)指令，而顯式任務(wù)一般是底層具體任務(wù)。隱式任務(wù)需要結(jié)合環(huán)境信息以及機(jī)器人的自身狀態(tài)，轉(zhuǎn)化為顯示任務(wù)序列加以實(shí)現(xiàn)。以機(jī)器人取書為例，假設(shè)機(jī)器人位置為（5, 8},書位置為（32, 36），推車位置為（67, 57）。將書放入推車為隱式任務(wù)目標(biāo)，其可分解為顯示任務(wù)目標(biāo)序列：移動(dòng)到位置點(diǎn)（32,36）,夾持位置點(diǎn)在（32, 36）的書,移動(dòng)到位置點(diǎn)（67,57）,放置書到位置點(diǎn)在（67, 57）的推車.一般而言，機(jī)器人Agent 的任務(wù)可用下式表示：

　　Task=（Goal,Precondition,Body,Effects,Setting）

　　其中Goal 表示任務(wù)task 的目標(biāo)，一般可用自然語(yǔ)言描述；Precondition 表示任務(wù)task 實(shí)現(xiàn)所需的前提條件；Body 表示任務(wù)task 的子任務(wù)序列或顯式目標(biāo)序列；Setting 表示任務(wù)task 的附加約束條件集；Effects 表示任務(wù)task 實(shí)現(xiàn)后對(duì)環(huán)境的效果集。

　　隱式任務(wù)在分解轉(zhuǎn)化為顯式任務(wù)時(shí)，也可能生成某些中間隱式任務(wù)，從而形成機(jī)器人任務(wù)分解的一種與/或樹結(jié)構(gòu)。其中與表示上層任務(wù)目標(biāo)通過(guò)實(shí)現(xiàn)所有下層任務(wù)目標(biāo)才能完成，或表示上層任務(wù)目標(biāo)可通過(guò)選擇實(shí)現(xiàn)下層的某個(gè)任務(wù)目標(biāo)加以完成。一般而言，樹狀結(jié)構(gòu)的最底層分支的端點(diǎn)都是機(jī)器人可直接執(zhí)行的顯式任務(wù)目標(biāo)，并且是與樹結(jié)構(gòu)，即顯示任務(wù)目標(biāo)序列。

　　2 基于多Agent的機(jī)器人系統(tǒng)的體系設(shè)計(jì)

　　2.1 環(huán)境設(shè)置

　　本系統(tǒng)為了便于機(jī)器人識(shí)別，將圖書館中所有的書柜用阿拉伯?dāng)?shù)字進(jìn)行編號(hào)，即每一書柜對(duì)應(yīng)相應(yīng)的標(biāo)簽編碼段，跟圖書館中每個(gè)柜上設(shè)置放置的圖書數(shù)目一致，并將其存入規(guī)則庫(kù)中。推車設(shè)計(jì)成具有若干個(gè)格子，且設(shè)定每個(gè)格子只放一本書，便于機(jī)器人區(qū)分某本書的在推車上的具體位置，推車上的格子也以阿拉伯?dāng)?shù)字標(biāo)識(shí)，便于機(jī)器人存儲(chǔ)、記憶。

　　2.2 系統(tǒng)結(jié)構(gòu)

　　本系統(tǒng)利用多Agent 系統(tǒng)減輕人工分類、擺放圖書的工作量，其工作流程如圖1 所示：

圖1 系統(tǒng)體系結(jié)構(gòu)。

（1）當(dāng)機(jī)器人的機(jī)械手拿一本圖書時(shí)，機(jī)器手上的自動(dòng)識(shí)別系統(tǒng)即帶有傳感器的環(huán)境識(shí)別Agent 立即感知環(huán)境變化，且獲取圖書條形碼信息，并將這些信息傳遞給圖書識(shí)別Agent.這一過(guò)程主要是實(shí)現(xiàn)從環(huán)境狀態(tài)（E）到感知（Per）的映射（函數(shù)see 的輸出是一種感知，即感知的輸入）：see : E--> Per.

　?。?）信息庫(kù)包括了圖書信息的集合和圖書館的電子地圖，存儲(chǔ)著所有圖書條形碼的信息、書名及其圖書標(biāo)簽和圖書館電子地圖。通過(guò)傳感器識(shí)別出條形碼，圖書識(shí)別Agent 接收條形碼信息，將信息分解，并跟信息庫(kù)中已有的條形碼進(jìn)行模式匹配，找到符合的樣本，返回圖書的基本信息，用函數(shù)book（館號(hào)，條形碼，條形碼號(hào)，書名，標(biāo)簽）表示，其中標(biāo)簽指的是在圖書館里的位置編碼，分為2 大部分，前一部分字母遵循中國(guó)圖書館圖書分類法，指出圖書的類別，而后一部分則為每個(gè)圖書館各自的編碼方式，存儲(chǔ)著每本圖書在館內(nèi)的具體位置。并將這個(gè)函數(shù)傳遞給圖書歸類Agent.

　?。?）規(guī)則庫(kù)是規(guī)則的集合，存儲(chǔ)著中國(guó)圖書館圖書分類法及本地圖書館子規(guī)則。

　　圖書歸類Agent 接收函數(shù)book,將對(duì)應(yīng)的標(biāo)簽跟規(guī)則庫(kù)中的規(guī)則進(jìn)行比較得到圖書在館中的位置，并將其分解為某類圖書的某個(gè)具體書柜，用函數(shù)position（編碼號(hào)，書柜號(hào)）將位置函數(shù)傳遞給動(dòng)作Agent.

　?。?）動(dòng)作選擇函數(shù)獲得推理結(jié)果實(shí)現(xiàn)從內(nèi)部狀態(tài)到動(dòng)作（Ac）的映射：action:I--> Ac.動(dòng)作Agent將圖書放入推車的空格子中，并在臨時(shí)庫(kù)中記錄每本書的書柜號(hào)和推車格號(hào)，同一書柜號(hào)的圖書可以記錄在一條記錄中，在原先記錄尾部追加其推車格號(hào)即可，那么機(jī)器人可將推車中同一個(gè)書柜的圖書一次性擺放，不需下次折回。臨時(shí)庫(kù)見表1 所示。

表1 臨時(shí)庫(kù)表一

　　（5）當(dāng)推車上的格子都擺滿后，動(dòng)作Agent 傳遞消息給智能決策Agent 圖書已擺滿，則智能決策Agent查看臨時(shí)庫(kù)中的各個(gè)書柜號(hào)，根據(jù)信息庫(kù)中已存儲(chǔ)的圖書館的電子地圖即各個(gè)書柜的擺放次序利用改進(jìn)BUG 算法計(jì)算出各個(gè)目的地的優(yōu)先次序和機(jī)器人的行走路徑，并指導(dǎo)動(dòng)作Agent 到各個(gè)目的地完成擺書操作，最后回到還書處等待下一次的擺書動(dòng)作。

　　3 關(guān)鍵算法分析

　　3.1 圖書歸類

　　依據(jù)圖書館給圖書分類編碼的標(biāo)準(zhǔn)，參照中國(guó)圖書館圖書分類法，因?yàn)閲?guó)家圖書館圖書分類法，從首字符可以分出大的圖書所屬類別，從一級(jí)類別中再細(xì)分，部分首字符，例如：E、U、V 就代表一類，不需要再細(xì)分，而有些要細(xì)分出來(lái)，則需要首四位字符的判斷才能分析出來(lái)，更特別的是審計(jì)類編碼規(guī)則，要有前六位才可以分辨出來(lái)。據(jù)此我們?cè)O(shè)計(jì)圖書分類編碼，共12 位，由26 個(gè)大寫字母和十個(gè)數(shù)字0~9 組成，前四位代表圖書的類別，如果按照中國(guó)圖書館分類法，字符不足四位的用通用字符*補(bǔ)足，例如：U 代表交通運(yùn)輸類，一本書的分類編碼前四位可以設(shè)計(jì)為U***;TP1 代表自動(dòng)化基礎(chǔ)理論，該類別一本書的分類編碼前四位可以設(shè)計(jì)為：TP1*,后8 位按照各個(gè)不同圖書館的不同要求進(jìn)行編碼，從而根據(jù)類別和后八位的編碼確定某本書所在的碼段，接著確定具體的位置和所在柜。

　　我們根據(jù)該編碼規(guī)則來(lái)設(shè)計(jì)圖書分類規(guī)則庫(kù)。我們?cè)O(shè)計(jì)四個(gè)子規(guī)則庫(kù)：

　　唯一字符規(guī)則庫(kù)：

　　r1: IF 第一個(gè)字符是U/E/P/Q/R/V THEN 該本書是所對(duì)應(yīng)的某一大類。

　　兩個(gè)字符規(guī)則庫(kù)：

　　r1: IF 第一個(gè)字符是某個(gè)字母 THEN 該本書是某種一級(jí)類；

　　r2: IF 第二個(gè)字符是某個(gè)字母或數(shù)字 THEN 該本書是二級(jí)類；

　　三個(gè)字符規(guī)則庫(kù)：

　　r1: IF 第一個(gè)字符是某個(gè)字母 THEN 該本書是某種一級(jí)類；

　　r2: IF 第二個(gè)字符是某個(gè)字母或數(shù)字 THEN該本書是某二級(jí)類；

　　r3: IF 第三個(gè)字符是某個(gè)字母或數(shù)字 THEN該本書是某三級(jí)類；