\documentstyle[IEEEtran]{article}

\tolerance 10000
\begin{document}

\pagestyle{myheadings}

\markright{APIC'95, El Paso,
Extended Abstracts,
A Supplement to the international journal of {\rm Reliable
Computing}\ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ }

\title{In Case of Interval Uncertainty, 
Optimal Control is NP-Hard Even for Linear Plants, so Expert Knowledge
is Needed}

\author{Samuel Smith and Vladik Kreinovich}

\maketitle

\begin{abstract} 
If we know the plant precisely, then in the first approximation (for a
linear plant and quadratic objective function), the
problem of 
optimal control has an explicit solution. In this paper, we show that
if we take into consideration the fact that in real life, all
parameters of a plant are known with interval uncertainty, then even
in the first approximation, the
problem of optimal control becomes computationally intractable
(NP-hard). This result justifies the necessity to use expert knowledge
in control
(and corresponding intelligent control methodologies). 
\end{abstract}

\auffil{The authors are with the 
Department of Oceanic Engineering, Florida Atlantic University,
500 N.W. 20th Street,
Boca Raton, FL 33431,
email smith@transquest.oe.fau.edu
 (S. Smith), and 
with the Computer Science Department of 
the University of Texas at El Paso, El Paso, TX 79968, USA,
vladik@cs.utep.edu (V. Kreinovich). This work was supported in part by
NSF Grant No. CDA-9015006 and NASA Research Grant No. 9-757.
The authors are thankful to John Yen for valuable discussions.}


\section{Mathematical Optimal Control Theory: A Brief General
Formulation of a Problem}

Traditional control theory (see, e.g., \cite{M91}) 
deals with the case when our knowledge is
complete:
\begin{itemize}
\item We know
exactly the initial state $x(0)=x_0$ 
of the plant (i.e., of the object that we want
to control). The state of a plant is usually described by 
its characteristics $x_1,...,x_n$; so, from mathematical viewpoint, the
state is an $n-$dimensional vector $x=(x_1,...,x_n)$. 
\item We know exactly how the state of the plant changes if we apply
different controls $u$. In precise mathematical terms, we know the
differential equation $\dot x=f(x,u)$ that describes the plant.
\item We know what exactly we want to achieve by this control, i.e.,
we know a functional $J(x,u)$ (called {\it objective function}) 
that we want to minimize (or maximize) by
applying the optimal control. For example, if we are planning a flight
to the planet:
\begin{itemize}
\item[$\bullet$]we may want to minimize the time that is necessary to
reach that planet; this objective function depends only on the
trajectory $x(t)$);
\item[$\bullet$] or, we may want to minimize 
the total amount of fuel spent during this flight;
this objective function depends only on the control $u(t)$;
\item[$\bullet$]we may also want to minimize some combination of time and
fuel spent; in this case, we have an objective function that depends on
both $x$ and $u$.
\end{itemize}
\end{itemize}
In this case, the problem of finding the optimal control becomes a
well-defined mathematical problem:
$$J(x,u)\to\min_u$$ under the conditions that $x(0)=x_0$ and $\dot
x=f(x,u)$. 

\section{This Problem Has Been Solved in the First Approximation}

In many important cases, this optimization problem has been solved, and
we have explicit formulas for optimal control that are being
successfully used in many real-life applications. 
Of course, there are still many complicated problems, with complicated
evolution function $f$ and complicated objective function $J$, for which
an optimization technique still need to be found, but at
least in the {\it first approximation}, the problem is solved. 
In order to describe this result in mathematical terms, 
we must describe what a ``first approximation'' means in this case.

Usually, we consider the plants for which both the evolution function
$f$ and the objective function $J$ depend {\it smoothly} (i.e.,
differentially) on both $x$ and $u$. Of course, one can imagine realistic
situations in which the dependency is not smooth and even not continuous
at all: e.g., in sports-like competition situations, we either score or
we do not; we either hit the planet, or we do not. In such situations,
the payoff function $J(x,u)$ takes only two values: 0 and 1, and it
therefore, cannot be continuous. Such situations are, however, an
idealization. In real-life situations, e.g., in spaceship trajectory
control, it is not true that when we change the thrust continuously, we
at some point immediately switch from hitting the planet to not hitting
it: due to inevitable uncertainties, we can only talk about the {\it
probability} of a hit, and this probability smoothly changes with $x$
and $u$. A similar argument can be applied to other situations, so, we
can safely assume that both the evolution function and the objective
function are smooth.

In this case, the notion of a first approximation is very natural: by
definition, a smooth function is the one that can be (at least locally)
well approximated by a linear, quadratic, etc functions (depending on
how many derivatives we require). So, we can take the first significant 
term in
the Taylor expansion as the first approximation of the function.  
\begin{itemize}
\item For an evolution function $f(x,u)$, 
we cannot take the 0-th order (constant)
term, because then, the system will be not controllable at all. So, to get
a reasonable first approximation, we
must also retain {\it linear} terms in $f$. As a result, we get a first
approximation of the type $\dot x=a+Ax+Bu$ for some vector $a$ and
matrices $A$ and $B$. 
\item For the objective function, linear approximation is not enough,
because linear functions do not have any minima at all. So, we also need to
consider terms that are quadratic in $x(t)$ and $u(t)$. In other words,
we must consider objective functions of the type $$J(x,u)=J_0+\int
J_x(t)x(t)\,dt+\int J_u(t)u(t)\,dt+$$ $$\int J_{xx}(t)x(t)x(t)\,dt+
\int J_{xu}x(t)u(t)\,dt+$$ $$\int J_{uu}(t)u(t)u(t)\,dt$$ for some constant
$J_0$, vectors $J_x(t)$ and $J_u(t)$ and matrices $J_{xx}(t)$,
$J_{xu}(t)$, and $J_{uu}(t)$. The constant term
can be safely dropped, because if $J_0$ is
a constant, then $J\to\min$
iff $J-J_0\to\min. $
\end{itemize}
For linear systems, and quadratic objective functions, there exists an
explicit solution to the optimal control problem. 

It therefore seems (at first glance) 
that in the first approximation, the problem
of optimal control is solved. We will show that the optimal control
problem is more complicated than that. The reason is that in the above
formulations, we were assuming that we know the plant {\it precisely}, but:

\section{In Real Life, We Never Know Any Values Precisely}
In real-life situations, we never know the precise values of any
parameters that describe a physical object: we get all these values from
measurements (direct or indirect), and measurement are never absolutely
precise. In this paper, we are going to show that {\it if we take that
imprecision into consideration, then even for the above-described first
approximation, the optimal control problem stops being simple and becomes
computationally intractable (NP-hard).} We will show that this problem
is intractable even in the {\it static} case, when all the parameters
$J_{...}$ of an objective function do not
depend on time at all. 

Moreover, we will show that not only the problem of finding an {\it
optimal} control (with $J\to\min$) is difficult, but even a simpler
problem of finding a {\it good enough} control (i.e., a control for
which $J\le J_g$ for some $J_g$) is also intractable.

To describe this result in mathematical terms, we must describe two
things:
\begin{itemize}
\item First, we must describe uncertainty in mathematical terms.
\item Second, we must describe a reasonable modification of the
above-described optimization problem that would take this uncertainty
into consideration.
\end{itemize}

Let us first describe uncertainty. The manufacturer of the measuring
instrument must provide us with the error bounds. If no error bounds are
provided, then the results of measuring by this instrument are of no
use: if, e.g., we get a temperature 100, but we do not know whether the
accuracy is $\pm 1$ or $\pm 1000$, then we cannot conclude anything
about the actual temperature. In addition to this error bound, some
instruments may have probabilities of different errors known, but in all
cases, we must have this error bound. So, as a general case, we can
consider the case when this error bound is known. 
In this case, whatever physical quantity 
we are interested in, after measuring
it and getting the measurement result $\tilde x$, the only thing that we
can guarantee about the actual value $x$ of this quantity is that it
lies in the interval $[\tilde x-\Delta,\tilde x+\Delta]$, where $\Delta$
is the error bound provided by the manufacturer of the measuring
instrument. 
In other words, we can assume that for each parameter, we only know the
{\it interval} of its possible values. 
In other words, we have an {\it interval uncertainty}. 

If there is an interval uncertainty in the parameters of the
evolution function, then, even if the initial state $x(0)$, the control
$u(t)$, and the objective function $J$ are precisely known, 
we cannot predict exactly what a trajectory can be,
and we cannot therefore predict exactly what the value of the objective
function will be, and whether the resulting control will be
good enough or not. 

In this case, it make sense to look for a control that {\it can} be good
enough. For example, if we are planning an automatic mission to another
planet, then we are well aware of the uncertainties, and we understand
very well that there is always a potential for a failure, We want,
however, to choose a control in such a way that there is also a
potential for a success (and thus, to avoid the disastrous controls that
leave us with no chances of succeeding).
In other words, we want to find a control $u(t)$ for which at least one
possible trajectory satisfies the property $J\le J_g$. 

Now, we are ready
for the mathematical formulation:

\section{Mathematical Formulation of the Problem and the Main Result}

\noindent{\bf Definition 1.} By a {\it control situation with
interval uncertainty}, we mean the tuple $$(n, m, x_0, {\bf a}, 
{\bf A}, {\bf B},
J_x, J_u, J_{xx}, J_{xu}, J_{uu}, J_g, T),$$ where:
\begin{itemize}
\item $n$ and $m$ are positive integers;
\item $x_0$ is an $n-$dimensional vector;
\item $\bf a$ is an $n-$dimensional interval vector;
\item $\bf A$ is an $n\times n$ interval matrix;
\item $\bf B$ is an $n\times m$ interval matrix;
\item $J_x$ is an $n-$dimensional vector;
\item $J_u$ is an $m-$dimensional vector;
\item $J_{xx}$ is an $n\times n$ matrix;
\item $J_{xu}$ is an $n\times m$ matrix;
\item $J_{uu}$ is an $m\times m$ matrix;
\item $J_g$ is a real number;
\item $T$ is a positive real number (called {\it time}).
\end{itemize}

\noindent{\bf Definition 2.} Let a control situation with interval
uncertainty be given.
 \begin{itemize}
\item By a {\it control}, we mean a function $u:[0,T]\to R^m$. 
\item Let a control $u(t)$ be given. 
We say that $x(t)$ is a {\it possible
trajectory}, if $x$ is a solution of the differential equation $\dot x
=a+Ax+Bu$, $x(0)=x_0$  for some vector $a\in{\bf a}$ and 
matrices $A\in {\bf A}$ and $B\in{\bf B}$.
\item We say that $x$ is a {\it good trajectory} if it is a possible
trajectory, and $J(x,u)\le J_g$, where 
$J(x,u)=\int_0^T K\,dt$, and $$K=J_x x(t)+J_u u(t)+$$
$$J_{xx}x(t)x(t)+J_{xu}x(t)u(t)+J_{uu}u(t)u(t).$$
\item We say that $u(t)$ is a {\it good control} if for this control, 
there exists at
least one good trajectory.  
\end{itemize}

\noindent{\bf Definition 3.} By an {\it optimal control problem in case
of interval uncertainty}, we mean the following problem:

\noindent{\it Given:} a control situation with interval uncertainty.

\noindent{\it To compute:} a good control (or, if there is no good
control, to return the corresponding message). 
\smallskip

\noindent{\bf THEOREM.} {\it Optimal control problem in case of interval
uncertainty is intractable (NP-hard).}
\smallskip

\noindent{\it Comment.} This result is in good accordance with the
similar results on NP-hardness:
\begin{itemize}
\item the problem of finding a {\it robust stable} control is in
general NP-hard (for references, see \cite{Barmish 1994});

\item for general non-linear systems, the problem of optimal control
is NP-hard even if there is no interval uncertainty \cite{Abello}, etc.
\end{itemize}
\section{Proof}

By definition, a problem is NP-hard if any algorithm that can solve it
in polynomial time (i.e., in time that is bounded by some polynomial of
the input) can be transformed into an algorithm that solves {\it all}
problems (from a certain very general class NP) also in polynomial
time. 
To prove that our problem is NP-hard, we will reduce it to another
problem that is known to be NP-hard: namely, to the following problem 
\cite{Lakeyev 1993}:
\smallskip

\noindent{\it Given:} an interval linear system of equations 

\noindent ${\bf B}u={\bf b}$.

\noindent{\it To find:} the vector $u$ that is a {\it possible
solution}, i.e., for which $Bu=b$ for some $B\in {\bf B}$ and $b\in{\bf
b}$. 
\smallskip

We will show that if we would be able to solve the above-formulated
control problem (optimal control
problem in case of interval uncertainty) in polynomial time, then we
would be able to solve this interval algebraic problem in polynomial
time as well. Indeed, suppose that we do have a polynomial-time
algorithm $\cal U$ for solving the interval control problem, and that we are
given the interval matrix $\bf B$ of dimensions $n\times m$ 
and the interval vector $\bf b$.
Then, we can solve the problem of finding the appropriate $u$ as
follows:
\begin{itemize}
\item Formulate the following control problem: 
Take the same $n$, $m$, and $\bf B$ as in the algebraic problem, ${\bf
a}=-{\bf b}$, $x_0=0$, ${\bf A}=0$, $J_{xx}=1$, and
$J_x=J_u=J_{xu}=J_{uu}=J_g=0$. 
\item Apply the algorithm $\cal U$ to this problem.
\item The result $u(t)$ is the desired solution of the algebraic
interval problem.
\end{itemize}

Indeed, for this system, $J(x,u)=\int x^2(t)\,dt$, so, the only way to have
a good trajectory $x$, i.e., to have 
$J\le J_g=0$, is to have $x(t)=0$ for all $t$. By definition of a
possible trajectory, this means that $Bu+a=0$, i.e., that $Bu=b$
for some $B\in {\bf B}$ and $b\in {\bf b}$. This is exactly the
definition of a possible solution.
Q.E.D.

\section{Conclusion}

The fact that in a realistic setting (of interval uncertainty), the
problem of finding the optimal control is intractable even in the first
approximation, means that no general algorithm is possible that would
find the optimal control for all possible plants. 

Instead of this non-existence 
general algorithm, we must use the {\it experience} of
expert controllers. There already exists a methodology (called {\it
intelligent control}) that translates the experience of an expert
controller into the actual control strategy (see, e.g., \cite{KL:94,SC91}).
Our result shows that 
{\it expert knowledge and intelligent control methodology are needed for
optimal control}, even
for the simplest case when the plant is described by a linear equation,
and the objective function is quadratic.  

\begin{thebibliography}{99}

\bibitem{Abello}
J. Abello, V. Kreinovich, H. T. Nguyen, S. Sudarsky, and J. Yen,
``Computing an appropriate control strategy
based only on a given plant's rule-based model
is NP-hard'',
In: L. Hall, H. Ying, R. Langari, and J. Yen
(eds.), {\it NAFIPS/IFIS/NASA'94, Proceedings of the First
International Joint Conference of The 
North American Fuzzy Information Processing Society Biannual Conference, The
Industrial Fuzzy Control and Intelligent Systems Conference, and The NASA Joint
Technology Workshop on Neural Networks and Fuzzy Logic, San Antonio,
December 18--21, 1994}, IEEE, Piscataway, NJ, pp. 331--332.

\bibitem{Barmish 1994}
B. R. Barmish, {\bf New tools for robustness of linear systems},
McMillan, N.Y., 1994. 

\bibitem{Lakeyev 1993}
V. Kreinovich, A. V. Lakeyev, and S. I. Noskov. 
``Optimal solution of interval linear
systems is intractable (NP-hard).'' {\it Interval Computations,} 1993,
No. 1, pp. 6--14.

\bibitem{KL:94} A. Kandel and G. Langholtz
(Editors), {\bf Fuzzy Control Systems}, CRC Press, Boca Raton, FL, 1994.

\bibitem{M91} R. Mohler, {\bf Nonlinear systems. Vol. 1. Dynamics and
control}, Prentice Hall, Englewood Cliffs, NJ, 1991. 

\bibitem{SC91} S. M. Smith and D. J. Comer, ``Automated calibration of a
fuzzy logic controller using a cell state space algorithm'', {\it IEEE
Control Systems}, August 1991, pp. 18--28.

\end{thebibliography}

\end{document}