On Computing Universal Plans for Partially Observable Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2305.16203v3
• Date: Sat, 24 Feb 2024 13:31:10 GMT
• Title: On Computing Universal Plans for Partially Observable Multi-Agent Path Finding
• Authors: Fengming Zhu, Fangzhen Lin
• Abstract summary: We argue that it is beneficial to formulate multi-agent routing problems as universal planning problems. We implement a system called ASP-MAUPF (Answer Set Programming for Multi-Agent Universal Plan Finding) for computing them.
• Score: 11.977931648859176
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent routing problems have drawn significant attention nowadays due to their broad industrial applications in, e.g., warehouse robots, logistics automation, and traffic control. Conventionally, they are modelled as classical planning problems. In this paper, we argue that it is beneficial to formulate them as universal planning problems. We therefore propose universal plans, also known as policies, as the solution concepts, and implement a system called ASP-MAUPF (Answer Set Programming for Multi-Agent Universal Plan Finding) for computing them. Given an arbitrary two-dimensional map and a profile of goals for the agents, the system finds a feasible universal plan for each agent that ensures no collision with others. We use the system to conduct some experiments, and make some observations on the types of goal profiles and environments that will have feasible policies, and how they may depend on agents' sensors. We also demonstrate how users can customize action preferences to compute more efficient policies, even (near-)optimal ones.

Related papers

• 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)
• Learn to Follow: Decentralized Lifelong Multi-agent Pathfinding via Planning and Learning [46.354187895184154]
  Multi-agent Pathfinding (MAPF) problem generally asks to find a set of conflict-free paths for a set of agents confined to a graph. In this work, we investigate the decentralized MAPF setting, when the central controller that posses all the information on the agents' locations and goals is absent. We focus on the practically important lifelong variant of MAPF, which involves continuously assigning new goals to the agents upon arrival to the previous ones.
  arXiv  Detail & Related papers  (2023-10-02T13:51:32Z)
• Deep Interactive Motion Prediction and Planning: Playing Games with Motion Prediction Models [162.21629604674388]
  This work presents a game-theoretic Model Predictive Controller (MPC) that uses a novel interactive multi-agent neural network policy as part of its predictive model. Fundamental to the success of our method is the design of a novel multi-agent policy network that can steer a vehicle given the state of the surrounding agents and the map information.
  arXiv  Detail & Related papers  (2022-04-05T17:58:18Z)
• Comprehensive Multi-Agent Epistemic Planning [0.0]
  This manuscript is focused on a specialized kind of planning known as Multi-agent Epistemic Planning (MEP). EP refers to an automated planning setting where the agent reasons in the space of knowledge/beliefs states and tries to find a plan to reach a desirable state from a starting one. Its general form, the MEP problem, involves multiple agents who need to reason about both the state of the world and the information flows between agents.
  arXiv  Detail & Related papers  (2021-09-17T01:50:18Z)
• Anytime Stochastic Task and Motion Policies [12.72186877599064]
  We present a new approach for integrated task and motion planning in settings. Our algorithm is probabilistically complete and can compute feasible solution policies in an anytime fashion.
  arXiv  Detail & Related papers  (2021-08-28T00:23:39Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• Modelling Multi-Agent Epistemic Planning in ASP [66.76082318001976]
  This paper presents an implementation of a multi-shot Answer Set Programming-based planner that can reason in multi-agent epistemic settings. The paper shows how the planner, exploiting an ad-hoc epistemic state representation and the efficiency of ASP solvers, has competitive performance results on benchmarks collected from the literature.
  arXiv  Detail & Related papers  (2020-08-07T06:35:56Z)
• Adaptive Informative Path Planning with Multimodal Sensing [36.16721115973077]
  AIPPMS (MS for Multimodal Sensing) We frame AIPPMS as a Partially Observable Markov Decision Process (POMDP) and solve it with online planning. We evaluate our method on two domains: a simulated search-and-rescue scenario and a challenging extension to the classic RockSample problem.
  arXiv  Detail & Related papers  (2020-03-21T20:28:57Z)
• Model-based Reinforcement Learning for Decentralized Multiagent Rendezvous [66.6895109554163]
  Underlying the human ability to align goals with other agents is their ability to predict the intentions of others and actively update their own plans. We propose hierarchical predictive planning (HPP), a model-based reinforcement learning method for decentralized multiagent rendezvous.
  arXiv  Detail & Related papers  (2020-03-15T19:49:20Z)

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.