Mean Payoff Optimization for Systems of Periodic Service and Maintenance

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

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

Year of publication 2023
Type Article in Proceedings
Conference Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023,
MU Faculty or unit

Faculty of Informatics

Citation
Web Paper URL
Doi http://dx.doi.org/10.24963/ijcai.2023/598
Keywords Periodic Maintenance; strategy synthesis
Attached files
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.