An Approximation Algorithm for a Task Allocation, Sequencing and Scheduling Problem involving a Human-Robot Team
This provides an incremental algorithmic solution for optimizing coordination in human-robot teams, relevant to robotics and operations research.
The paper tackles a task allocation, sequencing, and scheduling problem for human-robot teams by developing an approximation algorithm with performance guarantees expressed as ratios dependent on the number of humans and robots, achieving specific bounds like 7/2 - 5/(2k) for one human.
This article presents an approximation algorithm for a task allocation, sequencing and scheduling problem involving a team of human operators and robots. Specifically, we present an algorithm with an approximation ratio as a function of the number of human operators ($m$) and the number of robots ($k$) in the team. The approximation ratios are $\frac{7}{2} -\frac{5}{2k}$, $\frac{5}{2} -\frac{1}{k}$ and $\frac{7}{2} -\frac{1}{k}$ when $m=1$, $m\geq k\geq 2$ and $k>m\geq 2$ respectively. We also present computational results to corroborate the performance of the proposed approximation algorithm.