Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic

• URL: http://arxiv.org/abs/2407.10820v3
• Date: Tue, 29 Oct 2024 18:42:33 GMT
• Title: Enabling MCTS Explainability for Sequential Planning Through Computation Tree Logic
• Authors: Ziyan An, Hendrik Baier, Abhishek Dubey, Ayan Mukhopadhyay, Meiyi Ma,
• Abstract summary: Monte Carlo tree search (MCTS) is one of the most capable online search algorithms for sequential planning tasks. Despite its strong performance in real-world deployment, the inherent computation 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.
• Score: 8.832654509932565
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Monte Carlo tree search (MCTS) is one of the most capable online search algorithms for sequential planning tasks, with significant 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, further complicating the task of explaining the algorithm's operation in real-world contexts. To address this critical research gap, we introduce a novel computation tree logic-based explainer for MCTS. Our framework begins by taking user-defined requirements and translating them into rigorous logic specifications through the use of language templates. Then, our explainer incorporates a logic verification and quantitative evaluation module that validates the states and actions traversed by the MCTS algorithm. The outcomes of this analysis are then rendered into human-readable descriptive text using a second set of language templates. The user satisfaction of our approach was assessed through a survey with 82 participants. The results indicated that our explanatory approach significantly outperforms other baselines in user preference.

Related papers

• Combining LLMs with Logic-Based Framework to Explain MCTS [13.276888833862447]
  We design a Computational Tree-guided large language model (LLM)-based natural language explanation framework for the Monte Carlo Tree Search (MCTS) algorithm. By transforming user queries into logic and variable statements, our framework ensures that the evidence obtained from the search tree remains factually consistent. We evaluate the framework rigorously through quantitative assessments, where it demonstrates strong performance in terms of accuracy and factual consistency.
  arXiv  Detail & Related papers  (2025-05-01T15:40:58Z)
• Monte Carlo Planning with Large Language Model for Text-Based Game Agents [27.385517721352368]
  We introduce the Monte Carlo planning with Dynamic Memory-guided Large language model (MC-DML) algorithm. MC-DML leverages the language understanding and reasoning capabilities of Large Language Models (LLMs) alongside the exploratory advantages of tree search algorithms. Our results demonstrate that the MC-DML algorithm significantly enhances performance across various games at the initial planning phase.
  arXiv  Detail & Related papers  (2025-04-23T16:23:15Z)
• Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
  We introduce CodePlan, a framework that generates and follows textcode-form plans -- pseudocode that outlines high-level, structured reasoning processes. CodePlan effectively captures the rich semantics and control flows inherent to sophisticated reasoning tasks. It achieves a 25.1% relative improvement compared with directly generating responses.
  arXiv  Detail & Related papers  (2024-09-19T04:13:58Z)
• Scaling Up Natural Language Understanding for Multi-Robots Through the Lens of Hierarchy [8.180994118420053]
  Long-horizon planning is hindered by challenges such as uncertainty accumulation, computational complexity, delayed rewards and incomplete information. This work proposes an approach to exploit the task hierarchy from human instructions to facilitate multi-robot planning.
  arXiv  Detail & Related papers  (2024-08-15T14:46:13Z)
• Planning with OWL-DL Ontologies (Extended Version) [6.767885381740952]
  We present a black-box that supports the full power expressive DL. Our main algorithm relies on rewritings of the OWL-mediated planning specifications into PDDL. We evaluate our implementation on benchmark sets from several domains.
  arXiv  Detail & Related papers  (2024-08-14T13:27:02Z)
• H-STAR: LLM-driven Hybrid SQL-Text Adaptive Reasoning on Tables [56.73919743039263]
  This paper introduces a novel algorithm that integrates both symbolic and semantic (textual) approaches in a two-stage process to address limitations. Our experiments demonstrate that H-STAR significantly outperforms state-of-the-art methods across three question-answering (QA) and fact-verification datasets.
  arXiv  Detail & Related papers  (2024-06-29T21:24:19Z)
• Can Long-Context Language Models Subsume Retrieval, RAG, SQL, and More? [54.667202878390526]
  Long-context language models (LCLMs) have the potential to revolutionize our approach to tasks traditionally reliant on external tools like retrieval systems or databases. We introduce LOFT, a benchmark of real-world tasks requiring context up to millions of tokens designed to evaluate LCLMs' performance on in-context retrieval and reasoning. Our findings reveal LCLMs' surprising ability to rival state-of-the-art retrieval and RAG systems, despite never having been explicitly trained for these tasks.
  arXiv  Detail & Related papers  (2024-06-19T00:28:58Z)
• Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
  We propose a curriculum-based logical-aware instruction tuning framework, named LACT. Specifically, we augment the arbitrary first-order logical queries via binary tree decomposition. Experiments across widely used datasets demonstrate that LACT has substantial improvements(brings an average +5.5% MRR score) over advanced methods, achieving the new state-of-the-art.
  arXiv  Detail & Related papers  (2024-05-02T18:12:08Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications [8.471147498059235]
  We introduce a hierarchical structure to sc-LTL specifications with both syntax and semantics, proving it to be more expressive than flat counterparts. We develop a search-based approach to synthesize plans for multi-robot systems, achieving simultaneous task allocation and planning.
  arXiv  Detail & Related papers  (2024-01-08T16:35:13Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  We propose MURMUR, a neuro-symbolic modular approach to text generation from semi-structured data with multi-step reasoning. We conduct experiments on two data-to-text generation tasks like WebNLG and LogicNLG.
  arXiv  Detail & Related papers  (2022-12-16T17:36:23Z)
• Compositional Reinforcement Learning from Logical Specifications [21.193231846438895]
  Recent approaches automatically generate a reward function from a given specification and use a suitable reinforcement learning algorithm to learn a policy. We develop a compositional learning approach, called DiRL, that interleaves high-level planning and reinforcement learning. Our approach then incorporates reinforcement learning to learn neural network policies for each edge (sub-task) within a Dijkstra-style planning algorithm to compute a high-level plan in the graph.
  arXiv  Detail & Related papers  (2021-06-25T22:54:28Z)
• Online Learning Probabilistic Event Calculus Theories in Answer Set Programming [70.06301658267125]
  Event Recognition (CER) systems detect occurrences in streaming time-stamped datasets using predefined event patterns. We present a system based on Answer Set Programming (ASP), capable of probabilistic reasoning with complex event patterns in the form of rules weighted in the Event Calculus. Our results demonstrate the superiority of our novel approach, both terms efficiency and predictive.
  arXiv  Detail & Related papers  (2021-03-31T23:16:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.