DROPS

Document

DOI: 10.4230/OASIcs.DX.2024.8

Diagnosing Multi-Agent STRIPS Plans

Authors: Avraham Natan, Roni Stern, Meir Kalech, William Yeoh, and Tran Cao Son

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract

The increasing use of multi-agent systems demands that many challenges be addressed. One such challenge is diagnosing failed multi-agent plan executions, sometimes in system setups where the different agents are not willing to disclose their private actions. One formalism for generating multi-agent plans is the well-known MA-STRIPS formalism. While there have been approaches for delivering as robust plans as possible, we focus on the plan execution stage. Specifically, we address the problem of diagnosing plans that failed their execution. We propose a Model-Based Diagnosis approach to solve this problem. Given an MA-STRIPS problem, a plan that solves it, and an observation that indicates execution failure, we define the MA-STRIPS diagnosis problem. We compile that problem into a boolean satisfiability problem (SAT) and then use an off-the-shelf SAT solver to obtain candidate diagnoses. We further expand this approach to address privacy by proposing a distributed algorithm that can find these same diagnoses in a decentralized manner. Additionally, we propose an enhancement to the distributed algorithm that uses information generated during the diagnosis process to provide significant speedups. We found that the improved algorithm runs more than 10 times faster than the basic decentralized version and, in one case, runs faster than the centralized algorithm.

Cite as

Avraham Natan, Roni Stern, Meir Kalech, William Yeoh, and Tran Cao Son. Diagnosing Multi-Agent STRIPS Plans. In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{natan_et_al:OASIcs.DX.2024.8,
  author =	{Natan, Avraham and Stern, Roni and Kalech, Meir and Yeoh, William and Son, Tran Cao},
  title =	{{Diagnosing Multi-Agent STRIPS Plans}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{8:1--8:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.8},
  URN =		{urn:nbn:de:0030-drops-221001},
  doi =		{10.4230/OASIcs.DX.2024.8},
  annote =	{Keywords: Model-based diagnosis, Multi-agent systems, Distributed diagnosis, Privacy}
}

Document

Short Paper

DOI: 10.4230/OASIcs.DX.2024.23

Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions (Short Paper)

Authors: Avraham Natan, Roni Stern, and Meir Kalech

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract

Reinforcement learning (RL) algorithms output policies specifying which action an agent should take in a given state. However, faults can sometimes arise during policy execution due to internal faults in the agent. As a result, actions may have unexpected effects. In this work, we aim to diagnose such faults and infer their root cause. We consider two types of diagnosis problems. In the first, which we call RLDXw, we assume we only know what a normal execution looks like. In the second, called RLDXs, we assume we have models for the faulty behavior of a component, which we call fault modes. The solution to RLDXw is a time step at which a fault occurred for the first time. The solution to RLDXs is more informative, represented as a fault mode according to which the RL task was executed. Solving those problems is useful in practice to facilitate efficient repair of faulty agents, since it can focus the repair efforts on specific actions. We formally define RLDXw and RLDXs and design two algorithms called WFMa and SFMa for solving them. We evaluate our algorithms on a benchmark of RL domains and discuss their strengths and limitations. When the number of the observed states increases, both WFMa and SFMa report a decrease in runtime (up to significantly 6.5 times faster). Additionally, the runtime of SFMa increases linearly with the increase in candidate fault modes.

Cite as

Avraham Natan, Roni Stern, and Meir Kalech. Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions (Short Paper). In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{natan_et_al:OASIcs.DX.2024.23,
  author =	{Natan, Avraham and Stern, Roni and Kalech, Meir},
  title =	{{Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{23:1--23:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.23},
  URN =		{urn:nbn:de:0030-drops-221151},
  doi =		{10.4230/OASIcs.DX.2024.23},
  annote =	{Keywords: Diagnosis, Reinforcement Learning, Autonomous Systems}
}

Search Results

Documents authored by Stern, Roni

Diagnosing Multi-Agent STRIPS Plans

Abstract

Cite as

Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message