# Advancing Continual Learning for Robust Deepfake Audio Classification

1st Feiyi Dong  University of New South Wales
Sydney, Australia
<EMAIL_ADDRESS>2nd Qingchen Tang  University of New South
Wales
Sydney, Australia
<EMAIL_ADDRESS>3rd Yichen Bai  University of New South
Wales
Sydney, Australia
<EMAIL_ADDRESS>4th Zihan Wang  University of New South Wales
Sydney, Australia
<EMAIL_ADDRESS>
###### Abstract

The emergence of new spoofing attacks poses an increasing challenge to audio
security. Current detection methods often falter when faced with unseen
spoofing attacks. Traditional strategies, such as retraining with new data,
are not always feasible due to extensive storage. This paper introduces a
novel continual learning method Continual Audio Defense Enhancer (CADE).
First, by utilizing a fixed memory size to store randomly selected samples
from previous datasets, our approach conserves resources and adheres to
privacy constraints. Additionally, we also apply two distillation losses in
CADE. By distillation in classifiers, CADE ensures that the student model
closely resembles that of the teacher model. This resemblance helps the model
retain old information while facing unseen data. We further refine our model’s
performance with a novel embedding similarity loss that extends across
multiple depth layers, facilitating superior positive sample alignment.
Experiments conducted on the ASVspoof2019 dataset show that our proposed
method outperforms the baseline methods.

###### Index Terms:

fake audio detection, continual learning, anti-spoofing

##  I Introduction

The rapid development of Text-to-Speech (TTS) and Voice Conversion (VC)
technologies has significantly improved the realism of synthetic audio. This
advancement poses serious threats to social stability and the security of
speaker verification systems, now more vulnerable to sophisticated audio
spoofs.

As fake audio threats grow, the need for effective detection becomes more
urgent. Initiatives like ASVspoof [1, 2, 3] and Audio Deep Synthesis Detection
challenges [4, 5] have driven research in this area. Traditional methods focus
on two strategies: extracting robust acoustic features using signal processing
methods [6, 7, 8] and using effective classifiers, especially neural networks
[9, 10, 11, 12]. These methods, particularly deep neural networks, have made
significant progress in detecting deepfake audios. However, they often fail
against new, unseen spoofing attacks. For example, during the ASVspoof2019
challenge, systems that did well against known attacks struggled with novel
threats, showing a performance gap.

To address the challenge of degraded performance with unseen data, researchers
have explored innovative strategies. One approach involved a model ensemble,
where [13] trained three models jointly, achieving better results than those
trained with mixed data directly. Moreover, while fine-tuning models on new
data can be beneficial, it may lead to a decline in performance on previously
learned spoofing types, a problem known as catastrophic forgetting [14]. These
limitations highlight the need for a more dynamic solution.

Continual learning (CL) offers such a solution, providing a framework for
adaptive learning over time while preserving previously acquired knowledge.
There are two common types of CL: Regularization-based method [15] adds a
special term to the loss function to keep model updates close to old settings.
The replay-based method [16, 17] stores past examples in memory and uses them
during training to prevent forgetting like humans revisiting old information.
The CL methods are crucial for maintaining up-to-date and effective detection
systems across different attack scenarios.

The rapidly evolving capabilities of TTS and VC technologies, alongside the
growth of large language models, make audio anti-spoofing a prime candidate
for continual learning techniques. Despite the urgent need, the application of
continual learning in this field is still limited. Recently the DFWF [18]
method is a pioneering example of using continual learning for deepfake audio
detection. While DFWF employs the distillation [19] from the existing models
to new models to preserve knowledge, it fully relies on a regularization-based
strategy, its lack of exploration for reuse of a part of previous data
constrains its performance potential. Additionally, there is a significant
lack of comprehensive research applying continual learning strategies broadly
to the task of audio anti-spoofing.

This paper addresses limitations in audio anti-spoofing by introducing the
Continual Audio Defense Enhancer (CADE) which combines regularization-based
and replay-based continual learning methods. CADE uses a fixed memory size to
store random samples from past datasets efficiently. It also includes two
different distillation losses to preserve knowledge from old models while
training new ones, reducing information loss when new spoofing types appear.
Additionally, CADE employs an novel embedding similarity loss across multiple
layers, ensuring better alignment of genuine audio samples. Our experiments on
the ASVspoof2019 dataset show that CADE outperforms existing methods. We
propose a benchmark for future research, providing a foundation for evaluating
several continual learning approaches in audio anti-spoofing.

##  II Proposed Methods

Continual learning (CL) for anti-spoofing involves training a system to
recognize and detect fake audio while continuously updating and improving its
detection capabilities. This means the system learns from new data without
forgetting what it learned from previous data. The goal is to maintain high
performance even when new types of spoofing attacks emerge, ensuring robust
audio security over time.

Figure 1: Method diagram of proposed CADE approach. Specifically, this diagram
illustrates the training process at time $t$ for our novel method. At this
time step, new data from task $t$ and a subset of data from task $t-1$
(selected using a replay strategy) are combined to form the input. This input
is concurrently fed into the model from time $t-1$ (teacher model) for
inference and the model at time $t$ (student model) for training. $L_{c}$
refers to the classification loss. The student model’s training is further
guided by three loss functions: $L_{\text{ad}}$ (Attention Distillation Loss
derived from Grad-CAM), $L_{\text{psa}}$ (Positive Sample Alignment Loss), and
$L_{\text{kd}}$ (Knowledge Distillation Loss), which collectively help the
student model to retain the teacher model’s knowledge.

###  II-A Proposed Continual Audio Defense Enhancer

Our research introduces the Continual Audio Defense Enhancer (CADE), a novel
approach enhancing audio anti-spoofing technology under a continual learning
framework. CADE integrates three significant innovations, each targeting a
specific aspect of the learning process to improve the robustness and efficacy
of the detection system. The first innovation is the implementation of a
replay-based strategy, utilizing a fixed memory size to store randomly
selected samples from previous datasets. This method conserves resources and
adheres to privacy constraints. The second innovation, it incorporates two
types of distillation losses to preserve knowledge: Knowledge Distillation
loss [20] and Attention Distillation loss [21]. The novelty of the attention
distillation loss lies in its use of grad-CAM [22] to generate similar
attention feature maps, which enhances the model’s ability to retain crucial
information from old models while adapting to new spoofing types. Finally, we
enhance our model’s performance with a novel embedding similarity loss that
utilizes multiple depth layers, facilitating superior alignment of genuine
audio samples. The formula representing our model’s architecture is expressed
as follows:

$\text{CADE}=\text{Replay}+L_{c}+\alpha L_{kd}+\beta L_{ad}+\gamma L_{psa}$
(1)

In this formulation, $L_{c}$ denotes the Classification Loss, $L_{kd}$
represents the Knowledge Distillation loss, $L_{ad}$ is the Attention
Distillation Loss, and $L_{psa}$ stands for the Positive Sample Alignment
loss, which utilizes embeddings from multiple depth layers. The coefficients
$\alpha$, $\beta$, and $\gamma$ are hyperparameters that balance the
contribution of each loss component to the overall learning objective. Figure
1 shows the overview of our proposed novel methods. The details of KD loss
$L_{kd}$, AD Loss $L_{ad}$ and PSA loss $L_{psa}$ are explained in the
following subsection.

####  II-A1 Integration of Replay-Based Methods with Fixed Memory Sampling

One of the central innovations of our approach is the incorporation of replay-
based strategies, which have been extensively researched in the context of
continual learning. [23] conducted a comprehensive survey of replay-based
continual learning methods. The replay-based method stores a few old training
samples within a small memory buffer, there are different sampling strategies.
For example, the reservoir Sampling method randomly preserves a fixed number
of old training samples, the ring buffer method further ensures an equal
number of old training samples per class, mean-of-feature method selects an
equal number of old training samples that are closest to the feature mean of
each class. In our research, we adopt a fixed memory size for storing randomly
sampled old data samples, which is crucial for effectively combating
catastrophic forgetting. By revisiting these old samples periodically, the
model retains and refines its knowledge of past spoofing attacks, thereby
maintaining its overall accuracy and robustness.

####  II-A2 Knowledge Distillation Loss

In our study on identifying speech deepfakes, we employ knowledge distillation
loss [20, 24] to align the output probabilities of new data on the current
network with those on the original network. This approach extends the student-
teacher knowledge distillation model, which is prevalently used in speech
recognition. Specifically, the formula is defined by:

$L_{kd}(y,\hat{y})=-\sum_{i=1}^{N}y^{\prime}_{i}\cdot\log\hat{y}^{\prime}_{i}$
(2)

In this expression, $y$ and $\hat{y}$ are the prediction vectors of the models
$M_{t-1}$ and $M_{t}$ respectively, with each vector containing $N$
probability scores. The terms $y^{\prime}_{i}$ and $\hat{y}^{\prime}_{i}$ are
the sigmoid activations $\sigma(y_{i})$ and $\sigma(\hat{y}_{i})$ of the
predictions. This formulation encourages the network to produce a relative
similar probability contributions between the old and the new data.

####  II-A3 Attention Distillation Loss

Attention Distillation loss ($L_{ad}$) [21] is introduced to CADE method. In
our experiments, we use grad-CAM [22] to generate attention feature maps. It
is a visualization technique that identifies which parts of an input are most
important for a neural network’s predictions. The process starts with a
forward pass through the network to obtain the initial predictions. It then
computes the gradients of any target output class with respect to the feature
maps of a chosen convolutional layer. These gradients are globally averaged to
determine the importance of each feature map, creating a set of weights. These
weights are used to generate a weighted sum of the feature map known as
attention feature map. We adapted this method in audio anti-spoofing field,
where $Q_{i,c}^{t-1}$ and $Q_{i,c}^{t}$ denote the vectorized attention maps
for a class $c$ produced by models $M_{t-1}$ and $M_{t}$, respectively:

$Q_{i,c}^{t-1}=\text{vector}(\text{Grad-CAM}(i,M_{t-1},c))$ (3)
$Q_{i,c}^{t}=\text{vector}(\text{Grad-CAM}(i,M_{t},c))$ (4)

The $L_{ad}$ is calculated as the L1 norm of the difference between these
normalized attention maps:

$L_{ad}=\sum_{j=1}^{l}\left|\frac{Q_{i,b}^{t-1,j}}{\|Q_{i,b}^{t-1}\|_{2}}-\frac{Q_{i,b}^{t,j}}{\|Q_{i,b}^{t}\|_{2}}\right|$
(5)

where $b$ is the class with the highest predicted probability by $M_{t}$ for
the input $i$, and $l$ is the length of each vectorized attention map. This
formulation ensures that both models $M_{t-1}$ and $M_{t}$ produce similar
attention responses for the old and new data, aiding in the retention of
knowledge about the old model while effectively adapting to new spoof threats.

####  II-A4 Improved Positive Sample Alignment

In the task of distinguishing genuine from fake speech, genuine speech
typically exhibits a more consistent feature distribution across different
scenarios compared to the varied distributions of fake audio. This observation
is crucial in scenarios involving new types of spoofing attacks, where a clear
disparity exists between the feature distributions of previously known and
newly encountered spoofing data. Unlike fake audio, the features of genuine
speech remain relatively stable across different conditions. Recognizing the
stability of genuine speech features, we propose an enhanced version of the
Positive Sample Alignment (PSA) loss, which aims to constrain the feature
distribution of genuine speech across various data sources more effectively.
Unlike previous approaches [18] that only utilize embeddings from the last
fully connected layer, our novel method incorporates embeddings from multiple
layers, including different depths within the convolutional layers. This
multi-layer approach allows the student model to learn a more comprehensive
representation of the genuine speech’s feature distribution, leading to
improved detection performance. The PSA loss is formulated using the cosine
distance to measure the similarity between the genuine (positive) embeddings
from the current and the original model. The loss is computed as follows:

$L_{psa}=\sum_{l=1}^{L}\frac{1}{N_{P}}\sum_{k=1}^{N_{P}}\frac{\mathbf{y}_{l,+}^{k}~{}\hat{\mathbf{y}}_{l,+}^{k}}{\|\mathbf{y}_{l,+}^{k}\|\cdot\|\hat{\mathbf{y}}_{l,+}^{k}\|}$
(6)

where $N_{P}$ is the number of genuine speech samples evaluated, and $L$
represents the total number of layers from which embeddings are utilized, it
acts as a collective consideration of various depths within the model. For
each layer $l$, $\mathbf{y}_{l,+}^{k}$ and $\hat{\mathbf{y}}_{l,+}^{k}$ are
the embedding vectors of the $k$-th genuine speech sample as extracted by the
original and current models, respectively. The dot product $\cdot$ represents
the calculation between the embedding vectors, and $\|\mathbf{y}_{l,+}^{k}\|$
and $\|\hat{\mathbf{y}}_{l,+}^{k}\|$ are the norms of these vectors for each
layer. The PSA loss aims to minimize this cosine distance, ensuring that the
representation of genuine speech remains consistent across updates in the
model architecture or variations in the training data.

##  III Experiment setting

###  III-A Dataset

The effectiveness of our proposed methods is validated using the ASVspoof 2019
dataset, a benchmark in audio anti-spoofing. This dataset is divided into two
subsets: Logical Access (LA) and Physical Access (PA). The LA subset addresses
threats from synthesis attacks, covering 19 different spoofing techniques. In
our experiments, we use the A1 to A6 six spoofing techniques which is the most
in the dataset. We select different combinations within the LA dataset with
significant differences to validate our methods. This variety provides a
thorough evaluation ground for detecting unseen synthesized audio attacks. The
PA subset mimics replay attacks to simulate real-world conditions.

###  III-B Models

In audio anti-spoofing, choosing the right feature extraction backbone is key
to identifying real and fake audio. We use two main backbones: RawNet2 [25]
and LFCC-LCNN [1]. RawNet2 processes raw audio directly, avoiding handcrafted
features. It uses CNNs, batch normalization, and ReLU activation. GRUs capture
time dependencies, and self-attention focuses on key parts of the audio. This
makes RawNet2 effective for learning and adapting to new spoofing attacks.
LFCC-LCNN uses LFCC features, common in speech processing, to represent audio
signals compactly. The CNN framework in LFCC-LCNN processes these features
through convolutional and pooling layers, enhancing the model’s ability to
distinguish real from fake audio. This stable feature set helps the model
learn and generalize across different spoofing attacks.

###  III-C Task Setting

In order to establish a benchmark for future researchers, we research several
continual learning methodologies applicable to audio anti-spoofing tasks,
including Elastic Weight Consolidation (EWC) [26], Memory Aware Synapses (MAS)
[27], Learning Without Forgetting (LWF) [20], and Detecting Fake Without
Forgetting (DFWF) [18]. We compare these methods with our novel approach known
as CADE, to evaluate its performance. Additionally, we also implement
finetune, replay, and joint training strategies to further validate the
effectiveness of CADE. Finetune involves training sequentially on each new
task using solely the classification loss. Replay builds upon finetuning by
retaining a subset of data from previous tasks during the training of new
tasks. Joint training, considered as the upper limit in continual learning,
involves training on a combined dataset from all tasks. We conducted three
sets of experiments, detailed as follows:

  1. 1.

Using LFCC-LCNN as the backbone, we perform sequential training across
$LA\rightarrow PA$ and $PA\rightarrow LA$. The purpose of this experiment was
to evaluate the performance of the CADE method across spoofing types with
significant differences.

  2. 2.

We utilize LFCC-LCNN [1] and RawNet2 [25] as backbones to partition different
spoofing types within the LA dataset for sequential training, following these
specific divisions:

     * •

$A1+A2\rightarrow A3+A4\rightarrow A5+A6$

     * •

$A1+A2+A5\rightarrow A3+A4+A6$

The aim of this set is to explore the effects of different backbones on
continual learning for deepfake audio and to evaluate the CADE method’s
performance across spoofing types with more subtle distinctions.

  3. 3.

Based on the partitioning used in Experiment 2, we investigate the impact of
varying memory sizes for a replay-based strategy. This experiment aims to
explore how different memory sizes influence the replay-based strategy within
our CADE framework.

TABLE I: Performance of our method across spoofing types with significant
difference.

Experiment Setting(LFCC-LCNN) | Method | Test EER(%)
---|---|---
Joint | Joint | 23.228
LA->PA | Finetune | 46.006
EWC | 27.704
LWF | 40.689
MAS | 28.049
DFWF | 31.564
CADE(Ours) | 25.679
PA->LA | Finetune | 34.394
EWC | 27.550
LWF | 27.616
MAS | 26.475
DFWF | 25.634
CADE(Ours) | 24.717

###  III-D Metric

In assessing the effectiveness of our novel approaches, we employ the Equal
Error Rate (EER) as our primary metrics. EER is a widely used measure in
biometric systems, signifying the threshold at which the rates of false
acceptances and false rejections are identical; in simpler terms, it reflects
the point of equilibrium where the occurrence of both types of errors is
equal. The efficiency of a model is inversely proportional to the EER
value—the lower the EER, the more accurate the model. In our evaluation, we
focus on the performance of models that undergo sequential training, a common
practice in continual learning settings. After training, we directly evaluate
the models on the test set to assess model performance across different
spoofing scenarios.

##  IV Result and Analysis

###  IV-A Experiments on significantly different spoofing types

The evaluation of our CADE method shows its strong ability to handle different
spoofing attacks as table I. When moving from LA to PA, CADE achieved the
lowest Test EER (25.679%), outperforming methods like EWC, LWF, and DFWF. LWF
struggled with a Test EER of 40.689%, indicating its poor retention of past
knowledge. In the reverse transition from PA to LA, CADE again had the lowest
Test EER (24.717%). This shows that while finetuning is effective, CADE’s use
of regularization and replay strategies ensures more consistent performance.
The slight improvement over DFWF (25.634%) highlights CADE’s advantage in
various task sequences.

TABLE II: Performance on LA subset by using LFCC-LCNN.

Experiment Setting(LFCC-LCNN) | Name | Test EER(%)
---|---|---
Joint | Joint | 13.186
A1+A2 TO A3+A4 TO A5+A6 | Finetune | 32.171
EWC | 29.729
LWF | 28.293
MAS | 28.928
DFWF | 25.369
CADE(Ours) | 19.327
A1+A2+A5 TO A3+A4+A6 | Finetune | 26.327
EWC | 24.461
LWF | 23.173
MAS | 24.016
DFWF | 22.437
CADE(Ours) | 15.582

TABLE III: Performance on LA subset by using RawNet2.

Experiment Setting(RAWNET2) | Name | Test EER(%)
---|---|---
Joint | Joint | 2.065
A1+A2 TO A3+A4 TO A5+A6 | Finetune | 16.629
EWC | 11.273
LWF | 11.493
MAS | 12.174
DFWF | 8.249
CADE(Ours) | 6.473
A1+A2+A5 TO A3+A4+A6 | Finetune | 9.047
EWC | 5.792
LWF | 6.347
MAS | 5.883
DFWF | 4.702
CADE(Ours) | 3.172

###  IV-B Experiments on the LA series spoofing types

Our experiments on the LA subset using both LFCC-LCNN and RawNet2 backbones
show the effectiveness of the CADE method in handling various spoofing
attacks. Using LFCC-LCNN as table II, the joint training method, representing
the upper bound of performance, achieved the lowest Test EER of 13.186%. In
contrast, the finetune method, representing the lower bound due to more
forgetting, had higher error rates. In the A1+A2 to A3+A4 to A5+A6 transition,
CADE achieved a Test EER of 19.327%, outperforming finetune (32.171%), EWC
(29.729%), and DFWF (25.369%). In the A1+A2+A5 to A3+A4+A6 transition, CADE
also performed well with a Test EER of 15.582%, better than finetune
(26.327%), EWC (24.461%), and DFWF (22.437%). Using RawNet2 as table III, CADE
also achieved the lowest Test EER of 6.473% in the A1+A2 to A3+A4 to A5+A6
transition. In the A1+A2+A5 to A3+A4+A6 transition, CADE had a Test EER of
3.172%, better than the others.

Overall, CADE consistently outperformed other methods and approached the
performance of joint training. This highlights CADE’s potential for robust and
efficient continual learning in audio anti-spoofing, making it suitable for
real-world applications where adaptability and retention of past knowledge are
crucial.

TABLE IV: Performance of replay-based strategy with different memory size.

Experiment Setting(LFCC-LCNN) | Name | Memory | Test EER(%)
---|---|---|---
JOINT | JOINT | / | 13.186
A1+A2 TO A3+A4 TO A5+A6 | FINETUNE | 0 | 32.171
EWC | [500, 1000, 1500] | [23.234, 24.294, 25.248]
REPLAY | [500, 1000, 1500] | [28.624, 29.975, 31.239]
DFWF | [500, 1000, 1500] | [19.213, 21.372, 23.671]
CADE(Ours) | [500, 1000, 1500] | [16.673, 19.327, 22.629]
A1+A2+A5 TO A3+A4+A6 | FINETUNE | 0 | 26.327
EWC | [500, 1000, 1500] | [18.632, 20.379, 22.648]
REPLAY | [500, 1000, 1500] | [23.986, 24.347, 25.473]
DFWF | [500, 1000, 1500] | [16.230, 17.758, 20.362]
CADE(Ours) | [500, 1000, 1500] | [13.382, 15.582, 17.329]

###  IV-C Experiments on the various replay size

We evaluated the Continual Audio Defense Enhancer (CADE) with different memory
sizes using LFCC-LCNN for two transitions as table IV:

For A1+A2→A3+A4→A5+A6, CADE achieved the best Test EERs: 16.673%, 19.327%, and
22.629% for memory sizes of 500, 1000, and 1500. This shows CADE’s ability to
balance old and new data well, even with limited memory. The finetune method,
with no memory, had a higher Test EER of 32.171%, showing more forgetting.
Other methods like EWC and DFWF also had higher error rates than CADE, though
DFWF was better than REPLAY and EWC.

For A1+A2+A5→A3+A4+A6, CADE again performed best with Test EERs of 13.382%,
15.582%, and 17.329% for memory sizes of 500, 1000, and 1500. These are better
than finetune (26.327%), showing CADE’s effectiveness. EWC and DFWF were
better than finetune but still behind CADE. CADE’s 13.382% Test EER with 500
memory shows it uses minimal memory well.

Overall, CADE’s low error rates across memory sizes and tasks highlight its
robustness and efficiency, crucial for real-world applications with limited
memory and a need to retain past knowledge.

##  V Conclusion

This study introduces the Continual Audio Defense Enhancer (CADE). CADE
combines regularization-based and replay-based strategies, effectively
balancing the retention of old knowledge and the learning of new tasks. Our
experiments using LFCC-LCNN and RawNet2 backbones demonstrate CADE’s superior
performance compared to traditional methods, especially in settings with
significant differences in spoofing types. CADE consistently outperformed
other methods, achieving lower Test EERs even with limited memory sizes. This
highlights CADE’s efficiency and robustness in continual learning scenarios.

## References

  * [1] Massimiliano Todisco, Xin Wang, Ville Vestman, Md. Sahidullah, Héctor Delgado, Andreas Nautsch, Junichi Yamagishi, Nicholas Evans, Tomi H. Kinnunen, and Kong Aik Lee,  “ASVspoof 2019: Future Horizons in Spoofed and Fake Audio Detection,”  in Proc. Interspeech 2019, 2019, pp. 1008–1012.
  * [2] Tomi Kinnunen, Md Sahidullah, Héctor Delgado, Massimiliano Todisco, Nicholas Evans, Junichi Yamagishi, and Kong Aik Lee,  “The asvspoof 2017 challenge: Assessing the limits of replay spoofing attack detection,”  2017\.
  * [3] Tomi Kinnunen, Zhizheng Wu, EURECOM Nicholas Evans, and Junichi Yamagishi,  “Automatic speaker verification spoofing and countermeasures challenge (asvspoof 2015) database,”  2018\.
  * [4] Jiangyan Yi, Ruibo Fu, Jianhua Tao, Shuai Nie, Haoxin Ma, Chenglong Wang, Tao Wang, Zhengkun Tian, Ye Bai, Cunhang Fan, et al.,  “Add 2022: the first audio deep synthesis detection challenge,”  in ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 9216–9220.
  * [5] Jiangyan Yi, Jianhua Tao, Ruibo Fu, Xinrui Yan, Chenglong Wang, Tao Wang, Chu Yuan Zhang, Xiaohui Zhang, Yan Zhao, Yong Ren, et al.,  “Add 2023: the second audio deepfake detection challenge,”  arXiv preprint arXiv:2305.13774, 2023.
  * [6] Tanvina B Patel and Hemant A Patil,  “Combining evidences from mel cepstral, cochlear filter cepstral and instantaneous frequency features for detection of natural vs. spoofed speech.,”  in Interspeech, 2015, pp. 2062–2066.
  * [7] Massimiliano Todisco, Héctor Delgado, and Nicholas WD Evans,  “A new feature for automatic speaker verification anti-spoofing: Constant q cepstral coefficients.,”  in Odyssey, 2016, vol. 2016, pp. 283–290.
  * [8] Rohan Kumar Das, Jichen Yang, and Haizhou Li,  “Assessing the scope of generalized countermeasures for anti-spoofing,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 6589–6593.
  * [9] Galina Lavrentyeva, Sergey Novoselov, Egor Malykh, Alexander Kozlov, Oleg Kudashev, and Vadim Shchemelinin,  “Audio replay attack detection with deep learning frameworks.,”  in Interspeech, 2017, pp. 82–86.
  * [10] Galina Lavrentyeva, Sergey Novoselov, Andzhukaev Tseren, Marina Volkova, Artem Gorlanov, and Alexandr Kozlov,  “STC Antispoofing Systems for the ASVspoof2019 Challenge,”  in Proc. Interspeech 2019, 2019, pp. 1033–1037.
  * [11] Zhenchun Lei, Yingen Yang, Changhong Liu, and Jihua Ye,  “Siamese convolutional neural network using gaussian probability feature for spoofing speech detection.,”  in Interspeech, 2020, pp. 1116–1120.
  * [12] Patrick von Platen, Fei Tao, and Gokhan Tur,  “Multi-Task Siamese Neural Network for Improving Replay Attack Detection,”  in Proc. Interspeech 2020, 2020, pp. 1076–1080.
  * [13] Joao Monteiro, Jahangir Alam, and Tiago H Falk,  “An ensemble based approach for generalized detection of spoofing attacks to automatic speaker recognizers,”  in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2020, pp. 6599–6603.
  * [14] Hongji Wang, Heinrich Dinkel, Shuai Wang, Yanmin Qian, and Kai Yu,  “Dual-adversarial domain adaptation for generalized replay attack detection.,”  in Interspeech, 2020, pp. 1086–1090.
  * [15] Yang Xiao and Rohan Kumar Das,  “Configurable doa estimation using incremental learning,”  arXiv preprint arXiv:2407.03661, 2024.
  * [16] Yang Xiao, Xubo Liu, James King, Arshdeep Singh, Eng Siong Chng, Mark D. Plumbley, and Wenwu Wang,  “Continual learning for on-device environmental sound classification,”  in Proceedings of the 7th Detection and Classification of Acoustic Scenes and Events 2022 Workshop (DCASE2022), November 2022.
  * [17] Yang Xiao, Nana Hou, and Eng Siong Chng,  “Rainbow Keywords: Efficient Incremental Learning for Online Spoken Keyword Spotting,”  in Proc. Interspeech 2022, 2022, pp. 3764–3768.
  * [18] Haoxin Ma, Jiangyan Yi, Jianhua Tao, Ye Bai, Zhengkun Tian, and Chenglong Wang,  “Continual Learning for Fake Audio Detection,”  in Proc. Interspeech 2021, 2021, pp. 886–890.
  * [19] Yang Xiao and Rohan Kumar Das,  “Dual knowledge distillation for efficient sound event detection,”  arXiv preprint:2402.02781, 2024.
  * [20] Zhizhong Li and Derek Hoiem,  “Learning without forgetting,”  IEEE transactions on pattern analysis and machine intelligence, vol. 40, no. 12, pp. 2935–2947, 2017.
  * [21] Prithviraj Dhar, Rajat Vikram Singh, Kuan-Chuan Peng, Ziyan Wu, and Rama Chellappa,  “Learning without memorizing,”  in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, 2019, pp. 5138–5146.
  * [22] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in Proceedings of the IEEE international conference on computer vision, 2017, pp. 618–626.
  * [23] Liyuan Wang, Xingxing Zhang, Hang Su, and Jun Zhu,  “A comprehensive survey of continual learning: Theory, method and application,”  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
  * [24] Yang Xiao and Rohan Kumar Das,  “Ucil: An unsupervised class incremental learning approach for sound event detection,”  arXiv preprint arXiv:2407.03657, 2024.
  * [25] Hemlata Tak, Jose Patino, Massimiliano Todisco, Andreas Nautsch, Nicholas Evans, and Anthony Larcher,  “End-to-end anti-spoofing with rawnet2,”  in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021, pp. 6369–6373.
  * [26] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al.,  “Overcoming catastrophic forgetting in neural networks,”  Proceedings of the national academy of sciences, vol. 114, no. 13, pp. 3521–3526, 2017.
  * [27] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars,  “Memory aware synapses: Learning what (not) to forget,”  in Proceedings of the European conference on computer vision (ECCV), 2018, pp. 139–154.


# Optimizing Gait Libraries via a Coverage Metric

Brian Bittner  Robotics Institute, University of Michigan, Ann Arbor, USA
Johns Hopkins University Applied Physics Lab, Laurel, MD, USA
<EMAIL_ADDRESS>Shai Revzen  Robotics Institute, University of
Michigan, Ann Arbor, USA  Electrical Engineering and Computer Science
Department & Ecology and Evolutionary Biology Department, University of
Michigan, Ann Arbor, USA
<EMAIL_ADDRESS>
###### Abstract

Many robots move through the world by composing locomotion primitives like
steps and turns. To do so well, robots need not have primitives that make
intuitive sense to humans. This becomes of paramount importance when robots
are damaged and no longer move as designed. Here we propose a goal function we
call “coverage”, that represents the usefulness of a library of locomotion
primitives in a manner agnostic to the particulars of the primitives
themselves. We demonstrate the ability to optimize coverage on both simulated
and physical robots, and show that coverage can be rapidly recovered after
injury. This suggests that by optimizing for coverage, robots can sustain
their ability to navigate through the world even in the face of significant
mechanical failures. The benefits of this approach are enhanced by sample-
efficient, data-driven approaches to system identification that can rapidly
inform the optimization of primitives. We found that the number of degrees of
freedom improved the rate of recovery of our simulated robots, a rare result
in the fields of gait optimization and reinforcement learning. We showed that
a robot with limbs made of tree branches (for which no CAD model or first
principles model was available) is able to quickly find an effective high-
coverage library of motion primitives. The optimized primitives are entirely
non-obvious to a human observer, and thus are unlikely to be attainable
through manual tuning.

##  I Introduction

One of the most common sub-problems in modern robotics is path-planning, and
the choice of path is usually framed as a precise or approximate optimal
control problem. When restricted to mobile robots moving through many
practical environments, the path planning problem enjoys an additional
important symmetry. Given the configuration of the robot body, the short-
horizon movements it can execute are the same at nearly every point in space.
This allows short time horizon _primitives_ to be optimized offline and pre-
cached, later to be composed sequentially to produce solutions to the full
path planning problem. For example, a humanoid robot such as ATLAS can execute
the same walking steps at any point on flat, unobstructed ground. To plan the
motions of the robot walking through a building, one can sequence primitives
for generating a collection of steps in the correct order instead of solving
the full high-dimensional planning problem.

Unfortunately, the primitives seen in such library-based plans are usually
created by hand, and generated with constraints that help reduce the
complexity of an individual planning problem. For example, a common choice for
2D motion, dating back to the turtle robots of the 1950s [1], is to have
linear translation and turning in place as primitives. However, this
particular choice for generating movements is entirely arbitrary. A given
robot may be far more efficient moving diagonally or turning while moving on
an arc. The ability to optimize for a library of useful primitives can come to
have critical importance when a robot is damaged, and the choice of best
available primitives might no longer correspond to any motion obvious to a
human operator.

Here we present a method to optimize an entire primitive library concurrently
so as to achieve the ability to efficiently plan over the space of body
motions with that library. By optimizing for the _coverage_ goal function we
define, the library selected will be able to express desired short-horizon
plans through composition of primitives from the library.

One approach for approximate optimal planning is to construct a state lattice
[2, 3] – a discrete collection of states that can be generated by a library of
primitives. Planning consists of sequencing primitives to travel along the
lattice to approximate the total desired motion. Such previous work on state
lattices suggests that a good collection of primitives are:

  * •

complete – the space of desirable motions is densely populated

  * •

fast-to-compute – the robot is able to select and use primitives in real time

  * •

path optimal – each individual primitive should be similar to a globally
optimal path available between its start and end states.

When generating primitives, one has a variety of options to chose from [4, 5,
6, 7, 8]. Strategies can include learning from demonstration as well as
prioritizing spatial properties of the output trajectories of the system.
Large primitive libraries are often winnowed down to save run time or increase
the planning update rate. Our work can be viewed (in part) as a means for
generating very small, very expressive libraries of primitives.

Our work can also be seen as a way to relax the standard assumption used in
optimizing gaits, namely pre-specifying the direction [9, 10] or turn rate of
motion [11, 12] over a single cycle. We observe that most of the value a
primitive has is not intrinsic, but rather in its contribution to support
other compositions of primitives available to a planner and the overall needs
of the planning task. We thus provide a way to evaluate libraries of
primitives rather than their individual characteristics. Primitives that have
negligible exploration value in isolation may be critical to more densely
maneuvering through space. We demonstrate how our coverage measure values such
primitives rather than discards them.

Using our approach is nearly paradigmatically opposite to traditional behavior
learning in robotics. We allow for the optimizer to “ask” the robot what ways
are convenient to move, rather than dictating how the robot should move
a-priori. A subsequent advantage is that mechanical designers can rethink
common design criteria for locomotors. Typically robots acting on a planar
workspace are designed to have at least one mode by which gaits translate the
system without rotating it. This preference may simply be the result of an
anthropocentric bias. It is how humans move to avoid disorientation and
dizziness, but it is not a universal requirement for effective locomotion. The
coverage measure, being devoid of such biases, allows a broader range of robot
mechanisms to score highly. Crucially, it can also potentially allow broken
robots to recover their ability to plan motions by rapidly regenerating a
primitive library while damaged.

###  I-A Overview of this paper

Below we briefly review Lie groups in §II, so as to use them to represent the
composition of primitive libraries as a sequence of group actions acting on a
Lie group of body locations. Using this representation, we define coverage in
§III and provide examples of how it can be computed on the rigid body groups
$\mathsf{SE}(2)$ and $\mathsf{SE}(3)$. In §IV we use this coverage to discuss
a collection of toy systems whose locomotion ability becomes easy to
appreciate through our approach. We translate this framework of primitive
optimization to the world of gait driven systems in §V. There we pay special
attention to highly damped systems, where the task of chaining primitives can
be greatly simplified. We present coverage optimization of gait libraries for
some Purcell swimmer models in §VII. Using coverage as a tool, in §VIII we
investigate the ability of the Purcell swimmer to recover from joint locking
failures. Finally, we emphasize the ability of the optimization to work on
unintuitive robots, even when we do not specify the robot kinematics, mass
distribution, or material properties. We demonstrate with a robot whose limbs
are made of tree branches, and which gained the ability to navigate on the
floor with less than eleven minutes of hardware-in-the-loop optimization for
coverage.

##  II Expressing Motion Through the Space of Discrete Actions

To represent motion, we assumed that the configuration space $\mathcal{Q}$ of
our moving robot could be factored as a product of a shape $R$ and a
(generalized) position $G$. This generalized position is a Lie group,
typically a sub-group of the rigid body motions $\mathsf{SE}(3)$. In this
work, we restricted our attention to motion in the ground plane,
$\mathsf{SE}(2)$. We produced motion using _(periodic) gaits_ , which we take
to mean periodic changes in shape that produce a predictable body motion.
Formally, a gait $b$ is a function $\gamma_{b}:S^{1}\to R$ that produces a
body motion $M_{b}\in G$. A stride consisting of a left step followed by a
right step is an example of a gait cycle of human walking. Given a finite
selection of gaits and a means for switching between them, a planner can
produce any motion that corresponds to a word composed of the group elements
(letters) those gaits generate. For example, with gaits $\gamma_{a}$ and
$\gamma_{b}$, and provided any sequence is allowed, one can produce the
motions
($I,M_{a},M_{b},M_{a}^{2},M_{a}M_{b},M_{b}^{2},M_{b}M_{a},M_{a}^{3},\ldots$).
Figure 1 provides a visualization of what this representation looks like for
motion planning in a planar workspace.

Figure 1:  Illustration of composing gait cycles. Here, the two group actions
($M_{A},M_{B}$) are applied in various orders and combinations. An $n$-step
finite horizon planner considers words, a concatenation of group action
letters, of length $n$. For a two letter action library, $n$ step planners
consider $2^{n}$ paths (trees in the left panel). We illustrated a possible
case of such motions. By assuming that the robot is oriented tangent to the
direction of motion, the resulting motions can be represented by their
projection on the translational plane (right panel).

In this paper, we restricted our discussion to primitive libraries consisting
of single cycles of different gaits as the primitives and assumed the gaits
are connected in internal state at their start and end configuration. This is
not generally the case, and receives more careful treatment in §V.

##  III Specifying the Loss Function

As conventionally practiced, a motion planner is given some parameters $x$, a
means to generate motions $M(x)\in G$, and some loss function which it will
minimize. Because we did not consider power efficiency here, we took the loss
function

$\tilde{\eta}:G\to\mathbb{R}^{+}$ (1)

to be purely a function of the endpoint. Including additional factors in the
loss functions for individual primitives is only a matter of book-keeping,
provided the loss function of the overall path is additive in those of its
constituent primitives. We assumed that the loss function is written relative
to some desired goal position $G$ of the motion, and defined a relative
(local) loss function using the Lie algebra
$\eta(\xi):=\tilde{\eta}(\exp(\xi)G).$ We then optimized for the parameters
$x$ of the primitive with respect to the loss function
$x\mapsto\eta\circ\log(M(x)G^{-1}).$ Any left invariant distance metric for
$\mathsf{SE}(2)$ or $\mathsf{SE}(3)$ provides practical implementation of
$\tilde{\eta}$. Picking such a metric boils down to a choice of a constant
that relates the loss of translation errors to the loss of orientation errors,
and thus this choice is application specific. In this work, we chose this
parameter to make a half rotation on any axis to be of equal loss to
displacement of a body length.

We set up our optimization as follows: let $\mathbf{G}:=\\{G_{i}\\}_{i=1}^{n}$
be a set of goal motions and
$\mathbf{W}:=\\{w_{i}\\}_{i=1}^{n}\subset\mathbb{R}^{+}$ be a corresponding
set of weights. Let $\mathbf{M}:=\\{M_{j}\\}_{j=1}^{m}$ be a set of achievable
motions.

We defined the coverage cost

$h(\mathbf{M}):=\sum_{i}w_{i}\min_{j}\eta\circ\log(M_{j}G^{-1}_{i}).$ (2)

We further defined $h_{k}(\mathbf{M})$ as the cost of the set of words of $k$
or fewer elements of $\mathbf{M}$. The coverage cost is the sum of the costs
of the best approximations available for $G_{i}$, given the achievable $M_{j}$
and weighted by the weights $w_{i}$ for each $G_{i}$.

Figure 2:  Expressive power of the coverage cost. One has a variety of choices
for placement and weighting of coverage points. We provided some suggestions
for various design goals on the space of planar rigid body motions. A user can
prioritize versatility (panel A), zero-rotation translation (panel B), or
right lateral movement (panel C). Volumes and planes are suggested regions for
the user to evenly distribute uniformly weighted coverage points $G_{i}$.

###  III-A Higher order maneuvers

One of the surprising insights of nonlinear control is that the non-
commutativity of control actions can make reachable the iterated Lie brackets
of a control distribution [13, 14]. The discrete primitive library equivalent
of this insight is the observation that the _commutator_ word
$M_{a}M_{b}M^{-1}_{a}M^{-1}_{b}$ can at times reach directions that no word of
the form $M_{a}^{n}M_{b}^{m}$ could reach. Thus, designing $h_{k}(\cdot)$ such
that $k\geq 4$ allows these higher-order maneuvers to be included. It is,
however, important to note that the coverage computation time scales
exponentially with $k$. For this reason, we used $k=4$ in our implementations
here.

###  III-B Design choices for coverage points

The coverage cost presented offers a user the ability to specify both the
placement and weighting of coverage points. The selection of the points and
weights can radically change the priorities of the optimizer. A user
prioritizing versatility may want the robot to be able to reach all parts of
its local position space. They can place a uniformly weighted set of points
distributed evenly within some volume around the identity (non-)motion (Figure
2 A). Another user may wish to find a combination of gaits that translate
while preserving orientation. That might correspond to a coverage point
distribution in a thin wedge near the 2D slice of $\mathsf{SE}(3)$
corresponding to no rotation (Figure 2 B). Such maneuvers might be useful for
an inspection robot that needs to maintain a visual field of view while
moving. If one had a more specific navigational goal, e.g. finding a way to
translate laterally to the right, such a goal can also be captured (Figure 2
C).

The $w_{i}$ weighted collection of coverage goal points $G_{i}$ can be seen as
a discrete approximation to a measure on the group. Increasing the number of
goal points in a region while keeping the total weight constant implies a
preference for higher resolution in that region. Changing the weight while
keeping the goal points unchanged implies an increase or decrease in the
importance of approximating those goal motions with the primitive library.

Figure 3: Here we describe two mechanical systems that may appear as
unconventional travelers. The two-slider swimmer (left) can move spheres along
prismatic joints. The motion simultaneously induces a thrust on the system
while changing the geometry of drag forces acting on the system. We plotted
the gaits selected for the two-slider swimmer on the rotational connection
vector field [9] of the two-slider swimmer (middle). This provided insight
into how shape change can influence body velocity. We can see that paths
(shown in red) that start in the corner at the origin, travel along a shape
axis, sweep at a constant radius to another axis, then return to the origin.
The connection vector field aided gait selection of the two-slider swimmer,
which is discussed in §IV-B1. The three-branch swimmer (right) has two-joints
that can rotate, fixed to the end of a triangle. Since the shape space of the
three-branch swimmer is not restricted to planar representations, we selected
gaits in a different way.

##  IV Coverage Invites Non-traditional Mechanical Designs

Figure 4: Both systems were able to explore their local environments in a way
that is unrestricted to translation in the plane. We plotted paths to show the
number of steps required to arrive at a target pose, omitting visualization of
the orientation ($\theta$) component of the full $\mathsf{SE}(2)$ pose. We
plotted motions available in 5 steps (1=black, 2=green, 3=blue, 4=magenta, and
5=cyan). At 5 steps (cyan), the system had a broad variety of poses at its
disposal. Both systems appear to be capable of navigating through environments
with sparse obstacles.

Here we intentionally designed two robots that move in unconventional ways.
The first cannot translate without rotating. The second has a trilateral
symmetry. Often, roboticists do not consider such systems because their
mobility is non-intuitive. Yet we have shown below that both systems can move
quite effectively in $\mathsf{SE}(2)$.

###  IV-A Introducing two new mechanisms

Both of the mechanical system models we present are swimmers that operate at
the limit of low Reynolds number fluid dynamics [15], where friction dominates
inertia. The motion of these systems is fully dominated by the drag forces
induced by the internal velocities of the robots shape variables $r\in R$ and
body velocities $\accentset{\scriptstyle\circ}{g}\in\mathsf{T}\mathsf{SE}(2)$.
The motions of these systems can be usefully inspected using the tools of [9,
16, 17].

####  IV-A1 Two-slider swimmer model:

The two-slider swimmer in Figure 3 moves via the prismatic joints driven by
strictly positive displacements $r_{1}$ and $r_{2}$. The viscous force on each
sphere is linear in translational velocity and cubic in rotational velocity.
Its full model is:

$\displaystyle\begin{bmatrix}3d&0&0\\\ 0&3d&0\\\
-dr_{2}&-dr_{1}&d({r_{1}}^{2}+{r_{2}}^{2})+\frac{d^{3}}{4}\end{bmatrix}\accentset{\scriptstyle\circ}{g}=R(\alpha)\begin{bmatrix}0&d\\\
-d&0\\\ 0&0\end{bmatrix}\dot{r}$ (3) $\displaystyle\alpha=-\frac{\pi}{2}$

where R takes input parameters to a rotation about the origin on
$\mathsf{SE}(2)$.

####  IV-A2 Three-branch swimmer model:

We also designed the three-branch swimmer (see Figure 3), another viscous
swimmer. two-joints are free to rotate from the points of the triangle. For
biological intuition for how a system like this might move, a starfish might
move like a pentagonal five-branch system with longer segments of links at
each vertex. The links interact via the slender body theory of Cox [18], the
same that was used for the swimmer in [16] and paddles in [19]. The drag of
the triangular piece is represented by three static links that point from the
center of the triangle to their respective attachment points.

###  IV-B Hand selecting gaits

####  IV-B1 Gait selection for two-slider swimmer:

By inspection of the connection vector field of the rotational component of
the two-slider swimmer (see Figure 3), we saw that a variety of turning modes
could be excited. Hand-selected gaits all started at the origin of the base
space, travel along the axis of one shape variable, then translated at a
constant radius from the origin, traveling from one positive end of a shape
axis to the other. Each path was then sent to the origin via the other shape
variable. We can see from the curl of the vector field that clockwise gaits
will yield positive rotation, and counter-clockwise gaits will yield negative
rotation. The three paths printed in red represent three magnitudes of turning
the system can choose. The larger the radius, the greater the turn will be, as
explained in Figure 3. Each gait also induces a translational displacement of
the system from its starting location.

####  IV-B2 Gait selection for three-branch swimmer:

The three-branch swimmer is less amenable to inspection by the connection
vector field methods since it has a third shape variable. Reduction methods
(such as [20]) can make such gait analysis useful for more complex Stokesian
systems. Geometric gait optimization can also be employed on this analytical
system to obtain a collection of gaits, maximizing various objective functions
[21]. In this example, our goal is to demonstrate that sub-optimal behaviors
can be interpreted as valuable through the coverage metric. Therefor, we
selected gaits rather heuristically. Two criteria for selected motions were to
avoid self-intersections and enclose a non-zero volume in the shape
space111The scallop theorem [22] ensures that gaits with zero enclosed volume
will achieve zero displacement in the stokes regime. Two links oscillated in
anti-phase, providing a thrust that acts through a line from the midsection of
their attachment points to the third link’s attachment point. The third link
oscillated out of phase by a quarter cycle. We designed the gaits as:

$\displaystyle r_{mod(k,3)+1}$ $\displaystyle=\sin(\varphi)$ (4)
$\displaystyle r_{mod(k+1,3)+1}$ $\displaystyle=1-\cos(\varphi)$ (5)
$\displaystyle r_{mod(k+2,3)+1}$ $\displaystyle=-1+\cos(\varphi)$ (6)

for $\varphi\in S^{1}$ with gaits $\gamma_{k}$ enumerated k = (1,2,3). These
three gaits generate three group actions, which can also be run backward in
$\varphi$, generating three inverse group actions.

Each system had six gaits at its disposal. By inspection of Figure 4, we
observe the local planning ability of the systems, only using the six gaits as
possible actions (letters) of their total motion (word). We highlight the key
takeaway of this section. Behaviors that were not useful in isolation were
critical to providing dense coverage. Furthermore, these behaviors may lie
outside the scope of typical behaviors that a roboticist may prescribe for a
system.

##  V Connecting Gait and Motion

The algebraic structure for computing available motions is straightforward:
separate gaits were concatenated as a string of group multiplications. What
dynamical properties were required for such assumptions? We cover the
assumptions we made in this section, using the language of geometric
mechanics. For general dynamical systems, combining gaits would require a
transition behavior that matches the internal state ($r,\dot{r},p$) of the
endpoint of one gait and connects it with the internal state ($r,\dot{r},p$)
of the starting point of the next gait. There exist a class of systems where
the matching requirements are highly relaxed.

###  V-A Planning simplifications in principally kinematic systems

The class of systems we focused on in this work inhabit the Stokes regime
[23], which encompass the dynamic qualities of the principally kinematic case
covered in [24]. A well known example of such systems is low Reynolds number
swimmers [25, 26]. However, we recently accumulated evidence that this theory
applies to multi-legged locomotion [27, 28]. The function $A(\cdot)$ connects
gaits, as body shape loops, to the motion they induce, called the “holonomy”
of the loop.

It is known from Stokes’ Theorem that a closed loop integral of a vector field
is equal to the area integral of the volume enclosed by the loop. This is an
approximation of the motion for non-abelian systems, and careful selection of
coordinates can improve the quality of this approximation [29]. This theorem
extends to higher dimensional spaces, and when it is a close approximation it
provides the flexibility of inducing equivalent group actions no matter where
the closed loop starts or stops. Furthermore, any path in the kernel
distribution of $A(\cdot)$ can connect such loops to one-another without
introducing an additional motion in the group. In practice, however, obtaining
this kernel from data requires cumbersome sampling and system identification.

###  V-B Representational simplifications

Given a gait $\gamma_{b}$, the body frame motion $M_{b}$ it produces could, in
principle, be a function of the initial point in the gait cycle and the speed
with which this cycle is executed. For systems where momentum is dominated by
friction or constraints (Stokesian systems), this is not the case. In those
systems there exists a map $A(r):r\in
R\mapsto\mathsf{L(\mathsf{T}_{r},\mathsf{g})}$ taking shapes to linear maps
from shape velocities to the Lie Algebra $\mathsf{g}$ of $G$. This leads to
the “reconstruction equation” $\dot{g}=L_{g}A(r)\dot{r}$ where
$L_{g}:\mathsf{g}=\mathsf{T}_{e}\to\mathsf{T}_{g}$ is the lifted left action
of the group element $g$ (commonly written $g^{-1}\dot{g}=A(r)\dot{r}$ for
matrix Lie groups). Thus, if two base loops are connected at any point, the
combination of their actions can be represented as a group multiplication of
their respective $g$ elements.

There are infinite ways to take a gait library and coordinate it into a
complete motion planner. Typically people have a scheme for transitioning
between gaits. The overhead of finding such transitions for systems with no
model can be large.

When selecting a collection of gaits for computing coverage, we required that
each shares a common point in the base space and thereby allowing gait cycles
to be applied in any order.

##  VI Setup for Discovering a High Coverage Gait Library

To illustrate our approach on a classical system, we simultaneously optimized
three gaits on Purcell swimmers to provide coverage of a portion of
$\mathsf{SE}(2)$ surrounding the identity using their $h_{4}(\cdot)$ cost.

###  VI-A Coverage point selection

This coverage point distribution included equally weighted points derived from
all possible combinations of the following values, totaling 125 points:

$\displaystyle x$ $\displaystyle=[-1,-0.5,0,0.5,1]$ (7) $\displaystyle y$
$\displaystyle=[-1,-0.5,0,0.5,1]$ (8) $\displaystyle\theta$
$\displaystyle=[-\pi,-\frac{\pi}{2},0,\frac{\pi}{2},\pi]$ (9)

where units for translation were body lengths and units for rotation were in
radians. These spanned the translational bounds of moving by one body length
and the rotation bounds of rotating by a half of a full rotation.

###  VI-B Model extraction and motion parametrization

A single iteration of learning involved experimentally running each of the
three gaits for 30 noisy cycles, modeling their dynamics via the framework of
[30]. We parametrized the gaits with a modified version of the ellipse with
bump function parametrization also used in [30]. The following parametrization
$p$ is a modification that allows the base point, $b_{i}$, of the three gaits
to be an explicit parameter:

$\displaystyle r_{i}(t):=$ $\displaystyle c_{i}+(b_{i}-c_{i})\cos(\Omega
t)+a_{i}\sin(\Omega t)+$ (10)
$\displaystyle\sum_{k=0}^{N_{o}-2}u_{i,k}\,w\left(t-k\frac{2\pi}{N_{o}}\right)$
$\displaystyle w(x):=$
$\displaystyle\begin{cases}1+\cos(xfN_{o})&|xfN_{o}|<\pi\\\
0&|xfN_{o}|\geq\pi\end{cases},$ (11)

with gait parameters

$p_{i}=(c_{i},b_{i},a_{i},u_{i,k}).$ (12)

In this work, we used $N_{o}$ = 18 and $f$ = 3, totaling 16 bumps. Two bumps
were elided ($k=17,18$) via this representation such that base point $b$ is
left unshifted.

##  VII Finding Coverage with Purcell swimmers

Our first investigation was to see how well Purcell swimmers can optimize
three gaits simultaneously for the uniformly distributed set of coverage
points of §VI-A. We observed how the ability to optimize these gaits changed
as we added joints to the swimmer. We started with two joints (the two-joint
Purcell swimmer) and built our way up to eight joints. We repeated the
optimization process 30 times for each swimmer.

At the beginning of each optimization, a random joint was stimulated with a
sine wave. The stimulated joint was distinct for each gait. The only exception
to this was that for the two-joint Purcell swimmer, a gait had to be repeated
since there were three initial gaits and only two joints. The swimmers used 30
cycles at each gait to build a model. Then, the swimmers used the models
provided by [30] to predict how changing the parametrization of their three
gaits could be combined to optimize a 4-step plan over the coverage points
provided222Using 4 steps allowed us to include knowledge of the commutator
motions noted in §III-A.. An iteration of the optimization involved stepping
along the policy gradient of three gaits (step size computed via [30]) and
simultaneously updating the three gaits. The results are recorded in Figure 5.

We ended the optimization after 30 iterations. The test showed that the
swimmers were able to use the coverage metric to consistently find a gait
library for local motion planning. Having two joints was sufficient for
finding a gait library, but having three joints presented a notable
improvement in coverage. This jump in performance was less surprising after
considering that the third joint allowed the swimmer to become fully actuated
(when in non-singular configurations) with respect to $\mathsf{SE}(2)$. After
the third joint was added, the convergent behavior of the swimmers was
consistently within the performance noise window of adding another joint, i.e.
the marginal benefit of adding a joint was small.

The convergence rate of the swimmers improved when adding the third and fourth
joints. For all swimmers containing 3 or more joints, the standard deviation
of performance reached $h=0.4$ by the tenth trial. Here, we calculated $h$ as
the average normed distance to a coverage point. Converging at this expedient
rate required exactly 900 cycles of robot data. If we ran physical robots at
3Hz, the optimizations would have converged after collecting just five minutes
of experimental data, even on the eight-joint swimmers.

Figure 5: Purcell swimmers of varying complexity, such as the eight-joint
(pictured bottom left) were optimized for three gaits that maximize coverage.
See §VI-A and §VI-B for details on the setup of the experiment. We plotted the
mean (top, solid lines) and standard deviation (transparent bands) over 30
separate simulations of the average distance of goal motions to the nearest
available motion, denoted $h$. We can see how $h$ changes across trials and
the number of joints used by the swimmer (2=blue, 3=green, 4=red, 5=cyan,
6=magenta, 7=yellow, 8=black). At iteration 30 (marked by a vertical grey
line), we plotted how well the swimmers adapt to having the maximal amplitude
joint locked. We also observed how the quality of the coverage of the library
varies by the number of joints used by the swimmer (bottom right) before (blue
box plots) and after (green box plots) joint locking.  Figure 6: This provides
a detailed look at two optimization process for a three-joint and four-joint
swimmer in the study summarized in Figure 5. We plotted the 4 step horizon
(1=black, 2=green, 3=blue, 4=magenta) at various trials on the plane (left in
each section) and on $\mathsf{SE}(2)$ (right in each section). For reference,
we plotted the unit volume in $\mathsf{SE}(2)$ (gray box) over which the
coverage points were uniformly distributed. For the three-joint swimmer, we
showed the optimal policy before injury in trial 22 (top right), the
consequence of a locked joint (grey dot) on the optimal policy in trial 30
(top middle), and the optimal policy recovered while the joint remains locked
in trial 52 (bottom right). The three-joint swimmer was strongly impeded in
its ability to recover a high coverage collection of gaits post-injury. For
the four-joint swimmer, we showed the optimal policy before injury in trial 17
(top right), the consequence of a locked joint (grey dot) on the optimal
policy in trial 30 (top middle), and the optimal policy recovered while the
joint remains locked in trial 54 (bottom right). The four-joint swimmer was
not impeded in its ability to recover a high coverage collection of gaits
post-injury.

##  VIII Investigating the Ability of the Purcell Swimmer to Recover from
Joint Locking

In trials 30-60 of Figure 5, we tested the ability of the Purcell swimmer to
recover from simulated damage. We took the optimal collection of gaits from
the first 30 trials and found the joint that used the highest amplitude
behavior. We locked this joint at its value taken at the base point of the
parametrization. We then used this damaged optimal policy from the first 30
trials to start a on optimization leaving the damaged joints locked.

The two-joint swimmer was unable to move as a result of the injury. The three-
joint swimmer was able to partially recover. It was equipped with two
functional joints, yet was did not achieve the coverage scores of the un-
injured two-joint Purcell swimmer. The four-joint swimmers were notably better
at finding high coverage libraries during recovery than the three-joint
swimmers and remained within the standard deviation of performance of the
five-joint swimmers. The top row of Figure 6 details one optimization process
for a swimmer with three joints. It is clear that before injury, the swimmer
was able to achieve local poses. The injury greatly handicapped this ability,
even with the opportunity to recover. Likewise, the bottom row of Figure 6
details one optimization process for the swimmer with four joints. Before
injury, the four joint swimmer also found a useful gait library. The injury
clearly hindered its ability to move, but given the opportunity to recover,
the four joint swimmer found a new collection of behaviors with good coverage.

We interpret these results as follows. After damage, the two-joint swimmer was
left with one joint and was unable to move, possibly a consequence of the
scallop theorem in Stokesian systems [22]. The three-joint swimmer recovered
poorly, and did not come to match the performance of the undamaged two-joint
swimmer. This may suggest that the injury resulted in a body geometry that was
less amendable to producing good coverage than the conventional two-joint
Purcell swimmer. As we added more joints, the redundancy of joints both
minimized the dynamical impact of injury and provided a larger space of
solutions for recovery. The boxplots in Figure 5 suggest that at around five
or six joints, the coverage performance of the swimmer becomes robust to the
locking of a single joint.

Since all recovery processes took the same amount of time, we have a rare
result: adding actuated degrees of freedom improved our convergence and
recovery rates. Adding more freedom typically involves a substantial increase
in sampling requirements, both lengthening the convergence process and making
it less certain. In this example, convergence rate either improved or stayed
approximately the same as joints were added. Here, combining the methods of
[30] and the coverage metric allowed redundancy in the internal state to be an
asset for behavior optimization rather than a liability.

##  IX Implementation on Hardware

Here we communicate the general and noise-robust qualities of our approach by
optimizing coverage on real hardware with an unknown model. We did not have
explicit knowledge of the kinematics, mass distribution, or material
properties of this system when running the modeling and optimization
algorithms.

Figure 7: This robot (top right) was built from dynamixel modules and tree
branches available nearby (left and middle left). The trajectories showcase
the available 1 to 4 cycle motions of the system (bottom right) from the
robot’s origin before (green) and after (blue) the coverage optimization.

###  IX-A Methods on hardware

Inspired by the hardware used in [31], we foraged for tree branches. We
gathered these and sectioned the branches into robot appendages of a useable
size. We then constructed a robot by fixing tree branches to the endpoints of
a chain of three Robotis Dynamixel RX-64 actuators in modular cages. We
equipped the robot with 3 markers for our motion capture system (Qualisys Oqus
6 camera system); this provided us a observation of the position and
orientation of the robot. We connected the robot to a computer (Intel Xeon CPU
E3-1246 v3 running at 3.50GHz) running the gait modeling and optimization
algorithms. This connection used a CAT5 cable with 3 conductor pairs for power
and one pair for RS-485 serial communications. To build a physics model
centered at a given gait, we collect 20 cycles of noisy input data on the
robot and fit a regression informed by physics and geometry [30]. We then
compared the outcomes of two different optimizations for the $(x,y,\theta)$
outcomes of a gait or gaits, taking the position of the robot prior to
application of a gait cycle as the origin.

We performed two gait optimization experiments:

(1) Find one gait to move forward without turning: We designed a gait
optimization to maximize $x-y^{2}-\theta^{2}$ (per cycle) given the
coordinates of Figure 7 and units of body lengths ($\frac{1}{3}m$) and
radians.

(2) Find three gaits that optimize coverage in a volume of $\mathsf{SE}(2)$:
Given the ability to use the 3 gaits in up to 4 combined cycles, we designed a
gait library optimization to minimize the distance (computed on the Lie
group), from 125 points distributed across all combinations of coordinates
$x=[-1,-\frac{1}{2},0,\frac{1}{2},1]$, $y=[-1,-\frac{1}{2},0,\frac{1}{2},1]$,
$\theta=[-\frac{\pi}{2},-\frac{\pi}{4},0,\frac{\pi}{4},\frac{\pi}{2}]$. The
gray volume in Figure 7 contains all of the coverage points.

###  IX-B Results on hardware

For the first goal function, we seeded a zero motion gait oscillating the
middle joint with a sinusoidal input. We executed 15 iterations of our data-
driven gait optimization algorithm, each consisting of 20 cycles of motion.
Running at $\frac{1}{2}$Hz, each trial took 40 seconds. After the 8th
iteration, the robot was able to travel $40\%$ of its body length per cycle
with a turning rate of $0.10$ radians per cycle.

For coverage, we first completed an exploratory sampling of motions (12
cycles). From these 12 different gaits, we selected the subset of 3, which
performed the best on the coverage metric. After 5 iterations of trials (60
cycles, 20 for each gait), the system found a more complementary set of gaits
reducing the coverage score from 0.97 to 0.76.

##  X Discussion and Conclusions

In this paper, we introduced a new metric for the optimization of robot
motions. This metric involved calculation of the composition of motions from a
small library of primitives, determining their utility in “covering” some
region of the local body position space, formulated as a Lie group. What is
novel about this approach is that

  * •

It eliminated human bias from prescribing a limited set of allowable
primitives for a robot.

  * •

It allowed for the use of unconventional robot designs for navigation.

  * •

It allowed malfunctioning robots to quickly recover the ability to move
through space.

We showed the Purcell swimmers’ ability to recover from injury using the data-
driven geometric gait optimizer, guided by the coverage metric. Some
interesting trends emerged during these tests. The swimmers converged to a
high coverage gait library (containing three gaits) despite variation in the
number of links and initial gaits. This suggests insensitivity in the gait
optimization when using the coverage metric.

Furthermore, coverage allowed us to investigate the role that redundancy might
play in the ability of the swimmers to recover high coverage gait libraries
post-injury. We found that around four degrees of freedom, the addition of a
joint no longer provides a substantial change in the ability of the swimmer to
recover. The ability to apply this analysis to other robots could help inform
what degree of complexity is appropriate when designing a robot, and provide a
lower bound for how much recovery can be expected from different amounts of
damage.

Finally, using the coverage optimization on a robot made of tree branches we
were unable to find gaits that translate without substantial rotation. We were
able, however, to find a useful portfolio of maneuvers for navigation in 2D.
This machine learning task was solved on a timescale that is competitive with
an implementation of reinforcement learning by Google [32].

The tree branch robot example speaks to the morphology agnostic properties of
data-driven geometric gait optimization; this robot could be substituted with
robots of many other forms. As long as the system acts near the Stokesian
regime of locomotion, the methods of [30] assist in building behavioral models
that inform performance improvements. Interfacing the coverage optimization
metric to soft systems (where approaches to system identification have been
developed [33, 34]) could enable more reliable soft robots in hard to model
environments.

Taken together our results give strong evidence that optimizing for coverage
is a means for a robot to gain the ability to maneuver, and to recover this
ability after being damaged.

## Acknowledgement

Revzen and Bittner thank NSF CMMI 1825918, ARO W911NF-17-1-0306, D. Dan and
Betty Kahn Michigan-Israel Partnership for Research and Education Autonomous
Systems Mega-Project, and AOFSR FA9550-20-1-0238 for funding.

## References

  * [1] W. Walter  “THE LIVING BRAIN”  In _The Journal of Nervous and Mental Disease_ 120.1 Ovid Technologies (Wolters Kluwer Health), 1954, pp. 144  DOI: 10.1097/00005053-195407000-00069
  * [2] Mihail Pivtoraiko, Ross A. Knepper and Alonzo Kelly  “Differentially constrained mobile robot motion planning in state lattices”  In _Journal of Field Robotics_ 26.3 Wiley, 2009, pp. 308–333  DOI: 10.1002/rob.20285
  * [3] R.A. Knepper and M.T. Mason  “Path diversity is only part of the problem”  In _2009 IEEE International Conference on Robotics and Automation_ IEEE, 2009  DOI: 10.1109/robot.2009.5152696
  * [4] Ajo Fod, Maja J Matarić and Odest Chadwicke Jenkins  “Automated derivation of primitives for movement classification”  In _Autonomous robots_ 12.1 Springer, 2002, pp. 39–54  DOI: 10.1023/A:1013254724861
  * [5] E. Frazz, M.A. Dahleh and E. Feron  “Maneuver-based motion planning for nonlinear systems with symmetries”  In _IEEE Transactions on Robotics_ 21.6 Institute of ElectricalElectronics Engineers (IEEE), 2005, pp. 1077–1091  DOI: 10.1109/tro.2005.852260
  * [6] Stefan Schaal, Jan Peters, Jun Nakanishi and Auke Ijspeert  “Learning Movement Primitives”  In _Springer Tracts in Advanced Robotics_ Springer Berlin Heidelberg, 2005, pp. 561–572  DOI: 10.1007/11008941˙60
  * [7] Kris Hauser, Timothy Bretl, Kensuke Harada and Jean-Claude Latombe  “Using Motion Primitives in Probabilistic Sample-Based Planning for Humanoid Robots”  In _Springer Tracts in Advanced Robotics_ Springer Berlin Heidelberg, 2008, pp. 507–522  DOI: 10.1007/978-3-540-68405-3˙32
  * [8] Mihail Pivtoraiko and Alonzo Kelly  “Kinodynamic motion planning with state lattice motion primitives”  In _2011 IEEE/RSJ International Conference on Intelligent Robots and Systems_ IEEE, 2011  DOI: 10.1109/iros.2011.6094900
  * [9] Ross L Hatton and Howie Choset  “Optimizing coordinate choice for locomoting systems”  In _2010 IEEE International Conference on Robotics and Automation_ IEEE, 2010  DOI: 10.1109/robot.2010.5509876
  * [10] Chaohui Gong, Daniel I. Goldman and Howie Choset  “Simplifying Gait Design via Shape Basis Optimization”  In _Robotics: Science and Systems XII_ Robotics: ScienceSystems Foundation  DOI: 10.15607/rss.2016.xii.006
  * [11] Xingye Da et al.  “From 2D Design of Underactuated Bipedal Gaits to 3D Implementation: Walking With Speed Tracking”  In _IEEE Access_ 4 Institute of ElectricalElectronics Engineers (IEEE), 2016, pp. 3469–3478  DOI: 10.1109/access.2016.2582731
  * [12] Ross Hartley, Xingye Da and Jessy W. Grizzle  “Stabilization of 3D underactuated biped robots: Using posture adjustment and gait libraries to reject velocity disturbances”  In _2017 IEEE Conference on Control Technology and Applications (CCTA)_ IEEE, 2017  DOI: 10.1109/ccta.2017.8062632
  * [13] S.S. Sastry and R. Montgomery  “The Structure of Optimal Controls for a Steering Problem”  In _IFAC Proceedings Volumes_ 25.13 Elsevier BV, 1992, pp. 135–140  DOI: 10.1016/s1474-6670(17)52270-3
  * [14] Shankar Sastry  “Nonlinear systems: analysis, stability, and control”  Springer Science & Business Media, 2013  DOI: 10.1007/978-1-4757-3108-8
  * [15] E.. Purcell  “Life at low Reynolds number”  In _AIP Conference Proceedings_ AIP, 1976  DOI: 10.1063/1.30370
  * [16] Ross L. Hatton and Howie Choset  “Geometric Swimming at Low and High Reynolds Numbers”  In _IEEE Transactions on Robotics_ 29.3 Institute of ElectricalElectronics Engineers (IEEE), 2013, pp. 615–624  DOI: 10.1109/tro.2013.2251211
  * [17] Suresh Ramasamy and Ross L Hatton  “Soap-bubble optimization of gaits”  In _2016 IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 1056–1062  IEEE
  * [18] R.. Cox  “The motion of long slender bodies in a viscous fluid Part 1. General theory”  In _Journal of Fluid Mechanics_ 44.04 Cambridge University Press (CUP), 1970, pp. 791  DOI: 10.1017/s002211207000215x
  * [19] Matthew D. Kvalheim, Brian Bittner and Shai Revzen  “Gait modeling and optimization for the perturbed Stokes regime”  In _Nonlinear Dynamics_ 97.4 Springer ScienceBusiness Media LLC, 2019, pp. 2249–2270  DOI: 10.1007/s11071-019-05121-3
  * [20] Jennifer M Rieser et al.  “Geometric phase and dimensionality reduction in locomoting living systems”  In _arXiv preprint arXiv:1906.11374_ , 2019
  * [21] Suresh Ramasamy and Ross L. Hatton  “The Geometry of Optimal Gaits for Drag-Dominated Kinematic Systems”  In _IEEE Transactions on Robotics_ 35.4 Institute of ElectricalElectronics Engineers (IEEE), 2019, pp. 1014–1033  DOI: 10.1109/tro.2019.2915424
  * [22] Eric Lauga  “Life around the scallop theorem”  In _Soft Matter_ 7.7 Royal Society of Chemistry (RSC), 2011, pp. 3060–3065  DOI: 10.1039/c0sm00953a
  * [23] Scott D. Kelly and Richard M. Murray  “Geometric phases and robotic locomotion”  In _Journal of Robotic Systems_ 12.6 Wiley, 1995, pp. 417–431  DOI: 10.1002/rob.4620120607
  * [24] Jim Ostrowski and Joel Burdick  “The Geometric Mechanics of Undulatory Robotic Locomotion”  In _The International Journal of Robotics Research_ 17.7 SAGE Publications, 1998, pp. 683–701  DOI: 10.1177/027836499801700701
  * [25] S.D. Kelly and R.M. Murray  “The geometry and control of dissipative systems”  In _Proceedings of 35th IEEE Conference on Decision and Control_ IEEE  DOI: 10.1109/cdc.1996.574612
  * [26] A Shapere and F Wilczek  “Geometry of self-propulsion at low Reynolds number”  In _J Fluid Mech_ 198, 1989, pp. 557–585
  * [27] Ziyou Wu, Dan Zhao and Shai Revzen  “Coulomb Friction Crawling Model Yields Linear Force–Velocity Profile”  In _Journal of Applied Mechanics_ 86.5 ASME International, 2019  DOI: 10.1115/1.4042696
  * [28] G.. Clifton, D. Holway and N. Gravish  “Uneven substrates constrain walking speed in ants through modulation of stride frequency more than stride length”  In _Royal Society Open Science_ 7.3 The Royal Society, 2020, pp. 192068  DOI: 10.1098/rsos.192068
  * [29] Ross L Hatton and Howie Choset  “Geometric motion planning: The local connection, Stokes’ theorem, and the importance of coordinate choice”  In _The International Journal of Robotics Research_ 30.8 SAGE Publications Sage UK: London, England, 2011, pp. 988–1014
  * [30] Brian Bittner, Ross L. Hatton and Shai Revzen  “Geometrically optimal gaits: a data-driven approach”  In _Nonlinear Dynamics_ 94.3 Springer ScienceBusiness Media LLC, 2018, pp. 1933–1948  DOI: 10.1007/s11071-018-4466-9
  * [31] Azumi Maekawa et al.  “Improvised Robotic Design with Found Objects [ABSTRACT ONLY]”  In _Conference on Neural Information Processing Systems, Creativity Workshop_ , 2018  URL: https://azumi-maekawa.com/pdf/improvised_robotic_design_NeurIPS2018WS.pdf
  * [32] Sehoon Ha et al.  “Learning to Walk in the Real World with Minimal Human Effort”  In _arXiv preprint arXiv:2002.08550_ , 2020
  * [33] Daniel Bruder et al.  “Data-Driven Control of Soft Robots Using Koopman Operator Theory”  In _IEEE Transactions on Robotics_ 37.3 IEEE, 2020, pp. 948–961
  * [34] Brian Bittner, Ross L Hatton and Shai Revzen  “Data-Driven Geometric System Identification for Shape-Underactuated Dissipative Systems”  In _arXiv preprint arXiv:2012.11064_ , 2020