Robust and effective multi-agent path execution with timing uncertainty

Liu, Yihao

doi:10.1016/j.artint.2026.104586

Robust and effective multi-agent path execution with timing uncertainty

2026-09-01

0

PRE

AI

DOI：10.1016/j.artint.2026.104586

Original

Original request for help

Save

Abstract

En 中文

In many multi-agent applications, agents such as robots and automated guided vehicles move around concurrently in a shared workspace to carry out tasks. The path plans of agents are typically computed beforehand to avoid collisions and deadlocks. However, in real-world systems, unexpected conditions during plan execution can break the assumptions made in path planning and disturb path execution. In this paper, we develop a robust and effective execution framework of multi-agent path plans to deal with unexpected delays arising from unforeseen circumstances. The framework tracks the evolving locations of agents and dynamically chooses a maximal set of agents to move together while guaranteeing conflict-freeness and deadlock-freeness. To ensure that agents can always reach their destinations, we formulate a feasibility problem to check whether all agents can successfully execute the rest of their path plan when choosing which agents to move. We prove that this problem is NP-complete and design feasibility test algorithms. Leveraging feasibility tests, we further develop algorithms to coordinate agent movements in an online fashion. Several optimizations are also implemented to improve the efficiency and scalability of the feasibility test and coordination algorithms. We experimentally demonstrate the execution effectiveness and computational efficiency of our algorithms.

Keywords:

Multi-agent plan execution

Timing uncertainty

Collision avoidance

Deadlock avoidance

Coordination

Robust and effective multi-agent path execution with timing uncertainty

Abstract

Journal

Organization

Cited Papers