技术领域
本发明涉及群体智能启发式算法领域,具体涉及一种基于最大角聚集策略 的多智能体控制方法。
背景技术
由于在自然界中发现的群智能解决方法十分有效,因此仿生算法是近些年 的研究热点,包括蚁群算法,鸟群算法和控制智能体算法等。受自然界的启发, 群智能系统可以描述为系统中相对基本的个体之间的相互作用。群智能系统中 的多智能体控制是一个复杂的问题,可以分为高层次的路径规划和低层次的单 智能体动力学。多智能体控制是一种通过控制智能体(强智能体)控制一群简 单智能群体(弱智能体)的控制方法。
多智能体控制的一个典型应用场景就是牧羊犬赶羊,这样的场景在现实生 活中很常见。通常作为简单智能群体的种群的数量成百上千,而控制智能体的 数量很少。控制智能体主要有两个行为:收集种群、驱赶种群到目标点。以驱 赶为例,即使用一只或者多只控制智能体,将一群在空间中随机分布的简单智 能体,驱赶到一个指定的目标点。控制智能体驱赶问题背后的原理,其实就是 一种控制智能体对简单智能群体的控制。多智能体控制技术有很多应用场景, 比如:使用机器人进行放牧、人群控制、对于泄露石油清理、保护飞机免受鸟 类的袭击、救灾和救援行动、管理群居野生动物、保护微生物、军事上无人车辆在战场的控制。
现有的传统模型中,典型的有SPPL模型,该模型在执行收集行为时,简单 选择种群最外面的简单智能体作为收集目标点,而没有考虑控制智能体的位置 和简单智能群体的全局中心的位置。因此在某些情况下将会导致控制智能体来 回移动,影响最后的驱赶效率。因此该模型如果用于实际的机器人控制等应用 场景,可能由于算法效率低下的原因,导致达不到现实中的实时性要求。
发明内容
本发明的目的在于克服现有技术中所存在SPPL模型等现有技术效率低,不 能满足多智能体控制的实时性要求的不足,提供一种基于最大角聚集策略的多 智能体控制方法。
为了实现上述发明目的,本发明提供了以下技术方案:
一种基于最大角聚集策略的多智能体控制方法,根据各简单智能体的位置 和控制智能体的位置判断控制智能体的行为状态,包括以下步骤:
当存在一简单智能体与简单智能群体的全局中心的距离大于预设的简单智 能群体聚集程度f(N)时,触发控制智能体收集行为;控制智能体选择群子集内 第一角度最大的简单智能体作为目标点去聚集;所述第一角度为控制智能体与 全局中心的连线和控制智能体与简单智能体的连线的夹角度数;
当所有简单智能体和简单智能群体的全局中心的距离都小于或等于预设的 简单智能群体聚集程度f(N)时,触发控制智能体驱赶行为;控制智能体移动, 并控制着简单智能群体向目标点推进,当简单智能群体到达目标区域时,完成 控制任务。
优选地,所述简单智能体的下一个位置根据简单智能体的当前位置和下一 步要移动的方向和距离获得,简单智能体的下一个位置的位置向量A′
其中,A
优选地,所述下一步要移动的方向根据外部排斥力
其中,h为惯性力的权重;c为局部中心吸引力的权重;ρ
优选地,所述外部排斥力
其中,S表示控制智能体的位置向量,A
所述内部排斥力
其中,A
所述局部中心吸引力C
C
其中,LCM
优选地,所述控制智能体收集行为的执行方式采用未考虑目的地的收集行 为方式MAM,此时所述群子集Ω是整个简单智能群体。
优选地,所述控制智能体收集行为的执行方式采用考虑目的地的收集行为 方式DMAM;此时以控制智能体与全局中心的连线作为基准线;若目的地在基 准线上,则群子集Ω是整个简单智能群体;若目的地在基准线的一侧,则群子集 Ω是基准线另一侧的简单智能体的集合。
优选地,在收集行为时,所述控制智能体的控制方式如下所示:
Ω={a
(7)
Ω={a
(8)
上述公式(7)表示目的地D在基准线左侧时,选择群子集Ω为基准线右边 的简单智能体的集合;公式(8)表示目的地D在基准线右侧,选择群子集Ω为 基准线左边的简单智能体的集合;公式(9)使用向量夹角公式求解群子集Ω中 每个简单智能体的第一角度,以选择群子集Ω中第一角度最大的简单智能体
优选地,驱赶行为时,控制智能体的控制方式如下所示:
公式(12)表示控制智能体将向驱赶点P
优选地,简单智能群体聚集程度的计算公式如下所示:
其中,r
与现有技术相比,本发明的有益效果:基于最大角聚集策略执行收集行为, 考虑了控制智能体的位置和简单智能群体的全局中心的位置,避免了简单选择 种群最外面的简单智能体作为收集目标点时控制智能体来回移动,提高了将简 单智能群体驱赶到指定的目的地的效率,以满足多智能体控制方法应用于实际 的机器人控制时对实时性的要求。
附图说明:
图1为本发明示例性实施例1的多智能体的位置分布图;
图2为本发明示例性实施例1的控制智能体行为触发条件示意图;
图3为本发明示例性实施例1的基于最大角聚集策略执行收集行为的示意 图;
图4为本发明示例性实施例1的DMAM收集行为方式下目的地在基准线左 边的示意图;
图5为本发明示例性实施例1的DMAM收集行为方式下目的地在基准线右 边的示意图;
图6为本发明示例性实施例2的参数r
图7为本发明示例性实施例2的SPPL模型运行轨迹;
图8为本发明示例性实施例2的MAM模型运行轨迹;
图9为本发明示例性实施例2的DMAM模型运行轨迹;
图10为本发明示例性实施例2的SPPL模型和MAM模型在不同种群数量 下时间步的变化示意图;
图11为本发明示例性实施例2的DMAM模型和MAM模型在不同种群数 量下时间步的变化示意图。
具体实施方式
下面结合试验例及具体实施方式对本发明作进一步的详细描述。但不应将 此理解为本发明上述主题的范围仅限于以下的实施例,凡基于本发明内容所实 现的技术均属于本发明的范围。
实施例1
本实施例提供一种基于最大角聚集策略的多智能体控制方法,根据各简单 智能体的位置和控制智能体的位置判断控制智能体的行为状态,包括以下步骤:
当存在一简单智能体与简单智能群体的全局中心的距离大于预设的简单智 能群体聚集程度f(N)时,触发控制智能体收集行为;控制智能体选择群子集内 第一角度最大的简单智能体作为目标点去聚集;所述第一角度为以控制智能体 为顶点,控制智能体与全局中心的连线为始边,控制智能体与简单智能体的连 线为终边的角的角度值;
当所有简单智能体和简单智能群体的全局中心的距离都小于或等于预设的 简单智能群体聚集程度f(N)时,触发控制智能体驱赶行为,控制智能体移动, 并控制着简单智能群体向目标点推进,当简单智能群体到达目标区域时,完成 控制任务。
本实施例中,多智能体控制过程中,当控制智能体进行收集或驱赶行为时, 简单智能体会做出被动反应。本申请基于最大角聚集策略执行收集行为,考虑 了控制智能体的位置和简单智能群体的全局中心的位置,避免了简单选择种群 最外面的简单智能体作为收集目标点时控制智能体来回移动,提高了将简单智 能群体驱赶到指定的目的地的效率,以满足多智能体控制方法应用于实际的机 器人控制时对实时性的要求。
本实施例中,控制智能体需要根据目的地和简单智能群体的状态(比如群 体的分散程度),做出下一次的控制行为。在简单智能群体中,每个简单智能体 之间、简单智能体与控制智能体之间都是有相互作用。这在自然界是非常常见 的,群居动物靠近同伴并远离潜在危险。如图1所示,综合起来看,简单智能 体下一个位置主要是由外部排斥力
1.外部排斥力
简单智能体需要和控制智能体保持一定距离,因此当控制智能体的位置与 简单智能体的位置二者之间的距离小于控制智能体的感知距离r
2.内部排斥力
简单智能体群体内部也有排斥力。当在交互距离r
3.局部中心吸引力
距离简单智能体a
C
4.惯性力
受惯性力H
5.噪声
噪声代表了简单智能体的随机行为,表示简单智能体可能向任意一个方向 随机移动,使用∈
简单智能体的下一个位置根据简单智能体的当前位置和下一步要移动的方 向和距离获得。具体的,A
下一步要移动的方向根据外部排斥力、内部排斥力、局部中心吸引力、惯 性力以及噪声等五个向量进行计算;上述5个向量归一化为单位向量后,线性 加权组合得到下一步要移动的方向H′
其中,h为惯性力的权重;c为局部中心吸引力的权重;ρ
本实施例中,控制智能体的任务就是将简单智能体全部引导向目的地,因 此其主要有两种行为:收集和驱赶。如图2所示,为了便于描述,定义如下符 号:
简单智能群体聚集程度:f(N)
简单智能群体的全局中心GCM的位置:
局部中心位置LCM
简单智能体的位置:A
控制智能体的位置:S
目的地:D
简单智能体与全局中心的距离:d
群子集:Ω
简单智能体的数量:N
控制智能体收集以及驱赶两种行为的触发条件如下所示:
如图2所示,比较简单智能体和全局中心GCM的距离最大值d
具体的,本发明根据是否考虑目的地位置的方位,将收集行为的执行方式 分为两种:一是未考虑目的地的收集行为方式MAM;二是考虑目的地的收集行 为方式DMAM。
收集行为的执行方式采用未考虑目的地的收集行为方式MAM时:群子集Ω 是整个简单智能群体。
如图4或图5所示,收集行为的执行方式采用考虑目的地的收集行为方式 DMAM时:控制智能体与全局中心的连线作为基准线,若目的地在基准线上, 则群子集Ω是整个简单智能群体;若目的地在基准线的一侧,则群子集Ω是基准 线另一侧的简单智能体的集合。
一般情况下,我们希望收集时,收拢趋势能够朝向目的地,因此多采用考 虑目的地的收集行为方式DMAM。将控制智能体与全局中心的连线作为基准线, 如图4所示,如果目的地在基准线左边,则群子集Ω为基准线右边的简单智能体 的集合,在基准线右边的子集中寻找第一角度最大的简单智能体作为目标点去 聚集;如图5所示,如果目的地在基准线右边,则在基准线左边的子集中寻找 第一角度最大的简单智能体作为目标点去聚集。即基于最大角距离的聚集策略 执行收集行为,考虑了控制智能体的位置、全局中心的位置和目的地的位置, 以提高控制效率。
具体的,控制智能体的控制方式如下所示:
Ω={a
Ω={a
上述公式(7)表示目的地在基准线左侧时,选择群子集Ω为基准线右边的 简单智能体的集合;公式(8)表示目的地在基准线右侧,选择群子集Ω为基准 线左边的简单智能体的集合;公式(9)使用向量夹角公式求解群子集Ω中每个 简单智能体的第一角度,以选择群子集Ω中第一角度最大的简单智能体
本实施例中,当所有简单智能体和GCM的距离都小于f(N)时,就触发驱 赶行为。在驱赶状态下,考虑目的地和全局中心的相对位置。通常选择在沿着 全局中心和目的地的连线上,在群体的后方选取控制智能体的下一个驱赶点(如 图1的位置P
公式(12)表示控制智能体将向驱赶点P
实施例2
控制智能体的目标是控制简单智能群体向目的地移动,直到所有的简单的 智能体都在目标区域位置。当简单智能群体太分散的时候,控制智能体就对群 进行收集;当简单智能体全部都收集在一起时,控制智能体把种群向着目标点 进行驱赶。其中如何收集和如何驱赶的策略是讨论的重点。本实施例将分别对 比传统的SPPL模型与本发明提出的MAM与DMAM模型,以验证本发明的有 效性。
所有的算例都在有12GB内存、2.9GHz因特尔CPU、64位windows操作系 统上运行。模拟与数据分析采用Python3.7、标准图形化接口工具套件Tkinter。
基于最大角聚集策略的多智能体控制方法(MAM和DMAM)的仿真过程 包括以下步骤:
1初始设置
整个模拟区域是一个大小为L×L的区域,整个区域处于完全封闭状态, 左上角为坐标的原点。将会在该区域随机生成N个点,用来表示简单智能群体 中的N个简单智能体。目标区域是整个区域右下角的l×l的矩形。在所有模拟 开始的时候,控制智能体总是从目标区域开始工作。
相关参数设置如表1所示:
表1基于最大角聚集策略的多智能体控制方法实验的初始参数
2探索r
简单智能体之间的交互距离r
由于参数r
结论:当r
3结果分析
实验运行了SPPL、MAM、DMAM模型来执行控制任务,每个模型具有相 同的参数配置(如表1)、起始环境状态、相同动作规则作用于控制智能体和简单 智能体的行为(除控制智能体的收集行为外)。SPPL、MAM、DMAM模型运行 轨迹分别如图7、9、10所示:
从图中可以看出每个模型都成功地完成任务,并且在任务初始时,每个模 型中的控制智能体都倾向于将空间中散乱分布的简单智能体聚集起来,直到种 群到达一定的聚集程度;在这之后,控制智能体将会在聚集和驱赶两种状态之 间切换,将种群赶向右下角的目的地。从SPPL模型的图中可以明显看出,该模 型仅仅选择最远的简单智能体作为聚集的目标点,这会导致控制智能体进行来 回的、无意义的移动。相反MAM和DMAM由于考虑了目的地和种群的相对位 置,能够让控制智能体更加平滑、更加有规律地移动。
为了定量分析每种模型的效率,实验测试了完成任务所需要的的时间步、 控制智能体的移动距离、全局中心的移动距离,三个指标均在种群数量N= 50,70,125时的平均值,如下表2、3、4所示。使用最大角度的MAM模型能够 有效提升完成控制任务的效率。在N≥70时使用引导性最大角度的DMAM模 型能够进一步提升完成控制任务的效率,但是在N=50时,DMAM的效果甚 至比SPPL模型的效果还差。通过比较表4全局中心移动距离,可知原因可能是 DMAM模型在种群较小时,该模型总是选择控制智能体一侧的目标来聚集,而 忽略了另一侧的简单智能体。
表2完成任务的平均时间步数
表3控制智能体完成任务需要移动的平均距离
表4全局中心完成任务需要移动的平均距离
为了进一步比较模型,实验对比了模型在不同种群数量下,时间步的变化。 结果如下图10和11所示,横轴表示种群大小,纵轴表示完成任务的时间步。 在大多数情况下,MAM都要优于SPPL模型(在时间效率上平均提升16%的效 率),尤其是当简单智能体的数量超过45时,DMAM和MAM相比,仅仅只有 0.11%的提升。
4结论
通过实验可以发现,本发明的DMAM和MAM模型相比于SPPL模型,能 够有效提升控制智能体完成控制任务效率。
以上所述,仅为本发明具体实施方式的详细说明,而非对本发明的限制。 相关技术领域的技术人员在不脱离本发明的原则和范围的情况下,做出的各种 替换、变型以及改进均应包含在本发明的保护范围之内。
机译: 基于策略基于节点的基于策略的智能AD-HOC网络体系结构
机译: 基于聚集器优先级策略进行聚集器逻辑选择的方法,系统和终端
机译: 基于安全策略协商的智能通信终端的差分安全控制方法和装置