Towards a distributed solution to multi-robot task allocation problem with energetic and spatiotemporal constraints

• Autorzy: Zitouni Farouq , Harous Saad , Maamri Ramdane

Identyfikatory

DOI

10.7494/csci.2020.21.1.3427

• Języki publikacji: EN

Abstrakty

EN

This paper tackles the Multi-Robot Task Allocation problem. It consists of two distinct sets: a set of tasks (requiring resources), and a set of robots (offering resources). Then, the tasks are allocated to robots while optimizing a certain objective function subject to some constraints; e.g., allocating the maximum number of tasks, minimizing the distances traveled by the robots, etc. Previous works mainly optimized the temporal and spatial constraints, but no work focused on energetic constraints. Our main contribution is the introduction of energetic constraints on multi-robot task allocation problems. In addition, we propose an allocation method based on parallel distributed guided genetic algorithms and compare it to two state-of-the-art algorithms. The performed simulations and obtained results show the effectiveness and scalability of our solution, even in the case of a large number of robots and tasks. We believe that our contribution is applicable in many contemporary areas of research such as smart cities and related topics.

Słowa kluczowe

EN

multi-robot systems; multi-robot task allocation; energetic constraints; spatial constraints; temporal constraints; objective function; parallel distributed guided genetic algorithms

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2020
• Tom: T. 21 (1)
• Strony: 3--24
• Opis fizyczny: Bibliogr. 61 poz., rys., tab.

Twórcy

autor

Zitouni Farouq

• Kasdi Merbah University, Department of Computer Science, Ouargla, Abdelhamid Mehri University, LIRE Laboratory, Constantine, Algeria

autor

Harous Saad

• UAE University, Department of Computer Science and Software Engineering, Abu Dhabi, United Arab Emirates

autor

Maamri Ramdane

• Abelhamid Mehri University, Department of Computer Science, Constantine; Abdelhamid Mehri University, LIRE Laboratory, Constantine, Algeria

Bibliografia

• [1] Agarwal M., Kumar N., Vig L.: Non-additive multi-objective robot coalition for- mation. In: Expert Systems with Applications, vol. 41(8), pp. 3736-3747, 2014.
• [2] Alighanbari M., How J.P.: Decentralized task assignment for unmanned aerial vehicles. In: Proceedings of the 44th IEEE Conference on Decision and Control, pp. 5668-5673. IEEE, 2005.
• [3] Allen J.F.: Maintaining knowledge about temporal intervals. In: Readings in qualitative reasoning about physical systems, pp. 361-372. Elsevier, 1990.
• [4] Balas E., Simonetti N., Vazacopoulos A.: Job shop scheduling with setup times, deadlines and precedence constraints. In: Journal of Scheduling, vol. 11(4), pp. 253-262, 2008.
• [5] Bertsekas D.P.: The auction algorithm for assignment and other network ow problems: A tutorial. In: Interfaces, vol. 20(4), pp. 133-149, 1990.
• [6] Binetti G., Naso D., Turchiano B.: Decentralized task allocation for surveillance systems with critical tasks. In: Robotics and Autonomous Systems, vol. 61(12), pp. 1653-1664, 2013.
• [7] Brown E.C., Ragsdale C.T., Carter A.E.: A grouping genetic algorithm for the multiple traveling salesperson problem. In: International Journal of Information Technology & Decision Making, vol. 6(02), pp. 333-347, 2007.
• [8] Butt S.E., Cavalier T.M.: A heuristic for the multiple tour maximum collection problem. In: Computers & Operations Research, vol. 21(1), pp. 101-111, 1994.
• [9] Chen J., Sun D.: Coalition-based approach to task allocation of multiple robots with resource constraints. In: IEEE Transactions on Automation Science and Engineering, vol. 9(3), pp. 516-528, 2012.
• [10] Choi H.L., Brunet L., How J.P.: Consensus-based decentralized auctions for robust task allocation. In: IEEE transactions on robotics, vol. 25(4), pp. 912-926, 2009.
• [11] Choi H.L., Whitten A.K., How J.P.: Decentralized task allocation for heteroge- neous teams with cooperation constraints. In: Proceedings of the 2010 American Control Conference, pp. 3057-3062. IEEE, 2010.
• [12] Cord O., et al.: Genetic fuzzy systems: evolutionary tuning and learning of fuzzy knowledge bases, vol. 19. World Scientific, 2001.
• [13] Das G.P., McGinnity T.M., Coleman S.A., Behera L.: A fast distributed auction and consensus process using parallel task allocation and execution. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4716- 4721. IEEE, 2011.
• [14] Davis R.I., Burns A.: A survey of hard real-time scheduling for multiprocessor systems. In: ACM computing surveys (CSUR), vol. 43(4), p. 35, 2011.
• [15] Dechter R., Meiri I., Pearl J.: Temporal constraint networks. In: Artificial intelligence, vol. 49(1-3), pp. 61-95, 1991.
• [16] Dias M.B., Zlot R., Kalra N., Stentz A.: Market-based multirobot coordination: A survey and analysis. In: Proceedings of the IEEE, vol. 94(7), pp. 1257-1270, 2006.
• [17] Espina M.V., Grech R., De Jager D., Remagnino P., Iocchi L., Marchetti L., Nardi D., Monekosso D., Nicolescu M., King C.: Multi-robot teams for environmental monitoring. In: Innovations in Defence Support Systems{3, pp. 183-209. Springer, 2011.
• [18] Fakcharoenphol J., Harrelson C., Rao S.: The k-traveling repairmen problem. In: ACM Transactions on Algorithms (TALG), vol. 3(4), p. 40, 2007.
• [19] Gerkey B.P., Mataric M.J.: A formal analysis and taxonomy of task allocation in multi-robot systems. In: The International Journal of Robotics Research, vol. 23(9), pp. 939-954, 2004.
• [20] Huang L., Ding Y., Zhou M., Jin Y., Hao K.: Multiple-Solution Optimization Strategy for Multirobot Task Allocation. In: IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018.
• [21] Johnson L., Ponda S., Choi H.L., How J.: Asynchronous decentralized task allocation for dynamic environments. In: Infotech@ Aerospace 2011, p. 1441. 2011.
• [22] Junjie P., Dingwei W.: An ant colony optimization algorithm for multiple travelling salesman problem. In: First International Conference on Innovative Computing, Information and Control-Volume I (ICICIC'06), vol. 1, pp. 210-213. IEEE, 2006.
• [23] Khamis A., Hussein A., Elmogy A.: Multi-robot task allocation: A review of the state-of-the-art. In: Cooperative Robots and Sensor Networks 2015, pp. 31-51. Springer, 2015.
• [24] Kivelevitch E., Cohen K., Kumar M.: A market-based solution to the multiple traveling salesmen problem. In: Journal of Intelligent & Robotic Systems, vol. 72(1), pp. 21-40, 2013.
• [25] Koenig S., Keskinocak P., Tovey C.: Progress on agent coordination with cooperative auctions. In: Twenty-fourth aaai conference on artificial intelligence. 2010.
• [26] Korsah G.A., Stentz A., Dias M.B.: A comprehensive taxonomy for multi-robot task allocation. In: The International Journal of Robotics Research, vol. 32(12), pp. 1495-1512, 2013.
• [27] Kwasnica A.M., Ledyard J.O., Porter D.P., DeMartini C.: A new and improved design for multi-object iterative auctions. In: Handbook of Spectrum Auction Design, pp. 391-417. Cambridge University Press, 2017.
• [28] Lagoudakis M.G., Markakis E., Kempe D., Keskinocak P., Kleywegt A.J., Koenig S., Tovey C.A., Meyerson A., Jain S.: Auction-Based Multi-Robot Routing. In: Robotics: Science and Systems, vol. 5, pp. 343-350. Rome, Italy, 2005.
• [29] Lee D.H.: Resource-based task allocation for multi-robot systems. In: Robotics and Autonomous Systems, vol. 103, pp. 151-161, 2018.
• [30] Lerman K., Jones C., Galstyan A., Mataric M.J.: Analysis of dynamic task allocation in multi-robot systems. In: The International Journal of Robotics Research, vol. 25(3), pp. 225-241, 2006.
• [31] Liao Y.L., Su K.L.: Multi-robot-based intelligent security system. In: Artificial Life and Robotics, vol. 16(2), p. 137, 2011.
• [32] Lin S.W., Vincent F.Y.: A simulated annealing heuristic for the team orienteering problem with time windows. In: European Journal of Operational Research, vol. 217(1), pp. 94-107, 2012.
• [33] Lozenguez G., Adouane L., Beynier A., Mouaddib A.I., Martinet P.: Map partitioning to approximate an exploration strategy in mobile robotics. In: Multiagent and Grid Systems, vol. 8(3), pp. 275-288, 2012.
• [34] Luo Z., Qin H., Lim A.: Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. In: European Journal of Operational Research, vol. 234(1), pp. 49-60, 2014.
• [35] Marino A., Parker L.E., Antonelli G., Caccavale F.: A decentralized architecture for multi-robot systems based on the null-space-behavioral control with application to multi-robot border patrolling. In: Journal of Intelligent & Robotic Systems, vol. 71(3-4), pp. 423-444, 2013.
• [36] Mosteo A.R., Montano L.: A survey of multi-robot task allocation. In: Instituto de Investigacion en Ingeniera de Aragon, University of Zaragoza, Zaragoza, Spain, Technical Report No. AMI-009-10-TEC, 2010.
• [37] Nagatani K., Okada Y., Tokunaga N., Kiribayashi S., Yoshida K., Ohno K., Takeuchi E., Tadokoro S., Akiyama H., Noda I., et al.: Multirobot exploration for search and rescue missions: A report on map building in RoboCupRescue 2009. In: Journal of Field Robotics, vol. 28(3), pp. 373-387, 2011.
• [38] Nanjanath M., Gini M.: Repeated auctions for robust task execution by a robot team. In: Robotics and Autonomous Systems, vol. 58(7), pp. 900-909, 2010.
• [39] Nguyen S., Zhang M., Johnston M., Tan K.C.: Automatic programming via iterated local search for dynamic job shop scheduling. In: IEEE transactions on cybernetics, vol. 45(1), pp. 1-14, 2014.
• [40] Nunes E., Gini M.: Multi-robot auctions for allocation of tasks with temporal constraints. In: Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.
• [41] Nunes E., Manner M., Mitiche H., Gini M.: A taxonomy for task allocation problems with temporal and ordering constraints. In: Robotics and Autonomous Systems, vol. 90, pp. 55-70, 2017.
• [42] Oliver G., Guerrero J.: Auction and swarm multi-robot task allocation algorithms in real time scenarios. In: Multi-Robot Systems, Trends and Development. IntechOpen, 2011.
• [43] Parker L.E., Tang F.: Building multirobot coalitions through automated task solution synthesis. In: Proceedings of the IEEE, vol. 94(7), pp. 1289-1305, 2006.
• [44] Sariel S., Balch T.: Real time auction based allocation of tasks for multi-robot exploration problem in dynamic environments. In: Proceedings of the AAAI-05 Workshop on Integrating Planning into Scheduling, pp. 27-33. AAAI Palo Alto, CA, 2005.
• [45] Shiomi M., Kamei K., Kondo T., Miyashita T., Hagita N.: Robotic service coordination for elderly people and caregivers with ubiquitous network robot platform. In: 2013 IEEE Workshop on Advanced Robotics and its Social Impacts, pp. 57-62. IEEE, 2013.
• [46] Shkurti F., Xu A., Meghjani M., Higuera J.C.G., Girdhar Y., Giguere P., Dey B.B., Li J., Kalmbach A., Prahacs C., et al.: Multi-domain monitoring of marine environments using a heterogeneous robot team. In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1747-1753. IEEE, 2012.
• [47] Siddique N., Adeli H.: Computational intelligence: synergies of fuzzy logic, neural networks and evolutionary computing. John Wiley & Sons, 2013.
• [48] Tahbaz-Salehi A., Jadbabaie A.: On consensus over random networks. In: 44th Annual Allerton Conference. Citeseer, 2006.
• [49] Tang F., Parker L.E.: A complete methodology for generating multi-robot task solutions using ASyMTRe-D and market-based task allocation. In: Proceedings 2007 IEEE International Conference on Robotics and Automation, pp. 3351-3358. IEEE, 2007.
• [50] Tang H., Miller-Hooks E.: A tabu search heuristic for the team orienteering problem. In: Computers & Operations Research, vol. 32(6), pp. 1379-1407, 2005.
• [51] Venkatesh P., Singh A.: Two metaheuristic approaches for the multiple traveling salesperson problem. In: Applied Soft Computing, vol. 26, pp. 74-89, 2015.
• [52] Wang Y., Chen Y., Lin Y.: Memetic algorithm based on sequential variable neighborhood descent for the minmax multiple traveling salesman problem. In: Computers & Industrial Engineering, vol. 106, pp. 105-122, 2017.
• [53] Wei C., Hindriks K.V., Jonker C.M.: Dynamic task allocation for multi-robot search and retrieval tasks. In: Applied Intelligence, vol. 45(2), pp. 383-401, 2016.
• [54] Yan Z., Jouandeau N., Cherif A.A.: A survey and analysis of multi-robot coordination. In: International Journal of Advanced Robotic Systems, vol. 10(12), p. 399, 2013.
• [55] Zaman S., Grosu D.: A combinatorial auction-based mechanism for dynamic VM provisioning and allocation in clouds. In: IEEE Transactions on Cloud Computing, vol. 1(2), pp. 129-141, 2013.
• [56] Zhang K., Collins Jr E.G., Shi D.: Centralized and distributed task allocation in multi-robot teams via a stochastic clustering auction. In: ACM Transactions on Autonomous and Adaptive Systems (TAAS), vol. 7(2), p. 21, 2012.
• [57] Zhang S., Wang S.: Flexible Assembly Job-Shop Scheduling With Sequence- Dependent Setup Times and Part Sharing in a Dynamic Environment: Constraint Programming Model, Mixed-Integer Programming Model, and Dispatching Rules. In: IEEE Transactions on Engineering Management, vol. 65(3), pp. 487-504, 2018.
• [58] Zhao W., Meng Q., Chung P.W.: A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario. In: IEEE transactions on cybernetics, vol. 46(4), pp. 902-915, 2015.
• [59] Zitouni F., Maamri R.: Cooperative learning-agents for task allocation problem. In: Interactive Mobile Communication, Technologies and Learning, pp. 952-968. Springer, 2017.
• [60] Zitouni F., Maamri R.: FA-SETPOWER-MRTA: A Solution for Solving the Multi-Robot Task Allocation Problem. In: IFIP International Conference on Computational Intelligence and Its Applications, pp. 317-328. Springer, 2018.
• [61] Zitouni F., Maamri R., Harous S.: FA-QABC-MRTA: a solution for solving the multi-robot task allocation problem. In: Intelligent Service Robotics, pp. 1-12, 2019.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).