基于多Agent機器人系統(tǒng)的圖書歸類解決方案-技術(shù)方案

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

隨著科學(xué)的進步，現(xiàn)代圖書館的藏書量和報刊雜志的種類急劇增加。隨之而來的日益繁重的管理任務(wù)，僅憑傳統(tǒng)的人工操作，不僅耗費越來越多的人力、物力、財力，也降低了圖書管理工作的牢靠性，特殊是有些讀者借了多本書后隔天就立刻歸還，這無形中加重了圖書館理人員的勞動量，因而，讓機器代替人類實現(xiàn)圖書館管理的工作是圖書館管理的必定進展趨勢。

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

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

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

1.1Agent理論

在人工智能討論的進程中，討論者們漸漸熟悉到應(yīng)當(dāng)把人工智能各個領(lǐng)域的討論成果集成為一個具有智能行為概念的"人",更重要的是人們熟悉到了人類智能的本質(zhì)是一種社會性的智能，人類絕大部分的活動都涉及多個人構(gòu)成的社會團體，大型簡單問題的求解需要多個人員或組織協(xié)作完成。人重要的和多的智能是在由眾多個體構(gòu)成的社會中進行各種活動時體現(xiàn)出來的。"協(xié)作"、"競爭"、"談判"等等是人類智能行為的主要表現(xiàn)形式。要對社會性的智能進行討論，構(gòu)成社會的基本構(gòu)件"人"的對應(yīng)物"Agent"理所當(dāng)然地就成為人工智能討論的基本對象。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）規(guī)章庫是規(guī)章的集合，存儲著中國圖書館圖書分類法及本地圖書館子規(guī)章。

圖書歸類Agent接收函數(shù)book,將對應(yīng)的標(biāo)簽跟規(guī)章庫中的規(guī)章進行比較得到圖書在館中的位置，并將其分解為某類圖書的某個詳細書柜，用函數(shù)position（編碼號，書柜號）將位置函數(shù)傳遞給動作Agent.

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

表1臨時庫表一

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

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

3.1圖書歸類

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

我們依據(jù)該編碼規(guī)章來設(shè)計圖書分類規(guī)章庫。我們設(shè)計四個子規(guī)章庫：

字符規(guī)章庫：

r1:IF個字符是U/E/P/Q/R/VTHEN該本書是所對應(yīng)的某一大類。

兩個字符規(guī)章庫：

r1:IF個字符是某個字母THEN該本書是某種類；

r2:IF其次個字符是某個字母或數(shù)字THEN該本書是二級類；

三個字符規(guī)章庫：

r1:IF個字符是某個字母THEN該本書是某種類；

r2:IF其次個字符是某個字母或數(shù)字THEN該本書是某二級類；

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

四個字符規(guī)章庫：

r41:IF個字符是某個字母THEN該本書是某種類；

r42:IF其次個字符是某個字母或數(shù)字THEN該本書是某二級類；

r43:IF第三個字符是某個字母或數(shù)字THEN該本書是某三級類；

r44:IF第四個字符是某個字母或數(shù)字THEN該本書是某四級類；

r45:IF第五字符是點THEN依據(jù)前四位已推斷類別和后8位字符的范圍找到該書相應(yīng)的柜子的編碼AND跳出規(guī)章庫；

ELSE第五個字符是某個字母或數(shù)字THEN該S本書是某五級類；

r46:IF第6個字符是點THEN依據(jù)前五位已推斷類別和后7字符的范圍找到該書相應(yīng)的柜子的編碼AND跳出規(guī)章庫；

依據(jù)上述規(guī)章庫我們給出編碼和對應(yīng)書柜編號的識別通用算法如下：

If（其次個字符=*）

{轉(zhuǎn)入字符規(guī)章庫；

依據(jù)該類別和后8位字符的范圍找到該書相應(yīng)書柜的編碼；}

Elseif（第三個字符=*）

{轉(zhuǎn)入兩個字符規(guī)章庫；

依據(jù)該類別和后8位字符的范圍找到該書相應(yīng)書柜的編碼;}

Elseif（第四個字符=*）

{轉(zhuǎn)入三個字符規(guī)章庫

依據(jù)該類別和后8位字符的范圍找到該書相應(yīng)書柜的編碼;}

Else轉(zhuǎn)入四個字符規(guī)章庫；

我們以一個例子詳細說明編碼規(guī)章：

假設(shè)某一高校圖書館給出非審計類8位的編碼規(guī)章是，對于U類書籍，編碼范圍U***00000000-U***00000200內(nèi)的書籍放在1號柜。我們對一本編碼為U***00000023使用本文所述的分類算法進行分類。首先，推斷其次位字符，依據(jù)算法其次位是*,轉(zhuǎn)入字符規(guī)章庫，首先依據(jù)規(guī)章r11,推斷出該本書是交通運輸類，結(jié)合后八位0000023,該編碼在U***0000000-U***0000200范圍內(nèi)，推斷出該書所在的位置為1號柜。

3.2智能尋線導(dǎo)航

所謂路徑規(guī)劃是指移動機器人根據(jù)某一性能指標(biāo)（如距離、時間、能量等）搜尋一條從起始狀態(tài)到目標(biāo)狀態(tài)的或次優(yōu)路徑。路徑規(guī)劃主要涉及的問題包括：

利用獲得的移動機器人環(huán)境信息建立較為合理的模型，再用某種算法查找一條從起始狀態(tài)到目標(biāo)狀態(tài)的或近似的無碰撞路徑；能夠處理環(huán)境模型中的不確定因素和路徑跟蹤中消失的誤差，使外界物體對機器人的影響降到；如何利用已知的全部信息來引導(dǎo)機器人的動作，從而得到相對更優(yōu)的行為決策。

路徑規(guī)劃是移動機器人討論中的一個基本且重要的問題。路徑規(guī)劃的步是確定地圖的表示方法，其目的是將機器人和障礙物所在的物理空間的顯著特征描述出來，使之更適合于規(guī)劃。本文中將地圖置于信息庫中，智能決策Agent依據(jù)臨時庫中的各個目的地在電子地圖中的位置，確定物體或自身的位姿（位置和姿勢），制訂出他們的優(yōu)先次序。

由于機器人工作的環(huán)境是動態(tài)變化的，環(huán)境中的障礙物不全是已知的、靜止的。這就要求機器人要不斷地對四周環(huán)境進行探測，并對探測到的障礙物進行實時處理，即要求機器人具備局部規(guī)劃的力量。機器人在運行過程中，通常會發(fā)生如下幾種類型的沖突：

碰撞、擁塞以及死鎖。

碰撞：一個運動物體在另一個運動物體運行路線上的相同位置同時消失。擁塞：其它運動物體阻礙當(dāng)前運動物體按要求到達目標(biāo)。死鎖：運動物體無法進行各自的下一步動作。這些沖突的產(chǎn)生主要是由于機器人對環(huán)境信息缺乏具體了解造成的。因此，當(dāng)環(huán)境動態(tài)變化時，往往采納依靠傳感器的局部路徑規(guī)劃方法進行沖突消解。

由于本文中設(shè)計的機器人個數(shù)比較少，就將環(huán)境中其他機器人視為環(huán)境中的障礙物，而且環(huán)境比較簡潔，因而采納無通訊的避碰力一法的機器人，不需要與其他機器人的通訊，完全依靠機器人的傳感器獵取其他機器人的運動信息。

本文采納改進BUG算法計算兩點間的短路徑，即計算出離當(dāng)前點路徑短的目標(biāo)點，詳細算法如下：

依據(jù)電子地圖，智能策略Agent初步給出各個目的點的優(yōu)先次序及其行走路線，但是實際行走中還可以會遇到其他不行預(yù)知的障礙，這里改進BUG算法考慮到了這些因素，詳細算法如下：

S=起始點，T=終點

設(shè)M為空矩陣，i=1;V（1）為空集

MAP_R為與矩陣M對應(yīng)的二維位圖，Pi為機器人在地圖中的即時位置

While（TPi）//當(dāng)T==Pi表示機器人到達終點

{V（i--由EPC方式采集的數(shù)據(jù)）//EPC為端點采集法

M--M∪V（i）

位圖MAP_R隨之不斷更新

IF（線段PiT和障礙物邊界相交）THEN

由COD計算出方向//COD為近方向判決

ELSE

機器人沿方向移動到點Pi+1

i++;}

3.3動作選擇

依據(jù)內(nèi)部狀態(tài)的變化，動作Agent指導(dǎo)機器人該實行什么樣的動作，詳細流程如下