基于多Agent機器人系統的圖書(shū)歸類(lèi)解決方案

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

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

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

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

　　1 Agent與多Agent的機器人系統基本理論

　　1.1 Agent 理論

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

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

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

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

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

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

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

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

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

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

　　2 基于多Agent的機器人系統的體系設計

　　2.1 環(huán)境設置

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

　　2.2 系統結構

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

圖1 系統體系結構。

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

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

　?。?）規則庫是規則的集合，存儲著(zhù)中國圖書(shū)館圖書(shū)分類(lèi)法及本地圖書(shū)館子規則。

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

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

表1 臨時(shí)庫表一

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

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

　　3.1 圖書(shū)歸類(lèi)

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

　　我們根據該編碼規則來(lái)設計圖書(shū)分類(lèi)規則庫。我們設計四個(gè)子規則庫：

　　唯一字符規則庫：

　　r1: IF 第一個(gè)字符是U/E/P/Q/R/V THEN 該本書(shū)是所對應的某一大類(lèi)。

　　兩個(gè)字符規則庫：

　　r1: IF 第一個(gè)字符是某個(gè)字母 THEN 該本書(shū)是某種一級類(lèi)；

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

　　三個(gè)字符規則庫：

　　r1: IF 第一個(gè)字符是某個(gè)字母 THEN 該本書(shū)是某種一級類(lèi)；

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

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