An Approximation Algorithm for a Task Allocation, Sequencing and Scheduling Problem Involving a Human-Robot Team
Sai Krishna Kanth Hari, Abhishek Nayak, Sivakumar Rathinam
Abstract
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 k robots and m human operators, an algorithm is developed for solving the TASSP with an approximation ratio equal to 5/2- 1/k when m ≥ k and equal to 7/2 -1/k otherwise. Computational results are also presented to corroborate the performance of the proposed algorithm.
BibTeX
@inproceedings{ral2020_anapproximationa,
title = {An Approximation Algorithm for a Task Allocation, Sequencing and Scheduling Problem Involving a Human-Robot Team},
author = {Sai Krishna Kanth Hari and Abhishek Nayak and Sivakumar Rathinam},
booktitle = {RA-L 2020},
year = {2020}
}