Erfan Asaadi, Ewen Denney, and Ganesh Pai 11institutetext: KBR, Inc., NASA
Research Park
Moffett Field, CA 94035, USA
11email: {easaadi, edenney<EMAIL_ADDRESS>
# Quantifying Assurance in Learning-enabled Systems††thanks: This work was
supported by the Defense Advanced Research Projects Agency (DARPA) and the Air
Force Research Laboratory (AFRL) under contract FA8750-18-C-0094 of the
Assured Autonomy Program. The opinions, findings, recommendations or
conclusions expressed are those of the authors and should not be interpreted
as representing the official views or policies of DARPA, AFRL, the Department
of Defense, or the United States Government.

Erfan Asaadi  Ewen Denney  Ganesh Pai${}^{(\textrm{{\char 0\relax}})}$

###### Abstract

Dependability assurance of systems embedding machine learning (ML)
components—so called _learning-enabled systems_ (LESs)—is a key step for their
use in safety-critical applications. In emerging standardization and guidance
efforts, there is a growing consensus in the value of using assurance cases
for that purpose. This paper develops a quantitative notion of assurance that
an learning-enabled system (LES) is dependable, as a core component of its
assurance case, also extending our prior work that applied to ML _components_.
Specifically, we characterize LES assurance in the form of _assurance
measures_ : a probabilistic quantification of confidence that an LES possesses
system-level properties associated with functional capabilities and
dependability attributes. We illustrate the utility of assurance measures by
application to a real world autonomous aviation system, also describing their
role both in  i) guiding high-level, runtime risk mitigation decisions and
ii) as a core component of the associated _dynamic assurance case_.

Keywords: Assurance, Autonomy, Confidence, Learning-enabled systems, Machine
learning, Quantification

##  1 Introduction

The pursuit of developing systems with increasingly autonomous capabilities is
amongst the main reasons for the emergence of _learning-enabled systems_
(LESs), i.e., systems embedding machine learning (ML) based software
components. There is a growing consensus in autonomy standardization efforts
[1] on the value of using _assurance cases_ (ACs) as the mechanism by which to
convince various stakeholders that an LES can be relied upon. assurance cases
have been successfully used for safety assurance of novel aviation
applications where—like LESs—regulations and standards continue to be under
development [2]. However, LESs pose particular assurance challenges [3] and
existing AC technologies may not be sufficient, requiring a framework where
the system and its AC evolve in tandem [4]. Here too, there are specific
additional challenges: first, structured arguments111The systematic reasoning
that captures the rationale why specific conclusions, e.g., of system safety,
can be drawn from the evidence supplied. in many ACs are effectively _static_
, i.e., they are usually developed prior to system deployment under
assumptions about the environment and intended system behavior. Evolution of
the system or its ML components (e.g., via online learning, or by adaptation
in operation) can render invalid a previously accepted AC. In principle,
although it is possible to dynamically evolve structured arguments [4], since
their role is primarily to convince human stakeholders, it makes more sense
for such updates to happen between missions at well-defined points.

Second, an operational evaluation of the extent of assurance in an LES (or its
ML components, where appropriate) is a valuable system-level indicator of
continued fitness for purpose. That, in turn, can facilitate potential
intervention and counter-measures when assurance drops below an acceptable
level during a mission. Indeed, _online assurance updates_ that are aimed at
machine consumption must necessarily be in a computable form, e.g., using a
formal language, such as a logic, or as a quantification. So far as we are
aware, prevailing notions of ACs do not yet admit such evaluation. Prior
efforts at AC confidence assessment [5, 6] have focused on the argument
structure rather than the system itself, and face challenges in repeatable,
objective validation due to their reliance on subjective data. They have also
not been applied to LESs. Thus, there is a general need to capture a
computable form of assurance to bolster an otherwise qualitative AC. Note that
although a qualitative AC may well refer to quantitative evidence items, here
we are identifying the necessity to have quantified assurance as a core facet
of LES ACs.

This paper focuses on the problem of assurance quantification, deferring its
use in dynamic updates to future work. The main contribution is an approach to
characterize assurance in an LES through uncertainty quantification (UQ) of
system-level dependability attributes, demonstrated by application to an
aviation domain LES.

##  2 Methodology

Previously [7], we have described how assurance of ML _components_ in an LES
can be characterized through UQ of component-level properties associated with
the corresponding (component-level) dependability attributes. Here, we extend
our methodology to the system-level, relying on the following concepts:
_assurance_ is the provision of (justified) confidence that an _item_ —i.e., a
(learning-enabled) component, system, or service—possesses the relevant
assurance properties. An _assurance property_ is a logical, possibly
probabilistic characteristic associated with _dependability attributes_ [8]
and functional capabilities. One or more assurance properties applied to a
particular item give an _assurance claim_ 222Henceforth, we do not distinguish
assurance properties from assurance claims.. An _assurance measure_
characterizes the extent of confidence that an assurance property holds for an
item through a probabilistic quantification of uncertainty. It can be seen as
implementing a UQ model on which to query the confidence in an assurance
property.333When the assurance property is itself probabilistic, the
corresponding assurance measure is deterministic, i.e., either 0 or 1.

In general, we can define multiple assurance properties (and assurance
measures), based on the LES functionality and dependability attributes for
which assurance is sought. For example, the proposition “ _the aircraft
location does not exceed a specified lateral offset from the runway centerline
during taxiing_ ” is a system-level assurance claim associated with the
attribute of _reliability_. Similarly, the assurance property “ _the aircraft
does not veer off the sides of the runway during taxiing_ ” is associated with
the attribute of _system safety_. Such assurance properties directly map to
the claims made in the structured arguments of an LES assurance case. Thus, we
can leverage the methodology for creating structured arguments [9] to also
specify assurance properties.

For quantification, we mainly consider assurance measures for those system-
level properties that can be reasonably and feasibly quantified. For example,
assurance measures for the preceding example quantify the uncertainty that the
aircraft location does not exceed, respectively, the specified lateral offset
from the runway centerline (reliability), and half the width of the runway
pavement (safety), over the duration of taxiing.

LESs used in safety-critical applications, especially aviation, are
effectively stochastic dynamical systems. The insights from this observation
are that we can:  i) capture LES behavior through model-based representations
of the underlying stochastic process;  ii) view system-level assurance
properties as specific realizations of particular random variables of that
process; and  iii) express confidence in the assurance properties—i.e., the
assurance measures—by propagating uncertainty through the model to determine
the distributions over the corresponding RVs.

One challenge is selecting an appropriate model and representation of the
stochastic process to be used to model LESs. Although there is not a generic
answer for this, such a model could be built, for example, by eliciting the
expected system behavior from domain experts, by transforming a formal system
description, using model fitting and statistical optimization techniques
applied to (pre-deployment) system simulation and execution traces, or through
a combination of the three. For LESs, a formal system description may be often
unavailable. As such, we rely on elicitation and statistical techniques, using
Bayesian models where possible, making allowance to admit and use other well-
known, related stochastic process models—such as Markov chains—and leveraging
data from analytical representations of system dynamics, simulations, and
execution. The Bayesian concepts of _credible_ intervals and
regions—determined on the posterior distribution of the RVs for assurance
properties—give a formal footing to the intuitive, subjective notion of
confidence that usually accompanies claims in assurance arguments, and ACs in
general [10].

##  3 Illustrative Example – Runway Centerline Tracking

###  3.1 System Description

To show our methodology is feasible, we now apply it to quantify assurance in
an aviation domain LES supplied by our industrial collaborators: a unmanned
aircraft system (UAS) embedding an ML component, trained offline using
supervised learning, to support an autonomous taxiing capability. The broader
goal is to enable safe aircraft movement on a runway without human pilot
input. Fig. 1 shows a simplified _pipeline architecture_ used to realize this
capability. A deep convolutional neural network (CNN) implements a perception
function that ingests video images from a wing-mounted camera pointed to the
nose of the aircraft. The input layer is $(360\times 200)$ pixels $\times~{}3$
channels wide; the network size and complexity is of the order of $100$ layers
with greater than two million tunable parameters. Effectively, this ML
component performs regression under supervised learning producing estimates of
_cross track error_ (CTE)444The horizontal distance between the aircraft nose
wheel and the runway centerline. and _heading error_ (HE)555 _Heading_ refers
to the compass direction in which an object is pointed; heading error (HE)
here, is thus the angular distance between the aircraft heading and the runway
heading. as output. These estimates are input to a classical proportional-
integral-derivative (PID) controller that generates the appropriate steering
and actuation signals.

Figure 1: Pipeline architecture to implement an autonomous taxiing capability
in a UAS.

###  3.2 Assurance Properties

The main objective during taxiing (autonomously, or under pilot control) is to
safely follow the runway (or taxiway) centerline. Safety during taxiing
entails avoiding _lateral runway overrun_ , i.e., not veering off the sides of
the runway pavement. Although avoiding obstacles on the runway is also a
safety concern, it is a separate assurance property that we do not consider in
this paper. Thus, safety can be achieved here, in part, by meeting a
performance objective of maintaining an acceptable lateral offset (ideally
zero) on either side of the runway centerline during a taxi _mission_ from
starting taxi to stopping (or taking off).666Our industry collaborators
elicited the exact performance objectives from current and proficient
professional pilots. In other words, the closer the aircraft is to the runway
centerline during taxiing, the less likely it is to veer off the sides of the
runway.

This performance objective relates to the attribute of reliability, where
_taxi failure_ is considered to be the violation of the specified lateral
offset. Here, we focus on the corresponding assurance property,
$\mathtt{AssuredTaxi}:\lvert\mathrm{CTE}_{a}\rvert<\mathtt{offset}$, where
$\mathtt{offset}=2$ is the maximum acceptable lateral offset on either side of
the runway centerline for this application and aircraft type.
$\mathrm{CTE}_{a}$, which is the true (or actual) cross track error (CTE) for
the UAS, is a signed, real valued scalar; the absolute value gives the
magnitude of the offset, and the sign indicates where the UAS is located
relative to the centerline, i.e., to its left or its right.

###  3.3 Assurance Quantification

####  3.3.1 Model Choice

The assurance measure corresponding to $\mathtt{AssuredTaxi}$, establishes
$\mathrm{Pr}\left(\lvert\mathrm{CTE}_{a}\rvert<2\right)$, which characterizes
the uncertainty (or conversely, confidence) in the true (or actual) CTE
($\mathrm{CTE}_{a}$) relative to the specified offset. $\mathrm{CTE}_{a}$
evolves in time as the PID controller responds to _estimates_ of CTE and HE,
themselves the responses of the deep CNN component, to runway images captured
by the wing mounted camera (see Fig. 1). $\mathrm{CTE}_{a}$ is thus uncertain
and depends on other variables, of which those that can be observed are the
estimated CTE ($\mathrm{CTE}_{e}$), estimated HE ($\mathrm{HE}_{e}$), and a
sequence of images. We can also model the controller behavior in terms of a
time series evolution of $\mathrm{CTE}_{a}$ since, during taxiing, the true
CTE at a given time is affected by the controller actuation signals at prior
times.

An abstracted model of LES behavior is reflected in the joint distribution of
the relevant observed and uncertain variables. In fact, a _dynamic Bayesian
network_ (DBN) [11] is a convenient and compact representation of this joint
distribution, as we will see subsequently in this section. It takes into
account the temporal evolution of the variables and their (known or assumed)
conditional independence relations. Thus, to determine the assurance measure,
we effectively seek to quantify the (posterior) distribution over
$\mathrm{CTE}_{a}$, given a sequence of runway images, the estimates of CTE
and HE produced by the ML component, and the controller behavior, as a query
over the corresponding dynamic Bayesian network (DBN) model.

Table 1: DBN model variables.

####  3.3.2 Model Variables

Model variables can be discrete or continuous, and there are tradeoffs between
information loss and computational cost involved in the choice. Table 1 lists
the discrete variables we have chosen, giving the interval boundaries for
their states. The choice of the intervals that constitute the states of the
variables has been based, in part, on:  i) domain knowledge,  ii) an
assessment of the data sampled from the environments used for training and
testing the CNN, and  iii) the need to develop an executable model that was
modest in its computational needs.

Here, $w$ is the width of the runway in meters, and negative values represent
CTE measured on the left of the runway centerline. The HE is given in degrees,
while $D$ is dimensionless. An additional variable ($I$, not shown in Table 1)
models the runway image captured from the camera video feed as a vector of
values in the range $[0\dots 1]$ representing normalized pixel values. The
Boolean variable $D$ represents the detection of outliers in camera image
data. Such outliers may manifest due to various causes, including camera
errors and _covariate shift_ , i.e., when the data input to the CNN has a
distribution different from that of its training data. Note that the LES shown
in Fig. 1 does not indicate whether or not it includes a mechanism to detect
outliers or covariate shift. However, we include this variable here, motivated
by our earlier work on component-level assurance quantification of the CNN
[7], which revealed its susceptibility to outlier images. In fact, $D$ models
a runtime monitor for detecting out of distribution (OOD) inputs to the CNN.

Figure 2: DBN structure for assurance quantification, showing two adjacent
slices at times $t-1$, and $t$; shaded nodes represent observed variables,
clear nodes are the uncertain, latent variables.

####  3.3.3 Model Structure

Each variable in Table 1 is indexed over time: we will denote a variable $X$
at time $t$ as $X^{(t)}$. The causal ordering of the model variables (Fig. 2)
informs the structure of the DBN: the estimated CTE and HE at time $t$ are
inputs to the controller which, in turn, impacts the future location of the
aircraft at time $t+\varepsilon$. The directed links between the corresponding
variables in adjacent time slices capture this dependency. For example, in
Fig. 2, these are the directed links
$\mathrm{CTE}_{e}^{(t-1)}\to\mathrm{CTE}_{a}^{(t)}$, and
$\mathrm{HE}_{e}^{(t-1)}\to\mathrm{CTE}_{a}^{(t)}$ (and likewise for the
preceding and subsequent time slices). The directed links
$\mathrm{CTE}_{a}^{(t-1)}\to\mathrm{CTE}_{a}^{(t)}$ model the correlation
between actual vehicle position over time, also capturing vehicle inertia.

At time $t$, the runway image $I^{(t)}$ influences the belief about the true
aircraft location, i.e., the states of $\mathrm{CTE}_{a}^{(t)}$, with the node
$D$ modeling the associated structural uncertainty. This reflects the
intuition that upon detecting an outlier image (more generally an OOD input),
we are no longer confident that the image seen is an indicator of the actual
aircraft location. Fig. 2 reflects these dependencies by the directed edges
$\mathrm{CTE}_{a}^{(t)}\leftarrow I^{(t)}$, and
$\mathrm{CTE}_{a}^{(t)}\leftarrow D^{(t)}$, respectively.

Fig. 2 shows two adjacent time slices of the DBN structure, although the
actual structure is unrolled for $T$ time steps, the duration of taxiing, to
compute the assurance measure over the taxi phase. At time $t$, this is, in
fact, the sum of the probability mass over the seven states of
$\mathrm{CTE}_{a}^{(t)}$ that lie within the interval $[-2,2]$ (see Table 1).
By unrolling the DBN for an additional $\varepsilon$ time steps and
propagating the uncertainty through the model from the time of the last
observations, the model can provide an assurance forecast.

####  3.3.4 Probability Distributions

To complete the DBN model specification, we need to specify the conditional
probability distributions over the model variables, as encoded by its
structure. One way to identify the CPDs is through uncertainty quantification
of the physical system model [12]. Practically, the latter may not be
available, especially for LESs.

Another alternative—the approach we take here—is to assume a functional form
for the CPDs that is then tuned based on execution and simulation data.
Specifically, to construct the CPD represented by the transition edge between
the time slices, i.e.,
$\mathrm{Pr}(\mathrm{CTE}_{a}^{(t)}\,|\,\mathrm{CTE}_{a}^{(t-1)},\mathrm{CTE}_{e}^{(t-1)},\mathrm{HE}_{e}^{(t-1)})$,
we chose a multinomial distribution with a uniform prior, tuned using the
maximum a posteriori probability (MAP) estimate on simulation data. This
choice was advantageous in the sense that the DBN produces a uniform posterior
distribution over $\mathrm{CTE}_{a}$ when the observed variables take on
values from a distribution different from that of the data used to build the
CPDs. For this example, the simulation data comprised sequences of runway
images, estimated CTE and HE as produced by the CNN, and true CTE. Section 4
gives more details on the simulation platform and data gathered.

To determine the emission probability
$\mathrm{Pr}(\mathrm{CTE}_{a}^{(t)}\,|\,I^{(t)})$, first we used the Gaussian
process (GP) model underpinning our prior work on component-level assurance
quantification [7]. In brief, the idea is to use a GP to model the error
performance of the CNN (i.e., its accuracy) on its input (i.e., runway
images). Then, adding the error distribution to the estimate of CTE gives the
distribution over the true CTE. However, for high dimensional data (such as
images), this is computationally expensive. Instead, in this paper we used an
ensemble of decision trees [13] as a classifier that ascribes a probability
distribution over the states of $\mathrm{CTE}_{a}$, given a runway image, $I$.
This approach builds uncorrelated decision trees such that their combined
estimate is more accurate than that of any single decision tree. To identify
the decision rules, we used supervised learning over the collection of runway
images and corresponding true CTE, sampled from the same environments used to
train and test the CNN (see Section 4). For this example, we built $280$
decision trees with terminal node size of at least $10$, by randomly sampling
$100$ data points using the _Gini index_ as a performance metric, selecting
the model parameters to balance classification accuracy and computational
resources.

##  4 Experimental Results

We now present some results of our experiments in quantifying LES assurance in
terms of the assurance measure,
$\mathrm{Pr}\left(|\mathrm{CTE}_{a}|<2\right)$, based upon simulations of
constant speed taxiing missions.

###  4.1 Simulation Setup

We use a commercial-off-the-shelf flight simulator instrumented to reflect the
pipeline architecture of Fig. 1. The simulation environment includes various
airports and runways with centerlines of varying quality, e.g., portions of
the centerline may be obscured at various locations (see Fig. 1). We can
create different training and test environments by changing various simulation
settings, among which two that we have selected are:  i) weather induced
visibility (_clear_ and _overcast_), and  ii) the time of day (_07:30am_ to
_2:00pm_).  Two such environments are, for example, “ _Clear at 07:30am_ ”,
and “ _Overcast at 12:15pm_ ”. More generally, we can construct environments
such as “ _Clear Morning_ ”, “ _Overcast Afternoon_ ”, and so on. The former
refers to the collection of data sampled from the environment having clear
weather, and the time of day incremented in steps of $15$ and $30$ minutes
from _07:30am_ until _noon_. A similar interpretation applies to other such
environments.

From these environments, we gathered images via automated screen capture
(simulating the camera output) whilst taxiing the aircraft on the airport
runway, using different software controllers, as well as different CNNs for
perception: i.e., the same CNN architecture described in Section 3, but
trained by our industrial collaborators with data drawn from the various
environments identified earlier. In tandem, for each image, we collected true
CTE (from internal simulation variables), along with estimates of CTE and HE.
We used several such data sets, one for each of the different environments
identified above, from which data samples were drawn to build the CPDs of the
DBN model. Here, note that these data samples were _not_ identical to those
used to train and test the CNN, even though the samples were drawn from the
collection of environments common to both the LES and the DBN.

Figure 3: Visualization of predicted uncertainty in true cross track error,
$\mathrm{CTE}_{a}^{(t)}$, to quantify assurance in runway centerline tracking
as the assurance measure, $\mathrm{Pr}(\mathtt{AssuredTaxi})$.

Figure 4: $\mathrm{Pr}(\mathtt{AssuredTaxi})$ for $\mathtt{offset}=2$ and
$\mathtt{offset}=1.43$.

###  4.2 Uncertainty Quantification

Fig. 4 shows the results of assurance quantification for one test scenario,
visualized as a probability surface overlaid on a stretch of the runway,
itself shown as a grid. The horizontal axis—discretized using the interval
boundaries for the states of $\mathrm{CTE}_{a}$ (see Table 1)—gives the true
aircraft location, which is uncertain during taxiing. Thus, moving from left
to right (or vice versa) constitutes lateral aircraft movement. The vertical
axis (discretized into $6$ steps, each of duration $0.33$) represents the
number of time slices for which the DBN model is unrolled. We selected this
based on the time taken for the UAS to laterally depart the runway after
violating the $2$ bound, given: runway dimensions, maximum allowed taxiing
speed, and other constraints on the UAS dynamics, e.g., non-accelerating
taxiing.

At $t=0$, the horizontal axis gives the aircraft location at the current time.
The time steps $t=1,\ldots,6$ are _lookahead times_ for which the horizontal
axis gives the _predicted_ location of the aircraft relative to the
centerline, given the CNN estimates of CTE and HE at $t=0$. Thus, moving from
the bottom to the top of Fig. 4 represents forward taxiing, i.e., the temporal
evolution of aircraft position over the runway. Each cell of the grid formed
by discretizing the two axes is, therefore, a state of $\mathrm{CTE}_{a}$ at a
given time, shaded such that darker shades indicate lower uncertainty (or
higher confidence) and lighter shades indicate higher uncertainty (or lower
confidence). Thus, the row at $t=0$ shows the DBN estimate of uncertainty over
$\mathrm{CTE}_{a}$ at the current time. Similarly, each row for $t=1,\ldots,5$
shows the _predicted_ uncertainty over $\mathrm{CTE}_{a}$ for those lookahead
times, given that the last known values for the observed variables are at
$t=0$. The solid white line in Fig. 4 at $t=0$ is _ground truth_ , i.e., the
true CTE at the current time based on internal simulation variables. Although
this may not be otherwise available during taxiing, we show it here primarily
for model validation, i.e., to show that the interval (state of
$\mathrm{CTE}_{a}$) estimated by the DBN to be the least uncertain is also the
one that includes the ground truth. The solid black line is CTE as estimated
by the CNN (i.e., $\mathrm{CTE}_{e}$) at the current time.

Recall that assured taxiing involves maintaining $\mathrm{CTE}_{a}$ between a
$2$ lateral offset on either side of the centerline. To quantify assurance in
this property, we sum up the probability mass in each cell between the two
offsets. Fig. 4 shows the assurance measure,
$\mathrm{Pr}(|\mathrm{CTE}_{a}^{(t=0)}|<\mathtt{offset})$ computed for two
different offset values: $2$ and $1.43$.777The introduction of a second offset
was motivated by our industry collaborators to integrate the assurance measure
on the LES platform. The interval $[-2,2]$ is a Bayesian _credible interval_
within which the true CTE lies with probability $\approx 95\%$, based on Fig.
4. In other words, _the DBN model is $\approx 95\%$ confident that the
aircraft is truly located within $2$ of the runway centerline_. In general,
the expected (and desired) DBN behavior is to be more uncertain over longer
term assurance forecasts, when there are no additional observations with which
to update the posterior distributions on the assurance measures.

###  4.3 Sufficient Assurance

We must select a threshold on the assurance measure to establish what
sufficient assurance constitutes, based on which we can assert whether or not
the assurance claim holds. The criterion we have selected here is: when the
DBN is $\geq 30\%$ confident that the true UAS location exceeds the allowed
lateral offset, the assurance claim does not hold, i.e.,
$\Pr(|\mathrm{CTE}_{a}^{(t)}|\geq 2)\geq
0.3\Rightarrow\neg(\mathtt{AssuredTaxi})$. We determined this threshold under
conservative assumptions about vehicle behavior, leveraging the engineering
judgment of our industry collaborators, to balance the tradeoff between safety
(avoiding runway overrun) and mission effectiveness (not stopping too often).

##  5 Discussion

We now evaluate how the DBN performs relative to the LES, in the context of
ground truth. The intent is to show that it is a reasonable (i.e., valid)
_reference model_ of the system suitable for runtime use (i.e., simple and
abstract), based on which to make certain decisions, e.g., whether or not to
stop taxiing. Moreover, we must also show that the software implementation of
the DBN can be relied upon. In this paper, we primarily address the former,
leaving the latter for future work.

###  5.1 Validity

We compare how well the DBN and the LES can discriminate between _true
positive_ and _true negative_ situations when their respective outputs are
transformed into a classification on a plurality of image data drawn from
multiple simulated taxiing scenarios for different test environments unseen by
both the DBN and the LES.

A true positive (negative) situation for the DBN is one where it indicates
that the assurance property is satisfied (not satisfied) based on the
criterion for sufficient assurance (see Section 4), and ground truth data also
indicates that it is truly the case that the UAS location is within (exceeds)
the allowed lateral offset from the runway centerline. Likewise for the LES, a
true negative (positive) situation is one where the CNN estimate of CTE
indicates (does not indicate) an offset violation i.e., $\mathrm{CTE}_{e}\geq
2$ (equivalently, $\mathrm{CTE}_{e}<2$), and so does ground truth data.

Table 2: DBN Performance evaluation for runway centerline tracking.

Table 2 shows our evaluation results in terms of _sensitivity_ (true positive
rate) and the _specificity_ (true negative rate) of both the DBN model and the
LES, varying the embedded CNN used for perception. The variability arises from
using CNNs trained under two different training environments. We also used
these training environments to build the DBN for both LES variants using
$\approx 37000$ image samples. These samples were not the same as those that
were used to train the CNN variants: indeed, we did not have access to the
actual training data for the different CNNs. Also, the test environments
listed in the table (and, therefore, the resulting test data), are unseen
during the development of both LES variants, and the DBN models of the same.

Based on Table 2, in the context of the sensitivity and specificity metrics
shown, as well as the criterion for sufficient assurance, we are cautiously
optimistic in claiming that the DBN models the LES reasonably well. For the
test environments “ _Clear at 11:45am_ ”, and “ _Overcast at 12:15pm_ ”, the
DBN has a lower sensitivity than the LES, however its specificity is
substantially better. This suggests that the LES may be biased in its
estimates of CTE for those operating conditions.

###  5.2 Suitability

The DBN model structure—in particular, the conditional independence relations
encoded by the structure—is informed by (our knowledge of) the causal impacts
of the identified variables and the system dynamics, and the resulting
assumptions. We note that it is always possible to relax these assumptions and
learn the DBN structure as well as its parameters. However, in most cases,
especially when there is limited data available, structure learning can be an
unidentifiable problem, or can produce a non-unique solution. In our case, the
conditional independence assumptions used have turned out to be neither too
strong to affect model performance nor too conservative to impose a problem in
identifying the CPDs given limited data.

Our assessment in Table 2 does _not_ compare the DBN and the CNN that
estimates CTE. Indeed, the latter is a learned, static regression function for
a _component_ , that associates a vector of real values with a real-valued
scalar, whereas here we are assessing a stochastic process model of a
(learning-eabled) _system_ (i.e., the DBN) against the system itself. When we
use the DBN for runtime assurance, we implement it as a software component
integrated into the LES. This can be viewed as an item to which we can apply
our own assurance methodology, i.e., as in Section 2, and [7]. Thus, although
we have not formulated assurance properties for the DBN, sensitivity and
specificity are probabilistic performance metrics (albeit in a frequentist
sense) that we can view as assurance measures in their own right, that we have
now applied to our model.

The validation above is admittedly not exhaustive although the following
observations are worth noting: the DBN is a relatively simple and abstract
model of the time-series evolution of the _system_ , whose estimates can be
updated through Bayesian inference given observed data. Thus, it is amenable
to applying other verification techniques including inspection, and formal
verification.

Moreover, the DBN _does not_ produce point estimates of CTE; rather, in
quantifying confidence in a system-level assurance property, a by-product is
the uncertainty in true CTE given as a probability distribution over the range
of admissible values of $\mathrm{CTE}_{a}$. Thus, in unseen situations where
the CNN can produce an inaccurate estimate of CTE (see Fig. 4), the DBN gives
a distribution over possible values of true CTE. As sucsh, it is more
conservative in potentially unsafe scenarios. Based on this assessment, we
submit that the DBN is a reasonable and suitable runtime reference model of
the LES for the autonomous taxiing application, when used for centerline
tracking.

###  5.3 Utility

A key advantage of an abstract assurance quantification model is a small
implementation footprint for runtime integration into the LES. As indicated in
Section 1, one of the primary motivations for quantified assurance measures is
to provide feedback signals (in a computable form) to the LES, that can be
acted on, e.g., by a _Contingency Management System_ (CMS), in operation. In
this work, the assurance measure values were translated into commands to
either _stop_ , _slow down_ , or _continue_ based on  i) the chosen decision
thresholds (Section 4), and  ii) a simple model of the system-level effect
(i.e., likelihood of lateral runway overrun) given the assurance measure and
current system state.888Although the content of integrating assurance measures
with a Contingency Management System (CMS) is very closely related to the work
here, it is not in scope for this paper, and will be the topic of a
forthcoming article. In general, deciding between a series of options in the
presence of conflicting and uncertain outcomes is a special case of _decision
making under uncertainty_ [14]. We plan to investigate such techniques as
future work to develop a principled approach to contingency management using
assurance measures.

The aim of _run-time assurance_ , also known as _run-time verification_ , is
to provide updates as to whether a system satisfies specified properties as it
executes [15]. This is done using a run-time _monitor_ , which evaluates the
property using values extracted from the state of the system and its
environment. In a sense, therefore, the notion of assurance measure we have
described here is a kind of monitor. However, it is worth making several
distinctions. A monitor relates directly to properties of the system, whereas
an assurance measure characterizes _confidence_ in our knowledge of such
properties. Second, an assurance measure seeks to aggregate a range of sources
of information, including monitors. Thus it can be seen as a form of _data
fusion_. Third, monitors typically provide values that relate to the current
state of the system, whereas the assurance measures we have defined are
predictive, intended to give a probabilistic quantification on dependability
attributes.

In general, our approach to assurance quantification admits other models
including runtime monitors: recall that the node $D^{(t)}$ in Fig. 2 is a
runtime monitor detecting data distribution shift in the input image at time
$t$. Indeed, our framework is not intended to replace runtime verification,
and the assurance measures generated show the assurance contribution of the
runtime monitors, additionally providing an assurance/uncertainty forecast. We
are not aware of existing runtime verification techniques that do this.

##  6 Related Work

The work in this paper is closely related to our earlier research on assurance
case confidence quantification [5]. There, although confidence estimation in
an assurance claim also uses Bayesian techniques, it relies primarily on the
argument structure to build the model. Similarly, based on the structure of an
argument, the use of an evidential theory basis has been explored for
confidence quantification in assurance claims [6]. However, neither work has
been applied to LES assurance quantification. Moreover, in this paper the
focus is on those properties where quantification is possible, relying upon
models of the system that can be assessed against objective, measured data.

This paper is a natural extension of our prior work on quantifying assurance
in ML components [7]: the assurance property we consider there is
$\mathrm{CTE}_{e}$ _accuracy_. Assurance quantification then entails using
Gaussian processes (GPs) to determine the uncertainty in the error of
$\mathrm{CTE}_{e}$, which is inversely proportional to accuracy. However, the
data used are not (and need not be) time dependent and the model used applies
regardless of whether or not the aircraft position has violated
$\mathtt{AssuredTaxi}$. Indeed, despite a high assurance CNN that accurately
estimates CTE, it is nevertheless possible to violate $\mathtt{AssuredTaxi}$.
However, in this paper we model the LES as a stochastic process, including any
runtime mitigations, e.g., a monitor for detection OOD images. As such, the
models used for UQ are a generalization of that in [7] to time-series
behavior.

As previously indicated (Section 1), one of the motivations is to support
dynamic assurance cases (ACs). Our prior work [4] first explored this concept,
which has subsequently been tailored for so-called _self-adaptive software_
[16]. Again, neither work has considered LESs, although self-adaptation is one
of the properties that LESs can exhibit. In [4], confidence quantification has
been situated as a core principle of dynamic assurance which has also
motivated this paper to an appreciable degree. However, that work relies on
the quantification methodology in [5]. In [16], assurance quantification
employs probabilistic model checking, which can be leveraged for LESs if they
can be represented using state-space models, e.g., as in [17] which uses
hybrid model checking instead. Neither technique is incompatible with the
stochastic processes-based modeling approach that we have adopted. As such,
they may be a candidate means to check properties of the stochastic models
that we build as a means of (meta-)assurance.

_Dynamic safety management_ as an assurance concept has also been proposed as
a run-time assurance method [18], but it is largely speculative about
applicability for LESs. The idea of _requirements-aware_ runtime models [19]
is very closely related to our notion of building a reference model.
Quantified and probabilistic guarantees in reinforcement learning have been
explored in developing assured ML components in [20]. That work is also
closely related to what we have presented here, though its focus is mainly on
assurance of correctness properties that have a safety impact. Additionally,
the assurance approach there is _intrusive_ in the sense that the ML component
being built is modified. In our case, assurance quantification does not modify
the ML components. _Benchmarking_ of uncertainty estimation techniques [21]
has also been investigated, although mainly in the context of image
classification. It is unclear if the reported results translate to assurance
quantification as applied in this paper. However, the benchmarking principles
and metrics used could be candidates for evaluating various system models
built using our approach.

Kalman filters have long been used to address uncertainty during state
estimation, and have some similarities to our approach. A Kalman filters is a
special case of a DBN where amongst the main assumptions are that sensor
errors are distributed as zero mean Gaussians, and that the uncertainty does
not vary between sensing outputs. In contrast, our model uses discrete
distributions, admitting varying sensor uncertainty for each image input, in a
more general graphical model that has a different structure, whilst including
detections of OOD inputs.

##  7 Conclusion and Future Work

We have described our approach to quantifiable assurance using assurance
measures, run-time computations of uncertainty (conversely, confidence) in
specified assurance properties, and their application to learning-enabled
systems (LESs). Assurance measures complement design-time assurance
activities, each of which forms part of an overall dynamic assurance case
(DAC). In collaboration with system integrators from industry, we have applied
our framework to an aviation platform that employed supervised learning using
a deep CNN. Collaboration was crucial to develop the contingency management
capability, which relied on engineering judgment to tradeoff safety risk
reduction and achieving performance objectives. Feedback from the end-users
(i.e., our industry collaborators) was also essential in refining the final
visualizations of the assurance measure that we ultimately deployed in the
system (based on Fig. 4). Those are intended to provide insight into the
system assurance state for safety observer crew.

We have shown that our methodology can feasibly quantify assurance in system-
level properties of an aviation domain LES, though we have used classical UQ
techniques. Our work in quantifying assurance in LESs is ongoing, and we will
be developing assurance measures for other autonomous platforms in the context
of more complex mission objectives that require additional ML components and
learning schemes.

The work in this paper is one strand of our overall approach to assurance
through DACs. The diverse components of an assurance case, including
structured arguments, safety architecture [22], as well as the assurance
measures described here, each represent one facet of an integrated DAC. There
are close connections between the probabilistic models underlying assurance
measures and the safety architecture, as well as between assurance properties
and claims in an assurance arguments. Our future work will place these
connections on a rigorous basis. In part, this can be achieved through use of
a high-level _domain-specific language_ (DSL) that will let us  i) abstract
from the details of the individual probabilistic models, and  ii) conversely,
allow compilation into a range of different models, whilst making more
explicit the connections to domain concepts used elsewhere in the assurance
case.

A related avenue of future work is providing comprehensive assurance for our
approach itself, and in turn, the assurance measures produced. From a
verification standpoint, we can consider _correctness_ properties entailing
i) consistency between the quantification model and the other DAC components,
e.g., the risk scenarios captured by a safety architecture, and  ii)
correctness of the low-level implementation against the higher level
specification embodied by the quantification model.  Additionally, assurance
measure validity is related, in part, to the limits of the statistical
techniques used to infer the underpinning stochastic models, and the data used
to build them.

Indeed, one of the challenges we faced in this work was obtaining sufficient
useful data. Moreover, the quality of the data gathered also plays a key role
in corroborating that the assurance quantification models sufficiently
represent the system behavior across its intended operational profile. We
believe that a more principled approach to specifying a variety of training
data should be possible (e.g., to include various types of perturbed and
adversarial inputs), and that such specifications could be derived from the
DSL used to specify the assurance measures themselves. The dynamic nature of
assurance cases (ACs) will also bear further investigation, to see how real-
time updates provided by assurance measures during a mission can inform
updates between missions, to the qualitative arguments of ACs.

## References

  * [1] Underwriter Laboratories Inc.:  Standard for Safety for the Evaluation of Autonomous Products UL 4600\.  (April 2020)
  * [2] Clothier, R., Denney, E., Pai, G.:  Making a Risk Informed Safety Case for Small Unmanned Aircraft System Operations.  In: 17th AIAA Aviation Technology, Integration, and Operations Conference (ATIO 2017), AIAA Aviation Forum. (June 2017)
  * [3] McDermid, J., Jia, Y., Habli, I.:  Towards a Framework for Safety Assurance of Autonomous Systems.  In Espinoza, H., et al., eds.: 2019 AAAI Workshop on Artificial Intelligence Safety (SafeAI 2019), CEUR Workshop Proceedings (January 2019)
  * [4] Denney, E., Habli, I., Pai, G.:  Dynamic Safety Cases for Through-Life Safety Assurance.  In: IEEE/ACM 37th IEEE International Conference on Software Engineering (ICSE 2015). Volume 2., (May 2015) 587–590
  * [5] Denney, E., Pai, G., Habli, I.:  Towards measurement of confidence in safety cases.  In: 5th International Symposium on Empirical Software Engineering and Measurement (ESEM 2011). (Sept. 2011) 380–383
  * [6] Wang, R., Guiochet, J., Motet, G., Schön, W.:  Safety Case Confidence Propagation based on Dempster–Shafer Theory.  Intl. Journal of Approximate Reasoning 107 (2019) 46 – 64
  * [7] Asaadi, E., Denney, E., Pai, G.:  Towards Quantification of Assurance for Learning-Enabled Components.  In: 15th European Dependable Computing Conference (EDCC 2019), IEEE (September 2019) 55–62
  * [8] Avižienis, A., Laprie, J.C., Randell, B., Landwehr, C.:  Basic concepts and taxonomy of dependable and secure computing.  IEEE Transactions on Dependable and Secure Computing 1(1) (Jan 2004) 11–33
  * [9] Denney, E., Pai, G.:  Tool Support for Assurance Case Development.  Journal of Automated Software Engineering 25(3) (September 2018) 435–499
  * [10] Hawkins, R., Kelly, T., Knight, J., Graydon, P.:  A new approach to creating clear safety arguments.  In Dale, C., Anderson, T., eds.: Advances in Systems Safety, (2011) 3–23
  * [11] Murphy, K.P.:  Machine Learning: A Probabilistic Perspective.  MIT Press (2012)
  * [12] Najm, H.N.:  Uncertainty Quantification and Polynomial Chaos Techniques in Computational Fluid Dynamics.  Annual Review of Fluid Mechanics 41(1) (January 2009) 35–52
  * [13] Criminisi, A., Shotton, J., Konukoglu, E.:  Decision Forests: A Unified Framework for Classification, Regression, Density Estimation, Manifold Learning and Semi-Supervised Learning.  Foundations and Trends in Computer Graphics and Vision 7(2–3) (2012) 81–227
  * [14] Kochenderfer, M.J.:  Decision Making Under Uncertainty: Theory and Application.  MIT Press (2015)
  * [15] Moosbrugger, P., Rozier, K.Y., Schumann, J.:  R2U2: Monitoring and Diagnosis of Security Threats for Unmanned Aerial Systems.  (April 2017) 1–31
  * [16] Calinescu, R., Weyns, D., Gerasimou, S., Iftikhar, M.U., Habli, I., Kelly, T.:  Engineering Trustworthy Self-Adaptive Software with Dynamic Assurance Cases.  IEEE Transactions on Software Engineering 44(11) (November 2018) 1039–1069
  * [17] Ivanov, R., Weimer, J., Alur, R., Pappas, G.J., Lee, I.:  Verisig: Verifying Safety Properties of Hybrid Systems with Neural Network Controllers.  In: 22nd ACM Intl. Conference on Hybrid Systems: Computation and Control. (HSCC ’19) (2019) 169–178
  * [18] Trapp, M., Schneider, D., Weiss, G.:  Towards Safety-Awareness and Dynamic Safety Management.  In: 14th European Dependable Computing Conference (EDCC 2018). (September 2018) 107–111
  * [19] Bencomo, N., Garcia-Paucar, L.H.:  RaM: Causally-connected and Requirements-aware Runtime Models using Bayesian Learning.  In: 22nd IEEE/ACM International Conference on Model Driven Engineering Languages and Systems (MODELS 2019). (September 2019)
  * [20] Bouton, M., Karlsson, J., Nakhaei, A., Fujimura, K., Kochenderfer, M.J., Tumova, J.:  Reinforcement Learning with Probabilistic Guarantees for Autonomous Driving.  Computing Research Repository (CoRR) arXiv:1904.07189v2 [cs.RO] (May 2019)
  * [21] Henne, M., Schwaiger, A., Roscher, K., Weiss, G.:  Benchmarking uncertainty estimation methods for deep learning with safety-related metrics.  In Espinoza, H., et al., eds.: 2020 AAAI Workshop on Artificial Intelligence Safety (SafeAI 2020), CEUR Workshop Proceedings, Volume 2560 (February 2020) 83–90
  * [22] Denney, E., Pai, G., Whiteside, I.:  The Role of Safety Architectures in Aviation Safety Cases.  Reliability Engineering & System Safety 191 (2019)

  *[ML]: machine learning
  *[LESs]: learning-enabled system
  *[LES]: learning-enabled system
  *[ACs]: assurance case
  *[AC]: assurance case
  *[UQ]: uncertainty quantification
  *[RVs]: random variable
  *[UAS]: unmanned aircraft system
  *[CNN]: convolutional neural network
  *[CTE]: cross track error
  *[HE]: heading error
  *[PID]: proportional-integral-derivative
  *[DBN]: dynamic Bayesian network
  *[OOD]: out of distribution
  *[CPDs]: conditional probability distribution
  *[CPD]: conditional probability distribution
  *[MAP]: maximum a posteriori probability
  *[GP]: Gaussian process
  *[CNNs]: convolutional neural network
  *[ DBN]: dynamic Bayesian network
  *[CMS]: Contingency Management System
  *[GPs]: Gaussian process
  *[DAC]: dynamic assurance case
  *[DACs]: dynamic assurance case
  *[DSL]: domain-specific language


# VascularPilot3D: Toward a 3D fully autonomous navigation for endovascular
robotics

Jingwei Song, Keke Yang, Han Chen, Jiayi Liu, Yinan Gu, Qianxin Hui, Yanqi
Huang, Meng Li, Zheng Zhang,
Tuoyu Cao, and Maani Ghaffari J. Song is with United Imaging Research
Institute of Intelligent Imaging, Beijing 100144, China
<EMAIL_ADDRESS>Yang, H. Chen, J. Liu, Y. Gu, Q. Hui, Y. Huang,
M. Li, Z. Zhang, and T. Cao are with United Imaging, Shanghai, China.
{keke.yang, han.chen03, jiayi.liu01, yinan.gu, qianxin.hui, yanqi.huang,
meng.li02, zheng.zhang<EMAIL_ADDRESS>M. Ghaffari is with the
University of Michigan, Ann Arbor, MI 48109, USA<EMAIL_ADDRESS>
###### Abstract

This research reports VascularPilot3D, the first 3D fully autonomous
endovascular robot navigation system. As an exploration toward autonomous
guidewire navigation, VascularPilot3D is developed as a complete navigation
system based on intra-operative imaging systems (fluoroscopic X-ray in this
study) and typical endovascular robots. VascularPilot3D adopts previously
researched fast 3D-2D vessel registration algorithms and guidewire
segmentation methods as its perception modules. We additionally propose three
modules: a topology-constrained 2D-3D instrument end-point lifting method, a
tree-based fast path planning algorithm, and a prior-free endovascular
navigation strategy. VascularPilot3D is compatible with most mainstream
endovascular robots. Ex-vivo experiments validate that VascularPilot3D
achieves $100\%$ success rate among 25 trials. It reduces the human surgeon’s
overall control loops by $18.38\%$. VascularPilot3D is promising for general
clinical autonomous endovascular navigations.

##  I Introduction

Robot-assisted Endovascular Image-Guided Interventions (EIGIs) are gaining
popularity in contrast to conventional regular EIGIs in treating heart
disease, cancer, stroke, or neurovascular disease due to their lower mortality
rate, faster recovery, and most importantly, limited exposure to radiation for
surgeons. Existing robot-assisted EIGIs follow the master-slave robot
operation system and are manipulated manually by surgeons for
guidewire/catheter navigation and other operation procedures. Pre-operative
Computed Tomography (CT) or Computed Tomography Angiography (CTA) and intra-
operative fluoroscopic X-ray or Digitally Subtracted Angiograms (DSA) serve as
maps and eyes for surgeons’ navigation tasks. In clinical applications, hand-
operated navigation is laborious for surgeons because humans have difficulty
adapting to multi-modal data, soft-tissues’ deformation, non-isometric
friction, and incompatibility of control panels. Therefore, this work proposes
the first 3D fully autonomous endovascular navigation system VascularPilot3D,
under intra-operative (fluoroscopic X-ray in this study) and pre-operative
data (CTA in this study). VascularPilot3D aims to reduce time consumption and
the mental and physical burden placed on the operators in navigation
procedures, allowing more focus on the clinical aspects.

Existing autonomous endovascular robots navigated instruments through
intelligent agents which were trained with Reinforcement Learning (RL) [1, 2,
3, 4, 5, 6, 7, 8]. Among these RL-based studies, [2, 3, 4, 6] adopted
imitation learning to make full use of human experiences while others were
fully unsupervised. These works were trained and tested on phantoms except [1]
whose “haptic vision” setup falls out of this article’s scope. It should be
pointed out that clinical applications of these RL-based approaches require a
massive amount of training on phantoms or patients, and generalization
capability across different patients is unknown. More importantly, all these
works were conducted on 2D dimensions, which suffered from topological
ambiguity. Some trafficable intersections on 2D images were illusions from
non-intersect overlapping 3D vessels. Thus, a prior-free 3D navigation method
may overcome topological ambiguity and avoid expensive or even inaccessible
RL-based training.

This research proposes VascularPilot3D as the first 3D prior-free autonomous
endovascular navigation system. It follows the typical autonomous driving’s
“mapping-localization-navigation” workflow, where “mapping” builds the full 3D
vascular from pre-operative data, “localization” localizes instruments intra-
operatively, “navigation” plans the global route, and makes local sequential
controls. Among them, “mapping” and “localization” methods have been widely
analyzed. Massive amount of studies have shown that 3D U-Net like Deep Neural
Networks (DNNs) [9, 10, 11, 12, 13, 14, 15, 16] and graph convolution network
[17, 18, 19] achieve satisfying and robust 3D vessel “mapping”. Meanwhile,
“localization” can be realized by combining fast 2D instrument segmentation
and 3D-2D vessel registration. 2D instrument segmentation, similar to 3D
vessel segmentation, is developed taking the off-the-shelf lightweight U-Net
DNN. Prior-free fast 3D-2D vessel registration algorithms [20, 21, 22, 23, 24]
has also been well studied.

(a)  Figure 1: Presented is the framework of the proposed VascularPilot3D.

Our VascularPilot3D leverages previous algorithms for “mapping” and
“localization” and enhances the localization with 3D topology constraints.
More importantly, a newly proposed prior-free “navigation” module achieves
efficient global path planning by treating the vessel as a tree data structure
with parent pointers. We additionally propose a strategy for making controls.
Our contributions include:

  * •

To our knowledge, VascularPilot3D is the first 3D prior-free autonomous
endovascular navigation system. 3D navigation overcomes the false intersection
problem in conventional 2D navigation works.

  * •

A novel topology-constrained instrument end point 2D to 3D registration method
is proposed.

  * •

A tree-based map presentation and global path planning method is proposed. A
practical control strategy is also developed for fast navigation.

  * •

Ex-vivo experiments demonstrate that VascularPilot3D consumes $18.38\%$ less
control loops than human operators and achieves $100\%$ success rate among 25
trials.

##  II Methodology

###  II-A System overview

Fig. 1 shows the framework of VascularPilot3D. “Centerline extraction (I)”
yields intra-operative 2D vessel centerlines in real-time from X-ray images.
“Centerline extraction (II)” extracts 3D vessel centerlines from the pre-
operative data before the operation. Then, a real-time 3D-2D registration is
performed to match 3D and 2D vessels. Meanwhile, a lightweight DNN is applied
to estimate the endpoint position of the instrument (guidewire in this study).
With the correct 3D-2D registration, the endpoint is lifted from 2D to 3D
space with the correct topology. Finally, a path is planned from the latest 3D
endpoint position to the target 3D point in the path planning phase.
VascularPilot3D then makes iterative control based on the estimated endpoint’s
3D position from the latest obtained intra-operative 2D image.

###  II-B Centerline segmentation and 3D-2D registration

This work strictly follows [24] for 3D and 2D centerline segmentation as well
as non-rigid registration, and we briefly introduce the procedure here. Widely
used Otsu’s method [25] was applied for fast 2D vessel segmentation. A DNN-
based method from commercial software was used for 3D vessel segmentation. It
should be emphasized that other prior-based DNNs [19, 26] are also applicable
for 3D/2D image segmentation. Based on the segmented 3D and 2D centerlines,
registration (optimal rigid and nonrigid transformation) was achieved by
jointly maximizing Reproducing Kernel Hilbert Space (RKHS) sum constrained by
regularization as

$\displaystyle\operatorname{max}_{\mathbf{T},\theta}E_{data},\text{ such
that},\operatorname{min}_{\mathbf{T},\theta}\lambda_{1}E_{init}+\lambda_{2}E_{reg}$
(1) $\displaystyle
E_{data}=\sum_{i\in\Omega}\mathrm{w}_{i}\\!\sum_{j\in\Delta(i)}$
$\displaystyle\exp\left(-\frac{\lVert\pi(\mathbf{T}\Gamma(\mathbf{T}_{dsa\\_cb}\mathbf{p}_{i}-\mathbf{c},\theta),\mathbf{K})-\mathbf{q}_{j}\rVert^{2}_{2}}{2\ell^{2}}\right)$
$\displaystyle
E_{init}=\lVert\operatorname{log}(\mathbf{T}^{-1}_{0}\mathbf{T})^{\vee}\rVert_{2}^{2}$
$\displaystyle
E_{reg}=\mathrm{w}_{1}\sum_{i\in\Omega}\left\lVert\mathbf{r}_{i}\right\lVert^{2}_{2}+\mathrm{w}_{2}\sum_{i\in\Omega}\sum_{j\in\\{i-1,i+1\\}}\left\lVert\mathbf{r}_{i}-\mathbf{r}_{j}\right\lVert^{2}_{2}+$
$\displaystyle\mathrm{w}_{3}\sum_{i\in\Omega}\sum_{j\in\Omega_{i}}\left\lVert\mathbf{r}_{i}-\mathbf{r}_{j}\right\lVert^{2}_{2},$

where $\Omega$ is the set of 3D centerline point
$\mathbf{p}_{i}\in\mathbb{R}^{4}$ (in homogeneous coordinate and the same
applies to the rest), $\Delta(i)$ is the set of corresponding 2D point
$\mathbf{q}_{j}\in\mathbb{R}^{4}$, $\mathbf{T}_{0}$ is the initial pose or
pose in previous state and $\ell$, $\lambda_{1}$, $\lambda_{2}$,
$\mathrm{w}_{1}$, $\mathrm{w}_{2}$, $\mathrm{w}_{3}$ are hyperparameters, and
$\theta=\\{\mathbf{r}_{i}\\},\mathbf{r}_{i}\in\mathbb{R}^{4}$ (last dimension
is fiexed to $0$) is the deformation parameter,
$\mathbf{K}\in\mathbb{R}^{3\times 4}$ is the camera intrinsic matrix following
pin-hole camera. $E_{init}$ defines the distance on $\mathrm{SE}(3)$ manifold
and $(\cdot)^{\vee}$ converts Lie algebra $\mathfrak{se}(3)$ to 6-vector
$\mathbb{R}^{6}$. $E_{init}$ is used to avoid scale drift. In the first step
of minimization, $\ell$ is initialized as the maximum
$||\pi(\mathbf{T}\Gamma(\mathbf{T}_{dsa\\_cb}\mathbf{p}_{i}-\mathbf{c},\theta))-\mathbf{q}_{j},\mathbf{K}||^{2}_{2}$
and shrinked by half every 5 iterations. This work follows the latest progress
[27] and adopts the Iterative Reweighted Least Squares (IRLS) combined with
Levenberg–Marquardt for fast optimization.

Input: 3D start $\mathbf{p}_{s}\in\mathbb{R}^{3}$, 3D target
$\mathbf{p}_{e}\in\mathbb{R}^{3}$ and $\mathcal{M}(\cdot)$ tests if input is
on path

Output: Sequential translation and rotation control
$\mathbf{C}=\\{\cdot,\cdot\\}$, both elements are in $\mathbb{R}^{1}$

1 Set Flag_back and Flag_on_Path_Last as True & $\mathrm{w}=0$

2 while  _$\mathcal{D}(\mathcal{L}(),\mathbf{p}_{e}) >\mathrm{r}_{th}$_ do

3 if  _Flag_back is True_ then

4 if  _$\mathcal{L}()$ is True_ then

5 $\mathbf{C}=\\{-10,0\\}$/* Backward */

else

6 $\mathbf{C}=\\{10,0\\}$/* Forward */

7 Set Flag_back as False & Replan path from $\mathcal{L}()$ to
$\mathbf{p}_{e}$

end if

else

8 if  _$\mathrm{w} >\mathrm{w}_{th}$_ then

9 Replan path from $\mathcal{L}()$ to $\mathbf{p}_{e}$ & $\mathrm{w}=0$ &

10 Set Flag_back as True /* Redo path planning */

end if

11if  _$\mathcal{L}()$ is True_ then

12 $\mathrm{w}=0$

13 if  _Flag_on_Path_Last is True_ then

14 $\mathbf{C}=\\{\mathrm{c},0\\}$/* Forward */

else

15 $\mathbf{C}=\\{\mathrm{c},1\\}$/* Forward and rotate */

end if

else

16 $\mathbf{C}=\\{-\mathrm{c},1\\}$ & $\mathrm{w}=\mathrm{w}+1$ /* Backward
and rotate */

end if

end if

end while

Notation: $\mathcal{D}(\cdot,\cdot)$ measures the Euclidean distance between
two points. $\mathrm{r}_{th}$ determines whether the target has been reached.
$\mathrm{w}_{th}$ controls if the path should be replanned. $\mathbf{C}$ is
sent to slave machines each time it is assigned. $\mathrm{c}$ is a random
number ranging from 8 to 12. $\mathcal{L}()$ localizes the endpoint 3D
position following Section II-C.

Algorithm 1 Strategy-based navigation.

###  II-C Instrument endpoint estimation and 2D to 3D endpoint lifting

During the operation, real-time continuous X-ray images are obtained, and
instrument’s 2D endpoint can be estimated with UNet like DNN methods. SA-UNet
[28], first built for segmenting retinal vessels, is adopted for instrument
segmentation as it achieves state-of-the-art performance on limited training
data in curve-like segmentation scenario. [29]’s skeletonization method is
applied to instrument mask extraction due to its efficiency and accuracy.
Then, the skeleton points that have one adjacent are presumed to be candidate
endpoints. The surgeons must manually choose the endpoint if more than one is
found in the first frame; the selected endpoint is then adopted as the seed
for iterative tracking.

With the real-time 3D-2D alignment discussed in Section II-B and 2D endpoint
tracking, the estimated 2D endpoint is then lifted to 3D in pre-operative
vessel’s coordinate. Although computer vision community agrees that lifting 2D
to 3D is ambiguous in viewing direction, we overcome the issue using vessel
registration constraints. Since the 3D endpoint and its 2D projection are all
within the vessel, the 2D endpoint is lifted to 3D space via its closest 2D
vessel point and the 2D vessel point’s corresponding 3D vessel point. It is
obvious that the 3D localization accuracy depends on the registration and
vessel radius.

(a)  Figure 2: Left is the sample 2D DSA image projected from its right 3D
version.

###  II-D Global and local path planning

Previous 2D navigation methods’ global and local path planning modules [1, 2,
3, 4, 5, 6, 7, 8] cannot identify and handle false 2D intersections, as
illustrated in Fig. 2. Moreover, [7, 6, 5, 4, 3] pointed out that the state
presented in absolute 2D position makes the trained network difficult to be
generalized. We agree with [7] that the agent “learns the movements to
navigate this specific geometry”. Therefore, this research unifies global and
local path planning on 3D space to circumvent false intersections and enable
more generalized navigation.

Global path planning, or the route from start position to target position, is
done on the 3D map in the multiway trees data structure. To fasten the search
procedure, each node in the multiway trees have an additional pointer to their
parent. During global path planning, the 3D endpoint position (in Section
II-C) is the start point, and the surgeon chooses the 3D target position. The
route is then efficiently built by tracing both nodes to their common parent
in the multiway trees. This achieves the time complexity as
$\mathcal{O}((\log{}n)^{2})$.

Local path planning, or control, refers to sending instrument translation and
rotation motion control to the slave machines. Although existing RL-based
methods achieve successful navigation through iterative RL training, applying
RL to 3D navigation should solve the following obstacles considering hardware,
cost, and ethics: fast convergence in the phantom training process, fast
adaptation across modals, efficient inference, and uncertainties.
Uncertainties, mainly caused by unreliable localization, hardware control in
nonrigid and nonisometric friction, and system delay, bring unpredictable
phenomena in obtaining the correct control. Our experiments reveal that RL
behaves well in a virtual environment and deteriorates significantly in real-
world phantom. Thus, we gave up the previous RL roadmap and sought a prior-
free strategy-based method. Inspired by surgeon’s “trial-and-error” in their
routine endovascular navigation tasks [30, 31], VascularPilot3D summarized the
process and transplanted the experience as a simple yet effective strategy as
shown in Algorithm 1.

##  III Results and discussion

VascularPiolot3D was implemented as image receiver, 3D-2D registration, 2D
endpoint extraction and navigation packages and mounted on Robot Operating
System [32]. The complete software was deployed on a commercial laptop
ALIENWARE M17 R4 (i7-10870H, 32Gb RAM, and GeForce RTX 3060 6Gb). 3D-2D
registration package was implemented in C++ for efficient registration, and
the rest were implemented in Python. Our own robot was built which carries
VascularPiolot3D (see Fig. 3). The proposed VascularPiolot3D is modular to
other widely used vascular robots as well. Pre-operative CT data of a 3D
phantom was collected using United Imaging’s uCT 860 with volume size
$512\times 512\times 1959$ and voxel size $0.824\times 0.824\times 0.5mm$.
VascularPiolot3D grabbed real-time X-ray images from United Imaging’s uAngio
960. All collected 2D images were resized as $512\times 512$. The average
pixel size is in $0.30mm$. The average delay from uAngio 960 to
VascularPiolot3D is $0.2s$. The hyperparameters $\lambda_{1}$, $\lambda_{2}$,
${w}_{1}$, ${w}_{2}$ and ${w}_{3}$ are set as $100$, $1$, $0.1$, $10$ and $1$.

$527$ fluroscopic X-ray images were collected and labeled to train the
instrument segmentation network SA-UNet. Among them, $450$ were used for
training, and $77$ for validation. VascularPilot3D was tested on a phantom
that performs navigation on 5 different tasks shown in Fig. 3. 5 trials were
conducted in each task and the average values and standard deviations were
recorded. Since chosen tasks are typical tasks and VascularPiolot3D is prior-
free, successful navigation can validate that VascularPiolot3D is suitable
with any task without adaptation and training.

(a)  Figure 3: Figure shows our robot, phantom and 5 tasks (“Dest” stands for
destination).

(a)  Figure 4: Figure shows the sample navigation of VascularPilot3D on the five tasks (each row shows one task). Red marker is the guidewire endpoint on both 2D and 3D. White curve is the planned 3D path. Full navigations can be found in the attached video. TABLE I: This table compares the number of control loops of VascularPilot3D, human operator and RL [2] on the 5 tasks. “Mean” and “std” are the average and standard deviation of control loops. “-” indicates failing in all trials and “*” fails some trials. Method | Task1 | Task2 | Task3 | Task4 | Task5
---|---|---|---|---|---
Mean | Std | Mean | Std | Mean | Std | Mean | Std | Mean | Std
VascularPilot3D | 31.14 | 25.98 | 24.50 | 10.91 | 21.90 | 6.75 | 68.50 | 43.15 | 30.65 | 6.70
Surgeon | 29.89 | 11.70 | 51.46 | 20.93 | 31.65 | 11.46 | 66.25 | 23.00 | 37.23 | 11.56
RL navigation [2] | 53.67 | 31.04 | - | - | 40.67 | 21.04 | 57.00 | * | 26.33 | 8.11

###  III-A Navigation performances and time consumption

Fig. 4 shows selected sequential navigation results on both 2D and 3D end
111Readers are strongly advised to watch the attached video to appreciate the
performance.. [2]’s RL approach was adopted since it is clear for our
implementation. We followed [2]’s description and enhanced it by using the
last 4 frames as state and pretraining with the expert’s operations. The rest
setting strictly followed [2]’s description. A qualitative comparison was also
conducted to compare the performance of VascularPilot3D and a professional
surgeon. The surgeon obtained an M.D. Denote the one control loop as the cycle
“imaging-localization-control-mechanic” (VascularPilot3D) and “imaging-
control-mechanic” (human). This work compares the number of control loops in
each navigation trial. It should be emphasized that time consumption cannot be
fairly compared because of mechanical and imaging delay, and improvement in
hardware will be our main focus in the future. VascularPilot3D achieves
$100\%$ navigation success rate on five episodes of each task. Table I records
the averages and standard deviations of trial control loops of in each task.
It shows that VascularPilot3D outperforms the surgeon in 3 tasks out of 5. RL
navigation [2] failed 5 out of 25 trials. Since [2]’s was implemented and
trained by ourselves, and phantom was different, its result is for reference
only. VascularPilot3D reduces $18.38\%$ surgeon’s overall control loops.

VascularPilot3D consumes $550ms$ totally and Otsu-based segmentation is the
bottleneck. Time consumptions for vessel segmentation and 3D-2D alignment are
around $500ms$ and $50ms$. Global and local path plan consume less than $45ms$
and $10ms$. Guidewire endpoint tracking costs $50ms$ per frame and runs in
parallel.

###  III-B Limitations

VascularPiolot3D can be further improved by four directions. First, an
additional force feedback control can determine the range of translation value
$\mathbf{c}$ for safety purposes and rapid parameter adaptation. Second, CPU-
based Otsu-based segmentation (around $0.5s$), mechanical (around $1.3-1.8s$),
and data transmission delay (around $0.2s$) are most time-consuming. By
polishing these modules, one-step control loop can be significantly improved
from $2s$ to less than $0.2s$. Thirdly, collaboration of guidewire and
catheter is essential for real-world clinical applications. Lastly,
VascularPiolot3D can be further improved for optimizing X-ray imaging
direction to reduce radiation.

##  IV Conclusion

This work proposes the first 3D prior-free autonomous endovascular navigation
system VascularPilot3D. VascularPilot3D is a complete system that infers the
optimal sequential controls based on the pre-operative 3D and intra-operative
continuous 2D fluoroscopy. Navigation in 3D space overcomes the ambiguous
topological problem in existing 2D navigation works. VascularPilot3D has been
coupled into our hardware system. Ex-vivo experiments on phantom validate that
VascularPilot3D achieves $100\%$ success rate among 25 trials and reduce the
surgeon’s overall control loops by $18.38\%$.

## References

  * [1] G. Fagogenis, M. Mencattelli, Z. Machaidze, B. Rosa, K. Price, F. Wu, V. Weixler, M. Saeed, J. E. Mayer, and P. E. Dupont, “Autonomous robotic intracardiac catheter navigation using haptic vision,” Science robotics, vol. 4, no. 29, p. eaaw1977, 2019.
  * [2] T. Behr, T. P. Pusch, M. Siegfarth, D. Hüsener, T. Mörschel, and L. Karstensen, “Deep reinforcement learning for the navigation of neurovascular catheters,” current directions in biomedical engineering, vol. 5, no. 1, pp. 5–8, 2019.
  * [3] Y. Zhao, S. Guo, Y. Wang, J. Cui, Y. Ma, Y. Zeng, X. Liu, Y. Jiang, Y. Li, L. Shi, et al., “A CNN-based prototype method of unstructured surgical state perception and navigation for an endovascular surgery robot,” Medical & Biological Engineering & Computing, vol. 57, pp. 1875–1887, 2019.
  * [4] W. Chi, G. Dagnino, T. M. Kwok, A. Nguyen, D. Kundrat, M. E. Abdelaziz, C. Riga, C. Bicknell, and G.-Z. Yang, “Collaborative robot-assisted endovascular catheterization with generative adversarial imitation learning,” in Proc. IEEE Int. Conf. Robot. and Automation, pp. 2414–2420, IEEE, 2020.
  * [5] L. Karstensen, T. Behr, T. P. Pusch, F. Mathis-Ullrich, and J. Stallkamp, “Autonomous guidewire navigation in a two dimensional vascular phantom,” in Current Directions in Biomedical Engineering, vol. 6, p. 20200007, De Gruyter, 2020.
  * [6] J. Kweon, K. Kim, C. Lee, H. Kwon, J. Park, K. Song, Y. I. Kim, J. Park, I. Back, J.-H. Roh, et al., “Deep reinforcement learning for guidewire navigation in coronary artery phantom,” IEEE Access, vol. 9, pp. 166409–166422, 2021.
  * [7] L. Karstensen, J. Ritter, J. Hatzl, T. Pätz, J. Langejürgen, C. Uhl, and F. Mathis-Ullrich, “Learning-based autonomous vascular guidewire navigation without human demonstration in the venous system of a porcine liver,” Int. Jour. for Comp Assist. Rad. and Sur., vol. 17, no. 11, pp. 2033–2040, 2022.
  * [8] P. Schegg, J. Dequidt, E. Coevoet, E. Leurent, R. Sabatier, P. Preux, and C. Duriez, “Automated planning for robotic guidewire navigation in the coronary arteries,” in 2022 IEEE 5th International Conference on Soft Robotics (RoboSoft), pp. 239–246, IEEE, 2022.
  * [9] Ö. Çiçek, A. Abdulkadir, S. S. Lienkamp, T. Brox, and O. Ronneberger, “3D U-Net: learning dense volumetric segmentation from sparse annotation,” in Int. Conf. on Med. Image Comput. and Comput. Assist. Interv., pp. 424–432, Springer, 2016.
  * [10] H. Yang, J. Chen, Y. Chi, X. Xie, and X. Hua, “Discriminative coronary artery tracking via 3D CNN in cardiac CT angiography,” in Int. Conf. on Med. Image Comput. and Comput. Assist. Interv., pp. 468–476, Springer, 2019.
  * [11] Y.-C. Chen, Y.-C. Lin, C.-P. Wang, C.-Y. Lee, W.-J. Lee, T.-D. Wang, and C.-M. Chen, “Coronary artery segmentation in cardiac CT angiography using 3D multi-channel U-Net,” arXiv preprint arXiv:1907.12246, 2019.
  * [12] Y. Lei, B. Guo, Y. Fu, T. Wang, T. Liu, W. Curran, L. Zhang, and X. Yang, “Automated coronary artery segmentation in coronary computed tomography angiography (CCTA) using deep learning neural networks,” in Medical Imaging 2020: Imaging Informatics for Healthcare, Research, and Applications, vol. 11318, pp. 279–284, SPIE, 2020.
  * [13] L.-S. Pan, C.-W. Li, S.-F. Su, S.-Y. Tay, Q.-V. Tran, and W. P. Chan, “Coronary artery segmentation under class imbalance using a U-Net based architecture on computed tomography angiography images,” Scientific Reports, vol. 11, no. 1, p. 14493, 2021.
  * [14] Y. Wu, S. Qi, M. Wang, S. Zhao, H. Pang, J. Xu, L. Bai, and H. Ren, “Transformer-based 3D U-Net for pulmonary vessel segmentation and artery-vein separation from ct images,” Medical & Biological Engineering & Computing, vol. 61, no. 10, pp. 2649–2663, 2023.
  * [15] A. Zeng, C. Wu, G. Lin, W. Xie, J. Hong, M. Huang, J. Zhuang, S. Bi, D. Pan, N. Ullah, et al., “ImageCAS: A large-scale dataset and benchmark for coronary artery segmentation based on computed tomography angiography images,” Computerized Medical Imaging and Graphics, vol. 109, p. 102287, 2023.
  * [16] N. Mu, Z. Lyu, M. Rezaeitaleshmahalleh, J. Tang, and J. Jiang, “An attention residual U-Net with differential preprocessing and geometric postprocessing: Learning how to segment vasculature including intracranial aneurysms,” Medical image analysis, vol. 84, p. 102697, 2023.
  * [17] B. Kong, X. Wang, J. Bai, Y. Lu, F. Gao, K. Cao, J. Xia, Q. Song, and Y. Yin, “Learning tree-structured representation for 3D coronary artery segmentation,” Computerized Medical Imaging and Graphics, vol. 80, p. 101688, 2020.
  * [18] G. Zhao, K. Liang, C. Pan, F. Zhang, X. Wu, X. Hu, and Y. Yu, “Graph convolution based cross-network multiscale feature fusion for deep vessel segmentation,” IEEE Trans. Med. Imag., vol. 42, no. 1, pp. 183–195, 2022.
  * [19] Y. Li, Y. Zhang, W. Cui, B. Lei, X. Kuang, and T. Zhang, “Dual encoder-based dynamic-channel graph convolutional network with edge enhancement for retinal vessel segmentation,” IEEE Trans. Med. Imag., vol. 41, no. 8, pp. 1975–1989, 2022.
  * [20] S. R. Aylward, J. Jomier, S. Weeks, and E. Bullitt, “Registration and analysis of vascular images,” Int. J. Comput. Vis., vol. 55, no. 2, pp. 123–138, 2003.
  * [21] P. Markelj, D. Tomazevic, F. Pernus, and B. Likar, “Robust gradient-based 3-D/2-D registration of CT and MR to X-ray images,” IEEE Trans. Med. Imag., vol. 27, no. 12, pp. 1704–1714, 2008.
  * [22] P. Steininger, M. Neuner, H. Weichenberger, G. Sharp, B. Winey, G. Kametriser, F. Sedlmayer, and H. Deutschmann, “Auto-masked 2D/3D image registration and its validation with clinical cone-beam computed tomography,” Physics in Medicine & Biology, vol. 57, no. 13, p. 4277, 2012.
  * [23] D. Rivest-Henault, H. Sundar, and M. Cheriet, “Nonrigid 2D/3D registration of coronary artery models with live fluoroscopy for guidance of cardiac interventions,” IEEE Trans. Med. Imag., vol. 31, no. 8, pp. 1557–1572, 2012.
  * [24] J. Song, K. Yang, Z. Zhang, M. Li, T. Cao, and M. Ghaffari, “Iterative PnP and its application in 3D-2D vascular image registration for robot navigation,” arXiv preprint arXiv:2310.12551, 2023.
  * [25] N. Otsu, “A threshold selection method from gray-level histograms,” IEEE Trans. Syst., Man, Cybern., vol. 9, no. 1, pp. 62–66, 1979.
  * [26] S. Moccia, E. De Momi, S. El Hadji, and L. S. Mattos, “Blood vessel segmentation algorithms—review of methods, datasets and evaluation metrics,” Computer methods and programs in biomedicine, vol. 158, pp. 71–91, 2018.
  * [27] W. Clark, M. Ghaffari, and A. Bloch, “Nonparametric continuous sensor registration,” J. Mach. Learning Res., vol. 22, no. 1, pp. 12412–12461, 2021.
  * [28] C. Guo, M. Szemenyei, Y. Yi, W. Wang, B. Chen, and C. Fan, “SA-UNet: Spatial attention U-Net for retinal vessel segmentation,” in Proc. Int. Conf. Pattern Recog., pp. 1236–1242, IEEE, 2021.
  * [29] T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, no. 3, pp. 236–239, 1984.
  * [30] C. Duran, S. Estrada, M. O’Malley, A. B. Lumsden, and J. Bismuth, “Kinematics effectively delineate accomplished users of endovascular robotics with a physical training model,” Journal of Vascular Surgery, vol. 61, no. 2, pp. 535–541, 2015.
  * [31] E. B. Mazomenos, P.-L. Chang, R. A. Rippel, A. Rolls, D. J. Hawkes, C. D. Bicknell, A. Desjardins, C. V. Riga, and D. Stoyanov, “Catheter manipulation analysis for objective performance and technical skills assessment in transcatheter aortic valve implantation,” Int. Jour. for Comp Assist. Rad. and Sur., vol. 11, pp. 1121–1131, 2016.
  * [32] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, A. Y. Ng, et al., “ROS: an open-source Robot Operating System,” in ICRA workshop on open source software, vol. 3, p. 5, Kobe, Japan, 2009.