A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost

Jungyun Bae; Jungho Lee; Woojin Chung

doi:10.1109/ICRA.2019.8794257

A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost

Jungyun Bae, Jungho Lee, Woojin Chung

School of Mechanical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	2019 International Conference on Robotics and Automation, ICRA 2019
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4531-4537
Number of pages	7
ISBN (Electronic)	9781538660263
DOIs	https://doi.org/10.1109/ICRA.2019.8794257
Publication status	Published - 2019 May
Event	2019 International Conference on Robotics and Automation, ICRA 2019 - Montreal, Canada Duration: 2019 May 20 → 2019 May 24

Publication series

Name	Proceedings - IEEE International Conference on Robotics and Automation
Volume	2019-May
ISSN (Print)	1050-4729

Conference

Conference	2019 International Conference on Robotics and Automation, ICRA 2019
Country/Territory	Canada
City	Montreal
Period	19/5/20 → 19/5/24

Bibliographical note

Funding 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.

Funding Information:
*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.

Publisher Copyright:
© 2019 IEEE.

ASJC Scopus subject areas

Software
Control and Systems Engineering
Artificial Intelligence
Electrical and Electronic Engineering

Access to Document

10.1109/ICRA.2019.8794257

Cite this

Bae, J., Lee, J., & Chung, W. (2019). A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. In 2019 International Conference on Robotics and Automation, ICRA 2019 (pp. 4531-4537). Article 8794257 (Proceedings - IEEE International Conference on Robotics and Automation; Vol. 2019-May). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRA.2019.8794257

A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. / Bae, Jungyun; Lee, Jungho; Chung, Woojin.
2019 International Conference on Robotics and Automation, ICRA 2019. Institute of Electrical and Electronics Engineers Inc., 2019. p. 4531-4537 8794257 (Proceedings - IEEE International Conference on Robotics and Automation; Vol. 2019-May).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bae, J, Lee, J & Chung, W 2019, A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. in 2019 International Conference on Robotics and Automation, ICRA 2019., 8794257, Proceedings - IEEE International Conference on Robotics and Automation, vol. 2019-May, Institute of Electrical and Electronics Engineers Inc., pp. 4531-4537, 2019 International Conference on Robotics and Automation, ICRA 2019, Montreal, Canada, 19/5/20. https://doi.org/10.1109/ICRA.2019.8794257

Bae J, Lee J, Chung W. A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. In 2019 International Conference on Robotics and Automation, ICRA 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 4531-4537. 8794257. (Proceedings - IEEE International Conference on Robotics and Automation). doi: 10.1109/ICRA.2019.8794257

Bae, Jungyun ; Lee, Jungho ; Chung, Woojin. / A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost. 2019 International Conference on Robotics and Automation, ICRA 2019. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 4531-4537 (Proceedings - IEEE International Conference on Robotics and Automation).

@inproceedings{73b30b5cb6d546789453dd3e437b20cc,

title = "A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost",

abstract = "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.",

author = "Jungyun Bae and Jungho Lee and Woojin Chung",

note = "Funding 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. Funding Information: *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. Publisher Copyright: {\textcopyright} 2019 IEEE.; 2019 International Conference on Robotics and Automation, ICRA 2019 ; Conference date: 20-05-2019 Through 24-05-2019",

year = "2019",

month = may,

doi = "10.1109/ICRA.2019.8794257",

language = "English",

series = "Proceedings - IEEE International Conference on Robotics and Automation",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4531--4537",

booktitle = "2019 International Conference on Robotics and Automation, ICRA 2019",

}

TY - GEN

T1 - A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost

AU - Bae, Jungyun

AU - Lee, Jungho

AU - Chung, Woojin

N1 - Funding 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. Funding Information: *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. Publisher Copyright: © 2019 IEEE.

PY - 2019/5

Y1 - 2019/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85071513751&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2019.8794257

DO - 10.1109/ICRA.2019.8794257

M3 - Conference contribution

AN - SCOPUS:85071513751

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 4531

EP - 4537

BT - 2019 International Conference on Robotics and Automation, ICRA 2019

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2019 International Conference on Robotics and Automation, ICRA 2019

Y2 - 20 May 2019 through 24 May 2019

ER -

A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this