# A Multiple Snapshot Attack on Deniable Storage Systems
††thanks: This research was supported in part by the National Science
Foundation grant number IIP-1266400, award CNS-1814347, and by the industrial
partners of the Center for Research in Storage Systems.

Kyle Fredrickson, Austen Barker, and Darrell D. E. Long  University of
California, Santa Cruz

###### Abstract

While disk encryption is suitable for use in most situations where
confidentiality of disks is required, stronger guarantees are required in
situations where adversaries may employ coercive tactics to gain access to
cryptographic keys. Deniable volumes are one such solution in which the
security goal is to prevent an adversary from discovering that there is an
encrypted volume. Multiple snapshot attacks, where an adversary is able to
gain access to two or more images of a disk, have often been proposed in the
deniable storage system literature; however, there have been no concrete
attacks proposed or carried out. We present the first multiple snapshot
attack, and we find that it is applicable to most, if not all, implemented
deniable storage systems. Our attack leverages the pattern of consecutive
block changes an adversary would have access to with two snapshots, and
demonstrate that with high probability it detects moderately sized and large
hidden volumes, while maintaining a low false positive rate.

###### Index Terms:

Security, Steganography, Storage

##  I Introduction

Conventional disk encryption has been very successful at ensuring the
confidentiality and integrity of disks. In many applications reducing these
properties to corresponding key management problems is sufficient to ensure
security. However, when faced with adversaries capable of using coercive
tactics to reveal keys, conventional encryption comes up short. In these
situations the possession of an encrypted drive can be considered suspicious
enough to justify coercive attacks euphemistically known as rubber hose
attacks. These situations require that the mere presence of encrypted data be
unknown to the adversary to avoid the use of coercive tactics. Deniable
storage systems have been developed in response to this threat. These systems
are used to create a hidden volume on the user’s device, the existence of
which is plausibly deniable. One common strategy among deniable storage
systems is to encrypt data and randomly write it throughout the disk’s free
space. Assuming that the free space is filled with pseudorandom bytes, this
renders hidden data indistinguishable from unallocated blocks. This achieves
the goal of deniability when an adversary is restricted to viewing the disk at
one point in time and there are no other sources of information leakage.

A multiple snapshot attack is an attack on a hidden volume where an adversary
is able to gain access to a machine and make observations at two or more
points in time. Information gained from comparing these snapshots would then
be analyzed for abnormalities that could imply the existence of a hidden
volume. In many circumstances where a deniable volume may be used multiple
snapshot attacks are feasible. As an example, suppose a journalist is entering
a repressive country with the intent to exfiltrate some data. The adversary
first takes a snapshot of all devices entering the country, the journalist
collects the data to be exfiltrated and constructs a hidden volume to hide it,
then the adversary takes another snapshot when the device leaves the country.
This leaves the pattern of changes on the file system as a new source of
information leakage.

While multiple snapshot attacks on hidden volumes have been described in the
literature and defenses against them proposed [1, 2, 3, 4], to our knowledge
there has never been a thoroughly described or attempted example of this class
of attack. Among the reasons for this are not only the difficulty in obtaining
enough disk images to establish what a _normal_ pattern of changes is, but
also the difficulty in identifying meaningful features in observed change
patterns that would be invariant across normal use cases.

Using features derived from the change patterns on disks, we have defined and
implemented the first multiple snapshot attack against deniable storage
systems. The main contribution of our work is to affirm the relevance of
multiple snapshot attacks to deniable storage systems by demonstrating a
practical attack, while also identifying the limitations of our techniques. We
propose analyzing the distribution on the lengths of consecutive block
changes, which we call chains, as a new metric for quantifying disk behavior,
and leverage this information to distinguish between disks containing hidden
volumes and those that do not. Specifically we attack Artifice [5], a deniable
storage system, but our attack if broadly applicable, and is able to reveal
most, if not all, implemented deniable storage systems. In response to this
attack we propose additional design requirements for deniable systems, and
discuss the implications of these requirements on Artifice. Through this work
we hope to guide the design and implementation of future systems, improving
their security even against powerful adversaries with the ability to gain
access to devices at several points in time.

We first give background on deniable storage systems, going into detail on
Artifice, and describe past attacks on these systems. We then propose our
attack, describe our data collection and simulation methods, and give results
of the attack on our dataset. Finally, we describe mitigation schemes and
conclude.

##  II Background and Related Work

As previously stated, the goal of a deniable storage system is to conceal the
existence of a volume from an adversary that would otherwise view an encrypted
volume as suspicious and consequently coerce the user to disclose their secret
keys. With a hidden volume the user is able to reveal keys to known encrypted
drives while allowing the user to deny that hidden volumes exist on the
device.

Many deniable or steganographic storage systems have been proposed in past
years. One of the key concerns of these systems has been defending against
multiple snapshot attacks. In this section we will describe existing deniable
storage systems and attacks against those systems.

###  II-A Deniable and Steganographic Storage Systems

Anderson, _et al._ [6] were the first to propose a steganographic file system
and described two possible approaches. The first approach consists of a set of
cover files filled with random information, of which a subset are combined
with hidden files using an additive secret sharing scheme. The second
construction hides data within the unallocated space of another file system.
Although the proposal lacked an implementation of the two ideas, most deniable
storage systems follow the second approach.

McDonald and Kuhn implemented Anderson _et al._ ’s second scheme as a Linux
file system based on ext2 known as StegFS [7]. Although the scheme provides
deniability when the adversary can only view the device once, McDonald _et
al._ ’s StegFS and similar systems like TrueCrypt [8] or Mobiflage [9] cannot
provide a reasonable defense against an adversary that can view the disk
multiple times and compare snapshots.

Pang, _et al._ [10, 1] implemented a variant of StegFS that attempts to defend
against multiple snapshot adversaries by performing dummy operations to the
disk that obscure hidden writes. Similar approaches to this have been
implemented using derivatives of Oblivious RAM [11, 12] or similar techniques
to render accesses to a hidden volume indistinguishable from accesses to the
public volume [2, 3, 4]. Although these approaches render hidden and public
writes indistinguishable, they incur other abnormalities such as fully random
write patterns not exhibited by common file systems and significant
performance losses that would betray the existence of a hidden volume or the
ability to construct a hidden volume.

A perennial weakness of many of these systems is that they do not take
measures to hide the existence of the software used to access the hidden
volume, often claiming that widespread adoption would ensure the ability to
create a hidden volume is not suspicious. The fact that disk encryption,
though widespread, can still be seen as suspicious by many organizations calls
this assumption into doubt.

###  II-B Attacks on Steganographic Storage

Most existing storage systems assume that the adversary has the ability to
closely analyze characteristics of the user’s device for any clues that the
device contains a hidden volume. With respect to multiple snapshot analysis
and related attacks, previous work [2, 1] has categorized adversary
capabilities into three general categories.

  * •

Single snapshot A single snapshot adversary can only view a device once. All
existing deniable systems have some level of resilience against this sort of
attack.

  * •

Multiple snapshot In this case the adversary can view the device two or more
times. These snapshots can be compared, and the changes analyzed for anomalies
that could reveal a hidden volume on the user’s device. It is important to
note that in this class of attack the adversary is only able to view static
snapshots of the disk a limited number of times.

  * •

Continuous observation This is when an adversary has the ability to
continuously observe writes to the user’s device or make a snapshot of the
device for each write. This adversary capability is sometimes also called
_continuous traffic analysis_. This sort of attack would likely require a form
of malware to be installed on the user’s device for the purposes of
information gathering. OS level spyware would be able to monitor writes to the
user’s device.

Proposed attacks and serious attempts to break deniable storage systems are
limited when compared to the variety of proposed systems. One vulnerability
found by Czeskis _et al._ when analyzing TrueCrypt was its susceptibility to
leaking information from the hidden to public volumes through operating system
utilities and common applications such as word processors. Another work by
Troncoso _et al._ describes and implements a continuous traffic analysis
attack against Pang’s StegFS that exploits repeated write patterns that
correspond to writes made to a hidden volume. While this attack shows the
effectiveness of monitoring disk operations in finding a hidden volume, it is
assumed that the adversary has enough power to continuously observe the disk.
The multiple snapshot adversary is considerably weaker than the continuous
observation adversary, yet there has been no previous work towards
demonstrating a multiple snapshot attack against a deniable storage system.

###  II-C Artifice

For the purposes of testing a multiple snapshot attack we will use Artifice as
our deniable storage system. Artifice follows the common model of hiding
information in unallocated blocks but with a few additional features that
address some pitfalls of other existing file systems [5]. Most importantly it
addresses problems with hiding its driver software and provides a layer of
protection against malware and information leakage by putting the Artifice
driver on a separate Linux live USB drive. To access a hidden volume, the user
boots into an Artifice-aware OS contained on this drive instead of the normal
public OS. This isolation does not leave behind suspicious drivers on the
user’s machine and mitigates the impact of malware and information leakage.

Artifice writes data by splitting data blocks into pseudo-random _carrier
blocks_ using an information dispersal algorithm (IDA) such as Shamir Secret
Sharing [13]. These carrier blocks are then uniformly distributed throughout
the unallocated space of the drive, which is assumed to be full of
pseudorandom blocks due to a secure deletion utility or similarly deniable
means. Since the public file system is not aware of Artifice, it is imperative
to protect the carrier blocks from accidental overwrite. IDAs provide Artifice
overwrite tolerance by writing redundant carrier blocks in excess of the
number needed to normally reconstruct the data. This allows Artifice to carry
out self-repair operations whenever accessed by the user and increases the
probability that an Artifice instance will survive many writes made by the
public file system.

Currently, Artifice aims to address the problem of multiple snapshot attacks
through writing hidden blocks under the guise of a suitable deniable
operation, such as defragmentation, where the contents of a disk are relocated
to be contiguous, routine file deletion, or by operational security measures
that render previous snapshots useless, such as reinstalling the public
operating system or wiping the storage prior to constructing an Artifice
instance.

##  III Attack Framework

Figure 1: Theoretical probability of consecutive changes when changes are made
uniformly. The probability of $c$ consecutive changes degrades very quickly,
especially when the free space is large.

Figure 2: Empirical probability of consecutive changes for 52 change records
where the changes are made by an ext4 file system.

The primary goal of an attack on a deniable storage system is not to recover
the plaintext files, but to discover the presence of hidden volumes. In
Artifice’s adversary model, it is assumed that the adversary can coerce a user
to reveal their keys provided there is sufficient suspicion that a user
possesses a hidden volume [5]. The success of a particular attack then is
dependent on how well the attack can discriminate between disks containing
hidden volumes and those that do not. In particular, the rates of false
positives and false negatives should both be very low for an attack to be
considered successful.

As noted most deniable storage systems achieve their aims by encrypting and
splitting data into redundant shares and writing these blocks uniformly on the
disk [5, 10]. This increases the odds of survival of the files when the public
file system, which is unaware of their existence, makes its own writes. Other
approaches write public and hidden data psuedorandomly so that public and
hidden writes are indistinguishable [2, 3].

The commonality between these approaches is that deniable storage systems make
many uniform writes. Depending on the size of the free space, writes made
uniformly are very likely to result in isolated changes on disk, which we call
_s_ ingletons. This is in contrast to normal file systems, which do not make
their writes uniformly, and are much more likely to make writes that are part
of longer strings of consecutive changes that we call _c_ hains. We call a
chain of $c$ consecutive changes a $c$-chain.

######  Example III.1.

Say that in a change record a 1 denotes a change and a 0 denotes no change
between two snapshots. Then in (1) there are two singletons (or 1-chains) and
one 3-chain.

1 | 0 | 1 | 0 | 1 | 1 | 1
---|---|---|---|---|---|---
(1)

An adversary observing the change records produced from a pair of disk
snapshots would be able to observe the lengths of the chains those changes
produce. Crucially if the disk contains a hidden volume, the adversary would
also see changes made by writes to that volume. In Appendix -A we give the
theoretical distribution of chains given the size of the disk and the number
of changes made. We find they are distributed according to lemma .1. Fig. 1
shows that as the free space grows relative to the number of writes, the
probability of a singleton increases. Fig. 2 shows that for real disks, the
probability of a singleton is much smaller, and the tail of the distribution
is typically much heavier. Together they show the disparity between the
distributions of chains due to a hidden volume and the chains due to a public
file system. This becomes more pronounced as the hidden volume makes more
writes. Our task then is to construct features to distinguish between the
distribution of consecutive changes made by a public file system and changes
made by a public file system and a hidden volume.

To carry out this attack, we assume that the attacker has access to a large
set of disk images, both from disks that contain hidden volumes and from those
that do not. Images in this set will be organized into pairs of images from
the same disk at different points in time. Comparing these pairs of images
results in a change record for a given disk. We will call pairs that do not
have an instance of a hidden volume clean and those that do dirty. Assuming
our adversary is well-funded and motivated these data requirements are easily
attainable.

Since for our proposed attack we only need to determine whether individual
blocks have changed, we can take snapshots of the clean and dirty disks in a
space efficient manner by hashing each block on the disk, and constructing a
Merkle tree [14] over the hashed blocks. This gives us a very efficient method
of finding changes, and producing change records. These change records are
further processed into lists of integers, $D_{i}$, recording the lengths of
chains found in each change record. We will denote these lists of chains
$\\{D_{i}\\}=\mathcal{D}$.

From $\mathcal{D}$ the adversary has several options for constructing an
arbitrary $n$ number of features for use in a classification algorithm. The
first is to remove a set of clean disks that we will call $\mathcal{C}$. Using
$\mathcal{C}$ the adversary estimates the probability of $c$-changes from $1$
to $n$, the number of features, for each $D_{i}$ by counting the occurrences
of each $c$-chain and dividing by the total number of chains in $D_{i}$. Using
these probabilities on $\mathcal{D}-\mathcal{C}$, the adversary can then
estimate the probability of a disk containing more than $k$ $c$-chains with
the cumulative distribution function (CDF) of the binomial distribution,
$F(k;n,p_{c})$ where $n$ is the length of the change record and $p_{c}$ is the
estimated probability of a chain of $c$ consecutive changes. We will denote
the event of an adversary observing $k$ consecutive changes of length $c$ as
$X_{c}$. Then,

$P(X_{c}>k)=1-F(k;n,p_{c}).$ (2)

Using these values we construct our final features $\mathcal{F}$ for
$\mathcal{D}$. This method has greater sensitivity to small variations in
probabilities for small disks; however, on large disks it tends to underflow
when computing equation (2). We give pseudocode for this in algorithm (1).

For large datasets, we take a simpler approach to computing $\mathcal{F}$ by
computing the probabilities of chains of length $1$ to $n$ for each $D_{i}$
and feeding these to our classifier.

Recall that the dataset is entirely constructed by the adversary, so it has
ground truth labels describing whether each row in $\mathcal{F}$ corresponds
to a disk containing a hidden volume or not. The adversary now trains a
supervised classification algorithm on $\mathcal{F}$ split into standard train
and test sets. On new pairs of disks the adversary runs through the feature
construction process, then runs the classification algorithm on those feature
and responds accordingly. Furthermore, if the adversary can confirm that some
disks did in fact contain a hidden volume, it can update its model using
various online learning techniques [15], further refining its model.

As a note on selection of the number of features, we observe from lemma .1
that when the free space on a disk is large relative to the number of writes,
the vast majority of writes will result in singleton changes. As a
consequence, the adversary could learn based on a single feature derived from
singletons. This may be desirable in some situations for the sake of
efficiency; however, Artifice could simply be modified so that when writing
blocks they would be grouped in chains of two or more, thereby defeating the
attack as described. The adversary can in turn thwart this countermeasure by
increasing the number of features, $n$. We go into more detail regarding this
problem in Section VI.

Input: $\mathcal{D}$, a set of processed disks; $\\{p_{1},...,p_{c}\\}$, the
estimated probabilities of consecutive changes of length $1...c$.

Output: $\mathcal{F}$, a $|\mathcal{D}|\times c$ matrix.

$\mathcal{F}:=\\{\\}$

foreach  _$D_{i}\in\mathcal{D}$_ do

$f:=\\{\\}$

foreach  _$c_{i}\in\\{1...c\\}$_ do

$k:=$ number of $c$-consecutive changes in $D_{i}$

$a:=1-F(k;|D_{i}|,p_{c_{i}})$

$\mathsf{append}(a,f)$

end foreach

$\mathsf{append}(f,\mathcal{F})$

end foreach

$\mathsf{return}$ $\mathcal{F}$

Algorithm 1 Feature Construction. This method is suitable for smaller disks,
where greater sensitivity is required, but suffers from underflow on large
disks.

##  IV Data Collection and Experiment Methodology

As noted previously, one of the challenges of carrying out a multiple snapshot
attack is the availability of pairs of disk images. These are necessary to
learn what normal chains look like. While collecting hundreds, or thousands,
of disk images may be feasible for a nation state level adversary (or a large
IT department), we were unable to collect such a large amount of data.

Instead, we have collected several months worth of snapshots from a 1 TB NVMe
SSD formatted with ext4 and in use as the boot disk of a desktop computer
running Ubuntu 18.04. We collected 53 snapshots in total, giving us 52 change
records111This data is available at https://files.ssrc.us/data/disk-change-
data.zip. The code for these experiments is available at
https://github.com/ucsc-ssl/multiple-snapshot-attack. which we have made
publicly available. By observing the distribution of lengths of changes over
our collected data (Figure 2), and the theoretical distribution of consecutive
changes (Figure 1) when changes are made uniformly, the potential strangeness
of a disk running a deniable volume becomes clear.

Because just 52 data points are insufficient to train a classifier, and
moreover, would be inconclusive regarding performance of that classifier, we
instead used this data to generate a synthetic dataset on which to train and
test our classifier. While in the real world different file systems may
produce different patterns of changes, this does not change the reality that a
deniable volume writing many single blocks, and thereby causing many singleton
chains in the change record, would be considered abnormal regardless of the
public file system in use. Though the fact that our attack only utilizes data
from ext4 file systems is a limitation, no file system in widespread use
writes blocks randomly, so we expect our attack will generalize to other data
sources.

Our experiments are conservative in terms of the operational security measures
the user of a hidden volume might take. We discuss them here to motivate our
experimental design.

There are several things that the user of a deniable volume could do to
decrease the odds of detection. To start, assume that a single snapshot has
been taken, and no deniable volume yet exists on the drive. A prudent user
would make many changes to the disk through the public file system. The reason
for this being that if there are overwhelmingly many chains distributed
according to normal disk behavior, the singletons made by writing to the
hidden volume could be made to look like noise. To illustrate this, consider a
user that does not produce a single change through the public file system
after the deniable volume is created and written to. In this case the
adversary would see, after taking a second snapshot and computing the
differences, only chains produced by the deniable volume. These chains would
be principally singletons, which would surely be conspicuous. As an extreme
measure the user could simply wipe the disk and then create the deniable
volume, but this may be considered suspicious or may be undesirable for other
reasons. As a less drastic alternative, the user could produce an overwhelming
number of changes to the disk through the public file system. In our
experiments we chose this middle ground by using our real data to simulate 25
GB worth of public changes on a 1 TB disk with 100 GB of free space. This
produces a sufficient number of public changes to hide private changes while
still behaving as a normal user might.

Each pair of disk snapshots can be regarded as producing a distribution over
consecutive change lengths, so in order to construct our synthetic dataset we
simply draw chains from these distributions. Realistically, the fraction of
disks containing hidden volumes would be relatively small, and the size of
hidden volumes would also be variable. For our hidden volumes, we assume that
we have instances that are from 250 MB to 1.25 GB in increments of 250 MB. In
addition to its realism, this allows us to determine a point at which the
number of uniform writes becomes conspicuous. For our Artifice parameters we
chose those that minimized the number of writes, while achieving survival
probabilities over 80% with 25 GB of cover changes. This led us to copy data
blocks 6 times, where the survival of a single block is sufficient for
reconstructing the data. Since our adversary is able to generate an arbitrary
number of disk snapshots with and without hidden volumes, in order to allow
our classifier to learn to distinguish disks more quickly our training set
contains an even split of disks with and without hidden volumes. However, to
reflect the rarity of hidden volumes in the real world only 5% of our test set
contains disks with a hidden volume. We generate a training set of size 10000
and a test set of size 2500. We repeat this generation, training and testing
cycle 100 times to ensure the reliability of our results.

##  V Results

By implementing the experimental methodology described in Section IV and
running it against our dataset we collected a set of results that show the
efficacy of our proposed multiple snapshot attack. It should be noted from the
start that at the core of our implementation is a simple logistic regression
that takes only the probability of a single block change on the disk into
account. In choosing to implement such a simple learning algorithm we
highlight the distinguishing power of analyzing consecutive block changes in
detecting anomalous disk behavior.

We collected five different metrics on our classifier: accuracy, precision,
recall, false positive rate, and false negative rate. Because only 5% of our
test set contains Artifice instances accuracy is not a very informative
metric, and we include it for completeness only. Precision is the ratio of
true positives to predicted positives. Recall is the ratio of true positives
to true positives and false negatives, giving the ratio of Artifice instances
that were identified from the test set. False positive rates and false
negative rates are useful for understanding how frequently our classifier
makes errors in both directions. We consider false classification rates to be
the most important metrics for an attacker.

In our experiments the 250 MB Artifice instances were often able to pass
undetected, implying that 25 GB of cover changes were sufficient to hide these
volumes. However, the largest four sizes were reliably detected, with the
three largest sizes, 0.75 GB, 1.0 GB and 1.25 GB, being detected nearly 100%
of the time. This highlights a feature of our attack, namely that for 25 GB of
cover changes every Artifice instance above a certain size will be detected
with high probability. This is because of our use of logistic regression, and
because the probability of singletons is so overwhelming. Eventually as free
space fills up, Artifice will begin to make changes that are parts of longer
chains, but if the reconstruction threshold is low, this will severely impact
the survivability of the volume.

Figure 3: Hidden volumes in excess of 0.75 GB are always identified
successfully.

The presence of a point where the FNR becomes negligible also offers an
explanation for the relatively constant false positive rate. This being that a
certain percentage of simulated clean disks will naturally have
disproportionately many singletons and thus get misclassified as containing an
Artifice volume. Interestingly, there were very few disks that naturally had
enough singletons to exceed the learned threshold.

Future work may combine the features we use in this attack with other
features. Such as what proportion of changes are made to blocks in free space
versus allocated blocks. The introduction of more features would serve to
better characterize disk behavior and further improve the efficacy of the
attack.

Size (GB) | Acc. | Precision | Recall | FPR | FNR
---|---|---|---|---|---
0.25 | 0.981 | 0.911 | 0.680 | 0.004 | 0.320
0.5 | 0.993 | 0.934 | 0.937 | 0.004 | 0.063
0.75 | 0.997 | 0.942 | 0.999 | 0.003 | 0.001
1.0 | 0.996 | 0.935 | 1.0 | 0.004 | 0.0
1.25 | 0.997 | 0.939 | 1.0 | 0.004 | 0.0
Figure 4: Numeric results from our experiments. These results are averaged
over 100 runs. Furthermore, 95% confidence intervals for all figures vary only
in the thousandths.

##  VI Attack Mitigation

Artifice’s authors propose an operational security based approach to defend
against multiple snapshot attacks [5]. The rationale being that if the user
can produce a deniable reason for changes to the entire disk, such as re-
installing the operating system or defragmentation, then the adversary’s
previously gathered data would be rendered useless. This defense relies
heavily on the ability of the user to out-maneuver the adversary and will not
always be practical. As a result, it would be prudent to develop some other
countermeasures against our proposed attack and future types of snapshot
analysis.

We can observe in Figure 3 that the FNR of our classifier decreases as the
effective size of the Artifice instance increases while the amount of data
written by the public volume remains the same. With this in mind we can
conclude that the operational strategy proposed in Section IV, to keep the
proportion of hidden to public writes sufficiently skewed in favor of the
latter, is a viable strategy. Unfortunately, this severely limits the
effective size of Artifice.

While our proposed mitigation technique is a promising means of defense
against snapshot analysis it is still worthwhile to explore the possibility of
a mechanism that does not require such close user involvement. In order for a
deniable storage system to defend against a snapshot attack without
operational measures, the designer of such a system could attempt to mimic the
distribution of writes that the public file system is making. Similar to our
operational approach, the survivability of a hidden volume may be impacted by
changing the distribution of writes from uniform to something more closely
resembling a normal file system. In the case of Artifice, the reason that it
writes blocks uniformly is to ensure that any writes made to the public file
system are unlikely to destroy too many Artifice blocks. As such, system
designers need to be careful when implementing countermeasures to maintain a
high probability of survival when using the public file system while still
successfully mimicking its write behavior.

In our proposed attack, we use only one feature associated with single block
changes to the disk. A naive approach would be to simply write all blocks in
pairs, producing consecutive changes of two blocks. This would defeat our
attack, but the adversary could expand its feature set to include changes two
blocks long and so on, forcing the user of the hidden volume to mimic the
public file system or risk detection. Furthermore, given the myriad measurable
features in the average file system and that the adversary is unlikely to
publish details of its attack, we can conclude it would be difficult to
accurately determine what features are and are not being tracked by the
adversary, making mimicry the safest option.

In order to accurately mimic expected access patterns, much more work needs to
be done to quantify exactly what a change pattern for a disk without a
deniable volume looks like. A significant body of work has been published in
the context of network steganography and pattern mimicking cryptography and
could be used to inform designers of future multiple snapshot resistance
systems. For instance, initial work into format transforming encryption by
Dyer _et al._ [16] showed that it was possible to efficiently encrypt data so
that it would conform to a target regular expression. An application of this
is found in censorship resistant networking. In this case a user might be
running a blacklisted protocol, such as Tor, but transforms the protocol
messages in such a way that they look like HTTPS. Similar techniques could be
applied to deniable storage to disguise suspicious write patterns.
Unfortunately, there is also evidence that more capable adversaries utilizing
more sophisticated attacks can easily identify these false protocols.
Houmansadr _et al._ [17] argue that it is unlikely that one could mimic a
protocol perfectly without running the actual protocol, because there are
often sub-protocols one would also need to mimic or differences in
implementations that allow for version fingerprinting. Assuming snapshot
analysis becomes more sophisticated it is likely that mimicry techniques
applied to deniable storage would also need to evolve.

Since Artifice relies on pseudorandom data in free space and the use of secure
deletion utilities to produce cover changes, one way to potentially sidestep
the issues of artificial mimicry could be found in actually using these
deleted files. Artifice could keep track of changes in free space on the
public file system, and when it sees a block added to free space it could
overwrite this with an Artifice block. As noted above this is not uniformly
written and so may risk corruption of files, but it also may provide stronger
mimicry guarantees than other methods. We leave it to future work to
investigate this and the other techniques we have presented for mitigation.

##  VII Conclusion

We have demonstrated the first implemented multiple snapshot attack against
deniable storage systems. In doing so we showed the broad usefulness of change
records to an adversary seeking to detect hidden volumes. Furthermore, we
presented a concrete way to analyze changing disks, even when the contents and
sizes of those disks are radically different. Through our data collection we
were able to show that this measure of computing consecutive change lengths of
a disk is relatively stable. For our data we collected over fifty images of
ext4 disks and used records of changes across these images to train a
classifier on probabilities of chains. We demonstrated that this classifier is
able to differentiate between disks containing a hidden volume from disks
without a hidden volume in a variety of configurations. In the process we have
also identified limitations to our technique and from those limitations have
proposed possible countermeasures to our attack.

As future work we would like to gather substantially more data from more
varied sources. In addition to covering the major file systems, collecting
data from many different types of computer users would give us greater
confidence in the stability of our metrics. Finally, the attack we propose has
great potential for expansion. Many more features could be included, such as
number of writes and location of writes in free and used space. Adding
additional features would be trivial, and have the potential to further
improve the performance of the attack, lowering the false positive rate, and
the size of hidden volumes that can be expected to evade detection.

## References

  * [1] X. Zhou, H. Pang, and K. Tan, “Hiding Data Accesses in Steganographic File System,” in _Proceedings 20th International Conference on Data Engineering_ , April 2004, pp. 572–583.
  * [2] E.-O. Blass, T. Mayberry, G. Noubir, and K. Onarlioglu, “Toward Robust Hidden Volumes Using Write-Only Oblivious RAM,” in _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security (CCS ’14)_. New York, NY, USA: ACM, 2014, pp. 203–214.
  * [3] A. Chakraborti, C. Chen, and R. Sion, “DataLair: Efficient Block Storage with Plausible Deniability against Multi-Snapshot Adversaries,” _Computing Research Repository (CoRR)_ , vol. abs/1706.10276, 2017.
  * [4] C. Chen, A. Chakraborti, and R. Sion, “PD-DM: An Efficient Locality-preserving Block Device Mapper with Plausible Deniability,” _Proceedings on Privacy Enhancing Technologies_ , vol. 2019, pp. 153–171, 01 2019.
  * [5] A. Barker, Y. Gupta, S. Au, E. Chou, E. L. Miller, and D. D. E. Long, “Artifice: Data in Disguise,” in _Proceedings of the Conference on Mass Storage Systems and Technologies (MSST ’20)_ , Oct. 2020.
  * [6] R. Anderson, R. Needham, and A. Shamir, “The Steganographic File System,” in _International Workshop on Information Hiding_ , D. Aucsmith, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1998, pp. 73–82.
  * [7] A. D. McDonald and M. G. Kuhn, “StegFS: A Steganographic File System for Linux,” in _International Workshop on Information Hiding_. Springer, 1999, pp. 463–477.
  * [8] Truecrypt Foundation, “Truecrypt,” http://truecrypt.sourceforge.net.
  * [9] A. Skillen and M. Mannan, “On Implementing Deniable Storage Encryption for Mobile Devices,” in _20th Annual Network & Distributed System Security Symposium_, February 2013.
  * [10] H. Pang, K. Tan, and X. Zhou, “StegFS: A Steganographic File System,” in _Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405)_ , March 2003, pp. 657–667.
  * [11] O. Goldreich, “Towards a Theory of Software Protection and Simulation by Oblivious RAMs,” in _Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC ’87)_. ACM, 1987, pp. 182–194.
  * [12] O. Goldreich and R. Ostrovsky, “Software Protection and Simulation on Oblivious RAMs,” _J. ACM_ , vol. 43, no. 3, pp. 431–473, May 1996.
  * [13] A. Shamir, “How to Share a Secret,” _Communications of the ACM_ , vol. 22, no. 11, pp. 612–613, 1979.
  * [14] R. C. Merkle, “A digital signature based on a conventional encryption function,” in _Conference on the theory and application of cryptographic techniques_. Springer, 1987, pp. 369–378.
  * [15] S. Shalev-Shwartz _et al._ , “Online learning and online convex optimization,” _Foundations and trends in Machine Learning_ , vol. 4, no. 2, pp. 107–194, 2011.
  * [16] K. P. Dyer, S. E. Coull, T. Ristenpart, and T. Shrimpton, “Protocol misidentification made easy with format-transforming encryption,” in _Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security_, 2013, pp. 61–72.
  * [17] A. Houmansadr, C. Brubaker, and V. Shmatikov, “The Parrot is Dead: Observing Unobservable Network Communications,” in _2013 IEEE Symposium on Security and Privacy_ , 2013, pp. 65–79.

###  -A Theoretical Probability of Consecutive Changes

Suppose we have an array, $A$, of size $n$ and we make $k$ changes to it at
random, where $1$ denotes a change and $0$ denotes no change. What is the
probability of selecting a chain of exactly $c$ consecutive changes? We give
an example and then give the general statement and proof.

######  Example .1.

When $n=7$ and $k=4$, what is the probability of drawing a chain of length 2
from the array?

In this case it is feasible to enumerate all ${7\choose 4}=35$ possible
arrangements of the disk. Doing so we see there are 12 ways to get arrays with
one chain of length $2$ and two chains of length $1$. We also see that there
are 6 ways to get arrays with two chains of length $2$. Therefore,
$\Pr(C=2;n=7,k=4)=\frac{12}{35}\cdot\frac{1}{3}+\frac{6}{35}\cdot\frac{2}{2}$

For larger values of $n$ and $k$ this quickly becomes infeasible. Instead, we
describe a method whose complexity only depends on $k$.

######  Lemma .1.

Let $A$ be an array of size $n$ with $k\leq n$ entries made at random. Then
the probability of a chain of $c$ consecutive changes in $A$ is

$\Pr(C=c)=\sum_{p\in P}\frac{{n-k+1\choose|p|}}{{n\choose k}}\Pr(C=c\mid p),$
(3)

where $P$ is the set of partitions of $k$, $|p|$ is the number of elements in
a partition $p$, and $\Pr(C=c\mid p)$ is the probability of $c$ in a partition
$p$.

###### Proof.

Let $A$ be an array of length $n$ with $k$ changes made uniformly at random.
Then $A$ can be represented as $p=(p_{1},p_{2},...,p_{k})$, an ordered
partition of $k$, where each $p_{i}\in\mathbb{Z}$ represents the $i$-th string
of $p_{i}$ consecutive $1$s separated by one or more $0$s. Let $|p|$ be the
length of the partition of $k$. By our construction of $p$, $A$ is uniquely
represented by $p$ and

$p_{1}+p_{2}+...+p_{|p|}=k.$ (4)

Since any array $A$ can be represented by $p\in P$, where $P$ is the partition
of $k$, we can compute $\Pr(C=c)$ as

$\Pr(C=c)=\sum_{p\in P}\Pr(C=c\mid p)\Pr(p),$ (5)

by marginalizing over $P$, the size of which is ${2k-1\choose k-1}$. We
conclude the proof by computing $\Pr(p)$. Since there are ${n\choose k}$
possible arrays, counting the number of arrays represented by $p$ is
sufficient to compute $\Pr(p)$.

######  Example .2.

(continued from example .1) The ordered partitions of 4 are

$(4),(3,1),(1,3),(2,2),(2,1,1),(1,2,1),(1,1,2),(1,1,1,1).$

Taking $c=2$, we have $(2,2),(2,1,1),(1,2,1),(1,1,2)$ all contain at least one
$2$.

Notice that when $p=(2,1,1)$, the array will take the form $\star 110\star
10\star 1\star$, where $\star$ represents zero or more $0$s. Therefore, there
is a single $0$ whose location is not fixed by $p$, and there are ${4\choose
1}=4$ ways to place it.

Arrays that are represented by $p$ must have the form

$\star\underbrace{11\cdots 10}_{p_{1}}\star\underbrace{11\cdots
10}_{p_{2}}\star\cdots\star\underbrace{11\cdots 1}_{p_{|p|}}\star$

by our construction. Notice that there are $k$ $1$s and $|p|-1$ $0$s in the
string above, so there are $n-k-(|p|-1)$ $0$s whose locations are unfixed.
There are ${n-k-1\choose|p|}$ different ways to place these $0$s, thus

$\Pr(p)=\frac{{n-k-1\choose|p|}}{{n\choose k}},$ (6)

completing the proof. ∎


# Developing Flying Explorer for Autonomous Digital Modelling in Wild Unknowns

Naizhong Zhang1,∗,# Yaoqiang Pan2,∗, Yangwen Jin2,∗, Peiqi Jin2, Kewei Hu2,
Xiao Huang1, and Hanwen Kang2,# ∗ Contribute Equally# Correspond Authors1 N.
Zhang, X. Huang are with the College of Civil Aviation, Nanjing University of
Aeronautics and Astronautics, Nanjing, China2 Y.Pan, Y.Jin, P.Jin, K.Hu and
H.Kang are with the College of Engineering, South China Agriculture
University, Guangzhou, China

###### Abstract

This work presents an innovative solution for robotic odometry, path planning
and exploration in wild unknown environments, focusing on digital modelling.
The approach uses a minimum cost formulation with pseudo-randomly generated
objectives, integrating multi-path planning and evaluation, with emphasis on
full coverage of unknown maps based on feasible boundaries of interest. The
evaluation carried out on a robotic platform with a lightweight 3D LiDAR
sensor model, assesses the consistency and efficiency in exploring completely
unknown subterranean-like areas. The algorithm allows for dynamic changes to
the desired target and behaviour. At the same time, the paper details the
design of AREX, highlighting its robust localisation, mapping and efficient
exploration target selection capabilities, with a focus on continuity in
exploration direction for increased efficiency and reduced odometry errors.
The real-time, high-precision environmental perception module is identified as
critical for accurate obstacle avoidance and exploration boundary
identification.

##  I Introduction

The Digital Twin (DT) concept, introduced by NASA in 1991, involves virtual
representations of physical assets that reflect their context through data
from various sensors[1]. Digital modelling (DM) is a critical task within the
DT framework[2], contributing to insights, predictions and performance
optimisation in industries such as manufacturing and transportation.
Industries that rely on digital models, such as agriculture and construction,
benefit greatly from drones with exceptional obstacle-avoidance
capabilities[3]. These drones can generate 3D models of complex terrains and
intricate plantations. The introduction of digital models in plantations
significantly enhances daily tasks like harvest planning, and revolutionizing
orchard management[4, 5].

This article explores a unique mapping and exploration theory that paves the
way for autonomous, drone-based, rapid exploration models of orchards. In the
field of management, the development of autonomous robotic platforms with
exploration and mapping capabilities is revolutionary[6]. Robots, especially
those equipped with 3D LiDAR sensors, contribute essential elements to DM,
including accurate 3D modelling[7]. Their ability to mark characteristic
points at specific locations is proving beneficial for later data collection
and processing[8, 9].

Exploring and mapping unknown and unstructured environments has always been an
important and fundamental task for robots. This includes tasks such as
inspecting large infrastructures, surveying buildings, performing search and
rescue missions, and exploring underground spaces. The exploration of wild,
unknown and unstructured environments, especially those that are harsh and
lack GPS connectivity, has become a major focus for autonomous robotic
exploration missions. This focus has grown significantly in recent years,
particularly with events such as the DARPA Subterranean Challenge. In this
challenge, teams of robots are tasked with exploring and identifying artefacts
in complex and unstructured environments. In conjunction with Simultaneous
Localisation and Mapping (SLAM), overcoming the challenges of motion planning
and exploration behaviour is one of the most fundamental issues in these
diverse applications.

Figure 1: AREX: Flight System Designed for High Durability, Multi-Scenario
Exploration, and Environmental Modeling.

Robotic localisation, path planning, and exploration are fundamental research
areas for building such a robotic system[10], with various solutions to the
challenge of fully exploring unknown areas, including pattern-based
approaches, frontier methods and entropy-based strategies[11]. Occupancy-based
path planning, which relies on maps of occupied and free space, often uses
algorithms such as Dijkstra’s or advanced versions of A* and jump-point-
search. Alternatively, the Rapidly-Exploring Random Tree (RRT) algorithm, in
its modern versions, serves as a core component of some path planning
solutions, offering computational efficiency and flexibility, but lacking the
guarantee of finding the shortest path within a limited number of iterations.
Traditionally, exploration and planning problems have been treated separately.
For example, in [12], a deep reinforcement model selects optimal bounds and an
A* algorithm finds the shortest path. In [13], stochastic differential
equations identify optimal bounds and an RRT* path planner computes the path.
Recently, the integration of exploration into the central planning problem has
gained attention, with solutions such as Next-Best-View planners [14] being
foundational. Exploration RRT (ERRT)[15] shares core concepts with Next-Best-
View planners but is innovative in its algorithmic implementation. ERRT
explicitly solves paths to pseudo-random objectives, which distinguishes it
from the iterative evaluation of RRT branches. In particular, ERRT computes
optimal actuation for trajectory following through a receding horizon NMPC
problem, with the proposed method using the Optimization Engine, an open-
source Rust-based optimization software.

Figure 2: Robot Design (a) AREX’s frame structure and sensor layout. The
MID-360 LiDAR is positioned at the front of the fuselage at a 45∘ angle to the
horizontal z-axis, while the Realsense D430 is mounted above the MID-360 to
fill in blind spots in the point cloud. The front dual arms of AREX form a
120∘ angle, maximizing the avoidance of obstructing the LIDAR’s scanning
range. (b) AREX’s circuitry structure. Reflects the circuitry between the ESCs
and motors, as well as the communication interfaces and protocols among
various modules.

This work presents a novel solution to the combined challenge of robotic
odometry, path planning, and exploration for digital modelling in wild unknown
environments. It employs a minimum cost formulation with pseudo-randomly
generated objectives, integrating multi-path planning and evaluation. This
evaluation considers information gain and total distance. Our approach
emphasises full coverage of the unknown map, depending on the availability of
feasible boundaries of interest. The evaluation focuses on a robotic platform
with a lightweight 3D LiDAR sensor model and evaluates the consistency and
efficiency of exploring a completely unknown subterranean-like and
unstructured area. The algorithm is designed with versatile robot localisation
and motion planning that allows dynamic changes to the desired goal and
behaviour. Our detailed contributions are presented below.

  * •

Developing the Aerial Robot EXploration (AREX) system, including its hardware
and software framework, for autonomous digital modelling in unstructured and
unknown environments.

  * •

Developing a novel algorithm for autonomous exploration in unknown
environments for multiple scenarios.

  * •

Demonstration of the developed AREX system in real-world applications,
showcases its effectiveness in several scenarios.

The rest of this paper is organised as follows. Section II will overview the
system setup and methodologies, followed by the experimental results and
discussions given in Sections III. Then the conclusions are given in Section
IV.

##  II Methodologies

###  II-A Robot Design

####  II-A1 Hardware Design

AREX features a frame design that prioritises strength, durability and ease of
assembly. Rigid bodywork is made from carbon fibre with a density of 0.00153
$mm^{3}/g$, resulting in a lightweight 250g frame. The diagonal engine
wheelbase is 380mm, powered by a 4s 30C 4000mah battery. The platform features
four SUNNYSKY X-2216 II KV880 brushless DC motors with APC 9045 two-blade
propellers, controlled by an XF 35A 4in1 electronic speed controller. For
autopilot functions, the Pixhack 6c mini provides attitude and thrust control.
The AREX measures 500x500x220mm, weighs 1.9kg and has an endurance of 10
minutes.

The schematic in Fig.2(b) illustrates AREX’s configuration. The Pixhack 6c
Mini Flight Controller communicates with the 4in1 Electronic Speed Controller
(ESC) using the Dshot600 protocol, while also connecting to the on-board
computer via a UART. This allows IMU data to be received from the onboard
computer and desired attitude and throttle commands to be received from the
flight plan. The sensor setup, shown in Fig.2, includes a LIVOX MID-360 mixed
LiDAR with a 360° horizontal and 59° vertical field of view. At the front, a
RealSense D430 depth camera operates at 10Hz for the LiDAR and 30Hz for the
camera. The Pixhack flight controller outputs 9-axis IMU data at 200Hz.

Figure 3: AREX: Flight System Designed for High Durability, Multi-Scenario
Exploration, and Environmental Modeling.

####  II-A2 Software Design

The software architecture of AREX, shown in Fig.3, consists of several key
modules. In the Robot Odometry module, data from LiDAR odometry or visual
odometry is used to estimate the 6-axis Degree of Freedom (DOF) positional
attitude of AREX. The resulting position and point cloud data are used in the
exploration module to maintain an octomap representing the exploration state
of the environment. This module uses RRT to identify a series of boundary
points in the unknown region of the Octomap. The directional RRT exploration
proposed in this paper determines the final exploration target point. This
information is then fed into the motion planning module which, using a PD
controller, calculates the desired attitude and throttle for AREX based on the
path points. Finally, the calculated commands are sent to the flight
controller. In cases where the stop strategy is triggered, AREX returns
autonomously to the starting point and lands or remains in place.

###  II-B Robot odometry

####  II-B1 Visual odometry

VINS-Fusion[16] is used for visual odometry, and the loss function is
constructed in the formula below:

$\displaystyle\min_{\mathcal{X}}\left\\{\underbrace{\|\mathbf{r}_{p}-\mathbf{H}_{p}\mathcal{X}\|^{2}}_{\text{prior
factor}}+\underbrace{\sum_{k\in\mathcal{B}}\left\|\mathbf{r}_{\mathcal{B}}(\hat{\mathbf{z}}_{b_{k+1}}^{b_{k}},\mathcal{X})\right\|_{\mathbf{P}_{b_{k+1}}^{b_{k}}}^{2}}_{\text{IMU
propagation factor}}\right.$ (1)
$\displaystyle\left.+\underbrace{\sum_{(l,j)\in\mathcal{C}}\rho(\|\mathbf{r}_{\mathcal{C}}(\hat{\mathbf{z}}_{l}^{c_{j}},\mathcal{X})\|_{\mathbf{P}_{l}^{c_{j}}}^{2})}_{\text{vision
factor}}\right\\}$

where the first item is the priority after the marginalization, the second
item is the IMU residual, and the third item is the visual residual. Because
of the complex design, this system is very robust. So we combine it with
improved FAST-LIO for better odometry. A graph is shown in Fig. 4 to
illustrate the framework of VINS-Fusion.

Figure 4: A graphic illustration of the VINS-Fusion framework. If the latest
keyframe comes, it will be kept, and the visual and IMU measurements of the
oldest frame will be marginalized. The prior factor of the loss function is
obtained from marginalization. We can get the IMU propogation factor from IMU
pre-integration. By computing the reprojection error between two keyframes, we
can get the vision factor. Figure 5: System overview of improved FAST-LIO,
which can output high-frequency odometry.

####  II-B2 LiDAR odometry

FAST-LIO[17] is used for LiDAR odometry, error-state iterated Kalman filter
(ESIKF) is used to update the state of the system. The overview of improved
FAST-LIO is shown in Fig. 5. The linearized update formula of the error-state
variables in FAST-LIO is

${\widetilde{\mathbf{x}}}_{i+1}{\simeq}\mathbf{F}_{\widetilde{\mathbf{x}}}\widetilde{\mathbf{x}}_{i}+\mathbf{F}_{\mathbf{w}}\mathbf{w}_{i}$
(2)

where the matrix $\mathbf{F}_{\widetilde{\mathbf{x}}}$ and
$\mathbf{F}_{\mathbf{w}}$ in (2) is computed in (3).

$\displaystyle\mathbf{F}_{\widetilde{\mathbf{x}}}$
$\displaystyle=\begin{pmatrix}\mathbf{Exp}(-(\omega_{\mathbf{m}}-\mathbf{\hat{\mathbf{b}}}_{\omega})\Delta
t)&0&0&-\mathbf{A}((\omega_{\mathbf{m}}-\mathbf{\hat{\mathbf{b}}}_{\omega})\Delta
t)^{\mathbf{T}}\Delta t&0&0\\\ 0&\mathbf{I}&\mathbf{I}\Delta t&0&0&0\\\
-^{G}\mathbf{\hat{\mathbf{R}}}_{I_{i}}(\mathbf{a_{\mathbf{m}}}-\mathbf{\hat{\mathbf{b}}}_{\mathbf{a}})^{\wedge}\Delta
t&0&\mathbf{I}&0&-^{G}\widehat{\mathbf{R}}_{I_{i}}\Delta t&\mathbf{I}\Delta
t\\\ 0&0&0&\mathbf{I}&0&0\\\ 0&0&0&0&\mathbf{I}&0\\\
0&0&0&0&0&\mathbf{I}\end{pmatrix}$ (3)
$\displaystyle\approx\begin{pmatrix}\mathbf{I}&0&0&{\bf{I}}\Delta t&0&0\\\
0&\mathbf{I}&\mathbf{I}\Delta t&0&0&0\\\
-^{G}\mathbf{\hat{\mathbf{R}}}_{I_{i}}(\mathbf{a_{\mathbf{m}}}-\mathbf{\hat{\mathbf{b}}}_{\mathbf{a}})^{\wedge}\Delta
t&0&\mathbf{I}&0&-^{G}\widehat{\mathbf{R}}_{I_{i}}\Delta t&\mathbf{I}\Delta
t\\\ 0&0&0&\mathbf{I}&0&0\\\ 0&0&0&0&\mathbf{I}&0\\\
0&0&0&0&0&\mathbf{I}\end{pmatrix}$ $\displaystyle\bf{F_{w}}$
$\displaystyle=\begin{pmatrix}-\mathbf{A}((\omega_{\mathbf{m}}-\mathbf{\hat{b}}_{\omega})\Delta
t)^{\mathbf{T}}\Delta t&0&0&0\\\ 0&0&0&0\\\
0&-^{G}\mathbf{\hat{\mathbf{R}}}_{I_{i}}\Delta t&0&0\\\ 0&0&\mathbf{I}\Delta
t&0\\\ 0&0&0&\mathbf{I}\Delta t\\\ 0&0&0&0\end{pmatrix}$
$\displaystyle\approx\begin{pmatrix}-\bf{I}^{\mathbf{T}}\Delta t&0&0&0\\\
0&0&0&0\\\ 0&-^{G}\mathbf{\hat{\mathbf{R}}}_{I_{i}}\Delta t&0&0\\\
0&0&\mathbf{I}\Delta t&0\\\ 0&0&0&\mathbf{I}\Delta t\\\ 0&0&0&0\end{pmatrix}$

We can get new state variables through forward propagation, which is used to
compensate for the motion distortion of the LiDAR in backward propagation, the
calculation formula is shown below:

${}^{L_{k}}\mathbf{p}_{f_{j}}={}^{I}\mathbf{T}_{L}^{-1}{{}^{I_{k}}}\mathbf{\check{T}}_{I_{j}}{}^{I}\mathbf{T}_{L}{}^{L_{j}}\mathbf{p}_{f_{j}}$
(4)

This LIO algorithm can quickly and robustly output LiDAR odometry, but the
frequency of the odometry it outputs is only 10hz, which is too low for robots
that need to obtain pose information in real-time. A high-frequency LiDAR
inertial odometer is used here to achieve the frequency required by robot,
whose frequency of odometry can reach 200hz. Whenever the ESKF is updated with
a frame of odometry, this odometry will be recorded, and the newly incoming
IMU measurement data will be integrated based on this optimized odometry. The
calculation is shown in the following formulas. When a new frame of IMU data
$\boldsymbol{a}_{m}$ arrives:

$\displaystyle\boldsymbol{a}_{c}=-\frac{\boldsymbol{a}_{m}}{\|\boldsymbol{a}_{m}\|}\cdot
G_{m}$ (5)

where $\boldsymbol{a}_{m}$ represents the acceleration measurement of IMU,
$\boldsymbol{a}_{c}$ represents the input acceleration of current time,
$G_{m}$ represents the preset gravity constant, which is a scalar.

Since we record the optimized pose output by the system, we have:

$\displaystyle\boldsymbol{a}_{0}=\boldsymbol{R}_{i}({\boldsymbol{a}_{p}}-\boldsymbol{b}_{a})-\boldsymbol{g}$
(6)

where $\boldsymbol{a}_{p}$ represents the input acceleration of previous time,
$\boldsymbol{R}_{i}$ is the previous pose, $\boldsymbol{b}_{a}$ is the bias of
acceleration, $\boldsymbol{g}$ is the estimated gravity in odonetry of FAST-
LIO. Then using median angular velocity to update the rotation matrix:

$\displaystyle\boldsymbol{\omega}$
$\displaystyle=\frac{\boldsymbol{\omega}_{0}+\boldsymbol{\omega}_{1}}{2}$ (7)
$\displaystyle\boldsymbol{R}_{i+1}$
$\displaystyle=\boldsymbol{R}_{i}\textbf{Exp}(\boldsymbol{\omega}\Delta t)$

where $\boldsymbol{\omega}_{0}$ is the previous angular velocity measurement
of IMU, $\boldsymbol{\omega}_{1}$ is the current angular velocity measurement
of IMU. Then transfer the acceleration to the world coordinate and calculate
the median value:

$\displaystyle\boldsymbol{a}$
$\displaystyle=\frac{\boldsymbol{a}_{0}+\boldsymbol{a}_{1}}{2}$ (8)

Then the position and linear velocity can be updated as follows:

$\displaystyle\boldsymbol{p}_{i+1}$
$\displaystyle=\boldsymbol{p}_{i}+v_{i}\Delta
t+\frac{1}{2}\boldsymbol{a}\Delta t^{2}$ (9)
$\displaystyle\boldsymbol{v}_{i+1}$
$\displaystyle=\boldsymbol{v}_{i}+\boldsymbol{a}\Delta t$

###  II-C Robot motion planning

####  II-C1 Environment Representation

The motion planning map is a localised raster map composed of radar point
cloud frames represented by a one-dimensional array. The value of each array
element indicates the occupancy state of the corresponding grid, with 0 for
free space and 1 for obstacles. The map has default dimensions of $L,W,H$ and
a grid size of $size_{grid}$, resulting in an array size of array_size. The
calculation for array_size is given by

$\displaystyle\textit{array\\_size}=\frac{L\cdot{W}\cdot{H}}{size_{grid}^{3}}$
(10)

The index value of each grid can be obtained by the Eq.LABEL:eq:_calculate_id

$\displaystyle
Id_{i}=h_{i}\cdot{num_{w}}\cdot{num_{l}}+w_{i}\cdot{num_{l}}+l_{i}$ (11)

where $h_{i}$, $w_{i}$, $l_{i}$ represent the indices of layers in three
directions of $grid_{i}$, $num_{w}$ denotes the number of grids in the width
direction, and $num_{l}$ is similar to $num_{w}$.

On receipt of a point cloud frame, the 2D array values representing local map
obstacle locations are set to zero. Each spatial point in the point cloud
frame calculates the corresponding index value and assigns the value 1 to the
corresponding position in the array. Spatial points outside the specified map
area are discarded. The layer indexes of the raster in which the spatial
points are located are as follows:

$\displaystyle w_{i}$
$\displaystyle=\lfloor\frac{P_{i}.x}{size_{grid}}\rfloor+\frac{num_{w}}{2}$
(12) $\displaystyle l_{i}$
$\displaystyle=\lfloor\frac{P_{i}.y}{size_{grid}}\rfloor+\frac{num_{l}}{2}$
$\displaystyle h_{i}$
$\displaystyle=\lfloor\frac{P_{i}.z}{size_{grid}}\rfloor+\frac{num_{h}}{2}$

To improve the feasibility of the motion planning path, obstacles are expanded
by applying a preset expansion coefficient to each point in the point cloud
frame, generating an expanded point set. The corresponding array positions are
then assigned a value of 1 based on the spatial locations of the points in
this set. The point set expression formula is as follows:

T (13) $\displaystyle a,b,c\in[0,n_{step}]$ $\displaystyle
n_{step}=\lceil\frac{\lambda_{inflat}}{size_{grid}}\rceil$

####  II-C2 Local Motion Planner

Our work follows EGO-planner. [18], a optimization-based framework for robot
motion planning.

Collision-Free Trajectory Generation: By given a motion goal, the motion
planning module generates an initial B-spline path $\boldsymbol{\Phi}$ that
does not take collisions into account. The start and end points of the path
are the robot’s position and the goal, respectively. Then the control point
$Q_{i}$, which exists in the obstacle, finds the anchor point $p_{i}$ at the
obstacle surface for the control point that exists inside the obstacle. Then
the obstacle distance from $Q_{i}$ to the obstacle is defined as

$\displaystyle d_{i}=(\mathbf{Q}_{i}-\mathbf{p}_{ij})\cdot\mathbf{v}_{i}$ (14)

A collision-free path is obtained by optimizing the position of $Q_{i}$ such
that $d_{i}$ $>$ 0.

Grediant-based Trajectory Optimization: The cost function of the trajectory
optimization is:

$\begin{matrix}minJ=\lambda_{s}J_{s}+\lambda_{c}J_{c}+\lambda_{d}J_{d},\\\
\end{matrix}$ (15)

where $J_{s}$ is the smoothness penalty, $J_{c}$ is for collision, and $J_{d}$
indicates feasibility. $\lambda_{s}$, $\lambda_{c}$, $\lambda_{d}$ are weights
for each penalty terms. We use a uniform B-spline, which means that for each
control point $\mathbf{Q}_{i}\in\mathbb{R}^{3}$, they have the same time
interval from the latter control point, i.e. $\triangle t=t_{i+1}-t_{i}$. Thus
the velocity $\mathbf{V}_{i}$, acceleration $\mathbf{A}_{i}$, and jerk
$\mathbf{J}_{i}$ at each control point are obtained by

$\begin{matrix}\mathbf{V}_{i}=\frac{\mathbf{Q}_{i+1}-\mathbf{Q}_{i}}{\triangle
t},\mathbf{A}_{i}=\frac{\mathbf{V}_{i+1}-\mathbf{V}_{i}}{\triangle
t},\mathbf{J}_{i}=\frac{\mathbf{A}_{i+1}-\mathbf{A}_{i}}{\triangle
t}.\end{matrix}$ (16)

For the smoothing term penalty, we examine the squares of the second-order and
third-order derivatives of the control points concerning $\triangle t$ each.
The second and third-order derivatives of the B-spline curve are reduced by
minimizing the second and third-order derivatives of the control points for
the node vector $\triangle t$ using the convex envelope property of the
B-spline. This smoothness penalty is defined as follows, considering a total
of $n$ control points on the B-spline:

$\displaystyle
J_{s}=\sum_{i=1}^{n-1}\|\mathbf{A}_{i}\|^{2}+\sum_{i=1}^{n-2}\|\mathbf{J}_{i}\|^{2}$
(17)

For the collision penalty, we set a safe distance $S_{f}$ and satisfy
$d_{i}<d_{s}$ by the penalty requirement function. The collision penalty
function is as follows:

$\displaystyle j_{c}(i)$ $\displaystyle=\begin{cases}0&(c_{i}\leq 0)\\\
c_{i}^{3}&(0<c_{i}\leq s_{f})\\\
3s_{f}c_{i}^{2}-3s_{f}^{2}c_{i}+s_{f}^{3}&(c_{i}>s_{f})\end{cases}$ (18)
$\displaystyle where\quad c_{i}$ $\displaystyle=s_{f}-d_{i},$

where $d_{ij}$ comes froms the Eq.14. Hence, the total collision penalties
across the entire path result from the summation of penalties associated with
individual control points $\mathbf{Q}_{i}$. The formula can be expressed as
follows:

$\displaystyle J_{c}=\sum_{i=1}^{n}j_{c}(\mathbf{Q}_{i}).$ (19)

To guarantee feasibility in the context of the Feasibility penalty, higher-
order derivatives of each control in the x, y, and z dimensions are
constrained to values below a predefined kinetic limit. The penalty function
is articulated as follows:

$\displaystyle
J_{d}=\sum_{i=1}^{n}w_{v}F(\mathbf{V}_{i})+\sum_{i=1}^{n-1}w_{a}F(\mathbf{A}_{i})+\sum_{i=1}^{n-2}w_{j}F(\mathbf{J}_{i})$
(20)

$w_{v},w_{a},$ and $w_{j}$ represent the weights assigned to different higher-
order derivatives for each control point. Meanwhile, the definition of
$F(\cdot)$ is as follows:

$\displaystyle F(\mathbf{C})=\sum_{r=x,y,z}f(c_{r})$ (21)

$\displaystyle
f(c_{r})=\begin{cases}a_{1}c_{r}^{2}+b_{1}c_{r}+c_{1}&(c_{r}\leq-c_{j})\\\
(-\lambda c_{m}-c_{r})^{3}&(-c_{j}<c_{r}<-\lambda c_{m})\\\ 0&(-\lambda
c_{m}\leq c_{r}\leq\lambda c_{m})\\\ (c_{r}-\lambda c_{m})^{3}&(\lambda
c_{m}<c_{r}<c_{j})\\\ a_{2}c_{r}^{2}+b_{2}c_{r}+c_{2}&(c_{r}\geq
c_{j})\end{cases}$ (22)

where
$c_{r}\in\mathbf{C}\in\\{\mathbf{V}_{i},\mathbf{A}_{i},\mathbf{J}_{i}\\},a_{1},b_{1},c_{1},a_{2},b_{2},c_{2}$
satisfy second-order continuity. $c_{m}$ is the derivative limit, and $c_{j}$
represents the intersection points between the quadratic and cubic intervals.
For a given condition where $\lambda<1-\epsilon$ and $\epsilon\ll 1$, the
objective is to ensure the structure adheres to the imposed constraint.

###  II-D Robot Exploration Module

####  II-D1 Environmental Modelling

By maintaining the collection of undistorted LiDAR feature points, a high-
precision global point cloud map is composed. This process is outlined by Eq.
23. ${}^{Lk}\mathbf{p}_{f_{j}}$ represents the undistorted LiDAR feature
points in the LiDAR coordinate obtained through 4, ${}^{I}\mathbf{T}_{L}$
denotes the transformation relationship from the LiDAR coordinate to the IMU
coordinate, and ${}^{G}\mathbf{T}_{I_{k}}$ signifies the system state
corresponding to the LiDAR frame.

${}^{G}\bar{\mathbf{p}}_{f_{j}}={}^{G}\bar{\mathbf{T}}_{I_{k}}^{I}{\mathbf{T}}_{L}{}^{L}{}^{k}{\mathbf{p}}_{f_{j}};j=1,\cdots,m.$
(23)

A 2D occupancy map is constructed to represent the known and unknown regions
in the scene, where each raster has only three values: -1, 0, and 1 for the
unknown, idle, and occupied states, respectively. When using the RRT-based
boundary point detector, by querying whether the grid on the tree growth line
is the unknown state value -1, we can determine whether to find the boundary
point of the unknown region.

Figure 6: Demostration of RRT exploration strategy, case A: Candidate vertexs
close to an obstacle will not be considered, case B: Candidate vertexs close
to a known area will not be considered, case C: Candidate vertex far away from
the exploration direction will not be considered.

The occupancy state of the occupied map is updated by LiDAR point cloud frames
in global coordinates, and we select the point clouds with height values of
0-2m in the point cloud frames in global coordinates to represent the state of
the raster. A grid is considered occupied when a point cloud exists in the
grid, while a grid is considered idle when the occupied grid is connected to
the robot’s position and the line passes through it. As the Explorer moves,
the LiDAR point cloud frames change with the environment, and the occupancy
map is updated by aggregating the odometer information.

####  II-D2 Direction-Aware RRT Exploration

Algorithm 1 demonstrates the Direction-Aware exploration based on RRT. The
following are the relevant definitions:

  * •

$\mathbf{R}$ represents the data frames from the LiDAR.

  * •

$\mathbf{O}$ represents the odometry information.

  * •

$\mathbf{M}$ represents the grid map.

  * •

$\mathbf{CGs}$ represents the frontier points.

  * •

$\mathbf{T_{t}}$ represents the expected exploration goal at time t.

  * •

$\mathbf{P_{s}}$ represents the the smoothed path.

  * •

$\mathbf{E_{x}}$ represents the flag for executing exploration

The four key nodes shown in Alg.1 are described below:

  * •

$\mathbf{OctomapServer}$: accepts radar data frame information and odometer
information for constructing a 2D occupancy map representing the scene
exploration.

  * •

$\mathbf{FrontierDetector}$: accepts the 2D occupancy map and odometer
information constructed by Octomap Server and searches for boundary points of
unexplored environment by RRT and outputs a list of candidate target points.

  * •

$\mathbf{RevenueCalculator}$: accepts the 2D occupancy map, odometer
information, and candidate target points, calculates the value of the utility
function of the candidate target points, and outputs the target point with the
highest score.

  * •

$\mathbf{PathPlanner}$: accepts target points, radar data frames, and odometer
information to plan a collision-free smooth path for the robot.

Data: $\mathbf{R}$, $\mathbf{O}$, $\mathbf{E_{x}}\leftarrow\text{True}$

Result: High-quality point cloud map

while  _$\mathbf{E_{x}}$ =True_ do

$\mathbf{M}\leftarrow\text{Octomap\\_Server}(\mathbf{R},\mathbf{O})$;

$\mathbf{CGs}\leftarrow\text{Frontier\\_Detector}(\mathbf{M},\mathbf{O})$;

if  _$\mathbf{CGs}\neq\mathbf{\emptyset}$_ then

$\mathbf{T_{t}}\leftarrow\text{Revenue\\_Calculator}(\mathbf{CGs},\mathbf{O},\mathbf{M})$;

$\mathbf{P_{s}}\leftarrow\text{Path\\_Planner}(\mathbf{T},\mathbf{O})$;

else

$\mathbf{E_{x}}\leftarrow\text{False}$

end if

end while

Algorithm 1 Direction-Aware RRT exploration

####  II-D3 Evaluation Strategy

The exploration strategy in this work evaluates candidate observation
positions to find the optimal frontier vertex. This strategic approach aims to
shorten the exploration time, reduce the overall step size, and ultimately
increase efficiency. Our strategy takes into account three key factors: the
distance of the robot to the observation position, the expected information
gain, and the correlation with the direction of the last exploration target.
Fig.6 visually demonstrates our exploration strategy.

$\displaystyle R(CG_{i})$ $\displaystyle=\lambda_{I}\cdot
f_{i}^{I}-\lambda_{N}\cdot f_{i}^{N}$ (24) $\displaystyle CG_{i}$
$\displaystyle=\text{Arg}\max_{CG_{i}\in CGs}\left(R(CG_{i})\right)$

In the explored method[19], the robot chooses the nearest, accessible and
unvisited border with the largest grid size as its goal. The choice of the
desired border is made by maximising the utility function 24, where
$f_{i}^{I}$ and $f_{i}^{N}$ represent the grid size of the border area and the
spatial distance between the robot and the border node, respectively.
$\lambda_{I}$ and $\lambda_{N}$ are weighting parameters associated with these
two terms. Importantly, the utility function reaches its maximum value when
the frontier size is large and the distance is small. This optimisation allows
the robot to navigate efficiently along the shortest obstacle-free path from
its current cell to the cell containing the map coordinate. As emphasised in
[20], the consistent movement towards new frontiers allows the robot to extend
its map into unexplored areas until the entire environment is covered.

In unstructured environments, the existing boundary selection method may
become inefficient because robots tend to prioritise boundary points with high
local information returns. As a result, the robot may be attracted to these
points, disregarding the continuity of environmental information in the
current direction of exploration. This leads to the robot revisiting
previously explored locations when moving towards points with lower
information returns. To address this inefficiency, this paper improves the
exploration strategy by incorporating a term influenced by the direction of
the exploration target point into the utility function for profit calculation.
The improved utility function $R_{d}(CG_{i})$ is expressed as follows

$\displaystyle R_{d}(CG_{i})$ $\displaystyle=\lambda_{I}\cdot
f_{i}^{I}-\lambda_{N}\cdot f_{i}^{N}-f_{i}^{D}$ (25) $\displaystyle f_{i}^{D}$
$\displaystyle={e}^{\lambda_{D}\cdot A}$

where $f_{i}^{I}$, $f_{i}^{N}$ are defined the same as Eq. 24. $f_{i}^{D}$ is
an exponential function of $A$. $A$ is the angle between the vectors
$\overrightarrow{T_{t-2}T_{t-1}}$ and $\overrightarrow{T_{t-1}CG_{i}}$.
Similarly, $\lambda_{I}$, $\lambda_{N}$, and $\lambda_{D}$ are user-defined
weightings for the size, distance and exploration direction.

####  II-D4 Stop Cretria

The termination criterion for exploration is a critical aspect of the
exploration process described above. In practical scenarios, it is often
unrealistic to set a specific percentage of exploration coverage in a given
area as the termination point[21]. For flying robots, efficient management of
their power supply is essential due to energy constraints. It is therefore
necessary to consider stopping the exploration mission either when a
particular area is completed or when the exploration yield becomes relatively
low. This stopping strategy is implemented to ensure that the robot can save
sufficient power for a safe return. The exploration termination strategies
used in this work, consist of the following two criteria:

  * •

No further candidate exploration target points are discovered.

  * •

The unknown area of the candidate region is below a preset threshold.

These two criteria exist side by side, and as long as either of these
conditions is met, the exploration mission stops and the robot will return to
the starting point.

##  III Experiments and discussion

###  III-A Experiment setups

In real-world scenarios, we conducted experiments to validate the
effectiveness of our work using the physical platform depicted in Fig. 2. Our
algorithm functions within the ROS Noetic operating system. We employ a method
utilizing a PD controller to steer the robot along the planned path at a
frequency of 100 Hz. Simultaneously, it detects potential collisions along the
path at a rate of 20 Hz, triggering a rerouting of the current trajectory in
the event of a collision. The global map resolution is configured at 0.1
meters, while the dimensions of the local sensing map for path planning are
set to 30m x 30m x 3m. Additionally, the obstacle point cloud’s expansion
radius is set to 0.5 meters. Notably, the starting point is established as the
map’s origin, denoted as $x_{\text{start}}=[0,0]^{T}$. The experimental setup
consists of two different scenes: a regularly maintained forest and an
underground parking lot.

###  III-B Evaluation on subsystems

####  III-B1 Comparison of Visual and LiDAR Odometry

In this section, we evaluate the performance of visual and LiDAR odometry in
real-world environments, as shown in Figure 7. In this experiment, we utilized
the robot kit illustrated in Fig 2 (a) to conduct a comparative analysis
between the visual and radar odometry systems. Our paper implements the
improved FAST-LIO as the robot’s primary odometry method, concurrently running
VINS-Fusion. Post-initialization, our motion planner, operated via Nomechine
software’s remote desktop, orchestrated the robot’s autonomous flight,
adhering to six pre-set waypoints. Notably, the sixth waypoint serves as the
starting point $x_{\text{start}}=[0,0]^{T}$. The outcomes are depicted in Fig.
7.

Figure 7: Comparison of Visual and LiDAR Odometry (a) Completion of Odometry
Initialization (b) Comparison of Global Paths

From Fig. 7(a), the completion of initialization showcases an excellent
alignment between the FAST-LIO and VINS-Fusion odometry. However, upon
completing the mission involving six waypoints, Fig. 7(b) distinctly
illustrates a considerable shift in the VINS-Fusion odometry. In contrast, the
LiDAR odometry remains stable, showing no significant deviation.

Figure 8: Effects of Different Parameters on Motion Planning. (a) Single-frame
LiDAR point cloud expansion grid map. (b) Single-frame LiDAR raw point cloud.
(c) Inflation grid map corresponding to the merged point cloud. (d) Merged raw
point cloud. (e) Obstacle avoidance demonstration with 0.1 inflation
coefficient. (g) Obstacle avoidance with a 0.5 inflation coefficient. (f), (h)
The obstacle avoidance paths of (e), and (g) in the raw point cloud. (i) robot
proximity to obstacle point cloud. (j) robot within the inflated obstacle
point cloud.

####  III-B2 Evaluation on Robot Motion planning

We validate the utilised motion planning methods in the wild environments. In
our experiments, we observed that the single-frame LiDAR point cloud output
from the MID-360 tends to exhibit sparsity, potentially leading to certain
smaller obstacles being unnoticed within the point cloud data. To address
this, we amalgamated the multi-frame LiDAR point cloud data with that of the
single-frame camera, presenting a comparative analysis in Fig. 8(a), (b), (c),
(d). Observing 8(a) and (b), it’s evident that the absence of an obstacle
point cloud leads to an inadequate grid map representation, consequently
rendering the planned path infeasible. However, through the fusion of 5-frame
LiDAR point cloud data with single-frame camera data, depicted in Figs. 8(c)
and (d), we effectively enhance our ability to perceive obstacles. The fusion
of multiple sensors and frames of point cloud data addresses the challenge of
perceiving smaller obstacles, enabling the motion planning process to generate
feasible paths.

The motion planning for obstacle avoidance is based on optimizing paths that
avoid inflated obstacles. Consequently, the choice of expansion coefficient
size significantly impacts the success rate of obstacle avoidance. In Fig.
8(e),(f),(g),(h), we showcase various obstacle avoidance paths for the same
scene, each utilizing different expansion coefficients. In Fig. 8(e) and (f),
the depicted obstacle avoidance paths utilize an expansion factor of 0.1. From
Fig. 8(e), it’s noticeable that while these paths circumvent the expanding
obstacles, they often appear excessively close to the obstacle point clouds in
the original point cloud maps. Consequently, this proximity can potentially
result in collisions due to the robot’s size or biases within the point clouds
during actual flight.

Contrastingly, in Fig. 8(g) and (h) where the paths incorporate an expansion
coefficient of 0.5, Fig. 8(h) distinctly illustrates how an increased
expansion coefficient effectively maintains a safer distance between the
avoidance paths and the obstacles. This augmentation notably enhances the
navigability and safety of the paths. However, the expansion coefficient is
not the bigger the better, too high expansion coefficient will cause the on-
board computer to mistakenly think that it is in the obstacle and stop
planning the path, such as Fig.8(i), (j) demonstrates the on-board computer’s
misjudgment in the case of expansion coefficient of 0.75.

###  III-C Field Experiments

To verify the feasibility and robustness of the proposed system, we conducted
exploratory experiments in two different scenarios.

####  III-C1 Scene 1

The first scenario was conducted in a forest located at South China
Agricultural University in Guangzhou, Guangdong, China. The exploration
process is shown in Fig. 9. According to the distribution range of the forest,
we set the exploration boundaries centred on the starting point, with the
farthest front/back point being 25m, and the farthest left/right point being
20m. We start the on-board computer through the remote desktop function of
Nomechine to make the robot perform the autonomous exploration task. During
the whole exploration process, the exploration module releases a total of six
exploration target locations as shown in Fig. 9(g), which are provided with
odometer information by the improved FAST-LIO in this paper, while the motion
planning module used in this paper is responsible for the local path planning
and optimization. It is worth noting that the sixth exploration target point
is the starting point, which is due to the stopping strategy triggered by the
exploration module, so the coordinates of the starting point are released as
the last target point so that the robot will return to the flight path and
land on its own to complete the exploration mission. A semantic processing o
point cloud map based on our previous work[22], which can process object
detection on point cloud in Bird-Eye-View (BEV) is utilised here to perform
scene understanding in world environments, as shown in Fig. 9 (b).

Figure 9: Instances of an autonomous exploration mission within the forest.
(a) The exploration results and on-site flight demonstration in the forest.
(b) Forest semantic map based on exploration results Figure 10: Presentation
of the Underground Parking Garage Exploration Process. (a) The exploration
results and on-site flight demonstration in the underground parking garage.
(b) Display of the Global Point Cloud Map in the Underground Parking Garage.

####  III-C2 Scene 2

The second scene took place in the underground parking garage of South China
Agricultural University in Guangzhou, Guangdong, China, as depicted in Fig. 10
(a). Utilizing the garage entrance as our starting point, we established an
exploration boundary extending 100 meters along the x-axis and 50 meters along
the y-axis from the starting point. Given the initial point’s orientation
towards a 30-degree downhill slope, point cloud data ranging from -5.0 to -10
meters in the z-axis direction was selected as the source for the 2D Octomap
map. To facilitate autonomous exploration, the onboard computer was activated
using Nomechine’s remote desktop function, enabling the robot to execute
exploration tasks. The actual exploration route is depicted in Fig. 10 (a),
while the exploration results are illustrated in 10 (b). It’s important to
note that due to insufficient remaining battery power for the robot to return
to the starting point, remote commands were dispatched to initiate an
autonomous landing upon completing the exploration mission.

###  III-D Failure Analysis

####  III-D1 Failure on Robot Odometry

In our experiments, odometer failure primarily occurs in two scenarios: (1)
When the fuselage lacks sufficient structural strength, the flight control IMU
(Inertial Measurement Unit) receives mechanical vibrations from the motor’s
rotation. Consequently, the flight control system adjusts the motor based on
the IMU waveform data, leading to resonance with the motor-transmitted
vibration. (2) Odometer tracking failure arises during high-speed robot
motion, especially when the robot undergoes rapid YAW angle changes. During
exploration missions, when the target point significantly deviates from the
robot’s current orientation, the PD controller principle prompts the robot to
perform significant spins for orientation adjustment, disabling the odometer.
To mitigate this issue, the direction-focused exploration strategy proposed in
this paper circumvents such situations.

####  III-D2 Failure on Motion Planning

This failure manifests in two scenarios:

  * •

Being entrapped within an obstacle group causes program judgment, leading to
collision and subsequent planning failure. This behaviour stems from
environmental perception inaccuracies due to LiDAR point cloud sparsity and
measurement errors. Notably, the obstacle point cloud’s inconsistency,
especially at object edges, causes sporadic jumps, resulting in the robot
colliding with the obstacle cluster.

  * •

Another prevalent failure involves obstacle avoidance. While achieving
collision-free trajectories entails bypassing expanded obstacles in flight,
determining an appropriate expansion coefficient in proportion to the airframe
size is crucial. Excessively high expansion coefficients exacerbate the point
cloud’s jumping phenomenon, leading to severe consequences.

Both issues stem from the inherent lack of accuracy in the employed
environmental perception method. Addressing these challenges necessitates the
development of a more precise environmental perception model.

##  IV Conclusion

This paper describes the design of AREX and its autonomous exploration
capabilities. The system is equipped with robust localisation, mapping and
efficient exploration target selection capabilities. In particular, it
prioritises continuity in exploration direction and minimises abrupt changes
to increase efficiency and mitigate odometry errors. The global point cloud
map generated by the exploration serves as a valuable resource for extracting
semantic information about the environment. In our experiments, the real-time,
high-precision environmental perception module proved to be crucial. The
accuracy of environmental perception significantly influences the
identification of exploration boundaries and the effectiveness of obstacle
avoidance. Future efforts will focus on developing more efficient and accurate
methods for perceiving and representing the environment, as well as exploring
robust path-planning approaches.

## References

  * [1] M. Grieves, “Origins of the digital twin concept,” _Florida Institute of Technology_ , vol. 8, 2016.
  * [2] IBM. (2022) What is a Digital Twin. [Online]. Available: https://www.ibm.com/topics/what-is-a-digital-twin
  * [3] G. M. Bisanti _et al._ , “Digital twins for aircraft maintenance and operation: A systematic literature review and an iot-enabled modular architecture,” _Internet of Things_ , vol. 24, p. 100991, 2023.
  * [4] K. Hu, Y. Wei, Y. Pan, H. Kang, and C. Chen, “High-fidelity 3d reconstruction of plants using neural radiance field,” _arXiv preprint arXiv:2311.04154_ , 2023.
  * [5] H. Kang and C. Chen, “Fast implementation of real-time fruit detection in apple orchards using deep learning,” _Computers and Electronics in Agriculture_ , vol. 168, p. 105108, 2020.
  * [6] H. Kang, H. Zhou, and C. Chen, “Visual perception and modeling for autonomous apple harvesting,” _IEEE Access_ , vol. 8, pp. 62 151–62 163, 2020.
  * [7] T. Liu, H. Kang, and C. Chen, “Orb-livox: A real-time dynamic system for fruit detection and localization,” _Computers and Electronics in Agriculture_ , vol. 209, p. 107834, 2023.
  * [8] Z. Wang, R. Gupta, K. Han, H. Wang, A. Ganlath, N. Ammar, and P. Tiwari, “Mobility digital twin: Concept, architecture, case study, and future challenges,” _IEEE Internet Things J._ , vol. 9, no. 18, p. 17452–17467, 2022. [Online]. Available: http://dx.doi.org/10.1109/JIOT.2022.3156028
  * [9] H. Kang and X. Wang, “Semantic segmentation of fruits on multi-sensor fused data in natural orchards,” _Computers and Electronics in Agriculture_ , vol. 204, p. 107569, 2023.
  * [10] C. Papachristos, F. Mascarich, S. Khattak, T. Dang, and K. Alexis, “Localization uncertainty-aware autonomous exploration and mapping with aerial robots using receding horizon path-planning,” _Autonomous Robots_ , vol. 43, pp. 2131–2161, 2019.
  * [11] S. Molina, G. Cielniak, and T. Duckett, “Robotic exploration for learning human motion patterns,” _IEEE Transactions on Robotics_ , vol. 38, no. 2, pp. 1304–1318, 2021.
  * [12] Z.-W. Hong, T.-Y. Shann, S.-Y. Su, Y.-H. Chang, T.-J. Fu, and C.-Y. Lee, “Diversity-driven exploration strategy for deep reinforcement learning,” _Advances in neural information processing systems_ , vol. 31, 2018.
  * [13] S. Shen, N. Michael, and V. Kumar, “Stochastic differential equation-based exploration algorithm for autonomous indoor 3d exploration with a micro-aerial vehicle,” _International Journal of Robotics Research_ , vol. 31, no. 12, pp. 1431 – 1444, October 2012.
  * [14] M. Naazare, F. G. Rosas, and D. Schulz, “Online next-best-view planner for 3d-exploration and inspection with a mobile manipulator robot,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 2, pp. 3779–3786, 2022.
  * [15] B. Lindqvist, A.-A. Agha-Mohammadi, and G. Nikolakopoulos, “Exploration-rrt: A multi-objective path planning and exploration framework for unknown and unstructured environments,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 3429–3435.
  * [16] T. Qin, S. Cao, J. Pan, P. Li, and S. Shen, “Vins-fusion: An optimization-based multi-sensor state estimator,” 2019.
  * [17] W. Xu and F. Zhang, “Fast-lio: A fast, robust lidar-inertial odometry package by tightly-coupled iterated kalman filter,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 3317–3324, 2021.
  * [18] X. Zhou, Z. Wang, H. Ye, C. Xu, and F. Gao, “Ego-planner: An esdf-free gradient-based local planner for quadrotors,” _IEEE Robotics and Automation Letters_ , vol. 6, no. 2, pp. 478–485, 2020.
  * [19] H. Umari and S. Mukhopadhyay, “Autonomous robotic exploration based on multiple rapidly-exploring randomized trees,” in _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2017, pp. 1396–1402.
  * [20] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in _Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA’97.’Towards New Computational Principles for Robotics and Automation’_. IEEE, 1997, pp. 146–151.
  * [21] G. Amorín, F. Benavides, and E. Grmapin, “A novel stop criterion to support efficient multi-robot mapping,” in _2019 Latin American Robotics Symposium (LARS), 2019 Brazilian Symposium on Robotics (SBR) and 2019 Workshop on Robotics in Education (WRE)_. IEEE, 2019, pp. 369–374.
  * [22] Y. Pan, H. Cao, K. Hu, H. Kang, and X. Wang, “A novel perception and semantic mapping method for robot autonomy in orchards,” _arXiv e-prints_ , pp. arXiv–2308, 2023.