G-flocking: Flocking Model Optimization based on Genetic Framework
Li Ma Weidong Bao Xiaomin Zhu Meng Wu Yuan Wang Yunxiang Ling Wen Zhou
cs.MA cs.RO



G-flocking: Flocking Model Optimization based on Genetic Framework
    Li Ma, Weidong Bao, Xiaomin Zhu, Member, IEEE, Meng Wu, Yuan Wang, Yunxiang Ling, and Wen Zhou
This work was supported in part by the National Natural Science Foundation of China under Grants 61872378,  91648204, 71702186, in part by Postgraduate Research Innovation Project in Hunan Province under grant CX2018B021, in part by the Scientific Research Project of National University of Defense Technology under Grants  ZK17-03-48
    Received: date / Accepted: date
=================================================================================================================================================================================================================================================================================================================================================================================================================================================




Flocking model has been widely used to control robotic swarm. However, with the increasing scalability, there exist complex conflicts for robotic swarm in autonomous navigation, brought by internal pattern maintenance, external environment changes, and target area orientation, which results in poor stability and adaptability. Hence, optimizing the flocking model for robotic swarm in autonomous navigation is an important and meaningful research domain.




Robotic swarms, flocking model, multiagent systems (MASs). 




§ INTRODUCTION


Robotic swarms pose an attractive and scalable solution to accomplish complicated missions such as search-and-rescue<cit.>, mapping<cit.>, target tracking<cit.>, and full coverage attacking, which can prevent human beings from boring, harsh and dangerous environment. One main advantage of a robotic swarm solution is the simple local interactions between individuals within a complex system that could generate some new properties and phenomena observed at the system level, such as a set of collective behaviors<cit.>. Much like their biological counterparts such as fish schools<cit.>, bird flocks<cit.>, ant colonies<cit.>, and cell populations<cit.>, the resulting collective patterns are robust and flexible to agents joining in and dropping out, especially when accidents like obstacles, dangers, and new missions emerge. While robotic swarm enjoys numerous advantages, the large-scale autonomous robotic swarm incurs a high robot-failure probability due to real-life conditions when delays, uncetainties, and kinematic constraints are present. This phenomenon is even more noticeable in military projects like Gremlins<cit.> and LOCUST<cit.>, since they are built on small, low-cost and semi-autonomous UAVs whose failure probability is expected to be much higher.

Among researches of flocking models with obstacle avoidance, Wang et al.<cit.> proposed an improved fast flocking algorithm with obstacle avoidance for multi-agent dynamic systems based on Olfati-Sabers algorithm. Li et al.<cit.> studied the flocking problem of multi-agent systems with obstacle avoidance, in the situation when only a fraction of the agents have information on the obstacles. Vrohidis et al.<cit.> considered a networked multi-robot system operating in an obstacle populated planar workspace under a single leader-multiple followers architecture.



To the best of our knowledge, few previous literatures studied the model that satisfies both stability and adaptivity of the autonomous robotic swarm. Thus, we design a novel genetic flocking optimizing framework that can achieve both stability and adaptivity of the robotic swarms. As shown in Fig. 1, a robot is seperated into three layers, including sensing layer, decision layer, and action layer, which supports the basic navigation function. Besides, we generalize velocity updating formula by rules described with weight parameters, which evolves through interaction with the environment. The environment is divided into two layers: the evaluation layer and the evolutionary layer, where the former provides fitness function for the latter. 



§ GENERALIZED FLOCKING MODEL


As shown in Fig. 2, a robot agent i has four detection areas: repulsion area, alignment area, attraction area, and obstacle avoidance area. The velocity updating fomula is described as follows:

In equation (1), we define the weight parameters a, b, c, d, e∈( 0,1), which is used to flexibly handle the generalization formula. 




    Δ v_i    = 
    a∑_j ∈Z_rep(R_0 - r_ij)p_i - p_j/r_ij
       + b1/N_ali∑_j ∈Z_aliv_j/| v_j| + c∑_j ∈Z_att(R_2 - r_ij)p_j - p_i/r_ij
       + d∑_j ∈Z_obs(R_3 - r_ik)p_i - p_k/r_ik + ep_tar - p_i/r_itar + v(t) .




Tunning the model above means that we propose four rules referring to classic reynolds' boids model and we optimize the parameters there. Note that the parameter space is 20-dimensional; therefore, manual tuning, global optimization methods, or parameter sweeping would be generally much time-consuming.



§ ORDER PARAMETERS AND FITNESS FUNCTION

In order to select the set of parameters that perform the best in the simulation process, we propose a fitness function composed by several order parameters, which helps us to abstract the mathematical model of single objective optimization. The fitness function is described as flollows:


    F    = ∑_j (T_j^arrive - T_j^start)/N×N_death/N_total
       ×∑_t ∑_j √((p_j^x - r_t^x)^2 + (p_j^y - r_t^y)^2)/NT
       ×∑_t (γ _t - γ̅)/T
       ×∑_t ∑_j (θ _j^t - δ ^t)^2/T×α  ,


where T_j^start is the time when the navigation is triggered, and T_j^arrive is the time when robotic agent j reaches the target area. N_death represents the number of the dead agent, and N_total represents the number of the total agents in the robotic swarm. r_t^x and r_t^y are the abscissa and ordinate of the position of the swarm's centroid at time t. T is the total time of the whole navigation process, while N is the agent number of the agents that arriving at target area.

We define the stability of the robotic swarm as the variance of the γ_t sequence, which describes whether the flock structure of this swarm is stable.

    s_γ ^2 = ∑_t = 0^T ( γ _t - γ̅)^2/T,


    γ _t = ∑_j √(( p_j^x - r_t^x)^2 + ( p_j^y - r_t^y)^2)/N.


We define anisotropic index to describe the variation of population velocity direction. Specifically, it needs to calculate the average angle of each individual velocity direction and flock velocity direction at a certain time, and then calculate the average value of the whole process, which is the index of anisotropic index. The variance of the average angle of the whole process represents the variation range of anisotropic index, and the formula of anisotropy is as follows:

    δ ^t = ∑_j θ _j/N.


With this method, we created a single-objective optimization scenario, which can be solved using genetic algorithm.



§ THE G-FLOCKING ALGORITHM

This research adopts Parameter Tuning of Flocking Model based on classical genetic algorithm (GA) framework. The main algorithm is described as follows:

  




In the algorithm, the random rules R^exp are represented as: {R^1_0,R^2_0,R^3_0,R^4_0}, and R^i_0={a^i_0,b^i_0,c^i_0,d^i_0,e^i_0}, i=1,2,3,4.

The outputs of G-flocking are also a set of optimized rules:
R^opt={R^1_opt,R^2_opt,R^3_opt,R^4_opt}, and R^i_opt={a^i_opt,b^i_opt,c^i_opt,d^i_opt,e^i_opt}, i=1,2,3,4.

Once optimized, we can get the optimal rules for the flocking which composing the BRIAN model.





§ EXPERIMENT ANALYSIS

To reveal the performance improvements of BRIAN, we compare it with basic rule-based model (BREAM). BREAM derives from the classical Reynolds' flocking model that has been widely used. To apply Reynolds' flocking model to more complex environment, the comprehensive obstacle avoidance strategies are integrated into BREAM. 



In order to clearly observe the impacts of different parameters of the formula for velcocity updating, we compare the performance of basic rule-based model (BREAM) and our optimized flocking model for robotic swarm in navigation (BRIAN) in scenary with three basic environmental elements including tunnel obstacle, non-convex obstacle and convex obstacle.




Fig. 3 shows directly that BRIAN performs better than BREAM in uniformity and stability. Fig. 3(a) and Fig. 3(b) represent the performance of these two models with 20 robotic agents, Fig. 3(c) and Fig. 3(d) with 60 robots, Fig. 3(e) and Fig. 3(f) with 100 robots. Specific performance indicators are shown in Table 1. We record the values of each evaluation index of the two models in three situations of the number and scale of robots. Generally, all the indicators of BRIAN model perform better (the smaller, the better). Specifically, aggregation of BRIAN is 56% lower than that of BREAM while the reduction of other indicators (anisotropy, averagetime, uniformity, deathrate, and fitness function) are 88.61%, 32.55%, 89.69%, 100%, and 99.92%, respectively.





Fig. 4 shows the change of uniformity in the whole time step. The total time step of each group of experiments is not the same, but it can be seen from the figure that the data of each group of BRIAN are stable between 0 and 1, which means that the stability and tightness of the cluster are very good during the whole cruise. When BREAM passes through obstacles, it can be seen that there will be large fluctuations near step 31 and step 71. Such fluctuations represent the situation of low cluster tightness and stability when cluster passes through narrow and non-convex obstacles, and the formation is not well maintained. At the same time, it can be seen that BRIAN has completed the whole task in about 84 seconds, while BREAM has completed the whole task.



§ CONCLUSIONS AND FUTURE WORK


We presented in this paper an optimized flocking model for robotic swarm in autonomous navigation. This model is obtained through G-flocking algorithm proposed by us, which is extended from the classical genetic algorithm and rule-based flocking model in most relative researches. This is the first of its kind reported in the literatures; it comprehensively addresses the reliability, adaptivity and scalability of the robotic swarm during completing the navigation tasks.

The following issue will be addressed in our future work: First,  we will extend our experiment to the real-world systems such as unmanned aerial systems and unmanned ground systems. Second, we will take more uncertainties of scenaries into the model to verify the correctness of our model, such as adding the moving obstacle, the irregular barriers, and even fluid barriers.

00

b1 Murphy, R. R., Tadokoro, S., Nardi, D., Jacoff, A., Fiorini, P., & Choset, H., et al. (2008). Search and rescue robotics. Springer Handbook of Robotics, 1151–1173.

b2 Dirafzoon, A. , & Lobaton, E. . (2014). Topological Mapping of Unknown Environments using an Unlocalized Robotic Swarm. IEEE/RSJ International Conference on Intelligent Robots & Systems. IEEE.

b3 Parker, L. E., Rus, D., & Sukhatme, G. S. (2008). Multiple Mobile Robot Systems. springer Handbook of Robotics, 921–941.

b4 Brown, D. S. , Kerman, S. C. , & Goodrich, M. A. . (2014). [acm press the 2014 acm/ieee international conference - bielefeld, germany (2014.03.03-2014.03.06)] In Proceedings of the 2014 acm/ieee international conference on human-robot interaction - hri 1̈4 - human-swarm interactions based on managing attractors. 90-97.


b5 Krause, J., Hoare, D., Krause, S., Hemelrijk, C. K., & Rubenstein, D. I. (2015). Leadership in fish shoals. Fish & Fisheries, 1(1), 82-89.

b6 Nagy, Máté, ákos, Zsuzsa, Biro, D. , & Vicsek, Tamás. (2010). Hierarchical group dynamics in pigeon flocks. Nature, 464(7290), 890-893.

b7 Feinerman, O. , Pinkoviezky, I. , Gelblum, A. , Fonio, E. , & Gov, N. S. . (2018). The physics of cooperative transport in groups of ants. Nature Physics.

b8 Cheung, K. J., Gabrielson, E., & Werb, Z., et al.(2013). Collective invasion in breast cancer requires a conserved basal epithelial program, Cell, 155(7). 

b9 Talal Husseini.(2018). Gremlins are coming: DARPA enters Phase III of its UAV programme. https://www.army-technology.com/features/gremlins-darpa-uav-programme/.

b10 (2018). Raytheon gets $29m for work on US Navy LOCUST UAV prototype. https://navaltoday.com/2018/06/28/raytheon-wins-contract-for-locus-inp/.

b11 Wang, J., & Xin, M. (2013). Flocking of multi-agent system using a unified optimal control approach. Journal of Dynamic Systems Measurement & Control, 135(6), 061005.

b12 Li, J. , Zhang, W. , Su, H. , & Yang, Y. . (2015). Flocking of partially-informed multi-agent systems avoiding obstacles with arbitrary shape. Autonomous Agents and Multi-Agent Systems, 29(5), 943-972.

b13 Vrohidis, C. , Vlantis, P. , Bechlioulis, C. P. , & Kyriakopoulos, K. J. . (2018). Reconfigurable multi-robot coordination with guaranteed convergence in obstacle cluttered environments under local communication. Autonomous Robots, 42(4), 853-873.






[
    < g r a p h i c s >
]Li Ma is currently working toward his Ph.D. degree in the College of Systems Engineering, National University of Defense Technology. Contact him at mali10@nudt.edu.cn.

[
    < g r a p h i c s >
]Weidong Bao is currently a professor in the College of Systems Engineering at National University of Defense Technology, Changsha, China. Contact him at wdbao@nudt.edu.cn.

[
    < g r a p h i c s >
]Xiaomin Zhu is currently an Associate Professor in the College of Systems Engineering at National University of Defense Technology, Changsha, China. Contact him at xmzhu@nudt.edu.cn.

[
    < g r a p h i c s >
]Meng Wu is currently pursuing the M.S. degree in the College of Systems Engineering, National University of Defense Technology, China. Contact her at wumeng15@nudt.edu.cn.

[
    < g r a p h i c s >
]Yuan Wang is currently a Ph.D Candidate of College of Systems Engineering, National University of Defense Technology, Changsha, China. Contact him at wy1020395067@hotmail.com.

[
    < g r a p h i c s >
]Yunxiang Ling is currently a professor in Officers college of PAP, Chengdu, China. Contact him at 2923821396@qq.com.

[
    < g r a p h i c s >
]Wen Zhou is currently an Assistant Professor in the College of System Engineering at National University of Defense Technology, Changsha, China. Contact him at zhouwen@nudt.edu.cn.

