Performance analysis of clustering methods for balanced multi-robot task allocations

Abstract

This paper models the Multi-Robot Task Allocation (MRTA) problem with a balance constraint to improve the utilisation (completion time) of the robots. Our balancing constraint attempts to minimise the travel distance difference among the robots as well as allocates an equal set of tasks to these robots. The clustering-based approach is employed to solve the Balanced Multi-Robot Task Allocation (BMRTA) problem for two principal reasons. That is, this approach clusters given tasks into groups using various clustering techniques for each robot and sequences the route for each robot using the travelling salesman problem (TSP) conhull algorithm. This work analyses the suitability and performance of the clustering techniques with respect to the balancing criteria using a benchmark dataset. Our findings suggest that K-means clustering is the most suitable for the solving BMRTA problem with complex topologies and it is scalable to deal with any number of tasks and robots compared with Gaussian Mixtures Models (GMM) and hierarchical clustering methods.

KEYWORDS:

• Balanced multi-robot task allocation problem
• clustering
• multiple travelling salesperson problem
• heuristics approach
• conhull algorithm

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Elango Murugappan

Elango Murugappan is Assistant Professor in the Department of Mechanical Engineering at Thiagarajar College of Engineering, Madurai, Tamil Nadu, India. He received his bachelor’s degree in Mechanical Engineering from Madurai Kamaraj University. He received his Master’s in Computer Aided Design from Anna University. He received his Ph.D. for his thesis Methods for Multi robot task allocation from Anna University, Tamil Nadu, Tamil Nadu in 2012. He has more than 20 years of teaching and research experience. He has published more than 18 research papers and has applied for 4 patents. He is reviewer for International Journal of Applied Energy, Neural Computing and Applications, and Expert Systems with Applications. His research interests include Multi robot Coordination, Composite materials and vibrations.

Nachiappan Subramanian

Nachiappan Subramanian (Nachi) is Professor of Operations and Logistics Management & Supply Chains at the University of Sussex UK. Nachi has 22 years of teaching experience in the UK, China, Australia and India. Nachi has published 106 peer reviewed journal articles in technology interventions in supply chain, sustainable supply chains and risk and resilience. He is Senior Associate Editor of the International Journal of Physical Distribution and Logistics Management and the Associate Editor for the International Journal of Logistics Management. He is Fellow of Chartered Institute of Logistics and Transport UK and a Senior Fellow of Higher Education Academy, UK. Nachi authored a book on the title ‘Blockchain and Supply Chain Logistics: Evolutionary Case Studies (ISBN 9783030475307)’ along with Chaudhri A, Kayıkcı Y published by Palgrave McMillan.

Shams Rahman

Shams Rahman is Professor of Supply Chain Management at RMIT University, Australia. Professor Rahman, a former British Commonwealth scholar, has worked with several universities in Australia, UK and Thailand. He is Associate Editor of International Journal of Information Systems and Supply Chain Management and a member of the editorial board of 16 international journals. Professor Rahman has published over 240 research papers which include articles in international journals, book chapters and referred papers in international conference proceedings. His current research interests focus on supply chain sustainability strategy, circular economy and reverse supply chain, disruptive technology and sustainability, and talent management in supply chain and logistics industry.

Mark Goh

Mark Goh holds a PhD from the University of Adelaide. In the National University of Singapore, he serves as Professor in the NUS Business School and holds the appointments of Director (Industry Research) at the Logistics Institute-Asia Pacific. His current research interests focus on supply chain strategy, performance measurement, buyer–seller relationships and sustainable logistics. He has published close to 250 journal articles.

Hing Kai Chan

Hing Kai Chan is Professor of Operations Management at the Nottingham University Business School China, the University of Nottingham Ningbo China. He has published close to 150 academic articles and (co-)edited several special issues for reputable international journals. His publications appear in Production and Operations Management, the European Journal of Operational Research, various IEEE Transactions, International of Production Research, Decision Support Systems, among others. Professor Chan has been a Co-Editor of Industrial Management and Data Systems and an Associate Editor of Transportation Research Part E: Logistics and Transportation Review since 2014 and 2018 respectively.