wiki:SvmViabilityKernelApproximationBis
Warning: Can't synchronize with repository "(default)" (/var/svn/SVMViabilityController does not appear to be a Subversion repository.). Look in the Trac log for more information.

SVM Viability Kernel Approximation (2/3)

SVM Viability kernel approximation algorithm


Approximating viability kernel with a classification procedure

Consider a grid Kh covering the viability constraint set, with h the maximal distance between the points. At the first iteration, all the points xh of the grid are viable. We also suppose that G is mu-Lipschitz.

At iteration n+1, the algorithm remove the points that clearly go outside the generalisation of the approximation of the viability kernel at step n. If a point is viable at iteration n+1, we attribute to it a +1 label and -1 otherwise. We obtain the classification function l that define the current approximation of the viability kernel:

$L(K_h^{n+1})=\left\{ \vec{x} \in K \mbox{ such that } l_h^{n+1}(\vec{x}) = +1 \right\}$.

Algorithm We iteratively define the sets such that:

$K_h^0 = K_h$
  \\
  $L_h^0 = K$
  \\
  $K_h^{n+1} = \left\{ x_h \in K_h^n \hbox{ such that } d(G(x_h), L_h^n) \leq \mu h  \right\}$
  \\
  $L_h^{n+1} = L(K_h^{n+1})$
  \\
  \hbox{until } $K_h^{n+1} = K_h^n = K_h^p$

Then, if the classification procedure respects some conditions,

$L_h^p \rightarrow Viab_G(K) \hbox{ when } h \rightarrow 0$.

The algorithm thus provides an outer approximation of viability kernels.


Approximating viability kernel with support vector machines

We consider SVMs as a relevant classification procedure in this context. The main advantage of choosing SVMs is that they provide a kind of barrier function of the viability kernel boundary, which enables one to use gradient techniques to find a viable control.

Initialization: discretization of the state space and initialization of non-viable examples

Iteration n+1: SVMn is available

Iteration n+1: we use a gradient method to find a viable control (possibility to extend to several time steps)

$f(x) = \sum_{i=1}^n \alpha _i y_i k(x_i,x) + b$.

Iteration n+1: update the labels from SVMn and define SVMn+1


SVM Viability controller

The idea is to keep the same control u0 until the point at the next step reaches

$f(x) < \Delta$.

where Delta is a security distance on the approximation (the algorithm provides an outer approximation and it is thus necessary to reduces the approximation in order to stay within it). When the point reaches the security distance, find a viable control using the gradient descent of function f.

It is possible to define more or less cautious controller, anticipating on several time steps.


Fulfilment of algorithm convergence condition

One condition the SVMs must respect in order to proove the algorithm convergence is that the SVM produce no missclassified points. In practice, one must choose an high C-value in the SVM settings and a "good" alpha value (in case of using a gaussian kernel). An algorithm has been developped at LISC, in order to set automatically the SVM C-value:



[Problem and viability] previous page next page [Example]