WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning

• URL: http://arxiv.org/abs/2508.01495v1
• Date: Sat, 02 Aug 2025 21:33:08 GMT
• Title: WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning
• Authors: Jingtian Yan, Stephen F. Smith, Jiaoyang Li,
• Abstract summary: Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications.<n>We propose kinodynamic Temporal Plan Graph Planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a kinodynamically feasible plan.<n>Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism.
• Score: 7.2069924323665235
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Planning collision-free paths for a large group of agents is a challenging problem with numerous real-world applications. While recent advances in Multi-Agent Path Finding (MAPF) have shown promising progress, standard MAPF algorithms rely on simplified kinodynamic models, preventing agents from directly following the generated MAPF plan. To bridge this gap, we propose kinodynamic Temporal Plan Graph Planning (kTPG), a multi-agent speed optimization algorithm that efficiently refines a MAPF plan into a kinodynamically feasible plan while accounting for uncertainties and preserving collision-freeness. Building on kTPG, we propose Windowed kTPG (WinkTPG), a MAPF execution framework that incrementally refines MAPF plans using a window-based mechanism, dynamically incorporating agent information during execution to reduce uncertainty. Experiments show that WinkTPG can generate speed profiles for up to 1,000 agents in 1 second and improves solution quality by up to 51.7% over existing MAPF execution methods.

Related papers

• Budget Allocation Policies for Real-Time Multi-Agent Path Finding [11.050047263054985]
  Real-Time MAPF embodies a realistic MAPF setup in which planning and execution are interleaved.<n>Existing solutions to RT-MAPF iteratively call windowed versions of MAPF algorithms in every planning period.<n>We explore different policies for allocating the planning budget in windowed versions of standard MAPF algorithms.
  arXiv  Detail & Related papers  (2025-07-22T08:32:55Z)
• Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning [46.35418789518417]
  Multi-agent pathfinding (MAPF) is a common abstraction of multi-robot trajectory planning problems.<n>We introduce MAPF-GPT-DDG, a decentralized suboptimal MAPF solvers that leverage machine learning.<n>Our experiments demonstrate that MAPF-GPT-DDG surpasses all existing learning-based MAPF solvers.
  arXiv  Detail & Related papers  (2025-06-30T12:34:31Z)
• PGPO: Enhancing Agent Reasoning via Pseudocode-style Planning Guided Preference Optimization [58.465778756331574]
  We propose a pseudocode-style Planning Guided Preference Optimization method called PGPO for effective agent learning.<n>With two planning-oriented rewards, PGPO further enhances LLM agents' ability to generate high-quality P-code Plans.<n>Experiments show that PGPO achieves superior performance on representative agent benchmarks and outperforms the current leading baselines.
  arXiv  Detail & Related papers  (2025-06-02T09:35:07Z)
• Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
  Multi-Agent Path Finding (MAPF) focuses on planning collision-free paths for multiple agents.<n>During the execution of a MAPF plan, agents may encounter unexpected delays, which can lead to inefficiencies, deadlocks, or even collisions.<n>This paper introduces Improved GSES, which significantly accelerates Graph-Based Switchable Edge Search (GSES) through four speedup techniques.
  arXiv  Detail & Related papers  (2024-12-20T13:59:15Z)
• Transient Multi-Agent Path Finding for Lifelong Navigation in Dense Environments [9.000023855628958]
  The Lifelong MAPF (LMAPF) problem is a well-studied online version of MAPF in which an agent receives a new target when it reaches its current target.<n>We propose to solve LMAPF problems by solving a sequence of modified MAPF problems, in which the objective is for each agent to eventually visit its target.<n>We refer to this MAPF variant as Transient MAPF (TMAPF) and propose several algorithms for solving it based on existing MAPF algorithms.
  arXiv  Detail & Related papers  (2024-12-05T15:37:29Z)
• 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)
• Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution [7.2988406091449605]
  We introduce a new graphical representation called a Bidirectional Temporal Plan Graph (BTPG) which allows switching orders during execution to avoid unnecessary waiting time. Experimental results show that following BTPGs consistently outperforms following TPGs, reducing unnecessary waits by 8-20%.
  arXiv  Detail & Related papers  (2023-12-30T20:23:27Z)
• Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding [49.730902939565986]
  Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph. In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally. We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
  arXiv  Detail & Related papers  (2023-12-26T06:57:22Z)
• Robust Multi-Agent Pickup and Delivery with Delays [5.287544737925232]
  Multi-Agent Pickup and Delivery (MAPD) is the problem of computing collision-free paths for a group of agents. Current algorithms for MAPD do not consider many of the practical issues encountered in real applications. We present two solution approaches that provide robustness guarantees by planning paths that limit the effects of imperfect execution.
  arXiv  Detail & Related papers  (2023-03-30T14:42:41Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks. In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
  arXiv  Detail & Related papers  (2022-03-26T20:37:14Z)
• Covert Model Poisoning Against Federated Learning: Algorithm Design and Optimization [76.51980153902774]
  Federated learning (FL) is vulnerable to external attacks on FL models during parameters transmissions. In this paper, we propose effective MP algorithms to combat state-of-the-art defensive aggregation mechanisms. Our experimental results demonstrate that the proposed CMP algorithms are effective and substantially outperform existing attack mechanisms.
  arXiv  Detail & Related papers  (2021-01-28T03:28:18Z)

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.