# Toward Certification of Machine-Learning Systems for Low Criticality
Airborne Applications

Konstantin Dmitriev  Technical University of Munich – Garching, Germany
Email<EMAIL_ADDRESS>Johann Schumann  KBR, NASA Ames Research
Center, Moffett Field, CA
Email<EMAIL_ADDRESS>Florian Holzapfel  Technical University of
Munich – Garching, Germany

Email<EMAIL_ADDRESS>
###### Abstract

The exceptional progress in the field of machine learning (ML) in recent years
has attracted a lot of interest in using this technology in aviation. Possible
airborne applications of ML include safety-critical functions, which must be
developed in compliance with rigorous certification standards of the aviation
industry. Current certification standards for the aviation industry were
developed prior to the ML renaissance without taking specifics of ML
technology into account. There are some fundamental incompatibilities between
traditional design assurance approaches and certain aspects of ML-based
systems. In this paper, we analyze the current airborne certification
standards and show that all objectives of the standards can be achieved for a
low-criticality ML-based system if certain assumptions about ML development
workflow are applied.

##  I Introduction

The European Union Aviation Safety Agency (EASA) has recently published a
roadmap [1] envisioning an increasing use of Artificial Intelligence (AI) and,
in particular, machine learning systems in commercial aviation in the near
future. Major application areas include autonomous flight, preventive
maintenance, and air traffic management.

However, some important aspects of machine learning principles are
incompatible with the requirements of aviation industry standards for safety
critical systems, such as granular traceability between requirements and
design, and appropriate metrics for structural coverage analysis. The
international technical committees EUROCAE WG-114 and SAE G-34 were recently
established to develop new industry standards to support development and
certification of aeronautical systems leveraging machine learning technology.
However, the formal consensus-based process for industry standard creation may
take many years, as was the case for the foundational airborne standards
DO-178C [2] and ARP-4754A [3], whereas there is an increasing need for ML
technology for airborne systems today.

This paper provides an analysis of certifiability of low-criticality
(ARP-4754A Design Assurance Level D) ML-based systems based on the existing
industry standards. The objectives and methods of the industry standards are
analyzed for applicability and satisfiability in the context of the proposed
development workflow for a machine learning component. This analysis is
intended to facilitate immediate deployment of machine learning technology in
low criticality airborne systems based on the existing regulatory framework
without a need for new regulations.

The rest of the paper is structured as follows: in Section II we provide an
overview of ML technology and discuss related work. Section III includes the
analysis of DO-178C standards with respect to ML technology. We first define
the relevant notions and assumptions about the ML development workflow. Then
we review in detail the objectives of the standards focusing on software of
low-criticality (DO-178C Level D). Section IV discusses other relevant
aerospace standards and their applicability to machine-learning based systems.
Finally, Section V summarizes the work and concludes with suggestions for
future work.

##  II ML Overview and Related work

In recent years, AI has gained tremendously in popularity and application
areas. Most traction was obtained by the use of deep neural networks (DNN) for
image analysis, object detection and classification, and natural speech
processing. Neural networks are a subclass of machine learning algorithms,
which themselves are a subclass of AI. Therefore, the notion of AI, ML, and
DNN are often used interchangeably. In this paper, we focus on DNNs.

In the area of (deep) neural networks, we usually distinguish between the
learning phase, where the (D)NN is presented with training data, and the
inference phase, where the trained network receives inputs (e.g., from a
camera or other sensors) and provides an estimate of the desired output.
Inside the neural network, the information is typically stored as vectors of
numbers, called weight parameters, or simply weights. These weights are
obtained during the execution of a training algorithm. Here, usually large
amounts of training data are used to set the weights in such a way that the
DNN provides best-possible estimates on test data.

There exist a large number of different learning regimes (e.g., unsupervised
or supervised learning, reinforcement learning) and numerous learning
algorithms. Also, the neural network can be trained during system development,
and the pre-trained network with frozen weight parameters can be used for
inference during operation. In contrast, online learning (or adaptation)
adjusts the network weights during operation. Thus, the system can learn and
adapt toward novel situations while in operation.

For our study, we restrict ourselves to the most popular type of neural
networks: a deep multilayer convolutional neural network, which is being
trained during development and not retrained during operation. Such a network
is defined by its architecture and the values of the weight and bias
parameters. Their values are the result of the learning process, using a given
set of training data and a given learning algorithm.

Typical examples (in the aerospace domain) for such a network include:

  * •

object detection and classification, based upon camera inputs, for example,
the detection of runway debris [4] and objects [5], of airport signs, or for
the avoidance of runway incursions [6].

  * •

NN-based control. Flight-control software can use neural networks for inner-
loop control (e.g., Intelligent Flight Control System [7]), or for efficient
calculation of aircraft dynamics [8]. Other examples include the use of neural
networks for Taxiing [9], or vision-based takeoff or landing [10].

  * •

Trajectory prediction. NNs can be used for 4D trajectory prediction [11] or
for on-board collision avoidance, e.g., ACAS Xu [12].

  * •

Pilot advisory systems [11].

  * •

Fault detection, diagnostics, and prognostics. Here, NNs are used to recognize
system faults, to reason about diagnoses, or to support component or system
prognostics [13, 14].

  * •

Natural language processing, e.g., to recognize ATC utterances [15, 16].

The operation of a neural network (or, more general, an ML component) on-board
an aircraft can have, depending on the application, an impact on safety and
performance. Developers of a safety-critical ML-based system have to address
numerous issues, ranging from suitable architecture selection, trust and
confidence, to testing and explainability [17]. Ultimately, any airborne
safety-critical system must be developed in compliance with stringent
certifications standards, which were released prior to the wide adoption of ML
and do not address specific aspects of ML technology.

The technical report [18] published by EUROCAE and SAE joint committee in 2021
identifies gaps in the existing certification standards with respect to ML
technology and discusses potential approaches to address the gaps, but without
detailed information on specific standards’ objectives. Another recent work
[19] includes a detailed analysis of ML-based system certification challenges
without proposing solutions.

There are multiple ongoing and completed research projects that tackle
different problematic aspects of ML design assurance, such as verification and
validation [20, 21], traceability [22], or coverage [23, 24]. However, novel
methods are often in their infancy and there is no systematic summary showing
how they will address all incompatibilities in existing standards.

##  III DO-178C and Machine Learning

DO-178C [2] is a foundational standard for aviation software development. It
specifies the objectives to be satisfied by software developers and provides
detailed guidelines for processes and activities to be implemented, as well as
the description of artifacts (data) to be produced for demonstrating a
necessary level of software assurance. DO-178C defines the following key terms
which we frequently use in this paper:

  * •

Objective – requirements that should be met to demonstrate compliance with
DO-178C.

  * •

Activity – task that provides a means of meeting the objectives.

  * •

Process – a collection of activities performed during the software life cycle
to produce a definable output or product.

  * •

Design Assurance Level (DAL, Software Level) – the designation that is
assigned to a component (e.g., software item) as determined by the system
safety assessment process. The software level establishes the rigor necessary
to demonstrate compliance with DO-178C.

  * •

Assurance – the planned and systematic actions necessary to provide adequate
confidence and evidence that a product or process satisfies given
requirements.

DO-178C defines _software levels_ from A to E, which correspond to the
categories of a software failure condition from ”Catastrophic” to ”No Safety
Effect”, respectively. The applicable objectives and independence requirements
vary depending on the level.

In this section we analyze the satisfiability of the DO-178C objectives for
the proposed machine learning development workflow. We focus on the Level D
software, for which a limited subset of objectives applies, and show that
Level D objectives can be satisfied in spite of major incompatibilities
between ML-based and traditional software development approaches.

###  III-A Proposed ML development workflow

In this study, we propose the following assumptions about the machine learning
development workflow:

  1. 1.

An ML-based system typically includes both ML-based components and traditional
software components (operating system, hardware support drivers, etc. –
further referred to as ’traditional’ components). This analysis is focused on
ML components only. For traditional non-ML software components, DO-178C
applies without modification.

  2. 2.

We do not consider adaptive ML systems, which can perform training while the
system is in operation and can change or evolve over time. Such ML techniques,
for example, based upon reinforcement learning [25] add another layer of
substantial complexity.

  3. 3.

In the analysis below, we consider a deep neural network as a representative
example of an ML-based system to demonstrate the key properties of ML-based
systems.

  4. 4.

We propose to implement the ML learning (training) at system level, and
provide a trained ML model to the software life cycle for implementation. A
typical algorithm for ML model (e.g., a DNN) is composed of simple arithmetic
operations and therefore can directly serve as low-level software
requirements, from which source code can be implemented. This assumption is
inspired by the MB Example 5 provided in DO-331 [26], which represents a
common industry practice of a model-based development approach. A neural
network, however, may require supplemental low-level requirements in
traditional format to enable translation to source code, for example, textual
specification of a mathematical library for matrix operation algorithms.

###  III-B Development processes

DO-178C development processes produce software requirements, design, source
code, executable object code, and associated trace data. There are multiple
known industry practices for the software development workflow, which can be
used to satisfy the objectives of DO-178C development processes, such as
waterfall, agile, model-based design approach, or a combination thereof [27].
The sequence and relationship of the development activities can vary depending
on the selected development workflow, but regardless of the workflow, strong
bi-directional traceability must be established and maintained between
requirements on all levels, source code, and test data (discussed in DO-178C,
Sections 5.5 and 6.5).

Traceability Issue. Traditional software is implemented by a programmer as
human-readable source code, which can be traced to certain requirements it
implements. In contrast, the functional behavior of an ML model is mainly
specified by a bulk of parameters (e.g., NN weights), which are automatically
adjusted by a learning algorithm during ML model training. It is assumed to be
practically impossible to map and trace values of these auto-tuned parameters
to specific functions implemented by the ML model, because an ML model is
generally not directly comprehensible by humans. As a result, the DO-178C
traceability objectives are not achievable for an ML model. This traceability
issue is one aspect of the more general ML explainability challenge [19].

However, since an ML model is positioned as representing only low-level
software requirements in the proposed workflow, the traceability issue has no
effect on Level D software, because objectives for low-level requirements do
not apply for Level D software. Table I includes details of analysis for each
software development objective applicable to Level D.

TABLE I: Software Development Objectives DO-178C / DO-331 Objectives | Software Levels | Analysis
---|---|---
| A | B | C | D | E |
1 |  High-level requirements (HLR) are developed. | x | x | x | x |  |  In the proposed ML workflow, a trained NN is provided from system level to software life cycle as Design Model, from which source code can be directly developed. In this case, as discussed in DO-331 MB.6.1.3, ”the guidance related to high-level requirements should be applied to the requirements from which the model is developed.” This objective can be achieved by developing system requirements specifying functional, operational, performance, and other applicable characteristics in traditional (e.g., textual) form using the applicable DO-178C guidelines for high-level requirements.
2 |  Derived high-level requirements are defined and provided to the system processes, including the system safety assessment. | x | x | x | x |  |  In the same manner as for the previous objectives, to achieve this objective, DO-178C guidelines for derived high-level requirements can be applied to system level requirements (from which then ML model is developed) expressed in traditional form.
3 |  Software architecture is developed. | x | x | x | x |  |  The software architecture defines the software components and their interfaces to enable appropriate grouping of the software functions. Given that a typical ML component (NN) is composed of simple sequential arithmetic operations, we assume that there is no need for an architectural breakdown of the ML function and it can be arranged as a single ML component. However, this objective still applies to traditional software components, which integrate with ML component and can be achieved using the applicable DO-178C guidelines for software architecture.
4 |  Low-level Requirements are developed. | x | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
5 |  Derived low-level requirements are defined and provided to the system processes, including the system safety assessment. | x | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
6 |  Source Code is developed | x | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
7 |  Executable Object Code and Parameter Data Item (PDI) Files, if any, are produced and loaded in the target computer. | x | x | x | x |  |  Activities for production and loading of executable object code and PDI files are not different between traditional software and ML components, DO-178C guidelines can be directly applied to achieve this objective.

###  III-C Verification Processes

The DO-178C verification process includes 43 objectives listed in the Tables
A-3 to A-7 of DO-178C. In the proposed development workflow, many objectives
can be achieved using tradition methods such as requirements-based testing,
reviews, and analysis of traditional artifacts (e.g., textual requirements,
source code, requirements-based test cases, and procedures). The most
problematic verification objectives with respect to ML technology relate to
coverage assessment and verification of ML model artifacts as discussed
hereafter.

Coverage issue. DO-178C requires assessment of (1) requirements coverage by
tests and (2) coverage of source code structure by tests. The first step is
intended to assess how well the created tests exercise the intended behavior
specified by software requirements (e.g., to confirm that tests exist for each
requirement). This is typically performed by review of tests and associated
requirements. The second step is intended to determine elements of the source
code structure that are not covered by requirements-based tests, which can
indicate unintended functionality in the source code or shortcomings in
requirements or tests.

  * •

In the proposed workflow, an ML model represents low-level software
requirements and therefore it must be evaluated how well tests cover the
requirements expressed by the ML model. However, as discussed above, an ML
model generally cannot be traced to requirements or tests because it is not
directly comprehensible by humans (explainability challenge). Therefore, it
becomes impossible to demonstrate test coverage of requirements expressed by
the ML model, and the corresponding DO-178C coverage objective is not
achievable.

  * •

The DO-178C metrics for structural coverage include statement, decision, and
modified condition/decision coverage (MC/DC). These metrics are efficient for
the control flow of traditional algorithms but are not representative for a
typical ML model implementation, which has a very simple control flow while
the functional behavior is embedded in the data arrays (in the NN domain
referred to as weights). As discussed in [28], ”a single randomly picked test
input was able to achieve 100% code coverage”. Consequently, even though the
DO-178C structural coverage objectives are achievable, they are generally not
representative for the ML source code. Additional activities have to be
performed to detect unintended functionality in the source code and achieve a
necessary level of confidence in correctness and completeness of requirements-
based tests.

ML model verification issue. As long as an ML model represents low-level
requirements (per the proposed workflow), the verification objectives of Table
A-4 of DO-178C apply. As discussed above, an ML model is generally not
directly comprehensible by humans, this impacts most of the applicable
verification objectives. For example, verification of accuracy, consistency,
and traceability is not feasible for non-comprehensible ML models with
traditional human review methods. However, ML model testing with test data
sets can be claimed to assist with some verification objectives, similar to
the simulation approach for model-based systems addressed in DO-331. This is
discussed in detail in Section IV.

Tables II and III include further analysis of the Level D verification
objectives listed in Tables A-3 and A-6 of DO-178C.

Tables A-4 (Software Design Verification), A-5 (Code Verification), and A-7
(Verification of Verification Results) of DO-178C include only three
objectives applicable to Level D:

  * •

”Software partitioning integrity is confirmed”. Partitioning techniques are
used to ensure isolation between software components of different levels. We
focus on Level D software in this study only, and therefore this objective
does not apply and is excluded from the analysis.

  * •

”Parameter Data Item File is correct and complete”. PDI files are intended to
influence the behavior of software without modifying its executable object
code. Examples include configuration tables and databases. Even though PDI may
seem relevant for capturing ML parameters (e.g., NN weights), this will
require one to verify ”all behavior of the Executable Object Code resulting
from the contents of the PDI File” (DO-178C, 6.6). Such a verification task is
practical for simple parameter sets of limited size but is deemed impossible
for the large non-comprehensible ML models (another fallout from the
explainability challenge). Hence, use of PDI is not envisioned for ML models
and this objective is excluded from the analysis.

  * •

”Test coverage of high-level requirements is achieved”. We assume that
traditional requirements-based testing will be used for high-level
requirements testing (see Objectives 1 and 2 in Table III), consequently the
conventional analysis methods (DO-178C, 6.6.4.1) can be used to achieve this
objective.

The important outcome of the objectives’ analysis is that neither traceability
nor ML verification issues prevent the fulfillment of the Level D objectives
if the proposed ML workflow is followed.

###  III-D Other Processes

In addition to development and verification processes, DO-178C specifies the
supporting processes: planning, configuration management, quality assurance
and certification liaisons processes. The objectives of these supporting
processes are mainly independent of the technology used for software
development and, as discussed hereafter, can be achieved for ML-based system
of any assurance level.

####  III-D1 Planning Process

The DO-178 planning process produces plans and standards that guide the
overall software life cycle. Planning process objectives are summarized in
Table A-1 of DO-178C and include definitions of the software life cycle, its
processes and activities, selection of the life cycle environment, addressing
additional considerations, and review and coordination of the developed plans.
The planning process is accomplished by development and review of plans and
standards, which should include all aspects specified in the process
objectives; there is no difference between a traditional and an ML-based
software life cycle. ML-specific considerations, which are not addressed in
DO-178C (such as traceability and coverage issues discussed above) have to be
covered by the applicant in the life cycle plans as additional considerations
(4.1.d of DO-178C).

####  III-D2 Configuration Management Process

The configuration management process is implemented in conjunction with all
other life cycle processes to ensure a ”defined and controlled configuration
throughout the software life cycle” (DO-178C). It includes data
identification, baseline establishment, change control, and data archiving
activities. DO-178C configuration management objectives are technology-
agnostic and can be applied to data of any nature. Therefore, all objectives
can be achieved for ML data using traditional methods. Special attention may
need to be taken for configuration management of large data sets which are not
typical in traditional software development.

####  III-D3 Quality Assurance and Certification Liaisons Processes

These are administrative processes intended to provide confidence that the
software life cycle is implemented in compliance with DO-178C and in
coordination with certification authorities. Objectives of these processes are
generally abstracted from the technologies used for development and can be
achieved for ML-based software in the same manner as for traditional software.

TABLE II: Software Requirements Verification Objectives DO-178C / DO-331 Objectives | Software Levels | Analysis
---|---|---
| A | B | C | D | E |
1 |  High-level requirements comply with system requirements. | i | i | x | x |  |  This objective is implicitly satisfied in the proposed ML workflow, because requirements, from which the ML model is developed, represent both system-level and high-level software requirements (see Item 1 under the Table MB.A-3 of DO-331).
2 |  High-level requirements are accurate and consistent. | i | i | x | x |  |  High-level requirements are expressed in traditional form (e.g., textual) in the proposed ML workflow and can be verified using standard review and analysis methods.
3 |  High-level requirements are compatible with target computer. | x | x |  |  |  |  This objective does not apply to Level D and is excluded from the analysis.
4 |  High-level requirements are verifiable. | x | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
5 |  High-level requirements conform to standards. | x | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
6 |  High-level requirements are traceable to system requirements. | x | x | x | x |  |  Same as the Objective 1, this objective is implicitly satisfied for the requirements from which ML model is developed.
7 |  Algorithms are accurate. | i | i | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
TABLE III: Testing Objectives DO-178C / DO-331 Objectives | Software Levels | Analysis
---|---|---
| A | B | C | D | E |
1 |  Executable object code complies with high-level requirements. | x | x | x | x |  |  In the proposed ML workflow, high-level requirements (from which the ML model is developed) are expressed in a traditional form, therefore the regular normal-range requirements-based testing approach described in DO-178C 6.4.2.1 can be applied to achieve this objective.
2 |  Executable object code is robust with high-level requirements. | x | x | x | x |  |  Same as for Objective 1, traditional robustness (abnormal range) requirements-based testing approach described in DO-178C 6.4.2.2 can be applied to achieve this objective.
3 |  Executable object code complies with low-level requirements. | i | i | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
4 |  Executable object code is robust with low-level requirements. | i | x | x |  |  |  This objective does not apply to Level D and is excluded from the analysis.
5 |  Executable object code is compatible with target computer. | x | x | x | x |  |  This objective can be achieved by execution of hardware/software integration tests in the target environment; there is no difference between ML and traditional components.

##  IV Other Applicable Standards

###  IV-A DO-331

DO-331 [26] is a supplement to the DO-178C standard, which provides additional
guidance when a model-based approach is used for software development and
verification. DO-331 provides modifications and additions to DO-178C
objectives and processes addressing special aspects of model-based design
approach. ML technology has certain similarities with the model-based design
described in DO-331:

  * •

the ML model is used to capture the intended functional behavior of a
(software) system being developed, i.e., the ML model can express system or
software requirements.

  * •

the ML model can be executed using test data sets to demonstrate certain ML
model properties (e.g., compliance with requirements, from which an ML model
is developed). This is similar to the model simulation concept described in
MB.4.4.4 of DO-331.

Based on these similarities, the assumption for positioning an ML model as
low-level software requirements is made (DO-331, MB example 5). Moreover, ML
model testing can be claimed as a means of compliance for most of the
verification objectives for low-level requirements (DO-331, Item 1 in MB.A-4).
In this case, some additional objectives for data set verification with
respect to correctness and completeness are imposed (similarly to additional
objectives for simulation cases described in MB.6.8.3.2 of DO-331). However,
ML model testing does not resolve the ML-specific traceability and coverage
issues.

###  IV-B DO-254

An ML-based system can be implemented using different types of electronic
hardware such as microprocessor/microcontrollers, programmable logic devices
(PLD), graphics processing units (GPU), or application specific integrated
circuits (ASICs). Guidance materials for airborne electronic hardware
development include DO-254 [29] complemented by the more recent EASA
CM–SWCEH-001 [30] and FAA Order 8110.105 [31], which provide more specific
guidance for modern hardware technologies such as highly-complex commercial
off-the-shelf (COTS) microprocessor/microcontrollers (e.g., with multi-core
processing units) or GPUs.

For ML systems implemented as software hosted on COTS microprocessors or
microcontrollers, development assurance of the core processing unit executing
ML software is covered by the application of DO-178C for software, and no
special hardware consideration is required with respect to ML (9.2 of [30]).

For ML systems implemented using PLD or ASIC, DO-254 with additional
considerations provided in [30] and [31] apply. The same traceability and
coverage issues that we described above for the DO-178C objectives are
relevant for the HDL language, which is typically used for PLD/ASIC design.
Nevertheless, for Level D hardware, traceability of low-level requirements is
not required (DO-254, Table A-1), and HDL coverage objectives do not apply
([30], 8.4.2.1). So, these issues do not affect the objectives for Level D
hardware.

DO-254 does not provide specific objectives for COTS GPUs and [30] guidance is
limited to airborne display applications only. This may not be the case for ML
applications, which may leverage GPUs in a broader context. However, the
existing guidelines for GPUs [30] do not introduce any additional objectives
for Level D systems. We consider that assurance of COTS GPUs can be handled in
the same manner as COTS microcontrollers and microprocessor (covered by the
application of DO-178C for ML software, e.g., CUDA source code). Same
arguments can be applied to neuromorphic processors. It must be noted, that
multi-core architectures typical for GPUs and neuromorphic processors are a
certification challenge on its own [32], which must be taken into account.

###  IV-C System level assurance standards

A system is defined in DO-178C as ”a collection of hardware and software
components organized to accomplish a specific function or set of functions”.
ARP4754A [3], the primary standard for design assurance at system level,
includes objectives for system level requirements and architecture definition
and validation, integration and verification of system components, as well as
generic configuration management, process assurance, and certification
objectives. These objectives are formulated as ’black-box’ goals, abstracted
from the technologies used for design, implementation, and assurance of system
components and therefore achievable for ML-based components using standard
methods.

##  V Conclusions and Future Work

We analyzed current industry standards for development of airborne software,
electronic hardware and systems with respect to low-criticality ML system of
design assurance Level D. We studied the incompatibilities between the
standards and aspects of ML technology, which may hinder the fulfillment of
the standards’ objectives: traceability, coverage, and ML model verification
issues. To mitigate these issues, we proposed the assumptions for an ML
development workflow, limiting the scope to non-adaptive, supervised learning
systems with a specific breakdown between system and software/hardware
artifacts inspired by the model-based design approach. Finally, we reviewed
the applicable objectives of the selected standards in the context of the
proposed workflow and have shown that under the proposed assumptions all
applicable objectives of DO-178C, DO-331, DO-254, and ARP-4754 can be achieved
for Level D ML-based systems using standard activities and methods.

For future work we are planning to extend the analysis to higher assurance
levels. We will study new techniques that might be able to address the
identified _explainability_ and _coverage_ issues. We also want to investigate
how the analysis can be extended toward online learning and adaptive systems.

Acknowledgments. We would like to thank Shanza Zafar, Kevin Schmiechen and
Pranav Nagarajan for the careful review of this paper and helpful feedback.

## References

  * [1] “Artificial intelligence roadmap. a human-centric approach to AI in aviation,” European Aviation Safety Agency, Tech. Rep., 2020.
  * [2] _Software Considerations in Airborne Systems and Equipment Certification_ , RTCA, Inc. Std. RTCA DO-178C, 2011.
  * [3] _Guidelines for Development of Civil Aircraft and Systems_ , SAE International Std. SAE ARP4754A, 2010.
  * [4] H. Xu, Z. Han, S. Feng, H. Zhou, and Y. Fang, “Foreign object debris material recognition based on convolutional neural networks,” _EURASIP Journal on Image and Video Processing_ , no. 21, 2018.
  * [5] J. P Sajeevan, P. Prasanna Kumar, S. G P, and S. Mishra, “DNN design for object detection in airport runway operations,” _International Journal of Advanced Science and Engineering_ , vol. 6, pp. 223–225, 12 2020.
  * [6] Z. Chen and J. Juang, “Mitigation of runway incursions by using a convolutional neural network to detect and identify airport signs and markings,” _Sensors and Materials_ , vol. 31, no. 12, pp. 3947–3958, 2019.
  * [7] J. Bosworth and P. Williams-Hayes, “Flight test results from the nf-15b intelligent flight control system (IFCS) project with adaptation to a simulated stabilator failure,” NASA, Tech. Rep. NASA/TM-2007-214629, 2007.
  * [8] Y. Yu, H. Yao, and Y. Liu, “Physics-based learning for aircraft dynamics simulation,” in _Proc. Conference of the Society for Prognostics and Health Management (PHM)_ , 2018.
  * [9] D. J. Fremont, J. Chiu, D. D. Margineantu, D. Osipychev, and S. A. Seshia, “Formal analysis and redesign of a neural network-based aircraft taxiing system with VerifAI,” in _Computer Aided Verification_ , S. K. Lahiri and C. Wang, Eds. Cham: Springer International Publishing, 2020, pp. 122–134.
  * [10] Y. Bicer, M. Moghadam, C. Sahin, B. Eroğlu, and N. Üre, “Vision-based UAV guidance for autonomous landing with deep neural networks,” 01 2019.
  * [11] “EASA Concept Paper: First usable guidance for Level 1 machine learning applications,” European Aviation Safety Agency, Tech. Rep., 2021.
  * [12] K. D. Julian, M. J. Kochenderfer, and M. P. Owen, “Deep neural network compression for aircraft collision avoidance systems,” _CoRR_ , vol. abs/1810.04240, 2018. [Online]. Available: http://arxiv.org/abs/1810.04240
  * [13] S. Heo and J. H. Lee, “Fault detection and classification using artificial neural networks,” _IFAC-PapersOnLine_ , vol. 51, no. 18, pp. 470–475, 2018, 10th IFAC Symposium on Advanced Control of Chemical Processes ADCHEM 2018\. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S2405896318320664
  * [14] J. Yang, Y. Guo, and W. Zhao, “Aircraft actuator fault diagnosis using deep learning based sparse representation and TSM,” in _2019 IEEE Aerospace Conference_ , 2019, pp. 1–9.
  * [15] Y. Lin, “Spoken instruction understanding in air traffic control: Challenge, technique, and application,” _Aerospace_ , vol. 8, no. 3, 2021. [Online]. Available: https://www.mdpi.com/2226-4310/8/3/65
  * [16] M. Lowry, T. Pressburger, D. A. Dahl, and M. Dalal, “Towards autonomous piloting: Communicating with air traffic control,” in _AIAA Scitech Forum_ , 2019, p. 2207.
  * [17] J. Schumann, P. Gupta, and Y. Liu, _Application of Neural Networks in High Assurance Systems: A Survey_. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 1–19. [Online]. Available: https://doi.org/10.1007/978-3-642-10690-3_1
  * [18] “Artificial intelligence in aeronautical systems. statement of concerns.” EUROCAE, Tech. Rep. AIR6988, 2021.
  * [19] H. Delseny, C. Gabreau, A. Gauffriau, B. Beaudouin, L. Ponsolle, L. Alecu, H. Bonnin, B. Beltran, D. Duchel, J.-B. Ginestet _et al._ , “White paper machine learning in certified systems,” _arXiv preprint arXiv:2103.10529_ , 2021.
  * [20] J. Zhang and J. Li, “Testing and verification of neural-network-based safety-critical control software: A systematic literature review,” _Information and Software Technology_ , vol. 123, p. 106296, 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0950584920300471
  * [21] M. Borg, C. Englund, K. Wnuk, B. Durán, C. Levandowski, S. Gao, Y. Tan, H. Kaijser, H. Lönn, and J. Törnqvist, “Safely entering the deep: A review of verification and validation for machine learning and a challenge elicitation in the automotive industry,” _CoRR_ , vol. abs/1812.05389, 2018. [Online]. Available: http://arxiv.org/abs/1812.05389
  * [22] V. Aravantinos and F. Diehl, “Traceability of deep neural networks,” 2019.
  * [23] Y. Sun, X. Huang, D. Kroening, J. Sharp, M. Hill, and R. Ashmore, “Structural test coverage criteria for deep neural networks,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 18, no. 5s, pp. 1–23, 2019.
  * [24] C.-H. Cheng, C.-H. Huang, and H. Yasuoka, “Quantitative projection coverage for testing ML-enabled autonomous systems,” in _International Symposium on Automated Technology for Verification and Analysis_. Springer, 2018, pp. 126–142.
  * [25] S. Heyer, D. Kroezen, and E.-J. V. Kampen, _Online Adaptive Incremental Reinforcement Learning Flight Control for a CS-25 Class Aircraft_ , 2020. [Online]. Available: https://arc.aiaa.org/doi/abs/10.2514/6.2020-1844
  * [26] _Model-Based Development and Verification Supplement to DO-178C and DO-278A_ , RTCA, Inc. Std. RTCA DO-331, 2011.
  * [27] K. Dmitriev, S. A. Zafar, K. Schmiechen, Y. Lai, M. Saleab, P. Nagarajan, D. Dollinger, M. Hochstrasser, F. Holzapfel, and S. Myschik, “A Lean and Highly-automated Model-Based Software Development Process Based on DO-178C/DO-331,” in _2020 AIAA/IEEE 39th Digital Avionics Systems Conference (DASC)_. IEEE, 2020, pp. 1–10.
  * [28] K. Pei, Y. Cao, J. Yang, and S. Jana, “DeepXplore: Automated whitebox testing of deep learning systems,” in _Proceedings of the 26th Symposium on Operating Systems Principles_ , ser. SOSP ’17. New York, NY, USA: Association for Computing Machinery, 2017, p. 1–18. [Online]. Available: https://doi.org/10.1145/3132747.3132785
  * [29] _Design Assurance Guidance for Airborne Electronic Hardware_ , RTCA, Inc. Std. RTCA DO-254, 2000.
  * [30] _Certification Memorandum. Development Assurance of Airborne Electronic Hardware_ , European Aviation Safety Agency Std. CM–SWCEH-001 Issue 01 Revision 02, 2018.
  * [31] _Simple and Complex Electronic Hardware Approval Guidance_ , U.S. Federal Aviation Administration Std. ORDER 8110.105A, 2017.
  * [32] W. Matters and I. River, “Certification of avionics applications on multi-core processors: Opportunities and challenges,” 2018.


# Transition Motion Planning for Multi-Limbed Vertical Climbing Robots Using
Complementarity Constraints

Jingwen Zhang1, Xuan Lin1, and Dennis W Hong1 1Robotics and Mechanisms
Laboratory (RoMeLa), Department of Mechanical and Aerospace Engineering,
University of California Los Angeles, CA 90095<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In order to achieve autonomous vertical wall climbing, the transition phase
from the ground to the wall requires extra consideration inevitably. This
paper focuses on the contact sequence planner to transition between flat
terrain and vertical surfaces for multi-limbed climbing robots. To overcome
the transition phase, it requires planning both multi-contact and contact
wrenches simultaneously which makes it difficult. Instead of using a
predetermined contact sequence, we consider various motions on different
environment setups via modeling contact constraints and limb switchability as
complementarity conditions. Two safety factors for toe sliding and motor over-
torque are the main tuning parameters for different contact sequences. By
solving as a nonlinear program (NLP), we can generate several feasible
sequences of foot placements and contact forces to avoid failure cases. We
verified feasibility with demonstrations on the hardware SiLVIA, a six-legged
robot capable of vertically climbing between two walls by bracing itself in-
between using only friction.

##  I INTRODUCTION

With many degrees of freedom, legged robots present an intriguing capacity for
versatile motions in complex environments, such as disaster sites for search
and rescue missions, and construction sites for maintenance. ZMP-based methods
[1] [2] provide a good starting point by assuming that the robot’s contacts
are co-planar. However, those scenes mentioned obviously involve uneven
terrains and interactions with objects that require non-coplanar contacts.
Many different locomotion strategies [3] [4] [5] [6] are developed to handle
uneven terrains and even obstacles with moderate height. However climbing is
inevitable when faced tall obstacles, such as natural tunnels and man-made
pipelines.

Figure 1: Proposed transition motion planner (red) is able to generate various
motions in order to overcome the transition phase between grounds and walls.

Many climbing robots [7] [8] [9] start by using gecko-type grippers or micro-
spine grippers inspired by animals. Those designs make the system complex and
task-specific. Planning climbing motions generally remains a challenging task
for legged locomotion since it involves planning both multi-contact and
contact wrenches simultaneously, especially when climbing more cluttered
environments. The classical graph search method is used by [10] in order to
plan the motion on one single wall. Our previous work [11] presents another
approach which is based on optimization methods but the pre-determined contact
sequence is required. Both methods assume that the initial condition of the
robot on the wall is known and human operators are able to guarantee the
initial setup at the beginning of the task. However, this assumption can be
violated during an autonomous vertical wall climbing with minimal human
intervention. Given the end posture of ground trajectory and initial posture
of on-wall trajectory, the transition phase between ground and walls remains
an open yet important question displayed in Fig. 1.

When planning climbing motions including the transition motion with contact,
the intuitive approach is to pre-specify a contact sequence, and then optimize
the trajectory for the fixed sequence. However, the number of possible
sequences grows exponentially with the number of contact points which makes it
difficult for operators to select an optimal one and challenges the discrete
search methods in many cases [12]. Multi-contact planning by nonlinear
programming (NLP) can avoid the combinatorial explosion of contact switching.
[13] presents a method to optimize over the discrete gait sequence using
continuous variables through parameterization. By exploiting the
complementarity condition between contact force and the distance to contact,
[14] and [15] formulate it as a direct trajectory optimization problem for
walking and jumping. In this paper we apply the same complementarity
constraint to our motion planner and extend it to overcome the transition
phase between the ground and walls.

This paper presents an NLP problem with complementarity constraints in order
to explore different contact sequences during the transition phase given
different setups, _e.g._ , friction coefficients and motor torque limitations.
Since the climbing motion for more complex, high degree-of-freedom robots is
still quasi-static [9], the terms related to the derivative of momentum in the
robot model are ignored. Besides the complementarity constraint between the
contact force and the distance to contact, we also provide an optional
complementarity constraint to capture the limb switchability, which describes
whether the status (active/inactive) of one limb’s contact should be switched,
in order to mitigate the local minima issue in this problem. Safety factors
for wall climbing are first proposed in our previous work [11]. In this paper,
we introduce the two safety factors, one for toe sliding and another for motor
over-torque, into the algorithm and make them the main tuning parameters to
reduce the gap between our planner and the hardware experiments, _e.g._ ,
inaccurate friction coefficients and motor heating problems. Although with
strong nonlinearity from complementarity constraints, the sparsity of the
resulting problem enables us to get efficient (locally optimal) solutions with
solvers such as SNOPT [16]. We implement the resulting solutions directly on
our hardware SiLVIA and verify the feasibility with demonstrations on several
different experiments. To the best of our knowledge, this is the first hexapod
robot who can overcome the transition phase between the ground and walls in
the real world with regular end effectors that only use frictional forces.

This paper is organized as follows. In Section II we describe the simple model
and introduce variations of our constraints in the formulation. In Section
III, we show our results on SiLVIA performing a variety of transition motions
between the wall and the ground. We conclude the discussion in Section IV.

##  II APPROACH

When a legged robot is moving from supporting by the ground reaction force to
bracing itself between walls with only frictional forces, static equilibrium
constraints are typically used with the assumption of quasi-static movements
in order to ensure the stability. Kinematic reachability and dynamic
constraints like forcing contact forces inside of a friction cone are
important as well for feasible planning.

###  II-A Static Equilibrium Constraint

Generally, legged robots with $n$ joints will be treated as an underactuated
system with a total of $n+6$ degrees of freedom (DOF) since the floating base,
which is often the body of a robot, cannot be controlled directly. The
additional DOF will be determined by wrenches (force/torque) applied on the
robot including contact wrenches and gravity. According to the centroidal
dynamics [17], we can represent them as linear and angular momentum at the
center of mass (COM). Climbing on the wall only with the friction generated by
regular end-effectors, like the point-contact toe, requires large motor
torques which is prone to causing over-torque. The additional acceleration
(linear/angular) of the body will burden motors significantly. For safety
consideration, quasi-static movements where the derivative of linear and
angular momentum can be negligible are presumed for our applications. With
this assumption, the robot is subject to the static equilibrium constraint for
every round $j$ where $j=1,\ldots,M$ and $M$ is the total rounds to be
planned.

$\displaystyle\sum^{N}_{i=1}\boldsymbol{f}_{i,j}+m\boldsymbol{g}=\boldsymbol{0}$
(1a)
$\displaystyle\sum^{N}_{i=1}(\boldsymbol{p}_{i,j}-\boldsymbol{c}_{j})\times\boldsymbol{f}_{i,j}+\boldsymbol{\lambda}_{i,j}=\boldsymbol{0}$
(1b)

where $m$ is the total mass of the robot,
$\boldsymbol{c}_{j}\in\mathbb{R}^{3}$ is the COM position,
$\boldsymbol{p}_{i,j}\in\mathbb{R}^{3}$ and
$(\boldsymbol{f}_{i,j},\boldsymbol{\lambda}_{i,j})\in\mathbb{R}^{6}$ denote
the position and contact wrench for the $i^{th}$ leg ($N$ is the total number
of limbs), with respect to the world frame. The contact wrench will be kept at
zero if the contact is inactive.

###  II-B Reachability

Given a legged robot, the design will put a variety of constraints on the
motion of the robot geometrically. For every round $j$, given the COM position
$\boldsymbol{c}_{j}\in\mathbb{R}^{3}$ and the body orientation
$\boldsymbol{\Theta}_{j}\in\mathbb{R}^{3}$, we can specify the limb
reachability as follows:

$\boldsymbol{p}_{i,j}\in\mathcal{R}(\boldsymbol{c}_{j},\boldsymbol{\Theta}_{j})$
(2)

where the set $\mathcal{R}(\boldsymbol{c}_{j},\boldsymbol{\Theta}_{j})$ can be
expressed explicitly with either analytical expressions by introducing
additional decision variables joint angles $\boldsymbol{\theta}_{i,j}$ for
each leg $i$, or approximated ranges. With full kinematics model, we can
express the constraint (2) exactly as follows:

$\displaystyle\boldsymbol{p}_{i,j}=\phi_{FK}(\boldsymbol{\theta}_{i,j})$ (3a)
$\displaystyle\boldsymbol{\theta}_{min}\leq\boldsymbol{\theta}_{i,j}\leq\boldsymbol{\theta}_{max}$
(3b)

where $\phi_{FK}(\cdot)$ and $\boldsymbol{J}(\boldsymbol{\theta}_{i,j})$
denote the forward kinematics and Jacobian matrix for each leg,
$\boldsymbol{\theta}_{min}$ and $\boldsymbol{\theta}_{max}$ describe the
physical joint limitations. Although full kinematics model enables rich
constraints including the position/orientation of every end-effector and
explicit joint limitation, it will increase the computational expense with
additional decision variables and high nonlinearility introduced by forward
kinematics and Jacobian matrix. With proper approximated ranges, we can still
capture the physical meanings behind those constraints although it will be
more conservative. For the reachability (2), we can approximate the leg
reachable workspace as a sphere around the nominal posture which can be
expressed as:

$\left\lVert\boldsymbol{p}_{i,j}-\boldsymbol{c}_{j}-\boldsymbol{R}(\boldsymbol{\Theta}_{j})\boldsymbol{v}\right\rVert_{2}\leq\Delta_{FK}$
(4)

where $\boldsymbol{v}$ denotes the offset from COM to the housing location of
legs on the body, $\boldsymbol{R}(\boldsymbol{\Theta}_{j})$ is the body
rotation matrix represented by Euler angles, and $\Delta_{FK}$ is the radius
of the approximated sephere. Furthermore, the step size of both the body and
limbs is considered to ensure the reachability between rounds as follows:

$\displaystyle|\Delta\boldsymbol{c}|\leq\Delta\boldsymbol{c}_{max}$ (5a)
$\displaystyle|\Delta\boldsymbol{\Theta}|\leq\Delta\boldsymbol{\Theta}_{max}$
(5b) $\displaystyle|\Delta\boldsymbol{p}_{i}|\leq\Delta\boldsymbol{p}_{max}$
(5c)

where $\Delta\boldsymbol{c}_{max}$, $\Delta\boldsymbol{\Theta}_{max}$ and
$\Delta\boldsymbol{p}_{max}$ denote maximum stepsizes for the body’s linear
translation, rotation and maximum limb stride length respectively.

###  II-C Contact Wrench

Since wall climbing is a high-risk task, being conservative on the choice of
contact wrenches is necessary for safety of both the robot and the operator.
Two safety factors are defined as follows in order to deal with the friction
coefficient $\mu$ which is hard to be measured precisely and the motor torque
limit $\tau_{max}$ which can degenerate by heating. More details can be seen
in our previous work [11].

$\displaystyle S_{\mu}$ $\displaystyle=\mu/\mu_{c}$ (6) $\displaystyle
S_{\tau}$ $\displaystyle=\tau_{max}/\tau_{c}$ (7)

where $\mu_{c}$ and $\tau_{c}$ denote the critical values for safety. For our
algorithm, critical values are not determined experimentally. Instead, we
accept $S_{\mu}$ and $S_{\tau}$ as two main tuning parameters and being
conservative can be achieved via keeping $S_{\mu}\geq 1$ and $S_{\tau}\geq 1$.
Similarly, the constraint on contact wrench can include two parts, one from
the motor torque limits and another from the friction cone.

$\boldsymbol{f}_{i,j}\in\mathcal{F}_{\tau}(\tau_{max},\boldsymbol{J}(\boldsymbol{\theta}_{i,j}),S_{\tau})\cap\mathcal{F}_{\mu}(\mu,S_{\mu})$
(8)

where the contact torque is not included for consideration since most legged
robots are assumed point contact generally (multiple point contacts at corners
of the sole are used for humanoids). If the torque can be generated by the
end-effector and is controllable, it is easy to modify the contraint (8).
Actually, the contact torque is very important for stability of a few contact
sequences which we will see in Section III. The friction cone can be expressed
as follows:

$\mathcal{F}_{\mu}(\mu,S_{\mu})=\left\\{\boldsymbol{f}_{i,j}\mid\left\lVert(\boldsymbol{f}^{c}_{i,j})_{x,y}\right\lVert^{2}_{2}\leq\mu(\boldsymbol{f}^{c}_{i,j})_{z}/S_{\mu}\right\\}$
(9)

where $\boldsymbol{f}^{c}_{i,j}$ denotes the contact force for the $i^{th}$
leg in the $j^{th}$ round with respect to the contact frame as shown in Fig.
2. $(\cdot)_{x,y}$ extracts the $x$ and $y$ components while $(\cdot)_{z}$ is
the $z$ component of the vector. In terms of the set
$\mathcal{F}_{\tau}(\tau_{max},\boldsymbol{J}(\boldsymbol{\theta}_{i,j}),S_{\tau})$,
two explicit options are provided similar to Section II-B. Based on full
kinematics model, we can express it as:

$\displaystyle\boldsymbol{\tau}_{i,j}=\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}\boldsymbol{f}_{i,j}$
(10a)
$\displaystyle\boldsymbol{\tau}_{i,j}\leq\boldsymbol{\tau}_{max}/S_{\tau}$
(10b)

where $\boldsymbol{\tau}_{i,j}$ denotes required torques of motors on the
$i^{th}$ leg. We can also assume all actuators have the same torque limit
$\tau_{max}$ which is a scalar value so that we require the maximum of joint
torques not to exceed the relaxed limit during operation,

$\left\lVert\boldsymbol{\tau}_{i,j}\right\rVert_{\infty}\leq\tau_{max}/S_{\tau}$
(11)

With the inequality
$\left\lVert\boldsymbol{\tau}_{i,j}\right\rVert_{\infty}\leq\left\lVert\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}\right\rVert_{\infty}\left\lVert\boldsymbol{f}_{i,j}\right\rVert_{\infty}$
from Eq. (10a), we can set the right-hand side of Eq. (11) as a conservative
upper bound for
$\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}_{\infty}\left\lVert\boldsymbol{f}_{i,j}\right\rVert_{\infty}$,
and the following relation can be obtained:

$\left\lVert\boldsymbol{f}_{i,j}\right\rVert_{\infty}\leq\frac{\tau_{max}}{S_{\tau}\underset{\boldsymbol{\theta}_{i,j}}{\textit{max}}\left\lVert\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}\right\rVert_{\infty}}$
(12)

and for a robot, we can treat the value of
$\underset{}{\textit{max}}\left\lVert\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}\right\rVert_{\infty}$
as a constant by searching all possible $\boldsymbol{\theta}_{i,j}$ offline.

Figure 2: Illustration of the world frame $\\{w\\}$ and the local contact
frame $\\{c\\}$. Solid dots indicate toes on the wall while the hollow one
indicates the swing leg. Inside the red box is the complementarity condition
between contact distance $(\boldsymbol{p}^{c}_{i,j})_{z}$ and the normal
contact force $(\boldsymbol{f}^{c}_{i,j})_{z}$. Inside the blue box is the
limb compliance for indirect force control of SiLVIA.

###  II-D Unscheduled Contact Sequence and Limb Switchability

As discussed previously in Section I, we apply the same idea of [14]
exploiting the complementarity condition between the contact distance and the
contact force to our motion planning algorithm. As shown in Fig. 2, the
contact force can be generated only when the contact distance is zero.
Therefore, either the contact distance $(\boldsymbol{p}^{c}_{i,j})_{z}$ or the
normal contact force $(\boldsymbol{f}^{c}_{i,j})_{z}$ will be zero which can
be express as:

$\displaystyle(\boldsymbol{f}^{c}_{i,j})_{z}\geq
0,\quad(\boldsymbol{p}^{c}_{i,j})_{z}\geq 0$ (13a)
$\displaystyle(\boldsymbol{f}^{c}_{i,j})_{z}(\boldsymbol{p}^{c}_{i,j})_{z}=0$
(13b)

It is noted that the complementarity condition between the contact distance
and the contact torque which can be expressed as
$\lVert{\lambda}^{c}_{i,j}\rVert^{2}(\boldsymbol{p}^{c}_{i,j})_{z}=0$ is
ignored here for the point contact assumption. In this way, we can use only
continuous variables in the optimization problem and search over all possible
contact sequences at once.

Furthermore, we also provide an optional complentarity constraint for limb
switchability. If we use the same leg for supporting the weight during the
transition phase for too many rounds which means a long period, it is likely
for motors of that leg to over torque due to heating. In order to reduce this
risk, we can force the motion planner to switch supporting legs between
rounds, expressed as follows:

$\text{for
$j=2,\dots,M$},\quad(\boldsymbol{f}^{c}_{i,j-1})_{z}(\boldsymbol{f}^{c}_{i,j})_{z}=0$
(14)

If one leg is used to generate nonzero contact force in the prior round, the
complentraity condition will force the normal contact force of the same leg
for the current round to be zero which means this leg will not be one of
supporting legs. The observation here is that it will also sacrifice some
richness in the possible transition motions. Without the constraint (14), we
can generate more feasible contact sequences which can be seen from our
results in Section III.

###  II-E Complete NLP formulation

With all constraints described previously, we can choose the decision
variables for the $j^{th}$ round as:

$\mathit{\Gamma}=\left\\{\boldsymbol{p}_{i,j},\boldsymbol{f}_{i,j},\boldsymbol{c}_{j},\boldsymbol{\Theta}_{j}\right\\}$
(15)

If the explicit form of constraints on reachability and the motor torque
limits is chosen as Eq. (3) and Eq. (10), additional decision variable
$\boldsymbol{\theta}_{i,j}$ will be required. Similarly,
$\boldsymbol{\lambda}_{i,j}$ can be introduced if consider contact torques
explicitly.

In terms of the cost function, a terminal cost and intermediate costs are
included. To prepare the robot ready for wall-climbing during transition
motion planning, we command the robot to reach the initial posture of the
following climbing trajectory which is our terminal condition. Intermediate
costs are composed of stepsize penalty and the $L_{1}$ norm of contact force.
Unlike the $L_{2}$ norm of contact force which would encourage evenly
distributed forces, the $L_{1}$ norm would favor sparse solutions which is
what we expect from complementarity constraints. The full NLP formulation can
be expressed as:

$\begin{aligned} &\begin{aligned}
\underset{\Gamma}{\textbf{minimize}}\quad&\sum^{N}_{i=1}|\boldsymbol{p}_{i,M}-\boldsymbol{p}_{i,d}|^{2}_{Q_{p}}+\sum^{M}_{j=2}(|\Delta\boldsymbol{c}_{j}|^{2}_{Q_{c}}\\\
&+|\Delta\boldsymbol{\Theta}_{j}|^{2}_{Q_{\Theta}}+\sum^{N}_{i=1}|\Delta\boldsymbol{p}_{i,j}|^{2}_{Q_{\Delta}}+|\boldsymbol{f}_{i,j}|^{2}_{L_{1}})\end{aligned}\\\
&\text{subject to \eqref{const:static}, \eqref{const:reachability},
\eqref{const:stepsiz}, \eqref{const:wrench}, \eqref{const:comple},
\eqref{const:switchability} (optional)}\\\ \\\ \end{aligned}$

where $|\cdot|^{2}_{Q}$ is the abbreviation for the quadratic cost with the
weight matrix as $Q\geq 0$, $\boldsymbol{p}_{i,M}$ and $\boldsymbol{p}_{i,d}$
denote the position at the last round $M$ and desired position for the
$i^{th}$ leg respectively. Note that we could also add the contact position
assignment as a constraint represented by
$\boldsymbol{A}\boldsymbol{p}_{i,j}\leq\boldsymbol{b}$ where $\boldsymbol{A}$
and $\boldsymbol{b}$ describe the convex hull of feasible contact regions.

###  II-F Indirect Force Control for SiLVIA

After solving our transition motion planner with SNOPT, the robot is able to
accomplish the transtion task from the ground to the wall round by round by
commanding the optimized leg positions and contact forces. If the robot has
force feedback on the end-effector of each leg, direct force control would
work easily. Unfortunately, our robot SiLVIA is position controlled. For
multi-limbed robots like SiLVIA, contact forces are statically indeterminate
if more than 3 contacts are active. In [18], the virtual penetration into the
wall $\boldsymbol{\delta_{wall}}$ and the body deformation
$\boldsymbol{\delta_{com}}$ as shown in Fig. 2 are considered to determine
contact forces indirectly. The optimized contact force $\boldsymbol{f}_{i,j}$
from our transition motion planner can be treated as the spring force using
the Virtual Joint Method (VJM) [19]. In order to achieve the contact force at
the $i^{th}$ leg for the $j^{th}$ round, we need to solve a feasibility
problem as follows:

find $\displaystyle\boldsymbol{\delta_{wall}},\boldsymbol{\delta_{com}}$ (16)
$\displaystyle\boldsymbol{f}_{i,j}=\boldsymbol{K}_{i,j}(\boldsymbol{\delta_{wall}}-\boldsymbol{\delta_{com}})$
(16a)
$\displaystyle\boldsymbol{K}_{i,j}=(\boldsymbol{J}(\boldsymbol{\theta}_{i,j})\boldsymbol{k}^{-1}\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top})^{-1}$
(16b)

where $\boldsymbol{K}_{i,j}$ is the stiffness matrix of the $n$ DOF leg,
$\boldsymbol{k}$ is the diagonal matrix with the virtual spring coefficients
$[k_{1},k_{2},\ldots,k_{n}]$ of the position controller motors. Since
$\boldsymbol{\theta}_{i,j}$ can be find after transition motion planner, only
$\boldsymbol{\delta_{wall}}$ and $\boldsymbol{\delta_{com}}$ are unknown.
Problem (16) can be solved efficiently. Therefore indirect force control can
be achieved by adding $\boldsymbol{\delta_{wall}}$ to optimized leg positions
$\boldsymbol{p}_{i,j}$ which is what we have done for the following
experiments.

##  III RESULTS

In this section, we presents several different scenarios about transition
between the wall and the ground, including the parallel wall, the parallel
wall with steps or inclines, and the circular wall. Without losing generality,
we also try to explore walking gaits on the ground. With the proposed
transition motion planner, we choose Eq. (4) and Eq. (12) to represent the
constraint (2) and (8) respectively in order to reduce the computational cost.
The constant
$\underset{}{\textit{max}}\left\lVert\boldsymbol{J}(\boldsymbol{\theta}_{i,j})^{\top}\right\rVert_{\infty}$
is determined offline as 963.5 mm. Results are implemented on the six-legged
robot SiLVIA weighted around 10 kg, each leg of which has 3 DOF. A pair of
Dynamixel MX-106 motors is used for each joint which can provide a maximum
torque at 27 Nm. For the resulting contact sequence, B-spline is used for
interpolation and we can generate the trajectory for the independent joint PID
controller. All hardware demonstrations can be viewed in the accompanied
video.

###  III-A The Parallel Wall

In this scenario, we let the robot stand between two parallel walls at a
distance of 1230 mm. Initially, the robot stands on the ground with the body
height as 210 mm. The desired configuration on the wall is the starting point
of the climbing trajectory from our previous work [11] indicated in Fig. 3 as
the translucent configuration.

Figure 3: Simulation visualization of 3 different resulting contact sequences.
The red arrow inside each graph denotes the gravity while blue arrows indicate
contact forces. The translucent model is the desired configuration for
transition. Red path represents 3-3 contact sequence. Green path represents
2-4 contact sequence with small $S_{\tau}$. Blue path represents 4-2 contact
sequence with large $S_{\mu}$.

In the hardware experiment, the walls are covered by rubber pads and the robot
toes are covered by anti-slip tapes, which gives a frictional coefficient
$\mu$ around 1. With the nominal values for safety factors ($S_{\tau}=1.8$,
$S_{\mu}=1.1$), the tripod gait (3-3 contact sequence) which lifts the front
and rear legs on one side, the middle leg on the other side firstly, and then
lifts the remaining 3 legs, is generated and validated in the robot as seen in
Fig. 1. In the following, the two safety factors are tuned to simulate
different experimental setups although the real environment for hardware
demonstrations is kept the same. For the planner, we make the wall surface
more slippery by increasing the value of $S_{\mu}$. When $S_{\mu}\approx
1.46$, the resulting solution shows the robot would lift two front and two
rear legs for the first round, and then lift two remaining middle legs to the
wall (4-2 contact sequence in Fig. 3). We also increase the motor torque limit
by decreasing $S_{\tau}$ to pretend that the robot has stronger motors. 2-4
contact sequence is generated when $S_{\tau}$ becomes around 0.85. Actually,
this is an aggressive setting for our robot since the torque density needs to
be $1/0.85$ times larger in order to execute the resulting solution
successfully in the hardware. It is noted that with smaller $S_{\tau}$, both
3-3 contact sequence and 4-2 contact sequence are also feasible local minimas
of the NLP planner. With a different initial guess, the planner would converge
to a different local minima.

The interesting observation in the hardware experiment is that the robot tips
over for those two contact sequences (2-4 and 4-2). In terms of the 4-2
contact sequence, falling down happens when lifting those 4 legs as indicated
in Fig. 4. The reason is that when the robot only has 2 legs generating
contact forces, they need to be perfectly aligned in order to avoid any
torques applied on the body. The better strategy is to include the contact
torque in the planner. However, SiLVIA only has 3 DOF each leg which means the
contact torque on the end-effector cannot be controlled directly. We simply
replace the point-contact toe with a bar to be robust passively and it
performs the 4-2 contact sequence successfully. For the 2-4 contact sequence,
the robot suffers from not only the same issue as noted above but also the
over-torque problems for the two legs on the wall.

Figure 4: (a) Failure with point-contact toes for the two middle legs. (b)
Success with bar toes for the two middle legs.

Furthermore, we ignore the limb switchability constraint (14) in order to
explore more possible contact sequences. A new contact sequence (2-2-2 contact
sequence) is generated by our planner. The robot would lift the left middle
leg (LM) and the right middle leg (RM) initially, then lift the left front leg
(LF) and the right rear leg (RR) with 4 legs for supporting (2 on the ground
and 2 on the wall), and finally lift the remaining two legs to the wall. From
Fig. 5, the complementarity constraint (13) is always satisfied. For example,
the contact distance of the leg RM at the round 1 is 0 while the contact force
is 0 for the round 2. Note that the leg RM is already on the wall after the
round 2 (the desired height of the leg on the wall is 180 mm). For rounds 3, 4
and 5, the contact distance of the leg RM is 0 with respect to the contact
frame which still keeps the complementarity condition. The hardware
demonstration shows that the 2-2-2 contact sequence provides stronger
stability of the transition motion since the robot always keeps at least 4
contact points.

Figure 5: The resulting z-component of the contact forces and toe positions
with respect to the world frame without limb switchability constraint. Shaded
areas indicate the contact is active for the leg.

###  III-B The Parallel Wall with Steps

This scenario focuses on investigating whether our planner can generate the
contact sequence taking advantage of objects presented in order to overcome
the transition phase. We put two bricks next to the left wall on the ground
and intuitively the robot would be able to step on the brick for the
intermediate round. To take advantage of the brick, we decrease the value of
$\Delta_{FK}$ in the constraint (4) for the legs on the left side until the
leg is unable to reach the desired positions on the wall in one step. The
3-3-3 contact sequence is generated which puts LF and LR on the brick and RM
on the right wall, then moves RF, RR and LM on the wall, finally moves LF, LR
and RM again to the desired positions on the wall, as shown in Fig. 6.
However, in the hardware experiment, the robot tips over when it is trying to
lift 3 legs based on the supporting from 2 legs on the brick and 1 leg on the
wall. The two legs on the brick (LF and LR) slip causing the failure. The
reason is that the friction coefficient between the brick and the toe is much
smaller than the one between the toe and the wall. By realizing this, we
correct the setting but the problem becomes infeasible. Then we add one more
round to enrich the possible contact sequence that the planner can search
over. From the bottom row of Fig. 6. We can see that for the second round, the
robot would not lift 3 legs together as what the robot would do in the 3-3-3
contact sequence. Instead, it is divided into two rounds. The robot would lift
the leg LM to create 4 contact points and then lift the right two legs (RF and
RR) to avoid too large horizontal forces required for the two legs on the
brick. The robot successfully overcomes the transition phase with steps by
performing the 3-1-2-2 contact sequence.

Figure 6: The upper row is the 3-3-3 contact sequence for the parallel wall
with steps while the bottom row is the 3-1-2-2 contact sequence. The middle
row is the screenshots of hardware experiments when implementing these two
contact sequences. (Green represents a surface with smaller friction
coefficient)

###  III-C Others

Besides the scenarios described previously, we also simulate two more cases.
The first one is that we replace the two bricks with an incline to investigate
the capability of changing the body orientation. We use $L_{2}$ norm of
contact force in the cost function to encourage forces to be distributed more
evenly which is also one possible incentive to change the body orientation. We
also reduce the weight $Q_{\Theta}$ of the body orientation stepsize. The
second one is to investigate how to transit from the wall to the ground.
Obviously, reversing the order of our previous contact sequence would work
since the robot is under the static equilibrium for every round. However, when
you want to climb out of a circular wall or a tube, the situation is totally
different since the flat surface the robot can place the leg is around the
tube externally. Both simulation results are visualized in Fig. 7.

Figure 7: (a) The transition motion with the parallel wall with an incline.
(b) The transition motion from a tube to the flat platform outside the tube.
Figure 8: Red circles highlight the moving legs. (a) Screenshots for the
repeated 2-4 gait (b) Screenshots for the repeated 3-3 gait.

Without losing generality, we also apply our transition motion planner for
ground walking. With different initial guesses, our planner converges to
different local minimas and generates the standard tripod gait (repeated 3-3
contact sequence actually) and repeated 2-4 gait. The hardware demonstration
is shown in Fig. 8.

###  III-D Running Time

Generally, a big concern about NLP, especially with complementarity
constraints, is the running time. Since only a small number of rounds $M$
(generally $\leq 5$) required for the transition motion, our MATLAB code using
SNOPT as the solver usually generates motions described previously within 10
secs. Also, NLP is very sensitive to the initial guess. A warm start that
ignores highly nonlinear complementarity constraints can always help find a
better initial guess leading to less computational time. Currently, for the
parallel wall task, the average running time varies from 1.054s to 3.083s.
These numbers are reported by running on an Intel Core i7-6500U CPU. We
believe the implementation with the C++ code can accelerate the planner and
make it run online which is also one of our future works.

##  IV DISCUSSION AND CONCLUSION

Although we propose that the contact wrench of the end-effector can be
optimized through our motion planner, multi-limbed robots, unlike humanoid
robots, generally are not designed with enough DOF to fully control the
contact wrench (in most cases, the contact torque cannot be controlled
directly). However, as we have seen from Section III-A, the contact torque can
play a big role in improving the robustness of the resulting transition
motions. Introduction of potential coupling relation between controllable
forces and uncontrollable torques remains an open question. For our proposed
method, the planning round $M$ needs to be determined based on human
experience. Investigation on planning $M$ simultaneously would be one of the
future works. Quantitative analysis based on appropriate performance metrics,
_e.g._ , success rate, running speed and the resulting joint torque can be
used to determine the optimal settings. Our proposed method assumes prior
knowledge of estimating the friction coefficient. Fortunately, recent
developments on image processing and learning technique make this prior
condition possible with on-board vision systems.

In this paper we present a transition motion planner for multi-limbed vertical
climbing robots to overcome the transition phase between the ground and walls.
Complementarity constraints are used to generate unscheduled contact sequences
and describe how to switch supporting limbs. The optional complementary
constraint on limb switchability helps mitigate the local minima issue to some
extent since this discontinuous planning problem tends to keeping same limbs
for supporting, which will lead to local minimas given different settings,
_e.g._ , limited planning round. Two safety factors for toe slip and motor
over-torque are considered in the planner. Instead of tuning randomly, they
are interpretable. The results show that a variety of transition contact
sequences is generated in order to handle different environment setups,
including slippery wall surfaces and steps/inclines that can be taken
advantage of. Hardware demonstrations verify the feasibility and show that our
planner can be used for standard gait schedule of legged robots as well.

## References

  * [1] S. Kajita, F. Kanehiro, K. Kaneko, K. Fujiwara, K. Harada, K. Yokoi, and H. Hirukawa, “Biped walking pattern generation by using preview control of zero-moment point,” in 2003 IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp. 1620–1626, IEEE, 2003.
  * [2] R. Tedrake, S. Kuindersma, R. Deits, and K. Miura, “A closed-form solution for real-time zmp gait generation and feedback stabilization,” in 2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids), pp. 936–940, IEEE, 2015.
  * [3] H. Dai and R. Tedrake, “Planning robust walking motion on uneven terrain via convex optimization,” in 2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids), pp. 579–586, IEEE, 2016.
  * [4] A. W. Winkler, F. Farshidian, M. Neunert, D. Pardo, and J. Buchli, “Online walking motion and foothold optimization for quadruped locomotion,” in 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 5308–5313, IEEE, 2017.
  * [5] M. H. Raibert, “Hopping in legged systems—modeling and simulation for the two-dimensional one-legged case,” IEEE Transactions on Systems, Man, and Cybernetics, no. 3, pp. 451–463, 1984.
  * [6] Q. Nguyen, M. J. Powell, B. Katz, J. Di Carlo, and S. Kim, “Optimized jumping on the mit cheetah 3 robot,” in 2019 International Conference on Robotics and Automation (ICRA), pp. 7448–7454, IEEE, 2019.
  * [7] S. Kim, M. Spenko, S. Trujillo, B. Heyneman, D. Santos, M. R. Cutkosky, et al., “Smooth vertical surface climbing with directional adhesion,” IEEE Transactions on robotics, vol. 24, no. 1, pp. 65–74, 2008.
  * [8] M. J. Spenko, G. C. Haynes, J. Saunders, M. R. Cutkosky, A. A. Rizzi, R. J. Full, and D. E. Koditschek, “Biologically inspired climbing with a hexapedal robot,” Journal of field robotics, vol. 25, no. 4-5, pp. 223–242, 2008\.
  * [9] A. Parness, N. Abcouwer, C. Fuller, N. Wiltsie, J. Nash, and B. Kennedy, “Lemur 3: A limbed climbing robot for extreme terrain mobility in space,” in Robotics and Automation (ICRA), 2017 IEEE International Conference on, pp. 5467–5473, IEEE, 2017.
  * [10] T. Bretl, “Motion planning of multi-limbed robots subject to equilibrium constraints: The free-climbing robot problem,” The International Journal of Robotics Research, vol. 25, no. 4, pp. 317–342, 2006.
  * [11] X. Lin, J. Zhang, J. Shen, G. Fernandez, and D. W. Hong, “Optimization based motion planning for multi-limbed vertical climbing robots,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1918–1925, IEEE, 2019.
  * [12] Y. Tazaki and M. Murooka, “A survey of motion planning techniques for humanoid robots,” Advanced Robotics, pp. 1–10, 2020.
  * [13] A. W. Winkler, C. D. Bellicoso, M. Hutter, and J. Buchli, “Gait and trajectory optimization for legged systems through phase-based end-effector parameterization,” IEEE Robotics and Automation Letters, vol. 3, no. 3, pp. 1560–1567, 2018.
  * [14] M. Posa, C. Cantu, and R. Tedrake, “A direct method for trajectory optimization of rigid bodies through contact,” The International Journal of Robotics Research, vol. 33, no. 1, pp. 69–81, 2014.
  * [15] H. Dai, A. Valenzuela, and R. Tedrake, “Whole-body motion planning with centroidal dynamics and full kinematics,” in 2014 IEEE-RAS International Conference on Humanoid Robots, pp. 295–302, IEEE, 2014.
  * [16] P. E. Gill, W. Murray, and M. A. Saunders, “Snopt: An sqp algorithm for large-scale constrained optimization,” SIAM review, vol. 47, no. 1, pp. 99–131, 2005.
  * [17] D. E. Orin, A. Goswami, and S.-H. Lee, “Centroidal dynamics of a humanoid robot,” Autonomous robots, vol. 35, no. 2-3, pp. 161–176, 2013.
  * [18] X. Lin, H. Krishnan, Y. Su, and D. W. Hong, “Multi-limbed robot vertical two wall climbing based on static indeterminacy modeling and feasibility region analysis,” in 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 4355–4362, IEEE, 2018.
  * [19] A. Pashkevich, A. Klimchik, and D. Chablat, “Enhanced stiffness modeling of manipulators with passive joints,” Mechanism and machine theory, vol. 46, no. 5, pp. 662–679, 2011.