An Efficient Minimum-Time Cooperative Task Planning Algorithm for Serving Robots and Operators

We establish an efficient minimum-time cooperative task planning algorithm for robots and operators to serve clients. This problem is an extension of the multiple traveling salesman problem and the vehicle routing problem with synchronization constraints, but it is more difficult due to the cooperat...

Full description

Saved in:
Bibliographic Details
Published in:Robotica 2020-11, Vol.38 (11), p.1895-1920
Main Authors: Kim, Yong-Hwi, Kim, Byung Kook
Format: Article
Language:English
Subjects:
Algorithms
Clients
Operators
Robots
Route planning
Service robots
Space exploration
Synchronism
Task planning (robotics)
Traveling salesman problem
Vehicle routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We establish an efficient minimum-time cooperative task planning algorithm for robots and operators to serve clients. This problem is an extension of the multiple traveling salesman problem and the vehicle routing problem with synchronization constraints, but it is more difficult due to the cooperative tasks of the robots and operators. To find the exact minimum-time task plan with a small tree size, we propose an efficient branch-and-bound with a good initial tree and keen complementary heuristics. Our algorithm is also effective as an approximate algorithm for the many clients problem within the capacity of the computer used. The efficiency of our algorithm is revealed via case studies: telemedical service robots and planetary exploration robots.
ISSN:0263-5747
1469-8668
DOI:10.1017/S0263574719001711