协同任务规划仿真实验系统的设计与实现

张 佳 辛 斌 杜 鑫 曹志强

(1. 北京理工大学 自动化学院, 北京 100081)

(2. 中国航天科技工业集团, 北京 100036)

人才培养是新工科建设中最重要、最核心的任务。依据新工科培养目标的特点[1],学生在掌握专业理论知识的基础上,必须加强实验教学,优化实验教学体系[2]。利用各种新技术建设和完善实验平台,是新工科实践教育发展的重要基础和保障[3]。虚拟仿真实验教学是国家信息化教育战略的重要实践内容[4]。与实物实验相比,虚拟仿真实验在实验教学方面具有人机交互性好、利用率高、易维护等诸多优点。

多智能体系统协同任务规划[5-6]是当前人工智能[7]研究的热点问题。随着科技成果向教学转化的不断深入,多智能体系统协同任务规划的相关知识在高校教学中已经逐步渗透至研究生和本科生,出现在控制专业的课堂上,但是配套的实验课程却屈指可数。机器人、无人机等设备价格昂贵,同时这类设备对实验场地要求较高,极易发生碰撞、坠毁等事故,不易于在高校针对学生开展大范围的实物实验,也不易于在实体实验室里同时开展各种不同研究方向的多智能体协同任务规划实验。因此,借助仿真手段是开展多智能体分布式协同任务规划教学实验的最佳途径。

在目前“新工科”建设的形势下,我国高校缺乏对多智能体系统协同任务规划方面高层次人才培养的必要实验手段,实验研究非常薄弱,亟需开展这方面的工作。为了研究出适合硕士生及本科高年级学生开展的多智能体协同任务规划的虚拟仿真实验环境,本文开展了相关工作。开发了可以进行多智能体协同任务规划的仿真实验系统,可以面向多智能体的任务分配和路径规划[8]开展仿真实验,为机器人控制相关的研究人员提供了一种便于开展相关教学和探索研究的工具和手段,为相关实验教学提供可视化、友好人机交互的仿真实验系统。同时,也为学生开展探究性学习、自主实验和创新实践提供先进手段和开放平台。

1 “智能体-环境-任务”模块化建模

为了让实验者能够在本实验系统上开展多智能体协同任务规划策略的实验研究,在构建仿真系统时需要对智能体所处的任务环境以及任务进行建模,为协同任务规划提供依据。

智能体、环境与任务这三个要素是仿真系统的基础,三者之间需要通过高效、统一的接口进行互通互联。因此,应考虑这三个要素之间的协同建模问题。单个智能体通过通信模块与环境、任务及其他智能体进行信息交互,因此需要按照图1所示模型构架设计三个基本要素之间的接口标准及数据传输的参数。

图1 智能体的信息传递

多智能体分布式协同的基础是智能体之间的信息交互,因此图1中单个受控智能体通过通信与交互模块作为接口,与环境信息、其他智能体信息以及任务信息进行交互。信息通过传感器、控制器、执行器进而传送给受控智能体。

1.1 智能体建模

智能体模型应具有可组合性,方便实验者根据不同的协同任务有针对性地选取仿真组件,通过多个组件的组合实现所需多智能体的功能。以仿真系统中模块化、可组合的智能体为例,至少应具备传感器模块、控制模块、执行模块和通信模块这四种基本模块。每个智能体都是由多个基本模块构成的,将不同的基本模块进行组合形成不同种类的智能体模型。

为了实现模块组合后的可用性,应首先确定智能体模块的内部逻辑然后将其封装,设计输入、输出接口与外界交互。使用者可通过输入接口改变模块内部参数,提高模块适用性。输出接口与其他模块的输入接口连接,负责信息传递,如图2所示。模块逻辑主体负责实体流和信息流的逻辑流转、分配、再处理等过程,与输出接口模块相连接,将信息或任务输入至特定接口。

图2 模块封装与信息传递

由于智能体的模块连接方式已基本确定,如对于地面智能体来说,测距传感器模块与地面智能体基本模块必须连接,故输出接口已写入模块连接语句。但由于模型中同类型的模块可能不止一个,例如有的智能体需要连接激光测距仪,有的智能体需要连接超声波传感器,故对每个智能体实际需要连接的模块需进一步确定。在输入接口中设计模块编号参数,同种类型的模块编号不同,通过输入接口写入模块自身的编号和与之连接的模块编号以完成模块柔性连接,如图3所示。

图3 可组合模块的柔性连接

1.2 任务环境建模

任务环境对智能体的任务执行能力、移动能力、通信能力等能力特征有至关重要的影响。本实验系统所实现的任务环境建模主要针对地图尺寸大小、障碍物数量和障碍物位置等。

1.3 任务建模

当智能体被分配给某项任务时,该任务通常可以看作多项基础子任务的集合,其中第i项任务对应的基础子任务集合记为Mi={mi1,mi2,…,mij},j为基础子任务的数量,基础子任务中包含的属性有:任务规模、任务处理的时间要求、任务的区域位置、任务的优先级以及任务需求下智能体之间的通信交互频率。

任务规模由所需的智能体数量进行表征。基础子任务所需时间要求通过时间窗口进行描述,记基础子任务mij的时间需求为mtij,实际任务完成时间为rtij,当mtij>rtij时认为任务被成功处理。任务位置是任务区域的中心坐标位置,以坐标形式表示,mij的任务区域位置可表示为(xij,yij)。基础子任务的优先顺序表示为基础子任务执行的序列关系,基础子任务间可能存在串行或并行关系,不允许存在循环链接,因此基础子任务间的序列关系可采用图表示。

智能体协同执行任务过程中,通常需要多种智能体具备的不同能力相互配合。因此,采用能力需求矢量表示一个多基础子任务的能力需求。对一次具体的任务,基础子任务在能力需求上与全部智能体具备的能力分类相一致,即矢量维度与智能体能力划分种类相同。记第i项父类任务的第j项基础子任务能力需求向量Dij=[tij1,tij2,…,tijn],其中tijp表示第j项基础子任务对第p种能力的需求,n为能力的种类。

相应地,每种智能体具有不同的能力,代表其适合完成某项任务的情况。每类智能体具有的不同能力由能力向量C表示,Ck=[mk1,mk2,…,mkn],其中mkp表示智能体k的第p项能力,当mkp>0时,表示智能体k具备该项能力,否则智能体k不具有该项能力,即不适于参加某项基础任务。

2 仿真系统架构

为了让学生能够更加直观和方便地开展多智能体协同任务规划仿真实验,本文基于AnyLogic软件进行了二次开发,设计并实现了一个多智能体仿真实验系统。用户可以选择不同的任务场景,控制和调整仿真参数,实时观察仿真过程、任务状态等,根据实验结果反馈更好地理解算法并改进算法。整个系统主要包含以下几个模块:

2.1 场景设计模块

多智能体协同任务规划主要包括任务分配和路径规划两大类问题,两类问题涉及的智能体主体、环境参数和任务类型都不相同。本文中的实验系统设计了任务分配和全覆盖路径规划两个场景。

2.2 环境设计模块

环境设计模块包括地图尺寸大小、障碍物数量和障碍物位置等。用户可以简单地通过交互式方法,例如鼠标点击、滑动等操作,自定义不同等环境参数,测试算法在不同环境约束下的性能。该模块是仿真系统的重要组成部分,是算法仿真的前提和基础。

2.3 参数设计模块

仿真系统中任务和智能体的参数都能自定义设置。智能体是任务执行的主体,用户可以根据需求自定义智能体的数量、初始位置、运动速度、搜索半径、通讯半径和能力大小等。任务参数则包括任务数量、初始位置和危险程度等。

2.4 综合演示模块

综合演示模块是多智能体协同任务规划仿真系统的核心模块,可根据用户预设的场景和参数对算法进行仿真,提供可视化的仿真界面。仿真过程提供二维或三维动画,可以实时观察到智能体的位置、运动状态、哪些区域任务未被完成、环境中障碍物的位置等信息。直观、清晰的仿真过程更有利于用户使用系统。用户还能调整仿真运行的速度,随时暂停观察现象和参数变化,并导出相关数据。

2.5 数据导出模块

系统在仿真过程中产生的所有数据均支持导出分析,包括智能体的决策方案,运动路径和任务完成时间等。数据支持导出文本格式或Excel格式,图片则支持JPG格式。该模块能为进一步理解算法、改进算法提供有力数据支持。图4是多智能体协同任务规划仿真系统结构图。

图4 多智能体协同任务规划仿真系统结构图

3 系统仿真实验

圣彼得堡工业大学分布式计算网络研究团队推出的AnyLogic软件是一款运用广泛、技术先进、功能强大的仿真工具,在公共交通建设、城市规划、物流配送、军事作战、策略制定等多方面具有广泛应用。本文的仿真系统设计采用了AnyLogic中基于智能体模型的仿真建模方式,在AnyLogic软件的支撑下可以为学生提供多智能体协同的仿真实验环境。

3.1 面向任务分配场景的仿真实验

实验以森林救火为任务背景。在该任务中,火灾点的火势随时间改变,在起火点刚开始燃烧时,仅需要较少的救援力量即可扑灭火情。随着时间的推移,如果不采取措施,火灾点的火势会逐渐变大,需要更多的救援力量、更长的救援时间才能扑灭。这个复杂任务可以用多点动态集结[9]的统一任务框架进行描述,其中的任务状态或威胁度随环境的改变而变化,是多智能体协同任务规划的一种典型场景。在该任务中,多个位于不同位置的智能体通过协作、通信确定目标任务点,并向选定任务点集结,到达任务点的有效作用范围后向其施加影响,使得每个任务的状态或威胁度降到某个阈值以下,最终完成任务。

设区域中有M个智能体和N个任务。现以任务i和智能体k为例,任务状态参数si表示任务的紧急或危险程度。状态值参数越大,表示任务越紧急。以森林救火为任务背景,每个着火点是一个任务,任务点的火势状态将采取非线性变化形式,具体变化形式为指数形式。即任务点的模型为:

(1)

其中i=1,2,...,N,si(t+Δt)表示第i个任务点在t+Δt时刻的状态值,λi(t)表示任务点i在t时刻的状态变化率。

该多点动态集结任务的目标是让所有任务状况尽快下降到危险度阈值ε以下,即最快完成全部任务的时间,定义优化准则为

(2)

(3)

(4)

其中,n∈{1,2,…,N},xn(tn(W))是任务n在tn(W)时刻的状态。任务n的状态值下降到阈值 以下的最早时间是任务n的完成时间。

针对上述任务建立了如图5所示的多智能体协作任务规划实验系统。左侧是数据自定义配置区域,可以定义地图环境的大小(包括地图的高度和宽度、是否有障碍物等)、障碍物参数(包括障碍物的坐标和大小)智能体参数(包括智能体的数量、速度和能力值等)和任务参数(任务数量、任务初始化状态值和任务威胁度等)等。仿真系统内置了多张地图,用户可以直接选中希望配置的地图。

图5 任务分配场景

实验中内置了非线性MPDA的两阶段分布式任务分配算法[10]。当仿真程序开始运行后,仿真系统中二维动画和三维动画会实时显示智能体和任务的状态。仿真系统右半侧为数据显示区,可以实时显示智能体和任务的关键行为数据。如图6所示是某时刻数据显示区的放大图。用户可以通过下拉框选择需要查看的智能体或任务的相关信息,包括智能体的任务方案、到达任务时间、离开任务点时间。

图6 任务分配场景数据显示区

智能体按照既定算法执行灭火任务,如图7所示是执行任务过程中第17、49、106和180秒的状态。未被完成的任务标记为蓝色,已完成的任务标记为黄色。随着仿真的进行,任务逐渐完成,到180秒,所有任务均被完成。此时可通过系统数据导出模块,导出仿真相关数据,辅助用户了解多智能体的协作过程,进一步改进或完善算法。

图7 任务分配仿真过程状态截图

3.2 面向路径规划场景的仿真实验

实验以军事搜索为任务背景,在作战环境中,多无人机群对目标区域进行全覆盖搜索,为作战后方提供数据情报,搜索过程中需避开危险区域和敌方基地等。

约束条件为

P1UP2U…UPM=Env

(5)

∀i={1,2,…,M},t∈{1,2,…,T}

(6)

∀i,j={1,2,…,M},t∈{1,2,…,T}

(7)

(8)

(9)

针对上述任务建立了图8的仿真实验场景,通过二维动画实时展现仿真运行进程。首先对地图参数初始化,然后点击“地图栅格化”将环境进行栅格处理,划分完成后设置智能体的参数,初始化全部完成后智能体开始进行全覆盖搜索,在此过程中可以暂停观察现象和查看数据,以便更好地理解算法流程和仿真过程。

图8 全覆盖路径规划场景实时显示区

该实验包含实时显示区、参数设置区和数据显示区三个界面,通过左上角的黄色按钮进行三个界面的切换。在图9的参数设置区,用户可自定义地图的大小,自主配置障碍物的数量、位置和大小。系统中内置了4张环境地图,可通过下拉框进行选择和配置。系统支持自定义智能体的数量和搜索范围,在图9右侧的“设置智能体参数”区域,用户可通过友好的交互界面设置每个智能体的通信范围和速度等参数,以便观察不同配置参数下的实验效果。

图9 全覆盖路径规划场景参数设置区

图10 全覆盖路径规划场景数据显示区

实验中内置了基于混合策略的分布式全覆盖路径规划算法,能够用于解决本实验中的路径规划问题。现按照以下参数对场景进行配置,以显示具体的仿真过程。选择内置1号地图,地图的宽度为13 km,地图的高度为7 km,智能体为3架小型旋翼无人机,智能体初始位置在地图的左上侧,搜索半径为200 m,通讯半径为4000 m,飞行速度是8 m/s。参数配置完成后,仿真系统栅格化后的地图的待搜索栅格数是65×35个,如图11。

图11 环境栅格化示意图

覆盖搜索过程中对仿真过程中对第273和297 min这2个时刻进行截图,如图12。其中蓝色、红色和黄色的线条表示3架无人机的运动路径。随着仿真时间的进行,区域覆盖率逐渐增加。第297 min,区域实现了全覆盖。

图12 全覆盖仿真过程截图(2个时刻)

3 结语

论文设计了多智能体协同任务规划仿真实验系统的架构,并基于AnyLogic仿真平台进行了开发,搭建了面向任务分配场景的仿真实验和面向路径规划场景的仿真实验。模块化的实验系统可以让操作者快速完成多智能体在不同环境、任务中的配置,进而把精力集中在协同任务规划方法的实验中,有利于激发学生兴趣,培养实践能力和创新精神。系统具有友好的交互性及可视化仿真功能,有利于加强学生对理论知识的理解和掌握,有利于提高学生的工程能力和创新能力。该系统还可以为研究人员提供多智能体协同任务规划的仿真验证环境,用于验证各关键技术算法的有效性,并与同类算法进行效率对比和分析,具有经济性、开放性、针对性、安全性等优点。