基于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.