Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic

Ziyan An, Hendrik Baier, Abhishek Dubey, Ayan Mukhopadhyay, Meiyi Ma

ECAI 2024 - 27th European Conference on Artificial Intelligence 2024

PDF

Why This Matters

Monte Carlo tree search is a powerful planning algorithm but its decision-making process is opaque to non-technical users like transit dispatchers. This work addresses a critical gap by making sequential planning algorithms interpretable without sacrificing performance. The innovation lies in bridging formal verification methods with practical natural language explanation, enabling AI-based transit systems to communicate their reasoning to human operators who must ultimately trust and validate the recommendations.

What We Did

This paper presents a computation tree logic (CTL)-based explainable Monte Carlo tree search framework for sequential decision-making in transportation systems. The work develops a systematic approach to translate non-technical user queries into CTL logic formulas that can be verified against MCTS search trees. The framework incorporates specialized explainers that generate human-readable natural language responses describing why the planning algorithm selected particular actions, with explanations tailored to user concerns about route efficiency, time constraints, and alternative options.

Key Results

The CTL-based explainer successfully generates human-readable explanations for MCTS decisions in transit routing scenarios with different query types including efficiency queries, contrastive queries, and tree exploration questions. User studies with 82 participants demonstrate that the proposed framework significantly outperforms baseline visualization methods in user understanding, satisfaction, and trust. The approach maintains computational efficiency while providing comprehensive explanations suitable for real-world transit dispatch applications.

Full Abstract

Cite This Paper

@inproceedings{an2024enablingmctsexplainabilitysequential,
  author = {An, Ziyan and Baier, Hendrik and Dubey, Abhishek and Mukhopadhyay, Ayan and Ma, Meiyi},
  title = {Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic},
  year = {2024},
  abstract = {Monte Carlo tree search (MCTS) is one of the most capa- ble online search algorithms for sequential planning tasks, with sig- nificant applications in areas such as resource allocation and transit planning. Despite its strong performance in real-world deployment, the inherent complexity of MCTS makes it challenging to understand for users without technical background. This paper considers the use of MCTS in transportation routing services, where the algorithm is integrated to develop optimized route plans. These plans are required to meet a range of constraints and requirements simultaneously, fur- ther complicating the task of explaining the algorithm’s operation in real-world contexts. To address this critical research gap, we intro- duce a novel computation tree logic-based explainer for MCTS. Our framework begins by taking user-defined requirements and translat- ing them into rigorous logic specifications through the use of lan- guage templates. Then, our explainer incorporates a logic verifica- tion and quantitative evaluation module that validates the states and actions traversed by the MCTS algorithm. The outcomes of this anal- ysis are then rendered into human-readable descriptive text using a second set of language templates. The user satisfaction of our ap- proach was assessed through a survey with 82 participants. The re- sults indicated that our explanatory approach significantly outper- forms other baselines in user preference.},
  archiveprefix = {arXiv},
  booktitle = {ECAI} 2024 - 27th European Conference on Artificial Intelligence},
  contribution = {colab},
  acceptance = {23},
  eprint = {2407.10820},
  location = {Santiago de Compostela, Spain},
  primaryclass = {cs.AI},
  url = {https://arxiv.org/abs/2407.10820},
  keywords = {explainable AI, Monte Carlo tree search, sequential planning, natural language explanation, transportation, user interpretability, transit routing, human-AI interaction}
}
Quick Info
Year 2024
Keywords
explainable AI Monte Carlo tree search sequential planning natural language explanation transportation user interpretability transit routing human-AI interaction
Research Areas
transit Explainable AI middleware
Search Tags

Enabling, MCTS, Explainability, Sequential, Planning, Computation, Tree, Logic, explainable AI, Monte Carlo tree search, sequential planning, natural language explanation, transportation, user interpretability, transit routing, human-AI interaction, transit, Explainable AI, middleware, 2024, An, Baier, Dubey, Mukhopadhyay, Ma