A replication study of the TA-prioritized algorithm with a modified deadlock avoidance method

Received: 19-Jul-2024, Manuscript No. PULJMAP-24-7118; Editor assigned: 23-Jul-2024, Pre QC No. PULJMAP-24-7118 (PQ); Reviewed: 06-Aug-2024 QC No. PULJMAP-24-7118; Revised: 12-Jan-2025, Manuscript No. PULJMAP-24-7118 (R); Published: 19-Jan-2025

This open-access article is distributed under the terms of the Creative Commons Attribution Non-Commercial License (CC BY-NC) (http://creativecommons.org/licenses/by-nc/4.0/), which permits reuse, distribution and reproduction of the article, provided that the original work is properly cited and the reuse is restricted to noncommercial purposes. For commercial reuse, contact reprints@pulsus.com

Abstract

This paper proposes a modified deadlock avoidance method for the TAprioritized algorithm. Their algorithms were developed for the offline Multi-Agent Pickup and Delivery (MAPD) problems where a team of agents have delivery tasks with known release times (when the tasks are ready for pickup.) Offline MAPD problems exist in settings such as warehouses and factories where the release times of tasks are known in advance make use of this information to compute a good task sequence for each agent using a Travelling Salesman Problem (TSP) solver. The task sequences are then used to plan agent paths accordingly and the deadlock avoidance method proposed attempts holding the pickup locations (keeping an agent stationed at a vertex) if an agent has reached it before the release time and retrying a 1time step delayed path from the agent’s initial parking location if any of the agent’s tasks’ path finding fails.

Keywords

Multi-agent path finding; Generalized task assignment and path finding; Determinism and indeterminism; Complexity theory; Freedom; Epigenetics

Introduction

In an MAPD problem setting there exists multiple robots in a shared environment intending to have the lowest makespan and collision-free paths planned over the entire set of tasks distributed amongst agents. Multi-Agent Path Finding (MAPF) problems are known to be NP-hard, however, they might be computed within polynomial time when treated as a max-flow problem when allowing task goals to be swapped.

The TA-hybrid and TA-prioritized algorithms were designed for an offline setting, where the tasks for an instance and their release times (time that collection is ready) are known before initializing the system. There are also settings of lifelong (online) problems, where tasks are only known to exist after their release times have expired. Online MAPD algorithms such as the one studied may also be used to solve offline problems, however, mention that they do not utilise all of the information and may compute less effective solutions [1-3].

The main objective of this paper is to replace the original "reserving dummy paths" deadlock avoidance method and conclude whether it improves makespans by implementing it for the TA-prioritized algorithm.

Related work

The MAPD problem is related to the Generalized Task Assignment and Path Finding (G-TAPF) problem where each agent may have multiple tasks [4-6]. Proposed using answer set programming to perform both the task assignment and path finding, however, their results found that it only scales to 20 agents and the number of tasks has to be less than the number of agents (Figure 1).

Figure 1) Kiva Robotics system. Now owned by Amazon and used in their sortation centers as an autonomous delivery system

Published a taxonomy paper on task allocation problems with temporal constraint. Described the most related approach as treating the task assignment problem as a Travelling Salesman Problem (TSP) The travelling sales-man problem is a well-known NP-complete problem and pickup and delivery travelling salesman problems receive increasing interest in recent studies [7-9].

The MAPF component has similarly attracted many re- searchers and there are several different methods studied since it is also NP-hard to solve optimally [10]. There exist Anonymous Multi-Agent Path Finding (AMAPF) methods that allow solving the path finding in polynomial time using maxflow algorithms such as for problems where agent goals may be swapped. The MAPF problem may not swap agent goals on the other hand and it may be solved with specialised solvers or other combinatorial methods and are suggested surveys on them.

Materials and Method

Overview

This paper is structured from the following section with the theoretical background of the TA-Prioritized algorithm. The problem is then divided into a two sub-problems: To find good task sequences for each agent using a Travelling Salesman Problem (TSP) solver and then to solve the MAPF for each agent to its allocated tasks’ endpoints. Modifications to the original algorithm’s deadlock avoidance method are then discussed and the algorithm was then implemented and analyzed using the original instance data sets.

Theoretical background

The MAPD problem is formalized as a set of agents, a={a₁, ..., a_M} with a set of task T={t₁, ..., t_N} and an environment as an undirected graph G=(V, E), with vertices V that contain locations of the environment and edges E that permit travelling between possible vertices. Each agent has an assigned parking location p_i ∈ V where the agent is initially located and moves to this location only again once it has finished executing all of its tasks. Each task is characterized by a pickup location (start) s_j ∈ V, delivery location (goal) g_j ∈ V and release time (the time when the pickup is available) r_j ∈ V.

Each agent has to move from its parking location to its first task’s pickup location and may start moving to its delivery location after the release time has expired. Agent paths may wait in a vertex (hold it) for a period of time steps or move to a neighboring vertex if it does not cause a collision. Once an agent reaches its current task’s delivery location, it immediately assigns its next task as its current task and assigns the task’s pickup location as its next endpoint. There are two types of collisions that have to be avoided; the first is called vertex collisions, which occur when two agents occupy the same vertex at a given time step and the second type called edge collisions occur when two agents move to each other’s location within the same time step.

Task assignment

TA-prioritized first computes an ordered task sequence for each agent. The primary objective of MAPD is to minimize the makespan- which is described as the time step when all tasks deliveries are complete.

First construct a directed weighted graph for all the tasks using their endpoint locations and release times to determine the weights. They then use a TSP solver to compute improved sets of task sequences and distribute them among all of the MAPD instance agents.

Directed weighted graph

Constructed a directed weighted graph G′=(V′, E′) with V′=A ∪ T. V′, which contains an integer representing the order of each agent along with integers representing each task of the instance. There are four types of edges in E′, which each have an integer weight reflecting a time step and they are listed below:

The first type, max (dist (p_i , s_j ), r_j), computes the weight as the distance from ai's parking location to its first task’s pickup location sj. If the agent arrives at the pickup location before the task’s release time. The weight is taken as release time instead.

The second edge type, dist (s_i, g_i)+dist (g_i, s_j), computes the edge weight from and agent’s current assigned task’s pickup location si to its delivery location gi and then to its pickup location of its next task s_j.

The third type, dist (s_i, g_i), computes the edge weight from the agent’s last task’s pickup location si to its respective delivery location g_i .

And the last type is an edge with zero weight as the agent has finished its tasks and does not add to the make span any further.

The concept is for G' to be a complete graph that contains Hamiltonian cycles that may be divided into M partitions to allocate a sequence to each agent.

TSP solver

Then made use of the extended Lin Kernighan Helsgaun TSP solver (LKH-3) to improve the Hamiltonian cycles of G′to more efficient sequences of task execution. The graph is loaded and configured as a pickup-and-delivery problem with time windows and the solver is found to deliver good task sequences.

Path finding

Once the task sequences have been computed, TA-Prioritized then performs prioritized path planning based on each agent’s execution time. Solve the Multi Agent Path Finding (MAPF) problem by planning agent paths one by one in decreasing order of their execution times. The algorithm starts by calculating each agent’s execution time by finding paths for its entire sequence. The agent with the highest execution time’s path is stored, while the others are reinitialized to be computed again. The algorithm then finds the next agent with the highest execution time while avoiding collision with the path already found for the previous agent. This cycle continues until each agent’s path for its entire task sequence has been calculated. This approach aims to minimize the number of constraints that higher executiontime agents have to keep the make span minimal.

The paths of each agent are found as a concatenation of sub paths for all of its allocated tasks. The sub paths are computed from the parking location (for the agent’s first task only) or delivery locations to the next task’s pickup location and then another subpath from this pickup location to its respective delivery location. This cycle continues until the last delivery is complete and a subpath is then computed back to the agent’s parking location.

The paths may be found by an A* search in the space of location-time pairs (x, t) and TA-Prioritized plans the paths without backtracking as it avoids deadlocks with a method referred to as "reserving dummy paths". The dummy paths may also be found with an A* search from every sub path’s goal location to the agent’s parking location. The dummy paths are replaced by the agent’s new calculated path to its goal after every iteration and agent paths have to avoid collisions with other agents’ paths and their dummy paths. Agents never move along their dummy paths, except for the last one that takes the agent back to its parking location from its last delivery location. Collision free paths are guaranteed to exist for each agent when the MAPD instance is regarded as well-formed and in this case, no path should not transverse parking locations.

Modifications

Deadlock avoidance modification: The TA-prioritized deadlock avoidance method-"reserving dummy paths", was replaced with modifying the A* search to attempt holding the pickup location of a task for as long as the release-time of the task has not yet expired. If a higher priority agent’s path leads to the same pickup location, the A* search finds a path for the current (lower priority) agent to the nearest safe neighboring vertex of the pickup location (or to other vertices) and finds the path back to the task’s pickup location should it become safe again. The goal is to keep the agent as close as possible to the pickup location, instead of holding the agent’s initial location, which might be constraint more when planning the path back to the pickup location.

Deadlocks still occur and the path planning might fail to find any safe path once the agent gets surrounded by more than one higher priority agent, which results in a failed A* search. When this occurs, the agent path is recalculated after holding the initial parking location for 1-time step.

The original algorithm makes use of the final dummy path to make the agent travel back to its parking location and this modification requires an additional sub-path calculated from the agent’s last delivery location to its parking location (Figure 2 and Table 1).

 

Figure 2) A 33 × 46 grid with 180 agents and 2000 tasks in simulation

Table 1: Small warehouse results

Results and Discussion

The modified TA-Prioritized algorithm was implemented in python 3 and was ran on a PC with an i7 CPU at 2.6 GHz with 16 GB installed RAM. An agent-based modelling framework called Mesa was used to simulate the computed MAPF instances. The source code may be found on GitHub.

The original map, task and TSP sequence instance data were supplied by the authors and used to compute make spans that may be compared to the original results. The runtimes (program execution) captured were considerably larger than the original findings since this implementation was done in Python a dynamically typed programming language as opposed to the original results found with c⁺⁺. The deadlock avoidance modification is expected to reduce the runtimes and since the main objective of MAPD problems is to compute the lowest make spans only the make spans are considered to compare the results (Table 2).

Table 2: Large warehouse results

Small warehouses

The original small warehouse instances were simulated for a total of 500 tasks each. Each instance includes 5 different frequencies of tasks being released and they include frequencies of 1, 2, 5, 10 and 500 tasks per time step. The results show that the modified TA-Prioritized algorithm’s make span was lower than the other algorithms in three more instances than before and its average make span was reduced by 1-time step.

Large warehouses

The original large warehouse instances were simulated for a total of 2000 tasks each. All tasks were released at the first time step. The modified TAPrioritized algorithm’s results almost consistently improved the make spans for the large warehouse instance and the average make span was reduced by 14 time steps.

Conclusion

A modified deadlock avoidance method was proposed in this paper by replacing the original "reserving dummy path" deadlock avoidance method. The modification was implemented for the TA-Prioritized algorithm and the results show a minor improvement for smaller instance make spans and a more significant improvement for the large instance make spans.

The modification was only implemented for the TA-Prioritized algorithm and future work may modify other algorithms that use dummy paths as a deadlock avoidance method to provide a richer set of results for analysis.

References

1. Liu M, Ma H, Li J, et al. Task and path planning for multi-agent pickup and delivery. 2019.

   [Google Scholar]

2. Hönig W, Kiesel S, Tinka A, et al. Conflict-based search with optimal task assignment. 2018.

   [Google Scholar]

3. Ma H, Li J, Kumar TK, et al. Lifelong multi-agent path finding for online pickup and delivery tasks. 2017.

   [Google Scholar]

4. Nguyen V, Obermeier P, Son T, et al. Generalized target assignment and path finding using answer set programming. 2019.

   [Crossref] [Google Scholar]

5. Nunes E, Manner M, Mitiche H, et al. A taxonomy for task allocation problems with temporal and ordering constraints. Robot Auton Syst. 2017;90:55-70.

   [Crossref] [Google Scholar]

6. Osaba E, Diaz F, Onieva E, et al. A parallel meta-heuristic for solving a multiple asymmetric traveling salesman problem with simulateneous pickup and delivery modeling demand responsive transport problems. 2015;557-67.

   [Crossref] [Google Scholar]

7. Helsgaun K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. 2017;12:966-80.

   [Google Scholar]

8. Yoon S, Kim J. Efficient multi-agent task allocation for collaborative route planning with multiple unmanned vehicles. IFAC-PapersOnLine. 2017;50(1):3580-5.

   [Crossref] [Google Scholar]

9. Yu J, LaValle SM. Planning optimal paths for multiple robots on graphs. 2013;3612-7.

   [Crossref] [Google Scholar]

10. Ma H, Koenig S. Optimal target assignment and path finding for teams of agents. 2016.

    [Google Scholar]