# H

Authors: Dong Xue; Jing Yao; Jun Wang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A new concept ofH∞ formation is proposed to handle a group of agents navigating in a free and an obstacle-laden environment while maintaining a desired formation and changing formations when required. With respect to the requirements of changing formation subject to internal or external events, a hybrid multiagent system (HMAS) is formulated in this paper. Based on the fact that obstacles impose the negative effect on the formation of HMAS, the H∞ formation is introduced to reflect the above disturbed situation and quantify the attenuation level of obstacle avoidance via the H∞-norm of formation stability. An improved Newtonian potential function and a set of repulsive functions are employed to guarantee the HMAS formation-keeping and collision-avoiding from obstacles in a path planning problem, respectively. Simulation results in this paper show that the proposed formation algorithms can effectively allow the multiagent system to avoid penetration into obstacles while accomplishing prespecified global objective successfully.


---

## Body

## 1. Introduction

In recent years, there has been a spurt of interest in the area of cooperative control for multiple agents due to its challenging features and many applications, for example, formation control [1, 2], obstacles avoidance [3, 4], rendezvous [5], flocking [6], foraging [7], troop hunting, and payload transport. Referring to the existing literature, it is obvious that multiple agents can perform tasks faster and more efficiently than a single one. The existing approaches for cooperative control of MASs fall into several categories, including behavior-based, artificial potential, virtual structure, leader-follower, graph theory, and decentralized control methods. Other methods and research aspects of the cooperative control for MASs can be found in [8–10].As one key branch of cooperative control, formation and obstacle avoidance problems of multiagent systems have been received significant attentions [1–4, 8, 11]. In this case, the MAS is usually required to follow a trajectory while maintaining a desired formation and avoiding obstacles. In some practical situations, the group of agents may be necessary to perform certain maneuvers, such as split, reunion and reconfiguration, in order to negotiate the obstacles [2, 12]. Although the formation problem for MASs is attracting increasingly research attention, there are still several open fields deserving further investigation, such as robustness, fragility, and effectiveness of formation. With respect to the most robustness analysis of MASs, such as [13–15], the agents are investigated under uncertain environments with external disturbances. However, in some sense, obstacles in the navigational path can also be regarded as a disturbance from environment, which would impair the performance of formation stability. Furthermore, the influence of obstacles is usually negligible when the distances between agents and obstacles exceed certain range threshold. Inspired by obstacle avoidance issue and H∞ control theory, we introduce a new concept of H∞ formation, which treats the effects of obstacles as certain exterior disturbances, to handle the formation problem of MASs in clustered environment. Then a Lyapunov approach is employed to deal with H∞ analysis.Artificial potential field (APF) method is widely used in coordination control of MASs due to its simplicity and efficiency [7, 16], which was first introduced by [17] for formation and obstacle avoidance of MASs. Since then, several literatures have attempted to improve the performance of APF method. In [18], bifurcation theory is used to reconfigure the formation through a simple free parameter change to reduce the computational expense. By introducing a new concept of artificial potential trenches in [11], the scalability and flexibility of robot formations are improved. The basic idea of potential field theory is to create a workshop, where the agents are counterbalanced with each other by the interactive potential force between them and suffered a repulsive force from obstacles to steer around them [19]. Despite all the advantages of APFs, the lack of accurate representations of obstacles with arbitrary shapes is regarded as one major limitation to generally extend to practical applications. A potential function based on generalized sigmoid functions, which can be generated from the combinations of implicit primitives or from sampled surface data is proposed in [20]. Using the optical flow, [21] have achieved the automatic detection of obstacles in virtual environment. The formation control with obstacle avoidance is highly related to the flocking problems in [6], where only the obstacles with simple shapes are taken into account. In this paper, we assume that the boundary functions of arbitrary obstacles can be known from the implicit functions which can be constructed from sensor readings or image data. By combining the artificial potential model and the negotiating results with obstacles, a resultant artificial repulsive force is developed to guarantee the obstacles avoidance.In addition, it may happen that the MASs are desired to perform various formation shapes to achieve specified navigational objective. As a result, it is necessary for the MAS to possess the ability of changing formation shape during the navigation, such as split, rejoin, and reconfiguration. In this case, the MASs consist of both continuous variables and discrete events. In [2], a triple (group element 𝔤, shape variable 𝔯, control graph ℌ) is employed to model the mobile robots and meet the requirement of changing formations. Furthermore, a Petri-potential-fuzzy hybrid controller is presented for the motion planning of multiple mobile robots with multiple targets in a clustered environment in [22]. In this paper, a hybrid formation controller is proposed where the formation changes as events (tasks) occur. In practice, the correspondence between tasks and formation can be prespecified at the initialization step, and created intelligently by the embedded processors in each agent during the implementation. It is remarkable that the hybrid multiagent systems exhibit continuous-state dynamics and discrete behavior jumping between formations. Then, we formulate the HMAS by a hybrid machine owing to its advantages of illustrating inputs and outputs explicitly [23, 24].The paper proceeds as follows. The formation control and obstacle avoidance problem are addressed in Section2. In Section 3, a new concept of H∞ formation and technical proofs are provided. In Section 4, we discuss the obstacle-avoidance functions. Simulation results to illustrate the results are presented in Section 5. Conclusions and future work are provided in Section 6.Notation 1.
Throughout the paper, letℤ¯ be the set of positive integers, and let 𝕁=[t0,+∞)(t0≥0). ℝn represents the real Euclidean n-dimensional vector space. For x=(x1,…,xn)⊺∈ℝn, the norm of x is ∥x∥≜(x⊺x)1/2, where the symbol (·)⊺ denotes the transpose of a matrix or a vector. In denotes the identity matrix of order n (for simplicity I if no confusion arises). 𝔏2[0,∞) is the Lebesgue space of Rn-valued vector-functions g(·), defined on the time interval [0,∞), with the norm ∥g∥2≜(∫0∞‍∥g(t)∥2)1/2dt.


## 2. Problem Formulation and Preliminaries

Consider a multiagent system withN nodes and an undirected graph topology 𝔊=(ν,ε); ν and ε are the set of vertices and the set of edges (i.e, ε∈ν×ν), respectively. The notation (i,j) or (j,i) equivalently denotes the edge of the graph between node i and node j. Furthermore, a graph is connected if there exists a path between every pair of distinct nodes; otherwise it is disconnected.Before proceeding further, the following assumptions are made in this paper.(1)
Each agent is equipped with sensors and computational hardware that allow it to detect the distances to the obstacles within the sensing range. Furthermore, the agent can access its position in the world coordinate system and broadcast to its neighboring agents. The wireless communication has a limited range and is assumed to be imperfect; that is, links may be broken.(2)
The multiagent system has a task setΣ and a formation set 𝔽 which meet actual project needs before initiation. And suppose that all agents know the information of Σ and 𝔽, as well as the desired formation shape and trajectories in every step.Referred to hybrid machine presented in [23, 24] and associated with the practical application, we consider a special class of hybrid multiagent system (HMAS) which is modeled by an elementary hybrid machine (EHM) [25] as follows:
(1)HMAS=(Q,Σ,Dy,E,(Δ0,x(0))).
The elements of HMAS are denoted as follows. Q={q0,q1,…,qm-1} is a set of vertices (discrete states); in formation control, each discrete state qi∈Q corresponds to a desired formation shape Δi, and we denote a set of formation shape by 𝔽:={Δ0,Δ1,…,Δm-1}. Σ={ℋqiqj,qi,qj∈Q} (i,j=0,…,m-1) is a finite (task) set of event labels; (q0,x(0)) is the initial desired formation and state of HMAS, respectively. E={(qi,ℋqiqj,qj,xq00):qi,qj∈Q} is a set of edges (transition-paths), where qi is the exited vertex and qj is the entered one. If the event ℋqiqj is triggered, consequently the formation of HMAS transits from Δi to Δj. For example, Figure 1 shows a sequence of admissible collective behaviors of a HMAS triggered by event set Σ={form,dismiss,split,unite,transform1,transform2}.Figure 1
Example of a hybrid multiagent system performing under different events.Remark 1.
In practical application, the multiagent system is always assigned multiple tasks in the navigation, and each task may correspond to multiple formation shapes. Similarly to the deterministic automaton described in [26], we suppose that the HMAS is deterministic; namely, there cannot be two transitions with the same event label. It is worth mentioning that the following theoretical analysis is available for nondeterministic HMAS; that is, there can be multiple transitions triggered by the same event.D
y is the dynamics of HMAS and for each agent i and q∈Q, which is described by
(2)x˙i(t)=f(t,x)+∑j=1N‍Jij(t)xj(t)+uiq(t)+Ciwi(t),
where i∈{1,2,…,N}, t∈𝕁, xi(t)∈ℝn×1, x=[x1⊺,x2⊺,…,xN⊺]⊺, and Ci are real constant matrices with appropriate dimensions. f(t,x):𝕁×ℝN×n→ℝn×1 is continuously differentiable, representing the group motion (i.e., path of the HMAS). J(t)=(Jij(t))N×N is the time-varying coupling configuration matrix representing the communication strength and communicational topology of the HMAS. If there is an interconnection between agent i and agent j(j≠i), then Jij(t)=Jji(t)>0; otherwise, Jij(t)=Jji(t)=0, and the diagonal elements of matrix J(t) are defined by
(3)Jii(t)=-∑j=1,j≠iN‍Jij(t)=-∑j=1,j≠iN‍Jji(t).wi(t) here denotes the obstacle-avoiding function, which will be derived from potential function in Section 6.Moreover, the formation controller in this paper is derived by extending the one in [1] into multiformation case (q∈Q):
(4)uiq(t)=∑j=1j≠iN‍2(xj(t)-xi(t)-Δijq)×[e-(1/Lr2+1/La2)∥xj(t)-xi(t)-Δijq∥2SaLa2e-∥xj(t)-xi(t)-Δijq∥2/La2-SrLr2e-∥xj(t)-xi(t)-Δijq∥2/Lr2+Sr(1Lr2+1La2)×e-(1/Lr2+1/La2)∥xj(t)-xi(t)-Δijq∥2[SaLa2e-(∥xj(t)-xi(t)-Δijq∥2/La2)],
where Δijq∈ℝn×1 and Δq=(Δijq)N×N∈𝔽 is the formation-shape matrix of the multiagent system with Δijq=-Δjiq and Δiiq=0. Parameters Sa, Sr, La, and Lr are positive constants representing the strengths and effect ranges of the attractive and repulsive forces, respectively; and with the following constraint we have
(5)SaSr>La2Lr2e(-1/Lr2-1/La2)∥xj(t)-xi(t)-Δijq∥2-(1+La2Lr2)e-(∥xj(t)-xi(t)-Δijq∥2/Lr2),
where La>Lr.Remark 2.
Compared to the formation controller given in [1], the formation controller in this paper is designed to achieve more complicated control objects, such as formation switching in clustered environment. Furthermore, it is worth mentioning that the obstacle-avoiding function wi(t) (i=1,…,N) as a part of the controller is an important contribution for this paper.In order to simplify (4), define
(6)φijq(t)=2[e(-1/Lr2+1/La2)(∥xj(t)-xi(t)-Δijq∥2)SaLa2e-(∥xj(t)-xi(t)-Δijq∥2/La2)-SrLr2e-(∥xj(t)-xi(t)-Δijq∥2/Lr2)+(SrLr2+SrLa2)×e(-1/Lr2+1/La2)(∥xj(t)-xi(t)-Δijq∥2)SaLa2e-(∥xj(t)-xi(t)-Δijq∥2/La2)].
According to (5), one can verify φijq(t)>0, and the necessity of this constraint can be addressed by referring to that the force vector and position vector are unidirectional.Then rewrite the formation controller (4) as follows:
(7)uiq(t)=∑j=1j≠1N‍φijq(t)(xj(t)-xi(t)-Δijq),q∈Q.Remark 3.
Letφijq(t) be a continuous function with respect to ∥xj(t)-xi(t)-Δijq∥, and it is easy to prove that if the bounds of ∥xj(t)-xi(t)-Δijq∥ exist, then φijq(t) is bounded on all sets of ∥xj(t)-xi(t)-Δijq∥ (i,j=1,…,N and q∈Q). Furthermore, regard the fact that most multiagent systems are implemented in finite horizon which means the limitation of interagent distances exists. Throughout the paper, we assume that the lower bound of φijq(t) exists, and we denote it by
(8)0<φ¯≤mini,j=1,…,Nq=0,…,m-1φijq(t),
where φ¯>0 can be guaranteed by choosing appropriate values of La, Lr, Sa, and Sr in the constraint (5).


## 3. Analysis ofH∞ Formation Stability

Now, this section will analyzeH∞ formation stability of the above-developed framework of HMAS in a free and an obstacle-laden environment, respectively.Since we have property (3), the HMAS (1) is equivalent to
(9)x˙i(t)=f(t,x)+∑j=1N‍Jij(t)(xj(t)-xi(t))+uiq(t)+Ciwi(t).Before moving on, we need to note that the formation switching in the controller will introduce discontinuities to the right hand side of (9). With respect to the dwell-time theory in [27], if the switching of a family of individually stable systems is sufficiently slow, then overall systems remain stable. As a result, we assume that the intervals between consecutive switching signals, that is, dwell time, are large enough. Due to the introduction of average dwell-time, this assumption does not represent a restriction because this concept allows the formation switching mechanism to be more flexible provided that the average interval between consecutive switching is no less than certain fixed positive constant.To investigate the formation control of MAS, we introduce a measurement errorXij(t) given as
(10)Xij(t)=xj(t)-xi(t).
It follows from (5), (9), and (10) that the time derivative of Xij(t) is as follows:
(11)X˙ij(t)=∑k=1N‍(Jjk(t)Xjk(t)-Jik(t)Xik(t))+Cjwj(t)-Ciwi(t)+∑k=1N‍(φjkq(t)(Xjk(t)-Δjkq)-φikq(t)(Xik(t)-Δikq)(φjkq(t)(Xjk(t)-Δjkq)).For a formation of multiple agents moving in a clustered environment, it is inevitable to encounter various obstacles which affect the performance of formation or even break the whole system down. Naturally, the multiagent system is desirable to be able to adapt to the environment. In general, the agents are only affected by the obstacles when they enter a certain region. At other times, the influence being exerted from obstacles can be negligible. With the above analysis, the obstacles can be treated as exogenous disturbances deriving from the environment, andH∞ analysis can be employed to investigate the formation stability of HMAS.Associating the system (2) with the formation controller (7), we define a disagreement function similar to [28] as follows:
(12)Φ(Xij(t))=1N∑i=1N-1‍∑j>iN‍∥Xij(t)-Δijq∥2,
which demonstrates the formation performance of HMAS for q∈Q.For the HMAS given in (2), H∞ formation stability means to find a formation controller (7) such that the following conditions in (DF1) and (DF2) hold.(
DF1
). The formation of HMAS (1) is asymptotically stable when w(t)=0, where w(t)=[w1⊺,w2⊺,…,wN⊺]⊺, which is equivalent to the asymptotical formation stability of the HMAS (1) in the absence of obstacles. That is to say that, all agents asymptotically converge to the desired formation positions; that is, ∥Xij(t)-Δijq∥→0 as t→∞, where q∈Q.(
DF2
). The formation controller ensures a certain level of H∞ formation performance as follows:
(13)supXij(0)ωi≠0∫0∞‍Φ(Xij(t))dt(1/4N)∑i=1N∑j=1N∥Xij(0)-Δijq∥2+(1/N)∑i=1N∥wi(t)∥22((14N)∑i=1N∑j=1N∥Xij(0)-Δijq∥2<γ
for initial states xi(0)∈ℝn×1 and q∈Q, where γ≥1 is a constant, Xij(0)=xj(0)-xi(0), and Φ(Xij(t)) is given by (12). If the conditions (DF1) and (DF2) hold, then the formation of HMAS (1) is said to achieve the H∞ formation stability.Remark 4.
It is worthwhile noting that (DF2) is a standard condition arising from the H∞ control theory, which implies that Xij, (i,j=1,…,N), converges to Δijq in the sense of 𝔏2.Remark 5.
According to (DF2), the attenuation level γ≥1 shows the sensitivity of obstacle avoidance in HMAS (1). Giving a smaller γ≥1 means that the intensity and range of reaction of HMAS towards obstacles are smaller.Theorem 6.
Given a positive scalarγ≥1, the H∞ formation problem of the HMAS (1) under the conditions (DF1) and (DF2) is solved at initial positions xi(0)∈ℝn, if
(14)[-πij+IN00-CiN0-πijπij+χij200πij⊺+χij⊺2-χij0-Ci⊺N00-2γN2]<0
holds for all i,j=1,2,…,N, where
(15)πij=(φ¯+Jij)I2,χij=(φ¯-Jij)I2,
and φ¯ is defined in (8).Proof.
Without the loss of generality, construct a common Lyapunov function in the form of(16)V=14N∑i=1N‍∑j=1N‍∥Xij(t)-Δijq∥2,
where q∈Q. If the derivative of V with respective to (9) is constantly negative for all subsystems, then the formation of HMAS (1) is stable. For the sake of convenience, Xij(t) is implicitly rewritten as Xij, as well as Jij(t), φijq(t), and wi(t) in the proof.
From the above discussion, one has(17)V˙=12N∑i=1N‍∑j=1N‍(Xij-Δijq)⊺X˙ij=12N∑i=1N‍∑j=1N‍∑k=1N‍[(Xij-Δijq)⊺(JjkXjk-JikXik)]︸v1+1N∑i=1N‍∑j=1N‍∑k=1N‍φjkq(Xij-Δijq)⊺(Xjk-Δjkq)︸v2+12N∑i=1N‍∑j=1N‍(Xij-Δijq)⊺(Cjwj-Ciwi)︸v3.
In respect that the coupling configuration matrixJ(t) is symmetric, and Xij=-Xji, Δijq=-Δjiq, Xii=0, and Δjjq=0, one has
(18)v1=-1N∑i=1N‍∑j=1N‍∑k=1N‍(Xji-Δjiq)⊺JjkXjk=-1N∑i=1N‍∑k=1N‍∑k<jN‍(Xji-Δjiq)⊺JjkXjk-1N∑i=1N‍∑k=1N‍∑k>jN‍(Xji-Δjiq)⊺JjkXjk︸v11.
Renamingj in the v11 as k, thus one has
(19)v1=-1N∑i=1N‍∑k=1N‍∑k<jN‍[(Xji-Δjiq)⊺-(Xki-Δkiq)⊺]JjkXjk.
One can find the fact thatXji⊺-Xki⊺=Xjk⊺ and Δjiq-Δkiq=Δjkq; then
(20)v1=-1N∑i=1N‍∑k=1N‍∑k<jN‍(Xjk-Δjkq)⊺JjkXjk=-∑i=1N‍∑j>iN‍(Xij-Δijq)⊺JijXij.
Using the standard completing the square argument, it follows from (20) that
(21)v1=-12∑i=1N-1‍∑j>iN‍Jij∥Xij-Δijq∥2-12∑i=1N-1‍∑j>iN‍Jij∥Xij∥2+12∑i=1N-1‍∑j>iN‍Jij∥Δijq∥2.
Furthermore, thev2 is similarly analyzed as follows:
(22)v2=-∑i=1N‍∑j>iN‍φijq(Xij-Δijq)⊺(Xij-Δijq).
With respect to (8), one can easily obtain
(23)v2≤-φ¯∑i=1N-1‍∑j>iN‍(Xij-Δijq)⊺(Xij-Δijq)=φ¯2∑i=1N-1‍∑j>iN‍(2Xij⊺Δijq-∥Xij-Δijq∥2-∥Xij∥2-∥Δijq∥2∥Xij-Δijq∥2).
Then, forv3, one has
(24)v3=-2N∑i=1N-1‍∑j>iN‍(Xij-Δijq)⊺Ciwi.
Now, we consider the formation stability of HMAS (1) with w(t)=0. From the inequalities (21) and (23), V˙ becomes
(25)V˙≤∑i=1N-1‍∑j>iN‍Ωij⊺[-πij000-πijπij+χij20πij⊺+χij⊺2-χij]Ωij,
where Ωij=[(Xij-Δijq)⊺,Xij⊺,(Δijq)⊺]⊺, πij, and χij are given in (15). By the Schur complement formula, the achievement of inequality (14) is equivalent to the following inequalities satisfied as follows:
(26)[-πij+IN000-πijπij+χij20πij⊺+χij⊺2-χij]<0,[CiN00]⊺[πij-IN000πij-πij+χij20-πij⊺+χij⊺2χij]-1[CiN00]<2γN2.
By nonnegative matrix theory, one can easily find that
(27)[-πij000-πijπij+χij20πij⊺+χij⊺2-χij]≤[-πij+IN000-πijπij+χij20πij⊺+χij⊺2-χij]<0,
which implies V˙<0. This proves that condition (DF1) holds for the HMAS (1) with w(t)=0.
Next, we prove theH∞ performance constraint (DF2) for all nonzero wi(t)∈𝔏2[0,∞) and a prescribed γ≥1. Define
(28)V~=∫0∞‍(Φ(Xij(t))-γ1N∑i=1N‍wi⊺(t)wi(t))dt-γ2N∑i=1N-1‍∑j>iN‍∥xj(0)-xi(0)-Δijq∥2,
and one has
(29)V~=∫0∞‍(Φ(Xij(t))-γN∑i=1N‍wi⊺(t)wi(t)+V˙(x(t)))dt-V(x(∞))+1-γ2N∑i=1N-1‍∑j>iN‍∥xj(0)-xi(0)-Δijq∥2≤∫0∞‍(Φ(Xij(t))-γN∑i=1N‍∥wi(t)∥2+V˙(x(t)))︸Ξdt.
Combining (21), (23), and (24), one obtains
(30)Ξ=∑i=1N‍∑j=1N{[-πij2000-πij2πij+χij40πij⊺+χij⊺4-χij2]12N∥Xij-Δijq∥2-γN2wi⊺wi‍-1N(Xij-Δijq)⊺Ciwi+Ωij⊺[-πij2000-πij2πij+χij40πij⊺+χij⊺4-χij2]Ωij}=∑i=1N‍∑j=1N‍ξij⊺×[-πij2+I2N00-Ci2N0-πij2πij+χij400πij⊺+χij⊺4-χij20-Ci⊺2N00-γN2]ξij,
where ξij=[Ωij⊺,wi⊺(t)]⊺. From the LMI (14), it is easy to prove Ξ<0 which implies V~<0 and immediately leads to the inequality (13).
Therefore, the formation of HMAS (1) has the property of H∞ criteria (DF1) and (DF2). This completes the proof.Remark 7.
By studying the LMIs (14), the variables χij>0 in (15) indicate the connectivity strength among agents. In particular, due to the monotone decreasing property of φij with respect to norm ∥xj(t)-xi(t)-Δij∥ and the discussion in Remark 3, this connectivity strength is inversely proportional to the relatively active scope of MASs.


## 4. Design Obstacle-Avoiding Functions

In this section, collision avoidance in trajectory tracking is achieved using mutual repulsion between agents and obstacles, which is resulted from the Newtonian potential-based model. By regarding the agents and obstacles as conductors with uniform charges, the repulsive force inversely proportional to the distance of them can be derived in closed form.Based on practical applications in robotics and haptic rendering, an ideal potential field should possess all of the following attributes.(i)
With respect to the property of obstacle avoidance, the magnitude of potential and corresponding repulsion should be infinite at the boundary of obstacles and drop off with distance. And the range of potential is bounded, which is accordant with the limited detective scope of agent’s built-in explorer in this paper.(ii)
The shapes of equipotential surface should be similar with the obstacle surface and spherical symmetrical at the boundary of potential field.(iii)
The first and second derivatives of potential function should exist and be continuous, so that the resulting force field is smooth.Before moving on, for making this paper self-contained, we revisit the general definition of external disturbance in theH∞ problem. H∞ techniques are usually used to evaluate the incremental gain of external input signal in any direction and at any frequency. In the context of H∞ theory, the external signals with finite energy are often investigated; that is, ∥w(t)∥≤∞. More explicitly, the finite energy signal w(t) is said to belong to L2[0,∞), which implies
(31)[∫0∞‍∥w(t)∥2dt]1/2=[∫0∞‍∑i=1N‍wi⊺(t)wi(t)dt]1/2<∞.In order to utilizeH∞ theory to design obstacle-avoidance controller, we assume that multiagent systems ultimately get far from the obstacles as time evolves. Incorporated with attributes (ii) this assumption leads to limt→∞w(t)=0. That is, the obstacle-avoidance functions wi(t) are available in finite time intervals. In addition, for avoiding obstacles, the agent-obstacle distances are intuitively greater than zero, and consequently the supremum of function wi(t) (i=1,…,N) exists. Based on above analysis on obstacle-avoidance function, one can easily derive the conclusion that w(t) belongs to L2[0,∞).Now, we will discuss the obstacle-avoiding function beginning with the instance of mass points (when the bulks of agents and obstacles are close to each other) and then extending to bulky obstacles (over10 times bigger than agent) with arbitrary shapes.Consider that an agenti navigates in an obstacle-laden environment with M∈ℤ¯+ obstacles, and assume that sl∈ℝn is the position of obstacle l (l∈{1,2,…,M}). The potential at agent i due to obstacle l is
(32)Pilo(t)=ρil∥xi(t)-sl∥,
where ρil is the repulsion coefficient for obstacles avoidance and is defined as follows:
(33)ρil={ρ,∥xi(t)-sl∥<δ0,∥xi(t)-sl∥≥δ,
where ρ is a positive scalar and δ is the maximal sensing range of agent. When the relative distance of agent i and obstacle l is shorter than that of the detective scope δ, agent i will receive a signal of possible collision and the obstacle-avoiding function will work. In other words, the repulsive potentials between agents and obstacles act only when they get close to certain range. Now, the obstacle-avoiding function for agent i is introduced based on the negative gradient of the potential (32) in the following form:
(34)wi(t)=-∇xiPilo(xi,sl)=∑l=1M‍ρilxi(t)-sl∥xi(t)-sl∥3.Then we extend the obstacle-avoiding function for the bulky objects with arbitrary shapes. In practical situations, particularly in many exploration applications, the implicit functions of obstacles to be modeled are not available. But by samples of boundary surfaces obtained from camera, laser range finder and sonar, and with the help of some techniques such as signal sampling and image processing, the implicit functions can be obtained, and then they construct the APFs [20]. For convenience, in this paper, assume that the boundary function of obstacle l is known as Bl, and βl here is the position of arbitrary point on the boundary of obstacle. In fact, most of obstacles can be mathematically approximated with polyhedron. In this paper we focus on the convex polyhedra obstacles. Moreover, the results can be easily extended to obstacles with arbitrary shapes. The repulsion between agent i and an arbitrary point of the obstacle’s boundary is
(35)Filo(t)=ρilxi(t)-βl∥xi(t)-βl∥3,
where ρil are defined in (33). Then for the agent i the obstacle-avoiding function is defined as
(36)wi(t)=∑l=1M‍∮BldFilo,
where ∮Bl represents the surface integrals on boundary of obstacles.In view of above analysis, the obstacles laden in the terrain are static. However, it is worth mentioning that all the obstacle-avoidance functions are available for moving obstacles except for those with high-speed. In this case, the position vectorβl(t) is a vector-valued function over time t∈𝕁.


## 5. Numerical Examples

In this section, some simulation results illustrate the performance of the proposed control laws to achieve formation and obstacles avoidance. To avoid triviality, the advantage of formation controllers (4) compared with others is omitted in this paper, and the reader is referred to [1].Firstly, drive4 agents with the initialization positions (-1.2,-1.1)⊺, (-2.0,3.8)⊺, (5.3,2.0)⊺, and (4.2,2.0)⊺ to form a shape of square and realize obstacle avoidance in the navigation. The formation-shape matrix Δq is set as
(37)Δ121=[22,22]⊺,Δ231=[22,-22]⊺,Δ341=[-22,-22]⊺,Δ411=[-22,22]⊺,Δ131=[2,0]⊺,Δ241=[0,-2]⊺,
and two obstacles locate at [2.50,5.00]⊺ and [-0.82,15.90]⊺. The target trajectory of f(t,x) in HMAS (1) is given by
(38)f(t,x)=[-0.1000.1]xi+[cos(0.4*t)sin(0.25*t)],
and the time-varying configuration matrix switches from one mode to another. They are as follows:
(39)J1=[-0.60.300.30.3-0.60.3000.3-0.60.30.300.3-0.6],J2=[-0.90.30.30.30.3-0.90.30.30.30.3-0.90.30.30.30.3-0.9].
For the formation controller (5), let Sa=8.1, La=0.31, Sr=0.69, LR=0.3, and δ=3, ρ=0.5 in obstacle-avoiding function (34).According to Figures2 and 3, one can demonstrate the control laws presented in this paper realize the formation keeping while avoiding collision with obstacles (marked by black stars in the figures) in complex environment. For the sake of measuring and visualising the formation effectiveness, we introduce the following formation error:
(40)e(t)=∑i=1N-1‍∑j>iN‍(∥xj(t)-xi(t)∥-∥Δijq∥),
which is shown in Figure 4. Then, the sensitivity of obstacle-avoiding function is investigated in Figure 5, which depicts the curves of left term in inequality (13) under different repulsion coefficient ρ and repulsion rang δ. From Figure 5, one can verify the fact that the performance index γ in inequality (13) reflects the sensitivity of HMAS towards obstacles; that is, smaller γ requires HMAS to be less active (smaller ρ and δ) towards obstacle.Figure 2
Formation of MAS without obstacle-avoidance functions case.Figure 3
Formation of MAS with obstacle-avoidance functions case.Figure 4
Formation error of MAS controlled by obstacle-avoidance functions.Figure 5
Investigation of parametersγ, ρ, and δ.Next, in an attempt to demonstrate the effectiveness of obstacle-avoidance function (36), a rectangular obstacle stands in the way of the HMAS path. Figures 6 and 7 show that the HMAS steers around the obstacle smoothly with the help of obstacle-avoidance functions and keeps a predefined formation in the whole process, as well as the corresponding formation error.Figure 6
Obstacle avoidance of MAS in 2D.Figure 7
Formation error for obstacle avoidance of MAS in 2D.In many practical situations, the HMAS occasionally encounters the trench-shape obstacles which are impossible for the whole system keeping original shape to pass through. In such case, the HMAS has to transform formation to a feasible one. In this example, the task is to transition from a square formation to a straight line to pass the trench safely. When the HMAS detects the trench existed in the tracking path, specified task is triggered and corresponding formation is determined according to the predetermined task-formation scheme. As shown in Figure8, the HMAS breaks formation, goes in a straight line when it meets the trench, and transforms back into the original formation after passing the trench.Figure 8
Formation change for HMAS in the presence of trench-shaped obstacle.


## 6. Conclusion

In this paper, new formation and obstacle-avoidance protocols of multiagent systems are presented. A notion ofH∞ formation has been first defined to characterize the performance of obstacle-avoiding, and the H∞ performance index is concreted as a sensitivity of obstacle-avoidance in this paper. Then a hybrid formation controller with a task set and a formation set is introduced to handle distinct obstacles. By designing diverse task-formation mapping, the HMAS can accomplish various complex missions. Then obstacle-avoidance functions using potential field model are specified to realize multiagent systems avoiding arbitrarily-shaped obstacles on the path. According to the simulation results, not only the HMAS can steer around the obstacles with proposed approach, but also the reconfiguration of formation can be achieved in the complex environment.



---

*Source: 123072-2013-10-28.xml*