Abstract
This paper introduces an approach to solve the task assignment problem for a large number of tasks and robots in an efficient time. This method reduces the size of the state space explored by partitioning the tasks to the number of robotic agents. The proposed method is divided into three stages: first the tasks are partitioned to the number of robots, then robots are being assigned to the clusters optimally, and finally a task assignment algorithm is executed individually at each cluster. Two methods are adopted to solve the task assignment at each cluster, a genetic algorithm and an imitation learning algorithm. To verify the performance of the proposed approach, several numerical simulations are performed. Our empirical evaluation shows that clustering leads to great savings in runtime (up to a factor of 50), while maintaining the quality of the solution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wu, F., Zilberstein, S., Chen, X.: Online planning for multi-agent systems with bounded communication. Artif. Intell. 175(2), 487–511 (2011)
Avellar, G.S., Thums, G.D., Lima, R.R., Iscold, P., Torres, L. Pereira, G., et al.: On the development of a small hand-held multi-uav platform for surveillance and monitoring. In: 2013 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 405–412, IEEE (2013)
Iscold, P., Pereira, G.A., Torres, L.A.: Development of a hand-launched small uav for ground reconnaissance. IEEE Trans. Aerosp. Electron. Syst. 46(1), 335–348 (2010)
Burgard, W., Moors, M., Stachniss, C., Schneider, F.E.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21(3), 376–386 (2005)
Chandler, P.R., Pachter, M., Rasmussen, S., Schumacher, C.: Multiple task assignment for a uav team. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 4587 (2002)
Richards, A., Bellingham, J., Tillerson, M., How, J.: Coordination and control of multiple uavs. In: AIAA Guidance, Navigation, and Control Conference, Monterey, CA (2002)
Schumacher, C., Chandler, P., Pachter, M., Pachter, L.: Constrained optimization for uav task assignment. In: Proceedings of the AIAA Guidance, Navigation, and Control Conference, pp. 1–14. American Institute of Aeronautics and Astronautics Inc, Reston, VA, USA (2004)
Eun, Y., Bang, H.: Cooperative task assignment/path planning of multiple unmanned aerial vehicles using genetic algorithm. J. Aircraft 46(1), 338–343 (2009)
Shima, T., Rasmussen, S.J., Sparks, A.G., Passino, K.M.: Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Oper. Res. 33(11), 3252–3269 (2006)
Potvin, J.-Y.: Genetic algorithms for the traveling salesman problem. Ann. Oper. Res. 63(3), 337–370 (1996)
Cruz Jr, J.B., Chen, G., Li, D., Wang, X.: Particle swarm optimization for resource allocation in uav cooperative control. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 1–11, Providence, USA (2004)
MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297, Oakland, CA, USA (1967)
Rokach, L.: A survey of clustering algorithms. In: Data Mining and Knowledge Discovery Handbook, pp. 269–298. Springer (2010)
Burkard, R.E., Dell’Amico, M., Martello, S.: Assignment Problems. Revised Reprint, Siam (2009)
Kuhn, H.W.: The hungarian method for the assignment problem. Naval Res. Logist. Quart. 2(1–2), 83–97 (1955)
Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4), 325–340 (1987)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)
Goldberg, D.E., Lingle, R.: Alleles, loci, and the traveling salesman problem. In: Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pp. 154–159. Lawrence Erlbaum Associates, Publishers (1985)
Argall, B.D., Chernova, S., Veloso, M., Browning, B.: A survey of robot learning from demonstration. Robot. Auton. Syst. 57(5), 469–483 (2009)
Billard, A., Calinon, S., Dillmann, R., Schaal, S.: Robot programming by demonstration. In: Springer Handbook of Robotics, pp. 1371–1394. Springer (2008)
Duvallet, F., Stentz, A.: Imitation learning for task allocation. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3568–3573. IEEE (2010)
Ratliff, N.D., Silver, D., Bagnell, J.A.: Learning to search: Functional gradient techniques for imitation learning. Auton. Robots 27(1), 25–53 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing Switzerland
About this paper
Cite this paper
Janati, F., Abdollahi, F., Ghidary, S.S., Jannatifar, M., Baltes, J., Sadeghnejad, S. (2017). Multi-robot Task Allocation Using Clustering Method. In: Kim, JH., Karray, F., Jo, J., Sincak, P., Myung, H. (eds) Robot Intelligence Technology and Applications 4. Advances in Intelligent Systems and Computing, vol 447. Springer, Cham. https://doi.org/10.1007/978-3-319-31293-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-31293-4_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-31291-0
Online ISBN: 978-3-319-31293-4
eBook Packages: EngineeringEngineering (R0)