Argumentation for Explainable Scheduling (Full Paper with Proofs)

Kristijonas Cyras, Dimitrios Letsios, Ruth Misener, Francesca Toni

Researchers from Imperial College London have introduced ArgOpt, a framework designed to demystify complex scheduling algorithms using the logic of formal argumentation. By mapping mathematical constraints to "arguments" and "attacks," ArgOpt allows optimization solvers to explain their decisions in plain English while maintaining a rigorous mathematical foundation.

Bridging the Gap in Optimization

Mathematical optimization is essential for modern logistics, powering everything from airline scheduling to nurse rostering. However, these solvers often function as "black boxes." When a solver produces an "optimal" schedule, human managers frequently lack the means to understand why specific decisions were made. Conversely, if a manager attempts to modify a schedule and the solver rejects the change, the reasoning is often obscured by complex linear programming duality or combinatorial constraints.

The high-level architecture of the ArgOpt framework.

ArgOpt addresses the need for cognitive tractability—explanations that are mathematically sound yet simple enough for human comprehension and fast enough to generate in real-time. The framework acts as an intermediate translation layer between the raw output of an optimization solver and the end-user.

The ArgOpt Framework

The core of ArgOpt leverages Abstract Argumentation (AA), a field of AI that represents knowledge as a directed graph of arguments and conflicts (attacks). In this system:

  1. Decisions become Arguments: Every possible assignment (e.g., "Job $j$ is assigned to Machine $i$") is treated as an argument.
  2. Constraints become Attacks: Scheduling rules are translated into attacks. For instance, if two machines cannot perform the same job, the arguments for those assignments "attack" each other.

To provide comprehensive explanations, the framework is divided into three specialized Argumentation Frameworks (AFs):

The internal components of the ArgOpt argumentation layer.
  • Feasibility AF: Explains whether a schedule is valid (e.g., ensuring every job is assigned).
  • Optimality (Efficiency) AF: Focuses on "efficiency" via Single and Pairwise Exchange Properties, explaining if a schedule can be improved by simple swaps rather than tackling the NP-hard problem of global optimality.
  • Fixed Decision AF: Explains why a schedule does or does not satisfy specific user-defined constraints, such as a specific staff member's holiday request.

Finally, a Natural Language Generation (NLG) component converts these formal graph relationships into human-readable sentences. An "attack" in the graph might be translated as: "Schedule S is not feasible because Job 1 is assigned to both Nurse 1 and Nurse 2."

Key Insights and Computational Efficiency

A major contribution of this work is the proof of polynomial explainability. While finding an optimal schedule is NP-hard, the authors proved that explaining why a schedule is "good" (feasible and efficient) can be done in polynomial time ($O(n^2m^2)$). This ensures that the system remains responsive during interactive use.

Furthermore, the researchers established a mathematical correspondence between "good" schedules and stable extensions—sets of arguments that do not conflict and defeat all outsiders. This means a stable extension serves as a formal "certificate" of the schedule's quality. Explanations are derived from both attacks (explaining conflicts) and non-attacks (explaining why certain assignments were omitted).

Conclusion and Future Directions

ArgOpt demonstrates that complex scheduling logic can be reduced to simple, direct causal explanations. While the current implementation focuses on the "makespan" problem (minimizing total completion time), it lays the foundation for explaining more complex objectives like cost or worker preferences. Future work aims to extend the framework to handle intricate constraints like labor laws and explore advanced optimization concepts like "cutting planes" within the argumentation layer.

Summary updated

BibTeX
@inproceedings{cyras2019argumentation,
  author = {Kristijonas Cyras and Dimitrios Letsios and Ruth Misener and Francesca Toni},
  title = {{Argumentation for Explainable Scheduling (Full Paper with Proofs)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012752},
}
Figure