Following the successful publication in Nature Communications, the research team from Beihang University has published a paper titled “Mean-Shift Shape Formation of Multi-Robot Systems Without Target Assignment” in RA-L, a top robotics journal.

The paper employs a distributed, assignment-free algorithm based on the Mean-shift method to enable ten mobile robots to sequentially form the letters “R,” “A,” and “L” in real-world experiments. The effectiveness of the algorithm in real scenarios was validated with the help of the NOKOV measurement motion capture system. Additionally, the effectiveness, precision, and efficiency of the algorithm in forming complex formations at different group sizes were verified through simulation experiments.

Fig.1. Real-world experiment showing the sequential formation of the letters “R,” “A,” and “L” from random initial positions.

Citation:

Y. Zhang, R. Zhou, X. Li and G. Sun, "Mean-Shift Shape Formation of Multi-Robot Systems Without Target Assignment," in IEEE Robotics and Automation Letters, vol. 9, no. 2, pp. 1772-1779, Feb. 2024, doi: 10.1109/LRA.2024.3349926.

Research Background

Formation control in multi-agent systems is typically divided into two smaller problems: target assignment and collision avoidance. Target assignment strategies are categorized into pre-assignment and dynamic assignment methods. The former may reduce collision avoidance flexibility and increase the complexity of path planning; the latter may face high computational costs and potential conflict issues. Assignment-free methods eliminate the target assignment process but struggle to form formations with precise target positions. Therefore, achieving accurate, assignment-free formation control has become a research focus.

This paper proposes a distributed assignment-free algorithm based on the mean-shift algorithm to achieve precise and efficient formation control, and validates the algorithm's accuracy, efficiency, and practicality through simulation and real-world experiments.

Experimental results

1) Simulation experiments:

A. Effectiveness of the proposed algorithm for complex target formations and different group sizes

The formation control algorithm proposed in this paper effectively guides 200 robots to form complex desired formations in less than 30 seconds. When the group size increases from 50 to 350, the convergence time for the "DNA" formation increases from 10 seconds to 60 seconds. The increase in group size does not significantly affect the convergence time. These simulation results demonstrate the algorithm's effectiveness in forming complex formation shapes.

B. Comparison of the proposed algorithm with target assignment algorithms and mean-shift-based algorithms

The mean-shift-based algorithm cannot achieve precise target formation control. On the other hand, the convergence time of target assignment algorithms is more than eight times that of the proposed algorithm. This simulation experiment validates the advantages of the proposed algorithm in terms of formation control accuracy and efficiency.

2) Real-world verification experiments:

Fig.2 Real-world experiment system configuration and results

The experimental platform is equipped with the NOKOV optical 3D motion capture system to obtain the real-time position and heading angle of the robots. A PC is used to receive the robots’ state data and extract real-time status. The experiments are conducted on the PC (MATLAB/Simulink) with a distributed parallel mechanism to calculate the control commands from the proposed algorithm. The calculated control commands are then transmitted to the robots at a frequency of 10 Hz via a wireless router.

The ten robots move within a 4m x 5m experimental platform, starting from an initial position and forming the letter formations “R”, “A”, and “L” sequentially. As shown in Figure 2(d), the convergence time of each letter formation is less than 40 seconds, which verifies the applicability of the proposed algorithm in real-world scenarios.