# A Trajectory-Based Approach to Discrete-Time Flatness

Johannes Diwold  Bernd Kolar  Markus Schöberl  Institute of Automatic Control
and Control Systems Technology, Johannes Kepler University, Linz, Austria.
(e-mail<EMAIL_ADDRESS>
###### Abstract

For discrete-time systems, flatness is usually defined by replacing the time-
derivatives of the well-known continuous-time definition by forward-shifts.
With this definition, the class of flat systems corresponds exactly to the
class of systems which can be linearized by a discrete-time endogenous dynamic
feedback as it is proposed in the literature. Recently, checkable necessary
and sufficient differential-geometric conditions for this property have been
derived. In the present contribution, we make an attempt to take into account
also backward-shifts. This extended approach is motivated by the one-to-one
correspondence of solutions of flat systems to solutions of a trivial system
as it is known from the continuous-time case. If we transfer this idea to the
discrete-time case, this leads to an approach which also allows backward-
shifts. To distinguish the classical definition with forward-shifts and the
approach of the present paper, we refer to the former as forward-flatness. We
show that flat systems (in the extended sense with backward-shifts) still
share many beneficial properties of forward-flat systems. In particular, they
still are reachable/controllable, allow a straightforward planning of
trajectories and can be linearized by a dynamic feedback.

###### keywords:

Differential-geometric methods; discrete-time systems; nonlinear control
systems; feedback linearization; difference flatness

††thanks: The first author and the second author have been supported by the
Austrian Science Fund (FWF) under grant number P 32151 and P 29964.

##  1 Introduction

In the 1990s, the concept of flatness has been introduced by Fliess, Lévine,
Martin and Rouchon for nonlinear continuous-time systems (see e.g. Fliess et
al. (1992), Fliess et al. (1995) and Fliess et al. (1999)). Flat continuous-
time systems have the characteristic feature that all system variables can be
parameterized by a flat output and its time derivatives. This leads to a one-
to-one correspondence of solutions of a flat system to solutions of a trivial
system with the same number of inputs. Flat systems form an extension of the
class of static feedback linearizable systems and can be linearized by an
endogenous dynamic feedback. Their popularity stems from the fact that many
physical systems possess the property of flatness and that the knowledge of a
flat output allows an elegant solution to motion planning problems and a
systematic design of tracking controllers.

For nonlinear discrete-time systems, flatness is usually defined by replacing
the time-derivatives of the well-known continuous-time definition by forward-
shifts. More precisely, the flat output is a function of the state variables,
input variables, and forward-shifts of the input variables. Conversely, the
state- and input variables can be expressed as functions of the flat output
and its forward-shifts. This point of view has been adopted in Kaldmäe and
Kotta (2013), Sira-Ramirez and Agrawal (2004) and Kolar et al. (2016). With
this definition, the class of flat systems corresponds exactly to the class of
systems which can be linearized by a discrete-time endogenous dynamic feedback
as it is proposed e.g. in Aranda-Bricaire and Moog (2008). Recently, checkable
necessary and sufficient differential-geometric conditions have been derived
in Kolar et al. (2019b) and Kolar et al. (2019a). Furthermore, in Diwold et
al. (2020) it has been shown that in the two-input case even a transformation
into a certain normal form is always possible.

In this contribution, we focus solely on the one-to-one correspondence of
solutions of flat systems to solutions of a trivial system with the same
number of inputs, as it is known from the continuous-time case. For discrete-
time systems, this would mean that the flat output may depend both on forward-
and backward-shifts of the system variables. Conversely, the state- and input
variables could be expressed as functions of both forward- and backward-shifts
of the flat output. To distinguish the usual definition of Kaldmäe and Kotta
(2013), Sira-Ramirez and Agrawal (2004) and Kolar et al. (2016) with forward-
shifts from the alternative approach of the present paper, we refer to the
former as forward-flatness. A special case of this alternative definition has
already been suggested in Guillot and Millérioux (2020), where the flat output
may depend also on backward-shifts of the input variables but not on backward-
shifts of the state variables.111For systems where the Jacobian matrix of the
right-hand side of the system equations with respect to the state variables
has full rank, both approaches are equivalent. To justify our alternative
approach, we show that flat systems (in the extended sense with backward-
shifts) still share many beneficial properties of forward-flat systems. In
particular, we show that they still are reachable (and hence controllable) and
allow a straightforward planning of trajectories to connect arbitrary points
of the state space. Furthermore, we show that they can be linearized by a
dynamic feedback. With respect to the classical dynamic feedback linearization
problem, the following inclusions hold: (static feedback linearizable systems)
$\subset$ (forward-flat systems) $\subset$ (flat systems) $\subset$ (dynamic
feedback linearizable systems). We illustrate by examples that the class of
forward-flat systems is a strict subset of the class of flat systems in the
alternative sense with backward-shifts.

The paper is organized as follows: In Section 2 we introduce the extended
concept of flatness with both forward- and backward-shifts, and illustrate it
by examples. In Section 3 we first demonstrate the planning of trajectories
and prove the reachability of flat systems. Second, we show that every flat
system can be linearized by a certain dynamic feedback, and illustrate this
property again by an example.

##  2 Discrete-Time Flatness with Forward- and Backward-Shifts

Throughout this contribution, we consider discrete-time nonlinear systems in
state representation of the form

$x^{i,+}=f^{i}(x,u)\,,\quad i=1,\dots,n$ (1)

with $\dim(x)=n$, $\dim(u)=m$ and smooth functions $f^{i}(x,u)$. We assume
that the systems meet the submersivity condition

$\operatorname{rank}(\partial_{(x,u)}f)=n\,,$ (2)

which is necessary for reachability and consequently also for flatness.
Furthermore, we assume

$\operatorname{rank}(\partial_{u}f)=m\,,$

i.e. that the systems do not have redundant inputs. However, we want to
emphasize that we do not require $\operatorname{rank}(\partial_{x}f)=n$. As
mentioned in Aranda-Bricaire and Moog (2008), this property is always met by
systems which stem from the exact or approximate discretization of continuous-
time systems. However, we want to consider discrete-time systems in general,
no matter whether they stem from a discretization or not.

###  2.1 Equivalence of Solutions

To motivate our trajectory-based approach, we want to recall that a
continuous-time system $\dot{x}=f(x,u)$ is flat if there exists a one-to-one
correspondence between its solutions $(x(t),u(t))$ and solutions $y(t)$ of a
trivial system (sufficiently smooth but otherwise arbitrary trajectories) with
the same number of inputs (see e.g. Fliess et al. (1999)).

In the following, we attempt to define flatness for discrete-time systems in
exactly the same way. Within this paper, we call a discrete-time system (1)
flat if there exists a one-to-one correspondence between its solutions
$(x(k),u(k))$ and solutions $y(k)$ of a trivial system (arbitrary trajectories
that need not satisfy any difference equation) with the same number of inputs.

$\begin{array}[]{ccc}x^{+}=f(x,u)&&\begin{aligned} \text{trivial
system}\end{aligned}\\\ \downarrow&&\downarrow\\\
(x(k),u(k))&\overset{\text{one-to-
one}}{\Longleftrightarrow}&(y(k))\end{array}$

By one-to-one correspondence, we mean that the values of $x(k)$ and $u(k)$ at
some fixed time step $k$ may depend on an arbitrary but finite number of
future and past values of $y(k)$, i.e. on the whole trajectory in an
arbitrarily large but finite interval222Note that the time derivatives in the
continuous-time case provide via the Taylor-expansion also information about
the trajectory both in forward- and backward-direction.. Conversely, the value
of $y(k)$ at some fixed time step $k$ may depend on an arbitrary but finite
number of future and past values of $x(k)$ and $u(k)$. Thus, the one-to-one
correspondence of the solutions can be expressed by maps of the form

$(x(k),u(k))=F(k,y(k-r_{1}),\ldots,y(k),\ldots,y(k+r_{2}))$ (3)

and

$\displaystyle y(k)=\varphi(k,x(k-q_{1}),u(k-q_{1}),\ldots,$ (4)
$\displaystyle x(k),u(k),\ldots,x(k+q_{2}),u(k+q_{2}))\,.$

These maps must satisfy two conditions. First, in order to ensure the one-to-
one correspondence, after substituting (4) into (3) or vice versa the
resulting equations must be satisfied identically. Second, since the
trajectory $y(k)$ of the trivial system is arbitrary, after substituting (3)
into the system equations (1) they also must be satisfied identically. Because
of the time-invariance of the system (1), within this paper we only consider
maps

$(x(k),u(k))=F(y(k-r_{1}),\ldots,y(k),\ldots,y(k+r_{2}))$ (5)

and

$\displaystyle y(k)=\varphi(x(k-q_{1}),u(k-q_{1}),\ldots,x(k),u(k),\ldots,$
(6) $\displaystyle x(k+q_{2}),u(k+q_{2}))\,.$

which do not depend explicitly on the time step $k$.

###### Remark 1

The number of forward- and backward-shifts in (5) and (6) can of course be
different for the individual components of $y$, $x$ and $u$. Thus, where it is
necessary we will use appropriate multi-indices.

It is also important to note that the trajectories $x(k)$ and $u(k)$ are of
course not independent. Since (1) must hold at every time step $k$, it is
obvious that all forward-shifts $x(k+j)$ with $j\geq 1$ of the state variables
are determined by $x(k)$ and the forward-shifts $u(k+j-1)$, $j\geq 1$ of the
input variables, i.e.

$\displaystyle\begin{aligned} x(k+1)&=f(x(k),u(k))\\\
x(k+2)&=f(f(x(k),u(k)),u(k+1))\,.\\\ &\hphantom{a}\vdots\end{aligned}$ (7)

Thus, the forward-shifts of the state variables in (6) are redundant. A
similar argument holds for the backward-direction. Since (1) meets the
submersivity condition (2), there always exist $m$ functions $g(x,u)$ such
that the map

$\displaystyle\begin{aligned} x^{+}&=f(x,u)\\\ \zeta&=g(x,u)\end{aligned}$ (8)

is locally a diffeomorphism and hence invertible333It should be noted that the
choice of $g(x,u)$ is not unique.. If we denote by $(x,u)=\psi(x^{+},\zeta)$
its inverse

$\displaystyle\begin{aligned} x&=\psi_{x}(x^{+},\zeta)\\\
u&=\psi_{u}(x^{+},\zeta)\,,\end{aligned}$ (9)

then all backward-shifts $x(k-j)$ and $u(k-j)$ of the state- and input
variables with $j\geq 1$ are uniquely determined by $x(k)$ and the backward-
shifts $\zeta(k-j)$, $j\geq 1$ of the system variables $\zeta$ defined by (8).
This can be seen immediately by a repeated evaluation of (9), which yields

$\displaystyle\begin{aligned} (x(k-1),u(k-1))&=\psi(x(k),\zeta(k-1))\\\
(x(k-2),u(k-2))&=\psi(\psi(x(k),\zeta(k-1)),\zeta(k-2))\,.\\\
&\hphantom{a}\vdots\end{aligned}$ (10)

Consequently, with (7) and (10) the map (6) can be written as

$y(k)=\varphi(\zeta(k-q_{1}),\dots,\zeta(k-1),x(k),u(k),\dots,u(k+q_{2}))\,.$
(11)

We conclude that in the trajectory-based approach the flat output (11) is not
only a function of $x$, $u$ and forward-shifts of $u$, but also a function of
backward-shifts of $\zeta$. Thus, it extends the usual definition.

###### Remark 2

It is important to emphasize that the flatness of the system (1) does not
depend on the choice of the functions $g(x,u)$. Only the representation (11)
of the flat output may differ, while the parameterization (5) of $x$ and $u$
is not affected. If we would restrict ourselves to sampled data systems with
$\operatorname{rank}(\partial_{x}f)=n$, we could always choose $g(x,u)=u$.
This approach leads to a definition of flatness as proposed in Guillot and
Millérioux (2020), where the flat output is a function of $x$, $u$, and
forward- and backward-shifts of $u$.

Before we give a precise geometric definition of flatness, we also want to
mention that considering both forward- and backward-shifts in the
parameterizing map (5) is actually not necessary. Indeed, if there exists a
parameterizing map (5) and a flat output (11), then one can always define a
new flat output as the $r_{1}$-th backward-shift of the original flat
output.444Note that the number of required backward-shifts may differ for the
individual $m$ components of $y$, see Remark 1. The corresponding
parameterizing map is then of form

$(x(k),u(k))=F(y(k),\dots,y(k+r))$ (12)

with $r=r_{1}+r_{2}$.555Similarly, we may define a new flat output as the
$q_{1}$-th forward-shift of the original flat output. The resulting flat
output is then of the form $y(k)=\varphi(x(k),u(k),\dots,u(k+q))$, with
$q=q_{1}+q_{2}$, and the corresponding parameterizing map of the form (5).
Thus, without loss of generality, in the remainder of the paper we assume that
the parameterizing map (5) is of the form (12) and contains only forward-
shifts.

###  2.2 Geometric Approach

In order to give a concise definition of flatness including backward-shifts,
we use a space with coordinates $(\dots\zeta_{[-1]},x,u,u_{[1]}\dots)$, where
the subscript denotes the corresponding shift. Because of (7) and (10), every
point of this space corresponds to a unique trajectory $(x(k),u(k))$ of the
system (1). In accordance with (8), we have a forward-shift operator $\delta$
defined by the rule

$\displaystyle\begin{aligned}
\delta(h(\dots,\zeta_{[-2]},\zeta_{[-1]},x,u,u_{[1]},\dots))=\hphantom{aaaaaaaaaa}\\\
h(\dots,\zeta_{[-1]},g(x,u),f(x,u),u_{[1]},u_{[2]},\dots)\end{aligned}$

for an arbitrary function $h$. Because of (9), its inverse is given by the
backward-shift operator

$\displaystyle\delta^{-1}(h(\dots,\zeta_{[-1]},x,u,u_{[1]},u_{[2]},\dots))=$
$\displaystyle
h(\dots,\zeta_{[-2]},\psi_{x}(x,\zeta_{[-1]}),\psi_{u}(x,\zeta_{[-1]}),u,u_{[1]},\dots)\,.$

Likewise, every point of a space with coordinates
$(\ldots,y_{[-1]},y,y_{[1]},\dots)$ corresponds to a unique trajectory $y(k)$
of a trivial system. Here the shift operators have the simple form

$\delta_{y}(H(\ldots,y_{[-1]},y,y_{[1]},\dots))=H(\ldots,y,y_{[1]},y_{[2]},\dots)$

and

$\delta_{y}^{-1}(H(\ldots,y_{[-1]},y,y_{[1]},\dots))=H(\ldots,y_{[-2]},y_{[-1]},y,\dots)\,.$

A $\beta$-fold application of $\delta$ and $\delta_{y}$ or their inverses will
be denoted by $\delta^{\beta}$ and $\delta_{y}^{\beta}$, respectively.

With these preliminaries, we can give a geometric characterization for the
trajectory-based approach to discrete-time flatness suggested in Section 2.1.
In accordance with the literature on static and dynamic feedback linearization
for discrete-time systems, we consider a suitable neighborhood of an
equilibrium $x_{0}=f(x_{0},u_{0})$, see e.g. Nijmeijer and van der Schaft
(1990) or Aranda-Bricaire and Moog (2008). However, we want to emphasize that
for many systems the concept may be useful even if the conditions fail to hold
at an equilibrium.

###### Definition 3

The system (1) is said to be flat around an equilibrium $(x_{0},u_{0})$, if
the $n+m$ coordinate functions $x$ and $u$ can be expressed locally by an
$m$-tuple of functions

$y^{j}=\varphi^{j}(\zeta_{[-q_{1}]},\dots,\zeta_{[-1]},x,u,\dots,u_{[q_{2}]})\,,$
(13)

$j=1,\ldots,m$ and their forward-shifts

$\displaystyle\begin{aligned}
y_{[1]}&=\delta(\varphi(\zeta_{[-q_{1}]},\dots,\zeta_{[-1]},x,u,\dots,u_{[q_{2}]}))\\\
y_{[2]}&=\delta^{2}(\varphi(\zeta_{[-q_{1}]},\dots,\zeta_{[-1]},x,u,\dots,u_{[q_{2}]}))\\\
&\hphantom{a}\vdots\end{aligned}$ (14)

up to some finite order. The $m$-tuple (13) is called a flat output.

If (13) is a flat output, then it can be shown that all forward- and backward-
shifts of $\varphi$ are functionally independent. The functional independence
of $\dots,\delta^{-1}(\varphi),\varphi,\delta(\varphi),\dots$ in turn
guarantees that the representation of $x$ and $u$ by the flat output is unique
and a submersion of the form

$\displaystyle\begin{aligned} x^{i}&=F_{x}^{i}(y,\dots,y_{[R-1]})\,,\quad
i=1,\dots,n\\\ u^{j}&=F_{u}^{j}(y,\dots,y_{[R]})\,,\hphantom{ia}\quad
j=1,\dots,m\,.\end{aligned}$ (15)

A detailed proof using the differential-geometric concepts of exterior
derivatives and codistributions can be found in the appendix. The multi-index
$R=(r_{1},\dots,r_{m})$ contains the number of forward-shifts of each
component of the flat output which is needed to express $x$ and $u$. The
abbreviation $y_{[R]}$ denotes the components
$y_{[R]}=(y_{[r_{1}]}^{1},\dots,y_{[r_{m}]}^{m})$, and the integer $r$
indicates the maximum number of forward-shifts that appear in the
parameterization (15), i.e. $r=\max(r_{1},\dots,r_{m})$. If we restrict
ourselves to forward-shifts in the flat output, then Definition 3 leads to the
special case of forward-flatness.

###### Definition 4

The system (1) is said to be forward-flat, if it meets the conditions of
Definition 3 with a flat output of the form
$y^{j}=\varphi^{j}(x,u,\dots,u_{[q_{2}]})$.

The class of forward-flat systems has already been analyzed in detail in the
literature, see e.g. Kaldmäe and Kotta (2013), Sira-Ramirez and Agrawal (2004)
and Kolar et al. (2016). In Kolar et al. (2019b), it has been shown that every
forward-flat system can be decomposed into a smaller dimensional forward-flat
subsystem and an endogenous dynamic feedback by a suitable state- and input-
transformation. Thus, a repeated decomposition allows to check whether a
system is forward-flat or not. In Kolar et al. (2019a), this test has been
formulated in terms of certain sequences of distributions, similar to the test
for static-feedback linearizability in Nijmeijer and van der Schaft (1990).
Thus, the property of forward-flatness can be checked in a computationally
efficient way. For flat systems that are not forward-flat, the decomposition
procedure as stated in Kolar et al. (2019b) necessarily fails in one step,
likewise the test as proposed in Kolar et al. (2019a).

We conclude this section with the special cases of single-input systems and
linear systems.

###### Theorem 5

For single-input systems (1) with $m=1$, the properties flatness, forward-
flatness, and static feedback linearizability are equivalent.

###### Proof 2.1

The implication static feedback linearizability $\Rightarrow$ forward-flatness
$\Rightarrow$ flatness follows directly from the corresponding definitions.
For the other direction, consider a general flat output

$y=\varphi(\zeta_{[-q_{1}]}^{1},\dots,\zeta_{[-1]}^{1},x,u^{1},\dots,u_{[q_{2}]}^{1})$
(16)

of a system with $m=1$ input. Since the forward-shifts of (16) are independent
of $\zeta_{[-q_{1}]}^{1}$, (16) would be the only function in the
parameterization (15) depending on this variable. Thus, $\zeta_{[-q_{1}]}^{1}$
could not cancel out and accordingly (16) itself must not be present in the
parameterization (15). Repeating this argumentation shows that (15) can only
contain forward-shifts of (16) which are already independent of
$\zeta_{[-q_{1}]}^{1},\dots,\zeta_{[-1]}^{1}$. However, the first such
forward-shift of (16) is obviously a forward-flat output

$y=\varphi(x,u^{1},\dots,u_{[q_{2}]}^{1})\,.$ (17)

A similar argumentation shows that (17) can actually only depend on $x$, and
$u^{1}$ only appears in the $n$-th forward-shift. Otherwise, the forward-
shifts of u could not cancel out and a parameterization (15) would not be
possible. Thus, (17) is a linearizing output in the sense of static feedback
linearizability.

For linear systems the properties are also equivalent, since flatness implies
reachability and every reachable linear system can be transformed into
Brunovsky normal form.

###  2.3 Examples

In this section we present two examples that meet the conditions of Definition
3. The first example stems from an exact discretization of a continuous-time
$(x,u)$-flat system, and is flat but not forward-flat. In fact, it allows not
a single decomposition as proposed in Kolar et al. (2019b), and thus does not
meet the corresponding necessary condition for forward-flatness. Accordingly,
the test for forward-flatness stated in Kolar et al. (2019a) fails in the
first step. Hence, the example proves that the class of forward-flat systems
is a strict subset of the class of flat systems.

###### Example 2.2

Consider the sampled data system

$\displaystyle\begin{aligned} x^{1,+}&=x^{1}+Tu^{1}\\\
x^{2,+}&=x^{2}+Tu^{2}\\\ x^{3,+}&=x^{3}+Tu^{1}u^{2}\end{aligned}$ (18)

for some sampling time $T>0$. Since the system meets
$\operatorname{rank}(\partial_{x}f)=n$, we can choose
$\zeta^{j}=g^{j}(x,u)=u^{j}$ for $j=1,2$ such that the combined map (8) forms
a diffeomorphism. We claim that the system has a flat output of the form

$y=(x^{1}-T\zeta_{[-1]}^{1},x^{3}-x^{2}\zeta_{[-1]}^{1})\,.$ (19)

In order to prove that the system is flat, we need to show that $x$ and $u$
can be expressed by (19) and its forward-shifts. A sequential application of
the shift operators to (19) yields the set of equations

$\displaystyle\begin{aligned} y^{1}&=x^{1}-T\zeta_{[-1]}^{1}\\\
y_{[1]}^{1}&=x^{1}\\\ y_{[2]}^{1}&=x^{1}+Tu^{1}\\\
y_{[3]}^{1}&=x^{1}+T(u^{1}+u_{[1]}^{1})\end{aligned}$
$\displaystyle\begin{aligned} y^{2}=&x^{3}-x^{2}\zeta_{[-1]}^{1}\\\
y_{[1]}^{2}=&x^{3}-u^{1}x^{2}\\\
\hphantom{aa}y_{[2]}^{2}=&x^{3}+Tu^{1}u^{2}-\\\
&\hphantom{aaa}u_{[1]}^{1}(x^{2}+Tu^{2})\,,\end{aligned}$

which can be solved for $\zeta_{[-1]}^{1},x^{1},x^{2},x^{3},u^{1},u^{2}$ and
$u_{[1]}^{1}$,

$\displaystyle\begin{aligned}
\zeta_{[-1]}^{1}&=\tfrac{y_{[1]}^{1}-y^{1}}{T}\\\ x^{1}&=y_{[1]}^{1}\\\
x^{2}&=\tfrac{T(y^{2}-y_{[1]}^{2})}{y^{1}-2y_{[1]}^{1}+y_{[2]}^{1}}\\\
x^{3}&=\tfrac{y^{1}y_{[1]}^{2}-y_{[1]}^{1}y^{2}-y_{[1]}^{1}y_{[1]}^{2}+y_{[2]}^{1}y^{2}}{y^{1}-2y_{[1]}^{1}+y_{[2]}^{1}}\end{aligned}$
$\displaystyle\begin{aligned} u^{1}=&\tfrac{y_{[2]}^{1}-y_{[1]}^{1}}{T}\\\
u^{2}=&F_{u}^{2}(y,y_{[1]},y_{[2]},y_{[3]})\\\
u_{[1]}^{1}=&\tfrac{y_{[3]}^{1}-y_{[2]}^{1}}{T}\vphantom{\tfrac{T(y^{2}-y_{[1]}^{2})}{y^{1}-2y_{[1]}^{1}+y_{[2]}^{1}}}\,.\\\
&\vphantom{\tfrac{y^{1}y_{[1]}^{2}-y_{[1]}^{1}y^{2}-y_{[1]}^{1}y_{[1]}^{2}+y_{[2]}^{1}}{y^{1}-2y_{[1]}^{1}+y_{[2]}^{1}}}\end{aligned}$
(20)

The function $F_{u}^{2}(y,y_{[1]},y_{[2]},y_{[3]})$ is too lengthy to present
it here explicitly. We conclude that the system (18) is flat with a flat
output (19) and the corresponding parameterization (15) contained in (20).

In our next example, we again consider a system that is flat but not forward-
flat. In contrast to the system of Example 2.2, it does not stem from any
discretization and does not meet $\operatorname{rank}(\partial_{x}f)=n$.
Hence, the choice $g(x,u)=u$ as stated in Remark 2 is not possible, since (8)
would not result in a diffeomorphism.

###### Example 2.3

Consider the system

$\displaystyle\begin{aligned} x^{1,+}&=u^{1}\\\ x^{2,+}&=u^{2}\\\
x^{3,+}&=x^{3}+x^{1}u^{2}+x^{2}u^{1}\,.\end{aligned}$ (21)

With the choice $\zeta^{j}=g^{j}(x,u)=x^{j}$ for $j=1,2$, the combined map (8)
forms a diffeomorphism and we claim that the system has a flat output of the
form

$y=(\zeta_{[-1]}^{1},x^{3}-x^{2}\zeta_{[-1]}^{1})\,.$ (22)

In order to prove that the system is flat, we need to show that $x$ and $u$
can be expressed by (22) and its forward-shifts. A repeated application of the
shift operators to (22) yields the set of equations

$\displaystyle\begin{aligned} y^{1}&=\zeta_{[-1]}^{1}\\\ y_{[1]}^{1}&=x^{1}\\\
y_{[2]}^{1}&=u^{1}\\\ y_{[3]}^{1}&=u_{[1]}^{1}\end{aligned}$
$\displaystyle\begin{aligned}
\hphantom{aaa}y^{2}=&x^{3}-x^{2}\zeta_{[-1]}^{1}\\\
y_{[1]}^{2}=&x^{3}+x^{2}u^{1}\\\
y_{[2]}^{2}=&x^{3}+x^{2}u^{1}+u^{2}(x^{1}+u_{[1]}^{1})\,,\\\ \\\
\end{aligned}$

which can be solved for $\zeta_{[-1]}^{1},x^{1},x^{2},x^{3},u^{1},u^{2}$ and
$u_{[1]}^{1}$,

$\displaystyle\begin{aligned} \zeta_{[-1]}^{1}&=y^{1}\\\
x^{1}&=y_{[1]}^{1}\vphantom{\tfrac{y_{[2]}^{2}-y_{[1]}^{2}}{y_{[3]}^{1}+y_{[1]}^{1}}}\\\
x^{2}&=\tfrac{y_{[1]}^{2}-y^{2}}{y_{[2]}^{1}+y^{1}}\\\
x^{3}&=\tfrac{y^{1}y_{[1]}^{2}+y_{[2]}^{1}y^{2}}{y^{1}+y_{[2]}^{1}}\end{aligned}$
$\displaystyle\hphantom{aa}\begin{aligned} u^{1}=&y_{[2]}^{1}\\\
u^{2}=&\tfrac{y_{[2]}^{2}-y_{[1]}^{2}}{y_{[3]}^{1}+y_{[1]}^{1}}\\\
u_{[1]}^{1}=&y_{[3]}^{1}\vphantom{\tfrac{y_{[1]}^{2}-y^{2}}{y_{[2]}^{1}+y^{1}}}\,.\\\
&\vphantom{\tfrac{y^{1}y_{[1]}^{2}+y_{[2]}^{1}y^{2}}{y_{[1]}^{1}+y_{[2]}^{1}}}\end{aligned}$
(23)

Again we conclude that the system (21) is flat with a flat output (22) and the
corresponding parameterization (15) contained in (23).

##  3 Trajectory Planning and Dynamic Feedback Linearization

In this section, we show that flat systems (in the extended sense with
backward-shifts) still allow straightforward trajectory planning and dynamic
feedback linearization.

###  3.1 Trajectory Planning

The popularity of differentially flat systems is mainly due to the fact that
the knowledge of a flat output allows an elegant solution to motion planning
problems. In this section, we show that also discrete-time flat systems
according to Definition 3 allow a straightforward planning of trajectories.

Usually the motion planning problem consists in finding trajectories
$(x(k),u(k))$ that satisfy the system equations (1) and some initial and final
conditions

$\displaystyle\begin{aligned} (x(k_{i}),u(k_{i}))&=(x_{i},u_{i})\\\
(x(k_{f}),u(k_{f}))&=(x_{f},u_{f})\,,\end{aligned}$

with $k_{f}>k_{i}$. For flat systems, this task can be formulated in terms of
trajectories $y(k)$ for the flat output. Since every trajectory $y(k)$
corresponds to a solution of (1), it remains to require that the trajectory
$y(k)$ meets

$\displaystyle\begin{aligned}
(x_{i},u_{i})&=F(y(k_{i}),y(k_{i}+1),\dots,y(k_{i}+r))\\\
(x_{f},u_{f})&=F(y(k_{f}),y(k_{f}+1),\dots,y(k_{f}+r))\,.\end{aligned}$ (24)

If we assume that $k_{f}>k_{i}+r$ holds, then since the parameterization (15)
is a submersion, the set of equations (24) can be solved independently for
$2(n+m)$ values of $y(k_{i}),\dots,y(k_{f}+r)$.666For certain
parameterizations the assumption $k_{f}>k_{i}+r$ may be relaxed. It would be
sufficient to require that the integer $k_{f}$ is large enough, such that (24)
can still be solved for arbitrary $2(n+m)$ values of the set
$y(k_{i}),\dots,y(k_{f}+r)$. The remaining values of
$y(k_{i}),\dots,y(k_{f}+r)$ can be chosen arbitrarily, and thus the
trajectories $y(k)$ are in general not unique.777Like in the continuous-time
case, this property can be very beneficial in optimal control problems, e.g.
minimizing control effort. Once the trajectories $y(k)$ are determined, the
corresponding state- and input-trajectories are also uniquely determined by

$\displaystyle(x(k),u(k))=F(y(k),y(k+1),\dots,y(k+r))\,,$

for $k=k_{i},\dots,k_{f}$. Since this procedure allows to connect any two
points of the state space, we conclude that flatness according to Definition 3
implies the reachability of (1).

###  3.2 Dynamic Feedback Linearization

In the continuous-time framework, flatness is closely related to the dynamic
feedback linearization problem. To be precise, the class of differentially
flat systems is equivalent to the class of systems linearizable via endogenous
dynamic feedback. A continuous-time dynamic feedback $\dot{z}=\alpha(x,z,v)$
with $u=\beta(x,z,v)$ is said to be endogenous, if there exists a one-to-one
correspondence between trajectories of the closed-loop system and trajectories
of the original system. As a consequence, $z$ and $v$ can be expressed as
functions of $x$, $u$ and time derivatives of $u$.

According to Aranda-Bricaire and Moog (2008), a discrete-time dynamic feedback
is said to be endogenous, if its states $z$ and inputs $v$ can be expressed as
functions of $x$, $u$ and forward-shifts of $u$. It can be shown that the
class of discrete-time systems that is linearizable via endogenous dynamic
feedback in the sense of Aranda-Bricaire and Moog (2008) exactly corresponds
to the class of forward-flat systems. In this section, we show that also for
flat systems according to Definition 3 there always exists a linearizing
discrete-time dynamic feedback

$\displaystyle\begin{aligned} z^{+}&=\alpha(x,z,v)\\\
u&=\beta(x,z,v)\,.\end{aligned}$ (25)

However, in general the required feedback (25) is not contained within the
class of endogenous dynamic feedbacks proposed in Aranda-Bricaire and Moog
(2008). In the following, we first illustrate how such a dynamic feedback can
be constructed, and show that the resulting closed loop system is
transformable into Brunovsky normal form afterwards.

The fact that the parameterizing map (15) is a submersion implies that also
the parameterization $F_{x}$ is a submersion. Consequently, there exists a map
$z=F_{z}(y,\dots,y_{[R-1]})$, such that the combined map
$(x,z)=(F_{x},F_{z}):=F_{xz}$ forms a diffeomorphism, with $\dim(z)=p\leq
mr-n$. The choice of $F_{z}$ is not unique, and thus also the resulting
feedback will not be unique in general. In the next step, we define the map
$\Phi(y,\dots y_{[R]})$ given by

$\displaystyle\begin{array}[]{cc}\Phi:&\begin{aligned}
x=&F_{x}(y,\dots,y_{[R-1]})\\\ z=&F_{z}(y,\dots,y_{[R-1]})\\\
v=&y_{[R]}\end{aligned}\end{array}$ (27)

and its inverse $\hat{\Phi}(x,z,v)$ given by

$\displaystyle\begin{array}[]{cc}\hat{\Phi}:&\begin{aligned}
(y,\dots,y_{[R-1]})=&\hat{F}_{xz}(x,z)\\\
y_{[R]}=&v\,.\end{aligned}\end{array}$ (29)

Based on (29), we claim that every flat system can be linearized by a dynamic
feedback of the form

$\displaystyle\begin{aligned}
z^{+}&=\delta_{y}(F_{z})\circ\hat{\Phi}(x,z,v)\\\
u&=F_{u}\circ\hat{\Phi}(x,z,v)\,.\end{aligned}$ (30)

In order to prove this statement, we need to show that the closed loop
dynamics

$\displaystyle\begin{aligned} x^{+}&=f(x,F_{u}\circ\hat{\Phi}(x,z,v))\\\
z^{+}&=\delta_{y}(F_{z})\circ\hat{\Phi}(x,z,v)\end{aligned}$ (31)

is transformable into Brunovsky normal form by a suitable state- and input-
transformation. For this purpose, we use the state-transformation
$(x,z)=F_{xz}(y,\dots,y_{[R-1]})$ and the input-transformation $v=y_{[R]}$.
Applying the transformations yields

$(y^{+},\dots,y_{[R-1]}^{+})=\hat{F}_{xz}\circ\left[\begin{array}[]{c}f(x,F_{u}\circ\hat{\Phi}(x,z,v))\\\
\delta_{y}(F_{z})\circ\hat{\Phi}(x,z,v)\end{array}\right]\circ\Phi\,,$

which can be rewritten as

$\displaystyle\begin{aligned}
(y^{+},\dots,y_{[R-1]}^{+})&=\hat{F}_{xz}\circ\left[\begin{array}[]{c}f(F_{x},F_{u})\\\
\delta_{y}(F_{z})\end{array}\right]\,.\end{aligned}$ (32)

The parameterization (15) satisfies the system equations identically, hence by
substituting $F$ into $\delta(x)=f(x,u)$ we get the relation
$\delta_{y}(F_{x})=f(F_{x},F_{u})$. Thus, we may rewrite (32) as

$(y^{+},\dots,y_{[R-1]}^{+})=\hat{F}_{xz}\circ\left[\begin{array}[]{c}\delta_{y}(F_{x})\\\
\delta_{y}(F_{z})\end{array}\right]\,.$

Since
$\hat{F}_{xz}\circ(\delta_{y}(F_{x}),\delta_{y}(F_{z}))=\delta_{y}(\hat{F}_{xz}\circ(F_{x},F_{z}))$,
and per definition $\hat{F}_{xz}\circ(F_{x},F_{z})$ yields identically
$(y,\dots,y_{[R-1]})$, the Brunovsky normal form follows as

$(y^{+},\dots,y_{[R-1]}^{+})=\delta_{y}(y,\dots,y_{[R-1]})=(y_{[1]},\dots,y_{[R]})\,.$

Like a continuous-time endogenous dynamic feedback, the dynamic feedback (30)
has the property that the trajectories of the closed loop system are in one-
to-one correspondence to the trajectories $(x(k),u(k))$ of the original system
(1). This follows from the fact that with (27), $z$ and $v$ can be expressed
in terms of the flat output and its forward-shifts $(y,\dots,y_{[R]})$, which
in turn can be expressed by forward- and backward-shifts
$(\dots,\zeta_{[-1]},x,u_{[1]},\dots)$ of variables of the original system. In
other words, there exists a one-to-one correspondence between the trajectories
of the closed-loop system and the trajectories of the trivial system. By the
definition of flatness, the same holds for the trivial system and the original
system. It should also be noted that the dynamic feedback (30) preserves
reachability and submersivity. This is of course obvious, since the closed-
loop system can be transformed into Brunovsky normal form.

###### Remark 6

In the classical dynamic feedback linearization problem, the one-to-one
correspondence between trajectories of the closed loop system and the original
system is not required. Thus, the linearizing output of the closed loop system
can possibly not be expressed in terms of forward- and backward-shifts of the
original system variables.

We conclude this section with an example that illustrates the construction of
a linearizing dynamic feedback for a flat system.

###### Example 3.1

Consider again the system of Example 2.2 with the parameterizing map (20). If
we choose the map $z=F_{z}$ as

$\displaystyle\begin{aligned} z^{1}&=y^{1}\\\
z^{2}&=y_{[2]}^{1}\,,\end{aligned}$

then by evaluating (30) we derive the dynamic feedback

$\displaystyle\begin{aligned} z^{1,+}&=x^{1}\\\ z^{2,+}&=v^{1}\\\
u^{1}&=\tfrac{z^{2}-x^{1}}{T}\\\
u^{2}&=\tfrac{(x^{3}-v^{2})T-x^{2}(v^{1}-z^{2})}{(x^{1}-2z^{2}+v^{1})T}\,.\end{aligned}$

By transforming the closed-loop system using the state-transformation
$(x,z)=(F_{x},F_{z})$ and the input-transformation $v=y_{[R]}$, we obtain the
Brunovsky normal form

$\begin{array}[]{cc}\begin{aligned} y^{1,+}&=y_{[1]}^{1}\\\
y_{[1]}^{1,+}&=y_{[2]}^{1}\\\
y_{[2]}^{1,+}&=y_{[3]}^{1}\end{aligned}&\begin{aligned}
y^{2,+}&=y_{[1]}^{2}\\\ y_{[1]}^{2,+}&=y_{[2]}^{2}\,.\\\ \\\
\end{aligned}\end{array}$

##  4 Conclusion

In this contribution, we have investigated the extension of the notion of
discrete-time flatness to both forward- and backward-shifts. We have shown
that adding backward-shifts fits very nicely with the concept of one-to-one
correspondence of solutions of the original system and a trivial system, as it
is well-known from the continuous-time case. Even with backward-shifts,
reachability and controllability still hold and trajectories can be planned in
a straightforward way. Furthermore, such systems still can be linearized by a
dynamic feedback. Thus, from an application point of view, the basic
properties of forward-flat systems are preserved. Since we expect that the
class of flat systems in the extended sense including backward-shifts is
significantly larger than the class of forward-flat systems, this opens many
new perspectives for practical applications.

Future research will deal with the systematic construction of flat outputs and
finding necessary and/or sufficient conditions as they already exist for
forward-flat systems. Another open question, which is motivated by the
continuous-time case, is whether the class of flat systems is only a subset of
or equivalent to the class of systems linearizable by dynamic feedback, see
Remark 6.

## References

  * Aranda-Bricaire and Moog (2008) Aranda-Bricaire, E. and Moog, C. (2008).  Linearization of discrete-time systems by exogenous dynamic feedback.  _Automatica_ , 44(7), 1707–1717.
  * Diwold et al. (2020) Diwold, J., Kolar, B., and Schöberl, M. (2020).  A normal form for two-input flat nonlinear discrete-time systems.  _arXiv 2004.09437, International Journal of Systems Science (accepted)_.
  * Fliess et al. (1992) Fliess, M., Lévine, J., Martin, P., and Rouchon, P. (1992).  Sur les systèmes non linéaires différentiellement plats.  _Comptes rendus de l’Académie des sciences. Série I, Mathématique_ , 315, 619–624.
  * Fliess et al. (1995) Fliess, M., Lévine, J., Martin, P., and Rouchon, P. (1995).  Flatness and defect of non-linear systems: introductory theory and examples.  _International Journal of Control_ , 61(6), 1327–1361.
  * Fliess et al. (1999) Fliess, M., Lévine, J., Martin, P., and Rouchon, P. (1999).  A Lie-Bäcklund approach to equivalence and flatness of nonlinear systems.  _IEEE Transactions on Automatic Control_ , 44(5), 922–937.
  * Guillot and Millérioux (2020) Guillot, P. and Millérioux, G. (2020).  Flatness and submersivity of discrete-time dynamical systems.  _IEEE Control Systems Letters_ , 4(2), 337–342.
  * Kaldmäe and Kotta (2013) Kaldmäe, A. and Kotta, Ü. (2013).  On flatness of discrete-time nonlinear systems.  In _Proceedings 9th IFAC Symposium on Nonlinear Control Systems_ , 588–593.
  * Kolar et al. (2019a) Kolar, B., Diwold, J., and Schöberl, M. (2019a).  Necessary and sufficient conditions for difference flatness.  _arXiv e-prints_.  ArXiv:1909.02868v2 [math.OC].
  * Kolar et al. (2016) Kolar, B., Kaldmäe, A., Schöberl, M., Kotta, Ü., and Schlacher, K. (2016).  Construction of flat outputs of nonlinear discrete-time systems in a geometric and an algebraic framework.  In _Proceedings 10th IFAC Symposium on Nonlinear Control Systems_ , 808–813.
  * Kolar et al. (2019b) Kolar, B., Schöberl, M., and Diwold, J. (2019b).  Differential-geometric decomposition of flat nonlinear discrete-time systems.  _arXiv e-prints_.  ArXiv:1907.00596 [math.OC].
  * Nijmeijer and van der Schaft (1990) Nijmeijer, H. and van der Schaft, A. (1990).  _Nonlinear Dynamical Control Systems_.  Springer, New York.
  * Sira-Ramirez and Agrawal (2004) Sira-Ramirez, H. and Agrawal, S. (2004).  _Differentially Flat Systems_.  Marcel Dekker, New York.

##  Appendix A Properties resulting from Definition 3

In this section, we prove that the functional independence of all forward- and
backward-shifts of a flat output
$\dots,\delta^{-1}(\varphi),\varphi,\delta(\varphi),\dots$, as well as the
property that (15) is a submersion, are direct consequences of Definition 3.
Furthermore, we show that the special structure that $F_{x}$ is independent of
$y_{[R]}$ follows from the fact that the parameterization (15) needs to
satisfy the system equations (1) identically.

By definition, the states $x$ and inputs $u$ can be expressed as functions of
$\varphi,\delta(\varphi)\dots,\delta^{r}(\varphi)$. Thus, there exist some
functions $F(y,\dots,y_{[r]})$ such that after substituting (14) the
identities

$\displaystyle\begin{aligned}
x&=F_{x}(\varphi,\delta(\varphi),\dots,\delta^{r}(\varphi))\\\
u&=F_{u}(\varphi,\delta(\varphi),\dots,\delta^{r}(\varphi))\end{aligned}$ (33)

hold. By taking the exterior derivative, relation (33) can be written as

$\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u\\}\subset\operatorname{span}\\{\mathrm{d}\varphi,\mathrm{d}\delta(\varphi),\dots,\mathrm{d}\delta^{r}(\varphi)\\}\,.$

A sequential application of the shift operator $\delta$ to
$u=F_{u}(\varphi,\delta(\varphi),\dots,\delta^{r}(\varphi))$ of (33), yields
the identities

$\displaystyle\begin{aligned}
u_{[\beta]}&=F_{u}(\delta^{\beta}(\varphi),\dots,\delta^{r+\beta}(\varphi))\,,\end{aligned}$
(34)

for arbitrary forward-shifts of $u$ with $\beta>0$. If we consider the
codistribution
$\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u,\dots,\mathrm{d}u_{[\beta]}\\}$
for an arbitrary integer $\beta$, then from (34) we get the relation

$\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u,\dots,\mathrm{d}u_{[\beta]}\\}\subset\operatorname{span}\\{\mathrm{d}\varphi,\mathrm{d}\delta(\varphi),\dots,\mathrm{d}\delta^{r+\beta}(\varphi)\\}\,.$
(35)

Since the forward-shifts $u_{[\beta]}$, with
$\dim(u_{[\beta]})=\dim(\varphi)=m$, are independent coordinates, the
dimension of
$\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u,\dots,\mathrm{d}u_{[\beta]}\\}$
grows by $m$ for each increment of $\beta$. Consequently, also the dimension
of
$\operatorname{span}\\{\mathrm{d}\varphi,\mathrm{d}\delta(\varphi),\dots,\mathrm{d}\delta^{r+\beta}(\varphi)\\}$
must grow by $m$ for each increment of $\beta$. If in some step the dimension
of
$\operatorname{span}\\{\mathrm{d}\varphi,\dots,\mathrm{d}\delta^{r+\beta}(\varphi)\\}$
would only grow by $\bar{m}<m$, then also in all following steps the dimension
could only grow at most by $\bar{m}$. However, this would necessarily result
in a contradiction to (35). Therefore, the condition

$\dim(\operatorname{span}\\{\mathrm{d}\varphi,\mathrm{d}\delta(\varphi),\dots,\mathrm{d}\delta^{\beta}(\varphi)\\})=(\beta+1)m$

must hold for arbitrary $\beta$ which means that the functions
$\varphi,\delta(\varphi)\dots,\delta^{\beta}(\varphi)$ are functionally
independent. A similar argument holds for the backward-shifts of $\varphi$.
With $F_{\zeta}:=g\circ F(y,\dots,y_{[R]})$ we have the identities

$\zeta=F_{\zeta}(\varphi,\dots,\delta^{r}(\varphi))\,.$

By a sequential application of the backward-shift operator $\delta^{-1}$, we
derive the identities

$\displaystyle\begin{aligned}
\zeta_{[-\alpha]}&=F_{\zeta}(\delta^{-\alpha}(\varphi),\dots,\delta^{r-\alpha}(\varphi))\,.\end{aligned}$
(36)

for arbitrary backward-shifts of $\zeta$ with $\alpha>0$. If we consider the
codistribution
$\operatorname{span}\\{\mathrm{d}\zeta_{[-\alpha]},\dots,\mathrm{d}\zeta_{[-1]},\mathrm{d}x,\mathrm{d}u\dots,\mathrm{d}u_{[\beta]}\\}$,
then we get the relation

$\displaystyle\begin{aligned}
\operatorname{span}\\{\mathrm{d}\zeta_{[-\alpha]},\dots,\mathrm{d}\zeta_{[-1]},\mathrm{d}x,\mathrm{d}u\dots,\mathrm{d}u_{[\beta]}\\}\subset\hphantom{aaaaa}\\\
\operatorname{span}\\{\mathrm{d}\delta^{-\alpha}(\varphi),\dots,\mathrm{d}\delta^{r+\beta}(\varphi)\\}\,.\end{aligned}$

Since the backward-shifts $\zeta_{[-\alpha]}$, with
$\dim(\zeta_{[-\alpha]})=\dim(\varphi)=m$, are independent coordinates, the
dimension of
$\operatorname{span}\\{\mathrm{d}\zeta_{[-\alpha]},\dots,\mathrm{d}\zeta_{[-1]},\mathrm{d}x,\mathrm{d}u\dots,\mathrm{d}u_{[\beta]}\\}$
grows by $m$ for each increment of $\alpha$. Consequently also the dimension
of
$\operatorname{span}\\{\mathrm{d}\delta^{-\alpha}(\varphi),\dots,\mathrm{d}\delta^{r+\beta}(\varphi)\\}$
must grow by each increment of $\alpha$. From

$\dim(\operatorname{span}\\{\mathrm{d}\delta^{-\alpha}(\varphi),\dots,\mathrm{d}\delta^{\beta}(\varphi)\\})=(\alpha+\beta+1)m\,,$

we conclude that the functions
$\delta^{-\alpha}(\varphi),\dots,\delta^{r+\beta}(\varphi)$ for arbitrary
$\alpha,\beta>0$, are functionally independent, which entails the uniqueness
of (15).

Next, we prove that the parameterizing map (15) is indeed a submersion. By
taking the exterior derivative of identity (15) we get the relation

$\displaystyle\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u\\}=$ (37)
$\displaystyle\operatorname{span}\\{(\partial_{y_{[k]}^{j}}F^{i}\circ(\varphi,\delta(\varphi),\dots))\mathrm{d}\delta^{k}(\varphi^{j}),i=1,\dots,n+m\\}\,.$

Since $\dim(\operatorname{span}\\{\mathrm{d}x,\mathrm{d}u\\})=n+m$, the
identity (37) can only be satisfied if the rows of the Jacobian-matrix
$\partial_{y_{[k]}^{j}}F^{i}$, $i=1,\dots,n+m$, are linearly independent.
Hence, the map (15) must be a submersion.

Finally, we show that the special structure that the parameterization of the
states is independent of $y_{[R]}$ is a consequence of the identity

$\delta(x^{i})=f^{i}(x,u),\quad i=1,\dots,n\,.$ (38)

If we substitute the parameterization into (38) we get

$\delta_{y}(F_{x}^{i}(y,\dots,y_{[R-1]}))=f^{i}\circ F(y,\dots,y_{[R]})\,,$

which can only be satisfied if $F_{x}$ is independent of $y_{[R]}$. Otherwise,
$\delta_{y}(F_{x})$ would depend on $(R+1)$-th forward-shifts of $y$.