assignment problem and its method

Assignment Problem: Meaning, Methods and Variations | Operations Research

After reading this article you will learn about:- 1. Meaning of Assignment Problem 2. Definition of Assignment Problem 3. Mathematical Formulation 4. Hungarian Method 5. Variations.

Meaning of Assignment Problem:

An assignment problem is a particular case of transportation problem where the objective is to assign a number of resources to an equal number of activities so as to minimise total cost or maximize total profit of allocation.

The problem of assignment arises because available resources such as men, machines etc. have varying degrees of efficiency for performing different activities, therefore, cost, profit or loss of performing the different activities is different.

Thus, the problem is “How should the assignments be made so as to optimize the given objective”. Some of the problem where the assignment technique may be useful are assignment of workers to machines, salesman to different sales areas.

Definition of Assignment Problem:

ADVERTISEMENTS:

Suppose there are n jobs to be performed and n persons are available for doing these jobs. Assume that each person can do each job at a term, though with varying degree of efficiency, let c ij be the cost if the i-th person is assigned to the j-th job. The problem is to find an assignment (which job should be assigned to which person one on-one basis) So that the total cost of performing all jobs is minimum, problem of this kind are known as assignment problem.

The assignment problem can be stated in the form of n x n cost matrix C real members as given in the following table:

The Hungarian method is a computational optimization technique that addresses the assignment problem in polynomial time and foreshadows following primal-dual alternatives. In 1955, Harold Kuhn used the term “Hungarian method” to honour two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry. Let’s go through the steps of the Hungarian method with the help of a solved example.

Hungarian Method to Solve Assignment Problems

The Hungarian method is a simple way to solve assignment problems. Let us first discuss the assignment problems before moving on to learning the Hungarian method.

What is an Assignment Problem?

A transportation problem is a type of assignment problem. The goal is to allocate an equal amount of resources to the same number of activities. As a result, the overall cost of allocation is minimised or the total profit is maximised.

Because available resources such as workers, machines, and other resources have varying degrees of efficiency for executing different activities, and hence the cost, profit, or loss of conducting such activities varies.

Assume we have ‘n’ jobs to do on ‘m’ machines (i.e., one job to one machine). Our goal is to assign jobs to machines for the least amount of money possible (or maximum profit). Based on the notion that each machine can accomplish each task, but at variable levels of efficiency.

Hungarian Method Steps

Check to see if the number of rows and columns are equal; if they are, the assignment problem is considered to be balanced. Then go to step 1. If it is not balanced, it should be balanced before the algorithm is applied.

Step 1 – In the given cost matrix, subtract the least cost element of each row from all the entries in that row. Make sure that each row has at least one zero.

Step 2 – In the resultant cost matrix produced in step 1, subtract the least cost element in each column from all the components in that column, ensuring that each column contains at least one zero.

Step 3 – Assign zeros

• Analyse the rows one by one until you find a row with precisely one unmarked zero. Encircle this lonely unmarked zero and assign it a task. All other zeros in the column of this circular zero should be crossed out because they will not be used in any future assignments. Continue in this manner until you’ve gone through all of the rows.
• Examine the columns one by one until you find one with precisely one unmarked zero. Encircle this single unmarked zero and cross any other zero in its row to make an assignment to it. Continue until you’ve gone through all of the columns.

Step 4 – Perform the Optimal Test

• The present assignment is optimal if each row and column has exactly one encircled zero.
• The present assignment is not optimal if at least one row or column is missing an assignment (i.e., if at least one row or column is missing one encircled zero). Continue to step 5. Subtract the least cost element from all the entries in each column of the final cost matrix created in step 1 and ensure that each column has at least one zero.

Step 5 – Draw the least number of straight lines to cover all of the zeros as follows:

(a) Highlight the rows that aren’t assigned.

(b) Label the columns with zeros in marked rows (if they haven’t already been marked).

(c) Highlight the rows that have assignments in indicated columns (if they haven’t previously been marked).

(d) Continue with (b) and (c) until no further marking is needed.

(f) Simply draw the lines through all rows and columns that are not marked. If the number of these lines equals the order of the matrix, then the solution is optimal; otherwise, it is not.

Step 6 – Find the lowest cost factor that is not covered by the straight lines. Subtract this least-cost component from all the uncovered elements and add it to all the elements that are at the intersection of these straight lines, but leave the rest of the elements alone.

Step 7 – Continue with steps 1 – 6 until you’ve found the highest suitable assignment.

Hungarian Method Example

Use the Hungarian method to solve the given assignment problem stated in the table. The entries in the matrix represent each man’s processing time in hours.

\(\begin{array}{l}\begin{bmatrix} & I & II & III & IV & V \\1 & 20 & 15 & 18 & 20 & 25 \\2 & 18 & 20 & 12 & 14 & 15 \\3 & 21 & 23 & 25 & 27 & 25 \\4 & 17 & 18 & 21 & 23 & 20 \\5 & 18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

With 5 jobs and 5 men, the stated problem is balanced.

\(\begin{array}{l}A = \begin{bmatrix}20 & 15 & 18 & 20 & 25 \\18 & 20 & 12 & 14 & 15 \\21 & 23 & 25 & 27 & 25 \\17 & 18 & 21 & 23 & 20 \\18 & 18 & 16 & 19 & 20 \\\end{bmatrix}\end{array} \)

Subtract the lowest cost element in each row from all of the elements in the given cost matrix’s row. Make sure that each row has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 5 & 10 \\6 & 8 & 0 & 2 & 3 \\0 & 2 & 4 & 6 & 4 \\0 & 1 & 4 & 6 & 3 \\2 & 2 & 0 & 3 & 4 \\\end{bmatrix}\end{array} \)

Subtract the least cost element in each Column from all of the components in the given cost matrix’s Column. Check to see if each column has at least one zero.

\(\begin{array}{l}A = \begin{bmatrix}5 & 0 & 3 & 3 & 7 \\6 & 8 & 0 & 0 & 0 \\0 & 2 & 4 & 4 & 1 \\0 & 1 & 4 & 4 & 0 \\2 & 2 & 0 & 1 & 1 \\\end{bmatrix}\end{array} \)

When the zeros are assigned, we get the following:

The present assignment is optimal because each row and column contain precisely one encircled zero.

Where 1 to II, 2 to IV, 3 to I, 4 to V, and 5 to III are the best assignments.

Hence, z = 15 + 14 + 21 + 20 + 16 = 86 hours is the optimal time.

Practice Question on Hungarian Method

Use the Hungarian method to solve the following assignment problem shown in table. The matrix entries represent the time it takes for each job to be processed by each machine in hours.

\(\begin{array}{l}\begin{bmatrix}J/M & I & II & III & IV & V \\1 & 9 & 22 & 58 & 11 & 19 \\2 & 43 & 78 & 72 & 50 & 63 \\3 & 41 & 28 & 91 & 37 & 45 \\4 & 74 & 42 & 27 & 49 & 39 \\5 & 36 & 11 & 57 & 22 & 25 \\\end{bmatrix}\end{array} \)

Stay tuned to BYJU’S – The Learning App and download the app to explore all Maths-related topics.

Frequently Asked Questions on Hungarian Method

What is hungarian method.

The Hungarian method is defined as a combinatorial optimization technique that solves the assignment problems in polynomial time and foreshadowed subsequent primal–dual approaches.

What are the steps involved in Hungarian method?

The following is a quick overview of the Hungarian method: Step 1: Subtract the row minima. Step 2: Subtract the column minimums. Step 3: Use a limited number of lines to cover all zeros. Step 4: Add some more zeros to the equation.

What is the purpose of the Hungarian method?

When workers are assigned to certain activities based on cost, the Hungarian method is beneficial for identifying minimum costs.

Leave a Comment Cancel reply

Your Mobile number and Email id will not be published. Required fields are marked *

Request OTP on Voice Call

Post My Comment

Register with BYJU'S & Download Free PDFs

Register with byju's & watch live videos.

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Assignment problem

The problem of optimally assigning $ m $ individuals to $ m $ jobs. It can be formulated as a linear programming problem that is a special case of the transport problem :

maximize $ \sum _ {i,j } c _ {ij } x _ {ij } $

$$ \sum _ { j } x _ {ij } = a _ {i} , i = 1 \dots m $$

(origins or supply),

$$ \sum _ { i } x _ {ij } = b _ {j} , j = 1 \dots n $$

(destinations or demand), where $ x _ {ij } \geq 0 $ and $ \sum a _ {i} = \sum b _ {j} $, which is called the balance condition. The assignment problem arises when $ m = n $ and all $ a _ {i} $ and $ b _ {j} $ are $ 1 $.

If all $ a _ {i} $ and $ b _ {j} $ in the transposed problem are integers, then there is an optimal solution for which all $ x _ {ij } $ are integers (Dantzig's theorem on integral solutions of the transport problem).

In the assignment problem, for such a solution $ x _ {ij } $ is either zero or one; $ x _ {ij } = 1 $ means that person $ i $ is assigned to job $ j $; the weight $ c _ {ij } $ is the utility of person $ i $ assigned to job $ j $.

The special structure of the transport problem and the assignment problem makes it possible to use algorithms that are more efficient than the simplex method . Some of these use the Hungarian method (see, e.g., [a5] , [a1] , Chapt. 7), which is based on the König–Egervary theorem (see König theorem ), the method of potentials (see [a1] , [a2] ), the out-of-kilter algorithm (see, e.g., [a3] ) or the transportation simplex method.

In turn, the transportation problem is a special case of the network optimization problem.

A totally different assignment problem is the pole assignment problem in control theory.

• This page was last edited on 5 April 2020, at 18:48.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

• DSA Tutorial
• Data Structures
• Linked List
• Dynamic Programming
• Binary Tree
• Binary Search Tree
• Divide & Conquer
• Mathematical
• Backtracking
• Branch and Bound
• Pattern Searching

Job Assignment Problem using Branch And Bound

Let there be N workers and N jobs. Any worker can be assigned to perform any job, incurring some cost that may vary depending on the work-job assignment. It is required to perform all jobs by assigning exactly one worker to each job and exactly one job to each agent in such a way that the total cost of the assignment is minimized.

Let us explore all approaches for this problem.

Solution 1: Brute Force  

We generate n! possible job assignments and for each such assignment, we compute its total cost and return the less expensive assignment. Since the solution is a permutation of the n jobs, its complexity is O(n!).

Solution 2: Hungarian Algorithm  

The optimal assignment can be found using the Hungarian algorithm. The Hungarian algorithm has worst case run-time complexity of O(n^3).

Solution 3: DFS/BFS on state space tree  

A state space tree is a N-ary tree with property that any path from root to leaf node holds one of many solutions to given problem. We can perform depth-first search on state space tree and but successive moves can take us away from the goal rather than bringing closer. The search of state space tree follows leftmost path from the root regardless of initial state. An answer node may never be found in this approach. We can also perform a Breadth-first search on state space tree. But no matter what the initial state is, the algorithm attempts the same sequence of moves like DFS.

Solution 4: Finding Optimal Solution using Branch and Bound  

The selection rule for the next node in BFS and DFS is “blind”. i.e. the selection rule does not give any preference to a node that has a very good chance of getting the search to an answer node quickly. The search for an optimal solution can often be speeded by using an “intelligent” ranking function, also called an approximate cost function to avoid searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like search but with one major optimization. Instead of following FIFO order, we choose a live node with least cost. We may not get optimal solution by following node with least promising cost, but it will provide very good chance of getting the search to an answer node quickly.

There are two approaches to calculate the cost function:  

• For each worker, we choose job with minimum cost from list of unassigned jobs (take minimum entry from each row).
• For each job, we choose a worker with lowest cost for that job from list of unassigned workers (take minimum entry from each column).

In this article, the first approach is followed.

Let’s take below example and try to calculate promising cost when Job 2 is assigned to worker A. 

Since Job 2 is assigned to worker A (marked in green), cost becomes 2 and Job 2 and worker A becomes unavailable (marked in red). 

Now we assign job 3 to worker B as it has minimum cost from list of unassigned jobs. Cost becomes 2 + 3 = 5 and Job 3 and worker B also becomes unavailable. 

Finally, job 1 gets assigned to worker C as it has minimum cost among unassigned jobs and job 4 gets assigned to worker D as it is only Job left. Total cost becomes 2 + 3 + 5 + 4 = 14. 

Below diagram shows complete search space diagram showing optimal solution path in green. 

Complete Algorithm:  

Below is the implementation of the above approach:

Time Complexity: O(M*N). This is because the algorithm uses a double for loop to iterate through the M x N matrix.  Auxiliary Space: O(M+N). This is because it uses two arrays of size M and N to track the applicants and jobs.

Please Login to comment...

Similar reads.

• How to Get a Free SSL Certificate
• Best SSL Certificates Provider in India
• Elon Musk's xAI releases Grok-2 AI assistant
• What is OpenAI SearchGPT? How it works and How to Get it?
• Full Stack Developer Roadmap [2024 Updated]

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Index     Assignment problem     Hungarian algorithm     Solve online    

Solve an assignment problem online

Fill in the cost matrix of an assignment problem and click on 'Solve'. The optimal assignment will be determined and a step by step explanation of the hungarian algorithm will be given.

Fill in the cost matrix ( random cost matrix ):

Don't show the steps of the Hungarian algorithm Maximize the total cost

HungarianAlgorithm.com © 2013-2024

Quantitative Techniques: Theory and Problems by P. C. Tulsian, Vishal Pandey

Get full access to Quantitative Techniques: Theory and Problems and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

WHAT IS ASSIGNMENT PROBLEM

Assignment Problem is a special type of linear programming problem where the objective is to minimise the cost or time of completing a number of jobs by a number of persons.

The assignment problem in the general form can be stated as follows:

“Given n facilities, n jobs and the effectiveness of each facility for each job, the problem is to assign each facility to one and only one job in such a way that the measure of effectiveness is optimised (Maximised or Minimised).”

Several problems of management has a structure identical with the assignment problem.

Example I A manager has four persons (i.e. facilities) available for four separate jobs (i.e. jobs) and the cost of assigning (i.e. effectiveness) each job to each ...

Get Quantitative Techniques: Theory and Problems now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design components—and how they should interact.

It’s yours, free.

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platform—then explore all the other resources our members count on to build skills and solve problems every day.

Procedure, Example Solved Problem | Operations Research - Solution of assignment problems (Hungarian Method) | 12th Business Maths and Statistics : Chapter 10 : Operations Research

Chapter: 12th business maths and statistics : chapter 10 : operations research.

Solution of assignment problems (Hungarian Method)

First check whether the number of rows is equal to the numbers of columns, if it is so, the assignment problem is said to be balanced.

Step :1 Choose the least element in each row and subtract it from all the elements of that row.

Step :2 Choose the least element in each column and subtract it from all the elements of that column. Step 2 has to be performed from the table obtained in step 1.

Step:3 Check whether there is atleast one zero in each row and each column and make an assignment as follows.

Step :4 If each row and each column contains exactly one assignment, then the solution is optimal.

Example 10.7

Solve the following assignment problem. Cell values represent cost of assigning job A, B, C and D to the machines I, II, III and IV.

Here the number of rows and columns are equal.

∴ The given assignment problem is balanced. Now let us find the solution.

Step 1: Select a smallest element in each row and subtract this from all the elements in its row.

Look for atleast one zero in each row and each column.Otherwise go to step 2.

Step 2: Select the smallest element in each column and subtract this from all the elements in its column.

Since each row and column contains atleast one zero, assignments can be made.

Step 3 (Assignment):

Thus all the four assignments have been made. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost

Example 10.8

Consider the problem of assigning five jobs to five persons. The assignment costs are given as follows. Determine the optimum assignment schedule.

∴ The given assignment problem is balanced.

Now let us find the solution.

The cost matrix of the given assignment problem is

Column 3 contains no zero. Go to Step 2.

Thus all the five assignments have been made. The Optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ` 9

Example 10.9

Solve the following assignment problem.

Since the number of columns is less than the number of rows, given assignment problem is unbalanced one. To balance it , introduce a dummy column with all the entries zero. The revised assignment problem is

Here only 3 tasks can be assigned to 3 men.

Step 1: is not necessary, since each row contains zero entry. Go to Step 2.

Step 3 (Assignment) :

Since each row and each columncontains exactly one assignment,all the three men have been assigned a task. But task S is not assigned to any Man. The optimal assignment schedule and total cost is

The optimal assignment (minimum) cost = ₹ 35

Related Topics

Privacy Policy , Terms and Conditions , DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.

Formation construction and reconfiguration control of UAV swarms: a perspective from distributed assignment and optimization

• Original Paper
• Published: 26 August 2024

Cite this article

• Jiangyuan Tian   ORCID: orcid.org/0000-0002-4770-6524 1 ,
• Ruixuan Wei 2 &
• Longting Jiang 1  

This article proposes a framework for the swarm of unmanned aerial vehicles (UAVs) to swiftly construct a formation. The framework also enables the swarm to reconfigure the formation effectively in a distributed way when the number of UAVs changes. Different from the classic formation methods, we endow each UAV with an objective function and an assignment vector. Then, a novel distributed optimization protocol is designed for the formation construction, which enables the swarm to construct the desired formation within a prescribed time. The formation needs to be reconfigured when some UAVs leave or join the swarm. A distributed assignment protocol is raised for the reconfiguration problem, which aims at reassigning the relative positions for the UAVs and reconfiguring the swarm formation. This article integrates these two protocols into one framework, where the transition between the formation construction and its reconfiguration is smooth. The distributed design of the framework improves the individual UAV’s decision-making ability. We further give the proofs of consensus and optimality of the two protocols. The simulation results confirm the effectiveness of the framework.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Explore related subjects

• Automotive Engineering

Code Availability

The code during the current study are not publicly available but are available from the first author on reasonable request.

Data availability

The datas in this paper are availability under request.

Hayat, S., Yanmaz, E., Muzaffar, R.: Survey on unmanned aerial vehicle networks for civil applications: a communications viewpoint. IEEE Commun. Surv. Tutor. 18 (4), 2624–2661 (2016). https://doi.org/10.1109/COMST.2016.2560343

Article   Google Scholar  

Mozaffari, M., Saad, W., Bennis, M., Nam, Y.-H., Debbah, M.: A tutorial on UAVS for wireless networks: applications, challenges, and open problems. IEEE Commun. Surv. Tutor. 21 (3), 2334–2360 (2019). https://doi.org/10.1109/COMST.2019.2902862

Zhao, B., Xian, B., Zhang, Y., Zhang, X.: Nonlinear robust adaptive tracking control of a quadrotor UAV via immersion and invariance methodology. IEEE Trans. Ind. Electron. 62 (5), 2891–2902 (2015). https://doi.org/10.1109/TIE.2014.2364982

Wu, J., Luo, C., Luo, Y., Li, K.: Distributed UAV swarm formation and collision avoidance strategies over fixed and switching topologies. IEEE Trans. Cybern. 52 (10), 10969–10979 (2022). https://doi.org/10.1109/TCYB.2021.3132587

Shakhatreh, H., Sawalmeh, A.H., Al-Fuqaha, A., Dou, Z., Almaita, E., Khalil, I., Othman, N.S., Khreishah, A., Guizani, M.: Unmanned aerial vehicles (UAVS): a survey on civil applications and key research challenges. IEEE Access 7 , 48572–48634 (2019). https://doi.org/10.1109/ACCESS.2019.2909530

Iscold, P., Pereira, G.A.S., Torres, L.A.B.: Development of a hand-launched small UAV for ground reconnaissance. IEEE Trans. Aerosp. Electron. Syst. 46 (1), 335–348 (2010). https://doi.org/10.1109/TAES.2010.5417166

Wang, T., Li, M., Zhang, M.-Y.: Cooperative coverage reconnaissance of multi-UAV. In: 2020 IEEE 5th Information Technology and Mechatronics Engineering Conference (ITOEC), pp. 1647–1651. IEEE, Chongqing (2020). https://doi.org/10.1109/ITOEC49072.2020.9141873

Zhou, L., Leng, S., Liu, Q., Wang, Q.: Intelligent UAV swarm cooperation for multiple targets tracking. IEEE Internet Things J. 9 (1), 743–754 (2022). https://doi.org/10.1109/JIOT.2021.3085673

Wang, X., Zhou, W., Wang, X.: Research on multi-UAV cooperative tracking target based on PSO predictive control algorithm. IOP Conf. Ser. Mater. Sci. Eng. 646 (1), 012038 (2019). https://doi.org/10.1088/1757-899X/646/1/012038

Xu, Y., Ren, G., Chen, J., Zhang, X., Jia, L., Kong, L.: Interference-aware cooperative anti-jamming distributed channel selection in UAV communication networks. Appl. Sci. 8 (10), 1911 (2018). https://doi.org/10.3390/app8101911

Duan, H., Huo, M., Yang, Z., Shi, Y., Luo, Q.: Predator-prey pigeon-inspired optimization for UAV ALS longitudinal parameters tuning. IEEE Trans. Aerosp. Electron. Syst. 55 (5), 2347–2358 (2019). https://doi.org/10.1109/TAES.2018.2886612

Xing, D., Zhen, Z., Gong, H.: Offense-defense confrontation decision making for dynamic UAV swarm versus UAV swarm. Proc. Inst. Mech. Eng. Part G J. Aerosp. Eng. 233 (15), 5689–5702 (2019). https://doi.org/10.1177/0954410019853982

Liu, X., Ansari, N.: Resource allocation in UAV-assisted m2m communications for disaster rescue. IEEE Wirel. Commun. Lett. 8 (2), 580–583 (2019). https://doi.org/10.1109/LWC.2018.2880467

Ouyang, Q., Wu, Z., Cong, Y., Wang, Z.: Formation control of unmanned aerial vehicle swarms: a comprehensive review. Asian J. Control 25 (1), 570–593 (2023). https://doi.org/10.1002/asjc.2806

Kim, M.-H., Baik, H., Lee, S.: Response threshold model based UAV search planning and task allocation. J. Intell. Robot. Syst. 75 (3–4), 625–640 (2014). https://doi.org/10.1007/s10846-013-9887-6

Malvankar-Mehta, M.S., Mehta, S.S.: Optimal task allocation in multi-human multi-robot interaction. Optim. Lett. 9 (8), 1787–1803 (2015). https://doi.org/10.1007/s11590-015-0890-7

Article   MathSciNet   Google Scholar  

Zhang, X., Duan, H.: An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Appl. Soft Comput. 26 , 270–284 (2015). https://doi.org/10.1016/j.asoc.2014.09.046

Liang, X., Meng, G., Luo, H., Chen, X.: Dynamic path planning based on improved boundary value problem for unmanned aerial vehicle. Clust. Comput. 19 (4), 2087–2096 (2016). https://doi.org/10.1007/s10586-016-0650-1

Lau, S.Y., Naeem, W.: Co-operative tensegrity-based formation control algorithm for a multi-aircraft system. In: 2015 American Control Conference (ACC), pp. 750–756. IEEE, Chicago (2015). https://doi.org/10.1109/ACC.2015.7170824

Liao, F., Teo, R., Wang, J.L., Dong, X., Lin, F., Peng, K.: Distributed formation and reconfiguration control of VTOL UAVs. IEEE Trans. Control Syst. Technol. 25 (1), 270–277 (2017). https://doi.org/10.1109/TCST.2016.2547952

Dong, X., Yu, B., Shi, Z., Zhong, Y.: Time-varying formation control for unmanned aerial vehicles: theories and applications. IEEE Trans. Control Syst. Technol. 23 (1), 340–348 (2015). https://doi.org/10.1109/TCST.2014.2314460

Li, N.H.M., Liu, H.H.T.: Formation UAV flight control using virtual structure and motion synchronization. In: 2008 American Control Conference, pp. 1782–1787. IEEE, Seattle (2008). https://doi.org/10.1109/ACC.2008.4586750

Xu, J., Guo, Q., Xiao, L., Chen, G., Guan, X.: An autonomous planning method for UAV based on behavior-conditional model. In: 2019 IEEE 7th International Conference on Computer Science and Network Technology (ICCSNT), pp. 255–261. IEEE, Dalian (2019). https://doi.org/10.1109/ICCSNT47585.2019.8962520

Ge, X., Han, Q.-L.: Distributed formation control of networked multi-agent systems using a dynamic event-triggered communication mechanism. IEEE Trans. Ind. Electron. 64 (10), 8118–8127 (2017). https://doi.org/10.1109/TIE.2017.2701778

You, K., Xie, L.: Network topology and communication data rate for consensusability of discrete-time multi-agent systems. IEEE Trans. Autom. Control 56 (10), 2262–2275 (2011). https://doi.org/10.1109/TAC.2011.2164017

Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., Johansson, K.H.: A survey of distributed optimization. Annu. Rev. Control. 47 , 278–305 (2019). https://doi.org/10.1016/j.arcontrol.2019.05.006

Molzahn, D.K., Dorfler, F., Sandberg, H., Low, S.H., Chakrabarti, S., Baldick, R., Lavaei, J.: A survey of distributed optimization and control algorithms for electric power systems. IEEE Trans. Smart Grid 8 (6), 2941–2962 (2017). https://doi.org/10.1109/TSG.2017.2720471

Lin, Z., Liu, H.H.T.: Topology-based distributed optimization for multi-UAV cooperative wildfire monitoring: topology-based distributed optimization for multi-UAV cooperative wildfire monitoring. Opt. Control Appl. Methods 39 (4), 1530–1548 (2018). https://doi.org/10.1002/oca.2424

Rajasree, R., Jisha, V.R.: Optimal formation control of unmanned aerial vehicles with reconfiguration. In: 2015 International Conference on Control Communication & Computing India (ICCC), pp. 36–41. IEEE, Trivandrum (2015). https://doi.org/10.1109/ICCC.2015.7432866

Zhang, H., Zhao, G., Xu, G.: Time-optimal control for formation reconfiguration of multiple unmanned aerial vehicles. In: 2016 35th Chinese Control Conference (CCC), pp. 5630–5635. IEEE, Chengdu (2016). https://doi.org/10.1109/ChiCC.2016.7554234

Sperandio Giacomin, P.A., Hemerly, E.M.: Reconfiguration between longitudinal and circular formations for multi-UAV systems by using segments. J. Intell. Robot. Syst. 78 (2), 339–355 (2015). https://doi.org/10.1007/s10846-014-0063-4

Zhou, Y., Rao, B., Wang, W.: UAV swarm intelligence: recent advances and future trends. IEEE Access 8 , 183856–183878 (2020). https://doi.org/10.1109/ACCESS.2020.3028865

Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001). https://doi.org/10.1007/978-1-4613-0163-9

Book   Google Scholar  

Zhang, F.: Matrix Theory: Basic Results and Techniques. Springer, New York (2011). https://doi.org/10.1007/978-1-4614-1099-7

Li, T., Li, Y., Qian, Y.: Improved Hungarian algorithm for assignment problems of serial-parallel systems. J. Syst. Eng. Electron. 27 (4), 858–870 (2016). https://doi.org/10.21629/JSEE.2016.04.14

Ding, C., Shi, C., Chen, Y.: Nonsingular prescribed-time stabilization of a class of uncertain nonlinear systems: a novel coordinate mapping method. Int. J. Robust Nonlinear Control 30 (9), 3566–3581 (2020). https://doi.org/10.1002/rnc.4949

Download references

Acknowledgements

This work was supported in part by Science and Technology Innovation 2030-Key Project of “New Generation Artificial Intelligence” under grant 2018AAA0102403. National Natural Science Foundation of China underGrant 61573373.

Author information

Authors and affiliations.

Graduate College, Air Force Engineering University, Baqiao, Xi’an, 710038, Shaanxi, China

Jiangyuan Tian & Longting Jiang

Aeronautics Engineering College, Air Force Engineering University, Baqiao, Xi’an, 710038, Shaanxi, China

Ruixuan Wei

You can also search for this author in PubMed   Google Scholar

Contributions

All authors contributed to the study conception and design. The manuscript was written by Jiangyuan Tian. All authors read and approved the manuscript.

Corresponding author

Correspondence to Ruixuan Wei .

Ethics declarations

Conflict of interest.

The authors declare that they have no Conflict of interest.

Ethical standards

This manuscript is in compliance with ethical standards.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This appendix gives an extension of the simulation in the 3-dimensional scenario.

Although the result in the Fig.  16 illustrates that our method can make the UAVs track the mobile locating points and construct the formation within the prescribed time, the crossed trajectories in the 2-dimensional space still reflect that there is a latent risk of collisions between UAVs. In order to eliminate this risk, we extend the space to 3-dimension. The \(X-Y\) plane is for the formation mission and the introduction of the Z direction provides us with an additional dimension for collision avoidance between UAVs.

Trajectories of UAVs

Projection of UAVs

As is shown in the Fig.  17 , the locating points as well as the final formation are in the projection layer. The UAVs are initialized in different layers. Then the whole mission can be devided in 2 independent control problems: the control of the UAVs’ projections to construct the formation and the control of the Z coordinate to make the UAVs reach the projection layer. We have proposed our method for the first control problem in the previous article. Next we commence solving the second control problem.

Without causing any ambiguity, in this appendix we denote the Z coordinate of the i th UAV and the projection layer as \(z_i\) and \(z_d\) respectively. Then we propose a control protocol for the i th UAV to drive it to the projection layer:

Obviously, with the application of the protocol described in Eq. A1 , \(z_i\) will reach \(z_d\) as \(t\rightarrow \infty \) . Then we prove that the protocol described in Eq. A1 can also realize the collision avoidance between UAVs.

For \(\forall i,j\in \left\{ 1,2,\ldots ,n \right\} ,i\ne j\) , if \(z_i(0) > z_j(0)\) , then we have \(z_i(t) \ge z_j(t)\) for \(\forall t\ge 0\) and the equal sign is taken when \(t\rightarrow \infty \) .

Let \(F(t)=z_i(t)-z_j(t)\) . Take the derivative of F ( t ), we have:

Solve the differential equation A2 and take the initial condition into consideration, we have

It indicates that F ( t ) is a monotonic decreasing function and \(F(t) \ge 0\) for \(\forall t\ge 0\) . \(\square \)

The Theorem 3 implies that if the initial Z coordinate of the UAV i is greater than that of the UAV j , then during the whole formation process, the UAV i will be above the UAV j all the time until they both reach the projection layer in the end. We can realize the collision avoidance through guaranteeing that different UAVs will have different Z coordinates at the same time.

Trajectories of UAVs in 3-dimensional space

Then we give the simulation of the Sect.  4.3 in 3-dimensional space. All the simulation conditions, parameters and dynamic equations are the same as those in the Sect.  4.3 . The only difference is the Z coordinate needs to be added into the position information. The Z coordinate of the projection layer is set as 0. The initial Z coordinates of the 6 UAVs are set as 3, 2, \(-0.5\) , \(-1.5\) , \(-3\) , \(-3.5\) respectively. The simulation result is demonstrated in the Fig.  18 . From the result we can see that the trajectories of the UAVs don’t cross with each other. The Fig.  18 illustrates that with the addition of the Z direction and the application of the protocol described in Eq. A1 , the UAVs can construct the formation without the risk of collisions.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Tian, J., Wei, R. & Jiang, L. Formation construction and reconfiguration control of UAV swarms: a perspective from distributed assignment and optimization. Nonlinear Dyn (2024). https://doi.org/10.1007/s11071-024-10024-z

Download citation

Received : 25 June 2023

Accepted : 10 July 2024

Published : 26 August 2024

DOI : https://doi.org/10.1007/s11071-024-10024-z

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Unmanned aerial vehicle swarm
• Formation control
• Formation reconfiguration
• Distributed assignment
• Distributed optimization
• Find a journal
• Publish with us
• Track your research