  Zero-shot coordination in cooperative artificial intelligence (AI) remains a
significant challenge, which means effectively coordinating with a wide range
of unseen partners. Previous algorithms have attempted to address this
challenge by optimizing fixed objectives within a population to improve
strategy or behaviour diversity. However, these approaches can result in a loss
of learning and an inability to cooperate with certain strategies within the
population, known as cooperative incompatibility. To address this issue, we
propose the Cooperative Open-ended LEarning (COLE) framework, which constructs
open-ended objectives in cooperative games with two players from the
perspective of graph theory to assess and identify the cooperative ability of
each strategy. We further specify the framework and propose a practical
algorithm that leverages knowledge from game theory and graph theory.
Furthermore, an analysis of the learning process of the algorithm shows that it
can efficiently overcome cooperative incompatibility. The experimental results
in the Overcooked game environment demonstrate that our method outperforms
current state-of-the-art methods when coordinating with different-level
partners. Our demo is available at https://sites.google.com/view/cole-2023.
