\documentclass{abstract}

\usepackage{times,amsthm,graphicx,epstopdf}

\usepackage[pdftex,colorlinks=true,linkcolor=blue,urlcolor=red]{hyperref}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{listings,color,pgf}
% define colors for source code list 
\definecolor{colKeys}{rgb}{0,0,1} 
\definecolor{colIdentifier}{rgb}{0,0,0} 
\definecolor{colComments}{rgb}{0,1,0.3} 
\definecolor{colString}{rgb}{0,0.5,0} 

\definecolor{dkgreen}{rgb}{0,0.6,0} 
\definecolor{gray}{rgb}{0.5,0.5,0.5} 
\definecolor{lightgray}{rgb}{0.9,0.9,0.9} 

\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\R}{\field{R}}
\newcommand{\N}{\field{N}}
\newcommand{\bu}{{\bf u}}
\newcommand{\ru}{\mathrm{u}}
\newcommand{\bx}{{\bf x}}
\newcommand{\bw}{{\bf w}}
\newcommand{\bp}{{\bf p}}
\newcommand{\bX}{{\bf X}}
\newcommand{\cU}{{\cal U}}
\newcommand{\cW}{{\cal W}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cF}{{\cal F}}
\newcommand{\cV}{{\cal V}}
\newcommand{\cQ}{{\cal Q}}
\newcommand{\cB}{{\cal B}}
\newcommand{\cX}{{\cal X}}
\newcommand{\cG}{{\cal G}}
\newcommand{\cN}{{\cal N}}
\newcommand{\cD}{{\cal D}}
\newcommand{\cS}{{\cal S}}
\newcommand{\eps}{{\varepsilon}}

\def\intr{\mathop{\rm int }\nolimits}
\def\KK{\mathcal{K}}
\def\LL{\mathcal{L}}
\def\Out{\mathop{\rm Out}\nolimits}
\def\In{\mathop{\rm In}\nolimits}
\def\endproof{\unskip \nobreak \hskip0pt plus 1fill \qquad \qed}
\newcommand{\grad}{\operatorname{grad}}
\newcommand{\argmin}{\operatorname{argmin}}
\newcommand{\operatorspan}{\operatorname{span}}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}

\begin{document}

\title{Dynamic programming\\ using radial basis functions}
\author{Oliver Junge}
\institute{Technische Universit\"at M\"unchen}
\email{oj@tum.de}
\coauthor{Alex Schreiber} % comment out if not needed

\mymaketitle

\section{Abstract}

We propose a discretization of the optimality principle in dynamic programming based on radial basis functions and Shepard's approximation method. 

Consider a discrete time control system $x_{k+1}=f(x_k,u_k)$ with a continuous map $f: \Omega \times U \to \R^n$ on compact sets $\Omega \subset \R^n$, $U \subset \R^d$, $0\in U$, as phase and control space, respectively.  In addition, we are given a continuous \emph{cost function} $c: \Omega \times U \to [0,\infty)$ and a compact \emph{target set} $T\subset\Omega$ and we assume that $c(x,u)$ is bounded from below by a constant $\delta > 0$ for $x\not\in T$ and all $u\in U$.  Our goal is to design a \emph{feedback law} $F:S\to U$, $S\subset\Omega$, $T\subset S$, that asymptotically stabilizes the system to the target set. To this end we employ the \emph{optimality principle} \cite{Be57a},
\begin{equation}\label{eq:DPP}
V(x) = \inf_{u\in U}\{c(x,u)+V(f(x,u))\},\quad x\in\Omega \backslash T,
\end{equation}
where $V:\R^n\to [0,\infty]$ is the \emph{(optimal) value function} which fulfills the boundary condition $V|_T=0$ and, by definition, $V|_{\R^n\backslash\Omega}=\infty$.

Using the \emph{Kru{\v{z}}kov transform} \cite{Kr75a} $V\mapsto v(\cdot)=\exp(-V(\cdot))$, (\ref{eq:DPP}) transforms to  $v(x) = \sup_{u \in U} \left\{e^{-c(x,u)} v(f(x,u))\right\}, x\in\Omega\backslash T$, the boundary condition transforms to $v|_T=1$ and we set $v|_{\R^n\backslash\Omega}=0$.  The right hand side of this fixed point equation yields the Bellman operator
\[
\Gamma(v)(x) := \left\{\begin{array}{ll}
\sup_{u \in U} \left\{e^{-c(x,u)} \bar v(f(x,u))\right\} & x\in\Omega\backslash T,\\
1 & x\in T,\\
0 & x\in\R^n\backslash\Omega
\end{array}\right.
\]
on the Banach space $L^\infty=L^\infty(\R^n,\R)$, where $\bar v(x) = v(x)$ for $x\in\R^n\backslash T$ and $\bar v(x)=1$ for $x \in T$.  By assumption on $c$, the Bellman operator $\Gamma:L^\infty\to L^\infty$ is a contraction and thus possesses a unique fixed point.

We are approximating $v$ by an element of the \emph{approximation space} $\cW = \operatorspan(w_1,\ldots,w_n)$, where 
\[
w_i(x) = \frac{\varphi_i(x)}{\sum_{j=1}^n \varphi_j(x)}, \quad i=1,\ldots,n,
\]
for $x\in\Omega$ and $w_i|_{\R^n\backslash\Omega}=0$ and the $\varphi_i(x)=\varphi(\|x-x_i\|_2)$, $x\in\Omega$, are \emph{radial basis functions} on the set $X = \{x_1, \ldots, x_n\}\subset\Omega$ of \emph{nodes}, cf.\ \cite{We95a,Fa07a}. We assume the \emph{shape function} $\varphi$ to be nonnegative, so that the $w_i$ are nonnegative, too. For some function $v:\R^n\to\R$, its \emph{Shepard approximant} $Sv\in\mathcal{W}$ is given by, cf.\ \cite{Sh68a}, $Sv = \sum_{i=1}^n v(x_i) w_i$.


We now want to approximate the fixed point of $\Gamma$. To this end, we define the \emph{Bellman-Shepard operator} to be $\tilde \Gamma := S\circ \Gamma:\cW\to\cW$. We show that the Shepard operator $S:(L^\infty,\|\cdot\|_\infty)\to (\cW,\|\cdot\|_\infty)$ has norm $1$ and that consequently the Bellman-Shepard operator $\tilde\Gamma:(\cW,\|\cdot\|_\infty)\to (\cW,\|\cdot\|_\infty)$ is a contraction and thus the iteration %(\ref{eq:value iteration}) 
$v^{(k+1)} := S\left(\Gamma[v^{(k)}]\right)$
converges to the unique fixed point $\tilde V\in\cW$ of $\tilde\Gamma$.

Numerical experiments illustrating the performance of the method will be given.

\paragraph{Acknowledgments.}
This work was partially supported by the EU under the 7th Framework Programme Marie Curie Initial Training Network FP7-PEOPLE-2010-ITN, SADCO project, GA number 264735-SADCO. 

\begin{thebibliography}{9} 
\bibitem{Be57a}
R.~Bellman.
\newblock {\em Dynamic programming}.
\newblock Princeton University Press, Princeton, N. J., 1957.

\bibitem{Fa07a}
G.E. Fasshauer.
\newblock {\em Meshfree Approximation Methods with Matlab}.
\newblock World Scientific, 2007.

\bibitem{Kr75a}
S.~N. Kru{\v{z}}kov.
\newblock Generalized solutions of {H}amilton-{J}acobi equations of eikonal
  type. {I}.
\newblock {\em Mat. Sb. (N.S.)}, 98(140):450--493, 1975.

\bibitem{Sh68a}
D.~Shepard.
\newblock A two-dimensional interpolation function for irregularly-spaced data.
\newblock In {\em Proc. 23rd ACM}, pages 517--524. ACM, 1968.

\bibitem{We95a}
H.~Wendland.
\newblock Piecewise polynomial, positive definite and compactly supported
  radial functions of minimal degree.
\newblock {\em Adv. Comp. Math.}, 4:389--396, 1995.
\end{thebibliography}

\end{document}
