Synchronization and Diversity of Solutions
Number of Authors: 4 2023 (English) In: Proceedings of the 37th AAAI Conference on Artificial Intelligence / [ed] Brian Williams, Yiling Chen, Jennifer Neville, Association for the Advancement of Artificial Intelligence , 2023, p. 11516-11524Conference paper, Published paper (Refereed)
Abstract [en]
A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.
Place, publisher, year, edition, pages Association for the Advancement of Artificial Intelligence , 2023. p. 11516-11524
Series
Proceedings of the annual AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468 ; 37(10)
Keywords [en]
MAS: Coordination and Collaboration, MAS: Multiagent Planning
National Category
Computer Sciences
Research subject Computer and Systems Sciences
Identifiers URN: urn:nbn:se:su:diva-225847 DOI: 10.1609/AAAI.V37I10.26361 ISBN: 978-1-57735-880-0 (electronic) OAI: oai:DiVA.org:su-225847 DiVA, id: diva2:1830701
Conference The Thirty-Seventh AAAI Conference on Artificial Intelligence, Washington, D.C., USA, February 7–14, 2023.
2024-01-232024-01-232024-11-11 Bibliographically approved