基于Shape Theory 和Flocking的多智能体编队机动控制

何嘉诚，姚其峰，代小林，宫大为，孙旭红

（电子科技大学 机械与电气工程学院，成都611731）

多智能体编队机动控制是驱动一组具有特定形状的编队完成旋转、放缩和平移运动，在城市搜救、资源探测、集群作战和环境感知[1-3]等诸多实际应用中发挥了重要作用。

目前的编队机动控制方法主要包括基于相对位移、基于相对距离和基于相对角度的三类算法[4]。这三类算法分别使用智能体之间相对位移、相对距离和相对角度作为约束条件，以此来定义多智能体编队的队形[5-8]。用来定义目标编队的约束条件的不变性对于编队的机动控制有着重要的影响。基于相对位移的算法能有效地追踪时变平动的目标编队[9]，却不能实现编队的放缩和旋转运动。基于相对距离的编队机动控制算法能够实现编队的平动和旋转，但是不能实现编队的放缩运动[10]。基于相对角度的编队控制算法能够实现编队的放缩和平动，但是不能实现编队旋转运动。

为了提高编队机动控制的性能，近些年来，学者们提出了一些新的定义编队队形的方法。例如质心坐标法[11]，应力矩阵法[6]，复拉普拉斯矩阵法[7]。使用这些理论作为定义编队队形的约束条件，提高了编队约束条件的不变性。然而，上述方法都没有被用于控制大规模的编队运动[12-13]。

Shape Theory 是学者提出来的一种用来定义编队的简单方法[14]，它是指去除编队的旋转、放缩和平移后保留下的几何信息。因此，当编队进行旋转、放缩和平移时编队的几何信息是恒定的。Shape Theory已经被用于定义目标编队的队形，但是它在解决编队的机动控制方面仍然具有很大的潜力。

本文采用基于Shape Theory 和Flocking 算法[15]来解决编队机动控制问题。先假设到达目标位置的可行路径是已知的，在可行路径上以一定的步长选取路径点，然后以每个路径点为中心设置正方形的限制区域；再利于基于Shape Theory 的编队队形控制算法从初始位置开始依次在每个限制区域中计算出满足队形约束的目标编队的位置； 最后使用Flocking 算法驱动智能体依次奔向这些目标编队，直到智能体运动到目标位置。

1 理论基础

本节主要讲述涉及到本文提出的编队机动控制算法的理论基础，主要包括Flocking 算法[15]和Shape Theory 理论[12]。

1.1 Flocking 算法

Flocking 算法是一种由生物集群行为而启发的分布式算法，它是多智能体集群行为的一种表现式。这种集群行为是通过智能体之间的简单的交互来完成的，该算法不使用全局信息。这种集群行为主要通过以下3 种规则构建：

避免碰撞智能体之间会保持一定的距离，当距离过近时智能体之间会产生排斥力；当距离过远时智能体之间会产生吸引力。

向中心聚集智能体会向周围的群体靠近。

速度一致性每个智能体的速度与周围所有智能体的平均速度保持一致。

文献[15]为分析和设计分布式Flocking 算法提供了理论框架，在无障碍物和目标的环境中，该算法中每个智能体的控制输入由三部分组成：

当环境中有目标为智能体导向时，每个智能体i 的控制输入包含两个部分，其中：

式中：Ni表示智能体i 的邻居的个数。Φα（z）是由下面函数定义的功能函数：

式中：rα和dα是α-lattice 的常参数；Φ（z）是一个具有参数a，b，c 的非均匀的s 形函数，是一个数值从0 到1 均匀变化的bump 函数，其定义如下：

式（2）的另一些参数定义如下：‖qj－qi‖σ表示连接qj和qi的向量的σ-norm。σ-norm 的定义如下所示：

式中：nij是连接qi和qj直线上的向量，且ε∈（0，1）是σ-norm 的一个参数。最后，aij（q）定义如下所示：

式中：c1和c2是正整数。

使用Flocking 算法进行目标跟踪，每个移动的智能体i 使用ui作为控制输入。

1.2 Shape Theory

Shape Theory 是一种新的定义编队的方法。假设在二维欧几里得空间中有个n 智能体，给定目标编队的队形：

2 问题分析

在阐述问题前，先对多智能体系统做如下假设：

a）多智能体系统包含n 个可移动智能体，所有智能体在长为l，宽为w 的二维区域内运动。

b）通信能力：每个智能体能够通过通信网络和其邻居智能体传递信息。

c）探测能力：每个智能体的探测范围是一个圆心为其所在位置，半径为r 的圆。智能体能够探测到其探测范围内的所有邻居智能体。

d）动力学特性：考虑到智能体之间避碰的情况下，每个智能体之间的运动控制是独立的。qi，pi∈R2分别表示智能体的位置和速度，智能体的运动特性可以由下式表示：

编队的机动控制问题是控制一组智能体在保持编队队形的情况下进行旋转、放缩和平移运动。智能体之间要避免碰撞，且在复杂的环境中能够适应环境的变化。多个智能体从初始位置开始，并以一定的队形运动到目标位置，这个过程主要应解决3 个问题：①编队队形形成，多个智能体形成给定的编队队形；②设置限制区域，以一定的步长沿着可行路径设置多个限制区域，以实现编队的运动；③编队变换，编队在运动的过程中需要调整编队的形状或者大小来适应环境的变化。

3 问题求解

3.1 编队队形形成

文献[12]将Shape Theory 用于定义编队的队形，进而将编队的队形控制问题转化为凸优化问题。文献[14]使用递归神经网络求解文献中的凸优化问题，提高了形成目标编队的速度。

式中：P 为编队的初始位置；Q 为目标编队的位置；A 为编队的队形约束矩阵；α 为编队的放缩倍数；Φ为预先设定的限制区域。

式（13）是一个非光滑的凸优化问题，文献[14]使用递归神经网络模型来求解该优化问题，其模型如下所示：

其求解结果如下所示：

其中γ=（∂T‖P－Q‖）T，且

通过求解常微分方程（15），可以得到满足约束条件的目标编队坐标

3.2 设置限制区域

本文先假设已知一条从初始位置到目标位置的可行路径。在可行路径上以步长k 为间隔，均匀地选取一系列的路径点，再以路径点为中心设置正方形的限制区域。其示意图如图1所示。在每个限制区域中，通过使用递归神经网络模型（14）求解非光滑的凸优化问题（13），便可求出在每个限制区域中目标编队Qj（j 表示限制区域的数量）。值得注意的是Q1的初始是随机设置的，Qj（j=2，…，m）的初始位置为Qj-1。

图1 在路径点上设置限制区域Fig.1 Set a restricted area on waypoints

3.3 编队变换

为了提高多智能体编队对环境的适应能力，尤其是通过狭窄空间的过程中，需要调整编队的队形（如编队的放缩倍数或形状）来适应环境的变化。

我们采用与编队形成类似的方案，假设已知具有特性形状的初始编队P，要变换成目标编队Q，只需使用递归神经网络模型（14）求解问题（13）即可。本文采用的编队变换的方法与编队形成的区别主要是初始编队的形状不同（编队形成过程中其初始形状是不规则的；编队变换过程中其初始形状是规则的）。

3.4 算法流程

本文提出的算法伪代码如下：

开始

（1）设定编队初始位置P 和目标队形S；

（2）根据已知路径设置步长k 和路径点；

（3）根据路径点设置限制区域；

（4）for j=1 to m do

使用公式（15）依次求解Qj；

end

（5）for j=1 to m do

其中error 智能体形成过程中智能体的实际位置与目标位置之间的稳态误差。distance 为一个略大于error 的常数。通过调节distance 的大小能够改变编队速度的平滑性。

4 系统仿真

本章节进行了一个编队机动控制的仿真实验，来验证本文所提出算法的可行性。

我们采用一个具有11 个智能体组成的二维编队，且智能体的动态特性如式（12）所示。本次仿真的目的是使多个智能体在保持给定队形的前提下，顺利地避开障碍物并到达目标位置。编队的目标队形如图2所示。使用Matlab 软件的ODE 工具箱来求解微分方程（15），β 的值设置为20[14]、步长k=50、distance=3.0、编队的旋转角度和放缩倍数分别为2π 和12。在次仿真实验中，如果qi=pi，就令∂‖pi－qi‖2=0。令s（t）＝（qT（t），μ（t）T）代表递归神经网络的状态向量。

图2 编队的目标队形（每一个圆代表一个智能体）Fig.2 Shape of expected formation（dots represent agents）

本仿真首先假设一条已知的可行路径，如图3中的实线所示； 并以相应的步长k 设置限制区域；五角星为编队的终点，其结果如图3所示。根据上文的算法伪代码，本文使用Matlab 软件对该软件进行仿真，其结果如图4所示。

图3 可行路径及限制区域规划（空心矩形表示编队的限制区域；直线代表可行位置；五角星为目标位置；黑色矩形为障碍物）Fig.3 Plan optimal paths and restricted areas（hollow rectangle indicates the restricted area of the formation，straight line represents the feasible position，pentagram is the target position；the black rectangle is the obstacle）

图4 编队机动控制仿真（黑色的圆表示智能体运动过程中不同时刻的位置；曲线表示智能体的运动轨迹）Fig.4 Simulation of formation maneuver control（black circles in the figure indicate the position of the agent at different times during the movement of the agent，curve represents the movement track of the agent）

图4展示了使用本文提出的算法得到的编队机动控制仿真结果。从图4中可以看出该算法能够控制智能体先形成给定的目标编队，并能使智能体在保持队形的情况下顺利通过障碍物，并到达指定位置。

5 结语

本文将基于Shape Theory 的编队队形控制算法应用于解决多智能体的编队机动控制问题。在给定的可行路径上，以一定的步长依次从初始位置到目标位置设定路径点； 再分别以这些路径点为中心，设置正方形的限制区域，使用递归神经网络分别求解多智能体在每个限制区域中的目标编队的位置。最后使用Flocking 算法使智能体依次奔向这些目标编队，从而到达目标位置。最后，通过仿真实验验证了该算法的有效性。