Multi-start team orienteering problem for UAS mission re-planning with data-efficient deep reinforcement learning
Applied Intelligence · 2024-03 · 54 (6) · 4467-4489
DOI: 10.1007/s10489-024-05367-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Applied Intelligence, online erschienen am 27.03.2024. Verfasst von Dong Ho Lee und 1 weiteren Autor:innen. Die Arbeit wurde bisher 16-mal zitiert (Crossref) und nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Research Foundation of Korea, Korea Advanced Institute of Science and Technology.
Abstract (Originalsprache)
In this paper, we study the Multi-Start Team Orienteering Problem (MSTOP), a mission re-planning problem where vehicles are initially located away from the depot and have different amounts of fuel. We consider/assume the goal of multiple vehicles is to travel to maximize the sum of collected profits under resource (e.g., time, fuel) consumption constraints. Such re-planning problems occur in a wide range of intelligent UAS applications where changes in the mission environment force the operation of multiple vehicles to change from the original plan. To solve this problem with deep reinforcement learning (RL), we develop a policy network with self-attention on each partial tour and encoder-decoder attention between the partial tour and the remaining nodes. We propose a modified REINFORCE algorithm where the greedy rollout baseline is replaced by a local mini-batch baseline based on multiple, possibly non-duplicate sample rollouts. By drawing multiple samples per training instance, we can learn faster and obtain a stable policy gradient estimator with significantly fewer instances. The proposed training algorithm outperforms the conventional greedy rollout baseline, even when combined with the maximum entropy objective. The efficiency of our method is further demonstrated in two classical problems – the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP). The experimental results show that our method enables models to develop more effective heuristics and performs competitively with the state-of-the-art deep reinforcement learning methods.
Förderung
- National Research Foundation of Korea
- Korea Advanced Institute of Science and Technology
Zitieren
APA
Lee, D. H., & Ahn, J. (2024). Multi-start team orienteering problem for UAS mission re-planning with data-efficient deep reinforcement learning. Applied Intelligence, 54(6), 4467-4489. https://doi.org/10.1007/s10489-024-05367-4
Vancouver
Lee DH, Ahn J. Multi-start team orienteering problem for UAS mission re-planning with data-efficient deep reinforcement learning. Applied Intelligence. 2024;54(6):4467-4489. doi:10.1007/s10489-024-05367-4
BibTeX
@article{Lee2024,
author = {Lee, Dong Ho and Ahn, Jaemyung},
title = {Multi-start team orienteering problem for UAS mission re-planning with data-efficient deep reinforcement learning},
journal = {Applied Intelligence},
year = {2024},
volume = {54},
number = {6},
pages = {4467--4489},
doi = {10.1007/s10489-024-05367-4}
}
EUVIMED