Hybrid Methodologies for Balanced Multi-Robot Task Allocation and Path Minimization

Balanced multi-robot task allocation involves scheduling of “K”number of robots to visit a set of “n” number of tasks so that each task is visited only once, while minimizing the total distance travelled by all the robots and to share the workload among the robots in terms of distance travelled. Finding the best allocation is strongly NP-hard. Allocating tasks to multi-robots in a balanced manner, such that all robots are used in n cost-effective manner is a tedious process. The current attempts made by the researchers concentrate on minimizing the distance between the robots and the tasks. Current scenario does not concentrate on sharing the task ami balance the distance between robots. This work attempts to develop a model for balanced multi-robot task allocation (BMRTA) and path minimization problem to use “K” robots in a cost-effective manner with n tasks. Two hybrid methodologies have been proposed. The first methodology combines saving matrix with TSP (onvlmll algorithm and the second one amalgamates angular method with TSP Convhull algorithm. The first pin t of both the method groups (assigns) selected numbers of task with the robot and the second part determined the shortest path of robot travel. Saving matrix based method tries to balance perfectly tasks allocated to the lobois whereas angular based method tries to minimize the total travel path length. A comparative study is pci I'm med for a set of benchmark data to evaluate the strengths and weaknesses of both the methods.