Minimizing Communications in Decentralized Greedy Task Allocation
Keum-Seong Kim, Hoyeon Kim, Han‐Lim Choi · Journal of Aerospace Information Systems · 2019
No AccessTechnical NotesMinimizing Communications in Decentralized Greedy Task AllocationKeum-Seong Kim, Ho-Yeon Kim and Han-Lim ChoiKeum-Seong KimKorea Advanced Institute of Science and Technology, Daejeon 34141, Republic of Korea, Ho-Yeon KimKorea Advanced Institute of Science and Technology, Daejeon 34141, Republic of Korea and Han-Lim ChoiKorea Advanced Institute of Science and Technology, Daejeon 34141, Republic of KoreaPublished Online:24 Jun 2019https://doi.org/10.2514/1.I010624SectionsRead Now ToolsAdd to favoritesDownload citationTrack citations ShareShare onFacebookTwitterLinked InRedditEmail About References [1] Richards A., Bellingham J., Tillerson M. and How J., "Coordination and Control of Multiple UAVs," AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2002-4588, 2002. doi:https://doi.org/10.2514/6.2002-4588 LinkGoogle Scholar[2] Jin Y., Minai A. A. and Polycarpou M. M., "Cooperative Real-Time Search and Task Allocation in UAV Teams," IEEE Conference on Decision and Control, Vol. 1, IEEE Publ., Piscataway, NJ, 2003, pp. 7–12. doi:https://doi.org/10.1109/CDC.2003.1272527 Google Scholar[3] Bellingham J., Tillerson M., Richards A. and How J. P., "Multi-Task Allocation and Path Planning for Cooperating UAVs," Cooperative Control: Models, Applications and Algorithms, Springer, New York, 2003, pp. 23–41. doi:https://doi.org/10.1007/978-1-4757-3758-5_2 CrossrefGoogle Scholar[4] Xu L. and Ozguner U., "Battle Management for Unmanned Aerial Vehicles," IEEE Conference on Decision and Control, Vol. 4, IEEE Publ., Piscataway, NJ, 2003, pp. 3585–3590. doi:https://doi.org/10.1109/CDC.2003.1271704 Google Scholar[5] Turra D., Pollini L. and Innocenti M., "Fast Unmanned Vehicles Task Allocation with Moving Targets," IEEE Conference on Decision and Control, Vol. 4, IEEE Publ., Piscataway, NJ, 2004, pp. 4280–4285. doi:https://doi.org/10.1109/CDC.2004.1429424 Google Scholar[6] Andersson A., Tenhunen M. and Ygge F., "Integer Programming for Combinatorial Auction Winner Determination," International Conference on Multi Agent Systems, IEEE Publ., Piscataway, NJ, 2000, pp. 39–46. doi:https://doi.org/10.1109/ICMAS.2000.858429 Google Scholar[7] Darrah M. A., Niland W. M. and Stolarik B. M., "Multiple UAV Dynamic Task Allocation Using Mixed Integer Linear Programming in a SEAD Mission," AIAA [email protected] Conference, AIAA Paper 2005-7164, 2005. doi:https://doi.org/10.2514/6.2005-7164 LinkGoogle Scholar[8] Atay N. and Bayazit B., "Mixed-Integer Linear Programming Solution to Multi-Robot Task Allocation Problem," Washington Univ. in St. Louis TR WUCSE-2006-54, St. Louis, MO, 2006. doi:https://doi.org/10.7936/K7R49P04 Google Scholar[9] Dias M. B., Zlot R., Kalra N. and Stentz A., "Market-Based Multirobot Coordination: A Survey and Analysis," Proceedings of the IEEE, Vol. 94, No. 7, 2006, pp. 1257–1270. doi:https://doi.org/10.1109/JPROC.2006.876939 CrossrefGoogle Scholar[10] Sujit P. and Beard R., "Distributed Sequential Auctions for Multiple UAV Task Allocation," American Control Conference, IEEE Publ., Piscataway, NJ, 2007, pp. 3955–3960. doi:https://doi.org/10.1109/ACC.2007.4282558 Google Scholar[11] Oh G., Kim Y., Ahn J. and Choi H.-L., "Market-Based Distributed Task Assignment of Multiple Unmanned Aerial Vehicles for Cooperative Timing Mission," Journal of Aircraft, Vol. 54, No. 6, Nov. 2017, pp. 2298–2310. doi:https://doi.org/10.2514/1.C032984 LinkGoogle Scholar[12] Choi H.-L., Brunet L. and How J. P., "Consensus-Based Decentralized Auctions for Robust Task Allocation," IEEE Transactions on Robotics, Vol. 25, No. 4, 2009, pp. 912–926. doi:https://doi.org/10.1109/TRO.2009.2022423 CrossrefGoogle Scholar[13] Sujit P. and Ghose D., "Self Assessment-Based Decision Making for Multiagent Cooperative Search," IEEE Transactions on Automation Science and Engineering, Vol. 8, No. 4, 2011, pp. 705–719. CrossrefGoogle Scholar[14] Ponda S., Redding J., Choi H.-L., How J. P., Vavrina M. and Vian J., "Decentralized Planning for Complex Missions with Dynamic Communication Constraints," American Control Conference, IEEE Publ., Piscataway, NJ, 2010, pp. 3998–4003. doi:https://doi.org/10.1109/ACC.2010.5531232 Google Scholar[15] Johnson L. B., Ponda S., Choi H.-L. and How J. P., "Improving the Efficiency of a Decentralized Tasking Algorithm for UAV Teams with Asynchronous Communications," AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2010-8421, 2010. doi:https://doi.org/10.2514/6.2010-8421 LinkGoogle Scholar[16] Johnson L. B., Ponda S. S., Choi H.-L. and How J. P., "Asynchronous Decentralized Task Allocation for Dynamic Environments," AIAA [email protected] Aerospace Conference, AIAA Paper 2011-1441, 2011. doi:https://doi.org/10.2514/6.2011-1441 LinkGoogle Scholar[17] Choi H.-L., Whitten A. K. and How J. P., "Decentralized Task Allocation for Heterogeneous Teams with Cooperation Constraints," American Control Conference, IEEE Publ., Piscataway, NJ, 2010, pp. 3057–3062. doi:https://doi.org/10.1109/ACC.2010.5530496 Google Scholar[18] Whitten A. K., Choi H.-L., Johnson L. B. and How J. P., "Decentralized Task Allocation with Coupled Constraints in Complex Missions," American Control Conference, IEEE Publ., Piscataway, NJ, 2011, pp. 1642–1649. doi:https://doi.org/10.1109/ACC.2011.5990917 Google Scholar[19] Johnson L. B., Choi H.-L., Ponda S. S. and How J. P., "Decentralized Task Allocation Using Local Information Consistency Assumptions," Journal of Aerospace Information Systems, Vol. 14, No. 2, Feb. 2017, pp. 103–122. doi:https://doi.org/10.2514/1.I010461 LinkGoogle Scholar[20] Ponda S. S., Johnson L. B., Kopeikin A. N., Choi H.-L. and How J. P., "Distributed Planning Strategies to Ensure Network Connectivity for Dynamic Heterogeneous Teams," IEEE Journal on Selected Areas in Communications, Vol. 30, No. 5, 2012, pp. 861–869. doi:https://doi.org/10.1109/JSAC.2012.120603 CrossrefGoogle Scholar[21] Johnson L. B., Choi H.-L. and How J. P., "The Role of Information Assumptions in Decentralized Task Allocation," IEEE Control Systems Magazine, Vol. 36, No. 4, 2016, pp. 45–48. doi:https://doi.org/10.1109/MCS.2016.2558419 CrossrefGoogle Scholar[22] Johnson L. B., Choi H.-L. and How J. P., "Hybrid Information and Plan Consensus in Distributed Task Allocation," AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2013-4888, 2013. doi:https://doi.org/10.2514/6.2013-4888 Google Scholar[23] Johnson L. B., "Decentralized Task Allocation in Communication Contested Environments," Ph.D. Thesis, Massachusetts Inst. of Technology, Cambridge, MA, 2016, https://dspace.mit.edu/handle/1721.1/105606. Google Scholar Previous article FiguresReferencesRelatedDetailsCited byHeterogeneous UAV collaborative task assignment based on extended CBBA algorithmGreedy Target Assignment with Interference Constraints Between Defensive WeaponsDaniel Lee, Min Kyu Shin and Han-Lim Choi31 January 2022 | Journal of Aerospace Information Systems, Vol. 19, No. 4Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment16 June 2021 | The Journal of Supercomputing, Vol. 78, No. 2Communication-Aware Consensus-Based Decentralized Task Allocation in Communication Constrained EnvironmentsIEEE Access, Vol. 10Greedy Decentralized Auction-based Task Allocation for Multi-Agent SystemsIFAC-PapersOnLine, Vol. 54, No. 20A Bid-Based Grouping Method for Communication-Efficient Decentralized Multi-UAV Task Allocation23 August 2019 | International Journal of Aeronautical and Space Sciences, Vol. 21, No. 1 What's Popular Volume 16, Number 8August 2019 Metrics CrossmarkInformationCopyright © 2019 by the American Institute of Aeronautics and Astronautics, Inc. All rights reserved. All requests for copying and permission to reprint should be submitted to CCC at www.copyright.com; employ the eISSN 2327-3097 to initiate your request. See also AIAA Rights and Permissions www.aiaa.org/randp. TopicsComputational Fluid DynamicsFluid DynamicsMonte Carlo MethodNumerical AnalysisSpace Exploration and TechnologySpace Science and Technology KeywordsSpace CommunicationMonte Carlo SimulationUnmanned VehiclesData TransmissionAcknowledgmentsThis research was supported in part by Institute for Information and Communications Technology Planning and Evaluation (no. R1711055271) and in part by the Unmanned Vehicle Advanced Research Center through the National Research Foundation (no. 2016M1B3A1A02937510).PDF Received5 December 2017Accepted29 April 2019Published online24 June 2019