# A Data-driven Human Responsibility Management System

Xuejiao Tang1 Jiong Qiu2(✉)  Ruijun Chen3 Wenbin Zhang4
Vasileios Iosifidis1 Zhen Liu5 Wei Meng6 Mingli Zhang7 and Ji Zhang8
1Leibniz University Hannover  Germany 2Hangzhou Quanshi Software Co  Ltd
China
3National Cheng Kung University 4University of Maryland  Baltimore County  USA
5Guangdong Pharmaceutical University  China 6Beijing Forestry University
China
7McGill University  Canada 8University of Southern Queensland  Australia
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

An ideal safe workplace is described as a place where staffs fulfill
responsibilities in a well-organized order, potential hazardous events are
being monitored in real-time, as well as the number of accidents and relevant
damages are minimized. However, occupational-related death and injury are
still increasing and have been highly attended in the last decades due to the
lack of comprehensive safety management. A smart safety management system is
therefore urgently needed, in which the staffs are instructed to fulfill
responsibilities as well as automating risk evaluations and alerting staffs
and departments when needed. In this paper, a smart system for safety
management in the workplace based on responsibility big data analysis and the
internet of things (IoT) are proposed. The real world implementation and
assessment demonstrate that the proposed systems have superior accountability
performance and improve the responsibility fulfillment through real-time
supervision and self-reminder.

##  I Introduction

Improving the accountability and responsibility awareness has always been
challenging in safety management [1]. A large number of works have been
proposed to avoid safety accidents through study the management methods or
behavior-based system approaches [2, 3, 4, 5]. Wachter et al. [6] propose a
safety management practices and worker engagement system for reducing and
preventing accidents, as well as investigating the significant relationships
between safety system practices and accident rates. In [7], the M.I.M.O.S.
(Methodology for the Implementation and Monitoring of Occupational Safety) is
proposed to evaluate the safety management systems. The results of these
studies have improved the safety management to some extent. However, heavily
relying on human involvement has limited the effects of their systems as to
err is human. On the contrary, data-driven artificial intelligence/machine
learning systems with limited human involvement have become pervasive across
all aspects of different domains [8, 9, 10, 11]. A data-driven system managing
responsibility with limited human involvement is also warranted. What’s more,
as Seok et al. mentioned [12], there exist differences in occupational health
and safety management system awareness in enterprises. Therefore, it is
extremely difficult to execute the safety management completely correct [13,
14]. In addition, the existing responsibility management mechanisms are
ineffective in managing the increasing complexity of the hierarchy in
enterprises [15, 16, 17]. For instance, large enterprises with complex
hierarchy ranging from leadership, supervision to security. The supervision of
safety responsibility fulfillment has been weakened due to the need to
decentralize other tasks, which would result in weak execution for safety
responsibility [18]. Last, timely discovering of risk problems is difficult
when the management hierarchy is too complex [19]. Consequently, a real-time
and comprehensive supervising safety management system with limited human
involvement is urgently needed [20, 21].

To this end, this paper proposes a data-driven human responsibility management
system. The proposed system is driven by responsibility big data with respect
to risk pre-control, potential hazard, and accident handling, which is
collected from the sensors and applications in IoT form as well as the
submitted responsibility lists and responsibility fulfillment data by users.
Analyzing the risk level and risk source of collected data, the dynamic
knowledge-based responsibility sets of each unit (department) are defined. In
addition, the directed acyclic graph (DAGs) is applied to sort out the
relationship (supervise and be supervised, superior and subordinate, etc.)
among responsibility nodes (an item in the responsibility list). Furthermore,
the boundaries of responsibility used to clarify responsibilities of each unit
(department) are automatically defined by combing the related responsibility
sets of various positions. Besides, the proposed system reminds the staff to
complete responsibilities according to the risk level or task cycle. Compared
to human supervision, the proposed system aims to achieve higher management
efficiency and real-time supervision.

##  II SYSTEM DESIGN

Figure 1 shows the proposed system structure. The data regarding risk,
potential hazards, and accidents are collected using IoT or manually input.
The safety management system analyzes the collected data and signals smart
indicators providing in the system GUI to reflect the status of responsibility
completion and ensuring a safe workplace. The following subsection outlines
the related definitions and key functions of the proposed system which enable
the smart implementation of safety management.

Figure 1: The structure of system.

###  II-A Related Definitions

  1. 1.

Boundaries of responsibility are defined to clarify the boundaries of
accountability. They consist of the responsibility id, the original source of
responsibility rules (regarding legal and other rules of safety management),
the upper boundary of responsibility, the lower boundary of responsibility,
classify rules of responsibility, relative cases.

  2. 2.

Responsibility sets are the responsibility data sets of each unit (department)
collected by IoT and the way that the staffs submit responsibility fulfillment
data and set the necessary responsibility lists. Concretely, a responsibility
set contains responsibility data of all positions in a related department.
Moreover, a position is defined by various task items. Each task item is
defined as a responsibility node. To better sort out the relationship among
responsibility nodes, the DAGs are applied for a weighted relationship graph.
The responsibility sets are defined by position id, superior position,
subordinate position sets, primary responsibility category (major
responsibility lists of each position), boundaries of responsibility, task
type, trigger method, the hierarchy of responsibility category (subject
responsibility, supervision responsibility, leadership responsibilities),
senior position responsibility set, subordinate position responsibility set,
risk id.

  3. 3.

Responsibility big data contains all of the input data along with processing
data. Input data include IoT collected data and submitted data by users.
Processing data such as data from boundaries of responsibility, responsibility
attributes (completion progress, process evidence, regulatory evidence,
consensus, assessment of completion), and responsibility sets (responsibility
process data, responsibility coarseness calculation, relational superposition
of directed acyclic graph, risk level analysis), are yield during system
running.

###  II-B Quantifying Responsibility

Quantifying responsibility is an efficient way to clarify the
responsibilities, supervisory responsibilities, and leadership
responsibilities of relevant positions in various industry departments. First,
the legal and professional responsibilities of various industries can be
declared in the system by defining responsibility sets. Next, the
responsibility sets of each department will redefine the responsibility lists
for each position. Sequentially, DAGs is applied among various task items
which are added in responsibility lists to sort out the relationship among
same level staffs, superior, and subordinate along with relationship among
various departments. Besides, the responsibility lists with weight, task
cycle, and evaluation rules information are precisely clarified to each
position. Thus, each position obtains a set of qualifying responsibility
lists. The responsibility lists are defined by different parameters (time,
space, responsible region, etc). For different industries, especially the
hazardous chemical industry, hazard monitoring and risk assessment are crucial
for maintaining a safe workplace. The potential risks should be considered as
a factor while designing the system so that responsibility lists contain the
corresponding responsibility items. The detailed steps are as follows:

  * •

`Step 1`: Create the responsibility sets and relevant boundaries of
responsibility.

  * •

`Step 2`: Sort out the hierarchy of the enterprises and identify the risk
source and risk level of each position, then update the responsibility sets in
Step 1 based on risk analysis of regarding positions.

  * •

`Step 3`: Analyze the risk level in responsibility sets to automatically
update the configuration of responsibility lists, such as responsibility
cycle, trigger method, etc. (see Figure 3).

  * •

`Step 4`: Create corresponding supervision responsibility lists based on the
risk level of responsibility lists of each position.

  * •

`Step 5`: Set the data collection method (by IoT sensors or manually input).

  * •

`Step 6`: Check if responsibility nodes (task items in responsibility lists)
exists in the collected data. In case of a responsibility node is an item in
collected responsibility data, link it to the relevant position. Otherwise,
the system will connect them with referring responsibility lists of multiple
positions.

  * •

`Step 7`: Generate a configuration list of DAG (Directed Acyclic Graph) [22]
for different levels of regulatory responsibility lists and subject
responsibility lists.

  * •

`Step 8`: Check responsibility performance status of positions with respect to
risk level. In case the performance status cannot meet requirements, back to
Step 3 - Step 7.

###  II-C Responsibility Evaluation and Supervision

This stage refers to the submission of responsibility fulfillment and
supervision data for the scoring process. Two components, the Internet of
Responsibilities and the Internet of Things, are involved herein. The
responsibility data and IoT [23] data, which reflect the responsibility
execution and machine running status, respectively, are collected by the
proposed system. Thus, the fulfillment score will be evaluated, based on the
status of responsibility fulfillment. Besides, the self-reminder module
supervises the completion status of responsibility and reminds the staff to
complete tasks on deadline or at a high risky level that can result in
accidents. The self-reminder works as follows:

  * •

`Step 1`: List all task items should be reminded.

  * •

`Step 2`: Check each task item. Identify its attribute such as non-periodic
and periodic tasks.

  * •

`Step 3`: In case of a non-periodic task, check whether the task data is
valid. If valid, sort the task into the list sets without self-reminders.
Otherwise, sort the tasks into the reminder list sets.

  * •

`Step 4`: In case of the periodic task, check the executed status, score
status, and supervision status. If the execution is complete and the score is
evaluated, sort it into the list that does not need to be reminded. Otherwise,
add the tasks in the reminder list set and ranked them by the score.

  * •

`Step 5`: For the reminder list sets, check the expiration time of each task
then prioritize by the expiration time.

The evaluation process is detailed as below:

  * •

`Step 1`: Obtain data from the submitting by user or IoT applications
automatically.

  * •

`Step 2`: Check the type of responsibility lists, if it is mandatory, check
the current status.

  * •

`Step 3`: If the current status can not result in risky accidents, score the
corresponding tasks directly.

  * •

`Step 4`: Check if there are other extension works and explain their benefits.
The staffs can self-evaluate the corresponding score, and the score will be a
part of the final results.

  * •

`Step 5`: Check whether existing any supervisory responsibility, if there is
supervision responsibility, submit supervision fulfillment data.

  * •

`Step 6`: When the supervision data are submitted, the result of the
supervisory is also considered for scoring. If the supervisory score is less
than 50 percent of overall supervisory scores, the corresponding task
completion score will be deducted in the same period.

  * •

`Step 7`: Summarize the corresponding scores to get the recommended scores for
each responsibility list.

  * •

`Step 8`: The real-time responsibility score is evaluated during the
execution.

###  II-D Scoring and Reporting

The responsibility score of personnel will be reported weekly or monthly. The
staffs with low responsibility scores will be reminded automatically. And the
relevant departments will also be informed. The overall workflow is shown
below:

  * •

`Step 1`: Analyze the current incident.

  * •

`Step 2`: List responsibility sets for accountability based on the
responsibility lists and responsibility boundaries.

  * •

`Step 3`: Determine the necessary positions of the enterprises based on the
assessments of incidents.

  * •

`Step 4`: List all the responsibility sets relevant to all of the
responsibility data.

  * •

`Step 5`: List positions with relatively low scores.

  * •

`Step 6`: Analyze the correlation between the positions and responsibility
lists among the staffs with relatively low scores.

  * •

`Step 7`: Rank personnel with low scores and start the process of holding
accountable.

##  III PRACTICAL APPLICATION

This paper has demonstrated the proposed system through a specific use case in
a shopping mall. The responsibility lists and the completion status of
responsibilities are visualized in the GUI interface. The type and evaluation
method of responsibilities can be set in the system (see Figure 3 and Figure
4). Also, an analysis result with weighted information will be given by the
system to help improve safety management.

###  III-A Application for Quantifying Responsibility

Figure 2: The responsibility lists of duty officer.

With the specified responsibility list of different positions, the
responsibility lists of duty officer are shown in Figure 2. Clicking the
“View” button of a specific task in each row, the items of the selected
responsibility list will be shown. Further clicks each responsibility list
item, the configuration will be shown in Figure 3 and Figure 4, where the
attributes of the task type and evaluation method can be configured manually,
such as setting the primary responsibility or the secondary responsibility. In
addition, the risk level and cycle type (periodic or aperiodic) are listed in
the items. If the task is periodic, the periodical information with the
minimum cycle and the score weight can be set. The source data ( such as
photos, documents, audio (sound recordings), videos, etc.) can be collected by
IoT or manual input. Besides, the responsibility can be scored automatically,
by evaluation or by voting.

Figure 3: The task type configuration of responsibility list. Figure 4: The
evaluation method configuration of responsibility list.

###  III-B Evaluation and Supervision Process

Figure 5: Completion status of responsibility lists. Figure 6: A fire alarm.

Figure 5 shows the completion status of responsibility list. The incomplete
items will be sorted according to the urgency degree and the weight of the
task. Process data can be obtained from the IoT module. Figure 6 shows a fire
alarm example, duty officer informs the patrols once the fire alarms go off.
After patrols are notified successfully, notification data with processing
start and end time will be submitted in the system.

###  III-C Quantifying Accountability

Figure 7: The scoring process.

As shown in Figure 7, the scoring composition is evaluated by measuring task
completion and performance assessment. Besides, the task completion status is
determined by assigned task scores and attendance scores, which could quantify
the performance of responsibilities for each position.

As shown in Figure 8, personal responsibility scores can be sorted by overall
and department ranking. The ranking results could be one of the performance
evaluation basis.

Figure 8: The score ranking.

Figure 9 shows the personnel’s responsibility scores, which would change by
time. The scores are evaluated in various aspects which intuitively reflect
the effect and timeliness of responsibility completion. Furthermore, the DAGs
[24] graph with responsibility weight information in Figure 10 sorts out the
relationship between positions and responsibility nodes, which can improve the
efficiency and accuracy of accountability. Based on the weight information,
the status of responsibilities execution can be measured and visualized.

Figure 9: Personnel’s responsibility score curves. Figure 10: DAGs with
responsibility weight information.

##  IV Conclusion

The proposed system aims at improving safety management in enterprises. The
practical applications show its performance in various aspects, such as
collecting data by using IoT, analyzing responsibility data and accountability
items from multiple perspectives (risk pre-control, troubleshoot potential
hazards, accident handing), visualization of the evaluation score, and
supervision the responsibility fulfillment. In the practical application in a
shopping mall, the proposed system visualizes the responsibility lists and the
completion status of responsibility lists. Also, in case of an emergency such
as a fire, the system will automatically alarm and send messages to notify the
staff, so that the problems can be solved timely. In this way, the probability
of accidents is greatly reduced. Moreover, the system evaluates the
responsibility score by responsibility data and clarifies the results by
visualized ranking results and curve diagram. Furthermore, the DAGs with
responsibility weight information can clearly reflect the problems in safety
management.

## References

  * [1] E. Gerede, “A study of challenges to the success of the safety management system in aircraft maintenance organizations in turkey,” _Safety science_ , vol. 73, pp. 106–116, 2015.
  * [2] K. e. a. Lee, “Improvements of safety management system in korean chemical industry after a large chemical accident,” _Journal of loss prevention in the process industries_ , vol. 42, pp. 6–13, 2016.
  * [3] W. Zhang, “Phd forum: Recognizing human posture from time-changing wearable sensor data streams,” in _2017 IEEE International Conference on Smart Computing (SMARTCOMP)_. IEEE, 2017, pp. 1–2.
  * [4] M. Fernández et al., “Safety management system: Development and validation of a multidimensional scale,” _Journal of Loss Prevention in the process Industries_ , vol. 20, no. 1, pp. 52–68, 2007.
  * [5] W. Zhang and J. Wang, “A hybrid learning framework for imbalanced stream classification,” in _2017 IEEE International Congress on Big Data (BigData Congress)_. IEEE, 2017, pp. 480–487.
  * [6] J. K. Wachter and P. L. Yorio, “A system of safety management practices and worker engagement for reducing and preventing accidents: An empirical and theoretical investigation,” _Accident Analysis & Prevention_, vol. 68, pp. 117–130, 2014.
  * [7] A. Saracinoet al., “A new model for evaluating occupational health and safety management systems (ohsms),” _Chemical engineering transactions_ , vol. 26, pp. 519–524, 2012.
  * [8] W. Zhang and E. Ntoutsi, “Faht: an adaptive fairness-aware decision tree classifier,” in _Proceedings of the 28th International Joint Conference on Artificial Intelligence_. AAAI Press, 2019, pp. 1480–1486.
  * [9] W. Zhang, J. Wang, D. Jin, L. Oreopoulos, and Z. Zhang, “A deterministic self-organizing map approach and its application on satellite data based cloud type classification.” IEEE Big Data, 2018, pp. 2027–2034.
  * [10] W. Zhang, J. Tang, and N. Wang, “Using the machine learning approach to predict patient survival from high-dimensional survival data.” BIBM, 2016, pp. 1234–1238.
  * [11] W. Zhang, X. Tang, and J. Wang, “On fairness-aware learning for non-discriminative decision-making,” in _2019 International Conference on Data Mining Workshops (ICDMW)_. IEEE, 2019, pp. 1072–1079.
  * [12] S. Yoon et al., “Effect of occupational health and safety management system on work-related accident rate and differences of occupational health and safety management system awareness between managers in south korea’s construction industry,” _Safety and health at work_ , 2013.
  * [13] A. J. Stolzer, M. C. D. Halford, and M. J. J. Goglia, _Safety management systems in aviation_. Ashgate Publishing, Ltd., 2015.
  * [14] W. Zhang and J. Wang, “Content-bootstrapped collaborative filtering for medical article recommendations.” BIBM, 2018, pp. 1184–1188.
  * [15] M. Bovens _et al._ , _The quest for responsibility: Accountability and citizenship in complex organisations_. Cambridge university press, 1998.
  * [16] W. ElMaraghy, H. ElMaraghy, T. Tomiyama, and L. Monostori, “Complexity in engineering design and manufacturing,” _CIRP annals_ , 2012.
  * [17] L. Zhang and W. Zhang, “A comparison of different pattern recognition methods with entropy based feature reduction in early breast cancer classification,” 2014\.
  * [18] S. Waddock and C. Bodwell, _Total responsibility management: The manual_. Routledge, 2017.
  * [19] P. Dobers, “Corporate social responsibility: management and methods,” _Corporate Social Responsibility and Environmental Management_ , vol. 16, no. 4, pp. 185–191, 2009.
  * [20] X. Tang et al., “The internet of responsibilities-connecting human responsibilities using big data and blockchain.” IEEE Big Data, 2019.
  * [21] R. Chen, J. Qiu, X. Tang, and W. Zhang, “Responsibility management through responsibility networks,” 2020.
  * [22] D. Colombo, M. H. Maathuis, M. Kalisch, and T. S. Richardson, “Learning high-dimensional directed acyclic graphs with latent and selection variables,” _The Annals of Statistics_ , pp. 294–321, 2012.
  * [23] J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami, “Internet of things (iot): A vision, architectural elements, and future directions,” _Future generation computer systems_ , vol. 29, no. 7, pp. 1645–1660, 2013.
  * [24] T. J. VanderWeele and J. M. Robins, “Directed acyclic graphs, sufficient causes, and the properties of conditioning on a common effect,” _American journal of epidemiology_ , vol. 166, no. 9, pp. 1096–1104, 2007\.


# Caching-Augmented Lifelong Multi-Agent Path Finding

Yimin Tang1∗, Zhenghong Yu2∗, Yi Zheng1, T. K. Satish Kumar1, Jiaoyang Li3,
Sven Koenig1 ∗Equal Contribution1University of Southern California, 3650
McClintock Ave, Los Angeles, CA 90089<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>University, 393 Middle Huaxia
Road, Shanghai 201210<EMAIL_ADDRESS>Mellon University,
5000 Forbes Ave, Pittsburgh, PA 15213<EMAIL_ADDRESS>
###### Abstract

Multi-Agent Path Finding (MAPF), which involves finding collision-free paths
for multiple robots, is crucial in various applications. Lifelong MAPF, where
targets are reassigned to agents as soon as they complete their initial
targets, offers a more accurate approximation of real-world warehouse
planning. In this paper, we present a novel mechanism named Caching-Augmented
Lifelong MAPF (CAL-MAPF), designed to improve the performance of Lifelong
MAPF. We have developed a new type of map grid called cache for temporary item
storage and replacement, and designed a locking mechanism for it to improve
the stability of the planning solution. This cache mechanism was evaluated
using various cache replacement policies and a spectrum of input task
distributions. We identified three main factors significantly impacting CAL-
MAPF performance through experimentation: suitable input task distribution,
high cache hit rate, and smooth traffic. In general, CAL-MAPF has demonstrated
potential for performance improvements in certain task distributions, maps,
and agent configurations.

##  I INTRODUCTION

Automated warehouses represent a multibillion-dollar industry led by
corporations such as Amazon, Alibaba, Ocado, and inVia. These facilities
deploy hundreds of robots to transport goods from one location to another [1].
Planning collision-free solutions for hundreds of robots is a key component of
these automated warehouses, and can be simplified to a multi-agent path
finding problem (MAPF) [2]. The MAPF problem requires planning collision-free
paths for multiple agents from their start locations to pre-assigned target
locations in a known environment while minimizing a given cost function. Many
algorithms have been developed to solve this problem optimally and
suboptimally, such as Conflict Based Search (CBS) [3], $M^{*}$, [4] and
Enhanced CBS (ECBS) [5].

Although MAPF is classified as an NP-hard problem [6], it still represents a
simplistic approximation of actual warehouse planning. It is the ’one-shot’
version of the real application challenge, where an agent only needs to reach
one target location and remains stationary until every participant has arrived
at their respective targets. To address this limitation, an advanced version
called Multi-Agent Pickup and Delivery (MAPD) or Lifelong MAPF [7] has been
introduced. This version reassigns targets to agents once they complete their
initial objectives, better reflecting continuous operational scenarios.
Various algorithms, such as RHCR [8], MAPF-LNS [9], PIBT [10], and LaCAM [11],
have been created and applied in practical environments.

Although many studies focus on developing effective algorithms, there is also
interest in improving the throughput of automated warehouses within the
Lifelong MAPF framework by optimizing warehouse layouts. Prominent approaches
include Fishbone design [12], DSAGE [13], and GGO [14]. However, these works
mainly focus on static storage design and do not consider input distributions
with specific patterns that may change over time. To address this problem,
some studies have explored intelligent decision-making strategies [15, 16,
17]. Notable examples include the Kiva system and various policies, such as
the velocity-based policy [16], and mixed-integer optimization and heuristic
methods [18]. However, these methods are designed for specific warehouse
systems, making it difficult to apply them to different warehouse types. They
also require implementing complex rearrangement policies for the entire
warehouse storage.

In this paper, we present a dynamic cache delivery mechanism named Caching-
Augmented Lifelong MAPF (CAL-MAPF), inspired by cache design, a foundational
element extensively utilized in computer architecture, databases, and various
other domains. This cache mechanism is adaptable to various Lifelong MAPF
algorithms, warehouse storage strategies, and incoming task distributions. We
have developed a novel map grid type that allows items to be temporarily
stored and replaced. Additionally, we design a lock mechanism to enhance the
stability of the planning solution. We have evaluated this cache mechanism
using different cache replacement policies and a range of input task
distributions. Through experimentation, we identified three main factors that
significantly impact CAL-MAPF performance: input task distribution, cache hit
rate, and map design. In general, CAL-MAPF has demonstrated potential for
performance improvements in certain task distributions and map and agent
configurations.

##  II Problem Definition

Lifelong Multi-Agent Path Finding (Lifelong MAPF) problem presents unique
challenges due to the dynamic and unending nature of the tasks. Following the
terminology in the MAPF community, we use agents to refer to robots. Let
$I=\\{1,2,\cdots,N\\}$ denote a set of $N$ agents. $G=(V,E)$ represents an
undirected graph, where each vertex $v\in V$ represents a possible location of
an agent in the workspace, and each edge $e\in E$ is a unit-length edge
between two vertices that moves an agent from one vertex to the other. Self-
loop edges are allowed, which represent “wait-in-place” actions. Each agent
$i\in I$ has a unique start location $s_{i}\in V$. Assume there is an task
queue $Q=[q_{1},q_{2},...]$. For each task $q_{i}\in Q$, $q_{i}$ represents a
certain item located in a reachable vertex in $V$ where at least one agent can
find a path to the vertex. Each item must be delivered to a vertex in $V$ as
the user specifies. These tasks are generated from a specific probability
distribution to enhance realism.

Figure 1: Caching-Augmented Map: (1) Blue grids represent Shelves $S$. (2)
Purple grids represent Caches $C$. (3) Green grids represent unloading ports
$U$. The upper map has multiple ports, while a single port is in the bottom
one. In the multi-port map, each unloading port has an independent cache area,
task queue, and agents. The cache areas are near the unloading ports within
$\pm 2$ rows. For the single-port map, the port can utilize all agents and all
caches. Given that the number of cache grids can affect the cache hit rate, we
also tested different numbers of cache grids, ranging from 80 to 16, by
removing cache grids column by column from right to left.

We study an on-line setting in which incoming tasks are not known in advance.
It is assumed that there is a task assigner (external to low-level MAPF
algorithm) from which agents can request target locations throughout the
system’s operation. The task assigner determines the specific target locations
for agents based on tasks in $Q$. In our paper, this task assigner is
considered naive and will return the target location based on the first
unfinished task in $Q$. Each agent $i\in I$ starts from a start location
$s_{i}\in V$ and its target location depends on the task assigner. As agents
complete their paths at their assigned goals, they are immediately assigned
new targets, reflecting warehouse operations’ perpetual and iterative nature.
Each action of agents, waiting in place or moving to an adjacent vertex, takes
a unit of time. An agent’s path,
$p^{i}=[v_{0}^{i},v_{1}^{i},\ldots,v_{T_{i}}^{i}]$, tracks the sequence of
vertices traversed by agent $i$ from its start to its target.

As shown in Figure 1, we primarily focus on 2D warehouse layout maps and
categorize all non-obstacle map grids into three types: blue grids
$S=\\{s_{i}|s_{i}\in V\\}$ for shelves that store items, white grids
$W=\\{w_{i}|w_{i}\in V\\}$ for normal aisle grids, and green grids
$U=\\{u_{i}|u_{i}\in V\\}$ for unloading ports where agents deliver items to
complete a task. Agents can enter $S$ positions only from $W$ positions.
Direct transitions between two positions in $S$ are not allowed.

Next, we will introduce specific assumptions in this paper beyond the standard
Lifelong MAPF definition. We assume each shelf $S$ stores an infinite number
of only one unique type of item. There will be a total of $M$ different types
of items corresponding to the number of shelves. Each unloading port $u_{k}$
is associated with an independent task queue $Q_{k}$. Each task $q_{i}\in
Q_{k}$ must be delivered to the unloading port $U_{k}$.

We will also involve a new type of map grid: caches. These additional
vertices, designated as $C=\\{c_{i}|c_{i}\in V\\}$ in purple, serve as interim
storage areas to streamline the completion of tasks by reducing the travel
time of the agents retrieving items. To the best of our knowledge, no previous
MAPF works have explored this new cache mechanism, so we adopt the following
simplifying assumptions: (1) The warehouse is considered to have an unlimited
supply of items, eliminating worries about stock running out. (2) Agents have
infinite capacity to carry items. However, they are limited to transporting
one type of item at a time, enabling them to move any quantity of that
specific item without restriction. (3) Items removed or evicted from the cache
are treated as if they vanish immediately.

##  III Related work

###  III-A MAPF

(One-Shot) MAPF, which has been proved an NP-hard problem with optimality [6],
has a long history [19]. It has inspired a wide range of solutions for its
related challenges. Decoupled strategies, as outlined in [19, 20, 21],
approach the problem by independently planning paths for each agent before
integrating these paths. In contrast, coupled approaches [22, 23] devise a
unified plan for all agents simultaneously. There also exist dynamically
coupled methods [3, 24] that consider agents that are planned independently at
first and then together only when needed in order to resolve agent-agent
conflicts. Among these, Conflict-Based Search (CBS) algorithm [3] stands out
as a centralized, optimal solution for MAPF, with several bounded-suboptimal
variants such as ECBS [5] and EECBS [25]. Some suboptimal MAPF solvers, such
as Prioritized Planning (PP) [26, 19], PBS [27], PIBT [10] and their variant
methods [28, 29, 11, 30] exhibit better scalability and efficiency.

###  III-B Lifelong MAPF

Compared to the MAPF problem, Lifelong MAPF continuously assigns new target
locations to agents once they have reached their current targets. It is not
necessary for agents to arrive at their targets simultaneously in Lifelong
MAPF. There are mainly three kinds of methods: solving the problem as a whole
[31], using MAPF methods but replanning all paths at each specified length
timestep [8, 10], and replanning only when agents reach their current target
locations and are assigned new targets [32, 33, 11, 30]. Among them, MAPF-LNS
[9, 29] and LaCAM [11, 30] are the leading methods with high performance in
task execution.

###  III-C Cache

The cache [34] serves as a crucial hardware component designed to temporarily
store data, enhancing the efficiency of future request processing. Its main
goal is to speed up access to frequently used data, thus minimizing dependence
on slower storage disks. Popular caching policies include Least Recently Used
(LRU) [35] and First-In-First-Out (FIFO) [36], with studies indicating LRU’s
superiority over FIFO [37, 38, 39]. The caching concept is widely applied in
various fields, such as Databases [40] and Content Delivery Networks (CDN)
[41].

###  III-D Warehouse Storage Strategy

Automated Storage and Retrieval Systems (AS/RS) have attracted attention for
their potential to enhance warehouse efficiency and reduce operational costs
[42, 43]. Various strategies for assigning items to storage locations have
been widely adopted and evaluated [43, 44]. The random storage policy
allocates each item type to a randomly chosen storage location and offers high
space utilization [45]. The policy for storage at the closest open location
places the arriving unit of items at the nearest available storage location,
minimizing the immediate travel distance [46, 47]. The turnover-based storage
policy assigns storage locations to each item based on their demand frequency
[16, 17].

Figure 2: Status 0: If the agent’s task item is not in the cache when
assigned, it must retrieve the item from a shelf. Status 1: If the agent’s
task item is in cache when assigned, it should retrieve the item from the
cache. Status 2: If at least one writable cache exists when the agent
retrieves the item from the shelf, the agent needs to insert the item into
cache. Status 3: If no writable cache is available when an agent gets the item
from the shelf, the agent goes to the unloading port. Status 4: After
retrieving or inserting the item from/to the cache, the agent heads to the
unloading port.

##  IV Method

In this section, we introduce our novel Caching-Augmented Lifelong MAPF (CAL-
MAPF) framework along with a cache lock mechanism. Consider a warehouse
scenario as depicted in Figure 1. When the task assigner encounters a new task
requiring completion, the first step typically involves determining which
location should be allocated to an available agent. The task assigner first
checks whether the task item is already stored in the cache grids. If located,
the task assigner will direct agents to retrieve the item from the cache grid
and deliver it to the unloading port, or alternatively, the agent may need to
collect the item from the shelves. Subsequently, the item is stored in a cache
grid. Once stored, the agent can transport the item from the cache to an
unloading port.

However, similar to caching in computer architecture, there is a risk that
other agents could replace an item in the cache before it being retrieved by
assigned agents in multi-agent scenarios. This situation could result in a
low-level MAPF algorithm, such as LaCAM, generating unusual collision-free
plans at each timestep, causing agents to move back and forth between two
adjacent grids. Thus, a lock mechanism ensures agents can secure an item after
confirming its availability in cache grids.

To ensure efficient and synchronized access to cache locations in the CAL-MAPF
framework, we implement a cache lock mechanism supported by a state machine.
This approach effectively prevents race conditions during cache interactions.
The mechanism uses read locks for agents fetching items and writes locks for
agents updating the cache, with the state machine managing transitions to
maintain access order and integrity. Every cache grid will have its
independent read lock and write lock. This streamlined system guarantees that
agents can safely access and modify cache contents, facilitating seamless task
execution within the dynamic warehouse environment.

###  IV-A Cache Lock Mechanism

####  IV-A1 Lock Types

The cache lock mechanism is designed around two principal lock types,
facilitating controlled access to the cache locations: (1) Read Lock (Shared
Lock): This type of lock permits an agent to access a cache location to
retrieve items. Multiple agents can simultaneously hold a read lock on a
single cache location as long as no write lock is active on that location.
This arrangement ensures that when agents need to retrieve items from the
cache, the item remains unchanged until all agents have successfully retrieved
it. (2) Write Lock (Exclusive Lock): An agent is required to secure a write
lock prior to inserting an item into a cache location. Write locks are
exclusive, implying that once an agent possesses a write lock on a cache
location, no other agent can acquire either a read lock or another write lock
on that location. This ensures that an agent can insert an item without
impacting other agents.

####  IV-A2 Lock Acquisition and Release

The mechanism defines a protocol for lock acquisition and release: (1)
Acquisition: To obtain a read lock, an agent must verify that no write lock is
active on the desired cache location. Conversely, to secure a write lock, an
agent must confirm that the target cache location is free from any active read
or write locks. (2) Release: Agents release read locks after successfully
retrieving the goods. Agents release write locks once they have updated the
cache, making the new items available to others.

The cache lock mechanism ensures that no agent needs to return to shelf when
its target location is in cache or unloading port, no two agents access the
same cache block concurrently for writing, and multiple agents may read from
the same cache block concurrently if no write lock is active. This concurrency
control is critical to prevent race conditions and maintain the cache’s
consistency.

Algorithm 1 CAL-MAPF with One Group Overview

Input: Map $G$, Initial Locations $S=s_{i}$, Task Queue $Q$, Agents $A$

1:portLoc = getPortLoc(G)

2:for agent in agents do

3: agent.startLoc = $s_{i}$

4: agent.task = Q.pop()

5: agent.targetLoc = getMapLoc(agent.task)

6: agent.status = 0

7:while not $Q$.empty() do

8: plan = MAPF(agents)

9: agents.excute(plan)

10: AgentReleaseLocks(agents, cache)

11: AgentGetLocks(agents, cache)

Algorithm 2 Task Assigner Functions

1:function AgentReleaseLocks(agents, cache)

2: for agent in agents do

3: agent.startLoc = plan.endLoc[agent]

4: if agent.targetLoc == agent.startLoc then

5: if agent.status == 1 or 2 then

6: agent.status = 4

7: cache.releaseAllLock(agent)

8: agent.targetLoc = portLoc

9:function AgentGetLocks(agents, cache)

10: for agent in agents do

11: if agent.status == 0 then

12: if agent.targetLoc == agent.startLoc then

13: targetLoc = cache.insert(agent)

14: CheckTarget(agent, targetLoc, 3, 2)

15: else

16: targetLoc = cache.check(agent)

17: CheckTarget(agent, targetLoc, 0, 1)

18: continue

19: if agent.status == 3 then

20: if agent.targetLoc == agent.startLoc then

21: AgentReachPort(agent)

22: else

23: targetLoc = cache.insert(agent)

24: CheckTarget(agent, targetLoc, 3, 2)

25: continue

26: if agent.status == 4 then

27: if agent.targetLoc == agent.startLoc then

28: AgentReachPort(agent)

29:function AgentReachPort(agent)

30: agent.task = Q.pop()

31: targetLoc = cache.check(agent)

32: CheckTarget(agent, targetLoc, 0, 1)

33:function CheckTarget(agent, targetLoc, statusa, statusb)

34: if targetLoc == portLoc then

35: agent.status = statusa

36: else

37: agent.status = statusb

38: agent.targetLoc=targetLoc

Algorithm 3 Cache Operation Functions

1:function releaseAllLock(agent)

2: cacheGrid = findCache(agent.startLoc)

3: cacheGrid.item = agent.task

4: cacheGrid.readLock.remove(agent)

5: cacheGrid.writeLock.remove(agent)

6: incoming.remove(taskItemId)

7:function Check(agent)

8: for cacheGrid in cache.allGrids do

9: noWrite = cacheGrid.writeLock.empty()

10: hasItem = cacheGrid.item == agent.task

11: if noWrite and hasItem then

12: cacheGrid.readLock.add(agent.id)

13: return cacheGrid.loc

14: return portLoc

15:function Insert(agent)

16: isInCache = cache.findItem(agent)

17: isIncoming = incoming.find(agent.task)

18: if isInCache or isIncoming then

19: return portLoc

20: cacheGrid = cache.findEmptyCache()

21: if cacheGrid != -1 then

22: cacheGrid.writeLock.add(agent.id)

23: return cacheGrid.loc

24: candidates = sortByCacheEvitedPolicy(cache.allGrids)

25: for cacheGrid in candidates do

26: if cacheGrid.readLock.empty() then

27: if cacheGrid.writeLock.empty() then

28: incoming.append(agent.task)

29: cacheGrid.writeLock.add(agent.id)

30: return cacheGrid.loc

31: return portLoc

###  IV-B Algorithm

As shown in Algorithms 1, 2 and 3, the whole procedure is mainly based on the
task assigner, who encounters new tasks and decides what locations the agents
need to visit. As illustrated in Figure 1, CAL-MAPF could have multiple
unloading ports and we call each unloading port and cache around the port a
group. Each group is independent in task queue, cache grids, and agents.
Agents in one group can only accept tasks from this group and use cache grids
of this group. Algorithm 1 illustrates the operation of a group. Task assigner
uses a state machine to control agent status and how they transfer to another
based on different situations. When any agent reaches its target location, we
must check all agents, update their status, and assign new target locations.

The state machine is illustrated in Figure 2, and the pseudocode of Algorithm
1 outlines how an agent transitions through five states while performing the
low-level MAPF algorithm for a group. The task assigner monitors and updates
the status of agents based on the item’s location, the state of the cache, and
the agents’ current status. This algorithm ensures the efficient completion of
all tasks by orchestrating the agents’ paths and their interactions with the
cache and unloading port.

Figure 3: The average frequency of agent wait actions on each map grid with
256 agents under Zhang distribution. It is evident that both CAL-MAPF and
baseline experience severe traffic congestion as agent number is large enough.

In Algorithm 1, we first set the status of each agent to 0 and assign them
initial target locations (Lines 1-6). Next, we obtain collision-free paths for
each agent by invoking a low-level MAPF algorithm. The plan will be executed
until at least one agent reaches its target location (Lines 7-9). Upon
arrival, the task assigner updates the lock information, attempts to assign
new target locations to available agents, and updates the status of all agents
based on the current warehouse situation (Lines 10-11).

Task assigner should first attempt to release locks to allow other agents the
opportunity to access cache grids. Status 1 is trying to read a cache grid,
and Status 2 is going to write. Only agents in status 1 and status 2 can hold
locks. After reaching their target location, they must go to the unloading
port to deliver items. So, we verify whether these agents have reached their
targets before releasing their held locks (Algorithm 2 Lines 1-8).

Then we evaluate whether other agents can alter their status. For agents in
status 0, heading to shelves, we examine if they have reached the shelves and
gotten items. We then check if they can do a write operation in the cache and
apply a cache replacement policy to select a cache grid. Thus, status 0 may
transition to status 2 (write to cache) or Status 3 (proceed directly to
unloading port) (Algorithm 2 lines 9-14). If they have not yet arrived, we
check whether they can retrieve an item from the cache, which would change
their status to 1 (read cache) (Algorithm 2 Lines 15-18). We do the same
status changes for agents in Status 3 and Status 4 as we describe in Figure 2
(Algorithm 2 Lines 19-28).

Figure 4: Makespan (Bar chart, lower is better) and Cache Hit Rate (Line
chart, higher is better). LRU, FIFO, and RANDOM represent CAL-MAPF with
different cache replacement policies. NONE represents Lifelong MAPF without
cache.

In Algorithm 3, we detail the process of reading or insertion (writing) a new
item into cache grids using a cache replacement policy. For the read
operation, it is necessary to verify if the item exists in the caches and if
there is an existing write lock on the cache grid (Algorithm 3 lines 7-14).
For the write operation, we first check whether the item is already in the
cache area or if another agent plans to insert the same item into the caches
(Algorithm 3 lines 15-19). Then, we determine if an available cache exists for
inserting the item (Algorithm 3 Lines 20-31).

##  V Experimental Results

We use Lifelong MAPF without cache as a baseline, which aligns with our
problem definition. To evaluate performance, we compare CAL-MAPF with Lifelong
MAPF, using LaCAM as the low-level MAPF solver for generating collision-free
paths. Both CAL-MAPF and Lifelong MAPF were implemented in C++, building on
parts of the existing LaCAM codebase111The LaCAM source code is publicly
accessible at https://github.com/Kei18/lacam. Our implementation is available
at https://github.com/HarukiMoriarty/CAL-MAPF. All experiments were conducted
on a system running Ubuntu 20.04.1, equipped with an AMD Ryzen 3990X 64-core
CPU and 64GB RAM at 2133 MHz.

###  V-A Test Settings

As shown in Figure 1, we designed a warehouse map (27x71) with caches based on
our problem definition. The map is adapted from the warehouse map of MAPF
benchmark [2]. It includes 1600 shelf grids, a maximum of 80 cache grids and 4
unloading ports. We tested CAL-MAPF in both multi-port and single-port
scenarios, as depicted in Figure 1. The multi-port scenario has 4 working
groups of unloading ports and cache grids, each with a maximum of 20 cache
grids. The single-port scenario maintains the same number of total cache grids
and agents as the multi-port but only has one unloading port. Each shelf grid
represents a unique kind of item, and we randomly assign an index to each
shelf grid. The maximum cache-to-shelf ratio is 5%. We test all scenarios with
different cache numbers {16, 32, 48, 64, 80} by deleting some cache grids in
Figure 1. We have also chosen various total numbers of agents,
$\\{4,8,16,32,64,128,192,256\\}$. In the multi-port scenario, each group is
assigned an equal number of agents $\\{1,2,4,8,16,32,48,64\\}$.

Since we can expect the distribution of the task queue could significantly
affect the performance of cache design, we designed three input task
distributions to test CAL-MAPF, including: (1) $M$-$K$ distribution (MK): For
any consecutive subarray of length $M$ in the task queue $Q$, there are at
most $K$ different kinds of item. This distribution is inspired by [37], where
LRU has been proven to have a limit on the cache miss rate and to be better
than FIFO. This distribution can also represent that there are only several
items people purchase daily, and some items may become very popular at one
time, replacing previously popular items. (2) 7:2:1 distribution (Zhang):
there are 70% kinds of items with only a 10% appearance probability in the
task queue, 20% kinds of items with a 20% probability, and 10% with a 70%
appearance probability [48]. (3) Real Data Distribution (RDD): we obtain data
from Kaggle’s public
warehouse222kaggle.com/datasets/felixzhao/productdemandforecasting, build a
probability distribution based on the frequency of Kaggle data items and
generate tasks from this probability distribution.

Figure 5: Makespan (Bar chart, lower is better) and Cache Hit Rate (Line
chart, higher is better). As the number of caches increases, CAL-MAPF’s cache
hit rate and makespan performance improve. In the MK, Real, and Zhang
distributions, CAL-MAPF surpasses the baseline in most test settings. However,
it is observable that as the number of agents increases, the improvement
offered by CAL-MAPF diminishes. Additionally, an abnormal increase in makespan
is observed at baseline under the Zhang distribution with 256 agents.  Figure
6: Makespan (Bar chart, lower is better) and Cache Hit Rate (Line chart,
higher is better). The hit rate significantly depends on the input task
distribution, and the hit rate also greatly affects the final makespan
performance.

We randomly generate agent start locations and $Q$ for all distributions with
a total length of 1,000. For the MK distribution, we select $M=200$ and $K$
values of $\\{1,20,40,80,120,160\\}$. We allocate a total of 10 seconds for
the low-level MAPF solver to find a collision-free solution for all 1,000
tasks in $Q$. We show performance using makespan which is the completion time
when the last task has been accomplished. For CAL-MAPF, we use three different
cache replacement policies. Least Recently Used (LRU), First-In-First-Out
(FIFO), and RANDOM. We use NONE to represent the baseline method.

###  V-B Performance

Many variables can influence the performance of CAL-MAPF, including the number
of agents, the number of caches, and the distributions of input tasks. As
illustrated in Figure 4, increasing the number of caches leads to improvements
in cache hit rate and makespan performance for both single- and multi-port
scenarios. And the cache hit rate decreases as the number of agents grows. It
is also observed that as the number of agents continues to increase (from 64
to 256), there is not much difference in the makespan for both CAL-MAPF and
the baseline, and the cache hit rate is dropping.

Two reasons could contribute to this scenario: (1) CAL-MAPF and baseline’s
makespan remain at the same level or even worse with too many agents: traffic
congestions occur in the map as the number of agents increases. (2) The CAL-
MAPF cache hit rate continues to decrease as the makespan performance shows
minimal differences: We employ a lock mechanism to maintain items stored in
the cache area. Traffic congestion prevents many agents from reaching their
target in the cache and agents always hold locks until they reach their target
locations. For other agents not significantly affected by traffic congestion,
they are constantly assigned new tasks and cannot obtain locks in the cache.
The item distribution cannot update with input tasks, which ultimately leads
to a continuous drop in the cache hit rate. This second reason can also
clarify why CAL-MAPF performs better as the number of caches increases:
enlarging the cache area mitigates traffic congestion and enhances the cache
hit rate.

In Figure 5 and Figure 6, we present the performance of CAL-MAPF and the
baseline for various task distributions. Figure 5 demonstrates that as the
number of caches increases, CAL-MAPF’s performance improves. In the MK, Real,
and Zhang distributions, CAL-MAPF surpasses the baseline in most test
settings. However, it is observable that as the number of agents increases,
the improvement offered by CAL-MAPF diminishes. One possible reason is that
the low hit rate leads agents to require longer paths to complete a task. As
depicted in Figure 6, the hit rate significantly depends on the input task
distribution, and the hit rate also greatly affects the final makespan
performance.

Furthermore, in Figure 5, an abnormal increase in makespan is observed at
baseline under the Zhang distribution with 256 agents. Traffic congestion
could contributing to this abnormal poor performance. Figure 3 illustrates the
average frequency of agent wait actions on each grid when the number of agents
reaches 256 with the Zhang distribution. It is evident that both CAL-MAPF and
baseline experience severe traffic congestion.

High cache hit rates and smooth traffic are crucial for the performance of
CAL-MAPF. To enhance the cache hit rate, we can increase the number of caches.
And we can also directly add more agents to improve the makespan performance.
However, both methods come with their drawbacks. The number of caches is
constrained by the space available close to the unloading port. Introducing
more agents can lead to severe traffic congestion, ultimately causing the hit
rate to drop. Nevertheless, there are potential solutions to mitigate these
adverse effects, such as implementing more efficient map designs [13] and
using one-way systems near the cache and unloading ports [14]. Additionally,
as we currently employ a simple task assignment policy, we could implement a
more advanced policy with predictive capabilities, leveraging real warehouse
task data to enhance the cache hit rate. The cache replacement policies, such
as LRU and FIFO, may be overly simplistic for CAL-MAPF. Incorporating more
complex policies, including learning-based approaches, could further improve
the cache hit rate, especially since CAL-MAPF allows more planning time than
traditional caches in computer architecture.

##  VI Conclusion

This work presents a novel mechanism, named Caching-Augmented Lifelong MAPF
(CAL-MAPF), designed to improve the performance of Lifelong MAPF. We have
developed a new map grid type called cache for temporary item storage and
replacement. Additionally, we have devised a locking mechanism for caches to
improve the stability of the planning solution. This cache mechanism was
evaluated using various cache replacement policies and a spectrum of input
task distributions. Through experimentation, we identified three main factors
that significantly impact CAL-MAPF performance: suitable input task
distribution, high cache hit rate, and smooth traffic. In general, CAL-MAPF
has demonstrated potential for performance improvements in certain task
distributions and map and agent configurations.

## References

  * [1] P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,” _Artificial Intelligence_ , vol. 29, no. 1, pp. 9–9, 2008.
  * [2] R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. Kumar _et al._ , “Multi-agent pathfinding: Definitions, variants, and benchmarks,” in _Proceedings of the International Symposium on Combinatorial Search (SoCS)_ , vol. 10, no. 1, 2019, pp. 151–158.
  * [3] G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,” _Artificial Intelligence_ , vol. 219, pp. 40–66, 2015.
  * [4] G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in _2011 IEEE/RSJ international conference on intelligent robots and systems_. IEEE, 2011, pp. 3260–3267.
  * [5] M. Barer, G. Sharon, R. Stern, and A. Felner, “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem,” in _Proceedings of the International Symposium on Combinatorial Search (SoCS)_ , 2014.
  * [6] J. Yu and S. LaValle, “Structure and intractability of optimal multi-robot path planning on graphs,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 27, no. 1, 2013, pp. 1443–1449.
  * [7] H. Ma, J. Li, T. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , 2017, p. 837–845.
  * [8] J. Li, A. Tinka, S. Kiesel, J. W. Durham, T. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding in large-scale warehouses,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 35, no. 13, 2021, pp. 11 272–11 281.
  * [9] J. Li, Z. Chen, D. Harabor, P. J. Stuckey, and S. Koenig, “Anytime multi-agent path finding via large neighborhood search,” in _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2021, pp. 4127–4135.
  * [10] K. Okumura, M. Machida, X. Défago, and Y. Tamura, “Priority inheritance with backtracking for iterative multi-agent path finding,” _Artificial Intelligence_ , vol. 310, p. 103752, 2022.
  * [11] K. Okumura, “Lacam: Search-based algorithm for quick multi-agent pathfinding,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 37, no. 10, 2023, pp. 11 655–11 662.
  * [12] K. R. Gue and R. D. Meller, “Aisle configurations for unit-load warehouses,” _IIE Transactions_ , vol. 41, no. 3, pp. 171–182, 2009.
  * [13] Y. Zhang, M. C. Fontaine, V. Bhatt, S. Nikolaidis, and J. Li, “Multi-robot coordination and layout design for automated warehousing,” in _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2023, pp. 5503–5511.
  * [14] Y. Zhang, H. Jiang, V. Bhatt, S. Nikolaidis, and J. Li, “Guidance graph optimization for lifelong multi-agent path finding,” _arXiv preprint arXiv:2402.01446_ , 2024.
  * [15] C. S. Tang and L. P. Veelenturf, “The strategic role of logistics in the industry 4.0 era,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 129, pp. 1–11, 2019.
  * [16] R. Yuan, S. C. Graves, and T. Cezik, “Velocity-based storage assignment in semi-automated storage systems,” _Production and Operations Management (POM)_ , vol. 28, no. 2, pp. 354–373, 2019.
  * [17] X. Li, G. Hua, A. Huang, J.-B. Sheu, T. Cheng, and F. Huang, “Storage assignment policy with awareness of energy consumption in the kiva mobile fulfillment system,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 144, p. 102158, 2020.
  * [18] F. Weidinger, N. Boysen, and D. Briskorn, “Storage assignment with rack-moving mobile robots in KIVA warehouses,” _Transportation Science (TS)_ , vol. 52, no. 6, pp. 1479–1495, 2018.
  * [19] D. Silver, “Cooperative pathfinding,” in _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE)_ , vol. 1, no. 1, 2005, pp. 117–122.
  * [20] R. J. Luna and K. E. Bekris, “Push and swap: Fast cooperative path-finding with completeness guarantees,” in _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2011, pp. 294–300.
  * [21] K.-H. C. Wang and A. Botea, “Fast and memory-efficient multi-agent pathfinding,” in _Proceedings of the International Conference on Auto- mated Planning and Scheduling (ICAPS)_ , 2008, pp. 380–387.
  * [22] T. Standley, “Finding optimal solutions to cooperative pathfinding problems,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 24, no. 1, 2010, pp. 173–178.
  * [23] T. Standley and R. Korf, “Complete algorithms for cooperative pathfinding problems,” in _Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)_ , 2011, pp. 668–673.
  * [24] G. Wagner and H. Choset, “Subdimensional expansion for multirobot path planning,” _Artificial intelligence_ , vol. 219, pp. 1–24, 2015.
  * [25] J. Li, W. Ruml, and S. Koenig, “Eecbs: A bounded-suboptimal search for multi-agent path finding,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 35, no. 14, 2021, pp. 12 353–12 362.
  * [26] M. Erdmann and T. Lozano-Perez, “On multiple moving objects,” _Algorithmica_ , vol. 2, pp. 477–521, 1987.
  * [27] H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig, “Searching with consistent prioritization for multi-agent path finding,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 33, no. 01, 2019, pp. 7643–7650.
  * [28] S.-H. Chan, R. Stern, A. Felner, and S. Koenig, “Greedy priority-based search for suboptimal multi-agent path finding,” in _Proceedings of the International Symposium on Combinatorial Search (SoCS)_ , vol. 16, no. 1, 2023, pp. 11–19.
  * [29] J. Li, Z. Chen, D. Harabor, P. J. Stuckey, and S. Koenig, “Mapf-lns2: fast repairing for multi-agent path finding via large neighborhood search,” in _Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)_ , vol. 36, no. 9, 2022, pp. 10 256–10 265.
  * [30] K. Okumura, “Engineering lacam∗: Towards real-time, large-scale, and near-optimal multi-agent pathfinding,” _arXiv preprint_ , 2023.
  * [31] V. Nguyen, P. Obermeier, T. Son, T. Schaub, and W. Yeoh, “Generalized target assignment and path finding using answer set programming,” in _Proceedings of the International Symposium on Combinatorial Search (SoCS)_ , vol. 10, no. 1, 2019, pp. 194–195.
  * [32] M. Čáp, J. Vokřínek, and A. Kleiner, “Complete decentralized method for on-line multi-robot trajectory planning in well-formed infrastructures,” in _Proceedings of the International Conference on Auto- mated Planning and Scheduling (ICAPS)_ , vol. 25, 2015, pp. 324–332.
  * [33] F. Grenouilleau, W.-J. Van Hoeve, and J. N. Hooker, “A multi-label a* algorithm for multi-agent pathfinding,” in _Proceedings of the International Conference on Auto- mated Planning and Scheduling (ICAPS)_ , vol. 29, 2019, pp. 181–185.
  * [34] A. W. Burks, H. H. Goldstine, and J. Von Neumann, “Preliminary discussion of the logical design of an electronic computing instrument,” in _The origins of digital computers: Selected papers_. Springer, 1946, pp. 399–413.
  * [35] J. McCabe, “On serial files with relocatable records,” _Operations Research_ , vol. 13, no. 4, pp. 609–618, 1965.
  * [36] W. F. K. III, “Analysis of paging algorithms,” in _in Proceedings of International Conference on Information Processing (IFIP) Congress_ , 1971, pp. 485–490.
  * [37] S. Albers, L. M. Favrholdt, and O. Giel, “On paging with locality of reference,” in _ACM Symposium on Theory of Computing (STOC)_ , 2002, pp. 258–267.
  * [38] A. Dan and D. Towsley, “An approximate analysis of the lru and fifo buffer replacement schemes,” in _Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems_ , 1990, pp. 143–152.
  * [39] M. Chrobak and J. Noga, “Lru is better than fifo,” _Algorithmica_ , vol. 23, pp. 180–185, 1999.
  * [40] M. Altınel, C. Bornhövd, S. Krishnamurthy, C. Mohan, H. Pirahesh, and B. Reinwald, “Cache tables: Paving the way for an adaptive database cache,” in _Proceedings 2003 VLDB Conference_. Elsevier, 2003, pp. 718–729.
  * [41] M. Harchol-Balter, T. Leighton, and D. Lewin, “Resource discovery in distributed networks,” in _Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing_ , 1999, pp. 229–237.
  * [42] J. Gu, M. Goetschalckx, and L. F. McGinnis, “Research on warehouse operation: A comprehensive review,” _European Journal of Operational Research (EJOR)_ , vol. 177, no. 1, pp. 1–21, 2007.
  * [43] K. J. Roodbergen and I. F. A. Vis, “A survey of literature on automated storage and retrieval systems,” _European Journal of Operational Research (EJOR)_ , vol. 194, no. 2, pp. 343–362, 2009.
  * [44] K. Azadeh, R. de Koster, and D. Roy, “Robotized and automated warehouse systems: Review and recent developments,” _Transportation Science (TS)_ , vol. 53, no. 4, pp. 917–945, 2019.
  * [45] B. C. Park, “An optimal dwell point policy for automated storage/retrieval systems with uniformly distributed, rectangular racks,” _International journal of production research_ , vol. 39, no. 7, pp. 1469–1480, 2001.
  * [46] M. Fukunari and C. Malmborg, “A heuristic travel time model for random storage systems using closest open location load dispatching,” _International Journal of Production Research_ , vol. 46, no. 8, pp. 2215–2228, 2008.
  * [47] J.-P. Gagliardi, J. Renaud, and A. Ruiz, “On storage assignment policies for unit-load automated storage and retrieval systems,” _International Journal of Production Research_ , vol. 50, no. 3, pp. 879–892, 2012.
  * [48] Y. Zhang, “Correlated storage assignment strategy to reduce travel distance in order picking,” _IFAC-PapersOnLine_ , vol. 49, no. 2, pp. 30–35, 2016.