EUVIMEDEUVIMED entdecken
Crossref

Multiagent, Multitarget Path Planning in Markov Decision Processes

Farhad Nawaz, Melkior Ornik

IEEE Transactions on Automatic Control · 2023-12 · 68 (12) · 7560-7574

DOI: 10.1109/tac.2023.3286807 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Automatic Control, 2023-12. Verfasst von Farhad Nawaz und 1 weiteren Autor:innen. Die Arbeit wurde bisher 20-mal zitiert (Crossref) und nennt 28 Literaturangaben. Gefördert von: NASA, Defense Advanced Research Projects Agency, Office of Naval Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Missions for autonomous systems often require agents to visit multiple targets in complex operating conditions. This work considers the problem of visiting a set of targets in minimum time by a team of noncommunicating agents in a Markov decision process (MDP). The single-agent problem is at least NP-complete by reducing it to a Hamiltonian path problem. We first discuss an optimal algorithm based on Bellman's optimality equation that is exponential in the number of target states. Then, we tradeoff optimality for time complexity by presenting a suboptimal algorithm that is polynomial at each time step. We prove that the proposed algorithm generates optimal policies for certain classes of MDPs. Extending our procedure to the multiagent case, we propose a target partitioning algorithm that approximately minimizes the expected time to visit the targets. We prove that our algorithm generates optimal partitions for clustered target scenarios. We present the performance of our algorithms on random MDPs and gridworld environments inspired by ocean dynamics. We show that our algorithms are much faster than the optimal procedure and more optimal than the currently available heuristic.

Förderung

  • NASA
  • Defense Advanced Research Projects Agency
  • Office of Naval Research

Zitieren

APA

Nawaz, F., & Ornik, M. (2023). Multiagent, Multitarget Path Planning in Markov Decision Processes. IEEE Transactions on Automatic Control, 68(12), 7560-7574. https://doi.org/10.1109/tac.2023.3286807

Vancouver

Nawaz F, Ornik M. Multiagent, Multitarget Path Planning in Markov Decision Processes. IEEE Transactions on Automatic Control. 2023;68(12):7560-7574. doi:10.1109/tac.2023.3286807

BibTeX
@article{Nawaz2023,
  author = {Nawaz, Farhad and Ornik, Melkior},
  title = {Multiagent, Multitarget Path Planning in Markov Decision Processes},
  journal = {IEEE Transactions on Automatic Control},
  year = {2023},
  volume = {68},
  number = {12},
  pages = {7560--7574},
  doi = {10.1109/tac.2023.3286807}
}
Kostenlos starten →