Streamlining the Action Dependency Graph Framework: Two Key Enhancements
Joachim Dunkel · 2024
Read Streamlining the Action Dependency Graph Framework: Two Key Enhancements by Joachim Dunkel (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01277.txt.
Introduction
Joachim Dunkel wrote this robotics paper, published in 2024. It sharpens a framework that keeps fleets of robots executing a shared plan in the right order, even when real-world timing goes wrong.
Multi-robot path finding produces plans, but delays can tangle them. The Action Dependency Graph method guards execution by chaining each wait and move to the actions that must come first. The original builder was slow and stuffed the graph with needless links. Dunkel proves wait actions are generally redundant, and dropping them can speed real robot runs. A new builder, Sparse Candidate Partitioning, skips pointless dependencies and cuts construction from quadratic to near-linear time. The paper offers both a leaner theory and a faster tool for warehouse-scale robot teams.
Catalog record
| CREATOR | Joachim Dunkel |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01277
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Streamlining the Action Dependency Graph Framework: Two Key Enhancements Joachim Dunkel Abstract . Multi-Agent Path Finding (MAPF) is critical for coordinating multiple robots in shared environments, yet robust execution of generated plans remains challenging due to operational uncertainties. The Action Dependency Graph (ADG) framework offers a way to ensure correct action execution by establishing precedence-based dependencies between wait and move actions retrieved from a MAPF planning result. The original construction algorithm is not only inefficient, with a quadratic worst-case time complexity it also results in a network with many redundant dependencies between actions. This paper introduces two key improvements to the ADG framework. First, we prove that wait actions are generally redundant and show that removing them can lead to faster overall plan execution on real robot systems. Second, we propose an optimized ADG construction algorithm, termed Sparse Candidate Partitioning (SCP) , which skips unnecessary dependencies and lowers the time complexity to quasi-linear, thereby significantly improving construction speed. 1. Introduction MAPF is a well-known problem in artificial intelligence, where the goal is to find collision-free paths for multiple agents, typically robots, operating in shared environments ( Stern et al. [n.d.]a ) . In real-world applications such as warehouse automation, the complexity of MAPF increases due to dynamic factors like varying robot speeds, unforeseen obstacles, and continuous task generation. While state-of-the-art MAPF solvers can generate feasible plans for large robot fleets in relatively short times, robust execution on physical robots—subject to kinematic and dynamic constraints—remains challenging due to operational uncertainties. In recent years, three key approaches have been developed to address these challenges: (1) Integrate operation uncertainty into the planning process: This includes methods like ( Zhang et al. [n.d.] ) , ( Atzmon et al. [n.d.] ) or ( Chen et al. [n.d.] ) , where the goal is to find k -robust plans (where each agents operational delay will not cause conflicts for k time steps). (2) Predictive control of agents during execution: In this category fall works such as ( Gregoire et al. [n.d.] ) and ( Wen et al. [n.d.] ) . (3) Post-process a plan into a time independent execution policy: These include works such as ( Hoenig et al. [n.d.]b ) and the Action Dependency Graph (ADG) framework, proposed by Hönig et. al ( Hoenig et al. [n.d.]a ) . Due to its simplicity and low communication overhead the ADG -framework has become a commonly used approach, that has since been adopted in different works such as ( Varambally et al. [n.d.] ) , ( Berndt et al. [n.d.]a ) , ( Berndt et al. [n.d.]b ) and ( Liu et al. [n.d.] ) . The ADG ensures robust execution of MAPF -plans by establishing dependencies between actions based on their precedence relations. However, the original ADG construction algorithm exhaustively checks all actions for potential conflicts, leading to a worst-case time complexity of O(n^{2}) , where n is the number of actions. Furthermore, this process results in a graph with many redundant dependencies between actions, leading to unnecessary communication and memory overhead. This paper introduces two key improvements to the ADG framework. First, we prove that wait actions are redundant and can be removed without affecting execution correctness. Furthermore, we show that removing them can lead to faster overall plan execution (makespan) in scenarios where consecutive motion is expected to be faster than stop-and-go behavior. Second, we propose an optimized ADG construction algorithm termed Sparse Candidate Partitioning (SCP) that efficiently skips unnecessary dependencies resulting in a significantly faster construction process and a sparser graph without any redundant dependencies. To the best of our knowledge, no prior work has specifically focused on improving the runtime of ADG construction itself. While in ( Berndt et al. [n.d.]b ) , the authors discuss the conversion of an ADG into a Spatially Exclusive Action Dependency Graph (SE-ADG) that does not contain wait actions, they do not directly drop them nor prove that they are unnecessary. Although solving the MAPF -problem optimally is NP-complete ( Yu and LaValle [n.d.] ) , making it the primary computational bottleneck in MAPF -based systems, our improved ADG construction process still provides meaningful performance gains, especially in systems utilizing fast planning schemes such as Prioritized Planning (PP) ( Erdmann and Lozano-Pérez [n.d.] ) . In lifelong MAPF , where tasks arrive continuously, ADG construction and execution must be performed repeatedly. As a result, the performance improvements we introduce become even more significant. 2. Problem Description In this section, we describe the ADG framework and introduce key concepts and definitions used throughout this paper. Further we will discuss the original ADG construction algorithm and its limitations. The construction of an Action Dependency Graph (ADG) – further referred to as G_{ADG} – begins once a valid MAPF solution \Pi is found. A solution \Pi is a set of k single-agent plans \pi_{i} for each agent (robot) R_{i} . A single agent plan pi_{i} represents a sequence of actions (a_{0},...,a_{n}) that lead R_{i} from its start to its goal vertex. Definition 0. Given a valid MAPF -Solution \Pi , let A be the set of all actions \{a_{0},...,a_{n}\} . An action a\in A is a four-tuple \langle s,g,t,R\rangle with: • s : the start vertex of action a , • g : the goal vertex of action a , • t : the time step at which action a occurs, • R : the agent (robot) performing action a . Note: While an ADG consists of action vertices with additional status information {completed, enqueued, pending}, this is not relevant for the purpose of this paper. For simplicity, we will use the terms "action vertex" and "action" interchangeably. Definition 0. If \Pi is a valid MAPF -Solution , there are no two actions a and b that start or end at the same vertex v and time step t . More formally: for all a,b\in A,\;\text{if }a.t=b.t:\{a.s\neq b.s\lor a.g\neq b.g\} must hold. (Otherwise, \Pi would contain a collision.) Given a valid MAPF -Solution \Pi , all its actions a_{i}\in A are then used to construct the ADG . 2.1. Action Dependency Graph Construction The graph G_{\text{ADG}} is a directed acyclic graph representing the temporal dependencies between actions in a MAPF -Solution \Pi . Actions a\in A represent the vertices of the graph, and dependencies between actions are represented as directed edges. If e.g. there is an edge from action a to b , this means that action b depends on action a and can only be executed after a has been completed. Note that a direct dependency between two actions a and b is denoted as a\to b , meaning b depends on a . An indirect dependency, such as a\to c\to b , is denoted as a\rightsquigarrow b . Since (a\to b) implies (a\rightsquigarrow b) we will consider a direct dependency (a\to b) as a special case of an indirect dependency (a\rightsquigarrow b) . Definition 0. Every consecutive action pair a_{i} and a_{i+1} for the same agent R_{a} is connected by a type1 dependency. Formally: for all a,b\in A , if a.R=b.R\land a.t=b.t-1 then a\to b . The original ADG construction algorithm works as follows: (1) Connect all consecutive actions of the same shuttle with type1 dependencies.