Broadcast control of multi-robot systems with norm-limited update vector

Abstract

This article addresses a problem in standard broadcast control framework which leads to an unstable solution in a certain motion-coordination task. First, the unstable phenomenon in a certain motion-coordination task is illustrated using standard broadcast control framework. This issue calls for modification to the standard broadcast control framework by limiting the norm of the update vector of robots’ positions into a constant value. Then, we demonstrate that the modified broadcast controller achieves the convergence with the probability of 1. Finally, we illustrate in numerical simulations that the modified broadcast controller can effectively solve the instability issue and also may improve the convergence time as compared to the standard broadcast controller.

Keywords

Multi-robot systems broadcast control instability simultaneous perturbation stochastic approximation (SPSA)norm-limited update vector

Introduction

Nowadays, multi-robot systems are of a great interest among researchers, compared to individual systems. This is because multi-robot systems can effectively carry out more tasks. Previously, many researchers were focusing on robot-to-robot communication framework to solve various multi-robot coordination problems. Instead of using robot-to-robot communication framework, some researchers explored a new idea to solve multi-robot coordination problems by considering one-to-all communication framework or better known as broadcast control framework. The example is illustrated in Figure 1. This one-to-all communication framework means that the same signal is sent indiscriminatingly to all robots. The consideration of this broadcast framework has been motivated by its advantages, such as practical motion-coordination task for large-scale multi-robot systems such as swarm robot that does not need robots’ identification, and consuming minimal energy during execution task execution. Readers may refer to Ismail and Sariff¹ for more examples of multi-robot applications.

Figure 1.

One-to-all robot communication framework for multi-robot systems.

The idea of broadcast control framework was originally inspired by Ueda et al.,² where such framework had been used to control a bio-inspired actuator system of many cellular units. A number of results regarding the broadcast control frameworks have been obtained.^3
–5 Aside from biological system, the idea of broadcast control was also implemented in controlling a group of multi-agent systems^{6

–14} and recently, to control connected and automated vehicles at merging highway,^15,16 unmanned aerial vehicles,¹⁷ as well as radar surveillance system.¹⁸ In particular, a standard broadcast control framework was synthesized in Azuma and Sugie⁸ to solve certain motion-coordination task for multi-agent systems, such as coverage problem. This work was supported in detailed proof by Azuma et al.⁹ The interesting problem encountered in the standard broadcast control framework is in determining methodology to perform any motion-coordination task by sending the same signal to each agent indiscriminatingly. Here, they came out with a novel solution by designing global and local controllers as a feedback system. These global and local controllers’ functions were, respectively, to generate commands to the agents by calculating the cost function and move the agents randomly and deterministically. Several solutions to the problem in the standard broadcast control framework were obtained. In their study, Tanaka et al.¹² focused on designing time-varying gain embedded in the local controllers for fast convergence. This work will also enable us to easily tune the gain. As a digital camera is commonly used as global controller’s sensor, Tanaka et al.¹³ had modified the standard broadcast control framework to cancel out the quantize effect caused by digital camera. Besides that, Tanaka et al.¹⁴ had proposed to combine the standard broadcast framework with one-to-one agent communication known as mix environment. This combination aims to overcome the limited communication range and to reduce convergence time. However, their results were validated for coverage^8,13 and consensus tasks only,^12
–14 and it was unsure whether the standard broadcast control framework can work for other motion-coordination tasks. In this study, we have simulated the standard broadcast control framework with some other motion-coordination tasks and identified that it only works for certain multi-robot coordination tasks. This is because in some coordination tasks, the broadcast control framework often encounters instability phenomenon. In this article, the instability phenomenon means that the robots are moving away from their preassigned target positions and never converged to the target positions due to unacceptable broadcasting input signal. For example, a group of robots (each employing the standard broadcast controller) are tasked to go to some target positions which are highly contaminated. Due to the instability phenomenon, these robots will move away from the target positions and probably will go to the place where the condition is unsuitable for the robots and might cause a serious damage to them. From this example, it is obvious that the instability phenomenon is important to be addressed and solved.

To illustrate the cause of the instability issue, consider a standard broadcast control system as shown in Figure 2, which comprises robots, local controllers, and a global controller. In the standard broadcast control framework,^8,9 the position of the robot is maneuvered by the local controller that connotes the random and the deterministic input, alternately. In particular, for iteration $k = 1, 2, ...,$ the input is a random vector when k is even. When k is odd, it is a vector comprising prespecified parameters, as shown in Figure 3. Note that the random vector is generated by the local controller itself, while the prespecified vector is uniquely determined from the output sequence of the global controller, corresponding to the assigned motion-coordination task. This way the robot is expected to achieve the given motion-coordination task as $k \to \infty$ . However, in some coordination tasks, that is, role-assignment task (the coordination task is represented as a cost function and we denote it as $J (x)$ in this article), there is a possibility that the deterministic input becomes too large to execute and numerically diverges as $k \to \infty$ . As a result, the local controller steers the robot in an unstable manner and cannot achieve the given motion-coordination task. The detailed numerical example of this instability problem will be shown in the second section.

Figure 2.

Standard broadcast control framework.

Figure 3.

Motion of robots by standard broadcast control framework.

In this article, we solved the instability problem by modifying the standard broadcast control framework which consisted of global and local controllers. In our modified broadcast control framework, a new local controller is derived so that it can limit the amount of the deterministic input in updating the robots’ position. Note that the derivation is based on simultaneous perturbation stochastic approximation (SPSA) with norm-limited update vector algorithm adopted from Tanaka et al.¹⁹ The algorithm was adopted because of the practicality in solving various model-free optimization problems.^19
–21 From this fact, we believe that the same idea can be applied to solve the instability problem in the standard broadcast control framework. On the other hand, we proved that the modified broadcast controller asymptotically had achieved the task with a probability of 1. Besides that, the numerical simulation also showed that the modified broadcast control can effectively handle the given task. In addition, it is expected that our proposed broadcast control framework may also reduce the convergence time in performing the motion-coordination tasks.

Our contributions are summarized as follows:

Modified an existing broadcast control framework (referred as standard broadcast control framework) based on SPSA with norm-limited update vector algorithm to overcome the instability problem of the existing broadcast control framework in solving some of the motion-coordination tasks (e.g. role-assignment tasks). By solving the instability problem, we believe that a large class of motion-coordination tasks can be catered by the broadcast control framework such as containment,²² flocking,²³ and formation²⁴ control.

Proved that the modified broadcast controller can achieve the motion-coordination task with a probability of 1.

Generated simulation results showing our modified broadcast controller also may have faster convergence time as compared to the standard broadcast controller while being competitive with another existing broadcast control framework.

Notation: Let ℝ, $ℝ_{+}$ , ℤ, and $ℤ_{0 +}$ be the set of real numbers, set of positive real numbers, set of integers, and set of nonnegative integers, respectively. For the vector x, $| | x | |$ is defined as the Euclidean norm. When other kind of norm is used, then the norm is denoted as $| | x {| |}_{p}$ for the p-norm. Next, we use $x^{- 1}$ to denote a non-zero value or elementwise inverse of the element. For the differentiable function $J : ℝ^{n} \to ℝ$ , that is, $[\partial J^{(j)} (x) / \partial x_{1}^{(j)} \partial J^{(j)} (x) / \partial x_{2}^{(j)} \dots \partial J^{(j)} (x) / \partial x_{N}^{(j)}] \in ℝ^{n}$ , it is expressed by $\nabla J^{(j)} (x)$ for $j = 1, 2, ..., N$ and $\dot{z} (k)$ is denoted as the differential equation of $d z (k) / d k$ . On the other hand, we denote $γ : ℝ^{n} \to ℝ^{n}$ as a saturation function, that is, $γ (θ) : = {[sign (θ_{1}) min (| θ_{1} |, e) sign (θ_{2}) min (| θ_{2} |, e) \dots sign (θ_{n}) min (| θ_{n} |, e)]}^{T}$ where $sign (θ_{n})$ is the signum function of the element $θ_{i} \in ℝ$ . Here, $θ_{i}$ is the ith element of $θ \in ℝ^{n}$ and $min (| θ_{n} |, e)$ is the minimum value between $| θ_{n} |$ and positive integer $e \in ℝ_{+}$ . The Kronecker product of matrix A and B is denoted as $A \otimes B$ . Finally, we denote $Pr (a)$ and $E (b)$ as the probability and expectation of event a and random variable b.

Broadcast control framework

This section briefly explains the standard broadcast control framework. Then, an example of unstable solution using the standard broadcast control is illustrated.

Standard broadcast control framework

Based on standard broadcast control system P in Figure 2, the state of the robot (e.g. discrete time model of an omnidirectional mobile robot) $S_{i} (i = 1, 2, \dots, N)$ is given by

S_{i} : x_{i} (k + 1) = x_{i} (k) + u_{i} (k)

where $k \in ℤ_{0 +}$ is the iteration, $x_{i} (k) \in ℝ^{n}$ is the n-dimensional space position of the robot, and $u_{i} (k) \in ℝ^{n}$ is the input of the robot. The collective position of the robots $x (k) \in ℝ^{n N}$ and the initial position $x (0) \in ℝ^{n N}$ are denoted as $x (k) : = {[\begin{matrix} x_{1} {(k)}^{T} & x_{2} {(k)}^{T} & \dots & x_{N} {(k)}^{T} \end{matrix}]}^{T}$ and $x (0) : = {[\begin{matrix} x_{1} {(0)}^{T} & x_{2} {(0)}^{T} & \dots & x_{N} {(0)}^{T} \end{matrix}]}^{T}$ , respectively.

The local controllers $L_{i} (1, 2, \dots, N)$ embedded in each of the following robots are described as

L_{i} : \{\begin{matrix} ξ_{i} (k + 1) = ϕ (k, ξ_{i} (k), y (k)) \\ u_{i} (k) = ψ (k, ξ_{i} (k), y (k)) \end{matrix}

where $ξ_{i} (i = 1, 2, \dots, N) \in ℝ^{2 n + 1}$ are the temporary memorizing variables, $y (k) \in ℝ$ and $u_{i} (k) \in ℝ^{n}$ are, respectively, the input and output of the local controller, and $ϕ : ℤ_{0 +} \times ℝ^{2 n + 1} \times ℝ \to ℝ^{2 n + 1}$ and $ψ : ℤ_{0 +} \times ℝ^{2 n + 1} \times ℝ \to ℝ^{n}$ are functions given by

ϕ (k, ξ_{i} (k), y (k)) : = \{\begin{matrix} [\begin{matrix} β_{i} (k) \\ c (k) β_{i} (k) \\ y (k) \end{matrix}] & if k is even \\ ξ_{i} (k) & if k is odd \end{matrix}

ψ (k, ξ_{i} (k), y (k)) : = \{\begin{matrix} c (k) β_{i} (k) & if k is even \\ - ξ_{i 2} (k) - a (k) (\frac{Δ J}{c (k)} ξ_{i 1}^{(- 1)} (k)) & if k is odd \end{matrix}

where $β_{i} (k) \in ℝ^{n}$ is a Bernoulli distributed random vector, $c (k)$ and $a (k)$ are gains sequence, the components of $ξ_{i} (k)$ are $ξ_{i 1} (k) \in ℝ^{n}$ , $ξ_{i 2} (k) \in ℝ^{n}$ , $ξ_{i 3} (k) \in ℝ$ , that is

ξ_{i} (k) = [\begin{matrix} ξ_{i 1} (k) \\ ξ_{i 2} (k) \\ ξ_{i 3} (k) \end{matrix}]

and $Δ J = y (k) - ξ_{i 3} (k) = J (x (k) + c (k) β_{i} (k)) - J (x (k))$ .

The global controller G is given by

G : y (k) = f (J (x (k)))

where $J (x (k)) \in ℝ_{0 +}$ and $y (k) \in ℝ$ are the input and output of the global controller, respectively, and $J : ℝ^{n N} \to 0 \cup ℝ_{+}$ and $f : ℝ_{0 +} \to ℝ$ are functions. Note that the function f is introduced so that we have sufficient flexibility in designing the broadcast controller. On the other hand, function J is an objective function that corresponds to the given motion-coordination task. Then, we can indicate that this standard broadcast control achieves the given motion-coordination task if

lim_{k \to \infty} J (x (k)) = min_{x \in ℝ^{n N}} J (x)

for every initial positions of the robots $x (0) \in ℝ^{n N}$ .

Unstable solution using standard broadcast control framework

In demonstrating the instable phenomenon in the standard broadcast control framework, we chose role-assignment task^9,25 given by

J (x) = \sum_{i = 1}^{N} \prod_{j = 1}^{N} ∥ x_{i} - p_{j} ∥ + λ {(\prod_{i = 1}^{N - 1} \prod_{j = i + 1}^{N} ∥ x_{i} - p_{j} ∥)}^{- 1}

where $p_{j} (j = 1, 2, \dots, N) \in ℝ^{n}$ is the target position and $λ \in ℝ$ is an approximate accuracy. Note that the overlapping function at the right-hand side of equation (6), that is, $λ {(\prod_{i = 1}^{N - 1} \prod_{j = i + 1}^{N} ∥ x_{i} - p_{j} ∥)}^{- 1}$ , is added so that the robots do not converge to the same place. The parameters of the standard broadcast controller (equations (1) to (5)) are tabulated in Table 1. Note that the design of gains $a (k)$ and $c (k)$ in Table 1 follows the similar way as in Azuma et al.⁹ and the detailed explanation on how we choose the parameters of these two gains will be described in the fourth section. From Figure 4, it can be seen that the evolution of the role-assignment task diverges from $x^{*}$ where $x^{*}$ is the optimal solution. Recall that this divergence or instability phenomenon occurred due to the deterministic input in the second condition of equation (4), where it becomes too large to execute as $k \to \infty$ .

Table 1.

Parameters of standard broadcast control.

Parameter	Value
n	2
N	6
$x (0)$	${[\begin{matrix} 90 & 60 & 80 & 80 & 60 & 90 \\ 40 & 90 & 20 & 80 & 10 & 60 \end{matrix}]}^{T}$
p_j	${[\begin{matrix} 50 & 80 & 40 & 60 & 60 & 60 \\ 30 & 40 & 50 & 40 & 70 & 40 \end{matrix}]}^{T}$
$β_{i j} (k) (i = 1, 2, \dots, N)$ $(j = 1, 2, \dots, n)$	$\{\begin{cases} Pr (β_{i j} (k) = 1) = 0.5 \\ Pr (β_{i j} (k) = - 1) = 0.5 \end{cases}$
$a (k)$	${\begin{cases} \frac{a_{0}}{{(\frac{k}{2} + 1 + a_{v})}^{a_{p}}} if k is even \\ a (k - 1) if k is odd \end{cases}$ $a_{0} = 2.1, a_{v} = 150, a_{p} = 1.55$
$c (k)$	$\begin{array}{l} \{\begin{cases} \frac{c_{0}}{{(\frac{k}{2} + 1)}^{c_{p}}} if k is even \\ c (k - 1) if k is odd \end{cases} \end{array}$ $c_{0} = 6, c_{p} = 0.86$
λ	$1 \times 10^{30}$

Figure 4.

Evolution of the cost function for role-assignment task using standard broadcast control framework.

This example proved that the standard broadcast control framework does not always resolve the motion-coordination task issue. Hence, it encouraged us to adopt a modified version of broadcast control framework.

Modified broadcast controller

In order to solve the instability phenomenon above, we propose a modified broadcast controller. In particular, the function ψ in the local controller is modified as

ψ (k, ξ_{i} (k), y (k)) : = \{\begin{matrix} c (k) β_{i} (k) & if k is even \\ - ξ_{i 2} (k) - γ (d (k, ξ_{i} (k), y (k))) & if k is odd \end{matrix}

where $γ : ℝ^{n} \to ℝ^{n}$ is a saturation function and the update vector $d (k, ξ_{i} (k), y (k))$ is described as

d (k, ξ_{i} (k), y (k)) = a (k) (\frac{Δ J}{c (k)} ξ_{i 1}^{- 1} (k))

Meanwhile, the function and the global controller are set similar to the standard broadcast controller in equations (3) and (5), respectively. Next, the convergence result of our proposed modified broadcast controller in equations (1), (3), (5), and (7) is shown.

Theorem 1

For the modified broadcast control system P, suppose that $(L_{1}, L_{2}, \dots, L_{N}, G)$ are given by equations (3), (5), and (7). Should the saturation function γ and objective function J are given, then

lim_{k \to \infty} x (k) = x^{*}

where $x^{*} \in ℝ^{n}$ is the solution to $x (k)$ subject to the following conditions:

C1: For almost of $x (k)$ (at each $k \geq K$ for some $K < \infty$ ) and some $ω_{0}$ , J is assumed to have twice continuously differentiable, $\nabla J^{(2)} (x)$ bounded by $ω_{0}$ for all x.

C2: $∥ x (k) ∥ < \infty$ for all $k \in ℤ_{0 +}$ .

C3: $x^{*}$ is an asymptotically stable solution of the differential equation $\dot{z} (k) = - \nabla J (z (k))$ where $z (k) \in ℝ^{n N}$ and the stability is in the Lyapunov sense.

C4: $a (k) = a (k + 1) > 0$ , $c (k) = c (k + 1) > 0$ for all $k \in {0, 2, 4, \dots}$ , ${lim}_{k \to \infty} a (k) = 0$ , $\sum_{k = 0}^{\infty} a (k) = \infty$ , ${lim}_{k \to \infty} c (k) = 0$ , $\sum_{k = 0}^{\infty} c (k) = \infty$ , and $\sum_{k = 0}^{\infty} {(a (k) / c (k))}^{2} < \infty$ .

C5: $β_{i j} (k) (i = 1, 2, \dots, N) (j = 1, 2, \dots, n)$ are i.i.d. random numbers drawn from the Bernoulli distribution with outcome $\pm 1$ and have equal probabilities given by

\{\begin{cases} Pr (β_{i j} (k) = 1) = 0.5 \\ Pr (β_{i j} (k) = - 1) = 0.5 \end{cases}

where $β_{i j} (k)$ is the Jth element of $β_{i j} (k)$ . Note that the $β_{i j} (k)$ is independent from $x (k) (k = 0, 1, 2, \dots)$ and symmetrically distributed close to zero with $| β_{i j} (k) | < \infty$ , $| β_{i j}^{- 1} (k) | < \infty$ , and $| β_{i j}^{- 2} (k) | < \infty$ . This condition is identical to the convergence condition for SPSA algorithm in Spall²⁶ where the design of this broadcast controller is inspired from.

Proof

The following facts prove the theorem.

(i) For all $k \in ℤ_{0 +}$ , the relation from equations (1), (2), (3), (5), (7), and (8) can be written as

\begin{matrix} x_{i} (2 k + 1) = x_{i} (2 k) + u_{i} (2 k) \\ = x_{i} (2 k) + ψ (2 k, ξ_{i} (2 k), y (2 k)) \\ = x_{i} (2 k) + c (2 k) β_{i} (2 k) \end{matrix}

\begin{matrix} x_{i} (2 k + 2) = x_{i} (2 k + 1) + u_{i} (2 k + 1) \\ = x_{i} (2 k + 1) + ψ ((2 k + 1), ξ_{i} (2 k + 1), y (2 k + 1)) \\ = x_{i} (2 k + 1) - ξ_{i 2} (2 k + 1) \\ - γ (d ((2 k + 1), ξ_{i} (2 k + 1), y (2 k_{1}))) \end{matrix}

\begin{array}{l} x_{i} (2 k + 2) = x_{i} (2 k + 1) - ξ_{i 2} (2 k + 1) \\ - \hat{a} (\frac{Δ J}{c (2 k + 1)} ξ_{i 1}^{(- 1)} (2 k + 1)) \end{array}

where

\hat{a} (2 k) = \hat{a} (2 k + 1) : = \{\begin{matrix} e \frac{c (2 k + 1)}{| Δ J |} & if | Δ J | > \frac{c (2 k + 1) e}{a (2 k + 1)} \\ a (2 k + 1) & otherwise \end{matrix}

If k is even, the position of the robot in equation (1) is updated with random movement $c (2 k) β_{i} (2 k)$ as shown in equation (10). Then, the resulted position from equation (10) is updated with deterministic movement $- ξ_{i 2} (2 k + 1) - γ (\cdot)$ if k is odd as appears in equation (11). From the definition of the saturation function $γ (\cdot)$ in equations (7) and (8), we can obtain equation (12) where the design of gain $\hat{a}$ (the same gain is used if k is even and odd) is given in equation (13). The value of gain $\hat{a}$ obtained from equation (13) determines how far the robot will perform the deterministic movement. The detailed derivation of gain $\hat{a}$ is described in the following paragraph.

Note that equation (12) corresponds to a general stochastic approximation algorithm in Appendix 1. From the convergence conditions of the modified broadcast controller algorithm, it is obvious that C2–C5 imply D1–D4 in Appendix 1. On the other hand, $\hat{a} (2 k + 1)$ in equation (13) is a nontrivial fact that must be proven to show that it satisfies the condition in C4.

(ii) Conditions from C1, C2, and C4 imply C4′ $\hat{a} (k) = \hat{a} (k + 1) > 0$ , $c (k) = c (k + 1) > 0$ for all $k \in {0, 2, 4, \dots}$ , ${lim}_{k \to \infty} \hat{a} (k) = 0$ , ${lim}_{k \to \infty} c (k) = 0$ , and $\sum_{k = 0}^{\infty} \hat{a} {(k)}^{2} / c {(k)}^{2} < \infty$ . Moreover, $\sum_{k = 0}^{\infty} \hat{a} (k) = \infty$ w.p.1.

(iii) From equations (7) and (8) and γ notation in the first section 1

γ (d ((2 k + 1), ξ_{i} (2 k + 1), y (2 k + 1))) = min (| d ((2 k + 1), ξ_{i} (2 k + 1), y (2 k + 1)) |, e) sgn (d ((2 k + 1), ξ_{i} (2 k + 1), y (2 k + 1)))

since $a (2 k + 1) (\frac{Δ J}{c (2 k + 1)} ξ_{i 1}^{(- 1)} (2 k + 1)) > e$ is equivalent to

e sgn (Δ J ξ_{i 1}^{(- 1)} (2 k + 1))

and since the parameter that we want to control is $Δ J$ , thus

γ (d ((2 k + 1), ξ_{i} (2 k + 1), y (2 k + 1))) = \{\begin{matrix} e sgn (Δ J ξ_{i 1}^{(- 1)} (2 k + 1)) if | Δ J | > e \frac{c (2 k + 1)}{a (2 k + 1)} \\ a (2 k + 1) (\frac{Δ J}{c (2 k + 1)} ξ_{i 1}^{(- 1)} (2 k + 1)) otherwise \end{matrix}

where $e \in ℝ_{+}$ is a predefined positive integer. The next step is to reconstruct equation (14) so that it follows the standard SPSA algorithm as shown in equation (8). From signum properties

e sgn (Δ J ξ_{i 1}^{(- 1)} (2 k + 1)) = e \frac{c (2 k + 1)}{c (2 k + 1)} \frac{| Δ J |}{| Δ J |} sgn (Δ J ξ_{i 1}^{(- 1)} (2 k + 1)) = e \frac{c (2 k + 1)}{| Δ J |} \frac{Δ J}{c (2 k + 1)} ξ_{i 1}^{(- 1)} (2 k + 1)

So, equation (16) shows that it satisfies equations (11) and (12) that we have equation (13).

(iv) The detailed proof of fact (ii) is shown here. For the first condition, since $0 < \hat{a} (k) < a (k)$ for all $k \in ℤ_{0 +}$ holds from equation (13) and C4, it follows a straightforward proof from Tanaka et al.¹⁹ which shows that our first condition of C4′ holds. Now, we prove the second condition of C4′, that is, $\sum_{k = 0}^{\infty} \hat{a} (k) = \infty$ w.p.1. For every $k \in ℤ_{0 +}$ , conditions C1 and C2 imply that there exist $δ_{0} > 0$ satisfying

∥ \nabla J^{(1)} (x (2 k)) ∥_{\infty} \leq δ_{0}

By applying Taylor’s theorem (e.g. Appendix I in Azuma et al.,²⁷), C1, C5, and equation (17)

| \nabla J | \leq | c (2 k) \nabla J^{(1)} x ((2 k)) β (2 k) + \frac{c {(2 k)}^{2}}{2} \nabla J^{(2)} (x (2 k)) β (2 k) \otimes β (2 k) | \leq c (2 k) n δ_{0} + \frac{c {(2 k)}^{2}}{2} n^{2} ω_{0}^{2} w.p.1

Substituting equation (18) into equation (13)

\begin{matrix} \frac{c (2 k) e}{| Δ J |} \geq e (\frac{c (2 k)}{c (2 k) n δ_{0} + \frac{c {(2 k)}^{2} n^{2} ω_{0}^{2}}{2}}) \\ \geq e {(n δ_{0} + \frac{c (2 k) n^{2} ω_{0}^{2}}{2})}^{- 1} w.p.1 \end{matrix}

Finally, from equations (13) and (18), $e > 0$ , $n > 0$ , $δ_{0} > 0$ , and $ω_{0} > 0$

\begin{matrix} \sum_{k = 0}^{\infty} \hat{a} (2 k) \geq \sum_{k = 0}^{\infty} \frac{c (2 k) e}{| Δ J |} \\ \geq \sum_{k = 0}^{\infty} e {(n δ_{0} + \frac{c (2 k) n^{2} ω_{0}^{2}}{2})}^{- 1} \\ = \infty w.p.1 \end{matrix}

which verify the proof.

Here we provide comments on conditions C1–C5. The twice differentiability, that is, $\nabla J^{(2)} (x)$ , in C1 means that the resulting J is sufficiently smooth and it is required to obtain equation (3A) in Appendix 1 by Taylor’s theorem. The easiest way to satisfy this condition is to ensure that the order of J is at least quadratic. In C2, the condition is required to obtain Taylor’s theorem in equation (18). In C3, the condition is required to guarantee that if $x (k)$ does not comply with this condition, the local minimum of $\nabla J (z (k))$ (i.e. $\nabla J (x (k))$ ) would still exist. That is because the gradient system and broadcast control system are different. So, even if the gradient system is stable, $x (k)$ would not necessarily converge to the solution. A sufficient condition for $x^{*}$ to be asymptotically stable solution is that the Hessian matrix of $J (x)$ must be nonsingular at each x satisfying $\nabla J (x) = 0$ . In summary, this condition is just a condition for gradient system correlated with the broadcast control. Condition C4 is imposed for users to design the gains a and c. More details are discussed in the fourth section, where by following the typical design would easily satisfy this condition. Finally, condition in C5 is provided to specify the random variables $β_{i j}$ which can be easily achieved.

Before explaining the simulation results, we summarize the modified broadcast control in Algorithm 1.

Algorithm 1.

Modified broadcast controller.

Numerical simulation

Consider the broadcast control system P in Figure 2, for $N : = 6$ , $n : = 2$ , $λ : = 1 \times 10^{30}$ , and $e : = 0.5$ . The cost function considered in this simulation is role-assignment task given in equation (6) where this choice of cost function is assumed to satisfy C1. For the broadcast controller $(L_{1}, L_{2}, \dots, L_{N}, G)$ , we employed the modified broadcast controller given by equations (2), (3), (7), and (8) which was proven to approximately achieve the convergence w.p.1 subject to C1–C5. Note that there is a difference between the local controllers utilized in the standard broadcast controller (i.e. equations (3) and (4)) and the modified broadcast controller (i.e. equations (3), (7), and (8)). This is because the local controller in the standard broadcast controller triggered the instability and resulted in different local controller being utilized in the modified broadcast controller. For this simulation, the gains $a (k)$ and $c (k)$ embedded in the local controllers are set to be the same as in Table 1 where these gains were arbitrarily chosen to satisfy the condition in C4. Note that the general guidelines to design the gains $a (k)$ and $c (k)$ can be found in Sections 7.5.1 and 7.5.2 of Spall.²⁸ For the value of e, we referred to the example given in Tanaka et al.¹⁹ and adjusted this value according to the size of the deterministic movement taken by the robots that the user want, that is, the larger the value of e, the larger the deterministic movement of the robots.

Figure 5 shows the snapshots of the initial positions of the robots $x_{i} (0) (i = 1, 2, \dots, N)$ and the target positions of the robots $p_{j} (j = 1, 2, \dots, N)$ . The values of these initial and target positions are set to be the same as in Table 1. The circles in gray denoted the robots numbered as $x_{1} (0)$ until $x_{6} (0)$ counted from the right-hand side and the small squares are the target positions. On the other hand, Figure 6 shows the positions of the robots $x_{i} (k) (i = 1, 2, \dots, N)$ at different iteration $k = (0, 500, \dots,2000)$ when performing the role-assignment task using the modified broadcast controller. Note that the desired position for the robots to perform the assignment task is unknown (i.e. it is not necessary for robot 1 to converge to target position 1, for robot 2 to converge to target position 2, etc.) and the robots are required to cooperate with each other to determine their ideal target positions.

Figure 5.

Snapshot of (a) initial position and (b) target position.

Figure 6.

Positions of robots at different iteration k when performing role-assignment task: (a) $k = 500$ , (b) $k = 1000$ , (c) $k = 1500$ , and (d) $k = 2000$ .

Figure 7 provides the evolution of the cost function from Figure 6 to perform the role-assignment task with the modified broadcast controller. The evolution is also compared with the standard and constant-distance random movement¹² (CDRM) broadcast controllers to analyze the performance of our modified broadcast controller in performing the role-assignment task. From the figure, the robots with modified broadcast controller begin to converge into the assigned positions at about $k = 400$ . Meanwhile, the standard and CDRM broadcast controllers diverge toward the infinite value of $J (x (k))$ even at the beginning of the iteration. We also have tuned the gain parameters of these three broadcast controllers for some values as tabulated in Table 2, but the evolution is still showing the same, that is, the modified broadcast controller is converging while the standard and CDRM broadcast controllers are diverging. Note that the CDRM broadcast controller only limits the random movement of the robots and not the deterministic movement. Because of this fact, the CDRM broadcast controller also diverges toward the infinite value of $J (x (k))$ .

Figure 7.

Evolution of the cost function for role-assignment task.

Table 2.

Experiment on different gain parameters for role-assignment task.

Gain parameters	Evolution of cost function
Gain parameters	Modified	Standard	CDRM
$a_{0} = 3$ , $a_{v} = 16.5$ , $a_{p} = 0.7$ , $c_{0} = 2$ , $c_{p} = 0.6$	Converge	Diverge	Diverge
$a_{0} = 4.1$ , $a_{v} = 32$ , $a_{p} = 0.95$ , $c_{0} = 5$ , $c_{p} = 0.36$	Converge	Diverge	Diverge
$a_{0} = 3.34$ , $a_{v} = 50$ , $a_{p} = 1.2$ , $c_{0} = 7$ , $c_{p} = 0.46$	Converge	Diverge	Diverge
$a_{0} = 1.1$ , $a_{v} = 12$ , $a_{p} = 0.8$ , $c_{0} = 1.4$ , $c_{p} = 0.26$	Converge	Diverge	Diverge
$a_{0} = 2.3$ , $a_{v} = 120$ , $a_{p} = 1.8$ , $c_{0} = 1.8$ , $c_{p} = 0.26$	Converge	Diverge	Diverge

CDRM: constant-distance random movement.

In order to demonstrate the usefulness of our modified broadcast controller in handling various classes of motion-coordination tasks, we also employed it to a motion-coordination task that has been successfully solved using the standard and CDRM broadcast controllers. Consider a consensus task¹³ given by

J (x) = (x_{i} - p_{i})^{T} (x_{i} - p_{i})

This cost function is different from the role-assignment task where the robots are assigned with their corresponding target positions. For example, robot x ₁ is required to go to target position p ₁, robot x ₂ is required to go to target position p ₂, and so on. Readers may refer to Cao et al.,²⁹ Wasiela et al.,³⁰ and Huang et al.,³¹ for other examples of consensus task. Note that we used the same parameter values as in Table 1 for this task except $a (k)$ , $c (k)$ , and e. For the gains $a (k)$ and $c (k)$ , we set the parameters $a_{0} = 2.2$ , $a_{v} = 450$ , $a_{p} = 0.95$ , $c_{0} = 0.26$ , and $c_{p} = 0.16$ while the value of e is set to be $e : = 1$ . Figure 8 shows the position of the robots $x_{i} (k) (i = 1, 2, \dots, N)$ at iteration $k = (0, 500, \dots,2000)$ .

Figure 8.

Positions of robots at different iteration k when performing consensus task: (a) $k = 500$ , (b) $k = 1000$ , (c) $k = 1500$ , and (d) $k = 2000$ .

Figure 9 shows the performance index of the modified broadcast controller in performing the consensus task. Since the standard and CDRM broadcast controllers can also perform this consensus task, we also include the evolution of the cost function of these two broadcast controllers so that we can compare the convergence time between all broadcast controllers. In this regard, we define the convergence time as the required number of iterations for the objective function $J (x (k))$ to achieve its minimum value and we choose the minimum value to be $J (x (k)) \leq 5$ . From Figure 9, we observe that the modified broadcast controller converges faster (converges at around $k = 1093$ ) as compared to the standard broadcast controller (converges at around $k = 1465$ ) but it shows a slower convergence compared to the CDRM broadcast controller (which converges at around k = 858).

Figure 9.

Evolution of the cost function for consensus task.

In order to fairly compare the convergence time in performing the consensus task, we run the simulation for 10 times for each broadcast controller and tabulated the results in Table 3. From the table, in particular the average values, it is obvious that the modified broadcast controller significantly improves the convergence time approximately 32% compared to the standard broadcast controller while being competitive when compared to the CDRM broadcast controller. On the other hand, the standard deviation shows that the convergence time for the modified broadcast controller does not varies much from the average in contrast with standard and CDRM broadcast controllers. This convergence time improvement is due to the limit we set for the norm of the update vector of robots’ positions (in this simulation, the parameter is e). Consecutively, we can confirm the effectiveness of our modified broadcast controller in handling the motion-coordination task in terms of the instability and also has the possibility to reduce convergence time.

Table 3.

Convergence time for modified, standard, and CDRM broadcast controllers.

	Standard	Modified	CDRM
Minimum	800	886	790
Maximum	1902	1058	1110
Average	1390.7	945.7	934.6
Standard deviation	357.5	63.3	98.0

CDRM: constant-distance random movement.

Conclusion

This article has addressed the issue of unstable solution in the standard broadcast control framework to solve certain motion-coordination tasks. Briefly, the standard broadcast control framework was modified, that is, limiting the norm of the update vector of robots’ position. As a theoretical result, the proposed modified broadcast controller was proven to approximately achieve the convergence w.p.1. Finally, simulation results were provided to illustrate the effectiveness of our modified broadcast controller in solving the instability issue and the possibility to reduce convergence time. As for future work, collision avoidance should be included into the broadcast controller so that we can prevent damage to the robots. In addition, experiments based on real robotic systems should also be considered to validate the performance of the modified broadcast controller.

Footnotes

Acknowledgement

The authors would like to thank Universiti Teknologi Malaysia for funding this research project.

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) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by Universiti Teknologi Malaysia through a research grant (Q.K130000.2543.13H80) titled “Machine Vision Algorithm for Remotely Operated Vehicle in the Inspection of Industrial Reservoirs.”

ORCID iD

Zool Hilmi Ismail

Appendix 1

A general stochastic approximation algorithm, that is, Robbins–Monro algorithm, is given by

where $t \in ℤ_{0 +}$ is discrete time, $ζ (t) \in ℝ^{d}$ is the state, $a (t) \in ℝ_{+}$ is the time-varying gain, $F : ℝ^{d} \to ℝ^{d}$ is a function that needs to be minimized, and $σ (t)$ as well as $e (t) \in ℝ^{d}$ are random variables. For detailed convergence analysis of this algorithm, refer to Kushner and Clark.³²

Considering the algorithm in equation (1A), the solution for $ζ^{*} \in ℝ^{d}$ and $min F (ζ (t))$ can be obtained if the following conditions are satisfied.

D1: There exist a compact set $S \subseteq ℝ^{d}$ where this set is the stability region for $\dot{ζ} (t) = - F (ζ (t))$ . The $\dot{ζ} (t) = - F (ζ (t))$ with $ζ (0)$ results in $ζ (\infty) = ζ^{*}$ such that $ζ (t) \in S$ occurs infinitely often for every $ζ (0) \in S$ and almost all sample points.

D2: ${lim}_{t \to \infty} a (t) = 0$ and $\sum_{t = 0}^{\infty} a (t) = \infty$ .

D3: ${sup}_{t \in Z_{0 +}} ∥ ζ (t) ∥ < \infty$ w.p.1 for every $ζ (0) \in S$ .

D4: For every $ζ (0) \in S$ and $t \in ℝ_{+}$

lim_{t \to \infty} Pr (sup_{l \geq i} ∥ \sum_{t = i}^{l} a (i) e (i) ∥ \geq t) = 0

From equation (12) and C4′

and by applying Taylor’s theorem to $Δ J$ (note the difference between $Δ J$ and $\nabla J$ ) and taking similar way as in Ji et al.²⁵ and Spall²⁶ resulted in

This means

The form in equation (4A) can be transformed into

where $x_{i} (2 k + 2)$ , $x_{i} (2 k)$ , $\hat{a} (2 k)$ , $\nabla J (x_{i} (2 k))$ , $\nabla J (x_{i} (2 k)) - E (d (2 k, ξ_{i} (2 k)), y (2 k) | x (2 k))$ , and $O (c (2 k))$ correspond to $ζ (t + 1)$ , $ζ (t)$ , $a (t)$ , $F (ζ (t))$ , $σ (t)$ , and $e (t)$ , respectively, in equation (1A).

References

Ismail

Sariff

. A survey and analysis of cooperative multi-agent robot systems: challenges and directions. In: Hurtado EG (ed) Applications of mobile robots. London, UK: IntechOpen, 2018, pp. 8–14.

Ueda

Odner

Asada

. Broadcast feedback of stochastic cellular actuators inspired by biological muscle control. Int J Robot Res 2007; 26: 1251–1265.

Julius

Halasz

Sakar

, et al. Stochastic modeling and control of biological systems: the lactose regulation system of Escherichia coli . IEEE Trans Autom Control 2008; 53: 51–65.

Wood

Das

Asada

. Broadcast feedback control of cell populations using stochastic Lyapunov functions with application to angiogenesis regulation. In: Proceedings of American control conference (ACC), Seattle, WA, USA, 11–13 June 2008, pp. 6227–6232. New Jersey, US: IEEE.

Mesquita

Hespanha

Astrom

. Optimotaxis: a stochastic multi-agent optimization procedure with point measurements. In: International workshop on hybrid systems: computation and control, St. Louis, MO, USA, 22–24 April 2008, pp. 358–371. Berlin: Springer.

Berman

Halasz

Hsieh

, et al. Optimized stochastic policies for task allocation in swarms of robots. IEEE Trans Robot 2009; 25(4): 927–937.

Das

Ghose

. Positional consensus in multi-agent systems using a broadcast control mechanism. In: Proceedings of American control conference (ACC), St. Louis, MO, USA, 10–12 June 2009, pp. 5731–5736. IEEE.

Azuma

Sugie

. Broadcast control of multi-agent systems. In: Proceedings of decision and control and European control conference (CDC-ECC), Orlando, FL, USA, 12–15 December 2011, pp. 3590–3595. IEEE.

Azuma

Yoshimura

Sugie

. Broadcast control of multi-agent systems. Automatica 2013; 49(8): 2307–23161.

10.

Azuma

Sakar

Pappas

. Stochastic source seeking by mobile robots. IEEE Trans Autom Control 2012; 57(9): 2308–2321.

11.

Azuma

Baba

Sugie

. Broadcast control of Markovian multi-agent systems. SICE J Control Measure Syst Integrat 2016; 9(2): 103–112.

12.

Tanaka

Azuma

Sugie

. Broadcast control with constant-distance random movement. Trans Soc Instrum Control Eng 2014; 50: 139–146.

13.

Tanaka

Azuma

Sugie

. Broadcast control of multi-agent systems with quantized measurements. IEICE Trans Fundam Electron Commun Comput Sci 2014; 97(3): 830–839.

14.

Tanaka

Azuma

Sugie

. Multi-agent consensus under a communication-broadcast mixed environment. Int J Control 2014; 87(6): 1103–1116.

15.

Ito

Kamal

MAS

Yoshimura

, et al. Multi-vehicle coordination on merging roads based on pseudo-perturbation-based broadcast control. In: Proceedings of annual American control conference (ACC), Milwaukee, WI, USA, 27–29 June 2018, pp. 4008–4013. IEEE.

16.

Ito

Kamal

MAS

Yoshimura

Azuma

. Coordination of connected vehicles on merging roads using pseudo-perturbation-based broadcast control. IEEE Trans Intelligent Transp Syst 2018; 20(9): 3496–3512.

17.

Darmaraju

Shanmugavel

Kamal

MAS

, et al. Area coverage by a group of UAVs using the broadcast control framework. IFAC-PapersOnLine 2019; 52(12): 370–375.

18.

Fujishima

Azuma

. Broadcast control of radar surveillance system. In: Annual conference of the Society of Instrument and Control Engineers of Japan (SICE), Nara, Japan, 11–14 September 2018, pp. 83–88. IEEE.

19.

Tanaka

Azuma

Sugie

. Simultaneous perturbation stochastic approximation with norm-limited update vector. Asian J Control 2015; 17: 2083–2090.

20.

Ahmad

Azuma

Sugie

. Performance analysis of model-free PID tuning of MIMO systems based on simultaneous perturbation stochastic approximation. Exp Syst Appl 2014; 41(14): 6361–6370.

21.

Baba

Azuma

Sugie

. Controller design for optimizing fuel consumption of hybrid electric vehicles: a model-free approach based on simultaneous perturbation stochastic approximation. Trans Soc Instrum Control Eng 2013; 49(9): 887–894.

22.

Xiong

Lin

Chen

, et al. Distributed containment control for first-order and second-order multi-agent systems with arbitrarily bounded delays. Int J Robust Nonlinear Control 2019; 29(4): 1122–1131.

23.

Liu

Gao

. A distributed flocking control strategy for UAV groups. Comput Commun 2020; 153: 95–101.

24.

Liu

Zhang

, et al. Formation control of multiple mobile robots incorporating an extended state observer and distributed model predictive approach. IEEE Trans Syst Man Cybern Syst 2018; 1–11.

25.

Azuma

Egerstedt

. Role-assignment in multi-agent coordination. Int J Assist Robot Mechatronics 2006; 7(1): 32–40.

26.

Spall

. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Trans Autom Control 1992; 37(3): 332–341.

27.

Azuma

Baba

Sugie

. Broadcast control of group of Markov chains. In: Annual conference on decision and control (CDC), Maui, HI, USA, 10–13 December 2012, pp. 2059–2064. IEEE.

28.

Spall

. Introduction to stochastic search and optimization: estimation, simulation, and control (Vol. 65). Hoboken: John Wiley and Sons, 2005.

29.

Cao

Zhang

, et al. Observer-based consensus tracking of nonlinear agents in hybrid varying directed topology. IEEE Trans Cybern 2017; 47(8): 2212–2222.

30.

Wasiela

Kasshyap

Pan

, et al. Realization of consensus with collision and obstacle avoidance in an unknown environment for multiple robots. In: International conference on robotics and biomimetics (ROBIO), Dali, China, 6–8 December 2019, pp. 741–746. IEEE.

31.

Huang

Pan

Bauer

. Leader–follower consensus control of multiple quadcopters under communication delays. J Dyn Syst Meas Control 2019; 141(10): 1–10.

32.

Kushner

Clark

. Stochastic approximation methods for constrained and unconstrained systems (Vol. 26). Berlin: Springer Science and Business Media, 2012.