TY - JOUR
T1 - A hybrid tabu search and 2-OPT path programming for mission route planning of multiple robots under range limitations
AU - Lee, Meng Tse
AU - Chen, Bo Yu
AU - Lai, Ying Chih
N1 - Funding Information:
Funding: This research was funded by the Ministry of Science and Technology, Taiwan (ROC), under grant number MOST-107-EPA-F-010-001.
Publisher Copyright:
© 2020 by the authors. Licensee MDPI, Basel, Switzerland.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/3
Y1 - 2020/3
N2 - The application of an unmanned vehicle system allows for accelerating the performance of various tasks. Due to limited capacities, such as battery power, it is almost impossible for a single unmanned vehicle to complete a large-scale mission area. An unmanned vehicle swarm has the potential to distribute tasks and coordinate the operations of many robots/drones with very little operator intervention. Therefore, multiple unmanned vehicles are required to execute a set of well-planned mission routes, in order to minimize time and energy consumption. A two-phase heuristic algorithm was used to pursue this goal. In the first phase, a tabu search and the 2-opt node exchange method were used to generate a single optimal path for all target nodes; the solution was then split into multiple clusters according to vehicle numbers as an initial solution for each. In the second phase, a tabu algorithm combined with a 2-opt path exchange was used to further improve the in-route and cross-route solutions for each route. This diversification strategy allowed for approaching the global optimal solution, rather than a regional one with less CPU time. After these algorithms were coded, a group of three robot cars was used to validate this hybrid path programming algorithm.
AB - The application of an unmanned vehicle system allows for accelerating the performance of various tasks. Due to limited capacities, such as battery power, it is almost impossible for a single unmanned vehicle to complete a large-scale mission area. An unmanned vehicle swarm has the potential to distribute tasks and coordinate the operations of many robots/drones with very little operator intervention. Therefore, multiple unmanned vehicles are required to execute a set of well-planned mission routes, in order to minimize time and energy consumption. A two-phase heuristic algorithm was used to pursue this goal. In the first phase, a tabu search and the 2-opt node exchange method were used to generate a single optimal path for all target nodes; the solution was then split into multiple clusters according to vehicle numbers as an initial solution for each. In the second phase, a tabu algorithm combined with a 2-opt path exchange was used to further improve the in-route and cross-route solutions for each route. This diversification strategy allowed for approaching the global optimal solution, rather than a regional one with less CPU time. After these algorithms were coded, a group of three robot cars was used to validate this hybrid path programming algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85082806464&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082806464&partnerID=8YFLogxK
U2 - 10.3390/electronics9030534
DO - 10.3390/electronics9030534
M3 - Article
AN - SCOPUS:85082806464
VL - 9
JO - Electronics (Switzerland)
JF - Electronics (Switzerland)
SN - 2079-9292
IS - 3
M1 - 534
ER -