Laboratoire d'Analyse et d'Architecture des Systemes du CNRS

De
Publié par

Niveau: Supérieur, Doctorat, Bac+8
These preparee au Laboratoire d'Analyse et d'Architecture des Systemes du CNRS en vue de l'obtention du Doctorat de l'Institut National Polytechnique de Toulouse Specialite : Systemes informatiques par Jeremi Gancet Systemes multi-robots aeriens : architecture pour la planification, la supervision et la cooperation Soutenance le 29 Septembre 2005 devant le jury : R. ALAMI LAAS-CNRS, Toulouse President R. CHATILA LAAS-CNRS, Toulouse Directeur de These P. LIMA IST/UTL, Lisbon Rapporteur A. SAFFIOTTI Universite d'Orebro Rapporteur S. LACROIX LAAS-CNRS, Toulouse Examinateur C. TESSIER ONERA, Toulouse Examinateur LAAS-CNRS 7, Avenue du Colonel Roche 31077 Toulouse Cedex 4

  • autonomie de decision

  • systemes multi-robots

  • classification en degres d'autonomie decisionnelle

  • degres eleves

  • comets

  • saffiotti universite d'orebro rapporteur

  • robotique aerienne


Publié le : jeudi 1 septembre 2005
Lecture(s) : 31
Source : ethesis.inp-toulouse.fr
Nombre de pages : 170
Voir plus Voir moins

These`
prepar´ ee´ au
Laboratoired’Analyseetd’ArchitecturedesSystemes` duCNRS
envuedel’obtentiondu
Doctoratdel’InstitutNationalPolytechniquedeToulouse
Specialit´ e´ :Systemes` informatiques
par
Jer´ emi´ Gancet
` ´Systemesmulti robotsa eriens:
architecturepourlaplanification,
lasupervisionetlacooperation´
Soutenancele29Septembre2005devantlejury:
R. ALAMI LAAS CNRS, Toulouse President´
`R. CHATILA Toulouse DirecteurdeThese
P. LIMA IST/UTL, Lisbon Rapporteur
¨´A. SAFFIOTTI Universited’Orebro
S. LACROIX LAAS CNRS, Toulouse Examinateur
C. TESSIER ONERA, Toulouse
LAAS CNRS
7,AvenueduColonelRoche
31077ToulouseCedex42Remerciements
Ce memoir´ e est la conclusion de quatre annees´ de travail au LAAS CNRS, a` Toulouse, dans
legroupederobotiqueetd’intelligenceartificielle.Jesouhaiteremercierlespersonnesquim’ont
permisderealiser´ cettethese` dansd’aussibonnesconditions.
Merci en premier lieu a` Malik Ghallab, directeur du laboratoire, pour m’avoir accueilli au
LAAS, et merci a` Raja Chatila, directeur du groupe RIA et directeur de ma these` , pour son ac
cueil,sonecoute´ ,etaussipoursaconfiance.
Merci a` Simon Lacroix, qui a dirige´ ma these` , pour son encadrement, sa disponibilite,´ son
habilete,sonsavoir fairequ’ilpartagesanscompter.´
Mercia` RachidAlami,quiaco encadr e´ mathese` ,pourlafinessedesesremarquesetdeson
jugement,quim’ontbeaucoupaide´ a` prendredurecullorsqu’ilyenavaitbesoin.
Merci a` mes rapporteurs Pedro Lima et Alessandro Saffiotti, pour avoir accepte´ de faire la
revuedemathese` ,pouretrˆ evenusdeloinpourassistera` lasoutenance,etpourleursremarques
pertinentes.
Merci egalement´ a` Catherine Tessier, qui a accepte´ de participer a` mon jury en tant qu’exa
minateur,etdontlesretoursm’ontdonne´ a` reflec´ hira` cetravailsousd’autresperspectives.
Merciaussia` tousmescollegues` thesar´ ds,toutaulongdecesquatresannees´ delabeur:un
clin d’oeil aux anciens, Solange, Fabien, Williams, Romain, Emmanuel (G.)... une tape dans le
dos a` mes “egos”, Emmanuel (Z.) et Fred, qui sont eux m emeˆ egalement´ Docteurs au moment
ou` j’ecris´ ces lignes... et puis tous mes encouragements aux cadets, bien trop nombreux pour ne
pas en oublier : une dedicace´ speciale´ pour Seb, pour les bons moments et delir´ es de COMETS,
ainsiquepourSylvain,pourladuretacˆ hederelecturedemathese` .
Merci encore aux partenaires du projet COMETS, pour les bons moments passes´ dans le
projet:unepenseeparticuliereaLuis,Fernando,Iker,Fran,Volker,quisontdesgensdontonse´ ` `
souvientlongtemps.
Merci enfin a` toute ma famille : supporter un thesar´ d pendant quatre ans n’est pas toujours
une sinecur´ e. La presence´ et la disponibilite´ de mes parents et de ma soeur Maud sont pour
beaucoupdanslareussite´ decetteetape´ demavie.
Merci,Han,ˆ pourtonattention,tapatience,tonamour.
34Table des mati`eres
Introduction 11
´ ´I Problematiqueetetatdel’art 15
I.1 Systemes` multi robots:lesprobl ematiques´ . . . . . . . . . . . . . . . . . . . 15
I.1.1 Architectureetdecision´ mono robot:g en´ eralit´ es´ . . . . . . . . . . . . . 15
I.1.2 Troispointsdevuepourapprehender´ lessystemes` multi robots . . . . . 18
I.1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
I.2 Robotiqueaerienne´ :defis´ etspecificit´ es´ . . . . . . . . . . . . . . . . . . . . . 26
I.2.1 Lepotentieldelarobotiqueaerienne´ . . . . . . . . . . . . . . . . . . . . 26
I.2.2 Systemes` multi UAV:tourd’horizon . . . . . . . . . . . . . . . . . . . 27
I.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
II Architecturedecisionnelle´ poursystemes` multi UAVh et´ er´ ogenes` 31
II.1 Unearchitecturea` geom´ etrie´ variable . . . . . . . . . . . . . . . . . . . . . . 31
II.1.1 Autonomiededecision´ etdecision´ d’autonomie . . . . . . . . . . . . . . 32
II.1.2 LecadreduprojetCOMETS . . . . . . . . . . . . . . . . . . . . . . . . 32
II.1.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
II.2 Architectureetautonomiedecisionnelle´ . . . . . . . . . . . . . . . . . . . . . 35
II.2.1 Uneclassificationendegres´ d’autonomiedecisionnelle´ . . . . . . . . . . 35
II.2.2 Degres´ faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
II.2.3 Degres´ ele´ ves´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
II.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
II.3 Propositiond’unecouchedelib´ erati´ veorientee´ interactionsmulti robots . . . . 41
II.3.1 Architecturedelib´ erati´ ve:tourd’horizon . . . . . . . . . . . . . . . . . 41
II.3.2 Leplanificateursymbolique . . . . . . . . . . . . . . . . . . . . . . . . 42
II.3.3 Lesraffineursspecialis´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . 43
II.3.4 Legestionnaired’interactions . . . . . . . . . . . . . . . . . . . . . . . 43
II.3.5 LesuperviseurdeCD. . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
II.3.6 Remarquesetrefle´ xionssurcettearchitecture . . . . . . . . . . . . . . . 44
III L’EMD:unexecutif´ gen´ erique´ 47
III.1 Considerations´ gen´ erales´ etformalismeadopte´ . . . . . . . . . . . . . . . . . . 47
III.1.1 Formalismedetacheˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
III.1.2 Fdecondition . . . . . . . . . . . . . . . . . . . . . . . . . . 49
III.1.3 Modalites´ surlesconditions . . . . . . . . . . . . . . . . . . . . . . . . 49
5`6 TABLE DES MATIERES
III.2 Principalesfonctionnalites´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
III.2.1 Gestiondesrequetesˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
III.2.2desev´ enements´ . . . . . . . . . . . . . . . . . . . . . . . . . . 51
III.2.3 Execution´ detacheˆ etsynchronisation . . . . . . . . . . . . . . . . . . . 52
III.2.4 Lecasparticulierdestachesˆ jointes . . . . . . . . . . . . . . . . . . . . 53
III.3 Exempledetraitementsdansl’EMD . . . . . . . . . . . . . . . . . . . . . . . 53
III.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
IV Delib´ eration´ etcoordinationdansunsysteme` multi UAVh et´ er´ ogene` 57
IV.1 Representations´ detachesˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
IV.1.1 Tachesˆ individuellesettachesˆ jointes . . . . . . . . . . . . . . . . . . . 59
IV.1.2 Tachesˆ el´ ementaires´ etplansel´ ementaires´ . . . . . . . . . . . . . . . . . 59
IV.1.3 Tachesˆ dehautniveau . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
IV.1.4 Missions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
IV.2 Lecoupleplanificateursymbolique/raffineurs... . . . . . . . . . . . . . . . . . 63
IV.2.1 Propagationd’identifantsdetacheˆ dehautniveau . . . . . . . . . . . . . 63
IV.2.2 Utilisationdesraffineurs . . . . . . . . . . . . . . . . . . . . . . . . . . 64
IV.3 Gerer´ lesinteractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
IV.4 Superviserladelib´ eration´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
IV.4.1 Aproposdelarepresentation´ deplan . . . . . . . . . . . . . . . . . . . 71
IV.4.2 Operations´ deplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
IV.5 Recapitulatif´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
V Legestionnaired’interactions 79
V.1 Vued’ensembledugestionnaired’interactions . . . . . . . . . . . . . . . . . . 79
V.1.1 Composants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
V.1.2 Principesdefonctionnement . . . . . . . . . . . . . . . . . . . . . . . . 81
V.2 Modelisations´ pourl’expressiondetachesˆ cooperati´ ves . . . . . . . . . . . . . 82
V.2.1 Introductionauxmodeles` d’interaction . . . . . . . . . . . . . . . . . . 82
V.2.2 Modelisation´ desrolesˆ . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
V.2.3 Modeles` decontraintesspatiales . . . . . . . . . . . . . . . . . . . . . . 88
V.2.4 Formalismedetabledecoordination . . . . . . . . . . . . . . . . . . . . 91
V.2.5 Modele` d’interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
V.3 Modalites´ denegociation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
V.3.1 Conceptionetapplicationdemodalites´ denegociation´ . . . . . . . . . . 95
V.3.2 Casdel’allocationderoleˆ . . . . . . . . . . . . . . . . . . . . . . . . . 97
V.3.3 Casdelanegociation´ d’intervalletemporel . . . . . . . . . . . . . . . . 99
V.3.4 D’autresmodalites...´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
V.4 Mecanique´ detraitementdesmodeles` d’interaction . . . . . . . . . . . . . . . 100
V.4.1 Etapepreliminaire´ :chargementd’unmodele` d’interaction . . . . . . . . 100
V.4.2 Activationettraitementd’unmodele` d’interactioncharge´ . . . . . . . . . 101
V.4.3 Leverificateur´ decontraintesspatiales . . . . . . . . . . . . . . . . . . . 114
V.5 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117`TABLE DES MATIERES 7
VI Resultats´ 119
VI.1 R´ enapplicationreelles´ dansCOMETS . . . . . . . . . . . . . . . . . 119
VI.1.1 Miseenœuvredel’architecturedanslesysteme` COMETS . . . . . . . . 119
VI.1.2 Missionsetscenarios´ COMETS,champsd’application . . . . . . . . . . 122
VI.1.3 Resultats´ obtenusenexperimentations´ reelles´ . . . . . . . . . . . . . . . 124
VI.1.4 Conclusionssurlesexp´ reelles´ . . . . . . . . . . . . . . . 128
VI.2 Resultats´ obtenusensimulation . . . . . . . . . . . . . . . . . . . . . . . . . . 128
VI.2.1 Dev´ eloppementlies´ a` lacouchedelib´ erati´ ve . . . . . . . . . . . . . . . . 128
VI.2.2 Implementation´ :choixtechniques . . . . . . . . . . . . . . . . . . . . . 128
VI.2.3 Planificationetraffinementdetachesˆ danslacouchedelib´ erati´ ve . . . . . 130
VI.2.4 Gestionnaired’interactions:miseenœuvrepartielle . . . . . . . . . . . 139
VII Conclusionsetperspectives 141
VII.1 Retoursurlescontributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
´ ´VII.1.1 Recapitulatifsynthetique . . . . . . . . . . . . . . . . . . . . . . . . . . 141
VII.1.2 Recapitulatif´ detaill´ e´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
VII.1.3 Etatdedev´ eloppement . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
VII.2 Limitesetperspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
VII.2.1 Leslimitesdenotreapproche . . . . . . . . . . . . . . . . . . . . . . . 143
VII.2.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
A IntroductionauplanificateurShop2 145
B Travauxexperimentaux´ pourlacouverturedezone 151
C Exemplederef´ er´ ence:automatesd’execution´ 155
Glossaire 159
´ ´Referencesbibliographiques 163`8 TABLE DES MATIERESTable des figures
I.1 L’architectureLAAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
I.2 8configurationsd’interactionselonFerber . . . . . . . . . . . . . . . . . . . . 19
II.1 Schema´ gen´ eral´ del’architecturedusysteme` COMETS . . . . . . . . . . . . . 34
II.2 5degres´ d’autonomiedecisionnelle´ (CsignifieCentralise´,etDsignifiedistribue´) 37
II.3 Degre´ 1:pasdecapacite´ decisionnelle´ autonome . . . . . . . . . . . . . . . . 38
II.4 Degre´ 2:supervisionautonome . . . . . . . . . . . . . . . . . . . . . . . . . 38
II.5 Degre´ 3:coordinationexecuti´ veautonome . . . . . . . . . . . . . . . . . . . . 39
II.6 Degre´ 4:planificationetcoordinationexecuti´ veautonomes . . . . . . . . . . . 40
II.7 Degre´ 5:allocationdynamiqueautonome . . . . . . . . . . . . . . . . . . . . 40
II.8 Architecturedecisionnelle´ :schema´ gen´ eral´ . . . . . . . . . . . . . . . . . . . 41
III.1 Traitementdesrequetesˆ :graphedetransitions . . . . . . . . . . . . . . . . . . 51
III.2 Tdesev´ enements´ :graphede . . . . . . . . . . . . . . . . 52
´ ˆIII.3 Executiondetache:graphedetransitions . . . . . . . . . . . . . . . . . . . . 53
III.4 Insertionetannulationdetachesˆ :exemple . . . . . . . . . . . . . . . . . . . . 54
IV.1 Architecturedecisionnelle´ :schema´ gen´ eral´ (rappel) . . . . . . . . . . . . . . . 58
IV.2 Detection´ avecunchampdepotentiel,ensimulation . . . . . . . . . . . . . . . 66
IV.3 Exemplesimpledemiseenœuvredesraffineursdepuisleplanificateur . . . . 67
IV.4 Entrees´ etsortiesdesoperateurs´ duSCD . . . . . . . . . . . . . . . . . . . . . 73
IV.5 Dependances´ entreop´ duSCD . . . . . . . . . . . . . . . . . . . . . . 76
V.1 Composantesdugestionnaired’interactions(GI). . . . . . . . . . . . . . . . . 80
V.2 Modele` d’interaction:composantes . . . . . . . . . . . . . . . . . . . . . . . 83
V.3 Exempledebasederolesˆ etbasedeMCS . . . . . . . . . . . . . . . . . . . . 84
V.4 Tabledecoordinationd’unevariantev1d’unmodele` d’interactionMI1 . . . . 85
V.5 Gauche:MI2“Poursuitedevehicule”´ -Droite:MI3“Cartographied’unezone” 85
V.6 Definition´ duref´ erentiel´ celeste´ a` partirdedeuxpoints . . . . . . . . . . . . . 89
V.7 Gestionnairedenegociations´ :traitementd’unemodalite´ denegociation´ . . . . 97
V.8 Moteurdetraitement:cycledebase . . . . . . . . . . . . . . . . . . . . . . . 111
V.9 Autresactivites´ dumoteurdetraitements . . . . . . . . . . . . . . . . . . . . . 112
VI.1 Hauta` gauche,Karma-Hauta` droite,Marvin-Enbas,Heliv . . . . . . . . . . 121
VI.2 Premiere` partie:detection´ d’unealarme . . . . . . . . . . . . . . . . . . . . . 124
VI.3 Deuxieme` partie:confirmationd’unealarme . . . . . . . . . . . . . . . . . . 125
910 TABLE DES FIGURES
VI.4 Troisieme` partie:surveillancecoordonnee´ etcartographie . . . . . . . . . . . 126
VI.5 Monitoringcooperatif´ d’unfoyerparMarvinetHeliv . . . . . . . . . . . . . . 127
VI.6 Configurationdetestdeplansproduitsparlecoupleplanificateur/raffineurs . . 130
VI.7 DomainedeplanificationCOMETS:hierarchie´ desmethodes´ . . . . . . . . . 131
VI.8 Definition´ d’unprobleme` ShoppourKarma . . . . . . . . . . . . . . . . . . . 132
VI.9 Tachesˆ el´ ementaires´ obtenuespour . . . . . . . . . . . . . . . . . . . . 134
VI.10 Testensimulation:detection´ d’alarmeparKarma . . . . . . . . . . . . . . . . 135
VI.11 Definition´ d’unprobleme` ShoppourHeliv(haut)etMarvin(bas) . . . . . . . . 136
VI.12 Tachesˆ el´ ementaires´ produitespourHeliv . . . . . . . . . . . . . . . . . . . . 137
VI.13 Tachesˆ el´ ementaires´ produitespourMarvin . . . . . . . . . . . . . . . . . . . 138
VI.14 Testensimulation:perceptionscooperati´ vesentreHelivetMarvin,apres` syn
chronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
A.1 ExemplesimplededomaineShop2 . . . . . . . . . . . . . . . . . . . . . . . . 146
` ´A.2 Exdeproblemeetresultatobtenu . . . . . . . . . . . . . . . . . 147
A.3 ExemplededomaineShop2avecdes“timelines” . . . . . . . . . . . . . . . . 148
A.4 Exdeprobleme` etsolutionassociee´ dansledomaineavec“timelines” . . 149
B.1 Partagedezone,resultat´ ensimulation . . . . . . . . . . . . . . . . . . . . . . 152
B.2 Applicationdemotifsdechemindesurvol . . . . . . . . . . . . . . . . . . . . 153
C.1 Automated’execution´ duroleˆ R1 . . . . . . . . . . . . . . . . . . . . . . . . . 156
C.2d’execution´ duroleˆ R2 . . . . . . . . . . . . . . . . . . . . . . . . . 157

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.