The article proposes a new heuristic for task allocation and routing of heterogeneous robots. Specifically, we consider a path planning problem where there are two (structurally) heterogeneous robots that start from distinctive depots and a set of targets to visit. The objective is to find a tour for each robot in a manner that enables each target location to be visited at least once by one of the robots while minimizing the maximum travel cost. A solution for Multiple Depot Heterogeneous Traveling Salesman Problem (MDHTSP) with min-max objective is in great demand with many potential applications, because it can significantly reduce the job completion duration. However, there are still no reliable algorithms that can run in short amount of time. As an initial idea of solving min-max MDHTSP, we present a heuristic based on a primal-dual technique that solves for a case involving two robots while focusing on task allocation. Based on computational results of the implementation, we show that the proposed algorithm produces a good quality of feasible solution within a relatively short computation time.
|Title of host publication||2019 International Conference on Robotics and Automation, ICRA 2019|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||7|
|Publication status||Published - 2019 May|
|Event||2019 International Conference on Robotics and Automation, ICRA 2019 - Montreal, Canada|
Duration: 2019 May 20 → 2019 May 24
|Name||Proceedings - IEEE International Conference on Robotics and Automation|
|Conference||2019 International Conference on Robotics and Automation, ICRA 2019|
|Period||19/5/20 → 19/5/24|
Bibliographical noteFunding Information:
This research was supported by the NRF, MSIP (NRF-2017R1A2A1 A17069329), also supported by the Agriculture, Food and Rural Affairs Research Center Support Program (714002-07), MAFRA, Korea.
*This work was supported by the NRF, MSIP (NRF-2017R1A2A1 A17069329), also supported by the Agriculture, Food and Rural Affairs Research Center Support Program (714002-07), MAFRA, Korea.
© 2019 IEEE.
ASJC Scopus subject areas
- Control and Systems Engineering
- Artificial Intelligence
- Electrical and Electronic Engineering