N˚ d'ordre

N˚d’ordre:2469
THÈSE
présentéepourobtenir
LE TITRE DE DOCTEUR
DE L’INSTITUT NATIONAL POLYTECHNIQUE DE TOULOUSE
ÉcoleDoctoraleSystèmes
SpécialitéSystèmesInformatiques
ParM.BenjaminLussier
TOLÉRANCE AUX FAUTES DANS LES SYSTÈMES AUTONOMES
Soutenuele24avril2007devantlejurycomposéde:
M. C. PECHEUR Président
M. M. BANÂTRE Rapporteur
M. B. ESPIAU
M. J.P. BLANQUART Membre
M. F. INGRANDe
M. D. POWELL DirecteurdethèseAvant propos
LestravauxprésentésdanscemémoireontétéréalisésauLaboratoired’Analyse
et d’Architecture des Systèmes du Centre National de la Recherche Scientifique (LAAS
CNRS). Je remercie Messieurs Malik Ghallab et Raja Chatila, qui ont assuré la
direction du LAAS CNRS depuis mon entrée, pour m’avoir reçu au sein de ce
laboratoire. Je remercie également Monsieur Jean Arlat, responsable du groupe
ToléranceauxfautesetSûretédeFonctionnementinformatique(TSF),etMessieursRaja
Chatila et Rachid Alami, responsables successifs du groupe Robotique et Interac
tionS(RIS),pourm’avoiracueillidanscesgroupesderecherche.
JeremercieMonsieurCharlesPecheur,Professeuràl’UniversitéCatholiquede
Louvain,pouravoirprésidémonjurydethèse,ainsique:
• MonsieurMichelBanâtre,directeurderechercheàINRIARennes(IRISA),
•Jean PaulBlanquart,ingénieurd’étudesàAstrium,
• MonsieurBernardEspiau,directeurderechercheàINRIARhônes Alpes,
pouravoirparticipéàcejury.JeremercieenparticulierMessieursMichelBanâtre
etBernardEspiauquiontacceptélacharged’êtrerapporteurs.
Merci,surtout,àceuxquim’ontencadrépendantceslongstravaux:RajaCha
tila, Félix Ingrand, Marc Olivier Killijian et David Powell. Merci particulièrement
à David, pour sa rigueur scientifique, ses conseils et ses relectures diligentes, et
à Félix, pour son expérience en robotique, sa compréhension et sa disponibilité
constantes.
Je remercie aussi les autres participants des réunions Systèmes Autonomes Cri
tiques (SAC), épisodiques ou réguliers : Alexandre, Étienne, Jérémie et Matthieu.
MercienparticulieràMatthieu,poursonaideinestimabledanslacompréhension
etlamanipulationduplanificateurIxTeT.
MerciauxmembresdugroupeRIS,passésetprésents,quim’ontapprisàma
nipuler des robots tout au long de mon parcours : Alexandre, Aurélie, Frédéric,
Guillaume,Matthieu(Gallien),Matthieu(Herrb),Sara,Sylvain...
Merci aux membres du groupe TSF, avec qui j’ai passé de nombreuses jour-
néesbienaccompagné.Pourceuxquin’ontpasencorefinileurrédactiondethèse,
bon courage. Merci en particulier aux anciens et nouveaux camarades du célèbre
bureau10:Anis,Caroline,mentorÉric,anappleadayÉtienne,libricielLudo,Manel,
Noredine,youyouYoussef.
Merci, enfin, à mes parents, mon frère, mes amis, sans lesquels ce mémoire
seraitprobablementtrèsdifférent.Tabledesmatières
Introduction 9
1 Terminologieetétatdel’art 11
1.1 Lasûretédefonctionnementinformatique . . . . . . . . . . . . . . . 11
1.1.1 Principesgénérauxdelasûretédefonctionnement . . . . . 11
1.1.2 Latoléranceauxfautes . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2.1 Principedelatoléranceauxfautes. . . . . . . . . . 13
1.1.2.2 Toléranceauxfautesdedéveloppement . . . . . . 14
1.1.2.3 Validationdesmécanismesdetoléranceauxfautes 16
1.2 Lessystèmesautonomes . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 Notiond’autonomie . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.2 Mécanismesdécisionnels . . . . . . . . . . . . . . . . . . . . 18
1.2.2.1 Propriétésetfonctions . . . . . . . . . . . . . . . . 18
1.2.2.2 Exemplesdemécanismesdécisionnels . . . . . . . 19
1.2.2.3 Particularitévis à visdesfautes . . . . . . . . . . . 20
1.2.3 Conceptderobustesse . . . . . . . . . . . . . . . . . . . . . . 21
1.2.4 Architecturedessystèmesautonomes . . . . . . . . . . . . . 23
1.2.4.1 Styled’architecturesubsomptif . . . . . . . . . . . 24
1.2.4.2 Styled’architecturehiérarchisé. . . . . . . . . . . . 24
1.2.4.3 Approchemulti agents . . . . . . . . . . . . . . . . 26
1.3 Analysedel’existant . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.3.1 Étatdel’artenrobustesse . . . . . . . . . . . . . . . . . . . . 27
1.3.1.1 Observationetchoix . . . . . . . . . . . . . . . . . . 27
1.3.1.2 Détectionettraitement . . . . . . . . . . . . . . . . 28
1.3.2 Étatdel’artensûretédefonctionnement . . . . . . . . . . . 31
1.3.2.1 Préventiondesfautes . . . . . . . . . . . . . . . . . 31
1.3.2.2 Éliminationdesfautes . . . . . . . . . . . . . . . . . 31
1.3.2.3 Toléranceauxfautes . . . . . . . . . . . . . . . . . . 32
1.3.2.4 Prévisiondes . . . . . . . . . . . . . . . . . . 34
1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2 Architecturesetméthodespouruneautonomiesûredefonctionnement 37
2.1 Aspectarchitectural . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 Leslimitesdutyped’architecturehiérarchisé . . . . . . . . . 38
2.1.1.1 Risquededésaccords . . . . . . . . . . . . . . . . . 38
56 Tabledesmatières
2.1.1.2 Lenteur de réaction face à certaines situations ad
verses . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.1.1.3 Criticitédumécanismedécisionnel . . . . . . . . . 40
2.1.2 Unealternative:letyped’architecturemulti agents . . . . . 40
2.1.2.1 Réponsesauxlimitesd’unearchitecturehiérarchisée 41
2.1.2.2 Inconvénients spécifiques au type d’architecture
multi agents . . . . . . . . . . . . . . . . . . . . . . 42
2.2 Composantindépendantdesécurité . . . . . . . . . . . . . . . . . . 42
2.2.1 Caractéristiques . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.1.1 Règlesdesécurité . . . . . . . . . . . . . . . . . . . 43
2.2.1.2 Observationetaction . . . . . . . . . . . . . . . . . 43
2.2.2 Applicationsdanslessystèmesautonomes . . . . . . . . . . 44
2.2.2.1 RequestandReportChecker . . . . . . . . . . . . . 44
2.2.2.2 GuardianAgent . . . . . . . . . . . . . . . . . . . . 45
2.3 Mécanismesliésaucontrôled’exécutionetàlaplanification . . . . 46
2.3.1 Reprisedesituationsadversesparlecontrôled’exécution . 46
2.3.1.1 Détectiond’unesituationadverse . . . . . . . . . . 46
2.3.1.2 Réactionparreprise . . . . . . . . . . . . . . . . . . 46
2.3.1.3 Modalités . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.2 Planificationetsûretédefonctionnement . . . . . . . . . . . 47
2.3.2.1 Difficultésspécifiquesliéesàlaplanification . . . . 48
2.3.2.2 Méthodesexistantes . . . . . . . . . . . . . . . . . . 49
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3 Toléranceauxfautespourlaplanification 53
3.1 Mécanismesproposés . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1 Mécanismesdedétection . . . . . . . . . . . . . . . . . . . . 54
3.1.2derétablissement . . . . . . . . . . . . . . . . . 55
3.1.2.1 Planificationsuccessive . . . . . . . . . . . . . . . . 55
3.1.2.2concurrente . . . . . . . . . . . . . . . 57
3.1.3 LecomposantFTplan . . . . . . . . . . . . . . . . . . . . . . 59
3.1.3.1 Placedansl’architecture . . . . . . . . . . . . . . . 59
3.1.3.2 Principalesfonctionsducomposant . . . . . . . . . 60
3.2 Miseenœuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.1 L’architectureLAAS . . . . . . . . . . . . . . . . . . . . . . . 61
3.2.1.1 Présentationdel’architecture . . . . . . . . . . . . 61
3.2.1.2 IxTeT . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2.2 IntégrationdeFTplandansl’architectureLAAS . . . . . . . 66
3.2.2.1 Placedansl’architectureLAAS . . . . . . . . . . . 66
3.2.2.2 FonctionnementdeFTplan . . . . . . . . . . . . . . 67
3.2.2.3 Modificationsnécessairesdel’existant . . . . . . . 70
3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4 Évaluationdesmécanismesdetoléranceauxfautes 75
4.1 Environnementd’évaluation . . . . . . . . . . . . . . . . . . . . . . 75
4.1.1 Environnementlogiciel . . . . . . . . . . . . . . . . . . . . . 76
4.1.2 Ensembled’activités . . . . . . . . . . . . . . . . . . . . . . . 78Tabledesmatières 7
4.1.2.1 Missionsetenvironnements . . . . . . . . . . . . . 79
4.1.2.2 Modèlesdeplanification . . . . . . . . . . . . . . . 80
4.1.3 Ensembledefautes . . . . . . . . . . . . . . . . . . . . . . . . 83
4.1.4 Relevésetmesures . . . . . . . . . . . . . . . . . . . . . . . . 86
4.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.2.1 Comportementsansinjectiondefautes . . . . . . . . . . . . 88
4.2.1.1 Comportementnominal . . . . . . . . . . . . . . . 88
4.2.1.2 Coûtdel’utilisationdeFTplan . . . . . . . . . . . . 90
4.2.2 Comportementenprés