This paper presents a comparative study between optimization-based and market-based approaches used for solving the Multirobot task allocation (MRTA) problem that arises in the context of multirobot systems (MRS). The two proposed approaches are used to find the optimal allocation of a number of heterogeneous robots to a number of heterogeneous tasks. The two approaches were extensively tested over a number of test scenarios in order to test their capability of handling complex heavily constrained MRS applications that include extended number of tasks and robots. Finally, a comparative study is implemented between the two approaches and the results show that the optimization-based approach outperforms the market-based approach in terms of optimal allocation and computational time. 1. Introduction In the last few years, the field of research in mobile robotics has encountered a significant shift as the researchers in this field have recently started focusing on MRS rather than single-robot systems. This increased interest in the community of mobile robotics research towards MRS comes from the significant advantages and higher potential provided by MRS than single-robot systems. The advantages of a robot team are many; some examples of these advantages include, but are not limited to, resolving task complexity, increased system reliability, increased system performance, and finally easier and simpler design . One of the main areas of research in this field is the task allocation problem in MRS, where the mapping of robots to tasks is done in order to increase the overall performance of the system. The task allocation problem is a major issue in MRS as it focuses on the proper utilization of the available resource. In MRS, the available resources are the robots which are used to solve a problem or to perform a certain task. Thus, in order to increase the performance of the system, one must efficiently utilizes the available robots in order to solve the required tasks. Since the decision of which robot will do which task has a significant effect on the performance of the system, the allocation of the tasks to the proper robots strongly affects the performance of the system . The task allocation problem is proved to be one of the toughest problems especially when it comes to complex heterogeneous robot teams that are required to solve and execute complex problems and tasks. The heterogeneity of the robots simply indicates that the robot team consists of robots that have different features such as different capabilities and skills, different
Y. Han, D. Li, J. Chen, X. Yang, Y. Hu, and G. Zhang, “A multi-robots task allocation algorithm based on relevance and ability with group collaboration,” International Journal of Intelligent Engineering and Systems, vol. 3, no. 2, pp. 33–41, 2010.
A. Mosteo and L. Montano, “Simulated annealing for multi-robot hierarchical task allocation with minmax objective,” in Proceedings of the Workshop on Network Robot Systems: Toward Intelligent Robotic System Integrated with Environments (IROS '06), 2006.
Z. Jian, P. Zhihong, and L. Bo, “Multi-task allocation of ucavs considering time cost and hard time window constraints,” in Proceedings of the 31st Chinese Control Conference (CCC '12), pp. 2448–2452, 2012.
P. Oberlin, S. Rathinam, and S. Darbha, “Today's traveling salesman problem: heterogeneous, multiple depot, multiple UAV routing problem,” IEEE Robotics and Automation Magazine, vol. 17, no. 4, pp. 70–77, 2010.
S. Sariel-Talay, T. R. Balch, and N. Erdogan, “Multiple traveling robot problem: a solution based on dynamic task selection and robust execution,” IEEE/ASME Transactions on Mechatronics, vol. 14, no. 2, pp. 198–206, 2009.
M. A. Darrah, W. M. Niland, and B. M. Stolarik, “Multiple UAV dynamic task allocation using mixed integer linear programming in a SEAD mission,” in InfoTech at Aerospace: Advancing Contemporary Aerospace Technologies and Their Integration, pp. 2324–2334, American Institute of Aeronautics and Astronautics, 2005.
A. R. Mosteo and L. Montano, “Simulated annealing for multirobot hierarchical task allocation with flexible constraints and objective functions,” in Proceedings of the Workshop on Network Robot Systems: Toward Intelligent Robotic Systems Integrated with Environments (IROS '06), 2006.
D. Juedes, F. Drews, L. Welch, and D. Fleeman, “Heuristic resource allocation algorithms for maximizing allowable workload in dynamic, distributed real-time systems,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS '04), pp. 1631–1638, April 2004.
W. Kmiecik, M. Wojcikowski, L. Koszalka, and A. Kasprzak, “Task allocation in mesh connected processors with local search meta-heuristic algorithms,” in Intelligent Information and Database Systems, N. Nguyen, M. Le, and J. Swiatek, Eds., vol. 5991 of Lecture Notes in Computer Science, pp. 215–224, Springer, Berlin, Germany, 2010.
A. Stentz, M. B. Dias, R. Zlot, and N. Kalra, “Market-based approaches for coordination of multi-robot teams at different granularities of interaction,” in Proceedings of the 10th International Conference on Robotics and Remote Systems for Hazardous Environments, pp. 145–151, Robotics Institute, Carnegie Mellon University, March 2004.
T. Sandholm and V. Lesser, “Issues in automated negotiation and electronic commerce: extending the contract net framework,” in Proceedings of the 1st International Conference on Multi-Agent Systems (ICMAS '95), 1995.
A. Chavez, A. Moukas, and P. Maes, “Challenger: a multi-agent system for distributed resource allocation,” in Proceedings of the 1st International Conference on Autonomous Agents, pp. 323–331, February 1997.
H. Kose, U. Tatlidede, C. Mericli, K. Kaplan, and H. L. Akin, “Qlearning-based market-driven multi-agent collaboration in robot soccer,” in Proceedings of the Turkish Symposium on Artifcial Intelligence and Neural Networks, pp. 219–228, 2004.
T. Sandholm and S. Suri, “Improved algorithms for optimal winner determination in combinatorial auctions and generalizations,” in Proceedings of the 17th National Conference on Artificial Intelligence, pp. 90–97, 2000.
M. Golfarelli, D. Maio, and S. Rizzi, “A task-swap negotiation protocol based on the contract net paradigm,” Tech. Rep. 005-97, CSITE (Research Center for Informatics and Telecommunication Systems), 1997.