Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming

• URL: http://arxiv.org/abs/2008.03573v1
• Date: Sat, 8 Aug 2020 18:34:34 GMT
• Title: Explanation Generation for Multi-Modal Multi-Agent Path Finding with Optimal Resource Utilization using Answer Set Programming
• Authors: Aysu Bogatarkan and Esra Erdem
• Abstract summary: The real-world applications of mMAPF require flexibility and explainability. This paper introduces a method for generating explanations for queries regarding the feasibility and optimality of solutions.
• Score: 1.7132914341329848
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-agent path finding (MAPF) problem is a combinatorial search problem that aims at finding paths for multiple agents (e.g., robots) in an environment (e.g., an autonomous warehouse) such that no two agents collide with each other, and subject to some constraints on the lengths of paths. We consider a general version of MAPF, called mMAPF, that involves multi-modal transportation modes (e.g., due to velocity constraints) and consumption of different types of resources (e.g., batteries). The real-world applications of mMAPF require flexibility (e.g., solving variations of mMAPF) as well as explainability. Our earlier studies on mMAPF have focused on the former challenge of flexibility. In this study, we focus on the latter challenge of explainability, and introduce a method for generating explanations for queries regarding the feasibility and optimality of solutions, the nonexistence of solutions, and the observations about solutions. Our method is based on answer set programming. This paper is under consideration for acceptance in TPLP.

Related papers

• AQA: Adaptive Question Answering in a Society of LLMs via Contextual Multi-Armed Bandit [59.10281630985958]
  In question answering (QA), different questions can be effectively addressed with different answering strategies. We develop a dynamic method that adaptively selects the most suitable QA strategy for each question. Our experiments show that the proposed solution is viable for adaptive orchestration of a QA system with multiple modules.
  arXiv  Detail & Related papers  (2024-09-20T12:28:18Z)
• Multi-LLM QA with Embodied Exploration [55.581423861790945]
  We investigate the use of Multi-Embodied LLM Explorers (MELE) for question-answering in an unknown environment. Multiple LLM-based agents independently explore and then answer queries about a household environment. We analyze different aggregation methods to generate a single, final answer for each query.
  arXiv  Detail & Related papers  (2024-06-16T12:46:40Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding [18.06081009550052]
  Multi-Agent Reinforcement Learning (MARL) based Multi-Agent Path Finding (MAPF) has recently gained attention due to its efficiency and scalability. Several MARL-MAPF methods choose to use communication to enrich the information one agent can perceive. We propose a new method, Ensembling Prioritized Hybrid Policies (EPH)
  arXiv  Detail & Related papers  (2024-03-12T11:47:12Z)
• Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
  Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations. Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential. We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
  arXiv  Detail & Related papers  (2024-01-30T14:26:04Z)
• Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet [31.253063077167617]
  We focus on the problem of multi-agent path finding (MAPF), which is also known as multi-robot route planning. We show the motivating success on an empty room map without obstacles, then the failure to plan on the harder room map and maze map of the standard MAPF benchmark.
  arXiv  Detail & Related papers  (2024-01-08T02:22:04Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• POGEMA: Partially Observable Grid Environment for Multiple Agents [64.88759709443819]
  POGEMA is a sandbox for challenging partially observable multi-agent pathfinding (PO-MAPF) problems. It can be tailored to a variety of PO-MAPF, which can serve as an excellent testing ground for planning and learning methods.
  arXiv  Detail & Related papers  (2022-06-22T09:39:50Z)
• Flexible and Explainable Solutions for Multi-Agent Path Finding Problems [0.0]
  The real-world applications of MAPF require flexibility (e.g., solving variations of MAPF) as well as explainability. In this study, both of these challenges are addressed and some flexible and explainable solutions for MAPF and its variants are introduced.
  arXiv  Detail & Related papers  (2021-09-17T01:50:01Z)
• Decentralised Approach for Multi Agent Path Finding [6.599344783327053]
  Multi Agent Path Finding (MAPF) requires identification of conflict free paths for spatially-extended agents. These find application in real world problems like Convoy Movement Problem, Train Scheduling etc. Our proposed approach, Decentralised Multi Agent Path Finding (DeMAPF), handles MAPF as a sequence of pathplanning and allocation problems.
  arXiv  Detail & Related papers  (2021-06-03T18:07:26Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)

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.