謝麗萍，周中余，張春梅，張宏麗

(1.太原科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院，太原 030024;2.新疆69028部隊，烏魯木齊 830006)

傳統(tǒng)人力搜索在面對有地震、煤礦坍塌等災(zāi)害現(xiàn)場以及有爆炸物存在、有害或有毒氣體泄漏等事故現(xiàn)場時，顯得力不從心。而群機器人目標(biāo)搜索是一種在環(huán)境惡劣條件下高效安全的定位潛在目標(biāo)的一種有效策略[1]。相對于傳統(tǒng)人力搜索，群機器人搜索安全系數(shù)高、搜索效率高、使用成本低。群機器人目標(biāo)搜索根據(jù)自身攜帶的傳感器對目標(biāo)發(fā)出的各種信號進行檢測，按照某種控制策略方法定位潛在目標(biāo)。群機器人在未檢測到目標(biāo)信號之前的搜索被稱為發(fā)現(xiàn)目標(biāo)線索的全局搜索階段，在檢測到目標(biāo)信號以后的搜索被稱為定位目標(biāo)的局部搜索階段。在定位目標(biāo)的局部搜索階段，有梯度搜索法、微粒群算法等作為搜索控制方法。

擬態(tài)物理學(xué)優(yōu)化算法(Artificial Physics Optimization，APO)是一種新提出的基于種群的隨機優(yōu)化算法[2]。該算法受物理規(guī)律啟發(fā)，基于擬態(tài)物理學(xué)基本框架設(shè)計。該算法通過模擬不同適應(yīng)值的個體之間存在引力或斥力，整個種群在這種引斥力的作用下運動，逼近更好的適應(yīng)值區(qū)域。APO算法的研究主要包括:個體間的不同作用力計算表達式[3]，算法的收斂性證明[4]，擴展 APO 算法以及其收斂性證明[5]，矢量APO模型以及混合一維搜索和多維搜索的矢量 APO[6-7]，速度上限的選擇策略[8]以及該算法在約束優(yōu)化方面的應(yīng)用[9]等等。

將APO算法作為群機器人的建模工具，應(yīng)用于群機器人目標(biāo)搜索問題，開發(fā)了基于APO算法的群機器人目標(biāo)搜索仿真系統(tǒng)。本系統(tǒng)設(shè)計的目標(biāo)是提供給研究擬態(tài)物理學(xué)搜索的研究人員一個驗證的研究成果的軟件工具，同時一般用戶也能通過本系統(tǒng)得到合適的搜索策略。本系統(tǒng)主要實現(xiàn)了參數(shù)的靈活設(shè)置，實驗數(shù)據(jù)的統(tǒng)計，實驗結(jié)果報表的生成等功能。

1 基于APO的群機器人目標(biāo)搜索模型

假設(shè)在一個封閉的二維空間內(nèi)，一群機器人在有限時間內(nèi)的尋找目標(biāo)。機器人的規(guī)模大小為Npop.假設(shè)機器人具有全局感知能力，通過廣播通信形式進行交互。群機器人在未檢測到目標(biāo)信號之前，進行螺旋漫游運動。當(dāng)有機器人感知到目標(biāo)信號時，則所有機器人進入?yún)f(xié)作搜索狀態(tài)，即基于APO算法控制機器人運動。

假設(shè)機器人的信號感知強度表達如下:

其中，Dis為傳感器的檢測半徑，P為目標(biāo)信號的發(fā)射能量，η()是呈正態(tài)分布的白噪聲樣本，d是機器人和目標(biāo)間的距離。

第i個機器人的虛擬質(zhì)量mi計算表達式為:

其中，I(Xbest)為最好感知機器人best的感知強度，I(Xi)為第i個機器人感知強度。

借鑒APO算法個體間的的引斥力規(guī)則，建立不同感知強度的機器人間的作用力規(guī)則為:較強感知的機器人受較弱感知的機器人排斥，較弱感知的機器人受較強感知機器人吸引，感知強度最大的機器人吸引其它機器人，而不受其它機器人的排斥;無感知強度的機器人無作用力施加于其它機器人;有感知強度的機器人吸引無感知強度的機器人。

機器人間的虛擬作用力計算表達式為:

任意兩個機器人的連續(xù)運動可用多個極小的離散時間片斷△t內(nèi)的位移量△X近似表示。令第i個機器人在第 t時刻的速度為 Vi(t) =(vi，1(t)，vi，2(t))，位置為 Xi(t) =(xi，1(t)，xi，2(t))，則第 i個機器人的速度和位置的迭代方程如下:

2 仿真系統(tǒng)的模型設(shè)計

2.1 系統(tǒng)用例模型設(shè)計

仿真系統(tǒng)的核心功能是對APO群機器目標(biāo)搜索算法的驗證，以及借助本系統(tǒng)對APO群機器目標(biāo)搜索算法進行研究。與此同時，第三方人員也希望通過此系統(tǒng)得到一個搜索方案，并在本系統(tǒng)上進行方案的模擬。

由以上三點根本目標(biāo)分析系統(tǒng)的基本業(yè)務(wù)用例為以下所述:

該系統(tǒng)主要有三個業(yè)務(wù)參與者，分別為:系統(tǒng)管理員、實驗員、一般用戶。

系統(tǒng)管理員向系統(tǒng)添加新的用戶及分配權(quán)限并把賬號及密碼告知用戶，定期維護系統(tǒng)，查看用戶使用系統(tǒng)情況，刪除用戶賬號以及相應(yīng)的實驗數(shù)據(jù);退出系統(tǒng)。

實驗員在系統(tǒng)管理員申請得知系統(tǒng)賬號及初始密碼;實驗員通過賬號登陸系統(tǒng);實驗員進行算法模擬(①設(shè)置參數(shù)，②觀察搜索過程，③多次實驗，查看參數(shù)對搜索系統(tǒng)的影響);實驗員管理歷史實驗數(shù)據(jù);退出系統(tǒng)。

一般用戶在系統(tǒng)管理員申請得知系統(tǒng)賬號及初始密碼;瀏覽實驗員的實驗數(shù)據(jù);選取實驗員的設(shè)定參數(shù)進行模擬搜索行為;退出系統(tǒng)。

根據(jù)業(yè)務(wù)流程提煉出以下基本用例:

U1登陸系統(tǒng);U2系統(tǒng)管理員登陸系統(tǒng);U3實驗員登陸系統(tǒng);U4一般用戶登陸系統(tǒng);U5用戶管理;U6添加用戶;U7刪除用戶;U8退出;U9刪除實驗數(shù)據(jù);U10保存實驗數(shù)據(jù);U11按單參數(shù)搜索實驗數(shù)據(jù);U12設(shè)置搜索實驗參數(shù);U13模擬搜索實驗;U14修改個人資料;U15按實驗員姓名搜索實驗數(shù)據(jù);U16選擇最佳實驗參數(shù)。

在系統(tǒng)基本用例的基礎(chǔ)上，繪制系統(tǒng)用例圖，如圖1所示。

圖1 系統(tǒng)用例圖Fig.1 Case diagram of the system

2.2 系統(tǒng)的對象模型設(shè)計

根據(jù)需求模型和系統(tǒng)需求模型抽象出對象模型，初步確定以下類。

CUser(用戶:包含賬號、密碼);CPrament(實驗參數(shù):實驗參數(shù)對象);CResult(實驗結(jié)果:實驗結(jié)果對象);CSearch(搜索算法);CDatabase(數(shù)據(jù)庫);CRobot(機器人);

考慮到系統(tǒng)的可復(fù)用性，運用設(shè)計模式中的工廠模式對搜索模塊(由CSearch類和CRobot類組成)進行設(shè)計，添加 IRobot類，CRobotFactory類，CGlobalRobot類。

CSearch類是搜索算法模塊向外的接口，也是算法的控制器。該類的主要方法介紹如下:

CSearch(CParament*mpParam，CResult*result)只能通過傳遞Cparament指針和CResult指針來構(gòu)造;calBestRobot()計算每代群機器人的最優(yōu)個體，并且更新虛擬機器人的值;productRobot()根據(jù)參數(shù)中的機器人個數(shù)，以及機器人，實例化一個機器人工廠類，產(chǎn)生相應(yīng)數(shù)量的機器人個體，保存在mRobotList容器中;search(CDC*pDC)方法進行APO算法的調(diào)度，并且通過枚舉每代群機器人的相應(yīng)坐標(biāo)，在設(shè)備環(huán)境CDC中打印一個小矩形來表示該機器人現(xiàn)在所在的坐標(biāo);IsEnd()方法通過判斷所有機器人與虛擬機器人的位置是否小于一個臨界值來確定是否結(jié)束搜索過程。

IRobot類是機器人個體的抽象類，它的方法聲明了機器人類對控制器類的接口。

CRobot類繼承IRobot，定義了機器人對象共有的方法和屬性。

CGlobalRobot類繼承于 Crobot，它定義了全局感知環(huán)境下的機器人個體計算感知度，計算質(zhì)量，計算速度，更新位置的特定方法。

仿真系統(tǒng)的算法模塊的類圖，如圖2所示。CSearch向業(yè)務(wù)層屏蔽掉了算法的實現(xiàn)細節(jié)。大大降低了系統(tǒng)模塊間的耦合度。

圖2 全局搜索的群機器人類圖Fig.2 The class diagram of swarm robots with global search mode

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

該仿真系統(tǒng)將會部署在局域網(wǎng)中，所以網(wǎng)絡(luò)部署采用C/S模型。在局域網(wǎng)中部署多臺客戶機，并且在局域網(wǎng)中部署一臺裝有SQL2000的主機充當(dāng)服務(wù)器，客戶機向遠程數(shù)據(jù)庫同步數(shù)據(jù)。

該系統(tǒng)采用軟件開發(fā)經(jīng)典的三層分層方式進行分層，分別為:表示層、控制層和數(shù)據(jù)連接層。表示層由MFC框架類組成，包括登陸、用戶管理、數(shù)據(jù)管理、參數(shù)設(shè)置、實驗結(jié)果、視圖這些窗口類組成;控 制 層 主 要 由 CParament、CSearch、IRobot、CFarctory、CResult等組成;數(shù)據(jù)連接層只有個一個CConnectDB類。系統(tǒng)結(jié)構(gòu)圖如圖3所示。

圖3 系統(tǒng)分層圖Fig.3 Layered graph of the system

2.4 參數(shù)靈活設(shè)置設(shè)計

進行仿真實驗時要求系統(tǒng)提供參數(shù)的靈活設(shè)置。設(shè)計系統(tǒng)接受兩種輸入?yún)?shù)方式，鍵盤輸入和鼠標(biāo)拖動方式輸入，對于機器人初始范圍和目標(biāo)位置這兩個參數(shù)即可以通過直接輸入(如圖4左上角所示)的方式精確設(shè)定參數(shù)，也可以通過鼠標(biāo)拖動的方式進行設(shè)置(如圖4空白區(qū)域所示)。對于不經(jīng)常修改的參數(shù)如機器人引力方位，目標(biāo)強度等參數(shù)設(shè)計為鍵盤輸入的方式進行參數(shù)設(shè)置。

圖4 參數(shù)設(shè)置界面Fig.4 Interface of setting parameters

通過對WM_LBUTTONDOWN(鼠標(biāo)左鍵按下的消息)進行時間處理獲知矩形區(qū)域的左上角坐標(biāo)，以及對WM_LBUTTONUP(鼠標(biāo)左鍵松開)事件處理，獲知矩形區(qū)域的右下角坐標(biāo)。這樣就能通過鼠標(biāo)來設(shè)定群機器人的初始范圍。

2.5 動態(tài)搜索過程顯示實現(xiàn)方法

在視圖類的OnDraw函數(shù)中，實例化CSearch對象，調(diào)用CSearch類的search(CDC*pDC)方法開始進行APO算法。每次群機器人位置更新，根據(jù)機器人的位置，在pDC所指向的設(shè)備環(huán)境中繪制一個3像素寬的矩形，來表示機器人個體。在整過算法計算過程中，不停在屏幕上繪制新的矩形群，矩形的軌跡反應(yīng)了群機器人的搜索過程。

2.6 試驗數(shù)據(jù)對比實現(xiàn)方法

圖5 實驗結(jié)果對比Fig.5 Comparison of the experiment results

在實驗結(jié)果窗口在初始化過程中即OnInitialUpdate()函數(shù)中實例化CConnectDB類，調(diào)用函數(shù)HandleResult(ID，systime，result，handle)查詢出所有參數(shù)并保存到結(jié)果窗口類的成員變量中，對查詢出的實驗數(shù)據(jù)及當(dāng)次實驗數(shù)據(jù)在同一界面進行顯示。當(dāng)用戶點擊了窗口的下拉框，在對應(yīng)的時間處理中獲知用戶具體選擇的數(shù)據(jù)(實驗時間)，彈出新的對話框(歷史參數(shù)對話框類)，并且調(diào)用 Searchtime(username，time)函數(shù)取得所對應(yīng)的實驗結(jié)果，然后賦值給對應(yīng)的文本編輯框，最后調(diào)用窗口的Update-Data(FLASE)函數(shù)，顯示新數(shù)據(jù)，效果如圖5所示。

3 仿真系統(tǒng)實現(xiàn)

3.1 開發(fā)環(huán)境

該系統(tǒng)在Visual Studio 6.0開發(fā)環(huán)境下，基于MFC(Microsoft Foundation Classes)框架開發(fā)。使用SQL Server 2000作為系統(tǒng)的數(shù)據(jù)庫。該仿真系統(tǒng)能在Windows 2000及以上操作系統(tǒng)上正常運行。

3.2 系統(tǒng)實現(xiàn)

進行一次仿真實驗，首先在圖4中的左側(cè)窗口進行參數(shù)設(shè)置，設(shè)置完成后，在一個狹小的矩形區(qū)間內(nèi)出現(xiàn)隨機分布的機器人，點擊“開始搜索”按鈕。系統(tǒng)在空白區(qū)域開始繪制，搜索的軌跡圖如圖6所示。為了驗證仿真系統(tǒng)的有效性，分別設(shè)置群機器人的初始范圍在搜索空間的左上角如圖7(a)所示和初始范圍在搜索空間的右下角的情況下的搜索軌跡如圖7(b)所示。

4 結(jié)束語

圖6 搜索軌跡圖Fig.6 Search track

群機器人搜索是一種安全高效的定位潛在目標(biāo)的有效方案。群機器人仿真系統(tǒng)將APO算法作為群機器人的建模工具，應(yīng)用于群機器人目標(biāo)搜索問題。本仿真系統(tǒng)設(shè)計的目標(biāo)是提供給研究擬態(tài)物理學(xué)搜索的研究人員一個驗證研究成果的實驗平臺。該系統(tǒng)在MFC框架下實現(xiàn)，系統(tǒng)運用面向?qū)ο筌浖_發(fā)的原理進行開發(fā)，分別進行了系統(tǒng)模型及對象模型的分析與設(shè)計，并且運用設(shè)計模式中的工廠模式對機器人類進行了重構(gòu)。本系統(tǒng)主要實現(xiàn)了參數(shù)的靈活設(shè)置，實驗數(shù)據(jù)的統(tǒng)計，實驗結(jié)果對比和動態(tài)演示搜索過程等功能。

圖7 不同初始分布下的群機器人搜索軌跡Fig.7 Search track of swarm robots with different initial distributions

[1]李進，薛松東，曾建潮，等.群機器人目標(biāo)搜索中的通信模式研究[J].太原科技大學(xué)學(xué)報，2011，32(4):264-268.

[2]謝麗萍，曾建潮.基于擬態(tài)物理學(xué)方法的全局優(yōu)化算法[J].計算機研究與發(fā)展，2011，48(5):848-854.

[3]XIE LIPING，TAN YING，ZENG JIANCHAO，et al.Artificial physics optimization:a brief survey[J].International Journal of Bio-Inspired Computation，2010，2(5):291-302.

[4]XIE LIPING，TAN YING，ZENG JIANCHAO，et al.The convergence analysis of artificial physics optimisation algorithm[J].Int.J.of Intelligent Information and Database Systems，2011，5(6):536-554.

[5]XIE LIPING，ZENG JIANCHAO，RICHARD A FORMATO.Convergence Analysis and Performance of the Extended Artificial Physics Optimization Algorithm[J].Applied Mathematics and Computation，2011，218:4000-4011.

[6]XIE LIPING，ZENG JIANCHAO，CAI XINGJUAN.A Hybrid Vector Artificial Physics Optimization with Multi-Dimensional Search Method[C]//The 2nd International Conference on Innovations in Bio-inspired Computing and Applications(IBICA-2011)，Shenzhen:2011.

[7]YANG G J，XIE L P，TAN Y，et al.A Hybrid Vector Artificial Physics Optimization with One-Dimensional Search Method[C]//International Conference on Computational Aspects of Social Networks，Taiyuan，China:2010.

[8]XIE LIPING，TAN YING，ZENG JIANCHAO.A Study on the Effect of Vmax in Artificial Physics Optimization Algorithm with High Dimension[C]//The Second International Conference of Soft Computing and Pattern Recognition，Dalian:2011.

[9]XIE LIPING，ZENG JIANCHAO.A Hybrid Vector Artificial Physics Optimization for Constrained Optimization Problems[C]//The First International Conference on Robot，Vision and Signal Processing，Taiwan，Kaohsiung:2011.