基于APO的群機器人目標搜索仿真系統設計

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

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

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

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

將APO算法作為群機器人的建模工具，應用于群機器人目標搜索問題，開發了基于APO算法的群機器人目標搜索仿真系統。本系統設計的目標是提供給研究擬態物理學搜索的研究人員一個驗證的研究成果的軟件工具，同時一般用戶也能通過本系統得到合適的搜索策略。本系統主要實現了參數的靈活設置，實驗數據的統計，實驗結果報表的生成等功能。

1 基于APO的群機器人目標搜索模型

假設在一個封閉的二維空間內，一群機器人在有限時間內的尋找目標。機器人的規模大小為Npop.假設機器人具有全局感知能力，通過廣播通信形式進行交互。群機器人在未檢測到目標信號之前，進行螺旋漫游運動。當有機器人感知到目標信號時，則所有機器人進入協作搜索狀態，即基于APO算法控制機器人運動。

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

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

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

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

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

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

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

2 仿真系統的模型設計

2.1 系統用例模型設計

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

由以上三點根本目標分析系統的基本業務用例為以下所述:

該系統主要有三個業務參與者，分別為:系統管理員、實驗員、一般用戶。

系統管理員向系統添加新的用戶及分配權限并把賬號及密碼告知用戶，定期維護系統，查看用戶使用系統情況，刪除用戶賬號以及相應的實驗數據;退出系統。

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

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

根據業務流程提煉出以下基本用例:

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

在系統基本用例的基礎上，繪制系統用例圖，如圖1所示。

圖1 系統用例圖Fig.1 Case diagram of the system

2.2 系統的對象模型設計

根據需求模型和系統需求模型抽象出對象模型，初步確定以下類。

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

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

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

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

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

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

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

仿真系統的算法模塊的類圖，如圖2所示。CSearch向業務層屏蔽掉了算法的實現細節。大大降低了系統模塊間的耦合度。

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

2.3 系統體系結構

該仿真系統將會部署在局域網中，所以網絡部署采用C/S模型。在局域網中部署多臺客戶機，并且在局域網中部署一臺裝有SQL2000的主機充當服務器，客戶機向遠程數據庫同步數據。

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

圖3 系統分層圖Fig.3 Layered graph of the system

2.4 參數靈活設置設計

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

圖4 參數設置界面Fig.4 Interface of setting parameters

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

2.5 動態搜索過程顯示實現方法

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

2.6 試驗數據對比實現方法

圖5 實驗結果對比Fig.5 Comparison of the experiment results

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

3 仿真系統實現

3.1 開發環境

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

3.2 系統實現

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

4 結束語

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

群機器人搜索是一種安全高效的定位潛在目標的有效方案。群機器人仿真系統將APO算法作為群機器人的建模工具，應用于群機器人目標搜索問題。本仿真系統設計的目標是提供給研究擬態物理學搜索的研究人員一個驗證研究成果的實驗平臺。該系統在MFC框架下實現，系統運用面向對象軟件開發的原理進行開發，分別進行了系統模型及對象模型的分析與設計，并且運用設計模式中的工廠模式對機器人類進行了重構。本系統主要實現了參數的靈活設置，實驗數據的統計，實驗結果對比和動態演示搜索過程等功能。

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

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

[2]謝麗萍，曾建潮.基于擬態物理學方法的全局優化算法[J].計算機研究與發展，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.