Towards a Distributed Solution to the Multi-Robot Task Allocation Problem with Energetic and Spatiotemporal Constraints

Farouq Zitouni, Saad Harous, Ramdane Maamri

Abstract


The multi-robot task allocation problem consists of two distinct sets: a set of tasks (requiring resources) and a set of robots (offering resources); then tasks are allocated to robots; while optimizing a certain objective function, subject to some constraints: e.g. allocate the maximum number of tasks, minimize the distances travelled by robots, etc. In this paper, we propose some objective functions, and 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. Performed simulations and obtained results show the effectiveness and scalability of our solution, even with a large number of robots and tasks.

Keywords


Multi-Robot Systems; Multi-Robot Task Allocation; Energetic Constraints; Spatial Constraints; Temporal Constraints; Objective Function; Parallel Distributed Guided Genetic Algorithms

Full Text:

PDF

References


Agarwal M., Kumar N., Vig L.: Non-additive multi-objective robot coalition formation. In: Expert Systems with Applications, vol. 41(8), pp. 3736-3747, 2014.

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.

Allen J.F.: Maintaining knowledge about temporal intervals. In: Readings in qualitative reasoning about physical systems, pp. 361-372. Elsevier, 1990.

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.

Bertsekas D.P.: The auction algorithm for assignment and other network flow problems: A tutorial. In: Interfaces, vol. 20(4), pp. 133-149, 1990.

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.

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.

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.

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.

Choi H.L., Whitten A.K., How J.P.: Decentralized task allocation for heterogeneous teams with cooperation constraints. In: Proceedings of the 2010 American Control Conference, pp. 3057-3062. IEEE, 2010.

Cord O., et al.: Genetic fuzzy systems: evolutionary tuning and learning of fuzzy knowledge bases, vol. 19. World Scientific, 2001.

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.

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.

Dechter R., Meiri I., Pearl J.: Temporal constraint networks. In: Artificial intelligence, vol. 49(1-3), pp. 61-95, 1991.

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.

Fakcharoenphol J., Harrelson C., Rao S.: The k-traveling repairmen problem. In: ACM Transactions on Algorithms (TALG), vol. 3(4), p. 40, 2007.

Gerkey B.P., Matari´c 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.

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.

Johnson L., Ponda S., Choi H.L., How J.: Asynchronous decentralized task allocation for dynamic environments. In: Infotech@ Aerospace 2011, p. 1441. 2011.

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.

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.

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.

Koenig S., Keskinocak P., Tovey C.: Progress on agent coordination with cooperative auctions. In: Twenty-fourth aaai conference on artificial intelligence. 2010.

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.

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.

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.

Lee D.H.: Resource-based task allocation for multi-robot systems. In: Robotics and Autonomous Systems, vol. 103, pp. 151-161, 2018.

Lerman K., Jones C., Galstyan A., Matari´c 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.

Liao Y.L., Su K.L.: Multi-robot-based intelligent security system. In: Artificial Life and Robotics, vol. 16(2), p. 137, 2011.

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.

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.

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.

Mosteo A.R., Montano L.: A survey of multi-robot task allocation. In: Instituto de Investigaci´on en Ingenierıa de Arag´on, University of Zaragoza, Zaragoza, Spain, Technical Report No. AMI-009-10-TEC, 2010.

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.

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.

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.

Nunes E., Gini M.: Multi-robot auctions for allocation of tasks with temporal constraints. In: Twenty-Ninth AAAI Conference on Artificial Intelligence. 2015.

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.

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.

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.

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.

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.

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.

Siddique N., Adeli H.: Computational intelligence: synergies of fuzzy logic, neural networks and evolutionary computing. John Wiley & Sons, 2013.

Tahbaz-Salehi A., Jadbabaie A.: On consensus over random networks. In: 44th Annual Allerton Conference. Citeseer, 2006.

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.

Venkatesh P., Singh A.: Two metaheuristic approaches for the multiple traveling salesperson problem. In: Applied Soft Computing, vol. 26, pp. 74-89, 2015.

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.

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.

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.

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.

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.

Zhang S., Wang S.: Flexible Assembly Job-Shop Scheduling With SequenceDependent 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.

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.

Zitouni F., Maamri R.: Cooperative learning-agents for task allocation problem. In: Interactive Mobile Communication, Technologies and Learning, pp. 952-968. Springer, 2017.

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.




DOI: https://doi.org/10.7494/csci.2020.21.1.3427

Refbacks

  • There are currently no refbacks.