Polynomial-Time Algorithms for Multiagent Minimal-Capacity Planning

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26230%2F22%3APU155512" target="_blank" >RIV/00216305:26230/22:PU155512 - isvavai.cz</a>

Výsledek na webu

<a href="https://ieeexplore.ieee.org/document/9695237" target="_blank" >https://ieeexplore.ieee.org/document/9695237</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/TCNS.2022.3146297" target="_blank" >10.1109/TCNS.2022.3146297</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Polynomial-Time Algorithms for Multiagent Minimal-Capacity Planning

Popis výsledku v původním jazyce

In this article, we study the problem of minimizing the resource capacity of autonomous agents that cooperate to achieve a shared task. More specifically, we consider high-level planning for a team of homogeneous agents that operate under resource constraints in stochastic environments and share a common goal: given a set of target locations, ensure that each location is visited infinitely often by some agents almost surely. We formalize the dynamics of agents by the so-called consumption Markov decision processes. In a consumption Markov decision process, the agent has a resource of limited capacity. Each action of the agent may consume some amount of the resource. To avoid exhaustion, the agent can replenish its resource to full capacity in designated reload states. The resource capacity restricts the capabilities of the agent. The objective is to assign target locations to agents, and each agent is only responsible for visiting the assigned subset of target locations repeatedly. Moreover, the assignment must ensure that the agents can carry out their tasks with minimal resource capacity. We reduce the problem to an equivalent graph-theoretical problem. We develop an algorithm that solves this graph problem in time that is polynomial in the number of agents, target locations, and size of the consumption Markov decision process. We demonstrate the applicability and scalability of the algorithm in a scenario where hundreds of unmanned underwater vehicles monitor hundreds of locations in environments with stochastic ocean currents.

Název v anglickém jazyce

Polynomial-Time Algorithms for Multiagent Minimal-Capacity Planning

Popis výsledku anglicky

In this article, we study the problem of minimizing the resource capacity of autonomous agents that cooperate to achieve a shared task. More specifically, we consider high-level planning for a team of homogeneous agents that operate under resource constraints in stochastic environments and share a common goal: given a set of target locations, ensure that each location is visited infinitely often by some agents almost surely. We formalize the dynamics of agents by the so-called consumption Markov decision processes. In a consumption Markov decision process, the agent has a resource of limited capacity. Each action of the agent may consume some amount of the resource. To avoid exhaustion, the agent can replenish its resource to full capacity in designated reload states. The resource capacity restricts the capabilities of the agent. The objective is to assign target locations to agents, and each agent is only responsible for visiting the assigned subset of target locations repeatedly. Moreover, the assignment must ensure that the agents can carry out their tasks with minimal resource capacity. We reduce the problem to an equivalent graph-theoretical problem. We develop an algorithm that solves this graph problem in time that is polynomial in the number of agents, target locations, and size of the consumption Markov decision process. We demonstrate the applicability and scalability of the algorithm in a scenario where hundreds of unmanned underwater vehicles monitor hundreds of locations in environments with stochastic ocean currents.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

IEEE Transactions on Control of Network Systems

ISSN

2372-2533

e-ISSN

—

Svazek periodika

3

Číslo periodika v rámci svazku

9

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

11

Strana od-do

1327-1338

Kód UT WoS článku

000856122100027

EID výsledku v databázi Scopus

2-s2.0-85124107262