Explainable Distributed Constraint Optimization Problems
This work addresses the need for explainable solutions in cooperative multi-agent systems, facilitating adoption in real-world applications, though it is incremental by extending existing DCOP models.
The paper tackles the problem that Distributed Constraint Optimization Problem (DCOP) solutions are not easily understandable, proposing the Explainable DCOP (X-DCOP) model with contrastive queries and a distributed framework to generate valid explanations, showing scalability to large problems and trade-offs between explanation lengths and runtimes.
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model cooperative multi-agent problems that need to be solved distributively. A core assumption of existing approaches is that DCOP solutions can be easily understood, accepted, and adopted, which may not hold, as evidenced by the large body of literature on Explainable AI. In this paper, we propose the Explainable DCOP (X-DCOP) model, which extends a DCOP to include its solution and a contrastive query for that solution. We formally define some key properties that contrastive explanations must satisfy for them to be considered as valid solutions to X-DCOPs as well as theoretical results on the existence of such valid explanations. To solve X-DCOPs, we propose a distributed framework as well as several optimizations and suboptimal variants to find valid explanations. We also include a human user study that showed that users, not surprisingly, prefer shorter explanations over longer ones. Our empirical evaluations showed that our approach can scale to large problems, and the different variants provide different options for trading off explanation lengths for smaller runtimes. Thus, our model and algorithmic contributions extend the state of the art by reducing the barrier for users to understand DCOP solutions, facilitating their adoption in more real-world applications.