Mean Payoff Optimization for Systems of Periodic Service and Maintenance

Logo poskytovatele

Varování

Publikace nespadá pod Pedagogickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2023
Druh Článek ve sborníku
Konference Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www Paper URL
Doi http://dx.doi.org/10.24963/ijcai.2023/598
Klíčová slova Periodic Maintenance; strategy synthesis
Přiložené soubory
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.