An Approximation Algorithm for a Task Allocation, Sequencing and Scheduling Problem Involving a Human Robot Team
This article presents an approximation algorithm for a Task Allocation, Sequencing and Scheduling Problem (TASSP) involving a team of human operators and robots. The robots have to travel to a given set of targets and collaboratively work on the tasks at the targets with the human operators. The problem aims to find a sequence of targets for each robot to visit and schedule the tasks at the targets with the human operators such that each target is visited exactly once by some robot, the scheduling constraints are satisfied and the maximum mission time of any robot is minimum. This problem is a generalization of the single Traveling Salesman Problem and is NP Hard. Given <inline formula><tex math notation="LaTeX"$k$/tex math>/inline formula> robots and <inline formula><tex math notation="LaTeX"$m$/tex math>/inline formula> human operators, an algorithm is developed for solving the TASSP with an approximation ratio equal to <inline formula><tex math notation="LaTeX"\frac{5}{2} \frac{1}{k}/tex math>/inline formula> when <inline formula><tex math notation="LaTeX"$m\geq k$/tex math>/inline formula> and equal to <inline formula><tex math notation="LaTeX"\frac{7}{2} \frac{1}{k}/tex math>/inline formula> otherwise. Computational results are also presented to corroborate the performance of the proposed algorithm.
IEEE Robotics and Automation Letters