Polynomial-Time Algorithms for Multiagent Minimal-Capacity Planning

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Polynomial-Time Algorithms for Multiagent Minimal-Capacity Planning

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2022

Confidentiality

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

Name of the periodical

IEEE Transactions on Control of Network Systems

ISSN

2372-2533

e-ISSN

—

Volume of the periodical

3

Issue of the periodical within the volume

9

Country of publishing house

US - UNITED STATES

Number of pages

11

Pages from-to

1327-1338

UT code for WoS article

000856122100027

EID of the result in the Scopus database

2-s2.0-85124107262