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 a 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 lank and 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 Convhull algorithm and the second one amalgamates angular method with TSP Convhull algorithm. The first part 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 robots whereas angular based method tries to minimize the total travel path length. A comparative study is performed for a set of benchmark data to evaluate the strengths and weaknesses of both the methods.