Journal of Advances in Artificial Life Robotics
Vol. 4(4); March (2024), pp. 217–221
ON LINE ISSN 2435-8061; ISSN-L 2435-8061
https://alife-robotics.org/jallr.html

SUGISAKAMASANORIInternational JournalAdvances in Artificial Life Robotics
ICAROB series
Editor-in-Chief
Masanori Sugisaka
Co-Editor-in-Chief
Takao Ito

ISSN 2435-8061
Publisher Masanori Sugisaka(Global Register of Publishes)
regstrated in Jan, 25, 1996
Handadai Higashi 2-8-4, Oita, 870-1108, Japan

Research Article

Efficient Movement of Formation Transformation of Multiple
Mobile Robots on a Grid Plane
Kuo-Hsien Hsia, Chun-Chi Lai, Yu-Le Chen

National Yunlin University of Science and Technology, 123 University Road, Section 3, Douliou, Yunlin 64002, Taiwan

ARTICLE INFO
Article History
Received 15 November 2023
Accepted 30 July 2024
Keywords
Multi-robot motion planning
Formation transformation
Grid plane
Munkres assignment algorithm

ABSTRACTMulti-robot motion management is an important issue in the research of mobile robotics.
Formation transformation of multi-robots is one of the problems of multiple mobile-robots
locomotion. The algorithms proposed in the past for this problem cannot guarantee the bestsolution. From a mathematical perspective, this paper uses singularity check for a matrix andMunkres assignment algorithm to develop a new algorithm for solving this problem. Comparing
to the Monte Carlo method, the new algorithm can have better, at least the same, results in a very
short time.

© 2022 The Author. Published by Sugisaka Masanori at ALife Robotics Corporation Ltd.
This is an open access article distributed under the CC BY-NC 4.0 license(http://creativecommons.org/licenses/by-nc/4.0/).

targets, it is often impossible to achieve the shortest path
for all objects at the same time, so there may be two
criterions: the shortest of path summation and the shortestof longest path. The former is a kind of the traditional
assignment problem, while the formation change
problem is the later one.

1. Introduction
Time is money and is now a universal value. Therefore,
how to complete a task with a high efficiency is one of
the factors that must be considered when choosing asolution to the problem. When there are multiple tasks to
be assigned to multiple people working simultaneously,
and all the work is expected to be completed in the mostefficient way, this is a typical assignment problem [1].
The traditional assignment problem is to minimize thetotal time (or total cost). In the formation change problem,
the goal is to complete the change of the entire formationin the shortest time, that is, to allow the person who takes
the most time to complete it in the shortest time.
Path planning is one of the most important issues formotion planning of mobile robots. The goal of path
planning is to generate feasible motion paths to enable
one or more objects to reach specified targets in adesignated area. To move to specified positions in theshortest time, it is very important to find the shortest pathfor each object, and it is necessary to ensure that thismethod is effective all the time. For the case of single
mobile robot, there are many algorithms can be used.
Dijkstra's algorithm [2] is one of the most popular one.
However, in the case of multiple objects and multiple

There are usually two types of motion planning for
multi-robots: one is centralized path planning, and theother is decentralized path planning. The former has acommand center that makes overall planning and thennotifies each robot of the planned path for execution. The
latter has no command center. Each robot determines its
own movement path through communication with eachother and its own judgment. Since the problem
considered in this paper is a formation transformation
problem, It would be more appropriate for the robot's
movement planning to be mandatory by the commandcenter. Every robot should be noticed where he should
move to, and the actual moving path could be determinedby himself. We would like to develop an effective
algorithm to find an efficient assignment way to achievethis goal.

Corresponding author’s E-mail: khhsia@yuntech.edu.tw, cclai@yuntech.edu.tw, 1048576yc@gmail.com

217

2. Preliminary
2.1. Problem description

3. The proposed algorithm
3.1. Deviation of the algorithm

Suppose that there are n robots on a two-dimensional
grid plane. The robots can move laterally or vertically on
the plane in the same speed. They are asked to have theirformation change in the fastest way. In order to complete
this task, we have to minimize the longest routeassignment among all robots.

In [6], the algorithm proposed by Hsia, Li and Su is tofind the optimal assignment way for the robots from theentries of the distance matrix. In this paper, instead ofusing the distance matrix to determine the assignment
way directly, the minimum path is determined from thesingularity check of another matrix named judgement
matrix generated by the positional relationship of theelements in the distance matrix. The judgement matrix isof the same dimension as the distance matrix but with all
entries 0 initially. Then adjust the corresponding entriesof the judgement matrix based on the step-by-step search
results in the distance matrix, and then check thesingularity of the judgement matrix every time todetermine whether it is completed, and then use theMunkres assignment algorithm to determine the target foreach robot.

2.2. Distance between two points
The distance between two points on a Cartesian
coordinate plane could be determined by the L1-norm of
these two points, that is, the sum of the projection of theline segment with these two points as the end points on
the axes. For example, suppose the two points are at(𝑥𝑥1 , 𝑦𝑦1 ) and (𝑥𝑥2 , 𝑦𝑦2 ) , the distance between these twopoints is |𝑥𝑥1 − 𝑥𝑥2 | + |𝑦𝑦1 − 𝑦𝑦2 |.
2.3. Singularity of a matrix

3.2. The proposed algorithm

A square matrix is singular if its determinant is zero.
For a possible solution of the considered transformation
problem, each robot would be assigned a different target
position. The relation of the initial positions of the robots
and the possible target position can form a square matrix.
The relation of an unassigned positions for a robot can be
assigned as 0. For a successful assignment, there will ben non-zero values in the matrix on different rows andcolumns, forming a square matrix of full rank, i.e., thematrix is nonsingular.

Step 1: Establish the distance matrix D with the column
number as the starting position, the row number
as the target position, and the L1-norm fromstarting points to target points as the entries.
Step 2: Create a null matrix of same dimension as thedistance matrix D and named it as the judgement
matrix J.
Step 3: Set the search value s as the smallest value of thedistance matrix.
Step 4: For any position where the element value ofmatrix D is equal to s, fill in an increasing prime
number at the same position in matrix J. Thismeans all nonzero elements in D will bedifferent prime numbers. Note that the smallest
prime number is 2, and the next 5 prime numbers
are 3, 5, 7, 11, 13.
Step 5: If the judgement matrix J is singular(determinant is 0), increase the search value tothe next large number in the distance matrix Dand go back to Step 4. If not, go to the next step.
Step 6: Now the s is the smallest number of steps for theformation transformation. Replace all elementsin the distance matrix D whose value greaterthan s by a sufficiently large number like 9999.
Step 7: Apply Munkres assignment algorithm to thenew distance matrix D to find the best task
assignment for all mobile robots.

2.4. Munkres assignment algorithm
To solve an assignment problem, Munkres assignment
algorithm [3], an improved version of Hungarianalgorithm [4], is a useful tool for optimal solution. For aproblem with n workers and n tasks, and given a cost
matrix with element of i-th row and j-th column being thecost or benefit for assigning the i-th worker to do the j-thtask, either the Munkres algorithm or the Hungarianalgorithm can find the best assignment way thatmaximize the total benefit or minimize the total cost for
the worker with the rule one-worker-one task.
2.5. Monte Carlo method
The Monte Carlo method is a powerful numericalmethod for solving a deterministic problem based on
random sampling and statistical simulation [5]. When theMonte Carlo method is used for solving an assignment
problem, randomly assignments are picked again andagain and the maximum of the solution would be foundin each trial. As the times of sampling increases, moreassignment ways are tested. By minimizing the maximum
values, an almost optimal allocation can be obtained.

218

4. Two examples that the previous algorithm fail on
Two examples are illustrated in this paper. For both
examples, the previous algorithm cannot have actually
good results.
Given 7 starting points marked with a circle and 7 target
points marked with a cross on an 6x6 grid plane. The
starting points are at (1,2), (1,3), (1,4), (1,5), (2, 5), (3,5)
and (5,5); and the target points are at (1,1), (1,2), (2,1),(2,3), (3,1), (5,3) and (5,4), as shown in Fig. 1. Create thedistance matrix D with entries equal to the distances fromthe starting positions to the relative target positions. We
use the listed sequence as the default sequence. For
example, (1,2) as the starting point of the first robot, and(3, 1) as the fifth target point. The distance between thesetwo points is 3. Hence the element of first row and fifth
column is 3. The resulting distance matrix is:
1⎡2⎢3⎢
𝑫𝑫 = ⎢4⎢5⎢6⎣8012345723454572
123235345654
65456542

Fig. 2 Assignment result of Example 1
Table 1 The assignment result of Example 1

65⎤
4⎥
⎥5⎥.
4⎥
3⎥
1⎦

2 19 23
5 47 7
17 0 29
43 0 5300 3100 5900 0

61 00 00 00 00 0
000 37(1, 2) (1, 3) (1, 4) (1, 5) (2, 5) (3, 5) (5, 5)Target point(3, 1) (2, 1) (1, 1) (1, 2) (2, 3) (5, 4) (5, 3)Distance

33

3

3

2

3

2

Another example to verify that the new algorithm isbetter than the previous one is as follows. Given 5 starting
points and 5 target points on the same plane, with thestarting points at (0,4), (3, 4), (4,1), (5,2), (5,3) and thetarget points at (0,0), (0,4), (0,5), (1,1), (4,4), as shown in
Fig. 3. The distance matrix is:

The judgement matrix with search value 3 is:
3
⎡ 13
⎢41
⎢
𝑱𝑱 = ⎢ 0⎢ 0⎢ 0⎣ 0Starting point

00⎤
0 ⎥
⎥
0 ⎥.
0⎥
67⎥
11⎦4
⎡7
⎢
𝑫𝑫 = ⎢5⎢7⎣80 1
3 47 87 8
6 74 45 1⎤⎥
3 3⎥.
5 3⎥
6 2⎦

The judgement matrix with search value 5 is:

The determinant of this judgement matrix is −3.9 × 1011 .
Hence the formation transformation can be completed in
3 steps. However, solving this example using thealgorithm proposed in [6] will result in 4 steps tocomplete the formation transformation. This means thatthe algorithm proposed by [6] cannot guarantee theoptimality of the results obtained. The assignment results
is summarized in Table 1 and the moving paths are shownin Fig. 2.

23 2⎡ 0 11𝑱𝑱 = ⎢⎢ 41 0
⎢ 0 0
⎣ 0 0

3
29000

31
43
13
470375 ⎤⎥17⎥.
19⎥
7 ⎦The determinant of this judgement matrix is 337225.
Hence the formation transformation can be completed in
5 steps. However, solving this example using thealgorithm proposed in [6] will result in 6 steps incompleting the formation transformation. Again, weverified that the algorithm proposed in this paper is better
than the previous one. The assignment results are
summarized in Table 2.
Table 2 The assignment result of Example 2Fig. 1 Formations Example 1

219

Starting point(0, 4) (3, 4) (4, 1) (5, 2) (5, 3)

Target point
Distance(0, 5) (0, 4) (0, 0) (1, 1) (4, 4)
1
3
5
52

robot the target point so that the robot's formation can betransformed as required in the shortest time. The maindifference to the previous algorithms is the introduce ofthe judgement matrix and the singularity check of thismatrix. By comparing with the Monte Carlo method, thisalgorithm can ensure that the optimal task assignment
way could be obtained systematically.
References
1.

Fig. 3 Formations Example 22.

5. Comparison to Monte Carlo method3.

We conduct a series of comparisons between theproposed algorithm and the Monte Carlo method to verify
the superiority of this method. Matlab 2021 is used as theplatform for the comparisons. The simulation conditions
include formation transformation of 10, 30, 50, 100, 500,and 1000 robots on a grid plane. The staring points andthe target positions are all randomly generated for eachsimulation. Then we use the proposed algorithm to solve
the task assignment problem. We also use the Monte
Carlo method with the best one out of 10,000 trial foreach random data. Compared to the results obtained byboth method and find the better one. We have 1000
randomly generated data for each number of robots. Thismeans we have made 60,000 comparisons for different
cases. The assignment results via Monte Carlo method
could never be better than those via the proposed
algorithm. This means that the proposed algorithm isdefinitely better than Monte Carlo method for theformation transformation problem. The more important
point is that the computation time of the proposed method
is much smaller than that required by the Monte Carlomethod. The comparison results are summarized in Table
3.

4.
5.
6.

R. Burkard, M. Dell’Aamico and S. Martello, Assignment
Problems, Society for Industrial and Applied Mathematics,
2012.
M. Sniedovich, Dijkstra's algorithm revisited: the dynamic
programming connexion, Control and Cybernetics, 35(3),599-620, 2006.
F. Bourgeois and J. C. Lassalle, An extension of theMunkres Algorithm for the assignment problem torectangular matrices, Communications of the ACM,
14(12), 802-804, 1971.
H. W. Kuhn, The Hungarian method for the assignment
problem. Naval Research Logistics Quarterly 2, 83–97,1955.
N. Metropolis and S. Ulam, The Monte Carlo Method,
Journal of the American statistical association, 44(247),335-341, 1949.
K.H. Hsia, B.Y. Li and K.L. Su, Task Assignment andRoute Programming for Pattern Reformation on GridPlane, Journal of Robotics, Networking and Artificial Life,
2(4), pp.221-225, 2016.

Authors IntroductionDr. Kuo-Hsien Hsia

Table 3 Comparison-result summary
Dr. Chun-Chi Lai#- robots
103050100 500 1000
Count of the resultsby the newalgorithm not worse 1000 1000 1000 1000 1000 1000
than those by Monte
Carlo method

6. Conclusion
In this paper, we provide a new algorithm for solving
the formation transformation problem of multiple mobilerobots moving on a 2D grid plane. Each robot can only
move horizontally or vertically with the same speed. The
requirement is to complete the transformation in thefastest way. The proposed algorithm can be used tosystematically find out the best assignment way for each220

He received the Ph.D. degree inelectrical engineering from National
Sun Yat-Sen University, Taiwan. Heis currently an Associate Pofessor ofNational Yunlin University ofScience and Technology in Taiwan.
His research interests are in the areaof robotics, fuzzy systems, intelligent
control. He is a member of IEEE.
He received the Ph.D. degree inelectrical engineering from National
Chung Cheng University, Chiayi,Taiwan, in 2014. He is currently anAssistant Professor of National
Yunlin University of Science andTechnology in Taiwan. His researchinterests include multisensor fusion
and intelligent robotics.

Mr. Yu-Le Chen

He received his master's degree inelectrical engineering from National
Yunlin University of Science andTechnology, Taiwan in 2023. He iscurrently
a student in theGovernment AI Career Training
Institute, Taiwan.

221