Mean Payoff Optimization for Systems of Periodic Service and
Maintenance

D 2023

Mean Payoff Optimization for Systems of Periodic Service and Maintenance

KLAŠKA, David; Antonín KUČERA; Vít MUSIL a Vojtěch ŘEHÁK

Základní údaje

Originální název

Mean Payoff Optimization for Systems of Periodic Service and Maintenance

Autoři

KLAŠKA, David; Antonín KUČERA; Vít MUSIL a Vojtěch ŘEHÁK

Vydání

Neuveden, Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, od s. 5386-5393, 8 s. 2023

Nakladatel

International Joint Conferences on Artificial Intelligence

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Odkazy

Paper URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/23:00131517

Organizační jednotka

Fakulta informatiky

ISBN

978-1-956792-03-4

ISSN

Klíčová slova anglicky

Periodic Maintenance; strategy synthesis

Štítky

core_A, firank_1, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 7. 2025 10:26, Mgr. Michal Petr

Anotace

V originále

Consider oriented graph nodes requiring periodic visits by a service agent. The agent moves among the nodes and receives a payoff for each completed service task, depending on the time elapsed since the previous visit to a node. We consider the problem of finding a suitable schedule for the agent to maximize its long-run average payoff per time unit. We show that the problem of constructing an epsilon-optimal schedule is PSPACE-hard for every fixed non-negative epsilon, and that there exists an optimal periodic schedule of exponential length. We propose randomized finite-memory (RFM) schedules as a compact description of the agent's strategies and design an efficient algorithm for constructing RFM schedules. Furthermore, we construct deterministic periodic schedules by sampling from RFM schedules.

Návaznosti

GA21-24711S, projekt VaV

Název: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Akronym: Efektivní analýza a optimalizace pravděpodobnostní)

Investor: Grantová agentura ČR, Efektivní analýza a optimalizace pravděpodobnostních systémů a her

MUNI/A/1081/2022, interní kód MU

Název: Modelování, analýza a verifikace (2023)

Investor: Masarykova univerzita, Modelování, analýza a verifikace (2023)

MUNI/A/1433/2022, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 23

Přiložené soubory

0598.pdf

Požádat o autorskou verzi souboru

Citovat

KLAŠKA, David; Antonín KUČERA; Vít MUSIL a Vojtěch ŘEHÁK. Mean Payoff Optimization for Systems of Periodic Service and Maintenance. Online. In Edith Elkind. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,. Neuveden: International Joint Conferences on Artificial Intelligence, 2023, s. 5386-5393. ISBN 978-1-956792-03-4. Dostupné z: https://doi.org/10.24963/ijcai.2023/598.

@inproceedings{2304579,
   author = {Klaška, David and Kučera, Antonín and Musil, Vít and Řehák, Vojtěch},
   address = {Neuveden},
   booktitle = {Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,},
   doi = {https://doi.org/10.24963/ijcai.2023/598},
   editor = {Edith Elkind},
   keywords = {Periodic Maintenance; strategy synthesis},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Neuveden},
   isbn = {978-1-956792-03-4},
   pages = {5386-5393},
   publisher = {International Joint Conferences on Artificial Intelligence},
   title = {Mean Payoff Optimization for Systems of Periodic Service and Maintenance},
   url = {https://www.ijcai.org/proceedings/2023/598},
   year = {2023}
}

TY  - CONF
ID  - 2304579
AU  - Klaška, David - Kučera, Antonín - Musil, Vít - Řehák, Vojtěch
PY  - 2023
TI  - Mean Payoff Optimization for Systems of Periodic Service and Maintenance
PB  - International Joint Conferences on Artificial Intelligence
CY  - Neuveden
SN  - 9781956792034
KW  - Periodic Maintenance
KW  - strategy synthesis
UR  - https://www.ijcai.org/proceedings/2023/598
N2  - Consider oriented graph nodes requiring periodic visits by a service agent. The agent moves among the nodes and receives a payoff for each completed service task, depending on the time elapsed since the previous visit to a node. We consider the problem of finding a suitable schedule for the agent to maximize its long-run average payoff per time unit. We show that the problem of constructing an epsilon-optimal schedule is PSPACE-hard for every fixed non-negative epsilon, and that there exists an optimal periodic schedule of exponential length. We propose randomized finite-memory (RFM) schedules as a compact description of the agent's strategies and design an efficient algorithm for constructing RFM schedules. Furthermore, we construct deterministic periodic schedules by sampling from RFM schedules.
ER  -

KLAŠKA, David; Antonín KUČERA; Vít MUSIL a Vojtěch ŘEHÁK. Mean Payoff Optimization for Systems of Periodic Service and Maintenance. Online. In Edith Elkind. \textit{Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,}. Neuveden: International Joint Conferences on Artificial Intelligence, 2023, s.~5386-5393. ISBN~978-1-956792-03-4. Dostupné z: https://doi.org/10.24963/ijcai.2023/598.

Přehled o publikaci