# Person Search Challenges and Solutions: A Survey

Xiangtan Lin1 Pengzhen Ren2 Yun Xiao2 Xiaojun Chang1111Corresponding Author
Alex Hauptmann3 1Monash University 2Northwest University 3Carnegie Mellon
University {xiangtan.lin, cxj273<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Person search has drawn increasing attention due to its real-world
applications and research significance. Person search aims to find a probe
person in a gallery of scene images with a wide range of applications, such as
criminals search, multi-camera tracking, missing person search, etc. Early
person search works focused on image-based person search, which uses person
image as the search query. Text-based person search is another major person
search category that uses free-form natural language as the search query.
Person search is challenging, and corresponding solutions are diverse and
complex. Therefore, systematic surveys on this topic are essential. This paper
surveyed the recent works on image-based and text-based person search from the
perspective of challenges and solutions. Specifically, we provide a brief
analysis of highly influential person search methods considering the three
significant challenges: the discriminative person features, the query-person
gap, and the detection-identification inconsistency. We summarise and compare
evaluation results. Finally, we discuss open issues and some promising future
research directions.

##  1 Introduction

Person search Xu et al. (2014) aims to find a query person in a gallery of
scene images. Historically, person search was an extended form of person re-
identification (re-id) problem Liu et al. (2020b, a); Li et al. (2019b); Cheng
et al. (2018); Liu et al. (2018b); Cheng et al. (2017); Liu et al. (2017b).
Therefore, early researches on person search focused on an image-based
setting, which uses person image as the search query Xiao et al. (2017); Liu
et al. (2017a); Chang et al. (2018); Gao et al. (2019); Xiao et al. (2019).
Meanwhile, research in text-based person search Li et al. (2017b); Wang et al.
(2020b) has made significant advances in the past few years. Text-based person
search is handy when a probe image is unavailable but free-form natural
language. The two types of person search are illustrated in Figure 1.

Figure 1: The general frameworks of person search. (a) Image-based person
search in which person image is available as the search query against a
gallery of images. Image-based person search involves two sub-tasks, person
detection and person identification. (b) Text-based person search in which
search query is free form natural language. A general text-based person search
framework typically learns text feature through an RNN variant network and
then align text features with visual elements from the detection network to
identify the person in the target images.

Person search faces more challenges than person re-id problem. Unlike the
person re-id setting where the cropped person images are provided, and the
primary challenge is just to bring the query-person gap. Person search needs
to deal with an additional detection challenge so that the detected person can
be used for the downstream identification task. The additional detection task
poses more challenges due to the influences of poses, occlusion, resolution
and background clutter in the scene images. Such detection results may be
inconsistent with the identification task (Figure 2). Similarly, text-based
person search is also more challenging than the traditional text-image
matching problem Li et al. (2017b) as it needs to learn discriminative
features first before the text-person matching.

Person search is fast-evolving, and existing person search methods are diverse
and complex. Researchers may leverage the rich knowledge concerning object
detection, person re-id, and text-image matching separately. Systematic
surveys concerning person search bring more values to the community.
Especially, as far as we know, there is no existing survey covering the text-
based person search. Islam (2020) surveyed works on image-based person search
and neglected the text-based person search. Furthermore, Islam (2020) didn’t
discuss the joint challenge of person detection and identification, especially
the detection-identification inconsistency challenge as illustrated in Figure
2. Therefore, we survey works beyond image-based person search and provide a
systematic review of the diverse person search solutions. We summarise the
main differences between the previous survey Islam (2020) and ours in Table 1.

Survey |  Covering |  Analysis
---|---|---
Islam (2020) |  Image-based |  Components
Ours |  Image-based, Text-based |  (Challenges: Solutions) Discriminative person features: Deep feature representation learning Query-person gap: Deep metric learing Detection-identification inconsistency: Identity-driven detection

Table 1: Summary of the main differences between the previous survey and ours.
This survey focuses more on challenges and solutions.

In this survey, we aim to provide a cohesive analysis of the recent person
search works so that the rationals behind the ideas can be grasped to inspire
new ideas. Specifically, We surveyed recently published and pre-print person
search papers from top conference venues and journals. We analyse methods from
the perspective of challenges and solutions and summarise evaluation results
accordingly. At the end of the paper, we provide insights on promising future
research directions. In summary, the main contributions of this survey are:

  * •

In addition to image-based person search, we cover text-based person search
which was neglected in the previous person search survey.

  * •

We analyse person search methods from the perspective of challenges and
solutions to inspire new ideas.

  * •

We summarise and analyse existing methods’ performance and provide insights on
promising future research directions.

##  2 Person Search

Person search is a fast-evolving research topic. In 2014, Xu et al. (2014)
first introduced the person search problem and pointed out the conflicting
nature between person detection and person identification sub-tasks. Person
detection deals with common human appearance, while the identification task
focuses on a person’s uniqueness. After Xiao et al. (2017) introduced the
first end-to-end person search framework in 2017, we have seen an increasing
number of image-based person search works in the last three years. Meanwhile,
in 2017, GNA-RNN Li et al. (2017b) set the benchmark for text-based person
search. We draw a timeline to present the person search works in Figure 3 and
show the two divisions: image-based and text-based person search.

Figure 2: The detection-identification inconsistency problem. The detecion
model learns person proposal based on common person apperance using
intersection-over-union (IoU) over certain threshold, which may result in less
accurate bounding boxes compare to person for the identification task.

Person search addresses person detection and person identification
simultaneously. There are three significant person search challenges to be
considered when developing a person search solution. Firstly, a person search
model needs to learn discriminative person features from scene images suitable
for matching the query identity. Inevitably, the learnt person features differ
from the query identity features to some degrees. Therefore the second major
challenge is how to bring the gap between the query and the detected person.
The third challenge is related to the conflicting nature between person
detection and person identification. Person detection deals with common person
appearance, while the identification task focuses on a person’s uniqueness.
The detected person may not be suitable for identity matching. For instance, a
partial human body could be considered a person during detection and is
inconsistent with the query identity at the identification stage, which may be
a full person picture.

In this section, we analyse person search methods regarding above-mentioned
three challenges and corresponding solutions from the following three aspects
for both image-based and text-based person search:

  * •

Deep feature representation learning. Addressing the challenge of learning
discriminative person features from gallery images concerning background
clutter, occlusion and poses etc.

  * •

Deep metric learning. Addressing the challenge of bringing query-person gap by
using loss functions to guide feature representation learning.

  * •

Identity-driven detection. Addressing the challenge of mitigating the
detection-identification inconsistency by incorporating query identities into
the detection process.

Figure 3: Timeline of person search studies. Above the timeline are image-
based person search works. Below the line are text-based person search
methods.

###  2.1 Deep Feature Representation Learning

Deep feature representation learning focuses on learning discriminative person
features concerning distractors in the gallery images. The majority of the
early methods exploited global person features, including context cues, while
refining person proposals. Such as RCAA Chang et al. (2018) utilises the
relational spatial and temporal context in a deep reinforcement learning
framework to adjust the bounding boxes constantly. However, these methods
didn’t consider the background clutter in the proposal bounding boxes,
resulting in a situation where different persons with similar backgrounds are
close in the learnt feature space. SMG Zheng et al. (2020a) eliminates
background clutter using segmentation masks so that the learnt person features
are invariant to the background clutter. NAE Chen et al. (2020) separates
persons and background by norms and discriminates person identities by angles.
Person detection and object detection, in general, face the multi-scale
matching challenge. To learn scale-invariant features, CLSA Lan et al. (2018)
and DHFF Lu et al. (2019) utilise multi-level features from the identification
network to solve the multi-scale matching problem with different multi-metric
losses.

Local discriminative features are useful when two persons exhibit similar
appearance and can’t be discriminated against merely by full-body appearance.
APNet Zhong et al. (2020) divides the body into six parts and uses an
attention mechanism to weigh the body parts’ contribution further. Unlike
APNet, which uses arbitrary body parts, CGPS Yan et al. (2019) proposes a
region-based feature learning model for learning contextual information from a
person graph. BINet Dong et al. (2020a) uses the guidance from the cropped
person patches to eliminate the context influence outside the bounding boxes.

Deep feature representation learning in text-based person search learns visual
representations for the detected person most correspondent to the textual
features. Similar to image-based person search, text-based person search
methods exploit global and local discriminative features. GNA-RNN Li et al.
(2017b) exploits global features in the first text-based LSTM-CNN person
search framework and uses an attention mechanism to learn the most relevant
parts. GNA-RNN only attends to visual elements and doesn’t address various
text structure. To address this problem, CMCE Li et al. (2017a) employs a
latent semantic attention module and is more robust to text syntax variations.
To address the background clutter problem, PMA Jing et al. (2020b) uses pose
information to learn the pose-related features from the map of the key points
of human. To further distinguish person with similar global appearance,
PWM+ATH Chen et al. (2018b) utilises a word-image patch matching model to
capture the local similarities. ViTAA Wang et al. (2020b) decomposes both
image and text into attribute components and conducts a fine-grained matching
strategy to enhance the interplay between image and text.

###  2.2 Deep Metric Learning

Deep metric learning tackles the query-person gap challenge with loss
functions to guide the feature representation learning. The general purpose is
to bring the detected person features close to the target identity while
separating them from other identities. Similarity metrics such as Euclidean
distance and cosine similarity are common measures to evaluate the similarity
level among those query-person pairs. The identification task is generally
formulated as a classification problem where conventional softmax loss trains
the classifier. Softmax has a major problem of slow convergence with a large
number of classes. OIM (Eq: 2) Xiao et al. (2017) addresses this issue while
exploiting large number of identities and unlabeled identities. OIAM Gao et
al. (2019) and IEL Shi et al. (2018) further improve the OIM method with
additional center losses. Different from OIM variances, I-Net He and Zhang
(2019) introduces a Siamese structure with an online pairing loss (OPL) and
hard example priority Softmax loss (HEP) to bring the query-person gap. RDLR
Han et al. (2019) uses the identification loss instead of regression loss for
supervising the bounding boxes.

In the landmark OIM approach, the OIM loss effectively closes the query-person
gap utilising labelled and unlabeled identities from training data. The
probability of detected person features $x$ being recognised as the identity
with class-id $i$ by a Softmax function:

$p_{i}=\frac{\exp(v_{i}^{T}x/\tau)}{\sum_{j=1}^{L}\exp(v_{j}^{T}x/\tau)+\sum_{k=1}^{Q}\exp(u_{k}^{T}x/\tau)}.$
(1)

Where $v_{i}^{T}$ is the labelled person features for the $i_{th}$ identity in
the lookup table (LUT). $v_{j}^{T}$ is the $j_{th}$ labelled person features
in the LUT. $u_{k}^{T}$ is the $k_{th}$ unlabelled person features in the LUT.
$\tau$ regulates probability distribution. OIM objective is to maximize the
expected log-likelihood of the target $t$.

$\mathcal{L}=\mathrm{E_{x}}\left[\log{p_{t}}\right].$ (2)

Metric learning in text-based person search is to close the text-image
modality gap. The main challenge in text-based person search is that it
requires the model to deal with the complex syntax from the free-form textual
description. To tackle this, methods like ViTAA, CMCE, PWM+ATH Wang et al.
(2020b); Li et al. (2017a); Chen et al. (2018b) employ attention mechanism to
build relation modules between visual and textual representations. Unlike the
above three methods, which are all the CNN-RNN frameworks, Dual Path Zheng et
al. (2020b) employs CNN for textual feature learning and proposes an instance
loss for image-text retrieval. CMPM+CMPC Zhang and Lu (2018) utilizes a cross-
modal projection matching (CMPM) loss and a cross-modal projection
classification (CMPC) loss to learn discriminative image-text representations.
Similar to CMPM+CMPC, MAN Jing et al. (2020a) proposes cross-modal objective
functions for joint embedding learning to tackle the domain adaptive text-
based person search.

Inspired by the recent success of knowledge distillation Hinton et al. (2015),
instead of directly training detection and identification sub-nets, the two
modules can be learnt from the pre-trained detection and identification models
Munjal et al. (2019b). DKD Zhang et al. (2020) focuses on improving the
performance of identification by introducing diverse knowledge distillation in
learning the identification model. Specifically, a pre-trained external
identification model is used to teach the internal identification model. A
simplified knowledge distillation process is illustrated in Figure 4.

###  2.3 Identity-driven detection

The detection-identification inconsistency challenge in image-based person
search is tackled by incorporating identities into the detection process. This
means during training, ground-truth person identities are used to guide person
proposals, or at search time, the query identity information is utilised to
refine the bounding boxes. Person search tackles person detection and person
identification challenges in one framework. Existing person search methods can
be divided into two-stage and end-to-end solutions from the architecture
perspective. In two-stage person detection, the detection and identification
models are trained separately for optimal performance of both detection and
identification models Zhang et al. (2020); Loesch et al. (2019). However, due
to the detection-identification inconsistent issue, the separately trained
models may not yield the best person search result. To address the
inconsistency problem between the two branches, TCTS Wang et al. (2020a) and
IGPN+PCB Dong et al. (2020b) exploit query information at search time to
filter out low probable proposals. End-to-end methods share visual features
between detection and identification and significantly decrease runtime.
However, joint learning contributes to sub-optimal detection performance Wang
et al. (2020a), which subsequently worsen the detection-identification
inconsistency problem. To address the problem. NPSM Liu et al. (2017a) and
QEEPS Munjal et al. (2019a) leverage query information to optimise person
proposals in detection process. Differ from the query-guided methods, RDLR Han
et al. (2019) supervises bounding box generation using identification loss.
Therefore, proposal bounding boxes are more reliable. In person search
settings, the query identity is present in gallery images. Therefore, all
methods mentioned above essentially incorporate identities into the detection
process.

Figure 4: A representative end-to-end person search framework where the
detection and identification branches are supervised by pre-trained detection
and identification models through knowledge distillation. The detection loss
$L_{det}$, identification loss $L_{id}$ and the knowledge distillation losses
$L_{detkd}$ and $L_{idkd}$ can be optimised as a multi-task learning task
through back-propagation.

Text-based person search faces less detection-identification inconsistency
challenge since the proposal person is identified by text-image matching
without comparing bounding boxes. Therefore, text-based person search mainly
focuses on learning visual and language features and improving the matching
accuracy. The majority of current text-based person search methods are end-to-
end frameworks that consist of a CNN backbone for extracting visual elements
and a bi-LSTM for learning language representations. The two modules are
jointly trained to build word-image relations from the learnt visual and
language feature representations. CMCE Li et al. (2017a) is the only two-stage
framework in which the stage-one CNN-LSTM network learns cross-modal features,
and in stage-two, the CNN-LSTM network refines the matching results using an
attention mechanism.

|  |  | CUHK-SYSU | PRW | LSPM
---|---|---|---|---|---
Method | Feature | Loss | mAP(%) | R@1(%) | mAP(%) | R@1(%) | mAP(%) | R@1(%)
Non-identity-driven detection |
OIM Xiao et al. (2017) | global | OIM | 75.5 | 78.7 | 21.3 | 49.9 | 14.4 | 47.7
IAN Xiao et al. (2019) | global | Softmax, Center loss | 76.3 | 80.1 | 23.0 | 61.9 |  |
OIAM Gao et al. (2019) | global | OIM, Center loss | 76.98 | 77.86 | 51.02 | 69.85 |  |
FMT-CNN Zhai et al. (2019) | global | OIM, Softmax | 77.2 | 79.8 |  |  |  |
ELF16 Yang et al. (2017) | global & local | OIM | 77.8 | 80.6 |  |  |  |
IOIM Liu et al. (2018a) | global | IOIM, Certer loss | 79.78 | 79.90 | 21.00 | 63.10 |  |
EEPSS Loesch et al. (2019) | global | Triplet loss | 79.4 | 80.5 | 25.2 | 47.0 |  |
JDI + IEL Shi et al. (2018) | global | IEL | 79.43 | 79.66 | 24.26 | 69.47 |  |
RCAA Chang et al. (2018) | global & context | RL reward |  | 81.3 |  |  |  |
I-NET He and Zhang (2019) | global | OLP, HEP | 79.5 | 81.5 |  |  |  |
MGTS Chen et al. (2018a) | global & mask | OIM | 83.0 | 83.7 | 32.6 | 72.1 |  |
KD-OIM Munjal et al. (2019b) | global | OIM | 83.8 | 84.2 |  |  |  |
CGPS Yan et al. (2019) | global & context | OIM | 84.1 | 86.5 | 33.4 | 73.6 |  |
PFFN Hong et al. (2019) | global & multi scale | Triplet loss | 84.5 | 89.8 | 34.3 | 73.9 |  |
SMG Zheng et al. (2020a) | global & mask | Binary Cross Entropy | 86.3 | 86.5 |  |  |  |
FPSP Li et al. (2019a) | global | Cross entropy | 86.99 | 89.87 | 44.45 | 70.58 |  |
CLSA Lan et al. (2018) | global & multi-scale | Cross entropy | 87.2 | 88.5 | 38.7 | 65.0 |  |
APNet Zhong et al. (2020) | local | OIM | 88.9 | 89.3 | 41.9 | 81.4 | 18.8 | 55.7
DHFF Lu et al. (2019) | global & multi-scale | Multi-Metric loss | 90.2 | 91.7 | 41.1 | 70.1 |  |
BINet Dong et al. (2020a) | global & local | OIM | 90.8 | 91.6 | 47.2 | 83.4 |  |
NAE+ Chen et al. (2020) | global | OIM | 92.1 | 92.9 | 44.0 | 81.1 |  |
DKD Zhang et al. (2020) | global & local |  | 93.6 | 94.72 | 54.16 | 87.89 |  |
Identity-driven detection
NPSM Liu et al. (2017a) | global | Softmax | 77.9 | 81.2 | 24.2 | 53.1 |  |
QEEPS Munjal et al. (2019a) | global | OIM | 84.4 | 84.4 | 37.1 | 76.7 |  |
KD-QEEPS Munjal et al. (2019b) | global | OIM | 85.0 | 85.5 |  |  |  |
IGPN + PCB Dong et al. (2020b) | global |  | 90.3 | 91.4 | 47.2 | 87.0 |  |
RDLR Han et al. (2019) | global | Proxy Triplet Loss | 93.0 | 94.2 | 42.9 | 70.2 |  |
TCTS Wang et al. (2020a) | global | IDGQ loss | 93.9 | 95.1 | 46.8 | 87.5 |  |

Table 2: Performance of image-based person search methods on CUHK-SYSU, PRW
and LSPM datasets.

|  |  | CUHK-PEDES
---|---|---|---
Method | Feature | Loss | R@1 | R@5 | R@10
GNA-RNN Li et al. (2017b) | global | Cross entropy | 19.05 |  | 53.63
CMCE Li et al. (2017a) | global | CMCE loss | 25.94 |  | 60.48
PWM+ATH Chen et al. (2018b) | global | Cross entropy | 27.14 | 49.45 | 61.02
Dual-Path Zheng et al. (2020b) | global | Ranking loss, Instance loss | 44.4 | 66.26 | 75.07
CMPM+CMPC Zhang and Lu (2018) | global | CMPM, CMPC | 49.37 |  | 79.27
LPS+MCCL Liu et al. (2019) | global | MCCL | 50.58 |  | 79.06
A-GANet Liu et al. (2019) | global | Binary Cross Entropy | 53.14 | 74.03 | 81.95
PMA Jing et al. (2020b) | global & pose |  | 53.81 | 73.54 | 81.23
TIMAM Sarafianos et al. (2019) | global | Cross Entropy, GAN Loss | 55.41 | 77.56 | 84.78
ViTAA Wang et al. (2020b) | global & attribute | Alignment loss | 55.97 | 75.84 | 83.52

Table 3: Performance of text-based person search methods on the CUHK-PEDES
dataset.

##  3 Datasets and Evaluation

| Image-Based | Text-Based
---|---|---
Dataset | CUHK-SYSU | PRW | LSPS | CUHK-PEDES
#frames | 18184 | 11816 | 51836 | 40206
#identities | 8432 | 932 | 4067 | 13003
#anno boxes | 96143 | 34304 | 60433 |
#parts | 6% | 0% | 60% |
#cameras |  | 6 | 17 |
#description |  |  |  | 80440
#detector | hand | hand | Faster R-CNN |

Table 4: Person search datasets statistics.

###  3.1 Datasets

CUHK-SYSU Xiao et al. (2017) dataset is an image-based person search dataset,
which contains 18184 images, 8432 person identities, and 99809 annotated
bounding boxes. The training set contains 11206 images and 5532 query
identities. The test set contains 6978 images and 2900 query identities. The
training and test sets have no overlap on images or query person.

PRW Zheng et al. (2017) dataset has a total of 11816 frames which are manually
annotated with 43110 person bounding boxes. 34304 people have identifications
ranging from 1 to 932, and the rest are assigned identities of -2. The PRW
training set has 5704 images and 482 identities, and the test set has 6112
pictures and 450 identities.

LSPS Zhong et al. (2020) dataset is a new image-based person search dataset,
in which a total number of 51,836 pictures are collected. 60,433 bounding
boxes and 4,067 identities are annotated. LSPS has a substantially larger
number of incomplete query bounding boxes of 60% compare to 6% in CUHK-SYSU
and 0% in PRW.

CUHK-PEDES dataset Li et al. (2017b) is currently the only dataset for text-
based person search. The images are collected from five person re-id datasets
and added the corresponding language annotations. It contains 40206 images of
13003 identities and 80440 textual descriptions. Each picture has 2 textual
descriptions. The dataset is divided into three parts, 11003 training
individuals with 34054 images and 68126 captions, 1000 validation persons with
3078 images and 6158 sentences, and 1000 test identities with 3074 pictures
6156 captions.

CUHK-SYSU and PRW are de facto datasets for image-based person search. LSPS is
new to the community and contains many partial body bounding boxes, making it
a specialised dataset to evaluate methods exploiting local discriminative
features. CUHK-PEDES is the only text-based person search dataset, and new
datasets may further advance research in this area. Dataset statistics are
summarised in Table 4.

###  3.2 Evaluation Metrics

Cumulative matching characteristics (CMC top-K) and mean averaged precision
(mAP) are the primary evaluation metrics for person search. In CMC, the top-K
predicted bounding boxes are ranked according to the intersection-over-union
(IoU) overlap with the ground-truths equal to or greater than 0.5. The mAP is
a popular evaluation metric in object detection, in which an averaged
precision (AP) is calculated for each query person, and then the final mAP is
calculated as an average of all APs.

###  3.3 Performance Analysis

In this section, we summarise and analyse the evaluation results considering
the three significant challenges in person search discussed earlier. We aim to
present the influencing factors that contribute to the person search
performance. We don’t discuss CNN backbones as modern CNN backbones such as
ResNet50 and VGG are similar in performance and are mostly interchangeable in
different methods.

We summarise the evaluation results of image-based person search methods in
Table 2. We annotate feature types and loss functions used for metric learning
along with the methods. Image-based person search faces the steep detection-
identification inconsistency challenge. Therefore, we divide image-based
person search methods into identity-driven detection and non-identity-driven
detection methods to analyse the identity-driven detection solution’s
effectiveness.

Methods specifically addressing the detection and identification inconsistency
challenge, such as IGPN, RDLR and TCTS, outperform methods addressing the
detection and identification separately. Methods exploiting fine-grained
discriminative features without considering the detection-identification
inconsistency challenge don’t have a clear edge over methods using global
features. Our interpretation is that the query identity presents in the
gallery images. Therefore, the detected person needs to be consistent with the
query identity for better query-person matching. For example, if the detected
person features are free from noises, the query should be free of noises. Loss
functions play critical roles in guiding feature representation learning, such
as using a center loss on top of the OIM loss to bring the same identities
closer and separate different identities. Knowledge distillation is a notably
effective strategy in training the detection and identification models. KD-
OIM, KD-QEEPS and DKD beat the corresponding baseline methods without
knowledge distillation.

The performance of the text-based person search methods on CUHK-PEDES is
summarised in Table 3. We include feature types and loss functions along with
the methods. Text-based person search is essentially a text-image matching
problem, and fine-grained discriminative features play a critical role in
cross-modal matching. Recent methods exploiting fine-grained discriminative
features with novel loss functions outperform methods using global features
and vanilla Cross-Entropy loss. Specifically, ViTAA Wang et al. (2020b)
exploiting local discriminative features via attribute-feature alignment
achieves the best search results.

##  4 Discussion and Future Directions

In this survey, we review the recent person search advances covering both
image-based and text-based person search. There have been remarkable
achievements in the past few years, it remains an open question on addressing
the three significant person search challenges, namely the discriminative
features, the query-person gap and the detection-identification inconsistency.
Next, we discuss a few future research directions.

Multi-modal person search. Exiting works focus on search by either image or
text. None of them attempted a multi-modal search approach, in which query
image and query text complement each other. Multi-modal person search is handy
when a partial person image is available such as a passport-sized image. At
the same time, the free text provides the rest of the body appearance.
Specifically, the CUHK-PEDES dataset can be extended with annotated bounding
boxes. Thus CUHK-PEDES has both annotated bounding boxes and textual
descriptions, making it a suitable candidate dataset for multi-modal person
search.

Attribute-based person search. It is a big challenge for a machine to learn
complex sentence syntax. Attribute-based person search method AIHM Dong et al.
(2019) outperforms the text-based method GNA-RNN Li et al. (2017b) evaluated
on cropped person images with attribute annotations. Therefore, it’s
worthwhile to collect attribute annotated scene images and further advance
attribute-based person search. The state-of-the-art text-based person search
method ViTAA Wang et al. (2020b) decomposes textual description to attributes
to learn fine-grained discriminative features. Attribute annotations may ease
this process and subsequently improve text-based person search performance.

Zero-shot person search. Text-based person search is essentially a zero-shot
learning problem, in which the query person is unseen in training. Dong et al.
(2019) formulates the attribute-based person search as a Zero-Shot Learning
(ZSL) problem. In zero-shot learning, zero training image is available at
training time, and only semantic representations such as textual descriptions
are available to infer unseen classes. Text-based person search can leverage
the knowledge of zero-shot learning, such as using adversarially generated
person features to augment training data.

##  5 Conclusion

In this survey, we provide a systematic review of the recent works on person
search. For the first time, we surveyed papers on text-based person search
which is less investigated than image-based person search. We briefly discuss
highly regarded methods from the perspective of challenges and solutions. We
summarise and compare person search methods’ performance and provide insights
that a person search method needs to address the joint challenge of
discriminative features, query-person gap, and detection-identification
inconsistency. We finally discuss some future research directions which may be
of interest to incumbent and new researchers in the field.

## References

  * Chang et al. [2018] Xiaojun Chang, Po-Yao Huang, Yi-Dong Shen, Xiaodan Liang, Yi Yang, and Alexander G. Hauptmann.  RCAA: Relational Context-Aware Agents for Person Search.  pages 84–100, 2018.
  * Chen et al. [2018a] Di Chen, Shanshan Zhang, Wanli Ouyang, Jian Yang, and Ying Tai.  Person Search via A Mask-guided Two-stream CNN Model.  pages 734–750, 2018.
  * Chen et al. [2018b] T. Chen, C. Xu, and J. Luo.  Improving Text-Based Person Search by Spatial Matching and Adaptive Threshold.  In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1879–1887, March 2018.
  * Chen et al. [2020] Di Chen, Shanshan Zhang, Jian Yang, and Bernt Schiele.  Norm-Aware Embedding for Efficient Person Search.  pages 12615–12624, 2020.
  * Cheng et al. [2017] De Cheng, Xiaojun Chang, Li Liu, Alexander G. Hauptmann, Yihong Gong, and Nanning Zheng.  Discriminative dictionary learning with ranking metric embedded for person re-identification.  In IJCAI, 2017.
  * Cheng et al. [2018] De Cheng, Yihong Gong, Xiaojun Chang, Weiwei Shi, Alexander G. Hauptmann, and Nanning Zheng.  Deep feature learning via structured graph laplacian embedding for person re-identification.  Pattern Recognit., 82:94–104, 2018.
  * Dong et al. [2019] Qi Dong, Shaogang Gong, and Xiatian Zhu.  Person Search by Text Attribute Query As Zero-Shot Learning.  pages 3652–3661, 2019.
  * Dong et al. [2020a] Wenkai Dong, Zhaoxiang Zhang, Chunfeng Song, and Tieniu Tan.  Bi-Directional Interaction Network for Person Search.  pages 2839–2848, 2020.
  * Dong et al. [2020b] Wenkai Dong, Zhaoxiang Zhang, Chunfeng Song, and Tieniu Tan.  Instance Guided Proposal Network for Person Search.  pages 2585–2594, 2020.
  * Gao et al. [2019] Cunyuan Gao, Rui Yao, Jiaqi Zhao, Yong Zhou, Fuyuan Hu, and Leida Li.  Structure-aware person search with self-attention and online instance aggregation matching.  Neurocomputing, 369:29–38, December 2019.
  * Han et al. [2019] Chuchu Han, Jiacheng Ye, Yunshan Zhong, Xin Tan, Chi Zhang, Changxin Gao, and Nong Sang.  Re-ID Driven Localization Refinement for Person Search.  pages 9814–9823, 2019.
  * He and Zhang [2019] Zhenwei He and Lei Zhang.  End-to-End Detection and Re-identification Integrated Net for Person Search.  In C. V. Jawahar, Hongdong Li, Greg Mori, and Konrad Schindler, editors, Computer Vision – ACCV 2018, Lecture Notes in Computer Science, pages 349–364, Cham, 2019. Springer International Publishing.
  * Hinton et al. [2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the Knowledge in a Neural Network.  arXiv:1503.02531 [cs, stat], March 2015.  arXiv: 1503.02531.
  * Hong et al. [2019] Z. Hong, B. Liu, Y. Lu, G. Yin, and N. Yu.  Scale Voting With Pyramidal Feature Fusion Network for Person Search.  IEEE Access, 7:139692–139702, 2019.  Conference Name: IEEE Access.
  * Islam [2020] Khawar Islam.  Person search: New paradigm of person re-identification: A survey and outlook of recent works.  Image and Vision Computing, 101:103970, September 2020.
  * Jing et al. [2020a] Y. Jing, W. Wang, L. Wang, and T. Tan.  Cross-Modal Cross-Domain Moment Alignment Network for Person Search.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 10675–10683, June 2020.  ISSN: 2575-7075.
  * Jing et al. [2020b] Ya Jing, Chenyang Si, Junbo Wang, Wei Wang, Liang Wang, and Tieniu Tan.  Pose-Guided Multi-Granularity Attention Network for Text-Based Person Search.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(07):11189–11196, April 2020.  Number: 07.
  * Lan et al. [2018] Xu Lan, Xiatian Zhu, and Shaogang Gong.  Person Search by Multi-Scale Matching.  pages 536–552, 2018.
  * Li et al. [2017a] Shuang Li, Tong Xiao, Hongsheng Li, Wei Yang, and Xiaogang Wang.  Identity-Aware Textual-Visual Matching With Latent Co-Attention.  pages 1890–1899, 2017.
  * Li et al. [2017b] Shuang Li, Tong Xiao, Hongsheng Li, Bolei Zhou, Dayu Yue, and Xiaogang Wang.  Person Search With Natural Language Description.  pages 1970–1979, 2017.
  * Li et al. [2019a] J. Li, F. Liang, Y. Li, and W. Zheng.  Fast Person Search Pipeline.  In 2019 IEEE International Conference on Multimedia and Expo (ICME), pages 1114–1119, July 2019.  ISSN: 1945-788X.
  * Li et al. [2019b] Zhihui Li, Wenhe Liu, Xiaojun Chang, Lina Yao, Mahesh Prakash, and Huaxiang Zhang.  Domain-aware unsupervised cross-dataset person re-identification.  In ADMA, 2019.
  * Liu et al. [2017a] Hao Liu, Jiashi Feng, Zequn Jie, Karlekar Jayashree, Bo Zhao, Meibin Qi, Jianguo Jiang, and Shuicheng Yan.  Neural Person Search Machines.  pages 493–501, 2017.
  * Liu et al. [2017b] Wenhe Liu, Xiaojun Chang, Ling Chen, and Yi Yang.  Early active learning with pairwise constraint for person re-identification.  In ECML PKDD, 2017.
  * Liu et al. [2018a] H. Liu, W. Shi, W. Huang, and Q. Guan.  A Discriminatively Learned Feature Embedding Based on Multi-Loss Fusion For Person Search.  In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 1668–1672, April 2018.  ISSN: 2379-190X.
  * Liu et al. [2018b] Wenhe Liu, Xiaojun Chang, Ling Chen, and Yi Yang.  Semi-supervised bayesian attribute learning for person re-identification.  In Sheila A. McIlraith and Kilian Q. Weinberger, editors, AAAI, 2018.
  * Liu et al. [2019] Jiawei Liu, Zheng-Jun Zha, Richang Hong, Meng Wang, and Yongdong Zhang.  Deep Adversarial Graph Attention Convolution Network for Text-Based Person Search.  In Proceedings of the 27th ACM International Conference on Multimedia, MM ’19, pages 665–673, New York, NY, USA, October 2019. Association for Computing Machinery.
  * Liu et al. [2020a] Chong Liu, Xiaojun Chang, and Yi-Dong Shen.  Unity style transfer for person re-identification.  In CVPR, 2020.
  * Liu et al. [2020b] Wenhe Liu, Xiaojun Chang, Ling Chen, Dinh Phung, Xiaoqin Zhang, Yi Yang, and Alexander G. Hauptmann.  Pair-based uncertainty and diversity promoting early active learning for person re-identification.  ACM Trans. Intell. Syst. Technol., 11(2):21:1–21:15, 2020.
  * Loesch et al. [2019] A. Loesch, J. Rabarisoa, and R. Audigier.  End-To-End Person Search Sequentially Trained On Aggregated Dataset.  In 2019 IEEE International Conference on Image Processing (ICIP), pages 4574–4578, September 2019.  ISSN: 2381-8549.
  * Lu et al. [2019] Y. Lu, Z. Hong, B. Liu, W. Li, and N. Yu.  Dhff: Robust Multi-Scale Person Search by Dynamic Hierarchical Feature Fusion.  In 2019 IEEE International Conference on Image Processing (ICIP), pages 3935–3939, September 2019.  ISSN: 2381-8549.
  * Munjal et al. [2019a] Bharti Munjal, Sikandar Amin, Federico Tombari, and Fabio Galasso.  Query-Guided End-To-End Person Search.  pages 811–820, 2019.
  * Munjal et al. [2019b] Bharti Munjal, Fabio Galasso, and Sikandar Amin.  Knowledge Distillation for End-to-End Person Search.  arXiv:1909.01058 [cs], September 2019.  arXiv: 1909.01058.
  * Sarafianos et al. [2019] Nikolaos Sarafianos, Xiang Xu, and Ioannis A. Kakadiaris.  Adversarial Representation Learning for Text-to-Image Matching.  pages 5814–5824, 2019.
  * Shi et al. [2018] W. Shi, H. Liu, F. Meng, and W. Huang.  Instance Enhancing Loss: Deep Identity-Sensitive Feature Embedding for Person Search.  In 2018 25th IEEE International Conference on Image Processing (ICIP), pages 4108–4112, October 2018.  ISSN: 2381-8549.
  * Wang et al. [2020a] Cheng Wang, Bingpeng Ma, Hong Chang, Shiguang Shan, and Xilin Chen.  TCTS: A Task-Consistent Two-Stage Framework for Person Search.  pages 11952–11961, 2020.
  * Wang et al. [2020b] Zhe Wang, Zhiyuan Fang, Jun Wang, and Yezhou Yang.  ViTAA: Visual-Textual Attributes Alignment in Person Search by Natural Language.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, Computer Vision – ECCV 2020, Lecture Notes in Computer Science, pages 402–420, Cham, 2020. Springer International Publishing.
  * Xiao et al. [2017] Tong Xiao, Shuang Li, Bochao Wang, Liang Lin, and Xiaogang Wang.  Joint Detection and Identification Feature Learning for Person Search.  pages 3415–3424, 2017.
  * Xiao et al. [2019] Jimin Xiao, Yanchun Xie, Tammam Tillo, Kaizhu Huang, Yunchao Wei, and Jiashi Feng.  IAN: The Individual Aggregation Network for Person Search.  Pattern Recognition, 87:332–340, March 2019.
  * Xu et al. [2014] Yuanlu Xu, Bingpeng Ma, Rui Huang, and Liang Lin.  Person Search in a Scene by Jointly Modeling People Commonness and Person Uniqueness.  In Proceedings of the 22nd ACM international conference on Multimedia, MM ’14, pages 937–940, New York, NY, USA, November 2014. Association for Computing Machinery.
  * Yan et al. [2019] Yichao Yan, Qiang Zhang, Bingbing Ni, Wendong Zhang, Minghao Xu, and Xiaokang Yang.  Learning Context Graph for Person Search.  pages 2158–2167, 2019.
  * Yang et al. [2017] Jinfu Yang, Meijie Wang, Mingai Li, and Jingling Zhang.  Enhanced Deep Feature Representation for Person Search.  In Jinfeng Yang, Qinghua Hu, Ming-Ming Cheng, Liang Wang, Qingshan Liu, Xiang Bai, and Deyu Meng, editors, Computer Vision, Communications in Computer and Information Science, pages 315–327, Singapore, 2017. Springer.
  * Zhai et al. [2019] Sulan Zhai, Shunqiang Liu, Xiao Wang, and Jin Tang.  FMT: fusing multi-task convolutional neural network for person search.  Multimedia Tools and Applications, 78(22):31605–31616, November 2019.
  * Zhang and Lu [2018] Ying Zhang and Huchuan Lu.  Deep Cross-Modal Projection Learning for Image-Text Matching.  pages 686–701, 2018.
  * Zhang et al. [2020] Xinyu Zhang, Xinlong Wang, Jia-Wang Bian, Chunhua Shen, and Mingyu You.  Diverse Knowledge Distillation for End-to-End Person Search.  arXiv:2012.11187 [cs], December 2020.  arXiv: 2012.11187.
  * Zheng et al. [2017] Liang Zheng, Hengheng Zhang, Shaoyan Sun, Manmohan Chandraker, Yi Yang, and Qi Tian.  Person Re-Identification in the Wild.  pages 1367–1376, 2017.
  * Zheng et al. [2020a] Dingyuan Zheng, Jimin Xiao, Kaizhu Huang, and Yao Zhao.  Segmentation mask guided end-to-end person search.  Signal Processing: Image Communication, 86:115876, August 2020.
  * Zheng et al. [2020b] Zhedong Zheng, Liang Zheng, Michael Garrett, Yi Yang, Mingliang Xu, and Yi-Dong Shen.  Dual-path Convolutional Image-Text Embeddings with Instance Loss.  ACM Transactions on Multimedia Computing, Communications, and Applications, 16(2):51:1–51:23, May 2020.
  * Zhong et al. [2020] Yingji Zhong, Xiaoyu Wang, and Shiliang Zhang.  Robust Partial Matching for Person Search in the Wild.  pages 6827–6835, 2020.


# Co-Design of Topology, Scheduling, and Path Planning in Automated Warehouses
††thanks: This research was supported in part by the National Science
Foundation (NSF) under Awards 1846524 and 2139982, the Office of Naval
Research (ONR) under Award N00014-20-1-2258, the Defense Advanced Research
Projects Agency (DARPA) under Award HR00112010003, and the 2022 Okawa Research
Grant. The project has also received funding from the European Union’s Horizon
2020 research and innovation program under the Marie Skłodowska-Curie grant
agreement No. 894237.

Christopher Leet1, Chanwook Oh1, Michele Lora1,2, Sven Koenig1, Pierluigi
Nuzzo1<EMAIL_ADDRESS>1University of
Southern California, Los Angeles, California, USA 2University of Verona,
Verona, Italy

###### Abstract

We address the _warehouse servicing problem_ (WSP) in automated warehouses,
which use teams of mobile agents to bring products from shelves to packing
stations. Given a list of products, the WSP amounts to finding a plan for a
team of agents which brings every product on the list to a station within a
given timeframe. The WSP consists of four subproblems, concerning _what_ tasks
to perform (task formulation), _who_ will perform them (task allocation), and
_when_ (scheduling) and _how_ (path planning) to perform them. These
subproblems are NP-hard individually and become more challenging in
combination. The difficulty of the WSP is compounded by the scale of automated
warehouses, which frequently use teams of hundreds of agents. In this paper,
we present a methodology that can solve the WSP at such scales. We introduce a
novel, contract-based design framework which decomposes an automated warehouse
into traffic system components. By assigning each of these components a
contract describing the traffic flows it can support, we can synthesize a
traffic flow satisfying a given WSP instance. Component-wise search-based path
planning is then used to transform this traffic flow into a plan for discrete
agents in a modular way. Evaluation shows that this methodology can solve WSP
instances on real automated warehouses.

##  I Introduction

An _automated warehouse_ is a warehouse which uses a team of mobile agents to
move products from its shelves to its packing stations. Over the past decade,
automated warehouses have become increasingly important to industrial
logistics and e-commerce. Today, companies such as Amazon routinely deploy
teams of hundreds of agents to manage large warehouse complexes [1]. An
automated warehouse must solve the _warehouse servicing problem_ (WSP) to
operate. In the WSP, we are given a warehouse and a list of products termed a
_workload_ , and asked to find a plan for a team of agents which brings every
product on the list to one of the warehouse’s stations within a given time
limit. The WSP consists of four interdependent sub-problems:

  1. 1.

_Task Formulation._ Which shelf and station should a product be taken and
brought to?

  2. 2.

_Task Assignment._ Which tasks should an agent perform?

  3. 3.

_Scheduling._ When should an agent perform its tasks?

  4. 4.

_Path Planning._ What path should an agent take through the warehouse to
perform each of its tasks?

Task assignment, scheduling, and path planning are NP-Hard [2].
Interdependence only increases the challenge of these sub-problems. As a
result, existing methodologies for performing task assignment, scheduling, and
path planning concurrently [3] do not scale beyond tens of agents. Automated
warehouses, however, often have hundreds of agents [1]. Methodologies for each
solving subcase of the WSP which omit one or more of these sub-problems have
also been proposed [4], but it is unclear whether any can be extended to the
full WSP. The question: _“is it possible to solve the WSP at scale?”_ is thus
open and highly relevant.

We answer the question in the affirmative by developing a novel traffic-
system-based methodology for the WSP. In a traffic-system-based warehouse,
each shelf and station is linked by a network of roads termed a _traffic
system_. The movement of agents through a traffic system is restricted by the
rules of the traffic system. Well chosen rules prune the space of potential
solutions to the WSP dramatically while preserving efficient solutions. Almost
all automated warehouses today use traffic systems to plan for their agents.

In this paper, we present the first formal framework for designing a warehouse
traffic system. This framework provides a designer with a library of traffic
system _components_ and rules for composing these components into a traffic
system. There are three types of components: _shelving rows_ , which provide
access to shelves, _station queues_ , which provide access to stations, and
_transports_ , which connect other components. The traffic flows that a
component can support are captured by an assume-guarantee contract termed a
_component contract_.

This compositional formalization of a traffic system allows for a
compositional formulation of the planning problem. In this formulation, a plan
is composed out of a set of _agent cycles_. An agent cycle is a cycle of
traffic system components containing a _target shelving row_ and _target
station queue_. The agents in an agent cycle loop through this cycle of
components, carrying products from the target shelving row to the target
station queue. We synthesize a plan for a WSP instance by finding a set of
agent cycles which solves this instance and satisfies the constraints posed by
a given traffic system.

Based on this compositional view of a plan, our methodology for synthesizing a
plan for a WSP instance proceeds as follows. The traffic flow required to
service the instance’s workload within the instance’s time limit is captured
by an assume-guarantee contract termed a _workload contract_. A traffic flow
is found which satisfies the conjunction of this workload contract with the
composition of the traffic system’s component contracts. This traffic flow
both solves the WSP instance and can be supported by the traffic system.

This traffic flow is then mapped to a set of agent cycles, which is converted
to a plan in a modular fashion. Each timestep, a component moves each agent
that it contains toward the next component in its agent cycle. Evaluations
show that our methodology can solve WSP instances with hundreds of agents and
thousands of tasks on real warehouse layouts in under a minute.

##  II Background

###  II-A Prior Work

While this paper is the first to formalize and solve the WSP problem, a
related problem termed the Multi-Agent Pickup and Delivery (MAPD) problem has
been studied [3]. In MAPD, we are given a set of tasks characterized by a
pickup vertex $v_{i}$, a delivery vertex $v_{j}$, and a release time $t$, and
asked to execute each task by moving an agent from $v_{i}$ to $v_{j}$ after
time $t$. Studied variants include lifelong MAPD [5], where a task is not
revealed until its release time, and deadline aware MAPD [6], where each task
has a deadline. These solvers are not directly applicable to the WSP problem,
however, because they do not perform task formulation and have not been shown
to scale beyond 50-75 agents.

###  II-B Assume-Guarantee Contracts

We provide an overview of the Assume-Guarantee (A/G) contract framework by
starting with the notion of a component. A component $M$ is an element of a
design, which can be connected with other components to form larger systems.
An A/G contract $\tilde{C}:=(V,\tilde{A},\tilde{G})$ is a triple where $V$ is
a set of component variables, $\tilde{A}$ is a set of _assumptions_ , that is,
the set of behaviors that a component $M$ expects from the environment, and
$\tilde{G}$ is the _guarantees_ , that is, the set of behaviors promised by
the component $M$ if the assumptions hold. A/G contracts can be combined via
the _composition ( $\otimes$)_ or _conjunction ( $\land$)_ operators. Let
$\tilde{C}_{1}$ and $\tilde{C}_{2}$ be contracts describing the components
$M_{1}$ and $M_{2}$. Taking the composition of $\tilde{C}_{1}$ and
$\tilde{C}_{2}$ produces a contract which describes the system formed by
composing the components $M_{1}$ and $M_{2}$. Taking the conjunction of
$\tilde{C}_{1}$ and $\tilde{C}_{2}$ produces a contract which combines the
requirements of the two contracts. Further details on the A/G contract
framework can be found in the literature [7].

##  III Problem Formulation

Figure 1: (left) An example warehouse and (right) its floorplan graph.

An automated _warehouse_
$W{}:=(G{},S{},R{},\boldsymbol{\rho}{},\boldsymbol{\Lambda}{})$ is represented
as a 5-tuple containing the following elements:

  * •

Floorplan Graph $G{}:=(V{},E{})$. An undirected graph representing the
warehouse’s floorplan where each vertex $v_{i}\in V{}$ represents a one-agent-
wide cell in the floorplan. There is an edge $(v_{i},v_{j})\in E{}$ if and
only if (iff) an agent can move from $v_{i}$ to $v_{j}$ without traversing
another cell.

  * •

Shelf Access Vertices $S{}\subset V{}$. The vertices in $V{}$ which an agent
can access a shelf from.

  * •

Station Vertices $R{}\subset V{}$. The vertices in $V{}$ which workers can
access an agent from.

  * •

Product Vector
$\boldsymbol{\rho}{}:=\langle\rho_{1},\ldots,\rho_{n{}}\rangle$. The products
that warehouse $W$ contains.

  * •

Location Matrix $\boldsymbol{\Lambda}{}$. A $|\boldsymbol{\rho}{}|\times|S{}|$
matrix where $\boldsymbol{\Lambda}_{k,l}\in\mathbb{N}$ is the number of units
of product $\rho_{k}$ accessible from shelf access vertex $v_{l}$.

Fig. 1 (left) shows a warehouse with two shelves and two stations. Shelves are
accessed from the east and west. Fig. 1 (right) shows the floorplan graph
$G{}:=(V{},E{})$ of this warehouse. If $v_{x,y}$ is the vertex in $V{}$
representing the cell at coordinates $(x,y)$, this warehouse has shelf access
vertices $S{}=\\{v_{0,2},v_{2,2},v_{4,2}\\}$ and stations
$R{}=\\{v_{1,0},v_{3,0}\\}$. If the shelves at $(1,2)$ and $(3,2)$ contain
$10$ units of product $\rho_{1}$ and $\rho_{2}$, respectively, this warehouse
has product vector $\boldsymbol{\rho}{}:=\langle\rho_{1},\rho_{2}\rangle$ and
location matrix:

$\boldsymbol{\Lambda}{}=\begin{bmatrix}10&10&0\\\ 0&10&10\end{bmatrix}.$

Products are carried by a team of mobile _agents_ $\boldsymbol{A}{}:=\langle
a_{1},a_{2},\ldots\rangle$. Time in a warehouse is discretized. At each
timestep $t$, an agent $a_{i}$ has state $(\pi_{i,t},\phi_{i,t})\in
V{}\times\\{\rho_{0}\\}\cup\boldsymbol{\rho}{}$, where $\pi_{i,t}$ and
$\phi_{i,t}$ are the vertex that agent $a_{i}$ occupies and the product
$\rho_{k}\in\boldsymbol{\rho}{}$ that it holds at time $t$ respectively. If
agent $a_{i}$ is not holding a product at time $t$, $\phi_{i,t}=\rho_{0}$.

A _$T{}$ timestep plan_ $(\boldsymbol{\pi}{},\boldsymbol{\phi}{})$ for a team
of $c{}$ agents is a pair of $c{}\times T{}$ matrices such that
$(\pi_{i,t},\phi_{i,t})$ is the state of agent $a_{i}\in\boldsymbol{A}{}$ at
time $t\in[1,T{}]$. A $T{}$-timestep plan is _feasible_ iff:

_(1)_ An agent $a_{i}$ moves by 0 or 1 vertices per timestep, that is, the
vertex $\pi_{i,t+1}$ that $a_{i}$ occupies at step $t+1$ is the same as or
adjacent to the vertex $\pi_{i,t}$ that $a_{i}$ occupies at step $t$:

$\forall\ t\in[1,T],\ \forall\ a_{i}\in\boldsymbol{A}{},\
\pi_{i,t+1}\in\\{\pi_{i,t}\\}\cup Adj(\pi_{i,t}).$

_(2)_ Two agents do not collide, that is, two agents
$a_{i},a_{j}\in\boldsymbol{A}{}$ do not occupy the same vertex or traverse the
same edge in opposite directions at the same timestep:

$\displaystyle\forall\ t\in[$ $\displaystyle 1,T],\ \forall\
a_{i},a_{j}\in\boldsymbol{A}{},$
$\displaystyle\pi_{i,t}\neq\pi_{j,t}\wedge\neg(\pi_{i,t+1}=\pi_{j,t}\wedge\pi_{i,t}=\pi_{j,t+1}).$

_(3)_ An agent can only pick up a product $\rho_{k}$ at a shelf access vertex
containing $\rho_{k}$ and put down a product at a station. Let
$\textsc{productsAt}(v)$ be the set of products accessible at vertex $v$ (if
$v\notin S$, $\textsc{productsAt}(v)=\emptyset$); then,

$\displaystyle\forall\ t\in[1,T],\ \forall\ a_{i}\in\boldsymbol{A}{},$
$\displaystyle\phi_{i,t+1}\in\begin{cases}\\{\rho_{0}\\}\cup\textsc{productsAt}(\pi_{i,t})&\phi_{i,t}=\rho_{0}\\\
\\{\rho_{0},\phi_{i,t}\\}&\pi_{i,t}\in R{}\\\
\\{\phi_{i,t}\\}&\text{otherwise}.\end{cases}$

A _workload_ is a vector $\boldsymbol{w}{}:=\langle
w_{1},\ldots,w_{n{}}\rangle$ where $w_{k}$ is the number of units of product
$\rho_{k}$ which must be transferred to a station. We say that a $T{}$
timestep plan _services_ workload $\boldsymbol{w}{}$ iff it is feasible and it
transfers $w_{k}$ units of each product $\rho_{k}\in\boldsymbol{\rho}{}$ to
the warehouse’s stations $R{}$.

######  Problem III.1 (Warehouse Servicing Problem)

Given a warehouse $W{}$, a workload $\boldsymbol{w}{}$, and a timestep limit
$T$, find a $T{}$ timestep plan containing an arbitrary number of agents which
services workload $\boldsymbol{w}{}$.

##  IV Co-Design Methodology

Figure 2: The high-level workflow of the methodology.

The structure of the methodology is shown in Fig. 2, providing a framework for
designing a traffic system (Subsection IV-A). The framework offers rules for
grouping the vertices in a warehouse floorplan graph $G{}$ into traffic system
components. The high-level movement of agents through a traffic system is
represented by an agent cycle set (Subsection IV-B). An agent cycle set is
converted into a plan in a modular fashion (Subsection IV-C), such that, at
each timestep, each component moves each agent it contains toward the next
component in that agent’s agent cycle set.

The methodology finds an agent cycle set for a traffic system which services a
workload $\boldsymbol{w}{}$ within $T{}$ timesteps as follows. The properties
of the flow of agents entering and leaving a component are compiled into an
A/G contract. The properties that a traffic system’s set of agent flows must
have to service workload $\boldsymbol{w}{}$ within $T{}$ timesteps are also
compiled into an A/G contract. An agent flow set satisfying the conjunction of
these contracts is found (Subsection 3) and mapped to an agent cycle set
(Subsection IV-E). By construction, the resulting agent cycle set is supported
by the traffic system.

###  IV-A Traffic System Design Framework

An operator can construct a _traffic system_ for a warehouse by dividing the
vertices in its floorplan graph into disjoint simple paths called traffic
system _components_. A component $C_{i}$ behaves similarly to a one way road.
Agents enter a component $C_{i}$ at its head $\textsc{head}({C_{i}})$ and exit
it from its tail $\textsc{tail}({C_{i}})$. A component may not contain both
shelf access vertices and station access vertices. A component is termed a:

  1. 1.

_shelving row_ if it contains shelf access vertices;

  2. 2.

_station queue_ if it contains station vertices;

  3. 3.

_transport_ if it contains neither.

Every station and shelf access vertex must be contained by a component. Other
vertices, however, need not be. Vertices which are not part of any component
are termed _unused vertices_ since they will not be traversed by any agent.

A component $C_{i}$ has 1 or 2 _inlet components_ $\textsc{inlets}({C_{i}})$
and 1 or 2 _outlet components_ $\textsc{outlets}({C_{i}})$. Agents must enter
$C_{i}$ from one of its inlets and exit $C_{i}$ from one of its outlets. There
must be an edge in the floorplan graph between the head of a component and the
tail of each of its inlets and the tail of a component and the head of each of
its outlets.

The connections between the components of a traffic system are represented by
a directed graph termed a _traffic system_ graph $G_{s}:=(V_{s},E_{s})$. Each
vertex in $V_{s}$ is a component of the traffic system. There is an arc
$(C_{i},C_{j})$ in $V_{s}$ iff component $C_{i}$ is one of component $C_{j}$’s
inlets. A traffic system graph must be strongly connected, that is, there must
be a path between any two components in a traffic system graph. Since every
shelf access and station access vertex is in a component, it follows that
there is a way for an agent to move from any shelf access vertex to any
station access vertex and _vice versa_.

###  IV-B Agent Cycle Set

We synthesize a plan for a traffic system $G_{s}$ which satisfies a workload
$\boldsymbol{w}{}$ within $T{}$ timesteps from an _agent cycle set_
$\Sigma{}$. An _agent cycle_ is a set of $b$ agents associated with a cycle of
$b$ components in the traffic system graph $G_{s}{}$. These components must
include a _target shelving row_ and a _target station queue_. The agents in an
agent cycle transfer products from the _target shelving row_ to the _target
station queue_.

An agent cycle set has a _cycle time_ $t_{c}{}$. At timestep $t=1$, each agent
in an agent cycle is positioned on a unique component. Every $t_{c}{}$
timesteps, each agent in an agent cycle advances one component. Thus, an agent
cycle delivers one product from its target shelving row to its target station
queue every $t_{c}{}$ timesteps. In Subsection IV-C we show how we find a plan
that realizes the agent movement specified by an agent cycle set. (Due to
space constraints, we do not specify the exact timesteps at which an agent
cycle picks up and drops off products at its target shelving row and target
station queue.) In Subsection 3, we show how we find an agent cycle set that
services a workload $\boldsymbol{w}{}$ within $T{}$ timesteps.

###  IV-C Realizing an Agent Cycle Set

Let the time interval $[1,T{}]$ be divided into the $\lfloor
T{}/t_{c}{}\rfloor$ _cycle periods_ $[1,t_{c}{}]$, $[t_{c}{}+1,2t_{c}{}]$,
etc. Let $|C_{i}|$ be the number of vertices in a component $C_{i}$ and $m$ be
the length of the longest component in a traffic system, i.e.,

$m:=\max(|C_{i}|:C_{i}\in V_{s}{}).$

The realization algorithm has the following property:

###### Property IV.1

Our realization algorithm can realize an agent cycle set $\Sigma$ if it has
cycle time $2m$ and there is no component $C_{i}$ contained by more than
$\lfloor|C_{i}|/2\rfloor$ agent cycles.

The realization algorithm moves an agent at least once every other timestep
until the agent advances to the next component in its agent cycle. It
therefore takes at most $2m$ timesteps for the realization algorithm to
advance any agent in any agent cycle by one component. The realization
algorithm assumes, however, that a component $C_{i}$ can send an agent to its
outlets at least once every other timestep. This condition is violated if a
component’s outlets fill up with agents, preventing them from accepting
additional agents. To prevent a component from filling up, the realization
algorithm prevents agents from advancing multiple components in a single cycle
period. Since each component $C_{i}$ is in at most $\lfloor|C_{i}|/2\rfloor$
agent cycles, no more than $2\cdot\lfloor|C_{i}|/2\rfloor$ unique agents will
occupy any component $C_{i}$ every cycle period. Since
$2\cdot\lfloor|C_{i}|/2\rfloor\leq|C_{i}|$, no component will ever fill up.

Realization Algorithm Initialization. At timestep $t=1$, we place an agent
associated with an agent cycle on an arbitrary vertex of each component that
the agent cycle passes through.

Realization Algorithm Timestep. We realize the location of the agents in a
traffic system at time $t+1$ from their locations at time $t$ by calling the
function $\textsc{ComponentTimestep}(C_{i},t,\pi_{1,t},\pi_{2,t},\ldots)$,
Algorithm 1, on every component $C_{i}$ in the traffic system.

Algorithm 1 ComponentTimestep($C_{i}$, $t+1$, $\pi_{1,t}$, $\pi_{2,t}$,
$\ldots$)

1:$t_{s}\leftarrow\textsc{CyclePeriodStartT}(t)$

2:$a_{j}\leftarrow\textsc{head}({\textsc{agents}(C_{i},t)})$

3:if $\pi_{j,t}=\textsc{head}({C_{i}})\wedge\textsc{advanceT}(a_{j})<t_{s}{}$
then

4: $k\leftarrow\textsc{cycleI}(a_{j})+1\mod|\textsc{cycle}(a_{j})|$

5: if $\textsc{accepting}(C_{i},\textsc{cycle}(a_{j})[k])$ then

6: $\pi_{j,t+1}\leftarrow\textsc{tail}({\textsc{cycle}(a_{j})[k]})$

7: $\textsc{cycleI}(a_{j})\leftarrow k$

8: $\textsc{advanceT}(a_{j})\leftarrow t+1$

9:for $a_{j}\in\textsc{agents}(C_{i},t)$ do

10: $v\leftarrow\textsc{next}(C_{i},\pi_{j,1})$

11: if $v\neq\bot\wedge\neg\exists\
a_{k}\in\textsc{agents}(C_{i},t):\pi_{k,t}=v$ then

12: $\pi_{j,t+1}\leftarrow v$

13: else

14: $\pi_{j,t+1}\leftarrow\pi_{j,t}$

Let $t_{s}{}$ be the time at which the current cycle period starts (Line 1),
$\textsc{agents}(C_{i},t)$ be a list of the agents in $C_{i}$ at time $t$
ordered by their distance from $\textsc{head}({C_{i}})$, and $a_{j}$ be the
agent at the head of this list (Line 2). If $a_{j}$ is at the head of $C_{i}$
and $\textsc{advanceT}(a_{j})$, the timestep when $a_{j}$ advanced to $C_{i}$,
was before $t_{s}{}$, we check if $a_{j}$ can advance to the next component in
its agent cycle $\textsc{cycle}(a_{j})$ (Line 3). We compute the index $k$ of
the next component in $\textsc{cycle}(a_{j})$ from the index
$\textsc{cycleI}(a_{j})$ of the current component in $\textsc{cycle}(a_{j})$
(Line 4). If the component $\textsc{cycle}(a_{j})[k]$ is accepting agents from
$C_{i}$, we move agent $a_{j}$ to this component’s tail (Lines 6-8). Next, we
move agents within $C_{i}$. Let $\textsc{next}(C_{i},u)$ be the vertex in
$C_{i}$ following vertex $u$, if one exists, and $\bot$ otherwise. We move
each agent $a_{j}\in\textsc{agents}(C_{i},t)$ to vertex
$\textsc{next}(C_{i},\pi_{j,1})$ if it exists and is not occupied by another
agent (Lines 9-14).

###  IV-D Synthesizing an Agent Flow Set

Figure 3: Synthesizing agent flows using contracts.

Let an _agent flow_ $f_{i,j,k}\in\\{0\\}\cup\mathbb{N}$ be the number of
agents that move from component $C_{i}$ to component $C_{j}$ carrying product
$\rho_{k}$ every $t_{c}{}$ timestep period in a plan. Let an _agent flow set_
$F{}$ be the set containing all of a plan’s agent flows:

$F{}:=\\{f_{i,j,k}:(C_{i},C_{j})\in
E_{s}{}\wedge\rho_{k}\in\boldsymbol{\rho}{}\\}.$

An agent flow set completely describes how agents move between the components
in a traffic system each cycle period. We synthesize an agent flow set which
services workload $\boldsymbol{w}{}$ within $T{}$ timesteps as follows.

A component $C_{i}$ assumes that the agent flows entering it have certain
properties and guarantees that the agent flows leaving it have certain
properties. These assumptions and guarantees are compiled into an A/G contract
$\tilde{C}_{i}:=(\tilde{A}_{i},\tilde{G}_{i})$, termed a _component contract_
(Fig. 3, yellow). Component contracts are composed into a _traffic system
contract_ $\tilde{C}_{TS}{}$ (Fig. 3, red) describing the agent flow sets that
the traffic system allows, i.e.,

$\tilde{C}_{TS}{}:=\bigotimes_{C_{i}\in V_{s}{}}\tilde{C}_{i}.$

The properties that a traffic system’s agent flow set must have to service
workload $\boldsymbol{w}{}$ within $T{}$ timesteps are compiled into an A/G
contract termed a _workload contract_ $\tilde{C}_{\boldsymbol{w}{}}{}$ (Fig.
3, blue). We attempt to synthesize an agent flow set which satisfies the
conjunction of the traffic system contract and workload contract
$\tilde{C}_{\boldsymbol{w}{}}{}$ (Fig. 3). If no such agent flow set exists, a
plan which services workload $\boldsymbol{w}{}$ within $T{}$ timesteps cannot
be synthesized using our methodology.

Component Contract Assumptions. As discussed in Subsection IV-C, at most
$\lfloor|C_{i}|/2\rfloor$ agents may enter any component $C_{i}\in V_{s}{}$ in
any cycle period, i.e.,

$\forall\ C_{i}\in V_{s}{},\
\sum_{\mathclap{C_{j}\in\textsc{inlets}({C_{i}})\qquad}}\quad\sum_{\rho_{k}\in\boldsymbol{\rho}{}}f_{j,i,k}\leq\left\lfloor\frac{|C_{i}|}{2}\right\rfloor.$

Since a flow $f_{i,j,k}$ is defined as a non-negative integer, the minimum
flow entering any component $C_{i}\in V_{s}{}$ is 0.

Component Contract Guarantees. Let $f^{out}_{i,k}\in\\{0\\}\cup\mathbb{N}$ be
the number of units of product $\rho_{k}$ transferred from an agent to a
station in component $C_{i}$ each cycle period. If component $C_{i}$ does not
contain a station, $f^{out}_{i,k}=0$. If component $C_{i}$ contains stations,
$f^{out}_{i,k}$ is between 0 and the number of agents entering component
$C_{i}$ carrying $\rho_{k}$ each cycle period, that is,

$f^{out}_{i,k}\in\begin{cases}\\{0\\}&|C_{i}\cap R{}|=0\\\
[0,\sum_{C_{j}\in\textsc{inlets}({C_{i}})}f_{j,i,k}]&\text{otherwise}\end{cases}.$

Let $f^{in}_{i,k}\in\\{0\\}\cup\mathbb{N}$ be the number of units of product
$\rho_{k}$ transferred from a shelf in component $C_{i}$ each cycle period. If
component $C_{i}$ does not contain shelves, $f^{in}_{i,k}=0$. If component
$C_{i}$ contains shelves, $f^{in}_{i,k}$ is limited by the number of units of
product $\rho_{k}$ that component $C_{i}$ contains. Let
$\textsc{unitsAt}(C_{i},\rho_{k})$ be the total number of units of product
$\rho_{k}$ available at $C_{i}$:

$\textsc{unitsAt}(C_{i},\rho_{k}):=\sum_{\mathclap{v_{j}\in C_{i}\cap
S{}}}\Lambda_{k,j}.$

Let $q_{c}{}:=\lfloor t_{c}{}/T{}\rfloor$ be the number of cycle periods
executable in $T{}$ timesteps. In $q_{c}{}$ cycle periods, a component can
transfer at most $\textsc{unitsAt}(C_{i},\rho_{k})/q_{c}{}$ units of product
$\rho_{k}$ each cycle period. It follows that:

$f^{in}_{i,k}\in\begin{cases}\\{0\\}&|C_{i}\cap S{}|=0\\\
[0,\textsc{unitsAt}(C_{i},\rho_{k})/q]&\text{otherwise}\end{cases}.$

A product can only be transferred to an unburdened agent. Thus, the total
number of products transferred to agents in $C_{i}$ each cycle period is
limited by the total number of unburdened agents entering $C_{i}$ each cycle
period.

$\sum_{\mathclap{\rho_{k}\in\boldsymbol{\rho}{}}}f^{in}_{i,k}\leq\sum_{\mathclap{C_{j}\in\textsc{inlets}({C_{i}})}}f_{j,i,0}.$

Agents cannot appear or disappear. Thus, the total flow of agents carrying
product $\rho_{k}$ out of component $C_{i}$ is:

  1. 1.

the total flow of agents carrying product $\rho_{k}$ into $C_{i}$,

  2. 2.

_plus_ the total number of unburdened agents given a unit of product
$\rho_{k}$ from a shelf in $C_{i}$ each cycle period,

  3. 3.

_minus_ the total number of agents which transfer a unit of product $\rho_{k}$
to a station in $C_{i}$ each cycle period. Overall,

$\displaystyle\forall\ C_{i},\rho_{k}\in V_{s}{}\times\boldsymbol{\rho}{},\
\sum_{\mathclap{C_{j}\in\textsc{outlets}({C_{i}})}\quad}f_{i,j,k}=\sum_{\qquad\mathclap{C_{j}\in\textsc{inlets}({C_{i}})}}f_{j,i,k}+f^{in}_{i,k}-f^{out}_{i,k}.$

An analogous expression can be written relating the total flow of unburdened
agents leaving and entering a component $C_{i}$:

$\displaystyle\forall\ C_{i}\in V_{s}{},\
\sum_{\mathclap{C_{j}\in\textsc{outlets}({C_{i}})}\quad}f_{i,j,0}=\sum_{\qquad\mathclap{C_{j}\in\textsc{inlets}({C_{i}})}}f_{j,i,0}+\sum_{\mathclap{\rho_{k}\in\boldsymbol{\rho}{}}}f^{in}_{i,k}-\sum_{\mathclap{\rho_{k}\in\boldsymbol{\rho}{}}}f^{out}_{i,k}.$

Workload Contract. A workload contract $\tilde{C}_{\boldsymbol{w}{}}{}$ makes
no assumptions. It guarantees that the total number of units of product
$\rho_{k}$ transferred to the warehouse’s stations each cycle period is
greater than $w_{k}/q_{c}{}$, where $w_{k}$ is the demand for $\rho_{k}$ in
workload $\boldsymbol{w}{}$ and $q_{c}{}$ is the number of cycle periods
$q_{c}{}$ executable in $T{}$ timesteps, i.e.,

$\forall\ \rho_{k}\in\boldsymbol{\rho}{},\ \sum_{\mathclap{C_{i}\in
V_{s}{}}}f^{out}_{i,k}\geq\frac{w_{k}}{q_{c}{}}.$

The above contracts (and associated constraints) are used to generate a
formula in propositional logic augmented with arithmetic constraints over the
reals, which is solved using a satisfiability modulo theory (SMT) solver to
produce the flow rate through every component for every product.

###  IV-E Mapping the Agent Flow Set to an Agent Cycle Set

By construction, an agent flow set $F{}$ has the properties:

###### Property IV.2

There is a set of paths $P_{k}$ on $G_{s}{}$ for each product $\rho_{k}$ such
that:

  1. 1.

There are exactly $f^{in}_{i,k}$ paths in $P_{k}$ beginning at each component
$C_{i}\in V_{s}{}$.

  2. 2.

There are exactly $f^{out}_{i,k}$ paths in $P_{k}$ ending at each component
$C_{i}\in V_{s}{}$.

  3. 3.

There are exactly $f_{i,j,k}$ paths that contain the edge $(C_{i},C_{j})$ for
each edge $(C_{i},C_{j})\in E_{s}{}$.

###### Property IV.3

There is a set of paths $P_{0}$ on $G_{s}{}$ such that:

  1. 1.

There are exactly $\sum_{\rho_{k}\in\boldsymbol{\rho}{}}f^{out}_{i,k}$ paths
in $P_{0}$ beginning at each component $C_{i}\in V_{s}{}$.

  2. 2.

There are exactly $\sum_{\rho_{k}\in\boldsymbol{\rho}{}}f^{in}_{i,k}$ paths in
$P_{0}$ ending at each component $C_{i}\in V_{s}{}$.

  3. 3.

There are exactly $f_{i,j,0}$ paths that contain the edge $(C_{i},C_{j})$ for
each edge $(C_{i},C_{j})\in E_{s}{}$.

Properties IV.2 and IV.3 imply that there is a bijection
$B_{F}:P_{0}\rightarrow\bigcup_{\rho_{k}\in\boldsymbol{\rho}{}}P_{k}$ for any
agent flow set $F{}{}{}$ such that if path $p\in P_{0}$ is mapped to path
$p^{\prime}\in\bigcup_{\rho_{k}\in\boldsymbol{\rho}{}}P_{k}$, then the head of
path $p$ is the tail of path $p^{\prime}$ and vice versa:

$\displaystyle
B_{F}(p)=p^{\prime}\Rightarrow\textsc{head}({p})=\textsc{tail}({p^{\prime}})\wedge\textsc{head}({p^{\prime}})=\textsc{tail}({p}).$

An agent cycle set $\Sigma{}$ is then formed from an agent flow set $F{}$ by
turning each pair of paths in the bijection $B_{F}{}$ into a cycle.

##  V Evaluations

Figure 4: Fulfillment Center Map.

The proposed methodology is implemented as an automatic toolchain. The
component and workload contracts are compiled and composed using the CHASE
framework [8]. An agent flow set satisfying these contracts is then found
using Z3 [9]. All other toolchain components are implemented in Python 3.9.
The methodology is evaluated on two real industrial scenarios taken from the
literature: a Kiva (now Amazon Robotics) fulfillment center [10] and a package
sorting center [11].

Fulfillment Center. A fulfillment center ships products to individual
consumers. A fulfillment center map is characterized by blocks of shelves in
its center and stations on its perimeter. The proposed approach is evaluated
on two fulfillment center maps, a real map borrowed from [10] with 1071 cells,
560 shelves, 4 stations, and 55 unique products and a synthetic map based on
[10] with 793 cells, 240 shelves, 1 station, and 120 products. The real
fulfillment center map is depicted in Fig. 4. Shelves are depicted as yellow
cells, stations as blue shelves, obstacles as grey cells and empty space as
white cells. The tail of each component is depicted as a green cell with an
exclamation mark. Every other vertex in a component is depicted as a purple
cell with an arrow pointing to the next vertex in the component.

Sorting Center. The methodology is also evaluated on a variant of the WSP
which takes place in a sorting center [11]. A sorting center sorts packages by
destination. A sorting center map is characterized by uniformly placed chutes
in its center and bins of unsorted packages on its perimeter. Each chute leads
to a shipping counter bound for a unique destination. An agent sorts a package
by ferrying it from a bin to the chute associated with its destination.
Typically, a bin is modeled as having an unlimited number of packages. The
goal is to fill each shipping container before it is scheduled to depart.

This problem is modeled as an WSP instance as follows. Let the $i$th chute be
modeled as a shelf containing an arbitrary amount of the product $\rho_{i}$.
Let each bin of unsorted products be modeled as a station. Let $n_{i}$ be the
number of packages that must be brought to the $i$th chute. An instance of the
WSP is generated where the demand for product $\rho_{i}$ is $n_{i}$. Solving
this WSP instance produces an agent cycle set where $n_{i}$ units of product
$\rho_{i}$ are brought from the $i$th chute to the bins of unsorted products.
Swapping the locations where agents pick up and drop off products generates
the desired solution.

Figure 5: Sorting Center Map.

The sorting center evaluation is conducted on a map based on [11]. This map
contains 406 cells, 32 chutes and, 4 bins. It is depicted in Fig. 5.

Experimental Hardware. Each evaluation was performed on an 2.6 GHz Intel(R)
Core i7-10705H CPU with 32 GB of RAM in a Ubuntu 20.04 VM run on Windows 11.

TABLE I: Benchmarking the methodology on 9 WSP instances. Map | Unique Products | Units Moved | Runtime (s)
---|---|---|---
| 36 | 160 | 8.054
Sorting Center | 36 | 320 | 8.343
| 36 | 480 | 14.437
| 55 | 550 | 6.939
Fulfillment 1 | 55 | 825 | 7.001
| 55 | 1100 | 8.014
| 120 | 1200 | 65.880
Fulfillment 2 | 120 | 1320 | 65.886
| 120 | 1440 | 67.825

Results. The three WSP instances were generated on each map. For each WSP
instance, Table I lists:

  1. 1.

the number of unique products placed in the warehouse.

  2. 2.

the total units of product moved to a station.

  3. 3.

the time required to generate an agent flow set (the time required to convert
an agent flow set into a plan is small).

The length $T$ of a plan for each WSP instance was limited to 3,600 timesteps.
Solver runtime was limited to 1 hour.

The proposed methodology was able to solve an WSP instance where more than
1400 products had to be moved to a station in just over a minute. We
benchmarked the methodology on this instance against Iterated EECBS [4], a
state-of-the-art search-based lifelong path planner as follows. Iterated EECBS
was given the start position of each agent in our solution. It was asked to
find a plan where each agent visited the same sequence of shelves and stations
as it did in our solution. Iterated EECBS failed to terminate after an hour.

The runtime of traditional multi-agent path planners is exponential to the
size of their team of agents, the number of locations that an agent has to
visit, and the average distance between the locations that an agent has to
visit. Our proposed methodology, by contrast, is exponential in the number of
components in the traffic system (finding a set of agent flows is reducible to
the Integer Linear Programming problem). As a result, our methodology
outscales state-of-the-art path planners. Additionally, our methodology is
relatively insensitive to the number of products in a WSP instance. On both
the sorting center and fulfillment center, doubling the units of product in
the workload increased runtime by less than 10%.

##  VI Conclusion

In this paper we introduce the first methodology for solving the warehouse
servicing problem. This methodology provides a designer with a formal
framework for designing a warehouse traffic system. The traffic flows that
each component can support are captured using contracts. Combining these
contracts with a contract capturing the traffic flow that a workload for a
warehouse requires allows us to synthesize a traffic flow satisfying a given
WSP instance. A simple deterministic algorithm is used to convert this traffic
flow into a plan for discrete agents. The proposed methodology is evaluated on
maps taken from real automated warehouses and shown to be able to solve WSP
instances on these maps involving more than a thousand products in just over a
minute. In future work, we hope to find a bounded-suboptimal solution to the
WSP. In particular, we intend to look at ways to iteratively refine our
feasible solution into an optimal solution.

## References

  * [1] E. Ackerman, “Amazon Uses 800 Robots to Run This Warehouse,” https://spectrum.ieee.org/amazon-introduces-two-new-warehouse-robots, IEEE Spectrum, 2021, accessed: 16-May-2022.
  * [2] J. D. Ullman, “NP-Complete Scheduling Problems,” _Journal of Computer and System Sciences_ , vol. 10, no. 3, pp. 384–393, 1975.
  * [3] M. Liu, H. Ma, J. Li, and S. Koenig, “Task and Path Planning for Multi-Agent Pickup and Delivery.” in _Proc. of the International Joint Conference on Autonomous Agents and Multiagent Systems Search_ , 2019, pp. 11 560–11 565.
  * [4] J. Li, W. Ruml, and S. Koenig, “EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding,” _Proc. of the AAAI Conference on Artificial Intelligence_ , vol. 35, pp. 12 353–12 362, 2021.
  * [5] H. Ma, W. Honig, T. K. Satish, N. Ayanian, and S. Koenig, “Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery.” in _Proc. of the AAAI Conference on Artificial Intelligence_ , 2019, p. 7651–7658.
  * [6] X. Wu, Y. Liu, X. Tang, W. Cau, F. Bai, G. Khonstantine, and G. Zhao, “Multi-Agent Pickup and Delivery with Task Deadlines.” in _Proc. of the International Symposium on Combinatorial Search_ , 2021, p. 206–208.
  * [7] A. Benveniste, B. Caillaud, D. Nickovic, R. Passerone, J.-B. Raclet, P. Reinkemeier, A. Sangiovanni-Vincentelli, W. Damm, T. A. Henzinger, K. G. Larsen _et al._ , “Contracts for System Design,” _Foundations and Trends in Electronic Design Automation_ , vol. 12, pp. 124–400, 2018.
  * [8] P. Nuzzo, M. Lora, Y. A. Feldman, and A. L. Sangiovanni-Vincentelli, “CHASE: Contract-based Requirement Engineering for Cyber-Physical System Design,” in _Proc. of the 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2018, pp. 839–844.
  * [9] L. d. Moura and N. Bjørner, “Z3: An efficient SMT solver,” in _Proc. of the International conference on Tools and Algorithms for the Construction and Analysis of Systems_. Springer, 2008, pp. 337–340.
  * [10] P. R. Wurman, R. D’Andrea, and M. Mountz, “Co-ordinating Hundreds of Cooperative, Autonomous Vehicles in Warehouses,” in _Proc. of the AAAI Conference on Artificial Intelligence_ , 2007, p. 1752–1760.
  * [11] Q. Wan, C. Gu, S. Sun, M. Chen, H. Huang, and X. Jia, “Lifelong Multi-Agent Path Finding in a Dynamic Environment,” in _The International Conference on Control, Automation, Robotics and Vision_ , 2018, p. 875–882.