# Attainment Regions in Feature-Parameter Space for High-Level Debugging in
Autonomous Robots

Simón C. Smith and Subramanian Ramamoorthy1 This work was supported by EPSRC
funding for the ORCA Hub (EP/R026173/1, 2017-2021).1S. C. Smith and S.
Ramamoorthy are with the Institute of Perception, Action and Behaviour, School
of Informatics, The University of Edinburgh, 10 Crichton Street, EH8 9AB, UK.
SCS is also with the Adaptive & Intelligent Robotics Lab at Imperial College
London. {artificialsimon<EMAIL_ADDRESS>
###### Abstract

Understanding a controller’s performance in different scenarios is crucial for
robots that are going to be deployed in safety-critical tasks. If we do not
have a model of the dynamics of the world, which is often the case in complex
domains, we may need to approximate a performance function of the robot based
on its interaction with the environment. Such a performance function gives us
insights into the behaviour of the robot, allowing us to fine-tune the
controller with manual interventions. In high-dimensionality systems, where
the action-state space is large, fine-tuning a controller is non-trivial. To
overcome this problem, we propose a performance function whose domain is
defined by external features and parameters of the controller. Attainment
regions are defined over such a domain defined by feature-parameter pairs, and
serve the purpose of enabling prediction of successful execution of the task.
The use of the feature-parameter space –in contrast to the action-state space–
allows us to adapt, explain and fine-tune the controller over a simpler (i.e.,
lower dimensional) space. When the robot successfully executes the task, we
use the attainment regions to gain insights into the limits of the controller,
and its robustness. When the robot fails to execute the task, we use the
regions to debug the controller and find adaptive and counterfactual changes
to the solutions. Another advantage of this approach is that we can generalise
through the use of Gaussian processes regression of the performance function
in the high-dimensional space. To test our approach, we demonstrate learning
an approximation to the performance function in simulation, with a mobile
robot traversing different terrain conditions. Then, with a sample-efficient
method, we propagate the attainment regions to a physical robot in a similar
environment.

##  I INTRODUCTION

Many interesting tasks in autonomous robotics include scenarios where the
interaction between the robot and the environment involves complex and non-
linear dynamics. This complexity makes it hard the have access to an explicit
model of the dynamics. One way to cope with the lack of a model is to use
model-free learning techniques. In this learning paradigm, control policies
are learned directly from the interaction of the robot and the environment.
Examples of these techniques include model-free RL (Reinforcement Learning)
and supervised learning like LfD (Learning from Demonstration) [1, 2]. In
these methods, the robot interacts with the environment by choosing actions
through a combination of exploration and exploitation policies, or by being
guided by a supervisor.

Another approach is to approximate the dynamics based on data from interaction
between the robot and the environment. Learning this approximation is not
trivial as the dynamics may include non-linearities, hidden variables, and
intractable spaces.

In feedback control, a controller chooses actions based on the perceived state
of the environment and some internal parameters. These types of controllers
are usually described as a function of the action-state space. In a model-free
paradigm, after the execution of the task, a data point in the action-state
space can be mapped to a performance value. An example would be a reward
signal that depends on the final position of the robot in the environment.
Based on the performance, the action-state space can be divided into subsets
with different properties. These divisions, or regions, have been used to
produce hierarchies of _safe workspace regions_ where the system remains
within the region and converges to the goal [3]. Other uses of these regions
are viability kernels or backward-reachable sets [4, 5], where an agent can
safely explore the action-state space without reaching a failure state. In
general, these regions can be used for robust control, explainability, and to
fine-tune of the controller.

Such region analysis on the action-state space can be intractable for high-
dimensional systems. Most realistic systems and tasks would indeed involve
high-dimensionality of the state-action space. Some approaches to learning the
performance function in high-dimensional systems involve neural networks
(NNs). The drawback of using such NN architectures is that the regression
performance comes at the computational cost of requiring large training data
sets, and inscrutability of the decisions. Another approach to learning
erformance function is Gaussian process (GP) regression [4]. GPs can be used
to model the dynamics by making assumptions over the data distribution, but
their use can be restricted to lower-dimensional domains.

In this work, we propose to learn the performance of the system based on
features of the state and parameters of the controller. We define attainment
regions over the domain of the performance function as the set of feature-
parameter pairs that produce a successful execution of the task. A feature-
parameter pair represents the initial conditions of a single execution of the
task. If the result of the execution of the task is a success, the initial
condition pair is part of the attainment region. Thus, we can identify the
attainment regions in a model-free way.

Compared to the action-state space, the feature-parameter space can represent
subsets or regions of the former using a reduced number of variables, hence
allowing the use of learning architectures that are not too expensive.
Features can represent patterns that are common to a set of states. For
example, images belonging to a training set can be encoded as a small number
of features obtained in the latent space of a VAE (variational autoencoder
[6]), thus reducing the dimensions of the original state space. In the case of
controller parameters, such as for a Proportional-integral-derivative (PID)
controller, the selection of actions can be represented by only three
parameters. However, this isn’t directly connected to the environment. The use
of features and parameters allow us to study the behaviour in a way that
connects this to the environment. Another advantage of using features is the
ability to interpolate between states realistically. The interpolation allows
the generalisation of the controller and the estimation of the performance in
a scenario that has not yet been experienced. Also, debugging can benefit from
this simplified representation. For example, a single dimension of the latent
space can identify a full region of the original state space. In this case, we
show how we can tune a controller trained only with simulated data for a
physical system with only a few samples in the real environment.

There are several advantages to modelling the behaviour of the robot with
attainment regions. These regions allow us to understand the limits of the
operating regime of the robot. A larger region is more robust to external
perturbations than a smaller one. The use of features instead of states allows
the system to generalise in performance estimation to states that have not
been experienced. As the attainment region and its boundaries can be
represented graphically, system designers can debug the system. For example,
identifying combinations of features and parameters that require a more
detailed control policy. As the system assumes that any point outside the
attainment region does not result in a successful trial, we can search for the
shortest path in parameter-space between the failure point and the attainment
region. The controller can use the proposed parameters to change its internal
configuration and adapt for a successful trial. Another type of solution in
the case of a failed execution is based on the smallest modification of the
state to produce a successful trial. These solutions are termed
counterfactuals and are usually out of the reach of the robot. For example, a
counterfactual can propose a modification of the environment that requires
human intervention. In this case, the counterfactual serves as an explanation
of a failure case.

We test our system with a four-wheeled robot with the task of travelling
across a ramp at different inclinations and with different contact materials.
The material of the ramp varies between different friction coefficients, and
the steepness of the ramp can be regulated at different values. The task is
successful if the robot can traverse to the top of the ramp within a limited
time; otherwise, it is a failure. We collect synthetic data from a simulator
configured to represent the physical environment as close as possible,
including friction coefficient for the different materials. Using a Beta-VAE
on the RGB images, we can manually select two latent variables that best
represent the materials and steepness of the ramp as features of the state.
With the simulation data, we can fit a Gaussian process in the reduced
feature-parameter space to predict the performance of the robot based on the
image and controller gains.

After training the model with synthetic data, we apply the same method to a
physical robot. We show that we can fine-tune a mapping between simulated and
physical features. By adjusting the attainment regions to include data
collected from the physical robot, we show that with a few samples, the model
can adapt to the real sensory-motor loop and generalise to previously unseen
configurations.

###  I-A RELATED WORK

Defining and finding regions where the performance of a robot is reliably
known is crucial for safe deployment in complex environments. The notion of
controller robustness is related to gain and phase regions where the robot
remains stable even when it is externally disturbed [7]. With the calculation
of disk margins, based on gain and phase regions, and the explicit definition
of the model, controllers can be designed and fine-tuned [8, 9]. When there is
no access to an explicit model, sampling strategies are used to measure safety
boundaries [4, 10]. A popular approach to learning safety boundaries is the
viability kernel. These kernels represent regions in the state space where an
agent explores actions leading to success in a specific task. By sampling from
the state space, the kernels are used in the synthesis of robust controllers,
guaranteeing performance and estimating safety properties [11, 12]. Another
objective of the region analysis is to explain the decision process of the
system [13]. When the models have many parameters, e.g. with the use of deep
neural networks (DNN), system designers have to study them as a black-box. In
this case, one again requires sampling [14]. To study such high-dimensional
systems, the authors in [15] use features to build local models to explain the
full model. In [16], the authors exploit the feature space to measure the
robustness of robot control using counterfactuals. Other approaches to the
study of these regions are based on the parameter space. For example, in [17],
the parameter space of a controller is partitioned by regions that verify
constraints formulated using Signal Temporal Logic. Tuning parameters is
common in PID controllers, but usually, the state space is not considered
[18]. Similarly, in dynamical systems and probabilistic models, the parameters
can be synthesised for the system to arrive at a user-specified region [19].

In this paper, we propose learning and exploiting attainment regions in
feature-parameter space representing the successful completion of a task.

##  II METHOD

We define a dynamical systems in the action-state space as
$\mathbf{s}^{\prime}=f(\mathbf{a},\mathbf{s})$ with action $\mathbf{a}\in A$,
state $s\in S$ and a transition function $f$ to the next state
$\mathbf{s}^{\prime}$. Features of the state can be defined as
$\mathbf{z}=z(\mathbf{s})$ with $\mathbf{z}\in Z$ and $z:S\to Z$. Actions are
a function of the state and some internal parameters to a controller
$C_{\theta}$, $\mathbf{a}=C_{\theta}(\mathbf{s})$, with parameters
$\mathbf{\theta}\in\Theta$ and $C_{\theta}:\leavevmode\nobreak\
S\leavevmode\nobreak\ \to\leavevmode\nobreak\ A$. Here, we propose a
performance measure on the feature-parameter space
$p:Z\times\Theta\to\\{0,1\\}$, indicating the success or the failure of a
task.

The intuition here is that both $\mathbf{z}$ and $\mathbf{\theta}$ represent a
subset of $S$ and $A$, respectively. For example, a single feature could
represent the position of an object in the environment. In a task of obstacle
avoidance, the position of the object influences the final result of a trial.
In the state space, when the obstacle is perfectly aligned with the robot, it
is represented by a single state. If the obstacle is in front of the robot but
slightly shifted to one side, this is represented by a different state. The
use of features can represent a subset of these states. For example, one
variable representing the broad position of the object either in front, to the
left or the right of the robot, thus encapsulating several states in a single
variable. In the case of actions, the parameters define the outcome of the
controller. In a trial of $n$ steps, for a controller with fixed parameters,
the roll-out of actions during all the steps are represented by the initial
state and the parameters. In stochastic environments, this relationship still
holds, but an approximator of $p$ needs to address this characteristic, as we
will show next.

As we do not have access to the function $p$, we need to approximate it. GP
(Gaussian processes [20]) regression can be used as a probabilistic function
approximator. For simplicity, we define
$\mathbf{x}=(\mathbf{z},\mathbf{\theta})$ with $\mathbf{x}\in
X:=Z\times\Theta$ the feature-parameter space. The performance function is:

$y=p(\mathbf{x})=\begin{cases}1&\textrm{if the trial is successful}\\\
0&\textrm{if the trial failed}.\end{cases}$ (1)

The probabilistic estimate nature of the GP allows us to introduce prior
knowledge of the random variables and estimate an uncertainty of the
performance measure, in this case coming from the stochasticity of the system.
The posterior estimate of $\mathbf{x}$ is normally distributed, including a
set of samples $D=\\{(\mathbf{x}_{i},y_{i}),i=1,\dots,m\\}$ pairs. The
estimate $\hat{p}$ is conditioned on the samples
$\hat{p}_{X}(\mathbf{x})|D\sim\mathcal{N}(\mu(\mathbf{x}),\sigma^{2}(\mathbf{x}))$,
where $\mathcal{N}$ is the normal distribution, $\mu$ and $\sigma^{2}$ are the
posterior mean and variance given by the covariance function. Using an RBF
(Radial Basis Function) kernel and the set $D$, we can fit the parameters of
the GP to approximate $p$. Authors in [4] actively sample from the plant. This
approach is better suited when the sampling cost is high. In our case, we are
interested in sampling from synthetic data and later apply it to a physical
environment. In comparison, the cost of sampling is relatively low in our
approach. As the synthetic data could deviate from the data distribution of
the physical system, our system can fine-tune the feature-parameter space. We
see this property as a debugging tool for complex systems, and we give details
about it at the end of this section.

As the approximator $\hat{p}$ can estimate the probability of success of a
trial based on an instance of $\mathbf{x}$, we can define a threshold
parameter $\eta_{p}$ that indicate the minimum value to include $\mathbf{x}$
in the attainment region. We can calculate the probability that a feature-
parameter pair $\mathbf{x}$ belongs to the attainable region as:

$P[\hat{p}_{X}|D>\eta_{p}].$ (2)

With this definition of the attainment region, we can find solutions for
feature-parameter instances that do not belong to the region. Without loss of
generality and using multi-dimensional Euclidean distance, we can define a
constrained minimisation cost on the shortest path between the actual
$\mathbf{x}$ feature-parameter space point outside the attainment region and
an optimal point $\mathbf{x}^{*}$ in the attainment region limit.

$\mathbf{x}^{*}=\operatorname*{arg\,min}_{\mathbf{x}^{\prime}\in
X}||\mathbf{x}-\mathbf{x}^{\prime}||.$ (3)

In feature space, autoencoders show an _interpolation_ property. The
interpolation between two instances in the latent space produces a smooth
semantic warping in data space [21]. In parameter space, non-linearities are
captured as non-continuous attainment regions, e.g. a blob in feature-
parameter space where the task fails, surrounded by an area where the task
does succeed. Using a sequential importance sampling and re-sampling with
attribution prior algorithm ([22, 23]), we can find the smallest possible
change to $\mathbf{x}$ for a new trial to succeed with probability $\eta_{p}$.

We can restrict the sampling of possible solutions to either the feature or
parameter space. In this case, we have two different families of solutions.
First, the solutions on the parameter space belong to an adaptive controller
policy. At the beginning of the trial, with
$\hat{p}_{X}(\mathbf{x}=(\mathbf{z},\mathbf{\theta}))$, we can estimate the
probability of success of the actual configuration. Restricting the search of
the optimal value to the parameter space $\mathbf{\theta}$ and fixing the
features $\mathbf{z}$, we can find an optimal set of parameters $\theta^{*}$.
Now, the controller can update its internal representation based on
$\theta^{*}$

The second family of solutions is when we search over the feature space and
fix the parameters. This solution corresponds to a counterfactual solution
[16]. In this case, the solution is to modify the environment that will allow
the trial to succeed. Usually, the robot is not able to carry out the
counterfactual modification. If the robot were able to apply said
modification, it would be part of the original controller. Counterfactuals
give an approximation to what an external agent (autonomous or not) should
modify in the environment for the robot to succeed. In the example of obstacle
avoidance, in a cluttered environment, where there is no solution to avoid
them, removing one or more obstacles will allow the robot to find a solution
path. This minimal modification, outside the responsibility of the autonomous
robot, is the counterfactual solution. Counterfactuals are used for
accountability, as causes outside the responsibility of the robot can explain
why a trial has failed. Also, counterfactuals are a debugging tool. A single
counterfactual in feature space can indicate regions in the state space where
the system fails and requires attention.

##  III EXPERIMENTS & RESULTS

To evaluate our approach and to show that we can learn the attainment regions
in realistic settings, we define a task involving a physical robot with a
high-dimensional sensory-motor loop. We work with a Clearpath Robotics Husky
A200 UGV (unmanned ground vehicle). This robot us equipped with a Multisense
S7 sensor. We use the RGB camera as the main sensor. In our experiments, the
goal of the robot is to move along a ramp with different materials and
steepness. The materials that we vary in the trials are the metal of the ramp
itself and synthetic ice. The metallic ramp is designed to reduce slippage,
while the synthetic ice has a reduced friction coefficient. We vary the
steepness of the ramp between $0^{\circ}$ and $30^{\circ}$. Using a PID
controller on the angular velocity of the wheels, the task of the robot is to
travel to the end of the ramp successfully. In case that the robot does not
arrive, the task is a failure. Failure can occur for two main reasons. First,
the robot slips to a side given the different friction from the diverse
contact materials placed on top of the ramp. The second failure cause comes
from the steepness of the ramp. The ramp angle relative to the ground may be
too high for the robot to climb it.

The three gains of the PID controller represent the parameter vector
$\mathbf{\theta}=(K_{P},K_{I},K_{D})$. The state features are represented by
the occurrence of synthetic ice $z_{1}=\\{0,1\\}$ on the ramp and its
steepness $z_{2}=[0,30]$ as the inclination in degrees with respect to the
horizontal plane. Depending on the materials:

$z_{1}=\begin{cases}1&\textrm{if there is synthetic ice}\\\ 0&\textrm{if there
is no synthetic ice}.\end{cases}$

This function defines the feature vector $\mathbf{z}=(z_{1},z_{2})$ and the
feature-parameter vector as $\mathbf{x}=[\mathbf{z}:\mathbf{\theta}]$.

Fig. 1 shows the setup of the physical and simulated environment. We use the
Gazebo simulator to sample the data points to fit the Gaussian Process
estimator $\hat{p}_{X}$. We define both the set-point of the PID controller to
a $40\%$ of the maximum angular speed of the wheels and a sampling set for the
PID gains. Combining values for $\mathbf{z}$ and $\mathbf{\theta}$, we sample
more than 400 points in the feature-parameter space. We run a trial on the
simulator for each point and collect the performance result $y$ (Eq. 1). The
fitting of the GP was done on a standard desktop computer and took around 1
minute to process all the samples. Including more data points increased the
fitting time exponentially.

(a) Husky

(b) Multisense camera

(c) Gazebo simulator

(d) Gazebo camera

Figure 1: (a) and (b) Physical environment and on-board camera. Figs. (c) and
(d) Gazebo simulator environment and RGB camera.

To make the simulation result as aligned as possible to the physical
environment, we estimate the friction coefficients between the synthetic ice
and the rubber wheels of the robot. We sample a few trials in the physical
environment and search for the best coefficient to reproduce the same
performance results. In our experiment, we can easily estimate the coefficient
as we only have two materials. For more complex scenarios, the authors in [24]
propose a method based on annotated data to estimate the coefficient from
pixel-based signals.

Using an RBF as the kernel for the Gaussian process approximator, we fit
$\hat{p}_{X}$ with the results of the simulated trials. By setting a
confidence threshold as $\eta_{p}=0.8$, we can find the attainment regions of
the feature-parameter space where the model will predict an $80\%$ of success
rate. Fig. 2(a) shows the attainment region in light-blue, where the robot is
expected to succeed with a probability $P(y|\mathbf{x})\geq 0.8$. In the same
subfigure, the horizontal axis represents the angle of the ramp for trials
where we used synthetic ice. The vertical axis represents the proportional
gain $K_{P}$ of the PID controller. Fig. 2(b) shows the attainment region when
no synthetic ice is present. Comparing Figs. 2(a) and 2(b), we can see that
the occurrence of the ice material reduces the options in the feature-
parameters space where the robot can reach the goal. Fig. 2(c) shows that a
large $K_{P}$ (vertical axis) can be detrimental when the low-friction
material is present. The attainment region in Fig. 2(d) shows that the success
of the goal depends on the occurrence of the ice and the steepness of the
ramp. Figs. 2(e) and 2(f) show that the results of the task do not depend on
$K_{I}$ and $K_{D}$.

(a) $K_{P}$ vs angle (ice)

(b) $K_{P}$ vs angle (no ice)

(c) $K_{P}$ vs ice

(d) Ice vs angle

(e) $K_{I}$ vs angle (no ice)

(f) $K_{D}$ vs angle (no ice)

Figure 2: Light-blue areas represent attainment regions. The blue arrows
represent the direction of a counterfactual solution (a) and an adaptive one
(b). The dots represent data points. Red dots are failures, and grey ones
represent successful trials. Note that at each data point, there may be
overlaps of different runs. The images are slices of the 5-dimensional
parameter-feature space. In (a), (b), (c) and (d), the variables not shown are
not restricted. In (e) and (f), $K_{p}$ has been restricted to $1.0$.

###  III-A Physical Robot Implementation

As we do not have direct access to the features in a physical setup, we need
to extract them from sensors attached to the robot. From the sensory data, we
can use automatic feature extraction methods. However, sampling directly from
a robot can be expensive. A standard way to circumvent this limitation is to
use a physical simulator and tune the parameters to correlate the simulation
results with the real ones. Here, we propose to train a Beta-VAE [25] to
encode and decode images from an RGB camera in the simulated environment and
use its latent space as the feature space. As the autoencoder will be trained
on synthetic data, we will use a mapping to correct any deviation in the
encoding when using real images from the camera of the physical robot
$\mathbf{z}=m(z^{\prime}(\mathbf{s}))$, with $z^{\prime}:S\to Z$ as the Beta-
VAE encoding.

As we can linearly interpolate the features in an autoencoded latent space, we
use a linear function for $m$. A linear model allows us to fit its parameter
with just a couple of samples. In our experiments, this model effectively
translated the features from the simulator to the physical ones. Note that
this mapping allows us to carry the posterior learned during training with the
simulated system. Now, the performance predictor in the physical system is:

$\hat{p}_{X}(\mathbf{x})=\hat{p}_{X}((\mathbf{z},\mathbf{\theta}))=\hat{p}_{X}((m(z^{\prime}(\mathbf{s})),\mathbf{\theta})).$
(4)

From the data collected during the simulated trials from the previous step and
using data augmentation techniques, we train a Beta-VAE with the RGB images
from the onboard camera as a reconstruction target. The meta-parameters of the
autoencoder include a latent dimension of size 32, $\beta=20$, 5 hidden layers
of convolutional filters with batch normalisation, ReLU activation function
and a dropout rate of $0.5$ in both the encoder and decoder model. Fig. 3
shows a sample of manipulation of the latent space. Each row is a linear
modification of a latent dimension. To map the latent dimensions to the
features used to train the Gaussian process, we select two latent variables
that best represent the occurrence of synthetic ice and the steepness of the
ramp. In Fig. 3, the row marked with red shows the initial decoding of the
latent dimension where no white blob can be seen, while it gradually appears
when the latent variable value is increased. The white blob in the image
indicates whether synthetic ice is present or not. In the same figure, the
green box indicates a latent variable where the height of the ramp decreases.
We associate the height of the ramp with its steepness feature. Note that the
goal of the autoencoder is to extract the features, and it does not aim at
having a perfect reconstruction. In this experimental setup, we have used
expert knowledge to choose the features. In more general cases, automatic
selection of the features can achieve similar results at the expense of
explainability. For example, the system could use all the latent variables in
the latent space of the autoencoder. In this case, our method would still find
the attainment regions and the solutions in parameter and feature space.
However, counterfactual solutions in feature space could be harder to
understand by the user. The features may not have a clear representation in
the environment or may present a correlation in the data that does not
necessarily have a causal relation with the task, e.g. the sharpness of the
RGB image.

Figure 3: Latent space of the Beta-VAE trained with images from the onboard
camera. Two latent dimensions are selected for the synthetic ice occurrence
(red-box) and the ramp steepness (green-box).

To fit the linear model, we select four images representing the maximum and
minimum steepness and the occurrence and absence of synthetic ice in the
physical environment. Encoding each image, we obtain values in the latent
space: for the lowest angle, the value is $0.095$, for the highest angle is
$-1.63$, for the occurrence of ice is $1.26$, and for the absence of it, a
value of $0.35$. With two points for each latent dimension, we can calculate
the linear mapping:

$\displaystyle z_{1}=m_{I}(x)$ $\displaystyle=1.10x-0.38,$ (5) $\displaystyle
z_{2}=m_{A}(x)$ $\displaystyle=-17.39x+1.65,$ (6)

with $m_{A}$ and $m_{I}$ the functions for angle and the occurrence of
synthetic ice, respectively.

We use the attainment regions to find solutions on the physical Husky when the
prediction is ‘failure’. Using the known PID parameters and extracting the
state features from the camera, we can estimate the outcome of a trial. If the
value is outside the attainment region, we can find a solution either on the
feature or parameter space. The simplest solution is to find the smallest
modification to $\mathbf{\theta}$ that can move the performance prediction
inside the attainment region with fix features variables. To find this
modification, we use the sampling optimisation process [22] constrained to the
prior ($\hat{p}_{X}$) and the minimum Euclidean distance to the attainment
region. This solution correspond to moving on the parameter space, e.g.
horizontal axis on Fig. 2(b) blue $\mathbf{x}$, from a value of $K_{P}=1.3$ to
a value in the region limit of $K_{P}=0.8$. The controller can adapt to these
new parameters online and have a successful trial with parameters that have
not been directly experienced during training. Using the image taken from the
onboard camera, Fig. 1(b), we extract the latent values and map them with Eqs.
5 and 6 to the feature space. We define the parameters of the controller as
the feature-parameter vector
$\mathbf{x}=[z_{1},z_{2},K_{P},K_{I},K_{D}]=[1.09,13.53,0.05,$1\text{\times}{10}^{-6}$,0]$
that fails the task. The prediction of $\hat{p}_{X}(\mathbf{x})$ is $0.52$,
outside of the attainment region. Freezing $z_{1}$ and $z_{2}$, the system
find the new optimal parameter $\mathbf{\theta}^{*}=[0.5,0.00001,0.0]$ with
performance of $0.802$, in the limit of the attainment region. We test these
parameters on the Husky on three trials. All the trials succeed in the task.

The other type of solution that this system can provide are counterfactuals.
Fig. 2(a) blue $\mathbf{x}$ point shows that in an angle around $22^{\circ}$
with ice on the ramp, the Husky will fail to meet the goal. The solution,
moving on the feature space, shows a counterfactual where reducing the angle
of the ramp to $8^{\circ}$ would produce a successful trial with the required
minimum performance. We can also fix the angle of the ramp, so the system is
forced to find a solution in the rest of the feature, i.e. the synthetic ice.
In this case, the solution is at $z_{1}^{*}=0.53$, that using a threshold in
the middle point of the linear mapping for Eq. 5, represents the absence of
ice as another counterfactual solution.

##  IV CONCLUSION

We introduce the concept of attainment regions. Through our experiments, we
have shown that these regions can be used to achieve generalisation,
robustness, explainability, adaptability and debugging of an autonomous mobile
robot in realistic settings. These characteristics are relevant for
trustworthy autonomous robots in critical tasks. The advantage of our
definition of attainment regions compared to analysis of performance in
action-state space comes from its compact representation based on features and
parameters. We demonstrated extraction of features from an image-based sensory
input using autoencoders. More advanced feature extraction techniques would
facilitate even more sophisticated features within the proposed methodology.

## References

  * [1] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [2] S. Schaal _et al._ , “Learning from demonstration,” _Advances in neural information processing systems_ , pp. 1040–1046, 1997.
  * [3] R. R. Burridge, A. A. Rizzi, and D. E. Koditschek, “Sequential composition of dynamically dexterous robot behaviors,” _The International Journal of Robotics Research_ , vol. 18, no. 6, pp. 534–555, 1999.
  * [4] S. Heim, A. Rohr, S. Trimpe, and A. Badri-Spröwitz, “A learnable safety measure,” in _Conference on Robot Learning_. PMLR, 2020, pp. 627–639.
  * [5] S. Bansal, M. Chen, S. Herbert, and C. J. Tomlin, “Hamilton-Jacobi reachability: A brief overview and recent advances,” in _2017 IEEE 56th Annual Conference on Decision and Control (CDC)_. IEEE, 2017, pp. 2242–2253.
  * [6] D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” _arXiv preprint arXiv:1312.6114_ , 2013.
  * [7] K. Zhou and J. C. Doyle, _Essentials of robust control_. Prentice hall Upper Saddle River, NJ, 1998, vol. 104.
  * [8] S.-Y. Chu and C.-C. Teng, “Tuning of PID controllers based on gain and phase margin specifications using fuzzy neural network,” _Fuzzy sets and systems_ , vol. 101, no. 1, pp. 21–30, 1999.
  * [9] J. D. Blight, R. Lane Dailey, and D. Gangsaas, “Practical control law design for aircraft using multivariable techniques,” _International Journal of Control_ , vol. 59, no. 1, pp. 93–137, 1994.
  * [10] G. Piovan and K. Byl, “Reachability-based control for the active slip model,” _The International Journal of Robotics Research_ , vol. 34, no. 3, pp. 270–287, 2015.
  * [11] J.-P. Aubin, A. M. Bayen, and P. Saint-Pierre, _Viability theory: new directions_. Springer Science & Business Media, 2011.
  * [12] A. Liniger and J. Lygeros, “Real-time control for autonomous racing based on viability theory,” _IEEE Transactions on Control Systems Technology_ , vol. 27, no. 2, pp. 464–478, 2017.
  * [13] I. Rahwan, M. Cebrian, N. Obradovich, J. Bongard, J.-F. Bonnefon, C. Breazeal, J. W. Crandall, N. A. Christakis, I. D. Couzin, M. O. Jackson, _et al._ , “Machine behaviour,” _Nature_ , vol. 568, no. 7753, pp. 477–486, 2019.
  * [14] Y. Zhou, S. Booth, N. Figueroa, and J. Shah, “Rocus: Robot controller understanding via sampling,” _arXiv preprint arXiv:2012.13615_ , 2020.
  * [15] S. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” _arXiv preprint arXiv:1705.07874_ , 2017.
  * [16] S. C. Smith and S. Ramamoorthy, “Counterfactual explanation and causal inference in service of robustness in robot control,” 2020.
  * [17] C. Fan, X. Qin, and J. Deshmukh, “Parameter searching and partition with probabilistic coverage guarantees,” _arXiv preprint arXiv:2004.00279_ , 2020\.
  * [18] R. P. Borase, D. Maghade, S. Sondkar, and S. Pawar, “A review of PID control, tuning methods and applications,” _International Journal of Dynamics and Control_ , pp. 1–10, 2020.
  * [19] T. Dreossi, “Sapo: Reachability computation and parameter synthesis of polynomial dynamical systems,” in _Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control_ , 2017, pp. 29–34.
  * [20] C. E. Rasmussen, “Gaussian processes in machine learning,” in _Summer school on machine learning_. Springer, 2003, pp. 63–71.
  * [21] D. Berthelot, C. Raffel, A. Roy, and I. Goodfellow, “Understanding and improving interpolation in autoencoders via an adversarial regularizer,” _arXiv preprint arXiv:1807.07543_ , 2018.
  * [22] M. Burke, S. Penkov, and S. Ramamoorthy, “From explanation to synthesis: Compositional program induction for learning from demonstration,” _Robotics: Science and Systems (R:SS)_ , June 2019.
  * [23] S. C. Smith and S. Ramamoorthy, “Semi-supervised learning from demonstration through program synthesis: An inspection robot case study,” _Electronic Proceedings in Theoretical Computer Science_ , vol. 319, pp. 81–101, Jul 2020\. [Online]. Available: http://dx.doi.org/10.4204/EPTCS.319.7
  * [24] M. Brandao, K. Hashimoto, and A. Takanishi, “Friction from vision: A study of algorithmic and human performance with consequences for robot perception and teleoperation,” in _2016 IEEE-RAS 16th International Conference on Humanoid Robots (Humanoids)_. IEEE, 2016, pp. 428–435.
  * [25] I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner, “Beta-VAE: Learning basic visual concepts with a constrained variational framework,” 2016.


# Valuation rings of dimension one as limits of smooth algebras

Dorin Popescu  Simion Stoilow Institute of Mathematics of the Romanian
Academy, Research unit 5, University of Bucharest, P.O. Box 1-764, Bucharest
014700, Romania, Email<EMAIL_ADDRESS>
###### Abstract.

As in Zariski’s Uniformization Theorem we show that a valuation ring $V$ of
characteristic $p>0$ of dimension one is a filtered direct limit of smooth
${\bf F}_{p}$-algebras under some conditions of transcendence degree. Under
mild conditions, the algebraic immediate extensions of valuation rings are
dense if they are filtered direct limit of smooth morphisms.

Key words  : Immediate extensions of valuations rings, Pseudo convergent
sequences, Pseudo limits, smooth morphisms, Henselian rings.
2010 Mathematics Subject Classification: Primary 13F30, Secondary
13A18,13L05,13B40.

## Introduction

Zariski predicted, and proved in characteristic $0$ in [20], that any integral
algebraic variety X equipped with a dominant morphism $v:Spec(V)\rightarrow X$
from a valuation ring $V$ can be desingularized along $V$ : there should exist
a proper birational map ${\tilde{X}}\rightarrow X$ for which the lift
${\tilde{v}}:Spec(V)\rightarrow{\tilde{X}}$ of $v$ supplied by the valuative
criterion of properness would factor through the regular locus of $\tilde{X}$.
This local form of resolution of singularities remains open in positive and
mixed characteristic, and implies that every valuation ring V should be a
filtered direct limit of regular rings. A filtered direct limit (in other
words a filtered colimit) is a limit indexed by a small category that is
filtered (see [16, 002V] or [16, 04AX]). A filtered union is a filtered direct
limit in which all objects are subobjects of the final colimit, so that in
particular all the transition arrows are monomorphisms. There exists several
nice extensions of Zariski’s Uniformization Theorem as for example recently
the result of B. Antieau, R. Datta [1, Theorem 4.1.1], which says that every
perfect valuation ring of characteristic $p>0$ is a filtered union of its
smooth ${\bf F}_{p}$-subalgebras. This result is an application of [18,
Theorem 1.2.5] which relies on some results from [3]. Also E. Elmanto and M.
Hoyois proved that an absolute integrally closed valuation ring of residue
field of characteristic $p>0$ is a filtered union of its regular finitely
generated ${\bf Z}$-subalgebras (see [1, Corollary 4.2.4]).

The goal of this paper is to establish a kind of Zariski’s Uniformization
Theorem in characteristic $p>0$ and dimension one.

######  Theorem 1.

Let $V$ be a one dimensional valuation ring containing a perfect field $F$ of
characteristic $p>0$, $k$ its residue field, $\Gamma$ its value group and $K$
its fraction field. Then the following statements hold

  1. (1)

if $k\subset V$ and $K=k(x)$ for some system of algebraically independent
elements $x=(x_{1},\ldots,x_{r})\in V^{r}$ over $k$ such that
$\Gamma=\oplus_{i=1}^{r-1}{\bf Z}\mathrm{val}(x_{i})$ then $V$ is a filtered
union of its polynomial $k$-subalgebras, in particular of its smooth
$F$-subalgebras,

  2. (2)

if $\Gamma$ is free of rank $r$, $k\subset V$ and $x=(x_{1},\ldots,x_{r})\in
V^{r}$ is a system of elements such that $\Gamma=\oplus_{i=1}^{r}{\bf
Z}\mathrm{val}(x_{i})$ and $K/k(x)$ is algebraic then $V$ is a filtered union
of its smooth $F$-subalgebras, in particular of its smooth ${\bf
F}_{p}$-subalgebras,

  3. (3)

if $\Gamma$ is free of rank $r$, $k/F$ is a field extension of finite type and
$\operatorname{tr\,deg}_{F}K=\operatorname{tr\,deg}_{F}k+r$, then $V$ is a
filtered union of its smooth $F$-subalgebras, in particular of its smooth
${\bf F}_{p}$-subalgebras.

The proof is given in Corollaries 12, 16, 17. The idea of the proof of Theorem
1 (1) is to see that $W=V\cap k(x)$ is a filtered union of its localizations
of polynomial $k$-subalgebras and then to reduce to show that the immediate
extension $W\subset V$ is a filtered union of its smooth $W$-subalgebras. This
is done somehow in [14, Proposition 18] when $k\supset{\bf Q}$. If char $k>0$
this does not work (see e.g. [12, Remark 6.10]), the reason being that in
general a valuation ring could have a so called defect as was noted by
Ostrowski. The Generalized Stability Theorem of F. V. Kuhlmann [6, Theorem
1.1] says in particular that $W$ is defectless (see Corollary 6) and so we may
show (1) using Lemma 10. For Theorem 1 (2) we see that $W\subset V$ is dense
and we use a Néron-Schappacher Theorem (see e.g. [12, Theorem 4.1]) or a kind
of General Néron Desingularization (see Lemma 15) which allow us to handle
dense extensions.

When $V$ contains $\bf Q$ then an immediate algebraic extension of valuation
rings $V\subset V^{\prime}$ is dense by Ostrowski’s Defektsatz [10, Sect. 9,
No 57]. It follows that $V\subset V^{\prime}$ is a filtered direct limit of
smooth $V$-algebras (see e.g. [14, Proposition 9]). The converse is also
mainly true as shows the following result (see Theorem 23).

######  Theorem 2.

Let $V^{\prime}$ be an immediate algebraic extension of a valuation ring $V$,
$\hat{V}$ the completion of $V$ and $K$, ${\hat{K}}$ the fraction fields of
$V$, ${\hat{V}}$. Assume that $\operatorname{tr\,deg}_{K}{\hat{K}}\geq 1$,
${\hat{K}}/K$ is separable, $V^{\prime}$ is a filtered direct limit of smooth
$V$-algebras and either $V$ is Henselian, or $\dim V=1$. Then $V\subset
V^{\prime}$ is dense.

We owe thanks to F. V. Kuhlmann who hinted us some mistakes in some
preliminary forms of the paper. Also we owe thanks to Kęstutis Česnavičius who
hinted us some mistakes in the preliminary forms of Theorem 19.

##  1\. The Defect

Let $V$ be a valuation ring with value group $\Gamma$, $K$ its fraction field
and its valuation $\mathrm{val}:K^{*}=K\setminus\\{0\\}\rightarrow\Gamma$. Let
$F$ be a finite field extension of $K$, $v_{i}$, $1\leq i\leq r$ the
valuations of $F$ extending $\mathrm{val}$ and $V_{i}$ be the valuation rings
of $F$ defined by $v_{i}$. Let $e_{i},f_{i}$ be the ramification index
respectively the degree of the residue field extension of $V_{i}$ over $V$. It
is well known that

$[F:K]\geq\sum_{i=1}^{r}e_{i}f_{i}.$

If this inequality is equality for all finite (resp. finite separable) field
extensions $F$ of $V$ we say that $V$ is defectless (resp. separably
defectless, see [7] for details and examples).

We remind the following important result for the existence of defectless
valuation rings.

######  Theorem 3.

([2, Theorem 2, VI, (8.5)]) Let $F$ be a finite field extension of $K$ and $B$
be the integral closure of $V$ in $F$. Then the above inequality is equality
if and only if $B$ is a free $V$-module.

######  Lemma 4.

Let $V$ be a valuation ring and $S$ a multiplicative closed system from $V$.
If $V$ is defectless (resp. separably defectless) then the valuation ring
$S^{-1}V$ is defectless (resp. separably defectless) too.

###### Proof.

Assume $V$ is defectless (the proof in the separably defectless case is
similar). Let $F$ be a finite field extension of the fraction field $K$ of $V$
(and of $S^{-1}V$ too) and $B$, $B^{\prime}$ be the integral closures of $V$,
respectively $S^{-1}V$ in $F$. By Theorem 3 we have to show that $B^{\prime}$
is a free $S^{-1}V$-module. As $V$ is defectless by the quoted theorem we see
that $B$ is a free $V$-module and so $S^{-1}B$ is a free $S^{-1}V$-module.

We claim that $B^{\prime}\cong S^{-1}B$ which is enough. Indeed, let $z\in F$
be integral over $S^{-1}V$. We have

$z^{e}+\sum_{i=0}^{e-1}(a_{i}/s)z^{i}=0$

for some $e\in{\bf N}$, $a_{i}\in V$ and $s\in S$. Then

$(sz)^{e}+\sum_{i=0}^{e-1}s^{e-i-1}a_{i}(sz)^{i}=0$

and so $sz\in B$, which shows our claim.

Next it is very useful the following particular form of the Generalized
Stability Theorem of F. V. Kuhlmann (see [6, Theorem 1.1], [7, Theorem 5.1]).

######  Theorem 5.

Let $V\subset V^{\prime}$ be an extension of valuation rings with the same
residue field, $\Gamma\subset\Gamma^{\prime}$ its value group extension and
$K\subset K^{\prime}$ its fraction field extension. Assume $K^{\prime}/K$ is a
finite type field extension and $\Gamma^{\prime}/\Gamma$ is a finitely
generated free $\bf Z$-module of rank $\operatorname{tr\,deg}K^{\prime}/K$. If
$V$ is defectless (resp. separably defectless) then $V^{\prime}$ is defectless
(resp. separably defectless) too.

######  Corollary 6.

Let $V$ be a valuation ring of characteristic $p>0$ with finitely generated
value group $\Gamma$ and fraction field $K$. Assume $V$ contains its residue
field $k$ and $K=k(y)$ for some elements $y=(y_{1},\ldots,y_{r})$ of $V$ such
that $\mathrm{val}(y_{i})$, $1\leq i\leq r$ is a basis of the free $\bf
Z$-module $\Gamma$. Then $V$ is defectless.

For the proof note that $k$ is defectless for the trivial valuation, $y$ is
algebraically independent over $k$ by [2, Theorem 1, (10.3)] and apply the
above theorem to $k\subset V$.

######  Proposition 7.

(Kuhlmann, [6, Theorem 1.1]) Let $V$ be a valuation ring, ${\mathfrak{m}}$ its
maximal ideal and $X=(X_{1},\ldots,X_{n})$ some variables. If $V$ is
defectless then the valuation ring $V_{1}=V[X]_{{\mathfrak{m}}V[X]}$ is
defectless too.

###### Proof.

Applying induction on $n$ we reduce to the case $n=1$. Let $\Gamma$ be the
value group of $V$ and set $\Gamma^{\prime}=\Gamma\oplus{\bf Z}\gamma$ where
$\gamma$ is taken to be positive but $<$ than all positive elements of
$\Gamma$ and let $w$ be the valuation on $K(X)$ extending $\mathrm{val}$ by
$X\rightarrow\gamma$. By Theorem 5 we see that $W$, the valuation ring of $w$,
is defectless. Note that ${\mathfrak{m}}W$ is a prime ideal of $W$ and
$W_{{\mathfrak{m}}W}\cong V_{1}$ is defectless by Lemma 4.

An inclusion $V\subset V^{\prime}$ of valuation rings is an _immediate
extension_ if it is local as a map of local rings and induces equalities
between the value groups and the residue fields of $V$ and $V^{\prime}$. It is
dense if for any $x^{\prime}\in V^{\prime}$ and $\gamma\in\Gamma$ there exists
$x\in V$ such that $\mathrm{val}(x-x^{\prime})>\gamma$.

Let $\lambda$ be a fixed limit ordinal and $v=\\{v_{i}\\}_{i<\lambda}$ a
sequence of elements in $V$ indexed by the ordinals $i$ less than $\lambda$.
Then $v$ is _pseudo convergent_ if

$\mathrm{val}(v_{i}-v_{i^{\prime\prime}})<\mathrm{val}(v_{i^{\prime}}-v_{i^{\prime\prime}})\
\ \mbox{for}\ \ i<i^{\prime}<i^{\prime\prime}<\lambda$ (see [4], [15]). A
_pseudo limit_ of $v$ is an element $x\in V$ if

$\mathrm{val}(x-v_{i})=\mathrm{val}(v_{i}-v_{i^{\prime}}))\ \ \mbox{for}\ \
i<i^{\prime}<\lambda$. We say that $v$ is

  1. (1)

_algebraic_ if some $f\in V[T]$ satisfies
$\mathrm{val}(f(v_{i}))<\mathrm{val}(f(v_{i^{\prime}}))$ for large enough
$i<i^{\prime}<\lambda$;

  2. (2)

_transcendental_ if each $f\in V[T]$ satisfies
$\mathrm{val}(f(v_{i}))=\mathrm{val}(f(v_{i^{\prime}}))$ for large enough
$i<i^{\prime}<\lambda$.

When for any $\gamma\in\Gamma$ it holds
$\mathrm{val}(v_{i}-v_{i^{\prime}})>\gamma$ for $i<i^{\prime}<\lambda$ large
we call $v$ fundamental.

######  Lemma 8.

Let $V\subset V^{\prime}$ be an immediate extension of one dimensional
valuation rings and $K\subset K^{\prime}$ their fraction field extension. If
$V$ is separably defectless and $K^{\prime}/K$ is separable and algebraic then
$K^{\prime}/K$ is dense. Moreover, if $K^{\prime}/K$ is not separable but $V$
is defectless then $K^{\prime}/K$ is still dense.

###### Proof.

We may reduce to the case when $K^{\prime}/K$ is finite separable. Let
$K^{h}$, $K^{\prime h}$ be the Henselizations of $K$ respectively $K^{\prime}$
and $L=K^{h}(K^{\prime})\subset K^{\prime h}$. By [7, Theorem 2.3] we have
$K^{h}$ separably defectless and so we have
$[L:K^{h}]=e_{L/K^{h}}f_{L/K^{h}}=1$ because there exists an unique extension
of the valuation of $V$ to $K^{h}$. Thus $L\subset K^{h}$ and $K\subset K^{h}$
is dense because $\dim K=1$. The second statement goes similarly.

######  Example 9.

We consider [12, Example 3.1.3] inspirated by [10]. Let $k$ be a field of
characteristic $p>0$, $X$ a variable, $\Gamma={\bf Q}$ and $K$ the fraction
field of the group algebra $k[\Gamma]$, that is the rational function in
$\\{X^{q}\\}_{q\in{\bf Q}}$. Let $P$ be the field of all formal sums
$z=\sum_{n\in{\bf N}}a_{n}X^{\gamma_{n}}$ where $(\gamma_{n})_{n\in{\bf N}}$
is a monotonically increasing sequence from $\Gamma$ and $a_{n}\in k$. Set
$\mathrm{val}(z)=\gamma_{s}$, where $s=\operatorname{min}\\{n\in{\bf
N}:a_{n}\not=0\\}$ if $z\not=0$ and let $V^{\prime}$ be the valuation ring
defined by $\mathrm{val}:P^{*}\rightarrow\Gamma$.

Let $\rho_{n}=(p^{n+1}-1)/(p-1)p^{n+1}$,

$y=-1+\sum_{n\geq 0}(-1)^{n}X^{\rho_{n}}$

and $a_{i}=-1+\sum_{0\leq n\leq i}(-1)^{n}X^{\rho_{n}}$. We have
$1+\rho_{n}=p\rho_{n+1}$ for $n\geq 0$ and $p\rho_{0}=1$ and y is a pseudo
limit of the pseudo convergent sequence $a=(a_{i})_{i\in{\bf N}}$, which has
no pseudo limit in $K$. Then $x$ is a root of the separable polynomial
$g=Y^{p}+XY+1\in K[Y]$ and the algebraic separable extension $V=V^{\prime}\cap
K\subset V^{\prime}\cap K(y)$ is not dense. The above lemma cannot be applied
because $V$ is not separably defectless.

######  Lemma 10.

Let $V\subset V^{\prime}$ be an immediate extension of one dimensional
valuation rings, $K\subset K^{\prime}$ their fraction field extension and
$x\in V^{\prime}$ a transcendental element over $K$. Assume $V$ is separably
defectless and $x$ is a pseudo limit of a pseudo convergent sequence $a$ over
$V$ which has no pseudo limit in $V$. Then $a$ is transcendental.

###### Proof.

Let $a=(a_{j})_{j<\lambda}$ and assume $a$ is algebraic. Let $h\in V[X]$ be a
primitive polynomial of minimal degree among the polynomials $f\in V[X]$ such
that $\mathrm{val}(f(a_{j}))<\mathrm{val}(f(a_{j+1}))$ for all $j<\lambda$. We
may take $h$ separable. Indeed, assume that $h$ is not separable. We have
$\mathrm{val}(h(x))>\mathrm{val}(h(a_{j}))$ for $j<\lambda$ large. Choose
$b\in V$ such that $\mathrm{val}(bx)>\mathrm{val}(h(x))$ and set
$h^{\prime}=h+bX$. Note that $\mathrm{val}(x)=\mathrm{val}(a_{j})$ for $j$
large, which implies
$\mathrm{val}(ba_{j})=\mathrm{val}(bx)>\mathrm{val}(h(x))>\mathrm{val}(h(a_{j}))$
for $j$ large. It follows that
$\mathrm{val}(h^{\prime}(a_{j}))=\mathrm{val}(h(a_{j}))$ and we may replace
$h$ by $h^{\prime}$, which is separable.

By [4, Theorem 3] there exists a finite separable immediate extension $L=K(z)$
of $K$ such that $h(z)=0$ and $z$ is a pseudo limit of $a$. By Lemma 8 $L$ is
dense over $K$ and so $a$ has a pseudo limit in $K$ (see e.g. [12, Lemma
2.5]), which is false.

######  Proposition 11.

Let $V\subset V^{\prime}$ be an immediate extension of one dimensional
valuation rings and $K\subset K^{\prime}$ their fraction field extension.
Assume $V$ is separably defectless and $K^{\prime}=K(x)$ for some $x\in
K^{\prime}$ which is transcendental over $V$. Then $V^{\prime}$ is a filtered
union of localizations of its polynomial $V$-subalgebras in one variable.

###### Proof.

Then $x$ is a pseudo limit of a pseudo convergent sequence $a$ over $V$ which
has no pseudo limit in $V$ by [4, Theorem 1]. But $a$ is transcendental by
Lemma 10 and using [11, Lemma 3.2] or [14, Lemma 15] we are done.

######  Corollary 12.

Let $V$ be a one dimensional valuation ring, $K$ its fraction field, $k$ its
residue field and $\Gamma$ its value group. Assume $k\subset V$ and $K=k(x)$
for some system of algebraically independent elements
$x=(x_{1},\ldots,x_{r})\in V^{r}$ over $k$ such that either
$\Gamma=\oplus_{i=1}^{r}{\bf Z}\mathrm{val}(x_{i})$, or
$\Gamma=\oplus_{i=1}^{r-1}{\bf Z}\mathrm{val}(x_{i})$. Then $V^{\prime}$ is a
filtered union of localizations of its polynomial $V$-subalgebras in $r$
variables.

###### Proof.

The first case is a consequence of [2, Theorem 1, VI, (10.3)] and [11, Lemma
4.6] (see also [14, Lemma 26 (1)]). In the second case we see that $V$ is an
immediate extension of $W=V\cap k(x_{1},\ldots,x_{r-1})$. As above $W$ is a
filtered union of localizations of its polynomial $V$-subalgebras in $(r-1)$
variables. By Corollary 6 we have $W$ defectless and using Proposition 11 we
are done.

##  2\. Valuation rings as limits of smooth algebras

######  Proposition 13.

Let $V\subset V^{\prime}$ be an immediate extension of one dimensional
valuation rings and $K\subset K^{\prime}$ their fraction field extension.
Assume $V$ is separably defectless and $K^{\prime}/K$ is algebraic separable.
Then $V^{\prime}$ is a filtered union of its smooth $V$-subalgebras.

###### Proof.

By Lemma 8 the extension $V\subset V^{\prime}$ is dense. Then by a Néron-
Scappacher Theorem (see e.g. [12, Theorem 4.1]) we see that $V^{\prime}$ is a
filtered direct limit of smooth $V$-algebras.

######  Corollary 14.

Let $V$ be a one dimensional valuation ring of characteristic $p>0$ with a
free (over $\bf Z$) value group $\Gamma$ of rank $r$ and fraction field $K$.
Assume $V$ contains its residue field $k$ and $x=(x_{1},\ldots,x_{r})\in
V^{r}$ is a system of elements such that $\Gamma=\oplus_{i=1}^{r}{\bf
Z}\mathrm{val}(x_{i})$ and $K/k(x)$ is algebraic separable. Then $V$ is a
filtered union of its smooth $k$-subalgebras.

###### Proof.

By Corollary 6 we see that $W=V\cap k(x)$ is defectless and so $V$ is a
filtered union of its smooth $W$-subalgebras using the above proposition. But
$W$ is a filtered union of its smooth $k$-algebras (see [2, Theorem 1, VI,
(10.3)], [11, Lemma 4.6], [14, Lemma 26 (1)]), which is enough.

We need the following lemma ([14, Lemma 7] which is an extension of [5,
Proposition 3], and [13, Proposition 5]).

######  Lemma 15.

For a commutative diagram of ring morphisms

$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{b\,\mapsto\,a}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{V}$that
factors as
follows$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{V/a^{3}V}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A^{\prime}/a^{3}A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

with $B$ finitely presented over $A$, a $b\in B$ that is standard over $A$
(this means a special element from the ideal $H_{B/A}$ defining the non smooth
locus of $B$ over $A$, for details see for example [14, Lemma 4]), and a
nonzerodivisor $a\in A^{\prime}$ that maps to a nonzerodivisor in $V$ that
lies in every maximal ideal of $V$, there is a smooth $A^{\prime}$-algebra $S$
such that the original diagram factors as follows:

$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{V.}$$\textstyle{A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{S\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$

In fact the separability condition is not necessary in Corollary 14.

######  Corollary 16.

Let $V$ be a one dimensional valuation ring of characteristic $p>0$ with a
free (over $\bf Z$) value group $\Gamma$ of rank $r$ and fraction field $K$.
Assume $V$ contains its residue field $k$ and $x=(x_{1},\ldots,x_{r})\in
V^{r}$ is a system of elements such that $\Gamma=\oplus_{i=1}^{r}{\bf
Z}\mathrm{val}(x_{i})$ and $K/k(x)$ is algebraic. Then $V$ is a filtered union
of its smooth $k$-subalgebras.

###### Proof.

As in Corollary 14 we see that $W=V\cap k(x)$ is defectless and so the
algebraic extension $W\subset V$ is dense by Lemma 8. Let $E\subset V$ be a
finitely generated $F$-subalgebra and $w:E\rightarrow V$ its inclusion. Assume
$E=F[Y]/I$, for $Y=(Y_{1},\ldots,Y_{n})$. Using [17, Lemma 1.5] it is enough
to show that $w$ factors through a smooth $F$-algebra. Note that $K/F$ is
separable because $F$ is perfect. Thus $E/F$ is separable and
$w(H_{E/F})\not=0$, let us assume that $w(H_{E/F})V\supset zV$ for some $z\in
W$, $z\not=0$. Replacing $z$ by a power of it we may assume that
$z=\sum_{i}^{s}b_{i}b^{\prime}_{i}$ for some $b_{i}=\det(\partial
f_{ij}/\partial Y_{j_{i}})$ for some systems of polynomials $f_{i}$ from $I$
and $b^{\prime\prime}_{i}\in F[Y]$ which kills $I/(f_{i})$. Similarly as in
[5, Lemma 4] we may assume that we can take $s=1$, that is for some
polynomials $f=(f_{1},\ldots,f_{r})$ from $I$, we have $z\in NME$ for some
$N\in((f):I)$ and a $r\times r$-minor $M$ of the Jacobian matrix $(\partial
f_{i}/\partial Y_{j})$ (since $V$ is a valuation ring this reduction is much
easier). Thus we may assume $z$ is standard over $F$, which is necessary later
to apply Lemma 15.

Set $E^{\prime}=E\otimes_{F}W$ and let $w^{\prime}:E^{\prime}\rightarrow V$ be
the map induced by $w$. We have $w^{\prime}(H_{E^{\prime}/W})\supset zV$ and
note that $w^{\prime}$ factors modulo $z^{3}$ through the smooth
$W/z^{3}W$-algebra $W/z^{3}W\cong V/z^{3}V$ since $W\subset V$ is dense. Then
using Lemma 15 we see that $w^{\prime}$ factors through a smooth $W$-algebra.
Since $W$ is a filtered direct limit of smooth $k$-algebra as in Corollary 14
we see that $w$ factors through a smooth $k$-algebra even $F$-algebra.
Actually, we may apply as in Proposition 13 a variant of Néron-Schappacher
Theorem to get $V$ as a filtered union of its smooth $W$-subalgebras and we
are done.

######  Corollary 17.

Let $V$ be a one dimensional valuation ring containing a perfect field $F$ of
characteristic $p>0$, $\Gamma$ its value group, $K$ its fraction field and $k$
its residue field. Assume $\Gamma$ is free of rank $r$, $k/F$ is a field
extension of finite type and
$\operatorname{tr\,deg}_{F}K=\operatorname{tr\,deg}_{F}k+r$. Then $V$ is a
filtered union of its smooth $F$-subalgebras, in particular of its smooth
${\bf F}_{p}$-algebras.

###### Proof.

Let $E\subset V$ be a finitely generated $F$-subalgebra and $w:E\rightarrow V$
its inclusion. Using [17, Lemma 1.5] it is enough to show that $w$ factors
through a smooth $F$-algebra. Using Lemma 15 we may replace $V$ by its
completion as in [14, Proposition 9]. So we may assume $V$ is Henselian. A
lifting of $k$ to $V$ could be done when $V$ is Henselian and char $k=p=0$
(see [19, Theorem 2.9]) but the proof goes in the same way when $p>0$ and $k$
is separably generated over $F$. In particular the lifting could be done when
$k/F$ is of finite type because $F$ is perfect. Thus we may assume $k\subset
V$ and $\operatorname{tr\,deg}_{k}K=r$. Choose some elements
$x=(x_{1},\ldots,x_{r})\in V^{r}$ such that $\Gamma=\oplus_{i=1}^{r}{\bf
Z}\mathrm{val}(x_{i})$. Then $W=V\cap k(x)\subset V$ is algebraic and we may
proceed as in Corollary 16.

##  3\. Algebraic pseudo convergent sequences

Let $V^{\prime}$ be an immediate extension of a valuation ring $V$, $K\subset
K^{\prime}$ their fraction field extension, $v=(v_{j})_{j<\lambda}$ a pseudo-
convergent sequence in $V$ which is not fundamental and has a pseudo limit $x$
in $V^{\prime}$, but having no pseudo limit in $K$. Suppose that
$K^{\prime}=K(x)$. We need the following result [8, Theorem 1.8].

######  Theorem 18.

(Kuhlmann-Ćmiel) Assume that $x$ is not a root of an irreducible polynomial
$f\in K[X]$ and either $\dim V=1$, or $V$ is Henselian. Then for all $z\in V$
there is a $\nu<\lambda$ such that $\mathrm{val}(f(z))<\mathrm{val}(f(v_{j}))$
for all $\nu<j<\lambda$.

######  Theorem 19.

Assume $x$ is transcendental over $K$ and either $\dim V=1$, or $V$ is
Henselian. Then the following statements are equivalent:

  1. (1)

for every polynomial $f\in V[X]$ with $f(x)\not=0$ there exists a $y\in V$
such that $\mathrm{val}(f(y))=\mathrm{val}(f(x))$,

  2. (2)

for every polynomial $f\in V[X]$ with $f(x)\not=0$ there exists a $y\in V$
such that $\mathrm{val}(f(y))\geq\mathrm{val}(f(x))$

  3. (3)

$v$ is transcendental,

  4. (4)

$V^{\prime}$ is a filtered union of its localizations of polynomial
$V$-subalgebras in one variable.

###### Proof.

First assume that (4) holds and let $f$ be as in (1). Let $d\in V$, $z\in
V^{\prime}$ be such that $f(x)=dz$ and $zz^{\prime}=1$ for some $z^{\prime}\in
V^{\prime}$. Then the solution $x,z,z^{\prime}$ in $V^{\prime}$ of the
polynomials $F_{1}=f-dZ,F_{2}=ZZ^{\prime}-1\in V[X,Z,Z^{\prime}]$ must be
contained in a localization of a polynomial $V$-subalgebra
$C=V[u^{\prime}]_{P(u^{\prime})}$ of $V^{\prime}$, where $P\in V[U]$ and
$u^{\prime}\in V^{\prime}$ is transcendental over $V$. Choose a $u\in V$ such
that $u\equiv u^{\prime}$ modulo ${\mathfrak{m}}^{\prime}$ the maximal ideal
of $V^{\prime}$. Then $P(u)$ is a unit in $V$ and the map $\rho:C\rightarrow
V$ given by $u^{\prime}\rightarrow u$ is a retraction of $V\subset C$ and
$y=\rho(x),\rho(z),\rho(z^{\prime})$ is a solution of $F_{1},F_{2}$ in $V$,
and so $\mathrm{val}(f(y))=\mathrm{val}(d)=\mathrm{val}(f(x))$.

Clearly (2) follows from (1) and assume that (2) holds but $v$ is algebraic.
This is not possible as F. V. Kuhlmann said, the proof being done in Theorem
18 (see also [9, Lemma 5.4]). Let $h\in V[T]$ be a polynomial with minimal
degree among the polynomials $f\in V[T]$ such that
$\mathrm{val}(f(v_{i}))<\mathrm{val}(f(v_{j}))$ for large $i<j<\lambda$. Then
$h$ is irreducible (see the proof of [15, (II,4), Lemma 12]). Note that
$\mathrm{val}(h(x)-h(v_{j}))\geq\mathrm{val}(x-v_{j})=\mathrm{val}(v_{j+1}-v_{j})$.
As the last term is increasing we must have
$\mathrm{val}(h(x))\geq\mathrm{val}(h(v_{j}))$ for all $j$. By Theorem 18 for
every $z\in V$ we have $\mathrm{val}(h(z))<\mathrm{val}(h(v_{j}))$ for $j$
large. Thus $h$ fails the condition (2) and so $v$ cannot be algebraic.

If $v$ is transcendental then $V^{\prime}$ is a filtered union of its
localizations of polynomial $V$-subalgebras in one variable by [11, Lemma 3.2]
(see also [14, Lemma 15]).

######  Corollary 20.

In the assumptions of the above theorem, if $v$ is algebraic then $V^{\prime}$
is not a filtered union of its localizations of polynomial $V$-subalgebras in
one variable.

######  Lemma 21.

In the assumptions of the above theorem, assume that $V$ is Henselian and
there exists an immediate extension of valuation rings $V^{\prime}\subset
V_{1}$ such that $V_{1}$ is a filtered direct limit of smooth $V$-algebras.
Then for every polynomial $f\in V[X]$ such that $f(x)\not=0$ there exists a
$y\in V$ such that $\mathrm{val}(f(y))=\mathrm{val}(f(x))$.

###### Proof.

Fix $f\in V[X]$. Let $d\in V$, $z\in V^{\prime}$ be such that $f(x)=dz$ and
$zz^{\prime}=1$ for some $z^{\prime}\in V^{\prime}$. Since $V_{1}$ is a
filtered direct limit of smooth $V$-algebras, the solution
$x,z^{\prime},z^{\prime}$ in $V^{\prime}$ of the polynomials
$F_{1}=f-dZ,F_{2}=ZZ^{\prime}-1\in V[X,Z,Z^{\prime}]$ must come from a
solution $\bar{x}$, $\bar{z}$, ${\bar{z}}^{\prime}$ in a smooth $V$-algebra
$C$. But $V$ is Henselian and so there exists a retraction $\rho:C\rightarrow
V$ of $V\subset C$. Thus
$y=\rho({\bar{x}}),\rho({\bar{z}}),\rho({\bar{z}}^{\prime})$ is a solution of
$F_{1},F_{2}$ in $V$, and so
$\mathrm{val}(f(y))=\mathrm{val}(d)=\mathrm{val}(f(x))$.

######  Lemma 22.

In the assumptions of the above theorem, assume that $\dim V=1$ and there
exists an immediate extension of valuation rings $V^{\prime}\subset V_{1}$
such that $V_{1}$ is a filtered direct limit of smooth $V$-algebras. Let
$\hat{V}$ be the completion of $V$ and $K$, $\hat{K}$ the fraction fields of
$V$, $\hat{V}$. Suppose that ${\hat{K}}/K$ is separable. Then for every
polynomial $f\in V[X]$ with $f(x)\not=0$ there exists a $y\in V$ such that
$\mathrm{val}(f(y))=\mathrm{val}(f(x))$,

###### Proof.

Let ${\hat{V}}_{1}$ be the completion of $V_{1}$ and $K_{1}$ the fraction
field of $V_{1}$. Then ${\hat{V}}_{1}\cap{\hat{K}}={\hat{V}}$. Note that
$K_{2}={\hat{K}}(V_{1})$ is a localization of ${\hat{K}}\otimes_{K}K_{1}$
since ${\hat{K}}/K$ is separable. Then $V_{2}={\hat{V}}_{1}\cap K_{2}$ is a
localization of ${\hat{V}}\otimes_{V}V_{1}$ and so $V_{2}$ is a filtered
direct limit of smooth $\hat{V}$-algebras. As $\hat{V}$ is Henselian we get
$\mathrm{val}(f(z))=\mathrm{val}(f(x))$ for some $z\in{\hat{V}}$ using the
above lemma. Choose $y\in V$ such that $\mathrm{val}(y-z)>\mathrm{val}(f(x))$.
Then $\mathrm{val}(f(y))=\mathrm{val}(f(x))$.

######  Theorem 23.

Let $V^{\prime}$ be an immediate algebraic extension of a valuation ring $V$,
$\hat{V}$ the completion of $V$ and $K$, ${\hat{K}}$ the fraction fields of
$V$, ${\hat{V}}$. Assume that $\operatorname{tr\,deg}_{K}{\hat{K}}\geq 1$,
${\hat{K}}/K$ is separable, there exists an immediate extension of valuation
rings $V^{\prime}\subset V_{1}$ such that $V_{1}$ is a filtered direct limit
of smooth $V$-algebras and either $V$ is Henselian, or $\dim V=1$. Then
$V\subset V^{\prime}$ is dense.

###### Proof.

Assume that $V\subset V^{\prime}$ is not dense and let $x\in V^{\prime}$ which
is not in $\hat{V}$. Then $x$ is a pseudo limit of a pseudo convergent
sequence $v$ which is not fundamental and has no pseudo limits in $V$ by [4,
Theorem 1]. Note that $v$ is algebraic because $x$ is algebraic over $K$.
Choose a transcendental $t\in{\hat{V}}$ over $K$. Multiplying $t$ with a
constant of $V$ of high enough value we may assume that $x+t$ is still a
pseudo limit of $v$.

Let ${\hat{V}}_{1}$ be the completion of $V_{1}$ and set
$V_{2}={\hat{V}}_{1}\cap{\hat{K}}(V_{1})$. As in the proof of the above lemma
we see that $V_{2}$ is a filtered direct limit of smooth $\hat{V}$-algebras.
Thus for every polynomial $f\in V[X]$ such that $f(x)\not=0$ there exists a
$y\in V$ such that $\mathrm{val}(f(y))=\mathrm{val}(f(x+z))$ using Lemmas 21,
22. By Theorem 19 applied to $x+z$ we get $v$ transcendental, which is false.

## References

  * [1] B. Antieau and R. Datta, Valuation rings are derived splinters, arxiv/AG:2002.010627v1.
  * [2] N. Bourbaki, Éléments de mathématique. Algèbre commutative, chap. I-VII, Hermann (1961, 1964, 1965); chap. VIII-X, Springer, (2006, 2007), (French).
  * [3] A. J. de Jong, Smoothness, semi-stability and alterations, Inst. Hautes Études Sci. Publ. Math., 83, 51–93, (1996).
  * [4] I. Kaplansky, Maximal fields with valuations, Duke Math. J., 9, 303-321, (1942).
  * [5] Z. Kosar, G. Pfister, D. Popescu, Constructive Néron Desingularization of algebras with big smooth locus, Communications in Algebra, 46, 1902-1911, (2018), arXiv/AC:1702.01867.
  * [6] F. V. Kuhlmann, Elimination of Ramification I: The Generalized Stability Theorem, Trans. AMS, 362, 5697-5727, (2010), arXiv/AC:1003.5678.
  * [7] F. V. Kuhlmann, The Defect, arXiv/AC:1004.2135v1.
  * [8] F. V. Kuhlmann, H. Ćmiel, Observations and conjectures on key polynomials, Preprint 2020.
  * [9] F. V. Kuhlmann, I. Vlahu, The relative approximation degree in valued function fields, Math. Z., 276, 203–235, (2014).
  * [10] A. Ostrowski, Untersuchungen zur arithmetischen Theorie der Körper, Math. Z., 39, 321-404, (1935).
  * [11] D. Popescu, On Zariski’s uniformization theorem, in Algebraic geometry, Bucharest 1982 (Bucharest, 1982), Lecture Notes in Math., 1056, Springer, Berlin, 264-296, (1984).
  * [12] D. Popescu, Algebraic extensions of valued fields, J. Algebra, 108, 513-533, (1987).
  * [13] D. Popescu, Simple General Neron Desingularization in local $\bf Q$-algebras, Communications in Algebra, 47, 923 - 929, (2019),arXiv:AC/1802.05109.
  * [14] D. Popescu, Néron desingularization of extensions of valuation rings with an Appendix by Kęstutis Česnavičius, in Proceedings of the conference ’Transient Transcendence in Transylvania’ (Trans’19: https://specfun.inria.fr/bostan/trans19/), Eds. Alin Bostan, Kilian Raschel, to appear in a special volume of the Springer collection PROMS (Proceedings in Mathematics and Statistics, https://www.springer.com/series/10533), arxiv/AC:1910.09123v4.
  * [15] O. F. G. Schilling, The theory of valuations, Mathematical Surveys, American Math. Soc., (1950).
  * [16] A. J. de Jong et al., The Stacks Project. Available at
http://stacks.math.columbia.edu.

  * [17] R. Swan, Neron-Popescu desingularization, in "Algebra and Geometry", Ed. M. Kang, International Press, Cambridge, 135-192, (1998).
  * [18] M. Temkin, Tame distillation and desingularization by p-alterations, Ann. of Math. , 186, 97–126, (2017).
  * [19] L. van den Dries, Lectures on the model theory of valued fields., in Model theory in algebra, analysis and arithmetic, Lect. Notes in Math., 2111, Springer, Heidelberg, 55–157, (2014).
  * [20] O. Zariski, Local uniformization on algebraic varieties, Ann. of Math., 41, 852-896, (1940).