Date of Award
3-2022
Document Type
Thesis
Degree Name
Master of Science
Department
Department of Operational Sciences
First Advisor
Matthew J. Robbins, PhD
Abstract
This research formulates and solves the multiagent routing problem with dynamic target arrivals (MRP-DTA), a stochastic system wherein a team of autonomous unmanned aerial vehicles (AUAVs) executes a strike coordination and reconnaissance (SCAR) mission against a notional adversary. Dynamic target arrivals that occur during the mission present the team of AUAVs with a sequential decision-making process which we model via a Markov Decision Process (MDP). To combat the curse of dimensionality, we construct and implement a hybrid approximate dynamic programming (ADP) algorithmic framework that employs a parametric cost function approximation (CFA) which augments a direct lookahead (DLA) model via a parameterization to the objective function. We show a statistically significant improvement over the repeated greedy marginal heuristic benchmark policy for 19 out of 20 problem instances and a statistically significant improvement over the repeated sequential orienteering problem benchmark policy for 8 out of 10 problem instances of the MRP-DTA. Results of excursion analysis show the value trade off of balancing solution quality and computational effort when selecting the base optimization model for our CFA-DLA algorithm.
AFIT Designator
AFIT-ENS-MS-22-M-156
DTIC Accession Number
AD1172394
Recommended Citation
Mogan, Andrew E., "Multiagent Routing Problem with Dynamic Target Arrivals Solved via Approximate Dynamic Programming" (2022). Theses and Dissertations. 5350.
https://scholar.afit.edu/etd/5350