Gradient-Based Differential kWTA Network With Application to Competitive Coordination of Multiple Robots

Mei Liu, Xiaoyan Zhang, Mingsheng Shang, and Long Jin,

Abstract—Aiming at the k-winners-take-all (kWTA) operation,this paper proposes a gradient-based differential kWTA (GDkWTA) network. After obtaining the network, theorems and related proofs are provided to guarantee the exponential convergence and noise resistance of the proposed GD-kWTA network.Then, numerical simulations are conducted to substantiate the preferable performance of the proposed network as compared with the traditional ones. Finally, the GD-kWTA network, backed with a consensus filter, is utilized as a robust control scheme for modeling the competition behavior in the multi-robot coordination, thereby further demonstrating its effectiveness and feasibility.

I. INTRODUCTION

THE winner-take-all (WTA) operation denotes a selection of the maximum element from a specified collection ofminputs [1], [2]. There are many existing schemes for implementing WTA operations. For example, a discrete-time scheme Maxnet is introduced in [3], in whichmneurons are connected and inhibit each other so as to output neurons with maximum value. Afterwards, a group of compact complementary metaloxide-semiconductor integrated circuits withO(m) interconnection are devised and successfully implemented in the WTA operation [4]. Inspired by the species competition, a Lotka-Volterra model is constructed in [5], accomplishing the task of generating WTA behaviours. Being an expansion of the WTA operation, thek-winners-take-all (kWTA) operation is more common and practical, which takesk(k=1,2,...,m) most advanced elements fromminputs [6], [7]. It reveals great value in many application fields, such as decision making [8],information retrieval [9], multi-agent coordination [10], [11],circuit optimization [12]–[14], etc. This prompts researchers to put more effort into this issue. In response to the increasing size of inputs inkWTA operations, large-scale integrated circuits are established in [15], [16]. A continuous-timekWTA network in the form of a differential equation with the spike train being the summation of delta functions is presented in [17], which exhibits the virtues of low complexity and being independent of initial states.

With the in-depth study ofkWTA, a class of optimizationbased methods are developed to address such problems. Taking [18] and [19] for instances, thekWTA operation is performed after being arranged into the combinatorial optimization problem and the linear programming problem with bounded variables, respectively. Additionally, there exists another kind of optimization-based scheme that technically conducts an equivalent conversion between thekWTA operation and the constrained quadratic programming (CQP) problem. This kind of scheme expands ideas forkWTA operations, thus receiving a lot of attention. Particularly, after converting thekWTA operation into the CQP problem, its solution is obtained by leveraging a dual neural network, which processes the property of finite-time convergence without using any hard-limiting function [20]. With the same purpose and transformation procedure as in [20], the work in [21] also constructs a dual neural network to cope with CQP problems, which has only one neuron and a simple structure. For convenience, it is called the D-kWTA network. Schemes mentioned above belong to a recurrent neural network, a powerful tool for tackling numerical problems [22]. Furthermore, the gradient descent method, as a classical method in the recurrent neural network,is therefore considered forkWTA operations, correspondingly termed as a G-kWTA network. It defines the error function asthe index and forces the neural state to descend in the gradient direction of the error function until the equilibrium is reached[23]. It should be noted that the lack of velocity compensation for time-variant parameters makes the G-kWTA network produce lagging errors when dealing with time-variant problems [24]. In other words, the G-kWTA network is good at solving static problems rather than time-variant problems.

TABLE I COMPARISONS AMONG DIFFERENT METHODS FOR K-WTA OPERATION

Fig. 1. Research route of this paper.

On account of its wide applications, multi-agent coordination receives emerging study [25]–[28]. For example, multiple robots handle various problems that are difficult for the individual robot in [29]–[31]. This paper aims at the coordination behavior of target tracking, in which multiple robots cooperate to track the moving target in a competitive way with the help of thekWTA network. Specifically, by exploiting thekWTA network,krobots closest to the target are selected as winners to take actions to chase, while the other (m−k) robots remain stationary, waiting to be activated. This competitive coordination way reduces the movement of the robots as much as possible, thus saving energy and reducing cost. Additionally,this paper uses an average consensus estimator to complete the purpose of global information sharing of robots by drawing on existing research [32], [33]. Due to the real-time nature and complexity of the robot tracking task, its successful execution faces two main challenges. The first challenge is the lagging error induced by existingkWTA networks, as mentioned above. Another challenge is various inevitable noises that appear in the solution process, which would seriously weaken the performance of solvers. Specifically, these noises are mainly divided into two categories: constant noise and random noise, which are mainly caused by the biased voltage and unpredictable fluctuations in the dynamic system.Evidently, it becomes an urgent matter to propose akWTA network equipped with strong robustness, high accuracy, and real-time processing ability.

Motivated by the above discussion, this paper investigates a gradient-based differentialkWTA (GD-kWTA) network. As an improvement, the time-derivative information is applied on the GD-kWTA, and thus perfectly eliminates the lagging error and helps the GD-kWTA network converge to the theoretical solution. Further, an integration item is incorporated into the GD-kWTA network so that it can resist noises. In view of the characteristic of thekWTA problem, a bounded function is added to the network to further improve the accuracy of the output of the network. Table I presents the difference between the proposed network and existing networks. Firstly, most existing networks are designed for time-invariant problems,and they may generate lagging errors when handlingkWTA operation with time-variant inputs. As an improvement, the proposed GD-kWTA network is designed for time-variantkWTA operation, which eliminates the lagging error and improves the accuracy of the solution. Secondly, noises are inevitable in real applications, and few researches take into account both lagging error and noise disturbance, which are handled by the proposed network. Thirdly, the G-kWTA network, network [20], and D-kWTA network [21] fail to be applied in multi-robot coordination, while the proposed one achieves it. Lastly, compared with the latest research [31], the proposed network has higher accuracy, and the computational complexity of the proposed network is lower than that of the network [31]. In short, the proposed network compares favorably with recent schemes for performing thekWTA operation.

To clearly describe the research route of this paper, Fig. 1 is presented. Moreover, the organization of the remaining sections is as follows. Section II introduces thekWTA operation and provides its solution schemes. Section III theoretically analyzes the convergence performance of the proposed GDkWTA network. Section IV offers simulation results in noisefree and noisy cases. Section V discusses the realization of multi-robot coordination. In the final section, it comes to concluding remarks. The contributions of this paper are threefold, as summarized as follows.

1) A novel GD-kWTA network is designed and analyzed in this paper, which is equipped with improved accuracy and enhanced robustness in tacklingkWTA operations. Besides, a bounded function is applied to the output of the network,further improving its accuracy.

2) This paper presents theorems on the convergence and robustness of the proposed network and provides numerical simulations in cases with or without noises to check the correctness of the theorems, as well as to validate the superior performance over existingkWTA networks.

3) Aided with the constructed GD-kWTA network for describing the competitive behavior, an application on the multirobot system for conducting the tracking task is provided. As a result, the task is successfully accomplished.

II. SCHEME FORMULATION AND SOLUTIONS

In this section, we discuss thekWTA operation formulation and its solution schemes, thus laying the foundation for the subsequent work.

A. kWTA Operation Formulation

B. Network Construction

C. Existing kWTA Networks

III. THEORETICAL ANALYSIS AND RESULTS

This section provides theorems on GD-kWTA network (20)to investigate its performance for performing thekWTA operation.

A. Convergence Performance Without Noises

The convergence performance of GD-kWTA network (20)in the absence of noises is demonstrated in Theorems 2 and 3.

Theorem 2:When performingkWTA operation (1), the GDkWTA network (20) globally converges to its theoretical output in the case without noise.

B. Convergence Performance With Noises

This subsection surveys the convergence performance of GD-kWTA network (20) in cases with constant noise and random noise through Theorems 4 and 5, respectively.

IV. NUMERICAL SIMULATIONS

In this section, we provide a numerical example and focus on its simulation results generated by the proposed GD-kWTA network (20) and three comparative networks to further illustrate their performance.

In this simulation, a four-dimensional vector whose value isai(t)=sin(0.25π(t+2i))(i=1,2,3,4)is adopted as the input ofkWTA networks. The number of inputs is defined asm=4,and the number of winners is defined ask=2. For GD-kWTA network (20), the parameters are set as α=30 , β=300, andh¯=0.7; for G-kWTA network (7), α=30; for D-kWTA network (21), ι1=100; for Q-kWTA network (22), likewise,α=30 and β=300 are utilized to ensure the fairness of comparison, and its four bounds are provided aso−=−1,o+=1, ϵ−=−1, and ϵ+=1. Additionally, the whole execution time isT=10 s. In what follows, we introduce the output results generated by four different networks under given inputs with types of noises, corresponding to Figs. 2−4.

Fig. 2. Simulation results generated by GD-kWTA network (20). (a) Inputs and outputs without noise; (b) Inputs and outputs with constant noise n i(t)=10;(c) Inputs and outputs with random noise n i(t)∈[9,11]; (d) Residual errors with and without noises.

Fig. 3. Inputs a(t) of kWTA operation (1) and the corresponding outputs b(t) generated by G-kWTA network (7). (a) Without noise; (b) With constant noise ni(t)=10 ; (c) With random noise n i(t)∈[9,11].

Fig. 4. Inputs a(t) of WTA operation (1) and the corresponding outputs b(t) generated by D-kWTA network (21). (a) Without noise; (b) With constant noise ni(t)=10 ; (c) With random noise n i(t)∈[9,11].

As presented in Fig. 2, GD-kWTA network (20) can find the two largest elements from four time-variant inputs, and their corresponding output value is 1, which is consistent with the definition ofkWTA operation (1), meaning that GD-kWTA network (20) is feasible and effective in performing thekWTA operation in the environment without noise. It can be seen from Fig. 2(b) that when disturbed by constant noise,GD-kWTA network (20) can still successfully complete the selection task and ensure sufficient accuracy in a short time,suggesting that GD-kWTA network (20) is capable of suppressing constant noise well. Similarly to the results under constant noise, GD-kWTA network (20) can also make the correct selection under the interference of random noise. That is to say, GD-kWTA network (20) has the ability to suppress random noise. As shown in Fig. 2(d), the residual error between the theoretical output and the actual output reaches 0.

Fig. 3 shows the output curve of G-kWTA network (7)under different noisy conditions. As it shows in Fig. 3(a),when the ordering of the input changes, it will take a while for the system to produce the correct output. In Figs. 3(b) and 3(c), G-kWTA network (7) can neither guarantee timeliness nor keep the output of the two maximum values at 1 and the minimum output at 0. These results indicate that the G-kWTA network (7) is weak in real-time processing and noise suppression. Similarly, as seen from Fig. 4, D-kWTA network(21) can process time-varying input without noise under the given parameters, but can not produce correct outputs in the presence of noise, which is unacceptable in most practical application scenarios. To intuitively illustrate the performance of Q-kWTA network (22), Fig. 5 is provided. Although residual errors generated by network (22) are small, they are still greater than those generated by the proposed one, which indicates that the proposed network outperforms the Q-kWTA network (22) in terms of solution accuracy. On the whole,these simulation results reveal that the proposed network is superior to existingkWTA networks.

Fig. 5. Residual errors generated by Q-kWTA network (22) with and without noises.

V. COMPETITIVE MULTI-ROBOT COORDINATION

In this section, GD-kWTA network (20), assisted with the consensus estimator, is designed as a competitive coordination control law to perform the target-tracking task in a multi-robot system.

A. Control Law

On this basis, Algorithm 1 is given for describing the coordination of multiple robots.

Algorithm 1 Multi-Robot Coordination Input: Parameters α, β, , m, and k; initial position coordinates and .Output: The trajectory of robots.t

B. Simulation Experiments

Fig. 6. Movement trajectories of robots and the moving target. (a) Snapshot at t =0 s; (b) Snapshot at t =0.8 s. (c) Snapshot at t =2 s; (d) Snapshot at t =7 s.

Fig. 7. Simulation results of 10 robots tracking a moving target synthesized by GD-kWTA network (20) without noise. (a) Output of GD-kWTA network(20); (b) Speed of robots along X axis and Y axis; (c) Distance d between robots and the target.

Fig. 8. Simulation results of 10 robots tracking a moving target synthesized by GD-kWTA network (20) with constant noise. (a) Output of GD-kWTA network (20); (b) Speed of robots along X axis and Y axis; (c) Distance d between robots and the target; (d) Trajectories of robots and the target at t =10 s.

winners. All robots are randomly distributed in a 10 m × 10 m area. The execution time is set asT=10 s, and the rest of parameters in the system are set as: α=100 , β=300 ,h¯=0.7,andc=6. Based on these given conditions and parameters,the simulation is conducted with the results provided in Figs. 6 and 7.

Fig. 6 exhibits the trajectories of robots and the target. As Figs. 6(a)−6(c) show, whent=0 s, robots and the given target are randomly distributed in the form of particles. Fig. 6(b)reveals the snapshot att=0.8 s before the replacement, from which it is discovered that three robots closest to the target node win the competition and are allowed to track the moving target. Over time, as presented in Fig. 6(c), one of the winners is replaced with a new winner and thus remains stationary.The newly selected winner begins to approach the target node.Finally, att=7 s, the task is completed by successfully catching up with the target.

It can be observed from Fig. 7(a) that GD-kWTA network(20) can accurately output the corresponding results. That is,the winners deliver an output of 1, and the losers deliver an output of 0. What’s more, the network can switch quickly from 1 to 0 (and also from 0 to 1) when the winners are renewed. Fig. 7(b) displays the speeds of robots inX-axis andY-axis directions. As shown, the losers maintain a speed of 0,and the speeds of the winners gradually decrease as they get closer to the target and drop to 0 when the task is complete.Fig. 7(c) shows the real-time distance between each robot and the target, which presents a decreasing trend for the three winners. In addition, it can be seen that at aboutt=1.07 s, one of the winners is updated from Robot3 to Robot4 as a consequence of their distances to the target.

With the same parameters, simulation results under constant noise are illustrated in Fig. 8. As can be seen from Fig. 8(a),the output of GD-kWTA network tends to be stable for short intervals. In Fig. 8(b), the velocities of all the robots reach 0 around 9 s, indicating that the robots complete the tracking task in about 9 s, which is also verified in Fig. 8(c). The trajectories of the three winning robots and the target in Fig. 8(d)coincide at (4.05, 3.45), manifesting that the target is successfully pursued at this position.

Fig. 9. Movement trajectory of robots and the target.

C. Application on E-puck2 Robots

To visually exhibit the results, in this part, the experiment is carried out on a 1.4 m × 0.9 m E-puck2 micro-ground swarm intelligent cooperation system. In the experiment, all the communications are conducted on the host, and the 2.4 GHz wireless signal is used for robots to communicate with the host. Six E-puck2 robots (70 mm diameter × 45 mm height)are adopted, with one of them set as the target, and the rest five allocated the tracking task (including two winners). The velocities of robots and the target are respectively set as

1.2bi(t)(θi(t)−θ0(t))/εi(t) m/s and exp(−t)θ0(t)/‖θ0(t)‖2m/s,and the remaining parameters remain consistent with part B.Six snapshots of E-puck2 robots during the execution of the task are displayed in Fig. 9. The analysis of the whole process is similar to the previous subsection. As Fig. 9 shows, with the passage of time, the target keeps moving, and the activated robots follow behind, eventually completing the tracking task att=3 s. In view of this, once more, the feasibility and effectiveness of the proposed GD-kWTA network (20) are substantiated.

Remark 1:Due to the extensive connection between communication entities, networks are vulnerable to cyber-attacks, which seriously threatens their securities. Hybrid cyber-attacks and denial-of-service cyber-attacks are separately handled in[41] and [42], bringing us great inspiration. In the future work,we consider combining this work and existing research to deal with possible cyber-attacks, so as to ensure the stability and security of thekWTA network.

VI. CONCLUSIONS

This paper has designed a gradient-based differentialkwinners-take-all (GD-kWTA) network for performing thekWTA operation and provided an in-depth study on it. Five theorems have been offered, which manifest that the GDkWTA network can exponentially converge to zero in the absence of noises, and can effectively suppress the constant noises and the random noises, if any. With the aid of numerical simulations among the proposed GD-kWTA network and three existingkWTA networks, the superiority and robustness of the GD-kWTA network have been validated. Additionally,on both MATLAB and physical platforms, the GD-kWTA network has been successfully applied to the modeling of competitive behaviours of multiple robots for allocating tasks in real-time in executing the target tracking tasks, demonstrating the practicability and effectiveness of the GD-kWTA network. Considering the engineering application of the network, applying the proposed network to more complex scenarios while taking the impact of cyberattack into account would be a future direction of our research.