Abstract
New market-based decentralized algorithms are proposed for the task assignment of multiple unmanned aerial vehicles in dynamic environments with a limited communication range. In particular, a cooperative timing mission that cannot be performed by a single vehicle is considered. The baseline algorithms for a connected network are extended to deal with time-varying network topology including isolated subnetworks due to a limited communication range. The mathematical convergence and scalability analyses show that the proposed algorithms have a polynomial time complexity, and numerical simulation results support the scalability of the proposed algorithm in terms of the runtime and communication burden. The performance of the proposed algorithms is demonstrated via Monte Carlo simulations for the scenario of the suppression of enemy air defenses.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Alighanbari, M.: Task assignment algorithms for teams of uavs in dynamic environments. Master’s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge MA (2004)
Alighanbari, M.: Robust and decentralized task assignment algorithms for uavs. Ph.D. dissertation, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge MA (2007)
Arslan, G., Marden, J.R., Shamma, J.S.: Autonomous vehicle-target assignment: A game-theoretical formulation. J. Dyn. Syst. Meas. Control. 129(5), 584–596 (2007)
Balmas, F.: Displaying dependence graphs: a hierarchical approach. J. Softw. Maint. Evol. Res. Pract. 16(3), 151–185 (2004)
Beard, R.W., McLain, T.W.: Multiple Uav Cooperative Search under Collision Avoidance and Limited Range Communication Constraints. In: Proceedings of the IEEE Conference on Decision and Control, pp. 25–30 (2003)
Bellingham, J., Tillerson, M., Richards, A., How, J.P.: Multi-Task Allocation and Path Planning for Cooperating Uavs. In: Conference on Coordination, Control and Optimization (2001)
Chandler, P.R.: Decentralized Control for an Autonomous Team. In: Proceedings of the AIAA 2Nd Unmanned Unlimited Conference (2003)
Choi, H., Kim, Y., Kim, H.: Genetic algorithm based decentralized task assignment for multiple uavs in dynamic environments. Int. J. Aeronaut. Space Sci. 12(2), 163–174 (2011)
Choi, H.L., Brunet, L., How, J.P.: Consensus-based decentralized auctions for robust task allocation. IEEE Trans. Robot. 25(4), 912–926 (2009)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to algorithms. MIT University Press, Cambridge (2001)
Das, G.P., McGinnity, T.M., Coleman, S.A.: Simultaneous allocations of multiple tightly-coupled multi-robot tasks to coalitions of heterogeneous robots. In: Proceedings of the IEEE International Conference on Robotics and Biomimetics (2014). doi:10.1109/ROBIO.2014.7090496
Das, G.P., McGinnity, T.M., Coleman, S.A., Behera, L.: A distributed task allocation algorithm for a multi-robot system in healthcare facilities. J. Intell. Robot. Syst. 80(1), 33–58 (2015)
Devadoss, S.L., O’Rourke, J.: Discrete and computational geometry. Princeton University Press, Princeton (2011)
Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: a survey and analysis. Proc. IEEE 94(7), 1257–1270 (2006)
Dijkstra, E.W.: Selected writings on computing: a personal perspective. Springer, New York (1982)
Edison, E., Shima, T.: Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Oper. Res. 38(1), 340–356 (2011)
George, J., Sujit, P., Sousa, J.: Coalition Formation with Communication Delays and Maneuvering Targets. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference (2010)
Gerkey, B.P., Matari, M.J.: Sold!: Auction methods for multirobot coordination. IEEE Trans. Robot. Autom. 18(5), 758–768 (2002)
Gerkey, B.P., Matarić, M.J.: A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res. 23(9), 939–954 (2004)
Gross, J.L., Yellen, J.: Handbook of Graph Theory. CRC press, Boca Raton FL (2003)
Haque, M., Egerstedt, M., Rahmani, A.: Multilevel coalition formation strategy for suppression of enemy air defenses missions. J. Aerospace Inform. Syst. 10(6), 287–296 (2013)
Johnson, L., Choi, H.L., How, J.P.: Hybrid Information and Plan Consensus in Distributed Task Allocation. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference (2013)
Karaman, S., Shima, T., Frazzoli, E.: A process algebra genetic algorithm. IEEE Trans. Evol. Comput. 16(4), 489–503 (2012)
Khamis, A.M., Elmogy, A.M., Karray, F.O.: Complex task allocation in mobile surveillance systems. J. Intell. Robot. Syst. 64(1), 33–55 (2011)
Manathara, J.G., Sujit, P., Beard, R.W.: Multiple uav coalitions for a search and prosecute mission. J. Intell. Robot. Syst. 62(1), 125–158 (2011)
Martin, J.M.: Deadlock avoidance in distributed service oriented architectures. Master’s thesis, School of Computer Science, University of Oklahoma, Norman OK (2010)
Maza, I., Kondak, K., Bernard, M., Ollero, A.: Multi-uav cooperation and control for load transportation and deployment. J. Intell. Robot. Syst. 57(1-4), 417–449 (2010)
McLain, T.: Coordinated control of unmanned air vehicles. Technical Report ASC-99-2426 Air Vehicles Directorate of the Air Force Research Laboratory (1999)
Oh, G., Kim, Y., Ahn, J., Choi, H.L.: Market-Based Task Assignment for Cooperative Timing Missions over Networks with Limited Connectivity. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference (2015)
Ponda, S.S., Johnson, L.B., Kopeikin, A.N., Choi, H.L., How, J.P.: Distributed planning strategies to ensure network connectivity for dynamic heterogeneous teams. IEEE J. Sel. Areas Commun. 30(5), 861–869 (2012)
Pujol-Gonzalez, M., Cerquides, J., Meseguer, P., Rodríguez-Aguilar, J., Tambe, M.: Engineering the decentralized coordination of uavs with limited communication range. In: Advances in Artificial Intelligence, vol. 8109, Lecture Notes in Computer Science, pp. 199–208. Springer, Berlin (2013). doi:10.1007/978-3-642-40643-0_21
Rawlings, J.O., Pantula, S.G., Dickey, D.A.: Applied regression analysis: a research tool. Springer, New York (1998)
Sandholm, T.W., Lesser, V.R.: Coalition Formation among Bounded Rational Agents. In: Proceedings of the International Joint Conference on Artificial Intelligence (1995)
Service, T.C., Adams, J.A.: Coalition formation for task allocation: Theory and algorithms. Auton. Agent. Multi-Agent Syst. 22(2), 225–248 (2011)
Shaferman, V., Shima, T.: Unmanned aerial vehicles cooperative tracking of moving ground target in urban environments. J. Guid. Control. Dyn. 31(5), 1360–1371 (2008)
Shaferman, V., Shima, T.: Task Assignment and Motion Planning for Multiple Uavs Tracking Multiple Targets in Urban Environments. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference. Chicago, IL (2009)
Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101(1), 165–200 (1998)
Shima, T., Schumacher, C.: Assigning cooperating uavs to simultaneous tasks on consecutive targets using genetic algorithms. J. Oper. Res. Soc. 60(7), 973–982 (2009)
Smith, R.G.: The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Trans. Comput. 29(12), 1104–1113 (1980)
Sujit, P., Beard, R.: Distributed Sequential Auctions for Multiple Uav Task Allocation. In: Proceedings of the IEEE American Control Conference, pp. 3955–3960 (2007)
Sujit, P., George, J., Beard, R.: Multiple Uav Coalition Formation. In: Proceedings of the IEEE American Control Conference, pp. 2010–2015 (2008)
Sujit, P., George, J., Beard, R.: Multiple Uav Task Allocation Using Particle Swarm Optimization. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference (2008)
Sujit, P., Manathara, J., Ghose, D., de Sousa, J.: Decentralized Multi-Uav Coalition Formation with Limited Communication Ranges. In: Handbook of Unmanned Aerial Vehicles, pp. 2021–2048. Springer, Berlin, Germany (2014)
Vig, L., Adams, J.A.: Coalition formation: From software agents to robots. J. Intell. Robot. Syst. 50(1), 85–118 (2007)
Weerdt, M.d., Zhang, Y., Klos, T.: Multiagent task allocation in social networks. Auton. Agent. Multi-Agent Syst. 25(1), 46–86 (2012)
Whitten, A.K., Choi, H.L., Johnson, L.B., How, J.P.: Decentralized Task Allocation with Coupled Constraints in Complex Missions. In: Proceedings of the IEEE American Control Conference, pp. 1642–1649 (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Oh, G., Kim, Y., Ahn, J. et al. Market-Based Task Assignment for Cooperative Timing Missions in Dynamic Environments. J Intell Robot Syst 87, 97–123 (2017). https://doi.org/10.1007/s10846-017-0493-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-017-0493-x