Quantized flocking control for second-order multiple agents with obstacle avoidance

Abstract

A quantized flocking control for a group of second-order multiple agents with obstacle avoidance is proposed to address the problem of the exchange of information needed for quantification. With a reasonable assumption, a logarithmic or uniform quantizer is used for the exchange of relative position and velocity information between adjacent agents and the virtual leader, moving at a steady speed along a straight line, and a distributed flocking algorithm with obstacle avoidance capability is designed based on the quantitative information. The Lyapunov stability criterion of nonsmooth systems and the invariance principle are used to prove the stability of these systems. The simulations and experiments are presented to demonstrate the feasibility and effectiveness of the proposed approach.

Keywords

Multiple agents flocking control logarithmic quantizer uniform quantizer

Introduction

The flocking of a group of autonomous agents is currently a significant research subject in the field of multiple-robot cooperative control. Reynolds¹ introduced three heuristic rules to describe biological flocking: (1) separation: avoid collision with nearby group mates, (2) alignment: attempt to match velocity to that of nearby group mates, and (3) cohesion: attempt to stay close to nearby group mates.

Many variants based on these three rules have been proposed over the years. A Lyapunov-based approach was considered in Hong et al.² for switching the joint interconnection of an agent group. Graph theory was used to analyze the consensus problems of agents in Olfati-Saber and Murray.³ The theoretical framework for the design and analysis of distributed flocking algorithms was presented in Olfati-Saber⁴ by designing an artificial potential for $α$ lattice formation. However, all agents being informed and the virtual leader traveling at a constant velocity are based on the two critical assumptions in Olfati-Saber.⁴ Su et al.⁵ revisited the multi-agent flocking in the absence of the above two assumptions and showed that even when only a fraction of agents are informed, the flocking algorithm in Olfati-Saber⁴ enables not only all the informed agents to move with the desired constant velocity but also an uninformed agent to move with the same desired velocity if it can be influenced by the informed agents from time to time during the evolution. Furthermore, a novel individual-based alignment/repulsion algorithm for a stable and uncrowded flock that embodies many scenarios in not only bio-groups but also engineering applications was proposed in Zhang et al.⁶ Under this algorithm, each agent repels its sufficiently close neighbors, which are in repulsion neighborhoods, and aligns its velocity to the average velocity of its neighbors in alignment neighborhoods with moderate distances. Flocking control with obstacle avoidance and connectivity preservation has attracted an increasing number of interested researchers. Li et al.⁷ investigated the obstacle avoidance algorithm of multi-agent systems when only a subset of agents has obstacle dynamic information. In Li et al.,⁸ a novel geometry representation rule was proposed to transfer obstacles to a dense obstacle-agents lattice structure. Obstacles of arbitrary shape were allowed, regardless of whether their boundary was smooth or nonsmooth and whether they were convex or non-convex. In Su et al.,^9,10 the authors proposed a provably stable flocking algorithm based only on position information. Assuming that the initial network is connected, the flocking algorithms can preserve the connectivity of the network during the dynamical evolution.

Because agents are distributed and constrained by their limited sensing capabilities, they must rely on digital communication channels to obtain the needed information, and quantization is one of the basic limitations induced by finite bandwidth channels. This limitation has motivated an increasing interest in the use of quantized measurements to design effective coordination control strategies. In Dimarogonas and Johansson,¹¹ the spectral properties of the incidence matrix of the communication graph were exploited to study the convergence properties of a multi-agent network with quantized communication in continuous systems. For a team of mobile agents with second-order dynamics, a new set of tools, including new forms of the Lyapunov functions, was used to study how different quantizers affect the performances of consensus-type schemes to achieve synchronized collective motion.¹² In Ceragioli et al.,¹³ two quantization rules were considered: a uniform static quantizer and a hysteretic quantizer, which were designed to cope with the undesired chattering phenomena and study the convergence properties of the dynamics resulting from a hybrid system approach. In Chen et al.,¹⁴ the quantized consensus problem of continuous-time second-order multi-agent systems via sampled data was addressed, and a necessary and sufficient condition on the sampling period and design parameters was obtained.

However, the above research works did not investigate the flocking control of second-order multi-agent systems based on quantitative information. Specifically, obstacles were ignored, and thus, the obstacle avoidance feature was not addressed. There are two objectives in this article. The first objective is to extend the above research works to the flocking algorithm with the quantitative information regarding the relative position and velocity between neighboring agents. The second objective is to verify the flocking algorithm with obstacle avoidance when only a minority of the agents are informed regarding obstacle information. Through both mathematical analysis and numerical simulation, we show that a group of agents form a flock under exchange information quantized by a uniform or logarithmic quantizer condition. Furthermore, we apply these techniques to the problem of guaranteeing stable flocking of NAO humanoid robots whose model are used in the RoboCup 3D Simulated Soccer League.

Preliminaries and problem formulation

Filippov solutions

We consider the vector differential equation

\dot{x} = f (x, t), x_{0} = x (t_{0})

(1)

where $x \in R^{n}$ ; $f : R^{n} \times R \to R^{n}$ represents the vector field. Assuming that $f (x, t)$ is linear and bounded, that is, for all $x \in R^{n}$ and $t \in R$ , there exists a constant $γ > 0$ such that

‖ f (x, t) ‖ \leq γ ‖ x ‖ + c_{0}

(2)

then the Filippov solutions of equation (1) are as follows.

Definition 1

A vector function x is called a solution of equation (1) on $[t_{0}, t_{1}]$ if x is absolutely continuous on $[t_{0}, t_{1}]$ and for almost all $t \in [t_{0}, t_{1}]$ ¹⁵

\overset{\cdot}{x} = F [f] (x, t)

(3)

where

F [f] (x, t) = ⋂_{δ > 0} ⋂_{μ (N) = 0} \bar{c} o {f (B_{δ} (x) / N, t)}

(4)

and N is the set of x at which f is discontinuous; $B_{δ} (x)$ is the open ball of radius $δ$ centered at x; $⋂_{μ (N) = 0}$ denotes the intersection over all sets N of $Lebesgue$ measure 0; and $\bar{c} o$ denotes the convex closure.

Lemma 1

If $f_{1}, f_{2} : R^{n} \to R^{m}$ are locally bounded at $x_{0} \in R^{n}$ , then¹⁶

F [f_{1} + f_{2}] (x_{0}) \subseteq F [f_{1}] (x_{0}) + F [f_{2}] (x_{0})

Definition 2

The generalized directional derivative of f at x in the direction $ν \in D^{n}$ is defined by¹⁷

f^{o} (x; ν) = \underset{\underset{t ↓ 0}{y \to x}}{lim sup} \frac{f (y + t ν) - f (y)}{h}

(5)

if $f : R^{n} \to R$ is locally Lipschitz near any given point x, where $y \in R^{n}$ is a vector and t is a positive number.

Definition 3

If $f : R^{n} \to R$ is locally Lipschitz near x, then the generalized gradient of f at x is defined by¹⁷

\partial f (x) = {ζ \in R^{n} | f^{o} (x, ν) \geq 〈 ζ, ν 〉, \forall ν \in R^{n}}

(6)

Lemma 2

Let $x (\cdot)$ be a Filippov solution to function (1) on an interval containing $(t_{0}, t_{1})$ and $V : R^{n} \times R \to R$ be a Lipschitz and regular function.¹⁸ Then, $V (x, t)$ is absolutely continuous and $(d / dt) V (x, t)$ exists almost everywhere

\frac{d}{dt} V (x, t) \in^{a . e .} \overset{\cdot}{\tilde{V}} (x, t)

(7)

where

\overset{\cdot}{\tilde{V}} (x, t) = ⋂_{ζ \in \partial V (x (t), t)} ζ^{T} F [f] (x, t)

(8)

Lemma 3

Let $Ω$ be a compact set such that every Filippov solution to the autonomous system $\overset{\cdot}{x} = f (x)$ ; $x (t_{0}) = x_{0}$ starting in $Ω$ is unique and remains in $Ω$ for all $t \geq t_{0}$ .¹⁸ Let V be a time-independent regular function such that $ν \leq 0$ for all $ν \in \overset{\cdot}{\tilde{V}}$ (if $\overset{\cdot}{\tilde{V}} = \emptyset$ , then this is trivially satisfied). Define $S = {x \in Ω | 0 \in \overset{\cdot}{\tilde{V}}}$ . Then, every trajectory in $Ω$ converges to the largest invariant set, M, in the closure of S.

Problem formulation

We consider a team of $N > 0$ autonomous agents, with each agent governed by the following second-order dynamics

{\begin{matrix} {\overset{\cdot}{x}}_{i} = v_{i} \\ {\overset{\cdot}{v}}_{i} = u_{i}, i = 1, 2, \dots, N \end{matrix}

(9)

where $x_{i} \in R^{n}$ and $v_{i} \in R^{n}$ denote the position and velocity of agent i, respectively, and $u_{i} \in R^{n}$ is the ith agent’s control input. A virtual leader has the following model

{\begin{matrix} {\overset{\cdot}{x}}_{γ} = v_{γ} \\ {\overset{\cdot}{v}}_{γ} = 0 \end{matrix}

(10)

with $(x_{γ} (0), v_{γ} (0)) = (x_{0}, v_{d})$ . The information flow among agents is modeled as an undirected graph $G (t) = {V, E (t)}$ , where $V = {1, 2, \dots, N}$ is the set of vertices with i representing the ith agent and $E (t) = {(i, j)} \subset V \times V$ is the set of edges; the adjacency $A = [a_{ij}] \in R^{N \times N}$ is the $N \times N$ matrix given by $a_{ij} = 1$ , if $(i, j) \in E (t)$ , and $a_{ij} = 0$ otherwise. An edge denoted by the unordered pair $(i, j) \in E (t)$ represents a communication channel from i to j. A is a symmetric matrix.

Quantized flocking control with obstacle avoidance

In Zhang et al.,⁶ a general alignment repulsion algorithm for the flocking of multi-agent systems was proposed, and the controller $u_{i}$ was given by

\begin{matrix} u_{i} = - \sum_{j \in N_{1} (i)} a_{ij} (‖ x_{j} - x_{i} ‖) (\frac{x_{j} - x_{i}}{‖ x_{j} - x_{i} ‖}) \\ - \sum_{j \in N_{2} (i)} (v_{i} - v_{j}) \end{matrix}

(11)

where

a_{ij} (z) = {\begin{matrix} 1 - \frac{z}{r_{1}}, ς \leq z \leq r_{1} \\ 0, z > r_{1} \end{matrix}

and $ς$ is the diameter of an agent. For each individual agent, we define its two neighborhoods with radiuses $r_{1}$ and $r_{2}$ , called the repulsion and alignment neighborhoods, respectively. More precisely, the ith agent has two classes of neighbors

\begin{matrix} N_{1} (i) = {j | ‖ x_{j} - x_{i} ‖ < r_{1}, j \neq i, j = 1, 2, \dots, N} \\ N_{2} (i) = {j | ‖ x_{j} - x_{i} ‖ < r_{2}, j \neq i, j = 1, 2, \dots, N} \end{matrix}

where $r_{2} \geq r_{1} > ς$ .

In this article, we consider the scenario in which for each individual, the relative velocity and position information of its neighbors are acquired through digital communication. Thus, we have the control signals in the following form

\begin{matrix} u_{i} = - \sum_{j \in N_{1} (i)} a_{ij} (‖ q (x_{j} - x_{i}) ‖) \frac{q (x_{j} - x_{i})}{‖ q (x_{j} - x_{i}) ‖} \\ - \sum_{k \in N_{1} (i)} b_{ik} (‖ q (x_{k}^{o} - x_{i}) ‖) \frac{q (x_{k}^{o} - x_{i})}{‖ q (x_{k}^{o} - x_{i}) ‖} \\ - \sum_{j \in N_{2} (i)} q (v_{i} - v_{j}) - h_{i} q (x_{i} - x_{γ}) \end{matrix}

(12)

where $q (\cdot) : R^{n} \to R^{n}$ denotes the vector quantizer and

b_{ij} (z) = {\begin{matrix} 1 - \frac{z}{r_{1}}, \frac{(ς + R_{k}^{o})}{2 \leq z \leq r_{1}} \\ 0, z > r_{1} \end{matrix}

where $R_{k}^{o}$ is the diameter of obstacle k and $x_{k}^{o}$ denotes the position of obstacle k.

In this section, we assume that only some, not all, of the agents are informed agents who have the position information regarding the virtual leader. $h_{i} = 1$ if agent i is an informed agent and $h_{i} = 0$ otherwise.

We have assumed that all the individuals have been installed with identical quantizers. We consider the following two types of quantizers. The uniform quantizer we used is a map $q_{u} (\cdot) : R \to R$ such that

q_{u} (z) = ⌊ \frac{z}{δ_{u}} + \frac{1}{2} ⌋ δ_{u}

(13)

where $δ_{u}$ is a positive number and $⌊ x ⌋, x \in R$ denotes the greatest integer that is less than or equal to x.

The logarithmic quantizer we used is an odd map $q_{l} (\cdot) : R \to R$ such that

q_{l} (z) = {\begin{matrix} e^{q_{u} (\ln z)}, z > 0 \\ 0, z = 0 \\ - e^{q_{u} (\ln (- z))}, z < 0 \end{matrix}

(14)

For any $v = [v_{1}, v_{2}, \dots, v_{d}]^{T} \in R^{d}$ , we define the vector logarithmic quantizer $q_{l} (\cdot) : R^{d} \to R^{d}$ to be $q_{l} (v) \overset{Δ}{=} [q_{l} (v_{1}), q_{l} (v_{2}), \dots, q_{l} (v_{d})]^{T}$ and the vector uniform quantizer $q_{u} (\cdot) : R^{d} \to R^{d}$ to be $q_{u} (v) \overset{Δ}{=} [q_{u} (v_{1}), q_{u} (v_{2}), \dots, q_{u} (v_{d})]^{T}$ .

Denote the position difference vector and velocity difference vector between agent i and the virtual leader as ${\bar{x}}_{i} = x_{i} - x_{γ}$ and ${\bar{v}}_{i} = v_{i} - v_{γ}$ , respectively. We have

{\begin{matrix} {\overset{\cdot}{\bar{x}}}_{i} = {\bar{v}}_{i} \\ {\bar{v}}_{i} = u_{i}, i = 1, 2, \dots, N \end{matrix}

(15)

Let $x_{ij} = x_{i} - x_{j}$ and ${\bar{x}}_{ij} = {\bar{x}}_{i} - {\bar{x}}_{j}$ . Clearly

\begin{matrix} q ({\bar{x}}_{ij}) = q (x_{ij}) \\ q ({\bar{v}}_{ij}) = q (v_{ij}) \end{matrix}

Hence, the control protocol for agent i (12) can be rewritten as

\begin{matrix} u_{i} = - \sum_{j \in N_{1} (i)} a_{ij} (∥ q ({\bar{x}}_{ji}) ∥) \frac{q ({\bar{x}}_{ji})}{∥ q ({\bar{x}}_{ji}) ∥} \\ - \sum_{k \in N_{1} (i)} b_{ik} (∥ q ({\bar{x}}_{ki}^{o} ∥) \frac{q ({\bar{x}}_{ki}^{o})}{∥ q ({\bar{x}}_{ki}^{o}) ∥} \\ - \sum_{j \in N_{2} (i)} q ({\bar{v}}_{ij}) - h_{i} q ({\bar{x}}_{i}) \end{matrix}

(16)

To state the main results of this section, we define the potential and kinetic energies of the group as follows

Q (\bar{x}, \bar{v}) = V_{1} (\bar{x}) + V_{2} (\bar{x}) + V_{3} (\bar{x}) + K (\bar{v})

(17)

where $\bar{x} = [{\bar{x}}_{1}^{T}, {\bar{x}}_{2}^{T}, \dots, {\bar{x}}_{N}^{T}]^{T}$ , $\bar{v} = [{\bar{v}}_{1}^{T}, {\bar{v}}_{2}^{T}, \dots, {\bar{v}}_{N}^{T}]^{T}$

V_{1} (\bar{x}) = \frac{1}{2} \sum_{i = 1}^{N} \sum_{j \in N_{1} (i)} \int_{‖ q ({\bar{x}}_{ji}) ‖}^{r_{1}} a_{ij} (s) ds

V_{2} (\bar{x}) = \frac{1}{2} \sum_{i = 1}^{N} \sum_{k \in N_{1} (i)} \int_{‖ q ({\bar{x}}_{ki}^{o}) ‖}^{r_{1}} b_{ik} (s) ds

V_{3} (\bar{x}) = \sum_{i = 1}^{N} h_{i} \int_{0}^{{\bar{x}}_{i}} q (s) ds

K (\bar{v}) = \frac{1}{2} \sum_{i = 1}^{N} {\bar{v}}_{i}^{T} {\bar{v}}_{i}

When two agents i and j collide, that is, $‖ x_{ij} ‖ = ς$ , they generate a potential energy of

P_{ij} = \int_{ς}^{r_{1}} a_{ij} (s) ds

When agents i and obstacle k collide, that is, $‖ x_{k}^{o} - x_{i} ‖ = (ς + R_{k}^{o}) / 2$ . They generate a potential energy of

P_{ki} = \int_{(ς + R_{k}^{o}) / 2}^{r_{1}} b_{ik} (s) ds

Theorem 1

Consider a system of N mobile agents and a virtual leader with dynamics (9) and (10). Assume that $G (t)$ is a tree, the initial energy $Q (\bar{x} (0), \bar{v} (0))$ is finite and $Q (\bar{x} (0), \bar{v} (0)) < \max (P_{ij}, P_{ki}), \forall (i, j) \in E (t), \forall (i, k) \in E (t)$ . If the quantizers $q (\cdot) : R^{n} \to R^{n}$ are used in controller (12), then all agents will successfully trace the virtual leader with obstacle avoidance and no collisions will occur among multiple agents for all $t > 0$ . The following convergence properties are guaranteed:

In the case of logarithmic quantizers $q_{l} (\cdot) : R^{n} \to R^{n}$ in equation (14), the velocities of all the agents converge asymptotically to the velocity of the virtual leader (i.e. $v_{1} = v_{2} = \dots = v_{N} = v_{γ}$ ).

In the case of uniform quantizers $q_{u} (\cdot) : R^{n} \to R^{n}$ in equation (13), the velocities of all agents converge asymptotically to the set $I = {v ‖ | v_{i} - v_{γ} | < \sqrt{n} (δ_{u} / 2)}$ .

Proof

In view of Lemma 2, it follows that

\frac{d}{dt} Q (\bar{x}, \bar{v}) \in \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v}), for a . e . t . \geq 0

(18)

where

\begin{matrix} \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v}) = ⋂_{ξ \in \partial Q (\bar{x}, \bar{v})} ξ^{T} [{\overset{\cdot}{\bar{x}}}_{1}, {\overset{\cdot}{\bar{x}}}_{2}, \dots, {\overset{\cdot}{\bar{x}}}_{N}, F^{T} [{\overset{\cdot}{\bar{v}}}_{1}], \\ {F^{T} [{\overset{\cdot}{\bar{v}}}_{2}], \dots, F^{T} [{\overset{\cdot}{\bar{v}}}_{N}]]}^{T} \\ = ⋂_{ξ_{i} \in \frac{\partial Q (\bar{x}, \bar{v})}{\partial {\bar{x}}_{i}}} (\sum_{i}^{N} ξ_{i}^{T} {\bar{v}}_{i} + \sum_{i = 1}^{N} {\bar{v}}_{i}^{T} F [{\overset{\cdot}{\bar{v}}}_{i}]) \end{matrix}

(19)

Additionally

\frac{\partial Q (\bar{x}, \bar{v})}{\partial {\bar{x}}_{i}} = \frac{\partial V_{1} (\bar{x})}{\partial {\bar{x}}_{ji}} + \frac{\partial V_{2} (\bar{x})}{\partial {\bar{x}}_{ki}^{o}} + \frac{\partial V_{3} (\bar{x})}{\partial {\bar{x}}_{i}}

\frac{\partial Q (\bar{x}, \bar{v})}{\partial {\bar{v}}_{i}} = {\bar{v}}_{i}

Applying Lemma 1, one has

\begin{matrix} {\overset{\cdot}{\bar{v}}}_{i} \in F [u_{i}] \subseteq - \sum_{j \in N_{1} (i)} F [a_{ij} (‖ q ({\bar{x}}_{ji}) ‖) \frac{q ({\bar{x}}_{ji})}{‖ q ({\bar{x}}_{ji}) ‖}] \\ - \sum_{k \in N_{1} (i)} F [b_{ik} (‖ q ({\bar{x}}_{ki}^{o}) ‖) \frac{q ({\bar{x}}_{ki}^{o})}{‖ q ({\bar{x}}_{ki}^{o}) ‖}] \\ - \sum_{j \in N_{2} (i)} F [q ({\bar{v}}_{ij})] - h_{i} F [q ({\bar{x}}_{i})] \end{matrix}

Then, function (19) can be further computed as

\begin{matrix} \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v}) \subseteq ⋂_{ξ_{ij} \in \frac{\partial V_{1} (\bar{x})}{\partial {\bar{x}}_{ji}} ξ_{ki} \in \frac{\partial V_{2} (\bar{x})}{\partial {\bar{x}}_{ki}^{o}} {\hat{ξ}}_{i} \in \frac{\partial V_{3} (\bar{x})}{\partial {\bar{x}}_{i}}} \\ (\sum_{i = 1}^{N} (\sum_{j \in N_{1} (i)} ξ_{ij}^{T} + \sum_{k \in N_{1} (i)} ξ_{ki}^{T} + {\hat{ξ}}_{i}^{T}) {\bar{v}}_{i} \\ - \sum_{i = 1}^{N} \sum_{j \in N_{1} (i)} {\bar{v}}_{i}^{T} F [a_{ij} (‖ q ({\bar{x}}_{ji}) ‖) \cdot (\frac{q ({\bar{x}}_{ji})}{‖ q ({\bar{x}}_{ji}) ‖})] \\ - \sum_{i = 1}^{N} \sum_{j \in N_{2} (i)} {\bar{v}}_{i}^{T} F [q ({\bar{v}}_{ij})] \\ - \sum_{i = 1}^{N} \sum_{k \in N_{1} (i)} {\bar{v}}_{i}^{T} F [b_{ik} (‖ q ({\bar{x}}_{ki}^{o}) ‖) \cdot \frac{q ({\bar{x}}_{ki}^{o})}{∥ q ({\bar{x}}_{ki}^{o}) ∥}] \\ - \sum_{i = 1}^{N} h_{i} {\bar{v}}_{i}^{T} F [q ({\bar{x}}_{i})]) \\ = ⋂_{ξ_{ij} \in \frac{\partial V_{1} (\bar{x})}{\partial {\bar{x}}_{ji}}} \sum_{i = 1}^{N} \sum_{j \in N_{1} (i)} (ξ_{ij}^{T} {\bar{v}}_{i} - {\bar{v}}_{i}^{T} F [a_{ij} (‖ q ({\bar{x}}_{ij}) ‖) \frac{q ({\bar{x}}_{ij})}{‖ q ({\bar{x}}_{ij}) ‖}]) \\ + ⋂_{ξ_{ki} \in \frac{\partial V_{2} (\bar{x})}{\partial {\bar{x}}_{ki}^{o}}} \sum_{i = 1}^{N} \sum_{k \in N_{1} (i)} (ξ_{ki}^{T} {\bar{v}}_{i} - {\bar{v}}_{i}^{T} F [b_{ik} (‖ q ({\bar{x}}_{ki}^{o}) ‖) \frac{q ({\bar{x}}_{ki}^{o})}{‖ q ({\bar{x}}_{ki}^{o}) ‖}]) \\ + ⋂_{{\hat{ξ}}_{i} \in \frac{\partial V_{3} (\bar{x})}{\partial {\bar{x}}_{i}}} (\sum_{i = 1}^{N} ({\hat{ξ}}_{i}^{T} {\bar{v}}_{i} - h_{i} {\bar{v}}_{i}^{T} F [q ({\bar{x}}_{i})])) \\ - \sum_{i = 1}^{N} \sum_{j \in N_{2} (i)} {\bar{v}}_{i}^{T} F [q ({\bar{v}}_{ij})] \end{matrix}

(20)

From Definition 1, we can further deduce that

\begin{matrix} \frac{d}{dt} Q (\bar{x}, \bar{v}) \in \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v}) \\ \subseteq - \sum_{i = 1}^{N} \sum_{j \in N_{2} (i)} {\bar{v}}_{i}^{T} F [q ({\bar{v}}_{i} - {\bar{v}}_{j})] \\ = - \frac{1}{2} \sum_{i = 1}^{N} \sum_{j \in N_{2} (i)} ({\bar{v}}_{i} - {\bar{v}}_{j})^{T} F [q ({\bar{v}}_{i} - {\bar{v}}_{j})] \end{matrix}

This implies that

\frac{d}{dt} Q (\bar{x}, \bar{v}) \leq 0

(21)

From function (17), one has

\begin{matrix} \int_{‖ q ({\bar{x}}_{ji}) ‖}^{r_{1}} a_{ij} (s) ds \leq Q (\bar{x} (t), \bar{v} (t)) \\ \leq Q (\bar{x} (0), \bar{v} (0)) \\ < P_{ij} \\ = \int_{\bar{x} (t), \bar{v} (t)}^{\bar{x} (t), \bar{v} (t)} a_{ij} (s) ds, \forall t \in [0, \infty) \end{matrix}

that is, $‖ q ({\bar{x}}_{ji}) ‖ = ‖ q (x_{j} - x_{i}) ‖ > ς$ ; this implies that no collisions occur among multiple agents.

Furthermore, from function (17), we have

\begin{matrix} \int_{‖ q ({\bar{x}}_{ki}^{o}) ‖}^{r_{1}} b_{ik} (s) ds \leq Q (\bar{x} (t), \bar{v} (t)) \\ \leq Q (\bar{x} (0), \bar{v} (0)) \\ < P_{ki} \\ = \int_{(ς + R_{k}^{o}) / 2}^{r_{1}} b_{ik} (s) ds, \forall t \in [0, \infty) \end{matrix}

Then, one has $‖ q ({\bar{x}}_{ki}^{o}) ‖ = ‖ q (x_{k}^{o} - x_{i}) ‖ > (ς + R_{k}^{o}) / 2$ . This implies that multiple agents have obstacle avoidance capabilities.

From equations (17) and (21), it is clear that

{\bar{v}}_{i}^{T} {\bar{v}}_{i} \leq 2 Q (\bar{x} (0), \bar{v} (0))

hence, $‖ {\bar{v}}_{i} ‖ \leq \sqrt{2 Q (\bar{x} (0), \bar{v} (0))}$ . This implies that the velocity difference vector between agent i and the virtual leader is limited. For the connectivity of $G (t)$ , there exists $R > 0$ such that $‖ \bar{x} (t) ‖ \leq R$ , $\forall t \geq 0$ . Hence

Ω = {(\bar{x}, \bar{v}) | Q (\bar{x}, \bar{v}) \leq Q (\bar{x} (0), \bar{v} (0))}

(22)

is a compact set. Then, it follows from Lemma 3 that all trajectories of the agents that start from $Ω$ will converge to the largest invariant set

M = {(\bar{x}, \bar{v}) \in Ω | \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v}) = 0}

(23)

in the closure of

S = {(\bar{x}, \bar{v}) \in Ω | 0 \in \overset{\cdot}{\tilde{Q}} (\bar{x}, \bar{v})}

(24)

When the logarithmic quantizers (14) are used, it follows that ${\bar{v}}_{1} = {\bar{v}}_{2} = \dots {\bar{v}}_{N} = 0$ , that is, $v_{1} = v_{2} = \dots v_{N} = v_{γ}$ , indicating that the velocities of all the agents converge asymptotically to the velocity of the virtual leader.

When the logarithmic quantizers (13) are used, from ${\bar{v}}_{i} - {\bar{v}}_{j} \in [- (δ_{u} / 2), (δ_{u} / 2)] 1_{n}$ , one has $‖ {\bar{v}}_{i} - {\bar{v}}_{j} ‖_{2} \leq \sqrt{n} ‖ {\bar{v}}_{i} - {\bar{v}}_{j} ‖_{\infty} \leq (\sqrt{n} / 2) δ_{u}$ , that is, the velocities of all agents converge asymptotically to the set $I = {v ‖ | v_{i} - v_{γ} | < \sqrt{n} (δ_{u} / 2)}$ .

Simulation and experimental results

A simulation on six agents moving in a two-dimensional space was performed in MATLAB. The logarithmic quantizers $q_{l} (\cdot) : R^{n} \to R^{n}$ in equation (14) and uniform quantizers $q_{u} (\cdot) : R^{n} \to R^{n}$ in equation (13) were used in the controller (12), respectively, $(δ_{u} = 0.05)$ .

The initial velocities and positions of the six agents were chosen randomly from the boxes $[0, 10] \times [50, 60]$ and $[0, 1] \times [0, 1]$ , respectively. The initial velocity and position of the virtual leader were set at $v_{γ} (0) = [9, 59]^{T}$ and $x_{γ} (0) = [4, - 1]^{T}$ , respectively. The repulsion and alignment radius were chosen as $r_{1} = 4$ and $r_{2} = 6$ , respectively.

Some simulation results are shown in Figures 1 and 2. In the figure, there are six agents marked with circles; the solid lines represent the neighboring relations, the solid lines with arrows represent the velocities, and the star represents the virtual leader. The positions and radius of the obstacle are $[33, 80]$ and $10$ , respectively. Figure 1 illustrates that the initial velocities of the agents differ considerably. As time progresses, Figure 2 shows that all agents move with the same velocity as desired. Figure 2 also illustrates that the agents avoid collision with obstacles as they move forward.

Figure 1.

Initial state of multi-agent systems.

Figure 2.

Trajectories of the multi-agent systems applying control input (12) with obstacle avoidance.

The NAO humanoid robot was produced by Aldebaran Robotics and has 25 degrees of freedom, a height of approximately 0.57 m, and a weight of approximately 4.5 kg. The robot model used in the RoboCup 3D Simulated Soccer League is currently NAO. The CIT3D team, which was built by our laboratory, has taken part in several RoboCup 3D soccer simulation competitions and won world runner-up of the RoboCup (once), third place of RoboCup IranOpen (once), runner-up (twice), and second runner-up (four times) in the RoboCup ChinaOpen. The walking pattern generation of the CIT3D team was based on the three-dimensional (3D) linear inverted pendulum model (LIPM)^19,20 and preview control.^21–23 Stable bipedal walking has been successfully realized in the CIT3D team.

Based on the source code of the CIT3D team, an experiment of humanoid robot flocking behavior with obstacle avoidance was performed in the RoboCup 3D soccer simulation environment. The dimensions of the soccer field are 30 × 20 m, as shown in Figure 3.

Figure 3.

Dimensions and coordinate system of the soccer field.

Eleven blue NAO robots were placed randomly on the left side of the soccer field, while initial velocities of there robots were set to $[0, 0]$ , and 11 red NAO robots were placed as fixed obstacles on the right side of the soccer field, as shown in Figure 4. The initial velocity and position of the virtual leader were set at $v_{γ} (0) = [0.4, 0]^{T}$ and $x_{γ} (0) = [- 10, 0]^{T}$ , respectively. The repulsion and alignment radius were chosen as $r_{1} = 2$ and $r_{2} = 6$ , respectively.

Figure 4.

Snapshot of initial state of the experiment of humanoid robot flocking behavior with obstacle avoidance.

Figure 5 shows that the flocking of these 11 blue NAO robots was achieved by applying control input (12). Figures 6 and 7 show that these 11 blue NAO robots walked through these two obstacles based on flocking behavior with obstacle avoidance. Figure 8 shows that after avoiding obstacles, the team of 11 blue NAO robots reached the destination. The formation of these 11 blue NAO robots was again achieved.

Figure 5.

Snapshot at 17.4 s.

Figure 6.

Snapshot at 39.4 s.

Figure 7.

Snapshot at 57.4 s.

Figure 8.

Snapshot at 82.6 s.

Conclusion

In this article, the flocking control with obstacle avoidance problem has been considered for second-order agents under quantized communication. A distributed protocol has been proposed based on the exchange of the quantitative relative position and velocity between neighboring agents. It was shown that for an initial connected network, with the proposed distributed protocol, flocking with obstacles avoidance was achieved using quantitative information exchange between each pair of adjacent agents at each time step.

Footnotes

Academic Editor: Long Cheng

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Reynolds

CW.

Flocks, herds and schools: a distributed behavioral model. In: Proceedings of the ACM SIGGRAPH computer graphics, Anaheim, CA, 27–31 July 1987, vol. 21, pp.25–34. New York: ACM.

Hong

Gao

Cheng

. Lyapunov-based approach to multiagent systems with switching jointly connected interconnection. IEEE T Automat Contr 2007; 52: 943–948.

Olfati-Saber

Murray

RM.

Consensus problems in networks of agents with switching topology and time-delays. IEEE T Automat Contr 2004; 49: 1520–1533.

Olfati-Saber

Flocking for multi-agent dynamic systems: algorithms and theory. IEEE T Automat Contr 2006; 51: 401–420.

Wang

Lin

Flocking of multi-agents with a virtual leader. IEEE T Automat Contr 2009; 54: 293–307.

Zhang

Zhai

Chen

A general alignment repulsion algorithm for flocking of multi-agent systems. IEEE T Automat Contr 2011; 56: 430–435.

Zhang

. Coordinated obstacle avoidance with reduced interaction. Neurocomputing 2014; 139: 233–245.

Zhang

. Flocking of partially-informed multi-agent systems avoiding obstacles with arbitrary shape. Auton Agent Multi-Ag 2015; 29: 943–972.

Wang

Chen

A connectivity-preserving flocking algorithm for multi-agent systems based only on position measurements. Int J Control 2009; 82: 1334–1343.

10.

Zhang

Chen

MZQ

. Adaptive flocking with a virtual leader of multiple agents governed by locally Lipschitz nonlinearity. Nonlinear Anal: Real 2013; 14: 798–806.

11.

Dimarogonas

Johansson

KH.

Stability analysis for multi-agent systems using the incidence matrix: quantized communication and formation control. Automatica 2010; 46: 695–700.

12.

Liu

Cao

De Persis

Quantization effects on synchronized motion of teams of mobile agents with second-order dynamics. Syst Control Lett 2012; 61: 1157–1167.

13.

Ceragioli

De Persis

Frasca

Discontinuities and hysteresis in quantized average consensus. Automatica 2011; 47: 1916–1928.

14.

Chen

Jiao

LC.

Quantized consensus of second-order continuous-time multi-agent systems with a directed topology via sampled data. Automatica 2013; 49: 2236–2242.

15.

Filippov

AF.

Differential equations with discontinuous right-hand side. Am Math Soc Trans 1964; 42: 199–231.

16.

Cortes

Discontinuous dynamical systems. IEEE Contr Syst Mag 2008; 28: 36–73.

17.

Clarke

FH.

Optimization and nonsmooth analysis. New York: Wiley, 1983, pp.45–46.

18.

Shevitz

Paden

Lyapunov stability theory of nonsmooth systems. IEEE T Automat Contr 1994; 39: 1910–1914.

19.

Kajita

Matsumoto

Saigo

. Real-time 3D walking pattern generation for a biped robot with telescopic legs. In: Proceedings of the IEEE international conference on robotics and automation, Seoul, South Korea, 21–26 May 2001, pp.2299–2306. New York: IEEE.

20.

Kajita

Kanehiro

Kaneko

. A realtime pattern generator for biped walking. In: Proceedings of the IEEE international conference on robotics and automation, Washington, DC, 11–15 May 2002, pp.31–37. New York: IEEE.

21.

Kajita

Kanehiro

Kaneko

. Biped walking pattern generation by using preview control of zero-moment point. In: Proceedings ICRA’03 IEEE international conference on robotics and automation, Taipei, Taiwan, 14–19 September 2003, pp.1620–1626. New York: IEEE.

22.

Shimmyo

Sato

Ohnishi

Biped walking pattern generation by using preview control with virtual plane method. In: Proceedings of the 2010 11th IEEE international workshop on advanced motion control, Nagaoka, Japan, 21–24 March 2010, pp.414–419. New York: IEEE.

23.

Strom

Slavov

Chown

. Omnidirectional walking using ZMP and preview control for the NAO humanoid robot. In: Baltes

Lagoudakis

Naruse

. (eds) RoboCup 2009: robot soccer world cup XIII. Berlin; Heidelberg: Springer, 2010, pp.378–389.