# TBD Pedestrian Data Collection: Towards Rich, Portable, and Large-Scale
Natural Pedestrian Data

Allan Wang1, Daisuke Sato1, Yasser Corzo1, Sonya Simkin1, and Aaron Steinfeld1
1The authors are with the Robotics Institute, Carnegie Mellon University, 5000
Forbes Avenue, Pittsburgh, PA, USA {allanwan, daisukes, ycorzo,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Social navigation and pedestrian behavior research has shifted towards machine
learning-based methods and converged on the topic of modeling inter-pedestrian
interactions and pedestrian-robot interactions. For this, large-scale datasets
that contain rich information are needed. We describe a portable data
collection system, coupled with a semi-autonomous labeling pipeline. As part
of the pipeline, we designed a label correction web app that facilitates human
verification of automated pedestrian tracking outcomes. Our system enables
large-scale data collection in diverse environments and fast trajectory label
production. Compared with existing pedestrian data collection methods, our
system contains three components: a combination of top-down and ego-centric
views, natural human behavior in the presence of a socially appropriate
“robot”, and human-verified labels grounded in the metric space. To the best
of our knowledge, no prior data collection system has a combination of all
three components. We further introduce our ever-expanding dataset from the
ongoing data collection effort – the TBD Pedestrian Dataset and show that our
collected data is larger in scale, contains richer information when compared
to prior datasets with human-verified labels, and supports new research
opportunities.

##  I Introduction

Pedestrian datasets are essential tools for modeling socially appropriate
robot behaviors, recognizing and predicting human actions, and studying
pedestrian behavior. Researchers may use these data to predict future
pedestrian motions, including forecasting their trajectories [1, 17, 18],
and/or navigation goals [20, 24]. In social navigation, datasets can also be
used to model [33, 21] or evaluate robot navigation behavior [4]. For this, an
in-the-wild pedestrian dataset that is large-scale and supports ground-truth
metric labels is desired.

However, existing public pedestrian datasets are either unlabelled [19, 34],
only rely on labels produced by an automated pipeline [5, 25], only contain
pixel level information [36, 32] or are small in scale [35, 23, 27]. We
propose a system that can collect large quantities of quality data
efficiently. The data collected using our system feature a novel full
combination of three critical elements: a combination of top-down and ego-
centric views, natural human motion, and human-verified labels grounded in the
metric space. This allows the data collected using our system to contain rich
information.

Figure 1: This set of images represent the same moment recorded from multiple
sensors: a) Top-down view image taken by a static camera with grounded
pedestrian trajectory labels shown. b) Ego-centric point cloud from a 3D LiDAR
with the projected trajectories from (a). c) Ego-centric RBG and depth images
from the mounted stereo camera. Green vertical bars represent the projected
labels. Note that two pedestrians at the back are partially and completely
occluded from the stereo camera.

Large datasets with quality labels and rich information can assist in
addressing human behavioral research questions that require the modeling of
interaction. For example, a key problem researchers have tried to address is
the freezing robot problem [43]. Researchers have attributed this problem to
the robot’s inability to model interactions [41]. Some works [31] have used
datasets to show that modeling the anticipation of human reactions to the
robot’s actions enables the robot to deliver a better performance. However,
interactions are diverse and uncommon in human crowds, they contain many types
[28] and can further be diversified by the environment (e.g. an open plaza or
a narrow corridor), so pedestrian datasets need to be large-scale in order to
capture enough interaction data.

Autonomous vehicle datasets [7, 12] have inspired a plethora of research.
However, a dataset of similar caliber and label quality in pedestrian-dominant
environments has yet to arrive. As a step toward this goal, we have
constructed a data collection system that can achieve these two requirements:
large data quantity and diversity, and human-verified positional labels.
First, we ensure that our equipment is portable and easy to set up. This
allows collecting data in a variety of locations with limited lead time.
Second, we address the challenge of labeling large quantities of data using a
semi-autonomous labeling pipeline. We employ a state-of-the-art deep learning-
based [51] tracking module combined with a human inspection and tracking
error-fixing web app to semi-automatically produce high-quality ground truth
pedestrian trajectories in metric space. We make the web app open-
source111https://github.com/CMU-TBD/tbd_label_correction_UI so that other
researchers can use this tool or contribute to this effort.

While we hope our contributions support robot system improvements in the
community and we aim to accommodate a wide variety of pedestrian behavior
research, our dataset primarily supports human environment navigation research
that requires ground truth pedestrian positional information, such as social
navigation, pedestrian trajectory prediction, and ego-centric perception.
Specifically, we include three important characteristics. (1) Top-down view
and ego-centric views: This ensures that the robot has access to ground-truth
data even with occlusions. (2) Natural human motion: The manual pushing of the
inconspicuous suitcase robot mitigates the curiosity effects of nearby
pedestrians. And (3) Ground truth labeling in metric space: This allows our
dataset to be useful for research where positional pedestrian data are needed.
To the best of our knowledge, publicly available datasets only have at most
two of these characteristics.

We demonstrate our system through a dataset collected in a large indoor space:
the TBD Pedestrian Dataset222https://tbd.ri.cmu.edu/tbd-social-navigation-
datasets. Our dataset contains scenes with a variety of crowd densities and
pedestrian interactions. We show through our analysis that our dataset (Batch
1: 133 minutes - 1416 trajectories; Batch 2: 626 minutes - 10300 trajectories)
is larger in scale and contains unique characteristics compared to prior
similar datasets. This is an ongoing effort and we plan to collect additional
data in more diverse locations.

##  II Related Work

With the explosion of data-hungry machine learning methods in robotics, demand
for pedestrian datasets has been on the rise in recent years. One popular
category of research in this domain is human trajectory prediction (e.g., [1,
17, 39, 30, 18, 20, 24, 46]). Much of this research utilizes selected
mechanisms to model pedestrian interactions in hopes for better prediction
performance (e.g., pooling layers in the deep learning frameworks [1, 17] or
graph-based representations [30]). Rudenko et al. [38] provides a good summary
into this topic. While the state-of-the-art performance keeps improving with
the constant appearance of newer models, it is often unclear how well these
models can generalize in diverse environments. As shown in [38], many of these
models only conduct their evaluation on the relatively small-scale ETH [35]
and UCY [23] datasets.

Another popular demand for pedestrian datasets comes from social navigation
research. Compared to human motion prediction research, social navigation
research focuses more on planning. For example, social navigation research
uses learning-based methods to identify socially appropriate motion for better
robot behavior, such as deep reinforcement learning [14, 10, 11] or inverse
reinforcement learning [33, 42]. Due to the lack of sufficiently large
datasets, these models often train in simulators that lack realistic
pedestrian behavior. Apart from training, datasets are also increasing in
popularity in social navigation evaluation due to their realistic pedestrian
behavior [15]. Social navigation methods are often evaluated in environments
using pedestrian data trajectory playback (e.g., [44, 8, 41, 47]). However,
similar to human motion prediction research, these evaluations are typically
only conducted on the ETH [35] and UCY [23] datasets, as shown by [15]. These
two datasets only use overhead views, and therefore lack the ego-centric view
used by most robots.

Large-scale and high-quality datasets exist for other navigation-related
applications and research. Autonomous vehicle datasets such as nuScenes [7],
Cityscapes [12] and ArgoVerse [48] also contain pedestrian-related data.
However, pedestrians often have limited appearances on sidewalks or at
crosswalks. There is also no data on how pedestrians navigate indoors. Another
group of similar datasets mainly supports computer vision-related research,
such as MOT [13] for pedestrian tracking, and Stanford Drone Dataset (SDD)
[36] and VIRAT [32] for pedestrian motion/goal prediction on the image level.
Detailed comparisons of the characteristics between the TBD Pedestrian Dataset
and similar existing datasets can be found in section IV-A.

Simulators can fill in the role of datasets for both training and evaluation.
Simulators such as PedSIM [16], CrowdNav [10], SocNavBench [4] and SEAN [45]
are in use by the research community. However, sim-to-real transfer is an
unsolved problem in robotics. Apart from lack of fidelity in visuals and
physics, pedestrian simulators in particular entail the additional paradox of
pedestrian behavior realism [29]: If pedestrian models are realistic enough
for use in simulators, why don’t we apply the same model to social navigation?

##  III System Description

###  III-A Hardware Setup

Figure 2: Sensor setup used to collect the TBD Pedestrian Dataset. (left) One
of the nodes used to capture top-down RGB views. (middle) The cart used to
capture ego-centric sensor views during data collection for Set 1. (right) The
suitcase robot used to capture ego-centric sensor views during data collection
for Set 2.

Our system supports multiple static FLIR Blackfly RGB cameras for labeling and
metric space calculations (Figure 2). The TBD Pedestrian Dataset contains two
different configuration sets for the same physical space. Both sets include
three cameras surrounding the scene on the upper floors overlooking the ground
level at roughly 90 degrees apart from each other (Figure 3). The RGB cameras
are connected to portable computers powered by lead-acid batteries. The
multiple cameras complement each other’s coverage, because even from overhead
views, partial occlusions occur. We used the three overhead view cameras to
label trajectories. We also positioned three more units on the ground floor,
but did not use them for pedestrian labeling.

In addition to static cameras, we pushed a cart (Set 1) or robotic suitcase
[22] (Set 2) through the scene. The cart (Figure 2) was equipped with a ZED
stereo camera to collect ego-centric RGB-D views of the scene. A GoPro Fusion
360 camera for capturing high definition 360 videos of nearby pedestrians was
mounted above the ZED. Data from the 360 camera is useful for capturing
pedestrian pose data and facial expressions for future work. The ZED camera
was powered by a laptop with a power bank. Our entire data collection hardware
system is portable and does not require power outlets, thereby allowing data
collection outdoors or in areas where wall power is inaccessible.

The robotic suitcase (Set 2) is a converted carry-on rolling suitcase. It is
equipped with an IMU and a 3D LiDAR sensor. In addition, the same ZED camera
and GoPro Fusion 360 camera are mounted on the suitcase handle. The robot’s
computer, batteries, and all its internal components are hidden inside the
suitcase, so pushing the robot resembles pushing a suitcase. We selected this
robot because of its inconspicuous design to reduce curious, unnatural
reactions from nearby pedestrians, as curious pedestrians may intentionally
block robots or display other unnatural movements [6]. While it is true that
real-world pedestrians will react to mobile robots curiously in the short term
and some may argue in favor of a more robotic appearance, we envision that
such curiosity effects will die down in the long term.

During certain data collection sessions, we pushed the cart or the suitcase
robot from one end of the scene to another end, while avoiding pedestrians and
obstacles along the way in a natural motion similar to a human pushing a
delivery cart or walking with a suitcase. This collects ego-centric views from
a mobile robot traversing through the human environment. However, unlike other
datasets such as [49], [27], [19] and [34] that use a tele-operated robot, or
[37] that uses a scripted policy to act autonomously, we chose to have all
motion performed by the human walking with the system. This provides better
trajectory control, increased safety, and further reduced the novelty effect
from surrounding pedestrians.

Both sets of data collection occurred on the ground level in a large indoor
atrium area (Figure 3). Half of the atrium area has fixed entry/exit points
that lead to corridors, elevators, stairs, and doors to the outside. The other
half of the atrium is adjacent to another large open area and is unstructured
with no fixed entry/exit points. We collected data around lunch and dinner
times to ensure higher crowd densities. Additional data collection are planned
at more diverse locations.

Figure 3: Hardware setup for the TBD Pedestrian Dataset. Blue circles indicate
positions of RGB cameras. Green box shows our suitcase robot pushed through
the scene. The white area is where trajectory labels are collected.

###  III-B Post-processing Pipelines

To ensure time synchronization across the captured videos, we employed
Precision Time Protocol over a wireless network to synchronize each of the
computers powering the cameras. In addition, we used an LED light and check
for the light signal during the post-processing stage to synchronize the
frames of all captured data for each recording session.

The next step is to localize the cart/suitcase in the scene. For Set 1, this
was achieved by identifying the cart/suitcase on the overhead camera videos
and then applying the camera matrices to obtain the metric coordinates. For
Set 2, we first made a map inside the building and then computed its location
in the post processing phase by utilizing the robotic suitcase software
333https://github.com/cmu-cabot powered by Cartographer
444https://github.com/cartographer-project/cartographer.

For pedestrian tracking, we first tracked the pedestrians on the overhead
camera videos. We found ByteTrack [51] to be very successful in tracking
pedestrians in the image space. Upon human verification over our entire data,
ByteTrack successfully tracks $95.1\%$ of the pedestrians automatically.

For the automatically tracked labels in pixel space, we needed to convert them
into metric space. Each camera video contained a set of tracked trajectories
in the image space. We estimated the 3D trajectory coordinates for each pair
of 2D trajectories from different cameras and the set of estimated coordinates
that resulted in the lowest reprojection error were selected to be the
trajectory coordinates in the metric space.

###  III-C Human Label Verification

Figure 4: App interface for the human verification process. It contains a
media player and various options to fix tracking errors automatically and
manually.

To ensure the label quality of the data, human verification of the tracked
trajectories from ByteTack is desired. Semi-autonomous labeling procedures are
common in autonomous driving datasets and pedestrian datasets. However,
surveying existing pedestrian datasets literature, we noticed that datasets
that do contain human-verified metric space labels are often relatively small
[35, 23, 9, 27], and large-scale datasets often only use automated tracking
pipelines [25, 32, 5] or do not label surrounding pedestrians [19, 34]. We
attribute this to a lack of tools to streamline the human verification
process.

To this end, we designed an open-source web app (Figure 4) using Matlab App
Designer. The tool was designed to minimize complete human relabeling of
erroneously tracked trajectories. The app contains a media player. When using
the app, human labelers only need to watch videos with the automatically
tracked trajectories. When an error is noticed, the labeler only needs to
indicate to the system the type and location of the error. The system then
fixes the errors in the background, and updates the trajectory visualization
accordingly. Currently, the app contains the following set of error-fixing
options:

  * •

Break: Used when ByteTrack incorrectly assigns the same trajectory to two
different pedestrians.

  * •

Join: Used when two different trajectories actually belong to the same
pedestrian.

  * •

Delete: Used when a ghost trajectory appears, such as incorrectly tracking an
unworn jacket as a pedestrian.

  * •

Disentangle: Used when the two trajectories of two pedestrians swapped in the
middle, which can happen when one partially occludes the other.

The web app also supports undoing previous actions, partial or complete
relabeling of trajectories, and labeling missing trajectories. For future
work, we are looking at possible platforms to launch the app so that the human
verification process can be a crowdsource effort.

Combined with ByteTrack, it took an expert labeler about 30 hours to produce
human-verified labels for 375K frames of data, or 10300 trajectories.
ByteTrack successfully tracks $95.1\%$ of trajectories. Among the trajectory
errors that require human rectification, $0.35\%$ are fixed by “Break”,
$1.25\%$ are fixed by “Join”, $0.29\%$ are fixed by “Delete”, $0.89\%$ are
fixed by “Disentangle”, $1.21\%$ are fixed by “Relabel”, and $0.48\%$ are
fixed by “Missing”.

##  IV Dataset Characteristics and Analysis

###  IV-A Comparison with Existing Datasets

TABLE I: A survey of existing pedestrian datasets on how they incorporate the three components in section IV-A. For component 1, a “No” means either not human verified or not grounded in metric space. For component 2, TD stands for “top-down view” and “E” stands for “ego-centric view”. Datasets | Comp. 1 | Comp. 2 | Comp. 3
---|---|---|---
| (metric labels) | (views) | (“robot”)
TBD (Ours) | Yes | TD + E | Human + Robot
ETH [35] | Yes | TD | N/A
UCY [23] | Yes | TD | N/A
Edinburgh Forum [25] | No | TD | N/A
VIRAT [32] | No | TD | N/A
Town Centre [3] | No | TD | N/A
Grand Central [52] | No | TD | N/A
CFF [2] | No | TD | N/A
Stanford Drone [36] | No | TD | N/A
L-CAS [49] | No* | E | Robot
WildTrack [9] | Yes | TD | N/A
JackRabbot [27] | Yes | E | Robot
ATC [5] | No | TD | N/A
THÖR [37] | Yes | TD + E | Robot
SCAND [19] | No | E | Robot
Crowd-Bot [34] | No | E | Human + Robot

Compared to existing datasets collected in natural pedestrian-dominant
environments, our TBD pedestrian dataset contains three components that
greatly enhances the dataset’s utility. These components are:

Human verified labels grounded in metric space. ETH [35] and UCY [23] datasets
are the most popular datasets among human behavior analysis papers [38]. We
believe this is partly because the trajectory labels in these datasets are
human verified and are grounded in metric space rather than pixel space (e.g.
[36] and [3] only contain labels in bounding boxes). Having labels grounded in
metric space eliminates the possibility that camera poses might have an effect
on the scale of the labels. It also makes the dataset useful for robot
navigation related research because robots plan in the metric space rather
than pixel space.

Combination of top-down views and ego-centric views. Similar to datasets with
top-down views, we used top-down views to obtain ground truth trajectory
labels for every pedestrian present in the scene. Similar to datasets with
ego-centric views, we gathered ego-centric views from a “robot” to imitate
robot perception of human crowds. A dataset that contains both top-down views
and ego-centric views will be useful for research projects that rely on ego-
centric views. This allows ego-centric inputs to their models, while still
having access to ground truth knowledge of the entire scene.

Naturalistic human behavior with the presence of a “robot”. Unlike datasets
such as [49], [27], [19], and [34], the “robot” that provides ego-centric view
data collection is a cart or a suitcase robot being pushed by human. As
mentioned in section III-A, doing so reduces the novelty effects from the
surrounding pedestrians. Having the “robot” pushed by humans also ensures
safety for the pedestrians and its own motion has less jerk and more humanlike
behavior.

As shown in Table I, current datasets only contain at most two of the three
components555*L-CAS dataset does provide human verified labels grounded in the
metric space. However, its pedestrian labels do not contain trajectory data..
A close comparison is the THÖR dataset [37], but its ego-centric view data are
collected by a robot running on predefined trajectories. Additionally, unlike
all other datasets in Table I, the THÖR dataset is collected in a controlled
lab setting rather than in the wild. This injects artificial factors into
human behavior.

###  IV-B Dataset Size

TABLE II: Dataset comparison statistics, for those with human verified labels grounded in metric space. Numbers in parenthesis are for data that includes the ego-centric view. Datasets | Time length | # Trajectories | Label Freq (Hz)
---|---|---|---
TBD Set 1 | 133 (51) mins | 1416 | 60
TBD Set 2 | 626 (213) mins | 10300 | 10
ETH [35] | 25 mins | 650 | 15
UCY [23] | 16.5 mins | 786 | 2.5
WildTrack [9] | 200 sec | 313 | 2
JackRabbot [27] | 62 mins | 260 | 7.5
THÖR [37] | 60+ mins | 600+ | 100

Table II demonstrates the ability of a semi-automatic labeling pipeline to
produce large amounts of data. With the aid of an autonomous tracker, humans
only need to verify and make occasional corrections on the tracking outcomes
instead of locating the pedestrians on every single frame. The data we have
collected so far surpassed all other datasets that provide human-verified
labels in the metric space in terms of total time and number of pedestrians.
We will continue this effort and collect more data for future work.

###  IV-C Dataset Statistics

TABLE III: Comparison of statistics between our dataset and other datasets according to the methods in [37]. Datasets | Tracking | Percep. | Motion | Min Dist.
---|---|---|---|---
Duration | Noise | Speed | To Ped.
[$s$] | [$ms^{-2}$] | [$ms^{-1}$] | [$m$]
TBD Set 2 | $25.6\pm 57.1$ | $1$ | $0.88\pm 0.52$ | $1.25\pm 1.44$
THÖR [37] | $16.7\pm 14.9$ | $0.12$ | $0.81\pm 0.49$ | $1.54\pm 1.60$
ETH [35] | $9.4\pm 5.4$ | $0.19$ | $1.38\pm 0.46$ | $1.33\pm 1.39$
ATC [5] | $39.7\pm 64.7$ | $0.48$ | $1.04\pm 0.46$ | $0.61\pm 0.16$
Edinburgh | $10.1\pm 12.7$ | $0.81$ | $1.0\pm 0.64$ | $3.97\pm 3.5$
[25]

Extending the evaluations performed in THÖR [37], we added the same suite of
analysis on Set 2 of our TBD dataset. The evaluation metrics were the
following. (1) Tracking Duration ($s$): Average time duration of tracked
trajectories. (2) Perception Noise ($ms^{-2}$): The average absolute
acceleration of the trajectories. (3) Motion Speed ($ms^{-1}$): Velocities of
the trajectories measured in 1 second intervals. (4) Minimum Distance Between
People ($m$): Minimum Euclidean distance between two closest observed people.

As shown in Table III, our dataset has considerable average trajectory
duration ($\pm 25.6$) and large variation ($\pm 57.1$), second only to ATC,
which has a $900m^{2}$ coverage. While our dataset has a much smaller
coverage, we attribute this to the presence of pedestrians changing navigation
goals and static pedestrians in our dataset. Static pedestrians include
standing pedestrians having conversations or pedestrians sitting on chairs.
Their presence in our dataset often has a long duration, which also causes big
variation in this metric. The tracking noise of our system was sub-optimal
when compared to other datasets, which is likely due to noisy tracking of the
sitting pedestrians. We observed that sitting pedestrians change their body
poses frequently, which causes the tracked bounding boxes to change size
frequently. We will investigate how to improve this for future work. The
motion speeds of our dataset trajectories are lower ($0.88$), which suggests
the presence of more static pedestrians. We also have the second-highest
variation in motion speed ($\pm 0.52$), suggesting that our dataset captures a
wide range of pedestrian behavior. From the minimum distance between people,
it can be inferred that our dataset captures both dense and sparse population
scenarios, as indicated by the middle mean value ($1.25$) among the others and
high variance ($\pm 1.44$). Note that [37] also measures trajectory
curvatures, but we noticed that this measurement is heavily affected by how
static pedestrians are processed. [37] does not provide any details on this,
so we decided not to evaluate this metric.

###  IV-D Behavior Distribution Analysis

TABLE IV: Trajectory prediction displacement error on ETH/UCY datasets and TBD dataset Set 2.  | ETH/UCY Dataset
---|---
Models | Static + Dynamic | Dynamic
ADE($m$) | FDE($m$) | ADE($m$) | FDE($m$)
Social-GAN [17] | 0.48 | 0.96 | 0.59 | 1.13
Trajectron++ [40] | 0.27 | 0.49 | 0.35 | 0.65
AgentFormer [50] | 0.23 | 0.39 | 0.25 | 0.44
| TBD Set 2
Social-GAN | 0.36 | 0.72 | 0.64 | 1.30
Trajectron++ | 0.16 | 0.28 | 0.43 | 0.83
AgentFormer | 0.15 | 0.23 | 0.30 | 0.52
Figure 5: Examples from the TBD Set 1. a) a dynamic group. b) a static
conversational group. c) a tour group with 14 pedestrians. d) a pedestrian
affecting other pedestrians by asking them to come to the table. e)
pedestrians stop and look at their phones. f) two pedestrians change their
navigation goals and turn toward the table. g) a group of pedestrians change
their navigation goals multiple times. h) a crowded scene where pedestrians
are heading in different directions.

We additionally leveraged trajectory prediction models to evaluate our
dataset. Trajectory prediction models’ performance has advanced significantly.
We believe these well-trained models can be utilized in the other ways, such
as characterizing the variety of pedestrian behavior in datasets. Almost all
trajectory prediction models have been tuned and trained on ETH/UCY datasets.
Some have additionally made predictions on SDD [36] or autonomous driving
datasets. Because we were primarily concerned with metric labels and
pedestrian environments, we did not evaluate models trained on SDD or
autonomous vehicle datasets. We also chose models that largely leverage
pedestrian positional data and can work independently without image patch
inputs [39] or semantic segmentation [26].

Our dataset contains simple sessions and challenging sessions. To test if our
dataset contains pedestrian behavior outside of ETH/UCY dataset domains, we
analyzed the sessions from our dataset with great variety in pedestrian
behavior for this evaluation. We selected Social-GAN [17] as the baseline
model and Trajectron++ [40] and AgentFormer [50] as relatively state-of-the-
art models. Because the models trained on each of the other four sub-datasets
did not perform significantly differently in our dataset, we only report the
average Average Displacement Error (ADE) and the average Final Displacement
Error (FDE) across the five models.

We observed that when all pedestrians are concerned, the prediction models all
perform better in our dataset (Table IV). We believe it can be attributed to
the larger presence of static pedestrians in our datasets compared to ETH/UCY
because it is unlikely to yield large errors when predicting future
trajectories of static pedestrians. We additionally defined dynamic
pedestrians as pedestrians who move at least $1m$ during the prediction
window. We included static pedestrians during model inference but only dynamic
pedestrians were considered for evaluation. With this, we discovered that all
the prediction models’ performances degrade. This indicates that the models
have encountered more unseen scenarios in our dataset and that the moving
pedestrians in our dataset exhibit more diverse navigation behavior and wider
behavior distribution compared to the ones in ETH/UCY.

###  IV-E Qualitative Pedestrian Behavior

Due to the nature of the environment where we collect the data, we observe a
mixture of corridor and open-space pedestrian behavior, many of which are
rarely seen in other datasets. As shown in Figure 5, we observe both static
conversation groups and dynamic walking groups. We also observe that some
pedestrians change goals mid-navigation. During certain sessions, some
pedestrians set up activity areas with tables and chairs to engage with
passing pedestrians. This creates more interesting interaction scenarios.

##  V Conclusion

This paper presents a data collection system that is portable and enables
large-scale data collection. This paper also presents a human label
verification tool that streamlines the labeling process. Our semi-autonomous
pipeline easily produces human-verified labels in order to meet the demands of
the large-scale data collected by our hardware. Our systems offer better
utility for pedestrian behavior research because our systems consist of human-
verified labels grounded in the metric space, a combination of both top-down
views and ego-centric views, and a human-pushed cart or robot that
approximates naturalistic human motion with a socially aware robot. Lastly, we
present the TBD Pedestrian Dataset we have collected using our system, which
not only surpasses the quantity of similar datasets, but also offers unique
pedestrian interaction behavior that adds to the qualitative diversity of
pedestrian interaction data.

As mentioned earlier, our approach enables additional data collection in a
wide range of locations and constraints. Additional data collection and public
updates to this initial dataset are planned. We have also discovered
additional challenges with our labeling pipeline on static pedestrians,
because static pedestrians have long trajectory duration and constantly adjust
their body poses, the resulting trajectories can be noisy and escape the
labeler’s attention when using our tool. For future works, we would also
explore expanding the diversity of the labels. Some examples include: adding
activity labels indicating whether the pedestrian is walking, talking or
sitting; adding static obstacle labels for human-object interaction studies;
adding group labels for pedestrian groups; and adding gaze direction and head
orientation labels for the onboard high-definition 360 camera.

## ACKNOWLEDGMENTS

This work was supported by the National Science Foundation (IIS-1734361),
National Institute on Disability, Independent Living, and Rehabilitation
Research (NIDILRR 90DPGE0003), Office of Naval Research (ONR
N00014-18-1-2503), and Shimizu Corporation. We would like to thank Abhijat
Biswas and Henny Admoni for their initiation of this project, and colleagues
in the Tepper School of Business for their assistance on data collection
logistics.

## References

  * [1] A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, L. Fei-Fei, and S. Savarese, “Social lstm: Human trajectory prediction in crowded spaces,” in _Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit._ , June 2016, pp. 961–971.
  * [2] A. Alahi, V. Ramanathan, and L. Fei-Fei, “Socially-aware large-scale crowd forecasting,” in _Proc. IEEE Conf. on Comput. Vis. and Pattern Recognit._ , 2014, pp. 2203–2210.
  * [3] B. Benfold and I. Reid, “Stable multi-target tracking in real-time surveillance video,” in _CVPR 2011_. IEEE, 2011, pp. 3457–3464.
  * [4] A. Biswas, A. Wang, G. Silvera, A. Steinfeld, and H. Admoni, “Socnavbench: A grounded simulation testing framework for evaluating social navigation,” _arXiv preprint arXiv:2103.00047_ , 2021.
  * [5] D. Brščić, T. Kanda, T. Ikeda, and T. Miyashita, “Person tracking in large public spaces using 3-d range sensors,” _IEEE Trans. on Human-Machine Syst._ , vol. 43, no. 6, pp. 522–534, 2013.
  * [6] D. Brščić, H. Kidokoro, Y. Suehiro, and T. Kanda, “Escaping from children’s abuse of social robots,” in _Proc. of the tenth annual acm/ieee international Conf. on human-robot interaction_ , 2015, pp. 59–66.
  * [7] H. Caesar, V. Bankiti, A. H. Lang, S. Vora, V. E. Liong, Q. Xu, A. Krishnan, Y. Pan, G. Baldan, and O. Beijbom, “nuscenes: A multimodal dataset for autonomous driving,” in _CVPR_ , 2020.
  * [8] C. Cao, P. Trautman, and S. Iba, “Dynamic channel: A planning framework for crowd navigation,” in _2019 International Conf. on Robotics and Automation (ICRA)_. IEEE, 2019, pp. 5551–5557.
  * [9] T. Chavdarova, P. Baqué, S. Bouquet, A. Maksai, C. Jose, T. Bagautdinov, L. Lettry, P. Fua, L. Van Gool, and F. Fleuret, “Wildtrack: A multi-camera hd dataset for dense unscripted pedestrian detection,” in _Proc. IEEE Conf. on Comput. Vis. and Pattern Recognit._ , 2018, pp. 5030–5039.
  * [10] C. Chen, Y. Liu, S. Kreiss, and A. Alahi, “Crowd-robot interaction: Crowd-aware robot navigation with attention-based deep reinforcement learning,” in _Proc. IEEE International Conf. on Robotics and Automation (ICRA)_ , 2019, pp. 6015–6022.
  * [11] Y. Chen, C. Liu, B. E. Shi, and M. Liu, “Robot navigation in crowds by graph convolutional networks with attention learned from human gaze,” _IEEE Trans. Robot. Autom._ , vol. 5, no. 2, pp. 2754–2761, 2020.
  * [12] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele, “The cityscapes dataset for semantic urban scene understanding,” in _Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * [13] P. Dendorfer, H. Rezatofighi, A. Milan, J. Shi, D. Cremers, I. Reid, S. Roth, K. Schindler, and L. Leal-Taixé, “Mot20: A benchmark for multi object tracking in crowded scenes,” _arXiv:2003.09003[cs]_ , Mar. 2020, arXiv: 2003.09003.
  * [14] M. Everett, Y. F. Chen, and J. P. How, “Motion planning among dynamic, decision-making agents with deep reinforcement learning,” in _IEEE/RSJ International Conf. on Intell. Robots and Syst. (IROS)_ , Madrid, Spain, Sept. 2018.
  * [15] Y. Gao and C.-M. Huang, “Evaluation of socially-aware robot navigation,” _Frontiers in Robotics and AI_ , p. 420, 2021.
  * [16] C. Gloor, “Pedsim: Pedestrian crowd simulation,” _URL http://pedsim. silmaril. org_ , vol. 5, no. 1, 2016.
  * [17] A. Gupta, J. Johnson, L. Fei-Fei, S. Savarese, and A. Alahi, “Social gan: Socially acceptable trajectories with generative adversarial networks,” in _Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit._ , June 2018, pp. 2255–2264.
  * [18] B. Ivanovic and M. Pavone, “The trajectron: Probabilistic multi-agent trajectory modeling with dynamic spatiotemporal graphs,” in _Proc. IEEE/CVF International Conf. on Comput. Vis._ , 2019, pp. 2375–2384.
  * [19] H. Karnan, A. Nair, X. Xiao, G. Warnell, S. Pirk, A. Toshev, J. Hart, J. Biswas, and P. Stone, “Socially compliant navigation dataset (scand): A large-scale dataset of demonstrations for social navigation,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 4, pp. 11 807–11 814, 2022.
  * [20] K. M. Kitani, B. D. Ziebart, J. A. Bagnell, and M. Hebert, “Activity forecasting,” in _Comput. Vis. – ECCV 2012_ , 2012, pp. 201–214.
  * [21] H. Kretzschmar, M. Spies, C. Sprunk, and W. Burgard, “Socially compliant mobile robot navigation via inverse reinforcement learning,” _The International Journal of Robotics Research_ , vol. 35, no. 11, pp. 1289–1307, 2016.
  * [22] M. Kuribayashi, T. Ishihara, D. Sato, J. Vongkulbhisal, K. Ram, S. Kayukawa, H. Takagi, S. Morishima, and C. Asakawa, “Pathfinder: Designing a map-less navigation system for blind people in unfamiliar buildings,” in _Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems_ , ser. CHI ’23. New York, NY, USA: Association for Computing Machinery, 2023.
  * [23] A. Lerner, Y. Chrysanthou, and D. Lischinski, “Crowds by example,” _Comput. Graph. Forum_ , vol. 26, no. 3, pp. 655–664, 2007.
  * [24] J. Liang, L. Jiang, K. Murphy, T. Yu, and A. Hauptmann, “The garden of forking paths: Towards multi-future trajectory prediction,” in _Proc. IEEE Conf. on Comput. Vis. and Pattern Recognit._ , 2020.
  * [25] B. Majecka, “Statistical models of pedestrian behaviour in the forum,” _Master’s thesis, School of Informatics, University of Edinburgh_ , 2009.
  * [26] K. Mangalam, Y. An, H. Girase, and J. Malik, “From goals, waypoints & paths to long term human trajectory forecasting,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 15 233–15 242.
  * [27] R. Martin-Martin, M. Patel, H. Rezatofighi, A. Shenoi, J. Gwak, E. Frankel, A. Sadeghian, and S. Savarese, “Jrdb: A dataset and benchmark of egocentric robot visual perception of humans in built environments,” _IEEE Trans. Pattern Anal. Mach. Intell._ , 2021.
  * [28] C. Mavrogiannis, F. Baldini, A. Wang, D. Zhao, P. Trautman, A. Steinfeld, and J. Oh, “Core Challenges of Social Robot Navigation: A Survey,” _arXiv e-prints_ , p. arXiv:2103.05668, Mar. 2021.
  * [29] C. Mavrogiannis, F. Baldini, A. Wang, D. Zhao, P. Trautman, A. Steinfeld, and J. Oh, “Core challenges of social robot navigation: A survey,” _arXiv preprint arXiv:2103.05668_ , 2021.
  * [30] A. Mohamed, K. Qian, M. Elhoseiny, and C. Claudel, “Social-stgcnn: A social spatio-temporal graph convolutional neural network for human trajectory prediction,” in _Proc. IEEE/CVF Conf. on Comput. Vis. and Pattern Recognit. (CVPR)_ , June 2020.
  * [31] H. Nishimura, B. Ivanovic, A. Gaidon, M. Pavone, and M. Schwager, “Risk-sensitive sequential action control with multi-modal human trajectory forecasting for safe crowd-robot interaction,” in _2020 IEEE/RSJ International Conf. on Intell. Robots and Syst. (IROS)_. IEEE, 2020, pp. 11 205–11 212.
  * [32] S. Oh, A. Hoogs, A. Perera, N. Cuntoor, C.-C. Chen, J. T. Lee, S. Mukherjee, J. Aggarwal, H. Lee, L. Davis, _et al._ , “A large-scale benchmark dataset for event recognit. in surveillance video,” in _CVPR 2011_. IEEE, 2011, pp. 3153–3160.
  * [33] B. Okal and K. O. Arras, “Learning socially normative robot navigation behaviors with bayesian inverse reinforcement learning,” in _2016 IEEE International Conf. on Robotics and Automation (ICRA)_. IEEE, 2016, pp. 2889–2895.
  * [34] D. Paez-Granados, Y. He, D. Gonon, D. Jia, B. Leibe, K. Suzuki, and A. Billard, “Pedestrian-robot interactions on autonomous crowd navigation: Reactive control methods and evaluation metrics,” in _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2022, pp. 149–156.
  * [35] S. Pellegrini, A. Ess, K. Schindler, and L. van Gool, “You’ll never walk alone: Modeling social behavior for multi-target tracking,” in _Proc. IEEE Int. Conf. Comput. Vis._ , Sept 2009, pp. 261–268.
  * [36] A. Robicquet, A. Sadeghian, A. Alahi, and S. Savarese, “Learning social etiquette: Human trajectory understanding in crowded scenes,” in _Comput. Vis. – ECCV 2016_ , B. Leibe, J. Matas, N. Sebe, and M. Welling, Eds., 2016, pp. 549–565.
  * [37] A. Rudenko, T. P. Kucner, C. S. Swaminathan, R. T. Chadalavada, K. O. Arras, and A. J. Lilienthal, “Thör: Human-robot navigation data collection and accurate motion trajectories dataset,” _IEEE Trans. Robot. Autom._ , vol. 5, no. 2, pp. 676–682, 2020.
  * [38] A. Rudenko, L. Palmieri, M. Herman, K. M. Kitani, D. M. Gavrila, and K. O. Arras, “Human motion trajectory prediction: A survey,” _arXiv preprint arXiv:1905.06113_ , 2019.
  * [39] A. Sadeghian, V. Kosaraju, A. Sadeghian, N. Hirose, H. Rezatofighi, and S. Savarese, “Sophie: An attentive gan for predicting paths compliant to social and physical constraints,” in _Proc. IEEE/CVF Conf. on Comput. Vis. and Pattern Recognit. (CVPR)_ , June 2019.
  * [40] T. Salzmann, B. Ivanovic, P. Chakravarty, and M. Pavone, “Trajectron++: Dynamically-feasible trajectory forecasting with heterogeneous data,” in _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XVIII 16_. Springer, 2020, pp. 683–700.
  * [41] M. Sun, F. Baldini, P. Trautman, and T. Murphey, “Move beyond trajectories: Distribution space coupling for crowd navigation,” _arXiv preprint arXiv:2106.13667_ , 2021.
  * [42] L. Tai, J. Zhang, M. Liu, and W. Burgard, “Socially compliant navigation through raw depth inputs with generative adversarial imitation learning,” in _2018 IEEE International Conf. on Robotics and Automation (ICRA)_ , 2018, pp. 1111–1117.
  * [43] P. Trautman and A. Krause, “Unfreezing the robot: Navigation in dense, interacting crowds,” in _Proc. IEEE/RSJ Int. Conf. Intell. Robot. Syst._ , Oct 2010, pp. 797–803.
  * [44] P. Trautman, J. Ma, R. M. Murray, and A. Krause, “Robot navigation in dense human crowds: Statistical models and experimental studies of human-robot cooperation,” _International Journal of Robotics Research_ , vol. 34, no. 3, pp. 335–356, 2015.
  * [45] N. Tsoi, M. Hussein, J. Espinoza, X. Ruiz, and M. Vázquez, “Sean: Social environment for autonomous navigation,” in _Proc. 8th International Conf. on Human-Agent Interaction_ , 2020, pp. 281–283.
  * [46] A. Wang and A. Steinfeld, “Group split and merge prediction with 3D convolutional networks,” _IEEE Trans. Robot. Autom._ , vol. 5, no. 2, pp. 1923–1930, 2020.
  * [47] A. Wang, C. Mavrogiannis, and A. Steinfeld, “Group-based motion prediction for navigation in crowded environments,” in _Conf. on Robot Learning_. PMLR, 2022, pp. 871–882.
  * [48] B. Wilson, W. Qi, T. Agarwal, J. Lambert, J. Singh, S. Khandelwal, B. Pan, R. Kumar, A. Hartnett, J. Kaesemodel Pontes, D. Ramanan, P. Carr, and J. Hays, “Argoverse 2: Next generation datasets for self-driving perception and forecasting,” in _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks_ , J. Vanschoren and S. Yeung, Eds., vol. 1. Curran, 2021.
  * [49] Z. Yan, T. Duckett, and N. Bellotto, “Online learning for human classification in 3d lidar-based tracking,” in _2017 IEEE/RSJ International Conf. on Intell. Robots and Syst. (IROS)_. IEEE, 2017, pp. 864–871.
  * [50] Y. Yuan, X. Weng, Y. Ou, and K. M. Kitani, “Agentformer: Agent-aware transformers for socio-temporal multi-agent forecasting,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 9813–9823.
  * [51] Y. Zhang, P. Sun, Y. Jiang, D. Yu, Z. Yuan, P. Luo, W. Liu, and X. Wang, “Bytetrack: Multi-object tracking by associating every detection box,” _arXiv preprint arXiv:2110.06864_ , 2021.
  * [52] B. Zhou, X. Wang, and X. Tang, “Understanding collective crowd behaviors: Learning a mixture model of dynamic pedestrian-agents,” in _2012 IEEE Conf. on Comput. Vis. and Pattern Recognit._ IEEE, 2012, pp. 2871–2878.


# A General Dependency Structure for Random Graphs and Its Effect on Monotone
Properties

Zohre Ranjbar-Mojaveri and András Faragó
Department of Computer Science
The University of Texas at Dallas
Richardson, Texas

###### Abstract

We consider random graphs in which the edges are allowed to be dependent. In
our model the edge dependence is quite general, we call it $p$-robust random
graph. It means that every edge is present with probability at least $p$,
regardless of the presence/absence of other edges. This is more general than
independent edges with probability $p$, as we illustrate with examples. Our
main result is that for any monotone graph property, the $p$-robust random
graph has at least as high probability to have the property as an Erdős-Rényi
random graph with edge probability $p$. This is very useful, as it allows the
adaptation of many results from classical Erdős-Rényi random graphs to a non-
independent setting, as lower bounds.

##  1 Introduction

Random networks occur in many practical scenarios. Some examples are wireless
ad-hoc networks, various social networks, the web graph describing the World
Wide Web, and a multitude of others. Random graph models are often used to
describe and analyze such networks.

The oldest and most researched random graph model is the Erdős-Rényi random
graph $G_{n,p}$. This denotes a random graph on $n$ nodes, such that each edge
is added with probability $p$, and it is done independently for each edge. A
large number of deep results are available about such random graphs, see
expositions in the books [2, 4, 5]. Below we list some examples. They are
asymptotic results, and for simplicity/clarity we omit potential restrictions
for the range of $p$, as well as ignore rounding issues (i.e., an asymptotic
formula may provide a non-integer value for a parameter which is defined as
integer for finite graphs).

  * •

The size of a maximum clique in $G_{n,p}$ is asymptotically $2\log_{1/p}n$.

  * •

If $G_{n,p}$ has average degree $d$, then its maximum independent set has
asymptotic size $\frac{2n\ln d}{d}$.

  * •

The chromatic number of $G_{n,p}$ is asymptotically $\frac{n}{\log_{b}n}$,
where $b=\frac{1}{1-p}$.

  * •

The size of a minimum dominating set in $G_{n,p}$ is asymptotically
$\log_{b}n$, where $b=\frac{1}{1-p}$.

  * •

The length of the longest cycle in $G_{n,p}$, when the graph has a constant
average degree $d$, is asymptotically $n(1-d{\rm e}^{-d})$.

  * •

The diameter of $G_{n,p}$ is asymptotically $\frac{\log n}{\log(np)}$, when
$np\rightarrow\infty$. (If the graph is not connected, then the diameter is
defined as the largest diameter of its connected components.)

  * •

If $G_{n,p}$ has average degree $d$, then the number of nodes of degree $k$ in
the graph is asymptotically $\frac{d^{k}{\rm e}^{-d}}{k!}n$.

These results (and many others) make it possible that for random graphs that
one can find good and directly computable estimates of graph parameters that
are hard to compute for deterministic graphs. Moreover, the parameters often
show very strong concentration. For example, as listed above, the chromatic
number of $G_{n,p}$ is asymptotically $\frac{n}{\log_{b}n}$, where
$b=\frac{1}{1-p}$. However, we can say more: the chromatic number of a random
graph is so strongly concentrated that with probability approaching one, as
$n\rightarrow\infty$, it falls on one of two consecutive integers (see Alon
and Krivelevich [1]).

##  2 Random Graphs With Dependent Edges

The requirement that the edges are independent is often a severe restriction
in modeling real-life networks. Therefore, numerous attempts have been made to
develop models with various dependencies among the edges, see, e.g., a survey
in [3]. Here we consider a general form of edge dependency. We call a random
graph with this type of dependency a $p$-robust random graph.

###### Definition 1

($p$-robust random graph) A random graph on $n$ vertices is called $p$-robust,
if every edge is present with probability at least $p$, regardless of the
status (present or not) of other edges. Such a random graph is denoted by
$\widetilde{G}_{n,p}$.

Note that $p$-robustness does not imply independence. It allows that the
existence probability of an edge may depend on other edges, possibly in a
complicated way, it only requires that the probability never drops below $p$.
Let us show some examples of $p$-robust random graphs.

Example 1

First note that the classical Erdős-Rényi random graph $G_{n,p}$ is a special
case of $\widetilde{G}_{n,p}$, since our model also allows adding all edges
independently with probability $p$.

Example 2

However, we can also allow (possibly messy) dependencies. For example, let
$P(e)$ denote the probability that a given edge $e$ is present in the graph,
and let us condition on $k$, the number of other edges in the whole graph. Let
$P_{e}(k)$ denote the probability that there are $k$ edges in the graph, other
than $e$. For any fixed $k$, set $P(e|k)=1-(k+1)/n^{2}$; let this be the
probability that edge $e$ exists, given that there are $k$ other edges in the
graph. Using that the total number of edges cannot be more than $n(n-1)/2$, we
have that $k\leq n(n-1)/2-1$ always holds. Therefore, $P(e|k)\geq
1-\frac{n(n-1)}{2n^{2}}=1-\frac{n-1}{2n}\geq\frac{1}{2}$, for any $k$,
implying $P(e)=\sum_{k=0}^{n(n-1)/2-1}P(e|k)P_{e}(k)\geq 1/2$. Thus, with
$p=1/2$, this random graph is $p$-robust. At the same time, the edges are not
independent, since the probability that $e$ is present depends on how many
other edges are present.

Example 3

For a given edge $e$, let $r(e)$ denote the number of edges that are adjacent
with $e$ (not including $e$ itself). If $e$ does not exist, then let $r(e)=0$.
Let the conditional probability that edge $e$ exists, given that it has $k$
adjacent edges, be $P(e|r(e)=k)=\frac{1}{2}-\frac{1}{k+5}$. Note that the
possible range of $k$ is $0\leq k\leq 2(n-2)$. Then we have
$P(e|r(e)=k)\geq\frac{1}{2}-\frac{1}{5}=\frac{3}{10}$. This implies
$P(e)=\sum_{k=0}^{2(n-2)}P(e|r(e)=k)P(r(e)=k)\geq\frac{3}{10}\sum_{k=0}^{2(n-2)}P(r(e)=k)=\frac{3}{10}$.
Thus, with $p=\frac{3}{10}$, this random graph is $p$-robust. At the same
time, the edges are not independent, since the probability that $e$ is present
is influenced by the number of adjacent edges.

Example 4

Consider the model described above in 3, but with the additional condition
that each potential edge $e$ has at least 3 adjacent edges, whether or not $e$
is in the graph. What can we say about this conditional random graph? The same
derivation as in 3, but with $k\geq 3$, gives us that the new random graph
will remain $p$-robust, but now with $p=\frac{3}{8}$.

If we have a random graph like the ones in Examples 2,3,4 above (and many
possible others with dependent edges), then how can we estimate some parameter
of the random graph, like the size of the maximum clique? We show that at
least for so called monotone properties we can use the existing results about
Erdős-Rényi random graphs as lower bounds.

Let $Q$ be a set of graphs. We use it to represent a graph property: a graph
$G$ has property $Q$ if and only if $G\in Q$. Therefore, we identify the
property with $Q$. We are going to consider monotone graph properties, as
defined below.

###### Definition 2

(Monotone graph property) A graph property $Q$ is called monotone, if it is
closed with respect to adding new edges. That is, if $G\in Q$ and $G\subseteq
G^{\prime}$, then $G^{\prime}\in Q$.

Note that many important graph properties are monotone. Examples: having a
clique of size at least $k$, having a Hamiltonian circuit, having $k$ disjoint
spanning trees, having chromatic number at least $k$, having diameter at most
$k$, having a dominating set of size at most $k$, having a matching of size at
least $k$, and numerous others. In fact, almost all interesting graph
properties have a monotone version. Our result is that for any monotone graph
property, and for any $n,p$, it always holds that $\widetilde{G}_{n,p}$ is
more likely to have the property than $G_{n,p}$ (or at least as likely). This
is very useful, as it allows the application of the rich treasury of results
on Erdős-Rényi random graphs to the non-independent setting, as lower bounds
on the probability of having a monotone property. Below we state and prove our
general result.

###### Theorem 1

Let $Q$ be any monotone graph property. Then the following holds:

$\Pr(G_{n,p}\in Q)\;\leq\;\Pr(\widetilde{G}_{n,p}\in Q).$

Proof. We are going to generate $\widetilde{G}_{n,p}$ as the union of two
random graphs, $G_{n,p}$ and $G_{2}$, both on the same vertex set $V$.
$G_{n,p}$ is the usual Erdős-Rényi random graph, $G_{2}$ will be defined
later. The union $G_{n,p}\cup G_{2}$ is meant with the understanding that if
the same edge occurs in both graphs, then we merge them into a single edge. We
plan to chose the edge probabilities in $G_{2}$, such that $G_{n,p}\cup
G_{2}\sim\widetilde{G}_{n,p}$, where the “$\sim$” relation between random
graphs means that they have the same distribution, i.e., they are
statistically indistinguishable. If this can be accomplished, then the claim
will directly follow, since then a random graph distributed as
$\widetilde{G}_{n,p}$ can be obtained by adding edges to $G_{n,p}$, which
cannot destroy a monotone property, once $G_{n,p}$ has it. This will imply the
claim.

We introduce some notations. Let $e_{1},\ldots,e_{m}$ denote the (potential)
edges. For every $i$, let $h_{i}$ be the indicator of the event that the edge
$e_{i}$ is included in $\widetilde{G}_{n,p}$. Further, let us use the
abbreviation $h_{i}^{m}=(h_{i},\ldots,h_{m})$. For any
$a=(a_{1},\ldots,a_{m})\in\\{0,1\\}^{m}$, the event $\\{h_{1}^{m}=a\\}$ means
that $\widetilde{G}_{n,p}$ takes a realization in which edge $e_{i}$ is
included if and only $a_{i}=1$. Similarly, $\\{h_{i}^{m}=a_{i}^{m}\\}$ means
$\\{h_{i}=a_{i},\ldots,h_{m}=a_{m}\\}$. We also use the abbreviation
$a_{i}^{m}=(a_{i},\ldots,a_{m})$. Now let us generate the random graphs
$G_{n,p}$ and $G_{2}$, as follows.

Step 1.

Let $i=m$.

Step 2.

If $i=m$, then let $q_{m}=\Pr(h_{m}=1)$. If $i<m$, then set
$q_{i}=\Pr(h_{i}=1\;|\;h_{i+1}^{m}=a_{i+1}^{m})$, where $a_{i+1}^{m}$
indicates the already generated edges of $G_{n,p}\cup G_{2}$.

Step 3.

Compute

$p^{\prime}_{i}=\frac{p(1-q_{i})}{1-p}.$ (1)

Step 4.

Put $e_{i}$ into $G_{n,p}$ with probability $p$, and put $e_{i}$ into $G_{2}$
with probability $q_{i}-p^{\prime}_{i}$.

Step 5.

If $i>1$, then decrease $i$ by one, and go to Step 2; else halt.

First note that the value $q_{i}-p^{\prime}_{i}$ in Step 4 can indeed be used
as a probability. Clearly, $q_{i}-p^{\prime}_{i}\leq 1$ holds, as $q_{i}$ is a
probability and $p^{\prime}_{i}\geq 0$. To show $q_{i}-p^{\prime}_{i}\geq 0$,
observe that $p^{\prime}_{i}=\frac{p(1-q_{i})}{1-p}\leq q_{i},$ since the
inequality can be rearranged into $p(1-q_{i})\leq q_{i}(1-p)$, which
simplifies to $p\leq q_{i}$. The latter is indeed true, due to
$q_{i}=\Pr(h_{i}=1\;|\;h_{i+1}^{m}=a_{i+1}^{m})\geq p$, which follows from the
$p$-robust property.

Next we show that the algorithm generates the random graphs $G_{n,p}$ and
$G_{2}$ in a way that they satisfy $G_{n,p}\cup G_{2}\sim\widetilde{G}_{n,p}$.
We prove it by induction, starting from $i=m$ and progressing downward to
$i=1$. For any $i$, let $G^{i}_{n,p}$, $G^{i}_{2}$ denote the already
generated parts of $G_{n,p},G_{2}$, respectively, after executing Step 4
$m-i+1$ times, so they can only contain edges with index $\geq i$. Further,
let $\widetilde{G}^{i}_{n,p}$ be the subgraph of $\widetilde{G}_{n,p}$ in
which we only keep the edges with index $\geq i$, that is,
$\widetilde{G}^{i}_{n,p}=\widetilde{G}_{n,p}-\\{e_{i-1},\ldots,e_{1}\\}$. The
inductive proof will show that $G^{i}_{n,p}\cup
G^{i}_{2}\sim\widetilde{G}^{i}_{n,p}$ holds for every $i$. At the end of the
induction, having reached $i=1$, we are going to get $G^{1}_{n,p}\cup
G^{1}_{2}\sim\widetilde{G}^{1}_{n,p}$, which is the same as $G_{n,p}\cup
G_{2}\sim\widetilde{G}_{n,p}$.

Let us consider first the base case $i=m$. Then we have $\Pr(e_{m}\in
G_{n,p})=\Pr(e_{m}\in G^{m}_{n,p})=p$ by Step 4. Then in Step 4, edge $e_{m}$
is put into $G_{2}$ with probability $q_{m}-p^{\prime}_{m}$, yielding
$\Pr(e_{m}\in G^{m}_{2})=q_{m}-p^{\prime}_{m}$. Now observe that the formula
(1) is chosen such that $p^{\prime}_{i}$ is precisely the solution of the
equation

$p+q_{i}-p^{\prime}_{i}-(q_{i}-p^{\prime}_{i})p=q_{i}$ (2)

for $p^{\prime}_{i}$. For $i=m$ the equation becomes

$p+q_{m}-p^{\prime}_{m}-(q_{m}-p^{\prime}_{m})p=q_{m},$ (3)

and $p^{\prime}_{m}=\frac{p(1-q_{m})}{1-p}$ is the solution of this equation.
Since by Step 4 we have $\Pr(e_{m}\in G^{m}_{n,p})=p$ and $\Pr(e_{m}\in
G^{m}_{2})=q_{m}-p^{\prime}_{m}$, therefore, we get that the left-hand side of
(3) is precisely the probability of the event $\\{e_{m}\in G^{m}_{n,p}\cup
G^{m}_{2}\\}$. By (3), this probability is equal to $q_{m}$, which is set to
$q_{m}=\Pr(h_{m}=1)=\Pr(e_{m}\in\widetilde{G}^{m}_{n,p})$ in Step 2. This
means that $G^{m}_{n,p}\cup G^{m}_{2}\sim\widetilde{G}^{m}_{n,p}$, as desired.

For the induction step, assume that the claim is true for $i+1$, i.e.,
$G^{i+1}_{n,p}\cup G^{i+1}_{2}\sim\widetilde{G}^{i+1}_{n,p}$ holds. In Step 4,
edge $e_{i}$ is added to $G^{i+1}_{n,p}$ with probability $p$. It is also
added to $G^{i+1}_{2}$ with probability $q_{i}-p^{\prime}_{i}$. Therefore,
just like in the base case, we get that
$p+q_{i}-p^{\prime}_{i}-(q_{i}-p^{\prime}_{i})p=\Pr(e_{i}\in G^{i}_{n,p}\cup
G^{i}_{2}).$ We already know that $p^{\prime}_{i}$ satisfies the equation (2),
so $e_{i}$ is added to $\widetilde{G}^{i+1}_{n,p}$ with probability
$q_{i}=\Pr(h_{i}=1\;|\;h_{i+1}^{m}=a_{i+1}^{m})$, given the already generated
part, represented by $a_{i+1}^{m}$. By the inductive assumption, $h_{i+1}^{m}$
is distributed as $\widetilde{G}^{i+1}_{n,p}$, which is the truncated version
of $\widetilde{G}_{n,p}$, keeping only the $\geq i+1$ indexed edges. Hence,
for $h_{i+1}^{m}$, we can write by the chain rule of conditional
probabilities:

$\Pr(h_{i+1}^{m}=a_{i+1}^{m})=\Pr(h_{m}=a_{m})\prod_{j=i+1}^{m-1}\Pr(h_{j}=a_{j}\;|\;h_{j+1}^{m}=a_{j+1}^{m}).$

After processing $e_{i}$ (i.e., adding it with probability $q_{i}$), we get

$\displaystyle\Pr(h_{i}^{m}=a_{i}^{m})$ $\displaystyle=$
$\displaystyle\Pr(h_{i}=a_{i}\;|\;h_{i+1}^{m}=a_{i+1}^{m})\Pr(h_{i+1}^{m}=a_{i+1}^{m})$
$\displaystyle=$
$\displaystyle\Pr(h_{i}=a_{i}\;|\;h_{i+1}^{m}=a_{i+1}^{m})\underbrace{\Pr(h_{m}=a_{m})\prod_{j=i+1}^{m-1}\Pr(h_{j}=a_{j}\;|\;h_{j+1}^{m}=a_{j+1}^{m})}_{\Pr(h_{i+1}^{m}=a_{i+1}^{m})}$
$\displaystyle=$
$\displaystyle\Pr(h_{m}=a_{m})\prod_{j=i}^{m-1}\Pr(h_{j}=a_{j}\;|\;h_{j+1}^{m}=a_{j+1}^{m}),$

which, by the chain rule, is indeed the distribution of
$\widetilde{G}^{i}_{n,p}$, completing the induction.

Thus, at the end, a realization $a=a_{1}^{m}\in\\{0,1\\}^{m}$ of
$\widetilde{G}_{n,p}$ is generated with probability

$\Pr(h_{1}^{m}=a)=\Pr(h_{m}=a_{m})\prod_{j=1}^{m-1}\Pr(h_{j}=a_{j}\;|\;h_{j+1}^{m}=a_{j+1}^{m}),$

indeed creating $\widetilde{G}_{n,p}$ with its correct probability. Therefore,
we get $G_{n,p}\cup G_{2}\sim\widetilde{G}_{n,p}$, so $\widetilde{G}_{n,p}$
arises by adding edges to $G_{n,p}$, which cannot destroy a monotone property.
This implies the statement of the Theorem, completing the proof.

$\spadesuit$

##  3 An Example

As a sample application of the result, consider the random graph described in
Example 3. For handy access, let us repeat the example here:

> Example 3. For a given edge $e$, let $r(e)$ denote the number of edges that
> are adjacent with $e$ (not including $e$ itself). If $e$ does not exist,
> then let $r(e)=0$. Let the conditional probability that edge $e$ exists,
> given that it has $k$ adjacent edges, be
>
> $P(e|r(e)=k)=\frac{1}{2}-\frac{1}{k+5}.$
>
> Note that the possible range of $k$ is $0\leq k\leq 2(n-2)$. Then we have
>
> $P(e|r(e)=k)\geq\frac{1}{2}-\frac{1}{5}=\frac{3}{10}.$
>
> This implies
>
>
> $P(e)=\sum_{k=0}^{2(n-2)}P(e|r(e)=k)P(r(e)=k)\;\geq\;\frac{3}{10}\sum_{k=0}^{2(n-2)}P(r(e)=k)=\frac{3}{10},$
>
> Thus, with $p=\frac{3}{10}$, this random graph is $p$-robust. At the same
> time, the edges are not independent, since the probability that $e$ is
> present is influenced by the number of adjacent edges.

Now we can claim that this random graph asymptotically has a maximum clique of
size at least $2\log_{10/3}n$, chromatic number at least $\frac{n}{\log_{b}n}$
with $b=\frac{1}{1-p}=\frac{10}{7}$, minimum dominating set at most
$\log_{b}n$, also with $b=10/7$, and diameter at most $\frac{\log
n}{\log(3n/10)}$ . All these follow from the known results about the Erdős-
Rényi random graph $G_{n,p}$ (listed in the Introduction), complemented with
our Theorem 1. Note that such bounds would be very hard to prove directly from
the definition of the edge dependent random graph model.

## References

  * [1] N. Alon and M. Krivelevich, “The Concentration of the Chromatic Number of Random Graphs,” Combinatorica, vol. 17, 1977, pp. 303–313.
  * [2] B. Bollobás, Random Graphs, Cambridge University Press, 2001.
  * [3] A. Faragó, “Network Topology Models for Multihop Wireless Networks,” ISRN Communications and Networking, Vol. 2012, Article ID 362603, doi:10.5402/2012/362603
  * [4] A. Frieze and M. Karoński, Introduction to Random Graphs, Cambridge Univ. Press, 2016.
  * [5] S. Janson, T. Luczak, and A. Rucinski, Random Graphs, Wiley-Interscience, 2000.


# Enhanced dendrite nucleation and Li-clustering at vacancies on graphene

Jonathon Cottom  [  Qiong Cai  Department of Chemical and Process Engineering,
University of Surrey, Guildford, GU2 7XH United Kingdom  Emilia Olsson
<EMAIL_ADDRESS>[

###### Abstract

An ever present challenge for Li-ion batteries is the formation of metallic
dendrites on cycling that dramatically reduces cycle life and leads to the
untimely failure of the cell. In this work we investigate the modes of Li-
cluster formation on pristine and defective graphene. Firstly, we demonstrate
that on a defect free surface the cluster formation is impeded by the
thermodynamic instability of Li_2 and Li_3 clusters. In contrast, the presence
of a vacancy dramatically favours clustering. This provides insights into the
two modes of Li-growth observed: for the pristine basal plane if the Li-Li
repulsion of the small clusters can be overcome then plating type behaviour
would be predicted (rate / voltage dependent and at any point on the surface);
whilst dendritic growth would be predicted to nucleate from vacancy sites,
either pre-existing in the material or formed as a result of processing.

###### keywords:

DFT,LIB,dendrite,graphene

ARCNL] Advanced Research Center for Nanolithography, Science Park 106,
Amsterdam, 1098 XG The Netherlands [UvA] Institute of Theoretical Physics,
Institute of Physics, University of Amsterdam, Science Park 904, Amsterdam,
1098 XH The Netherlands ARCNL] Advanced Research Center for Nanolithography,
Science Park 106, Amsterdam, 1098 XG The Netherlands [UvA] Institute of
Theoretical Physics, Institute of Physics, University of Amsterdam, Science
Park 904, Amsterdam, 1098 XH The Netherlands

##  1 Introduction

Lithium-ion batteries (LIBs) have emerged as one of the most important
electrochemical energy storage technologies in the quest for a sustainable
fossil fuel-free energy future.1 LIBs typically employ a liquid electrolyte,
layered cathode and graphite anode. Despite their wide use, challenges remain
in terms of lifetime, and stability.2, 3, 4 Fast charging LIBs are
increasingly pursued which further accelerates the current LIB lifetime and
stability challenges. These challenges relate to the formation of lithium
dendrites at the anode surface, and irreversible lithium plating.5, 6, 7, 8
Dendrites can form and grow due to uneven deposition and accumulation of
lithium at the anode electrolyte interface, leading to short-circuiting.9, 10,
11, 12 For lithium plating, the lithium deposits on the anode surface at a
faster rate than it can intercalate.9 This leads to reduced battery life and
limited charging. As for dendrite formation, plating can also be
inhomogeneous, either due to kinetics or thermodynamics, but the exact
mechanism is poorly understood.13 The operating voltage of graphite LIB anodes
is very close to the Li metal voltage, leading to Li metal plating occurring
at high charging rates or low temperatures (below 273 K).2 At extreme
temperatures (above 373 K), carbon anodes are increasingly susceptible to
dendrite formation.9

All solid state batteries (ASSBs) are widely seen as the next frontier in
energy storage due to their high energy density as a consequence of the
possibility of using Li metal anodes with solid electrolytes.14, 15 With the
introduction of a solid electrolyte, the expectation was that Li dendrite
formation would be eradicated. However, it was found that Li dendrites are
also a challenge in ASSBs.14 To this end, carbon-based materials are also
finding a use in ASSBs as current collectors, protective layers, and support
materials for Li metal anodes, making the atomic scale understanding of
lithium nucleation on carbon surfaces imperative.16, 17, 18, 10, 15, 19, 20,
21

A plethora of different carbon-materials have been employed for battery
applications, including graphite, graphene, hard carbons, carbon nanotubes and
soft carbons. 22, 23, 9, 24 Whilst these materials are structurally different,
they all contain sp2 hybridized surfaces, forming the commonly present planar
basal planes with connected six-membered carbon rings.15, 20, 25, 9, 26, 27 In
real applications, the basal plane surface can also be defective, either as a
result of synthesis conditions or battery operation. Atomic scale
understanding of the effect of carbon vacancy (VC) on Li deposition and
nucleation is crucial for the design of longer lifetime, safer battery
architectures. In this letter, we conduct a density functional theory (DFT)
study of Li cluster growth on graphene. In our previous work we studied the
interaction of a single lithium ion with pristine and defective graphene in
the context of LIBs.28, 29, 30, 31, 32 These studies showed that defects have
a direct impact on the single lithium binding energy and the initial
lithiation during charging. Through calculations of adsorption and migration
energies, we postulated that VC defects would lead to irreversible capacity
loss for LIBs, a statement we here extend. Separate studies have investigated
the interaction of multiple Li atoms with different graphene models to probe
the effect of lithium concentration on adsorption energy as a proxy of
charging profile.33, 34, 35, 36, 37 Small Li clusters were found to be able to
adsorb more readily on graphene than Li metal (001) surface 36, and a separate
study of Li clusters on pristine graphene showed that the cluster binding
energy was dependent on Li concentration34. Here, we extend our considerations
to the step wise growth of lithium clusters, exploring the energetic stability
of these clusters on the pristine versus V_C as the initial dendritic growth
and plating step.

##  2 Methods

The calculations were performed spin polarised using the CP2K38, 39, 40, 41,
42 code with the DZVP-SR-MOLOPT39 family of basis-sets to describe the valence
electrons, and the GTH pseudopotentials43, 44, 45 to describe the core
electrons. The initial defect free relaxations were performed on a 308 atom
graphene cell (see Fig S1 in the supporting information). Both the xy-lattice
vectors and ion positions were fully relaxed using the quasi-Newton BFGS
update scheme (ion positions only for defect calculations), the vacuum slab
was converged above 10 Å, with 25 Å used to account for all the tested cluster
geometries.40, 42, 46, 47, 48, 49, 50 The PBE functional51, with the D3-BJ
dispersion correction scheme52, 53, 54, 55, 56 was employed for all
calculations in line with our previous work.12, 31, 29, 30 The convergence
criteria was 1 $\times$ 10-7 eV, and 0.005 eV / Å for forces, with an energy
cutoff of 750 Ry and a relative cutoff of 60 Ry to achieve an initial
convergence of 0.1 meV / formula unit. To identify the lowest energy cluster
configurations for each size, an exhaustive sampling was performed starting
from the single atom (Li_1). In each case the identified lowest energy
configuration becomes the starting point for Li_(n+1). The process is iterated
for the cluster n = 1 - 12 presented here. For completeness, the results for
the higher energy cluster configurations are included in the supplementary
information Fig S2-3. The interaction energies are calculated using the
standard formalism of Zhang and Northrup57 in terms of formation energy E_f
(eq. 1), binding energy (E_bind) (eq. (2)), and cohesive energy (E_coh) (eq.
(3)).

$E_{f}=\frac{E_{Li_{n}@surface}-E_{surface}-{n\mu_{Li}}}{n}$ (1)

$E_{bind}=\frac{E_{Li_{n}@surface}-E_{surface}-E_{Li_{n}}}{n}$ (2)

$E_{coh}=\frac{E_{Li_{n}}-{n\mu_{Li}}}{n}$ (3)

Here, ${E_{Li_{n@surface}}}$ is the total energy of the $Li_{n}$ cluster on
the surface, $E_{surface}$ is the total energy of the surface, n the number of
Li, and $\mu_{Li}$ the lithium chemical potential. The Li chemical potential
was varied from the vacuum ($\mu_{Li}$ defined as a single Li atom in vacuum)
to metallic reference ($\mu_{Li}$ defined from Li bulk).

##  3 Results and Discussion

To explore how V_C impact the Li nucleation on graphene, two key questions
need to be addressed. Firstly, how the presence of a vacancy impacts E_bind of
successive Li atoms with respect to the isolated Li, in essence how is
surface-Li binding aided or impeded by the presence of a V_C defect? Secondly,
how does the presence of the defect influence the morphology and E_coh of the
forming clusters? Probing whether the cluster formation is significantly aided
or frustrated on forming at a vacancy site. To act as a reference, cluster
binding is first calculated on the defect free basal plane, Li-atoms are added
step-wise to the lowest energy sites identified in ref28, E_bind, E_coh and
E_f are then extracted (Fig.1).

Figure 1: a) lowest energy cluster configurations for the range n = 1 - 12 on
the pristine where purple circles are Li (striped purple circles denotes Li in
next layer), and grey C. Figures made using the Atomic Simulation Environment
(ASE).58 b) the interaction energies decomposed into (E_bind), (E_coh) and
(E_f), and Li-C and Li-Li separation (c).

It is clear from the configurations in Figure 1a, that the preferred hole site
absorption geometry of the isolated Li, results in a significant distortion
for clusters from n $\geq$ 2\. Each Li cannot be accommodated at the high
symmetry hole site, as a result it is distorted from its central position. For
the smallest clusters (n = 2 and 3) the repulsive energetic penalty can be
estimated for the induction of a single neighbouring Li as 0.34 eV. This is
expressed in both E_bind (Figure 1b) and the C-Li separation with the cluster
moving away from the surface (Figure 1c). The repulsive interaction is
partially compensated for by the Li-Li E_coh (Figure 1b), which shows a marked
increase with increasing cluster size. For clusters n $>$ 3 the addition of
the (n+1)th Li to the next layer becomes favoured. The cluster then grows
stepwise via the building up of node sharing trigonal pyramidal units. The
ground state cluster geometries and relative energies are in agreement with
the results from Liu and co-workers.34

For the Li clusters explored, E_bind rapidly decreases and converges to -0.45
eV / atom, at the same rate E_coh of the cluster increases to -0.91 eV. As the
cluster structure forms layers, a further differentiation between those atoms
that interact with the C-surface and those that only interact with Li is seen.
This is expressed in the partial charges for the larger clusters with a clear
negative shift of the Mulliken charge for the non-surface interacting Li atoms
(+0.02 e) when compared to the surface interacting Li in a given cluster
(+0.47 e) and the isolated case (+0.5 e). It is important to note that for the
defect free system the small clusters (n $<$ 3) are energetically unfavoured
with respect to the dispersed Li, additionally clusters in the n =4 - 6 are
iso-energetic with the dispersed Li. Therefore, clustering would only be
predicted to be stable for the larger clusters (n $\geq$ 7).

Figure 2: a) lowest energy cluster configurations for the range n = 1 - 12 at
the V_C where purple circles are Li (striped purple spheres denotes Li in next
layer), and grey C. Figures were made using ASE.58 b) the interaction energies
decomposed into (E_bind), (E_coh) and (E_f). c) The mean cluster Li-C and Li-
Li separations (c).

Figure 2a shows the lowest energy of Li configurations for binding on the V_C.
In agreement with the previously reported isolated Li28, E_bind is -3.3 eV and
the Li interacts with the under-coordinated C-atom, while the other 2 vacancy
C-atoms form a 5-membered ring. This geometry remains stable for n = 1 & 2,
however for clusters n $\geq$ 3 the 5-membered ring opens, partially for n=3
and completely at n = 4 resulting in a Li sitting at the central C3 site
(Figure 2a). The under-coordinated C-atoms show a significant distortion
lifting 1.2 Å out of the plane. This can clearly be seen in the Li-Li
separation (Figure 2c), with a decrease from n=2 to n=4, followed by a sharp
increase once the defect and adjacent sites are occupied. Above n = 4 the next
Li can either be added adjacent to the cluster or on top forming a new Li-
layer. Similar to metal adsorption on the basal plane, the metal top site is
energetically favoured. The cluster then grows in lateral extent by the
addition of the next Li to the adjacent hole site in a manner similar to that
seen on the basal plane. The presence of a vacancy leads to a marked increase
in E_f and E_bind for the smallest clusters (n = 2 - 5). E_coh as a function
of cluster size is of the same order for both the V_C and pristine, being a
function of cluster size and the effective coordination that this supports. As
the cluster increases in size E_bind will converge to that of the pristine
(the influence of the vacancy bound Li becomes negligible in per atom terms).
Whereas E_coh will converge towards Li-metal (-1.78 eV / atom) for clusters of
sufficient size. The presence of the vacancy in essence anchors the cluster in
place, allowing the repulsive interactions seen in the small clusters on the
pristine to be overcome. Hence cluster nucleation would be predicted to be
favourable at the V_C for all of the cluster sizes considered.

It is clear that in both the pristine and the V_C there is a propensity to
form clusters by preferentially adding Li-atoms to the next layer for clusters
greater than n=3 and n=4, respectively. In each case it is most energetically
favourable to grow the cluster via filling the adjacent hole sites, followed
by the addition to the top site. This leads to the stepwise growth of the
cluster, for the range of cluster sizes considered here the growth is limited
to 2- / 3-layers. The main difference between the two binding modes is the
magnitude of the surface binding energy, with binding at the vacancy
dramatically favoured. It should be noted that the reduction in the cluster
binding energy for the pristine is largely driven by strain between
neighbouring Li with the system attempting to minimise repulsive Li-Li
interaction, while maximising Li-surface interaction. Here the average picture
given by E_bind gives a reasonable picture of cluster binding as each site is
approximately equivalent. In the V_C system the situation is complicated as
there is a large discrepancy in E_bind between sites28, in this case the
vacancy site (n = 1), and the filling of the adjacent sites (n = 2 - 4) are in
essence anchored in position interacting strongly with the vacancy site(s). As
the cluster grows the available sites for the next Li begin to resemble the
pristine system and this is seen in the increase in C-Li separation (Figure
2c), which approaches the pristine values as the number of pristine sites
dominate.

Figure 3a shows E_f of the Li clusters on pristine and defective pristine (E_f
in Figure 1b and 2b) as a function of Li chemical potential. For Li-poor
conditions, the chemical potential is taken from the vacuum reference, Li-rich
from the Li metal reference, and solvated Li is Li in 3:1 EC:DMC as described
by Fan et al. (2019).59. Taking the energy of a single Li on the pristine in
the solvated Li assumption as reference, it can be seen from Figure 3b that
only the larger Li clusters are energetically stable on the pristine basal
plane, and formation of the small clusters (n $<$ 4) is thermodynamically
hindered. Upon the introduction of a V_C, all clusters become
thermodynamically favoured.

Figure 3: a) Li cluster formation energy on pristine (filled markers and non-
dotted lines) and defective (empty markers and dotted lines) pristine with the
Li energy taken at the Li-poor, Li-rich, and Li solvated in EC:DMC ([3:1])
chemical potential. b) shows the lithium cluster formation energy with the
solvated Li chemical potential, referenced to a single Li bonded to the
pristine surface from the solvated Li reference.

The pristine and V_C show a number of similarities and some important
differences upon the formation of Li clusters. In both cases stepwise growth
is observed, with adjacent hole sites (Li_2 and Li_3) being filled before
adding a new layer (Li_4). Cluster growth on the pristine is significantly
hampered for the smallest cluster n=2-4, which are 0.25 eV/atom less favoured
than the dispersed Li. This suggests that cluster growth will only be observed
at high Li-concentrations / -rates, and is potentially linked to Li-plating
behaviour reported. In contrast the presence of the V_C dramatically increases
the binding strength for the small clusters, the formation of which is
unfavourable on the pristine surface. In addition, this strong binding anchors
the growing cluster onto the vacancy site. As the cluster size increases the
available site resemble the pristine basal plane, reducing the effect of the
V_C.

##  4 Conclusion

In summary, cluster growth is explored on both the pristine basal plane and
the V_C system. Cluster formation in the pristine system is hampered by the
thermodynamic instability of the small Li-clusters with respect to disperse Li
adsorption. Therefore, clustering would only be observed at high deposition
rates (Li-concentration). This mode of growth would be homogeneous across the
surface and analogous to the Li-plating behaviour observed. In contrast the
presence of the V_C results in a dramatic increase in Li-binding energy,
facilitated by the relaxation of the cluster to strongly bind the n = 4
cluster. The result of this is two-fold firstly, the thermodynamic instability
of the small clusters seen on the pristine surface is overcome. Secondly, the
forming cluster is anchored in place at the vacancy site. This results in
inhomogeneous growth mediated by surface vacancies resulting in dendritic
growth. Further investigations are underway to characterise those additional
defect types that favour, or indeed hamper clustering.

This work made use of the Dutch national e-infrastructure with the support of
the SURF Cooperative using grant no. EINF-2434. The authors thank SURF
(www.surf.nl) for the support in using the Lisa Compute Cluster and National
Supercomputer Snellius. Q.C. would like to acknowledge funding support from
Faraday Institution through the LiSTAR programme (EP/S003053/1, Grant
FIRG014), and funding support from Horizon Europe through the OPERA consortium
(Grant No. 101103834). E.O. is grateful for a WISE Fellowship from the Dutch
Research Council (NWO). This work has been carried out at the Advanced
Research Center for Nanolithography (ARCNL). ARCNL is a public–private
partnership with founding partners UvA, VU, NWO-I, and ASML and associate
partner RUG.

Higher energy Li cluster configurations are included in the supplementary
information.

## References

  * Armand and Tarascon 2008 Armand, M.; Tarascon, J. M. Building better batteries. 2008
  * Cai et al. 2020 Cai, W.; Yao, Y.-X.; Zhu, G.-L.; Yan, C.; Jiang, L.-L.; He, C.; Huang, J.-Q.; Zhang, Q. A review on energy chemistry of fast-charging anodes. _Chemical Society Reviews_ 2020, _49_ , 3806–3833
  * Zhang et al. 2020 Zhang, J.; Yao, X.; Misra, R. K.; Cai, Q.; Zhao, Y. Progress in electrolytes for beyond-lithium-ion batteries. 2020; https://doi.org/10.1016/j.jmst.2020.01.017
  * Liu et al. 2020 Liu, T.; Vivek, J. P.; Zhao, E. W.; Lei, J.; Garcia-Araez, N.; Grey, C. P. Current Challenges and Routes Forward for Nonaqueous Lithium-Air Batteries. _Chemical Reviews_ 2020, _120_ , 6558–6625
  * Landi et al. 2009 Landi, B. J.; Ganter, M. J.; Cress, C. D.; DiLeo, R. A.; Raffaelle, R. P. Carbon nanotubes for lithium ion batteries. _Energy and Environmental Science_ 2009, _2_ , 638–654
  * Morgan et al. 2022 Morgan, L. M. et al. Pushing the boundaries of lithium battery research with atomistic modelling on different scales. _Progress in Energy_ 2022, _4_ , 012002
  * Liu et al. 2020 Liu, W.; Liu, P.; Mitlin, D. Review of Emerging Concepts in SEI Analysis and Artificial SEI Membranes for Lithium, Sodium, and Potassium Metal Battery Anodes. _Advanced Energy Materials_ 2020, _10_ , 2002297
  * Wu et al. 2020 Wu, F.; Maier, J.; Yu, Y. Guidelines and trends for next-generation rechargeable lithium and lithium-ion batteries. 2020
  * Adams et al. 2019 Adams, R. A.; Varma, A.; Pol, V. G. Carbon Anodes for Nonaqueous Alkali Metal-Ion Batteries and Their Thermal Safety Aspects. _Advanced Energy Materials_ 2019, _9_ , 1900550
  * Yao et al. 2022 Yao, X.; Olsson, E.; Wang, M.; Wang, J.; Cai, Q.; Peng, N.; Webb, R.; Zhao, Y. Xenon Ion Implantation Induced Surface Compressive Stress for Preventing Dendrite Penetration in Solid-State Electrolytes. _Small_ 2022, _18_ , 2108124
  * Wang et al. 2022 Wang, J.; Ma, Q.; Sun, S.; Yang, K.; Cai, Q.; Olsson, E.; Chen, X.; Wang, Z.; Abdelkader, A.; Li, Y.; Yan, W.; Ding, S.; Xi, K. Highly aligned lithiophilic electrospun nanofiber membrane for the multiscale suppression of Li dendrite growth. _eScience_ 2022,
  * Olsson et al. 2022 Olsson, E.; Cottom, J.; Alptekin, H.; Au, H.; Crespo-Ribadeneyra, M.; Titirici, M. M.; Cai, Q. Investigating the Role of Surface Roughness and Defects on EC Breakdown, as a Precursor to SEI Formation in Hard Carbon Sodium-Ion Battery Anodes. _Small_ 2022,
  * Wang et al. 2020 Wang, H.; Zhu, Y.; Kim, S. C.; Pei, A.; Li, Y.; Boyle, D. T.; Wang, H.; Zhang, Z.; Ye, Y.; Huang, W.; Liu, Y.; Xu, J.; Li, J.; Liu, F.; Cui, Y. Underpotential lithium plating on graphite anodes caused by temperature heterogeneity. _PNAS_ 2020, _117_ , 29453–29461
  * Li and Monroe 2019 Li, G.; Monroe, C. W. Dendrite nucleation in lithium-conductive ceramics. _Physical Chemistry Chemical Physics_ 2019, _21_ , 20354–20359
  * Xiao et al. 2022 Xiao, J.; Xiao, N.; Li, K.; Zhang, L.; Chang, J.; Ma, X.; Li, H.; Bai, J.; Jiang, Q.; Qiu, J. Ultra-High Fluorine Enhanced Homogeneous Nucleation of Lithium Metal on Stepped Carbon Nanosheets with Abundant Edge Sites. _Advanced Energy Materials_ 2022, _12_
  * Xing et al. 2021 Xing, X.; Li, Y.; Wang, S.; Liu, H.; Wu, Z.; Yu, S.; Holoubek, J.; Zhou, H.; Liu, P. Graphite-Based Lithium-Free 3D Hybrid Anodes for High Energy Density All-Solid- State Batteries. _ACS Energy Letters_ 2021, 10.1021/acsenergylett.1c00627
  * Duan et al. 2019 Duan, J.; Wu, W.; Nolan, A. M.; Wang, T.; Wen, J.; Hu, C.; Mo, Y.; Luo, W.; Huang, Y. Lithium–Graphite Paste: An Interface Compatible Anode for Solid-State Batteries. _Advanced Materials_ 2019, _31_
  * Niu et al. 2019 Niu, C.; Pan, H.; Xu, W.; Xiao, J.; Zhang, J.-G. G.; Luo, L.; Wang, C.; Mei, D.; Meng, J.; Wang, X.; Liu, Z.; Mai, L.; Liu, J. Self-smoothing anode for achieving high-energy lithium metal batteries under realistic conditions. _Nature Nanotechnology_ 2019, _14_ , 594–601
  * Liu et al. 2019 Liu, W.; Xia, Y.; Wang, W.; Wang, Y.; Jin, J.; Chen, Y.; Paek, E.; Mitlin, D. Pristine or Highly Defective? Understanding the Role of Graphene Structure for Stable Lithium Metal Plating. _Advanced Energy Materials_ 2019, _9_ , 1802918
  * Mukherjee et al. 2014 Mukherjee, R.; Thomas, A. V.; Datta, D.; Singh, E.; Li, J.; Eksik, O.; Shenoy, V. B.; Koratkar, N. Defect-induced plating of lithium metal within porous graphene networks. _Nature Communications_ 2014, _5_
  * Gu et al. 2022 Gu, Y.; He, Y.; Wei, L.; Lian, Y.; Pan, W.; Li, X.; Su, Y.; Peng, Y.; Deng, Z.; Liu, Z. Fast-charging and dendrite-free lithium metal anode enabled by partial lithiation of graphene aerogel. _Nano Research_ 2022, _15_ , 9792–9799
  * Buiel and Dahn 1999 Buiel, E.; Dahn, J. R. Li-insertion in hard carbon anode materials for Li-ion batteries. _Electrochimica Acta_ 1999, _45_ , 121–130
  * Zhao et al. 2021 Zhao, L. F.; Hu, Z.; Lai, W. H.; Tao, Y.; Peng, J.; Miao, Z. C.; Wang, Y. X.; Chou, S. L.; Liu, H. K.; Dou, S. X. Hard Carbon Anodes: Fundamental Understanding and Commercial Perspectives for Na-Ion Batteries beyond Li-Ion and K-Ion Counterparts. _Advanced Energy Materials_ 2021, _11_ , 1–28
  * Li et al. 2019 Li, Y.; Lu, Y.; Adelhelm, P.; Titirici, M.-M.; Hu, Y.-S. Intercalation chemistry of graphite: alkali metal ions and beyond. _Chemical Society Reviews_ 2019, _48_ , 4655–4687
  * Rajkamal and Thapa 2019 Rajkamal, A.; Thapa, R. Carbon Allotropes as Anode Material for Lithium-Ion Batteries. _Advanced Materials Technologies_ 2019, _4_ , 1900307
  * Olsson et al. 2022 Olsson, E.; Yu, J.; Zhang, H.; Cheng, H.; Cai, Q. Atomic‐Scale Design of Anode Materials for Alkali Metal (Li/Na/K)‐Ion Batteries: Progress and Perspectives. _Advanced Energy Materials_ 2022, _2200662_ , 2200662
  * Li et al. 2019 Li, Y.; Lu, Y.; Adelhelm, P.; Titirici, M.-M.; Hu, Y.-S. Intercalation chemistry of graphite: alkali metal ions and beyond. _Chemical Society Reviews_ 2019, _48_ , 4655–4687
  * Olsson et al. 2019 Olsson, E.; Chai, G.; Dove, M.; Cai, Q. Adsorption and migration of alkali metals (Li, Na, and K) on pristine and defective graphene surfaces †. _Nanoscale_ 2019, _11_ , 5274–5284
  * Olsson et al. 2021 Olsson, E.; Cottom, J.; Cai, Q. Defects in Hard Carbon: Where Are They Located and How Does the Location Affect Alkaline Metal Storage? _Small_ 2021, _17_ , 2007652
  * Olsson et al. 2021 Olsson, E.; Cottom, J.; Au, H.; Titirici, M.-M. M.; Cai, Q. Investigating the Effect of Edge and Basal Plane Surface Functionalisation of Carbonaceous Anodes for Alkali Metal (Li/Na/K) Ion Batteries. _Carbon_ 2021, _177_ , 226–243
  * Olsson et al. 2020 Olsson, E.; Cottom, J.; Au, H.; Guo, Z.; Jensen, A. C. S.; Alptekin, H.; Drew, A. J.; Titirici, M.-M.; Cai, Q. Elucidating the Effect of Planar Graphitic Layers and Cylindrical Pores on the Storage and Diffusion of Li, Na, and K in Carbon Materials. _Advanced Functional Materials_ 2020, _30_ , 1908209
  * Hussain et al. 2020 Hussain, T.; Olsson, E.; Alhameedi, K.; Cai, Q.; Karton, A. Functionalized Two-Dimensional Nanoporous Graphene as Efficient Global Anode Materials for Li-, Na-, K-, Mg-, and Ca-Ion Batteries. _The Journal of Physical Chemistry C_ 2020, _124_ , 9734–9745
  * Okamoto 2016 Okamoto, Y. Density Functional Theory Calculations of Lithium Adsorption and Insertion to Defect-Free and Defective Graphene. _Journal of Physical Chemistry C_ 2016, _120_ , 14009–14014
  * Liu et al. 2014 Liu, M.; Kutana, A.; Liu, Y.; Yakobson, B. I. First-principles studies of Li nucleation on graphene. _Journal of Physical Chemistry Letters_ 2014, _5_ , 1225–1229
  * Liu et al. 2013 Liu, Y.; Artyukhov, V. I.; Liu, M.; Harutyunyan, A. R.; Yakobson, B. I. Feasibility of lithium storage on graphene and its derivatives. _Journal of Physical Chemistry Letters_ 2013, _4_ , 1737–1742
  * Fan et al. 2013 Fan, X.; Zheng, W. T.; Kuo, J.-L. L.; Singh, D. J. Adsorption of single Li and the formation of small Li clusters on graphene for the anode of lithium-ion batteries. _ACS Applied Materials and Interfaces_ 2013, _5_ , 7793–7797
  * Huo et al. 2019 Huo, L.; Su, F.; Yi, Z.; Cui, G.; Zhang, C.; Dong, N.; Chen, C.; Han, P. The Inhibition Mechanism of Lithium Dendrite on Nitrogen-Doped Defective Graphite: The First Principles Studies. _Journal of The Electrochemical Society_ 2019, _166_ , A1603–A1610
  * Vandevondele et al. 2005 Vandevondele, J.; Krack, M.; Mohamed, F.; Parrinello, M.; Chassaing, T.; Hutter, J. Quickstep: Fast and accurate density functional calculations using a mixed Gaussian and plane waves approach. _Computer Physics Communications_ 2005, _167_ , 103–128
  * VandeVondele and Hutter 2007 VandeVondele, J.; Hutter, J. Gaussian basis sets for accurate calculations on molecular systems in gas and condensed phases. _The Journal of Chemical Physics_ 2007, _127_ , 114105
  * Hutter et al. 2014 Hutter, J.; Iannuzzi, M.; Schiffmann, F.; Vandevondele, J. Cp2k: Atomistic simulations of condensed matter systems. _Wiley Interdisciplinary Reviews: Computational Molecular Science_ 2014, _4_ , 15–25
  * Burke et al. 1998 Burke, K.; Cruz, F. G.; Lam, K.-C. Unambiguous exchange-correlation energy density. _The Journal of Chemical Physics_ 1998, _109_ , 8161–8167
  * Kühne et al. 2020 Kühne, T. D. et al. CP2K: An electronic structure and molecular dynamics software package -Quickstep: Efficient and accurate electronic structure calculations. 2020
  * Krack 2005 Krack, M. Pseudopotentials for H to Kr optimized for gradient-corrected exchange-correlation functionals. _Theoretical Chemistry Accounts_ 2005, _114_ , 145–152
  * Goedecker et al. 1996 Goedecker, S.; Teter, M.; Hutter, J. Separable dual-space Gaussian pseudopotentials. _Physical Review B_ 1996, _54_ , 1703–1710
  * Hartwigsen et al. 1998 Hartwigsen, C.; Goedecker, S.; Hutter, J. Relativistic separable dual-space Gaussian pseudopotentials from H to Rn. _Physical Review B_ 1998, _58_ , 3641–3662
  * Head and Zerner 1985 Head, J. D.; Zerner, M. C. A Broyden-Fletcher-Goldfarb-Shanno optimization procedure for molecular geometries. _Chemical Physics Letters_ 1985, _122_ , 264–270
  * Broyden 1970 Broyden, C. G. The convergence of a class of double-rank minimization algorithms 1. General considerations. _IMA Journal of Applied Mathematics (Institute of Mathematics and Its Applications)_ 1970, _6_ , 76–90
  * Shanno 1970 Shanno, D. F. Conditioning of Quasi-Newton Methods for Function Minimization. _Mathematics of Computation_ 1970, _24_ , 647
  * Fletcher 1970 Fletcher, R. A new approach to variable metric algorithms. _The Computer Journal_ 1970, _13_ , 317–322
  * Goldfarb 1970 Goldfarb, D. A Family of Variable-Metric Methods Derived by Variational Means. _Mathematics of Computation_ 1970, _24_ , 23
  * Perdew et al. 1997 Perdew, J.; Burke, K.; Ernzerhof, M. Errata: Generalized Gradient Approximation Made Simple. _Physical review letters_ 1997, _77_ , 3865–3868
  * Becke and Johnson 2005 Becke, A. D.; Johnson, E. R. Density-functional thermochemistry. III. The role of exact exchange. _Journal of Chemical Physics_ 2005, _123_ , 154108
  * Johnson and Becke 2006 Johnson, E. R.; Becke, A. D. A post-Hartree-Fock model of intermolecular interactions: Inclusion of higher-order corrections. _Journal of Chemical Physics_ 2006, _124_ , 174104
  * Grimme et al. 2011 Grimme, S.; Ehrlich, S.; Goerigk, L. Effect of the Damping Function in Dispersion Corrected Density Functional Theory. _Journal of Computational Chemistry_ 2011, _32_ , 1456
  * Grimme et al. 2010 Grimme, S.; Antony, J.; Ehrlich, S.; Krieg, H. A consistent and accurate ab initio parametrization of density functional dispersion correction (DFT-D) for the 94 elements H-Pu. _Journal of Chemical Physics_ 2010, _132_ , 154104
  * Grimme et al. 2007 Grimme, S.; Antony, J.; Schwabe, T.; Mück-Lichtenfeld, C. Density functional theory with dispersion corrections for supramolecular structures, aggregates, and complexes of (bio)organic molecules. _Organic and Biomolecular Chemistry_ 2007, _5_ , 741–758
  * Zhang and Northrup 1991 Zhang, S.; Northrup, J. Chemical potential dependence of defect formation energies in GaAs: Application to Ga self-diffusion. _Physical review letters_ 1991, _67_ , 2339–2342
  * Hjorth Larsen et al. 2017 Hjorth Larsen, A. et al. The atomic simulation environment - A Python library for working with atoms. _Journal of Physics Condensed Matter_ 2017, _29_ , 273002
  * Fan et al. 2019 Fan, X.; Ji, X.; Chen, L.; Chen, J.; Deng, T.; Han, F.; Yue, J.; Piao, N.; Wang, R.; Zhou, X.; Xiao, X.; Chen, L.; Wang, C. All-temperature batteries enabled by fluorinated electrolytes with non-polar solvents. _Nature Energy_ 2019, _4_ , 882–890