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 [1]. 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 [2]. 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
References
[1]
L. E. Parker, “Multiple mobile robot systems,” in Springer Handbook of Robotics, pp. 921–941, Springer, Berlin, Germany, 2008.
[2]
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.
[3]
B. Gerkey, On multi-robot task allocation [Ph.D. dissertation], Faculty of the Graduate School, University of Southern California, 2003.
[4]
T. Bektas, “The multiple traveling salesman problem: an overview of formulations and solution procedures,” Omega, vol. 34, no. 3, pp. 209–219, 2006.
[5]
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.
[6]
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.
[7]
R. M. Zlot, An auction-based approach to complex task allocation for multirobot teams [Ph.D. dissertation], Carnegie Mellon University, 2006.
[8]
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.
[9]
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.
[10]
R. Horst, P. Pardalos, and N. van Thoai, Introduction to Global Optimization, Nonconvex Optimization and Its Applications, Springer, Berlin, Germany, 1995.
[11]
N. Atay and B. Bayazit, “Mixed-integer linear programming solution to multi-robot task allocation problem,” Tech. Rep. WUCSE-2006-54, Washington University, St. Louis, Mo, USA, 2006.
[12]
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.
[13]
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.
[14]
A. R. Mosteo, Multi-robot task allocation for service robotics: from unlimited to limited communication range [Ph.D. dissertation], Universidad de Zaragoza, 2010.
[15]
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.
[16]
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.
[17]
P. J. Shea, K. Alexander, and J. Peterson, “Group tracking using genetic algorithms,” in Proceedings of the 6th International Conference of Information Fusion, 2003.
[18]
E. G. Jones, M. B. Dias, and A. Stentz, “Time-extended multi-robot coordination for domains with intra-path constraints,” Autonomous Robots, vol. 30, no. 1, pp. 41–56, 2011.
[19]
J. Wang, Y. Gu, and X. Li, “Multi-robot task allocation based on ant colony algorithm,” Journal of Computers, vol. 7, no. 9, pp. 2160–2167, 2012.
[20]
Y. Ding, Y. He, and J. Jiang, “Multi-robot cooperation method based on the ant algorithm,” in Proceedings of the IEEE Swarm Intelligence Symposium (SIS '03), pp. 14–18, 2003.
[21]
W.-H. Chen and C.-S. Lin, “A hybrid heuristic to solve a task allocation problem,” Computers and Operations Research, vol. 27, no. 3, pp. 287–303, 2000.
[22]
D. K. Liu and A. K. Kulatunga, “Simultaneous planning and scheduling for multi-autonomous vehicles,” in Evolutionary Scheduling, pp. 437–464, Springer, Berlin, Germany, 2007.
[23]
M. B. Dias, R. Zlot, N. Kalra, and A. Stentz, “Market-based multirobot coordination: a survey and analysis,” Proceedings of the IEEE, vol. 94, no. 7, pp. 1257–1270, 2006.
[24]
B. P. Gerkey and M. J. Matari？, “Sold!: auction methods for multirobot coordination,” IEEE Transactions on Robotics and Automation, vol. 18, no. 5, pp. 758–768, 2002.
[25]
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.
[26]
B. P. Gerkey and M. J. Mataric, “A market-based formulation of sensor-actuator network coordination,” in Proceedings of the AAAI Spring Symposium on Intelligent Embedded and Distributed Systems, 2002.
[27]
B. P. Gerkey and M. J. Matari？, “A formal analysis and taxonomy of task allocation in multi-robot systems,” International Journal of Robotics Research, vol. 23, no. 9, pp. 939–954, 2004.
[28]
G. Zlotkin and J. S. Rosenschein, “A domain theory for task oriented negotiation,” in Proceedings of the 13th International Joint Conference on Artificial Intelligence, 1993.
[29]
T. Sandholm, “An implementation of the contract net protocol based on marginal cost calculations,” in Proceedings of the 11th National Conference on Artificial Intelligence, pp. 256–262, July 1993.
[30]
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.
[31]
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.
[32]
M. P. Wellman and P. R. Wurman, “Market-aware agents for a multiagent world,” Robotics and Autonomous Systems, vol. 24, no. 3-4, pp. 115–125, 1998.
[33]
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.
[34]
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.
[35]
A. Elmogy, Market-based framework for mobile surveillance systems [Ph.D. dissertation], University of Waterloo, 2010.
[36]
A. M. Khamis, A. M. Elmogy, and F. O. Karray, “Complex task allocation in mobile surveillance systems,” Journal of Intelligent and Robotic Systems, vol. 64, no. 1, pp. 33–55, 2011.
[37]
M. B. Dias, A new paradigm for robust and efficient multirobot coordination in dynamic environments [Ph.D. dissertation], Robotics Institute, Carnegie Mellon University, 2004.
[38]
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.
[39]
R. G. Smith, “The contract net protocol: high-level communication and control in a distributed problem solver,” IEEE Transactions on Computers, vol. 29, no. 12, pp. 1104–1113, 1980.
[40]
A. Hussein, A market-based approach to multi-robot task allocation problem [M.S. thesis], German University in Cairo, New Cairo, Egypt, 2013.
