¹呼和浩特民族学院数学与大数据学院，内蒙古 呼和浩特

²吉林大学数学学院，吉林 长春

收稿日期：2021年8月22日；录用日期：2021年9月12日；发布日期：2021年9月24日

摘要

本文研究具有切换拓扑网络的一般二阶多智能体系统蜂拥控制算法，当多智能体系统在遇到复杂障碍物时，引入了一种新的虚拟智能体产生一个切向排斥力，使得多智能体系统能够更光滑的通过障碍物。同时，采用动态牵制策略控制整个网络的连通性，确保多智能体系统能够达到蜂拥状态且智能体之间不发生碰撞。最后给出了一些数值模拟结果，证实了算法的有效性。

关键词

多智能体，蜂拥控制，复杂障碍物

Flocking Control Algorithm of Multi-Agent System with Complex Obstacles

Jingying Gao¹, Xu Xu², Siriguleng He¹

¹School of Mathematics and Big Data, Hohhot Minzu College, Hohhot Inner Mongolia

²College of Mathematics, Jilin University, Changchun Jilin

Received: Aug. 22^nd, 2021; accepted: Sep. 12^th, 2021; published: Sep. 24^th, 2021

ABSTRACT

The flocking control algorithm for general second-order multi-agent systems with switching topology networks is investigated in this paper. When the multi-agent system encounters complex obstacles, a new virtual agent is introduced to produce a tangential repulsion force, so that the multi-agent system can pass through obstacles more smoothly. At the same time, the dynamic pinning control strategy is adopted to control the connectivity of the whole network, so as to ensure that the multi-agent system can reach the flocking state and there is no collision between agents. Finally, some numerical simulation results are given to verify the effectiveness of the algorithm.

Keywords:Multi-Agent System, Flocking Control, Complex Obstacles

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

多智能体系统(Multi-agent System, MAS)是由大量的智能体构成，它是将大而复杂的系统转化成多个、简单的并且彼此相互通信的系统。受到人工智能理论的启发，多智能体系统最初的目标是弥补单一复杂系统在解决大型复杂实际应用中的不足之处。随着计算机技术的突飞猛进，同时受到大自然生物群体协调运动的启发，多智能体协调控制问题的研究取得了非常丰富的成果。

目前大部分多智能体蜂拥控制算法考虑的是双重积分模型，由于该系统的简单性，针对该系统的蜂拥控制算法研究已经有很多成果 [1] [2] [3] [4]。但是在实际应用当中不可能把所有系统都用二阶模型表示，因此有必要把二阶模型推广到更一般的模型 [5] [6]。此外，多智能体系统在运动过程中难免遇到障碍物情况，如何有效的绕过障碍物成为了多智能体协调控制问题的另一个热点研究方向。Olfati-Saber [7] 提供了一种多智能体能够有效绕过障碍物的方法。文献 [8] 在Olfati-Saber算法的基础上提出了一种更有效绕过障碍物的方法，增加了转向机制，当智能体遇到障碍物时根据其前进方向与障碍物之间夹角决定智能体应从障碍物的哪一侧绕过，大大提高了避障效率。文献 [9] 中给出了一种人工势函数结合流函数的方法，智能体根据流函数决定如何绕过障碍物，而势函数能保证智能体与障碍物之间不会发生碰撞。

本文研究一般二阶系统多智能体蜂拥控制算法，使其能够解决每个智能体具有更一般的二阶系统多智能体通过复杂障碍物时的蜂拥控制问题。考虑具有切换拓扑结构的多智能体网络，假设多智能体网络有一个虚拟领导者且有一部分智能体能够收到虚拟领导者的反馈信息。为了解决网络不连通的问题，采用动态牵制策略实现整个智能体网络蜂拥控制。为了能更光滑的绕过障碍物，引入了一种新的虚拟智能体叫做 ${\beta }_2$ -智能体，使其对 $\alpha$ -智能体产生一个切向排斥力。因此本文具有障碍物的蜂拥控制算法当中有两种 $\beta$ -智能体，它们产生的排斥力大小相同、方向垂直。最后给出了一些模拟结果，证实了算法的有效性。

2. 问题阐述

考虑n个智能体在m维欧式空间上移动，每个智能体的运动方程表示为

$\left[\begin{array}{l}{\stackrel{\dot{}}{q}}_i\\ {\stackrel{\dot{}}{p}}_i\end{array}\right]=\left(X\otimes I_m\right)\left[\begin{array}{l}{q}_i\\ p_i\end{array}\right]+\left(Y\otimes I_m\right)u_i,i=1,2,\cdots ,n$ (1)

其中 $q_i\in R^m$ 是智能体i的位置向量， $p_i\in R^m$ 是智能体i的速度向量， $u_i\in R^m$ 智能体i的控制输入向量。X是Y是二阶常量矩阵， $I_m$ 是m阶单位矩阵， $\otimes$ 表示Kronecker积，标记虚拟领导者的下标为0。

为了使虚拟领导者以常速运动，它的控制输入 $u_i$ 定义为

$X=\left[\begin{array}{cc}{\xi }_{11}& {\xi }_{12}\\ {\xi }_{21}& {\xi }_{22}\end{array}\right],Y=\left[\begin{array}{l}{\zeta }_1\\ {\zeta }_2\end{array}\right].$ (2)

虚拟领导者可以看作是提前给定的预定路线，蜂拥控制的目的是多智能体不仅要达到蜂拥状态而且还要按照预定路线移动，如来自地面指挥员的命令。本文考虑了切换拓扑结构，因此把每个智能体的邻域可以看作是时间t的函数。两个智能体之间的距离超过感应半径时，它们之间的连边会断开，有可能整个多智能体网络会不连通。本文采用动态牵制策略达到多智能体网络蜂拥控制目标。动态牵制策略的具体步骤是每次拓扑结构发生变化的时候，把整个智能体分为若干个连通子网络，然后从每个子网络当中选择度最大的智能体作为牵制节点(能收到虚拟领导者的反馈信息)。此时，每个智能体在每一个时刻都能直接或者间的接收到虚拟领导者的位置和速度信息，从而既不用每个节点都进行牵制控制，也不需要整个智能体网络时刻连通的情况下，达到对多智能体网络蜂拥控制目的，见图1。

图1. 动态牵制策略

3. 具有复杂障碍物的多智能体蜂拥控制算法

本文考虑了具有复杂障碍物的动态牵制蜂拥控制算法，即多智能体系统在蜂拥过程中遇到复杂障碍物的情况，见图2，其中白色区域是智能体可以通过的空间，其它区域是障碍物，如楼房，墙体等等。由于本文算法是基于文献 [7] 中第三个算法得到的，所以首先介绍一下在文中出现的相关概念。多智能体网络中实际存在的智能体称为 $\alpha$ -智能体，而障碍物的影响用另一种虚拟智能体表示，该智能体称为 $\beta$ -智能体。 $\beta$ -智能体可以通过在障碍物表面上映射 $\alpha$ -智能体的位置而得到，目的是使 $\alpha$ -智能体不会与障碍物发生碰撞。 $\beta$ -智能体会随着 $\alpha$ -智能体的移动而在障碍物边缘上移动。当 $\alpha$ -智能体感知障碍物的时候，根据自己的位置可以在障碍物表面上得到一个与自己对应的 $\beta$ -智能体，之后 $\alpha$ -智能体和 $\beta$ -智能体之间会产生排斥力，从而 $\alpha$ -智能体能够有效的避免与障碍物碰撞。为了使 $\alpha$ -智能体在遇到障碍物的时候能更光滑的绕过障碍物，本文引入了另一种虚拟智能体，但是该虚拟智能体不在障碍物表面上并且能给 $\alpha$ -智能体一个切向的排斥力。因此在本文算法当中有两种不同的 $\beta$ -智能体，为了避免发生混淆，在障碍物表面上的虚拟智能体称为 ${\beta }_1$ -智能体，而不在障碍物表面上的虚拟智能体称为 ${\beta }_2$ -智能体，见图3(a)。

图2. 复杂障碍物几何特征

图3. $\alpha$ -智能体， ${\beta }_1$ -智能体， ${\beta }_2$ -智能体，法向排斥力，切向排斥力示意图

${\beta }_2$ -智能体依然是虚拟智能体，它用于产生对 $\alpha$ -智能体一个切向排斥力，排斥力的方向与 ${\beta }_1$ -智能体的速度方向一致，且 $\alpha$ -智能体会向 ${\beta }_1$ -智能体的速度方向从障碍物的一侧绕过。由 ${\beta }_1$ -智能体产生的排斥称为法向排斥力，而由 ${\beta }_2$ -智能体产生的排斥力称为切向排斥力，两种排斥力是垂直的。因此， $\alpha$ -智能体与障碍物之间的排斥力是这两种排斥力的总和，见图3(a)。从图3(b)可以看出，由于增加了切向排斥力， $\alpha$ -智能体新的速度方向与原速度方向之间的夹角 ${\theta }_1$ 总是小于在没有切向力时的 $\alpha$ -智能体新的速度方向与原速度方向之间的夹角 ${\theta }_2$。这说明本文算法中的智能体更能光滑的绕过障碍物，并且不会与障碍物发生碰撞。每个智能体的控制输入分为三个部分，它们分别是每个 $\alpha$ -智能体与它周围智能体之间的作用力， ${\beta }_1$ -智能体与 ${\beta }_2$ -智能体之间的排斥力， ${\beta }_2$ -智能体与 $\alpha$ -智能体之间的排斥力。

本文提出的具有复杂障碍物蜂拥控制算法可以总结为如下几个步骤：

(1) 首先得到 ${\beta }_1$ -智能体在障碍物 $O_k$ 边缘上的位置 $q_{i,k}$ 和速度 $p_{i,k}$，$O_k$ 表示第k个障碍物。

(2) 根据 ${\beta }_1$ -智能体的位置和速度确定 ${\beta }_2$ -智能体的位置 $q_{i,l}$。 ${\beta }_2$ -智能体位置满足： $\left(q_i-q_{i,l}\right)\cdot p_i\ge 0$，

$\langle \left(q_{i,l}-q_i\right)\cdot \left(q_{i,k}-q_i\right)\rangle =\pi /2$ 和 ${\Vert q_{i,l}-q_i\Vert }_{\sigma }={\Vert q_{i,k}-q_i\Vert }_{\sigma }$，其中 $\langle \cdot \rangle$ 表示两个向量的夹角。

(3) 增加对 $\alpha$ -智能体的两个排斥力 ${\psi }_{\beta }\left({\Vert q_{i,k}-q_i\Vert }_{\sigma }\right)$ 和 ${\psi }_{\beta }\left({\Vert q_{i,l}-q_i\Vert }_{\sigma }\right)$，其中 ${\psi }_{\beta }(\cdot )$ 是 $\alpha$ -智能体与 $\beta$ -

智能体之间的势函数。

在步骤2中， $\left(q_i-q_{i,l}\right)\cdot p_i\ge 0$ 表示向量 $q_i-q_{i,l}$ 和速度向量 $p_i$ 的夹角总是锐角，

$\langle \left(q_{i,l}-q_i\right)\cdot \left(q_{i,k}-q_i\right)\rangle =\pi /2$ 表示向量 $q_{i,l}-q_i$ 垂直于向量 $q_{i,k}-q_i$，${\Vert q_{i,l}-q_i\Vert }_{\sigma }={\Vert q_{i,k}-q_i\Vert }_{\sigma }$ 表示从 ${\beta }_1$ -智能体

和 ${\beta }_2$ -智能体到 $\alpha$ -智能体的距离相等，这意味着 ${\beta }_1$ -智能体和 ${\beta }_2$ -智能体产生的排斥力相等。

文献 [7] 中当 $\alpha$ -智能体感应到障碍物的时候不是立刻对障碍物产生排斥作用的，而是障碍物和 $\alpha$ -智能体的距离小于某个临界值时才产生作用。本文提出的有障碍物蜂拥控制算法中对人工势函数做了一点改动，当 $\alpha$ -智能体感应到障碍物时马上在 $\alpha$ -智能体和 ${\beta }_1$ -智能体之间产生排斥力。

$\alpha$ -智能体和 $\beta$ -智能体的邻域分别定义如下

$N_i^{\alpha }=\left\{j\in V|{\Vert q_j-q_i\Vert }_{\sigma }<r\right\},$ (3)

和

$\begin{array}{l}{N}_i^{\beta }=\left\{k|{\Vert q_{i,k}-q_i\Vert }_{\sigma }<r^{\prime }\right\}\\ \cup \{l|\left(q_i-q_{i,l}\right)\cdot p_i\ge 0,\langle \left(q_{i,l}-q_i\right)\cdot \left(q_{i,k}-q_i\right)\rangle =\pi /2\\ \text{and}{\Vert q_{i,l}-q_i\Vert }_{\sigma }={\Vert q_{i,k}-q_i\Vert }_{\sigma }\}.\end{array}$ (4)

其中 ${\Vert \cdot \Vert }_{\sigma }$ 表示sigma范数， $r,r^{\prime }$ 分别是 $\alpha$ -智能体和 $\beta$ -智能体的感应半径且可以选择 $r^{\prime }\le r$。

下面给出具有障碍物的动态牵制蜂拥控制算法。对于每个智能体i的控制输入定义如下

$u_i=\left(w_i+v_i\right)/{\zeta }_2,i=1,2,\cdots ,n.$ (5)

其中第一项 $w_i$ 为智能体的状态反馈项，第二项 $v_i$ 为智能体i的协作控制项。设计控制输入的目的是使所有智能体的速度达到一致且智能体之间不会发生碰撞。为了达到该目的，第一项 $w_i$ 可以考虑如下形式

$w_i=-{\xi }_{21}{q}_i-{\xi }_{22}{p}_i,$ (6)

第二项 $v_i$ 可以考虑如下形式

$\begin{array}{l}{v}_i=-{\displaystyle \underset{j\in N_i^{\alpha }\left(t\right)}{\sum }{\nabla }_{q_i}{\psi }_{\alpha }\left({\Vert q_i-q_j\Vert }_{\sigma }\right)}-{\displaystyle \underset{j\in N_i^{\alpha }\left(t\right)}{\sum }{a}_{ij}\left(t\right)\left(p_i-p_j\right)}\\ -h_i\left(t\right)\left[c_1\left(q_i-q_0\right)+c_2\left(p_i-p_0\right)\right]\\ -{\displaystyle \underset{l\in N_i^{\beta }\left(t\right)}{\sum }{\nabla }_{q_i}{\psi }_{\beta }\left({\Vert q_i-q_{i,l}\Vert }_{\sigma }\right)}-{\displaystyle \underset{k\in N_i^{\beta }\left(t\right)}{\sum }{\nabla }_{q_i}{\psi }_{\beta }\left({\Vert q_i-q_{i,k}\Vert }_{\sigma }\right)}.\end{array}$ (7)

其中， $c_1,c_2>0$，$q_0$ 和 $p_0$ 分别是虚拟领导者的位置和速度向量。如果智能体i是牵制节点，则 $h_i\left(t\right)=1$，否则 $h_i\left(t\right)=0$。 ${\psi }_{\beta }\left(z\right)$ 如文献 [7] 中定义的势函数。公式(7)中最后两项分别是 ${\beta }_1$ -智能体和 ${\beta }_2$ -智能体与 $\alpha$ -智能体之间的排斥力。

4. 模拟结果与讨论

本文模拟了 $n=30$ 个智能体在控制输入(7)的影响下在2维平面上运动，验证当多智能体网络穿过复杂障碍物时的动态牵制蜂拥控制算法的有效性。30个智能体的初始位置和初始速度分别由区间 $\left[0,20\right]\times \left[0,20\right]$ 和 $\left[-1,1\right]\times \left[-1,1\right]$ 随机生成。每个智能体的感应半径为 $r=4$，感应障碍物的半径 $r^{\prime }=2,c_1=0.3,c_2=6$，虚拟领导者的初始位置和初始速度分别设为 $q_0\left(0\right)={\left[160,12\right]}^{\text{T}}$ 和 $p_0={\left[0.3,0\right]}^{\text{T}}$，并且虚拟领导者的速度是不变的。动力学方程(1)中矩阵X和Y设置为

$X=\left[\begin{array}{cc}2& 2\\ 2& -1\end{array}\right],Y=\left[\begin{array}{l}1\\ 1\end{array}\right].$

在这个部分考虑了两种不同几何特征的复杂障碍物，如图4和图5，障碍物外部的虚线表示危险区域，智能体一旦进入危险区域，立刻得到与之相对应的虚拟智能体，进而能顺利的通过复杂障碍物。首先，30个多智能体需要通过两个不同宽度的过道，第一个过道比较宽，第二个过道相比于第一个比较窄。在遇到第二种障碍物的时候多智能体需要通过一条蛇形通道，这种障碍物的几何特征相比第一个障碍物要复杂一点，两个狭窄过道宽度相同，选择这种复杂障碍物的可以更好的验证本文动态牵制蜂拥控制算法通过复杂障碍物的能力。图4和图5显示了30个智能体在通过两种复杂障碍物时的运动轨迹，从图可以清楚的看出所有智能体顺利通过障碍物且没有与障碍物发生碰撞。

图4. 30个智能体通过第一种复杂障碍物时的运动轨迹

图5. 30个智能体通过第二种复杂障碍物时的运动轨迹

5. 小结

本文提出了一种具有一般二阶线性系统的多智能体动态牵制蜂拥控制算法。基于动态牵制策略，提出了一种新的控制协议，在多智能体网络不需要假设多智能体网络连通或者使用无穷大势函数保持网络连通的情况下，有效的解决了多智能体系统蜂拥控制问题。为了能更光滑的绕过障碍物，引入了一种新的虚拟智能体叫作 ${\beta }_2$ -智能体对 $\alpha$ -智能体产生一个切向排斥力。最后，给出了一些模拟结果，进一步证实了算法的有效性。

基金项目

内蒙古自治区高等学校科学研究项目(NJZY19174)；呼和浩特民族学院博士基金(HMBS1903)；国家自然科学基金(11961022)；呼和浩特民族学院科研创新团队建设计划项目(HMTD202005)；呼和浩特民族学院校级项目。

文章引用

高晶英,徐 旭,何斯日古楞. 具有复杂障碍物的多智能体蜂拥控制算法
Flocking Control Algorithm of Multi-Agent System with Complex Obstacles[J]. 应用数学进展, 2021, 10(09): 3178-3184. https://doi.org/10.12677/AAM.2021.109332

参考文献