Synchronization and Diversity of Solutions

Authors

  • Emmanuel Arrighi University of Bergen
  • Henning Fernau University of Trier
  • Mateus de Oliveira Oliveira University of Bergen Stockholm University
  • Petra Wolf University of Bergen University of Trier

DOI:

https://doi.org/10.1609/aaai.v37i10.26361

Keywords:

MAS: Coordination and Collaboration, MAS: Multiagent Planning

Abstract

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.

Downloads

Published

2023-06-26

How to Cite

Arrighi, E., Fernau, H., de Oliveira Oliveira, M., & Wolf, P. (2023). Synchronization and Diversity of Solutions. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 11516-11524. https://doi.org/10.1609/aaai.v37i10.26361

Issue

Section

AAAI Technical Track on Multiagent Systems