Accéder directement au contenu Accéder directement à la navigation
Chapitre d'ouvrage

SVM approximation of value function contours in target hitting problems

L. Chapel 1 G. Deffuant 2
1 Lab-STICC_UBS_CID_DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (UMR 3192), Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance
Abstract : In a problem of target hitting, the capture basin at cost c is the set of states that can reach the target with a cost lower or equal than c, without breaking the viability constraints. The boundary of a c-capture basin is the c-contour of the problem value function. In this paper, we propose a new algorithm that solves target hitting problems, by iteratively approximating capture basins at successive costs. We show that, by a simple change of variables, minimising a cost may be reduced to the problem of time minimisation, and hence a recursive backward procedure can be set. Two variants of the algorithm are derived, one providing an approximation from inside (the approximation is included in the actual capture basin) and one providing a outer approximation, which allows one to assess the approximation error. We use a machine learning algorithm (as a particular case, we consider Support Vector Machines) trained on points of a grid with boolean labels, and we state the conditions on the machine learning procedure that guarantee the convergence of the approximations towards the actual capture basin when the resolution of the grid decreases to 0. Moreover, we define a control procedure which uses the set of capture basin approximations to drive a point into the target. When using the inner approximation, the procedure guarantees to hit the target, and when the resolution of the grid tends to 0, the controller tends to the optimal one (minimizing the cost to hit the target). We illustrate the method on two simple examples, Zermelo and car on the hill problems.
Type de document :
Chapitre d'ouvrage
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.archives-ouvertes.fr/hal-00743682
Déposant : Import Ws Irstea <>
Soumis le : vendredi 19 octobre 2012 - 16:21:38
Dernière modification le : mercredi 24 juin 2020 - 16:19:23
Archivage à long terme le : : dimanche 20 janvier 2013 - 03:43:55

Fichier

cf2013-pub00036003.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

L. Chapel, G. Deffuant. SVM approximation of value function contours in target hitting problems. Informatics in control, automation and robotics. 8th International Conference, ICINCO 2011 Noordwijkerhout, the Netherlands, July 28-31, 2011, Revised Selected Papers, Springer, p. 37 - p. 48, 2013, Lecture Notes in electrical engineering, vol. 174, 978-3642313523. ⟨10.1007/978-3-642-31353-0_3⟩. ⟨hal-00743682⟩

Partager

Métriques

Consultations de la notice

522

Téléchargements de fichiers

427