Journal
IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 5, Issue 2, Pages 2146-2153Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2020.2970689
Keywords
Planning; scheduling and coordination; path planning for multiple mobile robots or agents; task allocation
Categories
Ask authors/readers for more resources
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 ck robots and m human operators, an algorithm is developed for solving the TASSP with an approximation ratio equal to \frac{5}{2}-\frac{1}{k} when m\geq k and equal to \frac{7}{2}-\frac{1}{k} otherwise. Computational results are also presented to corroborate the performance of the proposed algorithm.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available