# Obstacle Boundary Point and Expected Velocity-Based Flocking of Multiagents with Obstacle Avoidance

Authors: Jianhui Wu; Yuanfa Ji; Xiyan Sun; Weibin Liang
Journal: International Journal of Intelligent Systems
 (2023)

---

## Abstract

Obstacle avoidance is a key technology of multiagents flocking control. However, most existing research studies assume that the agent can obtain global information about obstacles and have specific constraints on the shape and boundary of obstacles, which easily limit their practical applications. To relax these constraints, we assume that the agent can only perceive the position of obstacle boundary points within its sensing radius and propose an obstacle boundary point and an expected velocity-based flocking algorithm of multiagents with obstacle avoidance. In this algorithm, the attraction/repulsion potential is designed to avoid collisions between agents and between the agent and obstacle boundary points, the expected velocity is designed to tow the agent to move along the boundary of obstacles, and the virtual leader is designed to lead all agents to realize the group objective. Finally, the sufficient conditions that the agent does not collide are demonstrated, and the performance of the proposed algorithm is further verified through simulations.


---

## Body

## 1. Introduction

Flocking is an orderly motion phenomenon generated by relatively simple local interaction among multiagents, which is very common in nature, such as the migration of birds[1, 2], foraging of fish schools [3, 4], avoiding predators of deers [5], and swimming of bacteria [6, 7]. Multiagents often encounter some obstacles in the process of flocking motion [8–10]. Therefore, obstacle avoidance is a key technology problem to be solved in the research of flocking control.At present, the research on flocking with obstacle avoidance mainly concentrate on the collision cone approach, the velocity obstacle approach, the numerical solution approach, and the potential field approach. The main characteristics of the above four approaches are summarized in Table1. The collision cone approach detects the collision risk through the collision cone and converts the relative velocity vector into the obstacle-avoidance vector to solve the obstacle avoidance trajectory when the collision risk is detected. The velocity obstacle approach defines the space obtained by translating the collision cone along the obstacle velocity vector as the velocity obstacle space and realizes obstacle avoidance by bypassing the velocity obstacle space along the shortest path. Obviously, both the collision cone approach and the velocity obstacle approach solve the obstacle avoidance problem based on the relative geometric relationship between the agent and obstacles, but the difficulty in constructing and solving the relative geometric relationship will increase significantly with increasing the scale of agents or obstacles. In the numerical solution approach, the collision process between the agent and obstacles is constructed as a mathematical model under the motion constraints, and the optimal obstacle-avoidance trajectory at the current state is obtained by the intelligent algorithm [19, 20].Table 1
Summary of related research on flocking with obstacle avoidance.
ApproachReferenceControl inputLarge-scale agentObstacle constraintExperimental scenarioCollision cone approachBoardman et al. [11] (2021)Position and velocityNoYesStatic and dynamicBhattacharjee et al. [12] (2021) and Douthwaite et al. [13] (2019)VelocityNoYesDynamicChakravarthy and Ghose [14] (2020)AccelerationNoYesDynamicXu et al. [15] (2020)VelocityNoYesStatic and dynamicVelocity obstacle approachChen et al. [16] (2020)VelocityNoYesStatic and dynamicLópez et al. [17] (2020) and Fuad et al. [18] (2021)Linear and angular velocitiesNoYesStatic and dynamicNumerical solution approachHe et al. [19, 20] (2019 and 2022)Surge, sway and yaw accelerationsNoYesDynamicPotential field approachSakai et al. [21] (2016), Nath et al. [22] (2022), Dang et al. [23] (2019), and Wang et al. [24] (2014)AccelerationYesYesStatic and dynamicThe potential field approach generally maintains the distance between the agent and obstacles through the position-based virtual potential field and guides the agent to bypass obstacles through the velocity-based virtual potential field. Olfati-Saber assumed that all agents can completely obtain the smooth shape, position, and motion information of a spherical obstacle or infinite wall and presented a flocking algorithm with obstacle avoidance [25]. The algorithm assumes that the velocity of the obstacle is the projection velocity of the agent on the obstacle, which enables the agent to bypass the obstacle along the tangent direction of the obstacle but also restricts the obstacle to a hyperplane or convex obstacle with a smooth boundary. Li et al. proposed a filling scheme to change the nonconvex obstacle into the convex obstacle to solve the problem of obstacle avoidance under nonconvex obstacles [26]. The scheme can make the agent bypass the concave obstacle, but it still needs to obtain global information about obstacles. This constraint limits its practical applications. Therefore, relaxing the constraints of obstacle information, shape, and boundary is very challenging for the research of the flocking algorithm of multiagents with obstacle avoidance.The Bug algorithm is a kind of obstacle avoidance algorithm for an agent without knowing the global information of a map and obstacle shape, such as the Bug2 algorithm [27, 28], the IBug algorithm [29], the FuzzyBug algorithm [30], and the RandomBug algorithm [31, 32]. In this kind of algorithm, the agent firstly moves along the boundary of obstacles when encountering some, then leaves these obstacles based on certain judgment criteria, and then continues to move towards the target in a straight line. Moving along the boundary of obstacles is an efficient scheme to bypass complex obstacles [33]. Based on this, we attempt to convert the expected position of the agent at the next time into the expected velocity of the agent for all obstacle boundary points within its sensing radius and make the agent that perceives the obstacles preventing it following bypass obstacles follow along the boundary of obstacles using the expected velocity. Meanwhile, we regard the agent, obstacle boundary point, and virtual leader as α-agent, β-agent, and γ-agent, respectively, attempt to ensure that there is no collision between α-agents and between α-agent and β-agent at any time through the attractive/repulsive potential, and lead all α-agents to realize the group objective following through the γ-agent. In addition, to relax the constraint of obstacle information, we assume that α-agent can only perceive the position of β-agents within its sensing radius. Unlike the Bug algorithm, this study aims to realize collision avoidance and group objective following through the attractive/repulsive potential, expected velocity, and γ-agent, which is to relax the constraints of the flocking algorithm with obstacle avoidance based on obstacle information, shape, and boundary.The main contributions of this paper can be summarized as follows: first, a novel method is established to calculate the expected velocity ofα-agent for all β-agents within its sensing radius. Second, a novel obstacle boundary point and expected velocity-based flocking algorithm of multiagents with obstacle avoidance is designed to relax the constraints of obstacle information, shape, and boundary. Third, the sufficient conditions that α-agent does not collide in the proposed algorithm are obtained.The rest of this paper is organized as follows: In Section2, we formulate the multiagent motion model with velocity limit and introduce some preliminaries. Section 3 describes the design of the obstacle boundary point and the expected velocity-based flocking algorithm of multiagents with obstacle avoidance. The property analysis of the proposed algorithm is presented in Section 4. The simulations are provided to verify the theoretical results in Section 5. Finally, the main conclusions are drawn in Section 6.


## 2. Preliminaries

### 2.1. Problem Formulation

ConsiderNα-agents moving in the m-dimensional (e.g.,m=2,3) Euclidean space. Let qi∈Rm denote the position vector of α-agent i at the current time, pi∈Rm is the velocity vector of α-agent i at the current time, and ui∈Rm is the control input vector of α-agent i at the current time. The movement of α-agent i is described as [26](1)q˙i=pi,p˙i=ui,∀i∈1,⋯,N.In the practical implementation, the velocity ofα-agent i is limited. Therefore, the movement of α-agent i can be rewritten as(2)q˙i=satpi,pimax,p˙i=ui,∀i∈1,⋯,N,where pimax denotes the maximum velocity of α-agent i, satpi,pimax=δpi+1−δpipimax/pi, specifically δ=1 if pi≤pimax and δ=0 otherwise, and ⋅ is the Euclidean norm.To relax the constraint of obstacle information, we assume that theα-agent can perceive the position of obstacle boundary points within the sensing radius and obtain the position and velocity information of other α-agents within the sensing radius by information interaction. If the objects within the sensing radius of α-agent i have other α-agents and obstacles, Niα is the set of α-agents within the sensing radius r of α-agent i at the current time, Niβ is the set of obstacle boundary points within the sensing radius r of α-agent i at the current time, then the object set Ni within the sensing radius r of α-agent i can be defined as(3)Ni=Niα∪Niβ,Niα=j∈1,⋯,N:qj−qi≤r,i≠j,Niβ=k∈Ok:qk−qi≤r,where qk denotes the position vector of obstacle boundary point k, and Ok is the set of obstacle boundary points.As in previous studies [25], we introduce a γ-agent to represent a group objective. The movement of γ-agent is described as(4)q˙γ=pγ,p˙γ=uγ,where qγ∈Rm denotes the position vector of γ-agent at the current time, pγ∈Rm is the velocity vector of γ-agent at the current time, and uγ∈Rm is the control input vector of γ-agent at the current time.


### 2.2. Overview of Previous Flocking Algorithm with Obstacle Avoidance

The proposed algorithm is constructed by modifying the control input in [25], which considers relaxing the constraints of obstacle information, shape, and boundary. For the sake of clarity, this section gives a brief overview of the flocking algorithm with obstacle avoidance in [25].In Figure1, when an α-agent i perceives an obstacle k within the sensing radius r, it will generate a virtual β-agent k at the closest point on the obstacle. The position q^i,k of β-agent k is the projection position of α-agent i on the obstacle k, and the velocity p^i,k is the projection velocity of α-agent i on the obstacle k. In the case where the obstacle is an infinite wall, the position q^i,k and velocity p^i,k of β-agent k are given by [25](5)q^i,k=Pqi+1−Pyk,p^i,k=Ppi,where yk is the passing point of infinite wall boundary, P=I−akakT is the projection matrix, and ak=qi−yk/qi−yk.Figure 1
Position and velocity ofβ-agent (previous algorithm). (a) Infinite wall. (b) Spherical obstacle.
(a)(b)In the case where the obstacle is a spherical obstacle, the positionq^i,k and velocity p^i,k of β-agent k are determined by [25](6)q^i,k=μqi+1−μyk,p^i,k=μPpi,where yk is the center of spherical obstacle, Rk is the radius of spherical obstacle, and μ=Rk/qi−yk.Besides, following the results in [25], the control input ui is composed of α,α interaction term uiα, α,β interaction term uiβ, and α,γ interaction term uiγ. The control input ui is described as(7)ui=uiα+uiβ+uiγ.Theα,α interaction term uiα in formula (7) is defined as(8)uiα=−c1α∑j∈Niα∇qiψαqj−qiσ⏟gradient−basedterm+c2α∑j∈Niαaijqpj−pi⏟consensusterm,where c1α>0 and c2α>0 are the feedback gains, ∇qiψαqj−qiσ is the gradient of the pairwise attractive/repulsive potential ψαqj−qiσ between α-agent i and α-agent j at position qi, ψαqj−qiσ=∫dαqj−qiσϕαsds, ϕαs=ρhs/rαϕs−dα, ϕz=1/2a+bσ1z+c+a−b, σ1z=z/1+z2, b≥a>0, c=a−b/4ab, dα=dσ, aijq=ρhqj−qiσ/rα, rα=rσ, zσ=1/ε1+εz2−1, ε>0, and the bump function ρhz for h∈0,1 is defined as [21](9)ρhz=1,ifz∈0,h,121+cosz−hπ1−h,ifz∈h,1,0,otherwise.Theα,β interaction term uiβ in formula (7) is defined as(10)uiβ=−c1β∑k∈Niβ∇qiψβq^i,k−qiσ+c2β∑k∈Niβbi,kqp^i,k−pi,where c1β>0 and c2β>0 are the feedback gains, bi,kq=ρhq^i,k−qiσ/dβ, and ∑k∈Niβ∇qiψβq^i,k−qiσ is the gradient of the pairwise attractive/repulsive potential ψβq^i,k−qiσ between α-agent i and β-agent k at position qi, ψβq^i,k−qiσ=∫dβq^i,k−qiσϕβsds, ϕβs=ρhs/dβσ1z−dβ−1, dβ=d′σ.Theα,γ interaction term uiγ in formula (7) is defined as(11)uiγ=−c1γσ1qi−qγ−c2γpi−pγ,where c1γ>0 and c2γ>0 are the feedback gains.


## 2.1. Problem Formulation

ConsiderNα-agents moving in the m-dimensional (e.g.,m=2,3) Euclidean space. Let qi∈Rm denote the position vector of α-agent i at the current time, pi∈Rm is the velocity vector of α-agent i at the current time, and ui∈Rm is the control input vector of α-agent i at the current time. The movement of α-agent i is described as [26](1)q˙i=pi,p˙i=ui,∀i∈1,⋯,N.In the practical implementation, the velocity ofα-agent i is limited. Therefore, the movement of α-agent i can be rewritten as(2)q˙i=satpi,pimax,p˙i=ui,∀i∈1,⋯,N,where pimax denotes the maximum velocity of α-agent i, satpi,pimax=δpi+1−δpipimax/pi, specifically δ=1 if pi≤pimax and δ=0 otherwise, and ⋅ is the Euclidean norm.To relax the constraint of obstacle information, we assume that theα-agent can perceive the position of obstacle boundary points within the sensing radius and obtain the position and velocity information of other α-agents within the sensing radius by information interaction. If the objects within the sensing radius of α-agent i have other α-agents and obstacles, Niα is the set of α-agents within the sensing radius r of α-agent i at the current time, Niβ is the set of obstacle boundary points within the sensing radius r of α-agent i at the current time, then the object set Ni within the sensing radius r of α-agent i can be defined as(3)Ni=Niα∪Niβ,Niα=j∈1,⋯,N:qj−qi≤r,i≠j,Niβ=k∈Ok:qk−qi≤r,where qk denotes the position vector of obstacle boundary point k, and Ok is the set of obstacle boundary points.As in previous studies [25], we introduce a γ-agent to represent a group objective. The movement of γ-agent is described as(4)q˙γ=pγ,p˙γ=uγ,where qγ∈Rm denotes the position vector of γ-agent at the current time, pγ∈Rm is the velocity vector of γ-agent at the current time, and uγ∈Rm is the control input vector of γ-agent at the current time.


## 2.2. Overview of Previous Flocking Algorithm with Obstacle Avoidance

The proposed algorithm is constructed by modifying the control input in [25], which considers relaxing the constraints of obstacle information, shape, and boundary. For the sake of clarity, this section gives a brief overview of the flocking algorithm with obstacle avoidance in [25].In Figure1, when an α-agent i perceives an obstacle k within the sensing radius r, it will generate a virtual β-agent k at the closest point on the obstacle. The position q^i,k of β-agent k is the projection position of α-agent i on the obstacle k, and the velocity p^i,k is the projection velocity of α-agent i on the obstacle k. In the case where the obstacle is an infinite wall, the position q^i,k and velocity p^i,k of β-agent k are given by [25](5)q^i,k=Pqi+1−Pyk,p^i,k=Ppi,where yk is the passing point of infinite wall boundary, P=I−akakT is the projection matrix, and ak=qi−yk/qi−yk.Figure 1
Position and velocity ofβ-agent (previous algorithm). (a) Infinite wall. (b) Spherical obstacle.
(a)(b)In the case where the obstacle is a spherical obstacle, the positionq^i,k and velocity p^i,k of β-agent k are determined by [25](6)q^i,k=μqi+1−μyk,p^i,k=μPpi,where yk is the center of spherical obstacle, Rk is the radius of spherical obstacle, and μ=Rk/qi−yk.Besides, following the results in [25], the control input ui is composed of α,α interaction term uiα, α,β interaction term uiβ, and α,γ interaction term uiγ. The control input ui is described as(7)ui=uiα+uiβ+uiγ.Theα,α interaction term uiα in formula (7) is defined as(8)uiα=−c1α∑j∈Niα∇qiψαqj−qiσ⏟gradient−basedterm+c2α∑j∈Niαaijqpj−pi⏟consensusterm,where c1α>0 and c2α>0 are the feedback gains, ∇qiψαqj−qiσ is the gradient of the pairwise attractive/repulsive potential ψαqj−qiσ between α-agent i and α-agent j at position qi, ψαqj−qiσ=∫dαqj−qiσϕαsds, ϕαs=ρhs/rαϕs−dα, ϕz=1/2a+bσ1z+c+a−b, σ1z=z/1+z2, b≥a>0, c=a−b/4ab, dα=dσ, aijq=ρhqj−qiσ/rα, rα=rσ, zσ=1/ε1+εz2−1, ε>0, and the bump function ρhz for h∈0,1 is defined as [21](9)ρhz=1,ifz∈0,h,121+cosz−hπ1−h,ifz∈h,1,0,otherwise.Theα,β interaction term uiβ in formula (7) is defined as(10)uiβ=−c1β∑k∈Niβ∇qiψβq^i,k−qiσ+c2β∑k∈Niβbi,kqp^i,k−pi,where c1β>0 and c2β>0 are the feedback gains, bi,kq=ρhq^i,k−qiσ/dβ, and ∑k∈Niβ∇qiψβq^i,k−qiσ is the gradient of the pairwise attractive/repulsive potential ψβq^i,k−qiσ between α-agent i and β-agent k at position qi, ψβq^i,k−qiσ=∫dβq^i,k−qiσϕβsds, ϕβs=ρhs/dβσ1z−dβ−1, dβ=d′σ.Theα,γ interaction term uiγ in formula (7) is defined as(11)uiγ=−c1γσ1qi−qγ−c2γpi−pγ,where c1γ>0 and c2γ>0 are the feedback gains.


## 3. Algorithm Design

In this section, we design an obstacle boundary point and an expected velocity-based flocking algorithm of multiagents with obstacle avoidance, which seeks to modify the gradient-based terms in formulas (8) and (10) and the consensus term in formula (10) to relax the constraints of obstacle shape and boundary in the previous flocking algorithm with obstacle avoidance.


### 3.1. Gradient-Based Term

A distinguishing feature of the proposed algorithm as compared with the previous flocking algorithm with obstacle avoidance in Section2 is that the position of β-agent is not the projection position of α-agent on an obstacle surface but the position of the obstacle boundary point within the sensing radius of α-agent. Each obstacle boundary point within the sensing radius of α-agent corresponds to a β-agent. When the distance between α-agents or the distance between α-agent and β-agent is less than the minimum early-warning distance de, the possibility of collision between them may be greatly increased. To further reduce the possibility of collision, we divide the sensing radius region of α-agent into a separation region, an early-warning region, and an attraction region (see Figure 2), and define a nonnegative subsection function to adjust the weight of attractive/repulsive potential in these three regions.Figure 2
The sensing radius ofα-agent.The nonnegative subsection functionη1αdij is defined as(12)η1αdij=τaα,dij∈d,r,τeα,dij∈de,d,τsα,dij∈0,de,where τaα, τeα, and τsα are the weight factors, τsα≥τeα≥τaα≥0, de=dmin+2pimax∆t, dmin is the minimum safe distance, and dij=qj−qi is the distance between α-agent i and α-agent j.The gradient-based termωiα in formula (8) can be defined as(13)ωiα=−c1α∑j∈Niαη1αdij∇qiψαqj−qiσ.Let the attractive/repulsive potentialψβqk−qiσ between α-agent i and β-agent k be similar to ψαqj−qiσ and η1βdi,k be similar to η1αdij, then the gradient-based term ωiβ in formula (10) can be described as(14)ω1β=−c1β∑k∈Niβη1βdik∇qiψβqk−qiσ,where di,k=qk−qi is the distance between α-agent i and β-agent k.


### 3.2. Consensus Term

Another distinguishing feature of the proposed algorithm is thatp^i,k in formula (10) is not the velocity vector of β-agent, but is the expected velocity of α-agent for all β-agents. If the expected velocity of α-agent for all β-agents at the current time is equal to the distance from the current position of α-agent to the expected position of α-agent at the next time divided by step time ∆t, then the key to the proposed algorithm is determining the expected position of α-agent.Before presenting the method to determine the expected position ofα-agent, we define the split point Si of α-agent i as the position where α-agent i was at the rejoin point Ri or did not perceive the obstacles preventing it from following γ-agent at the previous time, but it perceives the obstacles preventing it from following at the current time. In addition, we define the rejoin point Ri of α-agent i as the position where the distance between α-agent i and γ-agent is less than or equal to the distance between the split point Si and γ-agent. The generation process of the split point Si and rejoin point Ri are shown in Figure 3.Figure 3
Generation process of split point and rejoin point. (a) A split point generation example in whichα-agent did not perceive the obstacles preventing it from following at the previous time. (b) Another split point generation example in which α-agent was at the rejoin point at the previous time. (c) A rejoin point generation example.
(a)(b)(c)To make the expected position choice ofα-agent directional, we translate the coordinate system to make the origin of the coordinate system become the position of α-agent, rotate the coordinate system to make the positive direction of the x-axis point to the split point when α-agent is located in the open interval between the split point and rejoin point, and rotate the coordinate system to make the positive direction of the x-axis point to γ-agent when α-agent is located in the other interval. The expected position determination method of α-agent is defined as follows in two cases(1)
If theα-agent i is located at the split point (A1 scenario), the open interval between the split point and rejoin point (A2 scenario), or the rejoin point where it is prevented from following by some obstacles (A3 scenario) in Figure 4, we use the phase comparison method to determine the expected position of the α-agent i. Suppose that Mi is the number of obstacle boundary points perceived by α-agent i at the current time, θi,km is the phase between α-agent i and obstacle boundary point k at sequence number m, θi is the phase set between α-agent i and obstacle boundary points perceived by α-agent i, θi=sortθi,km,∀k∈Niβandm∈1,⋯,Mi, sort⋅ is the ascending function, and ∆θ is the discrimination threshold of phase discontinuity. If α-agent i chooses to bypass obstacles based on counterclockwise motion, the phases are compared from small to large. When θi,km at sequence number m minus θi,jm+1 at sequence number m+1 is greater than or equal to ∆θ, the expected position vector q^i of α-agent i is defined as the position vector of obstacle boundary point k corresponding to θi,km. It can be expressed as(15)q^i=qk,∀θi,km−θi,jm+1≥∆θandm=1⟶Mi,whereqk is the position vector of obstacle boundary point k, 1⟶Mi is the sequence number increasing from 1 to Mi. Similarly, if α-agent i chooses to bypass obstacles based on clockwise motion, the phases are compared from large to small. When θi,km at sequence number m minus θi,jm−1 at sequence number m−1 is greater than or equal to ∆θ, the expected position vector q^i of α-agent i is defined as the position vector of obstacle boundary point k corresponding to θi,km. It can be expressed as(16)q^i=qk,∀θi,km−θi,jm−1≥∆θandm=Mi⟶1,whereMi⟶1 denotes the sequence number decreasing from Mi to 1.(2)
If theα-agent i perceiving some obstacles is located in the other interval (A4 Scenario), we define the expected position vector q^i of α-agent i as the position vector of γ-agent. It can be expressed as(17)q^i=qγ.Figure 4
The process of determining the expected position. (a) A2 scenario. (b) A1 and A3 scenarios.
(a)(b)Thus, the consensus termϖiβ in formula (10) can be modified as(18)ϖiβ=c2β∑k∈Niβbi,kqp^i,k−pi,where the expected velocity vector p^i,k=q^i−qi/∆t for all β-agents within the sensing radius of α-agent i, and the expected position vector q^i under four scenarios are summarized in Table 2.Table 2
The expected position vector under four scenarios.
ScenarioMotion modeExpected position vectorq^iA1, A2, and A3Counterclockwiseq^i=qk,∀θi,km−θi,jm+1≥∆θandm=1⟶MiA1, A2, and A3Clockwiseq^i=qk,∀θi,km−θi,jm−1≥∆θandm=Mi⟶1A4—q^i=qγIn addition, theα,γ interaction term uiγ of the proposed algorithm is defined as uiγ=−c1γqi−qγ−c2γpi−pγ. Using formulas (7), (13), (14), and (18), the control input ui of the proposed algorithm can be expressed as(19)ui=uiα+uiβ+uiγ,uiα=−c1α∑j∈Niαη1αdij∇qiψαqj−qiσ+c2α∑j∈Niαaijqpj−pi,uiβ=−c1β∑k∈Niβη1βdik∇qiψβqk−qiσ+c2β∑k∈Niβbi,kqp^i,k−pi,uiγ=−c1γqi−qγ−c2γpi−pγ.


## 3.1. Gradient-Based Term

A distinguishing feature of the proposed algorithm as compared with the previous flocking algorithm with obstacle avoidance in Section2 is that the position of β-agent is not the projection position of α-agent on an obstacle surface but the position of the obstacle boundary point within the sensing radius of α-agent. Each obstacle boundary point within the sensing radius of α-agent corresponds to a β-agent. When the distance between α-agents or the distance between α-agent and β-agent is less than the minimum early-warning distance de, the possibility of collision between them may be greatly increased. To further reduce the possibility of collision, we divide the sensing radius region of α-agent into a separation region, an early-warning region, and an attraction region (see Figure 2), and define a nonnegative subsection function to adjust the weight of attractive/repulsive potential in these three regions.Figure 2
The sensing radius ofα-agent.The nonnegative subsection functionη1αdij is defined as(12)η1αdij=τaα,dij∈d,r,τeα,dij∈de,d,τsα,dij∈0,de,where τaα, τeα, and τsα are the weight factors, τsα≥τeα≥τaα≥0, de=dmin+2pimax∆t, dmin is the minimum safe distance, and dij=qj−qi is the distance between α-agent i and α-agent j.The gradient-based termωiα in formula (8) can be defined as(13)ωiα=−c1α∑j∈Niαη1αdij∇qiψαqj−qiσ.Let the attractive/repulsive potentialψβqk−qiσ between α-agent i and β-agent k be similar to ψαqj−qiσ and η1βdi,k be similar to η1αdij, then the gradient-based term ωiβ in formula (10) can be described as(14)ω1β=−c1β∑k∈Niβη1βdik∇qiψβqk−qiσ,where di,k=qk−qi is the distance between α-agent i and β-agent k.


## 3.2. Consensus Term

Another distinguishing feature of the proposed algorithm is thatp^i,k in formula (10) is not the velocity vector of β-agent, but is the expected velocity of α-agent for all β-agents. If the expected velocity of α-agent for all β-agents at the current time is equal to the distance from the current position of α-agent to the expected position of α-agent at the next time divided by step time ∆t, then the key to the proposed algorithm is determining the expected position of α-agent.Before presenting the method to determine the expected position ofα-agent, we define the split point Si of α-agent i as the position where α-agent i was at the rejoin point Ri or did not perceive the obstacles preventing it from following γ-agent at the previous time, but it perceives the obstacles preventing it from following at the current time. In addition, we define the rejoin point Ri of α-agent i as the position where the distance between α-agent i and γ-agent is less than or equal to the distance between the split point Si and γ-agent. The generation process of the split point Si and rejoin point Ri are shown in Figure 3.Figure 3
Generation process of split point and rejoin point. (a) A split point generation example in whichα-agent did not perceive the obstacles preventing it from following at the previous time. (b) Another split point generation example in which α-agent was at the rejoin point at the previous time. (c) A rejoin point generation example.
(a)(b)(c)To make the expected position choice ofα-agent directional, we translate the coordinate system to make the origin of the coordinate system become the position of α-agent, rotate the coordinate system to make the positive direction of the x-axis point to the split point when α-agent is located in the open interval between the split point and rejoin point, and rotate the coordinate system to make the positive direction of the x-axis point to γ-agent when α-agent is located in the other interval. The expected position determination method of α-agent is defined as follows in two cases(1)
If theα-agent i is located at the split point (A1 scenario), the open interval between the split point and rejoin point (A2 scenario), or the rejoin point where it is prevented from following by some obstacles (A3 scenario) in Figure 4, we use the phase comparison method to determine the expected position of the α-agent i. Suppose that Mi is the number of obstacle boundary points perceived by α-agent i at the current time, θi,km is the phase between α-agent i and obstacle boundary point k at sequence number m, θi is the phase set between α-agent i and obstacle boundary points perceived by α-agent i, θi=sortθi,km,∀k∈Niβandm∈1,⋯,Mi, sort⋅ is the ascending function, and ∆θ is the discrimination threshold of phase discontinuity. If α-agent i chooses to bypass obstacles based on counterclockwise motion, the phases are compared from small to large. When θi,km at sequence number m minus θi,jm+1 at sequence number m+1 is greater than or equal to ∆θ, the expected position vector q^i of α-agent i is defined as the position vector of obstacle boundary point k corresponding to θi,km. It can be expressed as(15)q^i=qk,∀θi,km−θi,jm+1≥∆θandm=1⟶Mi,whereqk is the position vector of obstacle boundary point k, 1⟶Mi is the sequence number increasing from 1 to Mi. Similarly, if α-agent i chooses to bypass obstacles based on clockwise motion, the phases are compared from large to small. When θi,km at sequence number m minus θi,jm−1 at sequence number m−1 is greater than or equal to ∆θ, the expected position vector q^i of α-agent i is defined as the position vector of obstacle boundary point k corresponding to θi,km. It can be expressed as(16)q^i=qk,∀θi,km−θi,jm−1≥∆θandm=Mi⟶1,whereMi⟶1 denotes the sequence number decreasing from Mi to 1.(2)
If theα-agent i perceiving some obstacles is located in the other interval (A4 Scenario), we define the expected position vector q^i of α-agent i as the position vector of γ-agent. It can be expressed as(17)q^i=qγ.Figure 4
The process of determining the expected position. (a) A2 scenario. (b) A1 and A3 scenarios.
(a)(b)Thus, the consensus termϖiβ in formula (10) can be modified as(18)ϖiβ=c2β∑k∈Niβbi,kqp^i,k−pi,where the expected velocity vector p^i,k=q^i−qi/∆t for all β-agents within the sensing radius of α-agent i, and the expected position vector q^i under four scenarios are summarized in Table 2.Table 2
The expected position vector under four scenarios.
ScenarioMotion modeExpected position vectorq^iA1, A2, and A3Counterclockwiseq^i=qk,∀θi,km−θi,jm+1≥∆θandm=1⟶MiA1, A2, and A3Clockwiseq^i=qk,∀θi,km−θi,jm−1≥∆θandm=Mi⟶1A4—q^i=qγIn addition, theα,γ interaction term uiγ of the proposed algorithm is defined as uiγ=−c1γqi−qγ−c2γpi−pγ. Using formulas (7), (13), (14), and (18), the control input ui of the proposed algorithm can be expressed as(19)ui=uiα+uiβ+uiγ,uiα=−c1α∑j∈Niαη1αdij∇qiψαqj−qiσ+c2α∑j∈Niαaijqpj−pi,uiβ=−c1β∑k∈Niβη1βdik∇qiψβqk−qiσ+c2β∑k∈Niβbi,kqp^i,k−pi,uiγ=−c1γqi−qγ−c2γpi−pγ.


## 4. Properties Analysis

Before presenting the properties analysis under the proposed algorithm, we define the system total energyHq,p as the sum of the total potential energy between α-agents, the total potential energy between α-agent and β-agent, the total potential energy between α-agent and γ-agent, and the kinetic energy between α-agent and γ-agent. It can be expressed as(20)Hq,p=12∑i=1Nc1αViαq+2c1βViβq+c1γqi−qγTqi−qγ+pi−pγTpi−pγ,where(21)Viαq=∑j∈Niαη1αdijψαqj−qiσ,(22)Viβq=∑k∈Niβη1βdikψβqk−qiσ.We also define the system total energy att=0 as H0.Theorem 1.
Consider a system withNα-agents applying the control input (19) with multiagents motion model (2). Suppose that the β-agent and γ-agent are the static agent, the weight factor τsα and τsβ are big enough, and H0 is finite, then the following statements hold:(i)
The distance betweenα-agent and γ-agent is not larger than 2H0/c1γ for all t≥0;(ii)
There is no collision betweenα-agents and between α-agent and β-agent at any time.Proof.
We first prove the part (i) of Theorem1. By differentiating Hq,p in formula (20), we have(23)H˙q,p=12∑i=1Nc1αV˙iαq+∑i=1Nc1βV˙iβq+∑i=1Nc1γpiTqi−qγ+∑i=1NpiTui.
Sinceβ-agent and γ-agent are the static agent, then we have q˙k=pk=0 and q˙γ=pγ=0. In addition, since ∇qj−qiViαq=∇qjViαq=−∇qiViαq and ∇qk−qiViβq=∇qkViβq=−∇qiViβq, formula (23) can be rewritten as(24)H˙q,p=c1α∑i=1NpiT∇qiViαq+c1β∑i=1NpiT∇qiViβq+∑i=1Nc1γpiTqi−qγ+∑i=1NpiTui.
Sincep^i,k for all β-agents within the sensing radius of α-agent i are equal, then let p˜=colp1,⋯,pN,p^1,k,⋯p^N,k. Formulating (19), (21), and (22) into (24), we have(25)H˙q,p=−c2α∑i=1N∑j∈NiαaijqpiTpi−pj−c2β∑i=1N∑k∈Niβbi,kqpiTpi−p^i,k−c2γ∑i=1NpiTpi=−p˜TL⊗Imp˜,where L=c2α∆A−A+c2β∆B+c2γEN×N0N×N−c2βB0N×N, ∆A is a diagonal matrix with diagonal elements ∑j∈Niαaijq, A is an adjacency matrix, A=aijq, ∆B is a diagonal matrix with diagonal elements ∑k∈Niβbi,kq, B is an adjacency matrix, B=bi,kq, EN×N is a N-order identity matrix, and ⊗ is the Kronecker product.
Sincec2α, c2β, and c2γ are the positive numbers, and ∆A−A and ∆B are the positive semidefinite matrix, then L is a positive semidefinite matrix. Consequently, we have −p˜TL⊗Imp˜≤0, that is H˙q,p≤0, which implies that the system total energy Hq,p is a nonincreasing function, and thus Hq,p≤H0 for all t≥0. From formula (20), we have c1γqi−qγTqi−qγ≤2H0 for any α-agent i. Hence, the distance betweenα-agent and γ-agent is not greater than 2H0/c1γ for all t≥0.
Next, we prove the part (ii) of Theorem1 by contradiction. Suppose that α-agent i collides with α-agent j or obstacle boundary point k at t∗. Since the weight factor τsα and τsβ are big enough, then Viαq or Viβq tends to infinity. In addition, since H0 is finite, we have Hq,p>H0. This contradicts the proof that Hq,p is a nonincreasing function. Consequently, there is no collision at any time.


## 5. Simulations

In this section, we first illustrate the effectiveness of the proposed algorithm by comparing it with the Olfati-Saber flocking algorithm with obstacle avoidance. In this example, the simulation is performed on 30α-agents and a γ-agent moving in a two-dimensional Euclidean space with two spherical obstacles and a wall obstacle. The initial position vectors of 30 α-agents are selected randomly from 10,30×5,20, the initial velocity vectors of 30 α-agents are selected randomly from 0,2×0,2, the initial position vector of γ-agent is 75,80T, and the initial velocity vector of γ-agent is zero. The parameters of the proposed algorithm and the Olfati-Saber algorithm are shown in Table 3. The experiments were run continuously for 300 s under the three scenarios of spherical and wall obstacle independence, spherical obstacle combination, and spherical and wall obstacle combination, and the results are shown in Figures 5 and 6.Table 3
Simulation parameters.
ParameterValueN30r6d4ε0.5h0.2a2b20c1α1c2α1c1β1c2β1c1γ1c2γ1τaα0.1τeα10τsα10000∆θπ/4pimax5 m/sdmin1 m∆t0.1 sFigure 5
Motion process of the two algorithms under the independence scenario of spherical and wall obstacles. (a) Olfati-Saber algorithm. (b) Proposed algorithm. (c)x trajectories. (d) y trajectories.
(a)(b)(c)(d)Figure 6
Minimum distance betweenα-agent and objects.In Figures5(a) and 5(b), the black cylinder is the spherical obstacle, the black cuboid is the wall obstacle, the green triangle is the γ-agent, the red Coccinella septempunctata is the α-agent, the blue solid line between red circles is the neighborhood relationship between α-agents, and the red dotted lines are the motion trajectories of 30 α-agents. It can be seen from these figures that the two algorithms can enable all α-agents to bypass independent spherical or wall obstacles on their way. In Figures 5(c) and 5(d), the red, blue, and green solid lines represent the center positions (1/N∑i=1Nqi) of 30 α-agents in the Olfati-Saber flocking algorithm with obstacle avoidance, the center positions of 30 α-agents in the proposed algorithm, and the position of γ-agent, respectively. It can be observed that the convergence time of the proposed algorithm is decreased by more than 80% compared with the Olfati-Saber flocking algorithm with obstacle avoidance, which indicates that the proposed algorithm can make α-agent bypass obstacles faster. Figure 6 shows the minimum distance between α-agent and objects (e.g., other α-agents or obstacles), and it can be observed that the minimum distances of the two algorithms are greater than the minimum safe distance dmin. This indicates that there is no α-agent that collided with other α-agents or obstacles, and it also demonstrates that the proposed algorithm can ensure that α-agent bypass obstacles without collision.In Figures7 and 8, the black circle is the spherical obstacle, the black solid line is the wall obstacle, the green triangle is the γ-agent, and the red circle is the α-agent. Figures 7 and 8 show that many α-agents stop near the combination position of two obstacles, and it is difficult to bypass these obstacles in the Olfati-Saber flocking algorithm with obstacle avoidance. A possible reason for this is that the projection velocity here does not point in the direction of bypassing these obstacles. However, the proposed algorithm can enable all α-agents to bypass these obstacles, as well as enable all α-agents to regroup. This demonstrates that the proposed algorithm can relax the constraints of obstacle shape and boundary in the Olfati-Saber flocking algorithm with obstacle avoidance and has better environmental adaptability.Figure 7
Motion process of the two algorithms under the combination scenario of two spherical obstacles. (a) Olfati-Saber algorithm. (b) Proposed algorithm.
(a)(b)Figure 8
Motion process of the two algorithms under the combination scenario of spherical and wall obstacles. (a) Olfati-Saber algorithm. (b) Proposed algorithm.
(a)(b)To further demonstrate the environmental adaptability of the proposed algorithm, we selected 30–60α-agents and a γ-agent to move in a two-dimensional Euclidean space with multiple obstacles such as a diamond obstacle, a spherical obstacle, and a C-shaped obstacle. The algorithm parameters are shown in Table 3. The initial position vectors of 30–60 α-agents are selected randomly from 2,30×5,30, the initial velocity vectors of 30–60 α-agents are selected randomly from 0,2×0,2, the initial position vector of γ-agent is 75,25T, and the initial velocity vector of γ-agent is zero. The experiments were run continuously for 300 s.Figure9 shows the motion trajectories of 30 and 60 α-agents under multiple obstacles. It can be seen that all α-agents can move along the boundary of obstacles, bypass obstacles, and finally converge on the γ-agent at the center position of all α-agents. In Figure 10, we show the minimum distance between α-agent and objects (e.g., other α-agents or obstacles) for randomly generated 30, 40, 50, and 60 α-agents following the γ-agent 100 times under multiple obstacles. It can be observed from the figure that the minimum distance is always greater than the minimum safe distance dmin, which illustrates that the proposed algorithm can reduce the influence of the number of α-agents on the minimum distance and can also find a reasonable route to bypass obstacles without collision and follow the γ-agent in the complex environment.Figure 9
Motion process of 30 and 60α-agents under multiple obstacles. (a) 30 α-agents. (b) 60 α-agents. (c) x trajectories. (d) y trajectories.
(a)(b)(c)(d)Figure 10
Minimum distance betweenα-agent and objects in 100 simulation times.


## 6. Conclusions

In this paper, we regarded each obstacle boundary point within the sensing radius ofα-agent as a virtual β-agent and designed an obstacle boundary point and an expected velocity-based flocking algorithm for multiagents with obstacle avoidance. Under the proposed algorithm, we proved that the collision-free motion of multiagents can be realized when the sufficient conditions in Theorem 1 hold. Three examples under the independence scenario of spherical and wall obstacles, the combination scenario of two spherical obstacles, and the combination scenario of spherical and wall obstacles are presented to show that the proposed algorithm can relax the constraints of obstacle shape and boundary in Olfati-Saber’s flocking algorithm with obstacle avoidance. Besides, an example under multiple obstacles is given to illustrate that the proposed algorithm with better environmental adaptability can make α-agent quickly bypass obstacles without collision and follow the γ-agent. Future works will consider the influence of time delay and external disturbance in the proposed algorithm.



---

*Source: 1493299-2023-02-20.xml*