Home

Calculs longs et partage des ressources processeur dans les

1. 3 2 2 Utilisations possibles 3 3 Les artifacts de calcul 531 UNIT 4 3 54 Lai La she Ree Eee b b th ba de 3 32 D RNMIUON 4 4 pus pose ns audi ie a a e d 3 3 3 Notes d impl mentation et contraintes suppl mentaires 3 4 Le langage de mode d emploi des artifacts 3 4 1 Les alg bres de processus 3 4 2 Le langage initial 3 4 3 NOS extensions 3431 L attente os uy oe wR Np humain pau 3 4 3 2 L alternative apr s un timeout 3 4 3 3 Utilisation de l historique 3 4 3 4 Possibilit s de raisonnement pour l agent 3 4 3 4 1 Lien s mantique avec la base de connaissances de l agent 3 4 3 4 2 Utilisation de Design to Criteria 3 4 3 5 Fonctionnalit s manquantes 3 4 4 Mode d emploi des artifacts de calcul 3 4 4 1 Algorithme bo te noire 3 4 4 2 Algorithme dur e d ex cution connue 3 4 4 3 Algorithme contrat 3 4
2. Soit Mm l nergie processeur disponible dans l intervalle m Mm P DLm DDm avec P la puissance processeur par unit de temps Si ERim ESR lt Mm alors on r initialise ESR et les Ci y 0 Sinon on ajoute E Rim Mm ESR et on place Cim la valeur 1 4 1 3 2 3 R solution Nous avons maintenant d termin toutes les valeurs num riques utiles et il ne reste plus que les D j comme variables d terminer Le programme lin aire r soudre pour cela est le suivant on i Mas z X 2 j 1 D 4 1 j 1 90 Chapitre 4 La gestion des ressources processeur Dij 20 1 lt j lt 2 4 2 on i 5 Dys DLi DD 4 3 j l Eii ER 4 4 Ein lt ERip j 1 lt k lt 2 1 4 5 gn 1 Y Cir Es gt ESR 4 6 k j 1 4 1 On cherche maximiser la somme pond r e des dur es D de l intervalle 7 Les facteurs de pond ration sont tels que le facteur de D soit plus grand que le facteur de D 1 4 2 Toutes les dur es sont positives 4 3 La t che doit se terminer avant sa date limite la somme des dur es de ses parties est inf rieure ou gale la dur e de l intervalle courant 4 4 La somme des nergies des parties de la t che 7 dans l intervalle 2 doit tre gale l nergie restante affecter pour la t che 1 4 5 On ne peut affecter plus d nergie une t che dans l intervalle que la quantit qui reste pour cette t che part
3. DD To et on i 1 DD Y Das LEPE j 1 Soit Li 1 qui vaut 1 si la t che k poss de une de ses parties dans le sous intervalle j de l intervalle i et O sinon Et soit E y l nergie totale effectivement affect e la t che k dans l intervalle 7 on k E 3 BD j l On peut calculer ER y l nergie restante pour la t che k partir de l intervalle 7 inclus ainsi ER ET et ERik ERi 1k Ei1k 2 lt i lt n 1 lt k lt 2 74 Comme nous r solvons le probl me intervalle par intervalle nous devons nous assurer que nous choisissons correctement les t ches qui vont s ex cuter dans un intervalle 7 particulier En effet pour les t ches qui ne pourraient pas s ex cuter enti rement dans leur intervalle nous devons prendre en compte dans les intervalles pr c dents que l on doit absolument leur affecter une part de l nergie disponible Un exemple dans le paragraphe 4 1 3 2 4 illustre cela Soit ESR l nergie minimale affecter dans l intervalle i d autres t ches que la i Et soit Cik t 1 lt k lt 2 qui vaut 1 si la t che k fait partie de la liste des t ches pour lesquelles il faut affecter un minimum d nergie dans l intervalle 7 Le calcul des C 4 et de ESR se fait en partant du dernier intervalle et en remontant vers l intervalle 7 On initialise tout d abord ES R et les C y 20 A l intervalle m on met jour ES R et les C x de la mani re suivante
4. FIG 5 3 L aiguilleur dispatche les messages vers les fils de raisonnement 109 Lorsque l agent d marre l aiguilleur le FDR par d faut et la m moire globale sont initialis s Un interpr teur est charg de l ex cution du programme de l agent Il conserve les informations relatives aux FDR comme leur nom leur tat courant les valeurs des timeouts pos s et leur m moire locale Il conserve galement une file des v nements non encore trait s Un cycle d ex cution est d crit ainsi TANT QUE calculer le timeout a appliquer Lae s messages il reste au moins une instance de FDR FAIRE minimum des timeouts restants des FDR instanci s ntrants pendant au maximum timeout secondes SI il y a des messages a traiter ALORS appl liquer la proc dure strat gie_de_filtration message M a traiter pour s lectionner 1 app SINON le timeout a expir squels r veiller les FDR pour 1 FIN SI x cuter s quentiellement les actions des transitions qui ont t activ es supprimer les instances de FDR qui sont arriv es dans l tat FIN FIN TANT QUE 5 1 3 Int gration des artifacts la plateforme liquer les r gles de grammaire sur M pour d terminer le FDR r veiller Nous avons tudi et impl ment l int gration des artifacts de calcul pr sent s dans cette th se au sein de notre plateforme qui tait initialement con ue pour n accueillir
5. a D j Eu y gt e Acqu rir des grains Moudre le caf CHE J Limite Consomme RS 1 1 7 EEN S a e S onsomme an j Acheter des grains Utiliser des grains Limite au supermarch congeles Limite Consomme ae J ut AN a NET 7 0 0 20 0 100 0 0 0 0 0 100 0 0 0 20 0 100 0 FIG 2 6 Exemple d arbre T EMS courant pour chaque ressource Ici l eau chaude est actuellement au niveau 20 Le niveau minimal est 0 et le niveau maximal est 100 Les annotations et relations possibles sur les n uds sont tr s nombreuses et permettent de mod liser des situations tr s complexes L ordonnanceur utilis est Design to Time ou son volution Design to Criteria Le principe de P ordonnancement Design to Time est de construire dynamiquement des plans d ex cution en privi l giant les plans qui par ordre de priorit aboutissent des qualit s nulles pour tous les groupes de t ches maximisent la somme des qualit s de tous les groupes de t ches et minimisent le temps total d ex cution des m thodes Le r sultat de cet algorithme d ordonnancement est un plan d ex cution qui sp cifie quelles m thodes ex cuter quand les ex cuter et quelles valeurs sont attendues apr s leur ex cution Garvey et Lesser 1996 Design to Time a t utilis pour ordonnancer des algorithmes anytime en choisissant quelques temps d ex cution et
6. CENTRE NATIONAL USTL DE LA RECHERCHE SCIENTIFIQUE Calculs longs et partage des ressources processeur dans les systemes multi agents cognitifs THESE pr sent e et soutenue publiquement le 30 mars 2007 pour l obtention du Doctorat de l Universit des Sciences et Technologies de Lille sp cialit informatique par C dric DINONT Composition du jury Rapporteurs Amal EL FALLAH SEGHROUCHNI Professeur LIP6 Universit Pierre et Marie Curie Alessandro Ricci Docteur DEIS Universit de Bologne Examinateurs Laurence DUCHIEN Professeur LIFL Universit Lille I Pierre MARQUIS Professeur CRIL Universit d Artois Emmanuel DRUON Docteur ISEN Patrick TAILLIBERT Thales Division A ronautique Directeur Philippe MATHIEU Professeur LIFL Universit de Lille I UNIVERSITE DES SCIENCES ET TECHNOLOGIES DE LILLE Laboratoire d Informatique Fondamentale de Lille UPRESA 8022 U F R d LE E A Bat M3 59655 VILLENEUVE D ASCQ CEDEX T l 33 0 3 28 77 85 41 T l copie 33 0 3 28 77 85 37 email direction lifl fr Mis en page et compos avec I4TRX et la classe thlifi Remerciements Je tiens ici remercier les trois chefs qui m ont suivi tout au long de cette th se Philippe tu as tout d abord t un enseignant passionn et passionnant Comme directeur de th se J ai beaucoup appr ci ton enthousiasme permanent et ta pers v rance pour am liorer la clart de mon discour
7. To FIG 4 3 Prise en compte dans la r solution pour un intervalle de contraintes sur les intervalles restants Prenons pour notre second exemple un agent APRC et les requ tes suivantes pour trois arti facts 700ops 4s 1000ops 6s et 1300ops 8s La figure 4 4 montre que l on arrive terminer la tache 1 avant la fin de son intervalle tout en ex cutant les taches 2 et 3 en parall le La nouvelle date de d but du second intervalle n est plus DL mais la somme des D Il en est de m me pour la date de d but du troisi me intervalle puisque la t che 2 se termine avant la date DL Utilisation processeur 100 APRC Agent A3 A2 Al Temps DL FIG 4 4 Modification des dates de d but d intervalles 4 1 4 Extensions et variantes de l algorithme d ordonnancement La description pr c dente de notre algorithme d ordonnancement prend en compte un cas d uti lisation assez strict Nous proposons ici diff rentes extensions et variantes qui peuvent permettre de s adapter diff rentes situations que l on peut rencontrer en pratique lorsqu on utilise notre ordon nanceur 92 Chapitre 4 La gestion des ressources processeur 4 1 4 1 Apparition de nouveaux agents Lalgorithme pr sent plus haut g re un nombre d agents fixe et un nombre d artifacts volutif Il est possible d tendre le syst me pour prendre en co
8. c t des agents Ils ont ensuite cherch tendre le concept d autres utilisations que la coordination et iden tifier les modifications que l utilisation des artifacts apportent la mod lisation et la programmation des syst mes multi agents Ricci et al 2005 Ricci et al 2006 6 Nous d crivons dans la suite le concept d artifact tel que nous l utilisons dans nos syst mes Il y a quelques diff rences par rapport la d finition initialement introduite par l quipe italienne dans le cadre de ses travaux sur la coordination Celles ci sont mises en vidence dans le texte Nous proposons ensuite une sp cialisation du concept pour les longs calculs L analyse du langage utilis pour sp cifier les modes d emploi des artifacts fait l objet d une section particuli re 3 2 1 D finition Omicini remarque dans Omicini ef al 2005 que l utilisation d outils a toujours accompagn l volution de l esp ce humaine depuis l homo habilis l homo sapiens sapiens en passant par l homo faber l homme fabricateur Il est m me certain aujourd hui que le d veloppement de l in telligence comme caract ristique de l esp ce humaine est tr s fortement li la disponibilit et au d veloppement des outils La th orie de l activit humaine Kaptelinin et al 1995 fait ressortir le fait que les outils
9. cuter des t ches calculatoires longues De plus pour les raisons cit es dans le chapitre pr c dent nous ne pouvons modifier le code qui r alise les t ches calculatoires En particulier nous ne pouvons pas int grer dans ce code un appel r gulier la m thode de traitement des nouveaux messages de la bo te aux lettres de l agent Il faut donc disposer de plusieurs fils d ex cution qui s ex cutent en parall le processus ou processus l ger un qui int gre le comportement extraverti de l agent traitement des messages v rification des changements dans l environnement un autre pour chaque tache de calcul longue La question a laquelle il faut r pondre maintenant est sous quelle forme doit on faire apparaitre le second type de fil d ex cution dans le SMA Faut il le faire appara tre comme une partie des agents un objet un composant une couche Ou comme un type d agent particulier Ou encore comme une nouvelle entit dans les SMA 3 1 2 Une partie de l agent Consid rons tout d abord que les fils d ex cution qui r alisent les t ches longues soient des parties de l agent On pourrait mod liser un agent comme un assemblage d objets ou de composants L approche par composant semble s duisante car elle permet l utilisation de code h rit et elle apporte la r utilisa bilit dans diff rents contextes De plus les communaut s composant et agent tentent de combiner leurs
10. rester dans des chemins balis s o le risque d erreur est plus faible L am lioration de la mise en uvre de ces principes dans les syst mes s est faite par l introduction d une succession de paradigmes des mod les coh rents de vision de la mod lisation des applications Le paradigme objet est le plus couramment utilis actuellement L encapsulation des donn es per met un faible couplage entre les entit s du syst me et une r utilisabilit dans diff rents contextes L h ritage et le polymorphisme permettent de simplifier le d veloppement d entit s l g rement diff rentes de celles d j cr es en r utilisant du code d j prouv Le paradigme agent volution des travaux initi s par Carl Hewitt sur les langages d ac teur Hewitt et al 1973 semble correspondre une volution majeure des techniques de mod li sation Il peut tre vu comme un rempla ant avantageux du paradigme objet Le concept d autonomie doit permettre en d couplant les entit s du syst me de mani re beaucoup plus drastique qu aupara vant de casser la complexit structurelle des syst mes Les agents devraient par exemple tre capables de continuer fonctionner si leurs liens de communication avec les autres agents sont coup s ou si un agent ne r pond pas ou pas favorablement une de leurs requ tes Dans beaucoup de syst mes multi agents le concept d agent est une abstraction qui n e
11. sel et ensuite on revient dans l tat initial pour un nouveau cycle de dix lavages Ce fonctionnement est sch matis dans la figure 3 5 L instruction op ratoire correspondante est la suivante lave_vaisselle_simple laver fin_lavage laver fin_lavage gt laver fin_lavage remettre_du_sel fin_remplissage lave_vaisselle_simple Il est bien vident qu il ne sera possible de g rer ainsi que des boucles constitu es de quelques it rations Nous proposons d utiliser plut t des informations sur l historique des tats de l instruc tion op ratoire pour inhiber ou d sinhiber des branches de celui ci L historique est vu comme la 3 4 Le langage de mode d emploi des artifacts 67 Remettre du sel FIG 3 5 Mode d emploi d un lave vaisselle qui ne prend pas en compte I historique succession des v nements qui se sont produits lancement d une action a_nom_action ou d clenchement d une perception p_nom_percept ion La succession des v nements est conserv e comme ceci H a_actionl p_perceptionl a_action2 p_perception2 Les conditions sur historique sont exprim es sous la forme d expressions rationnelles 4 On dispose des op rateurs suivants pour une occurence unique d une action ou d une perception quelconque a_ pour une occurence unique d une action quelconque p_ pour une occurence unique
12. tout moment pr emptibilit il doit pouvoir tre suspendu et relanc au m me point avec un temps de r ponse n gligeable afin de se pr ter aux techniques d ordonnancement Le terme anytime est souvent utilis de mani re abusive pour d crire un algorithme seulement interruptible et ou incr mental Nous prendrons dans la suite une d finition plus stricte de la notion d algorithme anytime dans laquelle l algorithme consid r dispose obligatoirement d une capacit de pr diction de la qualit de la solution en fonction du temps de calcul qui lui a t allou La pr diction de la qualit est r alis e au moyen d un profil de performance qui montre l volu tion de la qualit de la solution en fonction du temps Un agent d cide du temps d ex cution d un algorithme en mettant en perspective la qualit esp r e du r sultat et l utilit correspondante En effet il arrive souvent que l utilit d une donn e d croisse en fonction du temps 20 Chapitre 2 Contexte Nous retenons les d finitions de qualit et d utilit donn es dans Delhay 2000 D finition 2 5 Qualit Pour un algorithme donn la qualit du r sultat O t d de l algorithme est une application de l ensemble des couples temps de calcul t donn e en entr e d dans R ou 0 1 D finition 2 6 Utilit Pour un algorithme donn l utilit U q t d un r sultat est une application de l ensemble
13. 38 Chapitre 2 Contexte L agent ex cute les op rations suivantes chaque top d horloge 1 lecture des messages en attente et mise jour de l tat mental Le programme de l agent met ainsi jour les croyances et les engagements de agent 2 ex cution des engagements pour la date courante Cette tape est r alis e de mani re automa tique sans que cela soit crit dans le programme de agent La figure 2 5 d crit les fl ts de contr le et de donn es qui existent entre les diff rents modules d un agent Agent 0 Initialisation de l tat mental et des comp tences Messages entrants D finition des r gles pour cr er de nouveaux engagements lq TN Repr sentation Mise jour de Horloge F de pat Tne l tat mental l tat mental et des comp tences A gt r Ex cution des engagements pour la date courante Messages sortants AA O AA gt Flotde contr le 2222 2 2 trem gt Flot de donn es FIG 2 5 Diagramme de flot d un agent Agent 0 Agent 0 est pr sent par Shoham comme un langage simple pour illustrer ses id es sur la program mation orient e agent Il a cependant t surpris par certaines difficult s apparues a la conception et galement par le nombre important d exemples d utilisation d couverts Nous d taillons l exemple de r servation de billets d avions
14. autres KA 2 2 3 4 4 T MS T EMS est l aboutissement des travaux du Multi Agent Systems Lab de l universit du Mas sachussets sur les choix des agents en pr sence de contraintes temporelles C est une architecture compl te pour la gestion du contr le local des agents et les raisonnements au niveau organisation du SMA T MS signifie Task Analysis Environment Modeling and Simulation Il propose un langage de description des activit s des agents sous forme d un arbre hi rarchique Celui ci permet de d crire les t ches de l agent plusieurs niveaux d abstraction avec des d lais possibles chaque niveau Les feuilles de l arbre repr sentent les m thodes ex cutables La figure 2 6 donne un exemple d arbre utilis par T MS issu de Horling 1999 Dans celui ci nous voyons comment un agent peut faire du caf 3 Les rectangles arrondis repr sentent des actions abstraites et les rectangles droits des actions l mentaires Les n uds correspondants des actions abstraites peuvent tre annot s pour permettre l or donnanceur de savoir comment voluent chacun des crit res en fonction des sous t ches r alis es Par exemple les n uds Faire le caf etAcqu rir les ingr dients sont annot s avec q_min qui signifie que toutes les sous t ches doivent tre r alis es pour pouvoir accro tre la qualit s mantique du ET Une autre annotation permet de soulever une des carac
15. duire par q_seq_sum mais fonctionne de la m me mani re part que la qualit obtenue pour la t che est la somme des qualit s de sous t ches Le choix entre les diff rentes traductions possibles d pend du crit re choisi pour faire fonctionner Design to Criteria et de la mani re avec laquelle on veut guider algorithme dans les diff rentes branches de arbre Cette traduction des instructions op ratoires vers T MS peut tre mise profit pour autoriser des raisonnements sur les diff rentes alternatives qui existent dans les instructions op ratoires No tons que nous pouvons toujours utiliser notre extension concernant l utilisation de l historique mais que cela impose de r appliquer Design to Criteria chaque fois que activation d une condition sur Vhistorique a modifi I instruction op ratoire 3 4 3 5 Fonctionnalit s manquantes Les modes d emploi tels que nous pouvons les d finir actuellement permettent de d finir un mode d emploi qu il est obligatoire de suivre Il n est pas possible d y indiquer des conseils d utilisation Dans l exemple du lave vaisselle pr c dent on pourrait ainsi indiquer que le remplissage du bac sel est recommand tous les dix lavages mais que ceci n est pas obligatoire La gestion du temps sous forme de param tres de dur es dans les instructions d attente et de timeout est galement tr s limitative Il serait int ressant de remplacer ces param tres d
16. ex cuter sur les machines distantes les primitives de cr ation ou de migration appel es par un agent et de g rer les transferts de donn es ventuellement n cessaires La continuit du service de messagerie est galement assur e pour que les agents ne perdent pas de messages pendant le processus de migration La figure 5 2 illustre le fonctionnement de la migration d agents ALBA d une machine une autre Machine 1 192 168 0 1 Messages a lt gt s x sx s x gt Ke s A 3 Migration re k g a D mon y W ye PA N P Machine 2 192 168 0 2 FIG 5 2 La migration des agents dans ALBA 108 Chapitre 5 Mise en ceuvre et valuation 5 1 2 Mod le d agent utilis Les diff rentes version de la plateforme de d veloppement d agent de Thales ont essay de d co reller la partie architecturale du sous syst me d ex cution et le mod le d agent r ellement implant dans les applications Le but est de pouvoir tester plusieurs mod les et construire de mani re incr mentale celui qui convient aux applications de Thales Les premi res applications ont donc t cod es en Prolog pur sans aucune biblioth que sp cifique au d veloppement agent Un certain nombre de limitations sont rapidement apparues comme la dif ficult 4 maintenir diff rents contextes de conversation et de raisonnement de mani re simultan e et ceci sans utiliser de processus l gers car
17. exploitation quel moment donner la main un autre programme Il dispose pour cela d un appel syst me yield Cette m thode le multi t che coop ratif a l avantage d tre simple mettre en uvre Elle permet de donner deux niveaux d illusion l utilisateur Un utilisateur n a pas tre conscient que d autres utilisateurs utilisent le syst me en m me temps que lui En effet si les ressources processeur disponibles pour un utilisateur donn lui suffisent il ne s aper oit pas que d autres utilisateurs consomment des ressources en m me temps que lui Les utilisateurs peuvent travailler de mani re ind pendante sans avoir se pr occuper des autres utilisateurs Un utilisateur peut voir plusieurs de ses programmes s ex cuter simultan ment si le passage de l un l autre est suffisamment fr quent Elle poss de cependant de nombreux inconv nients visibles au niveau des programmeurs C est une forme de couplage fort dans laquelle le d veloppeur d un programme ne peut faire abstraction du fait qu il y aura d autres programmes qui vont s ex cuter sur le processeur La robustesse est aussi limit e car le syst me entier peut s arr ter si un des processus n ex cute jamais l instruction yield La m thode actuellement utilis e sur la plupart des syst mes d exploitation disponibles se nomme multi t che pr emptif L appel syst me yield n est plus utilis et
18. 05 Mathieu et Picault 2006 MATHIEU P et PICAULT S 2006 Vers une repr sentation des compor tements centr e interactions In RFIA 06 McCabe et Clark 1995 MCCABE F G et CLARK K L 1995 April agent process interaction language In WOOLDRIDGE M et JENNINGS N R diteurs Intelligent Agents Theories Architectures and Languages LNAI volume 890 pages 324 340 Springer Verlag Heidelberg Germany Milner 1982 MILNER R 1982 A Calculus of Communicating Systems Springer Verlag New York Inc Secaucus NJ USA Moszkowski 1986 MOSZKOWSKI B 1986 Executing temporal logic programs Cambridge University Press New York NY USA Muller et Pischel 1993 MULLER J et PISCHEL M 1993 The agent architecture InteRRaP Concept and application Odell 2002 ODELL J 2002 Objects and agents compared Journal of Object Technology 1 1 41 53 Omicini et al 2005 OMICINI A RICCI A et VIROLI M 2005 Agens faber Toward a theory of artifacts for MAS In Electronic Notes in Theoretical Computer Sciences First International Workshop Coordination and Organization CoOrg05 COORDINATION 2005 Omicini et al 2004 OMICINI A RICCI A VIROLI M CASTELFRANCHI C et TUMMOLINI L 2004 Coordination artifacts Environment based coordination for intelligent agents In AA MAS 04 OpenMP OPENMP http openmp org Ricci et al 2005 RICCI A VIRO
19. 2 2 1 2 Classes de complexit 2 2 1 3 Utilisation d heuristiques 2 2 1 4 Algorithmique anytime 2 2 2 La distribution des calculs approches et techniques 2 2 2 1 Cas d une machine 2 2 2 1 1 Le multi t che 2 2 2 1 2 Les syst mes d exploitation temps r el 2 2 2 1 3 Les processeurs multi c urs vii Dn UU Hua pl viii Table des mati res 2 2 2 1 4 Les machines multiprocesseurs et les grappes 26 IMPI a Su aa DRE Ee es TE a 27 OpenMP we ee a ee ee es 27 2 2 2 2 Cas multi machine et solutions r seau 28 2 2 2 2 1 Objets distribu s 29 2 2 2 2 2 Composants 29 222 23 Le GRID 24 544 E e Se arte 29 Open Grid Services Architecture 30 Le calcul distribu la maison 30 2 2 3 Gestion du temps dans les syst mes intelligents 31 2 2 3 1 Langages et techniques pour le raisonnement temporel 31 2 2 3 1 1
20. Synthese 40 a 84 46 Done uns 8 AU He Eh UE a mue 102 5 Mise en uvre et valuation 105 S 1 Mise en uvre a ge 5 44 sus AA AUS Dee a 105 Dl ALBA e 21 4 acy ia disent hum ee ile sers 105 5 1 1 1 Une plateforme pour Prolog 105 5 1 1 2 Caract ristiques E de oi a aE a S Ms nas ete Le 106 5 1 1 2 1 D centraliSatiOM 106 5 1 1 22 sGenericite a o a A 107 5 1 1 2 3 La migration des agents o 107 5 1 2 Mod le d agent utilis 108 5 1 3 Int gration des artifacts la plateforme 109 xi 5 2 Pr sentation de l application Interloc 110 5 3 __ Nouvelle mod lisation d Interloc avec les artifacts 112 5 4 Exp rimentations 114 5 4 1 Avec etisans APRO o o o e og on sue md ma Da Eur es 114 5 4 2 Equilibrage de charge sur plusieurs processeurs 115 5 o 244 sus d saura eo dde Pade edeR seb 117 6 Conclusion 119 7 Perspectives 123 7 1 Mode d emploi des artifacts 123 T2 Modelo d agent ss 4 404 un enaa t pad Rad na l 124 7 3 Gestion du temps dans les syst mes multi agents 124 7 4 Rapprochement avec d autres era DDR
21. Une source d v nement est une interface utilis e par un type de composant en mode asyn chrone Les artifacts quant eux re oivent les actions qu ils doivent r aliser en mode synchrone les actions sont r alis es d s qu un agent le demande Par contre rien n est impos a l agent pour le traitement des perceptions Il peut le faire de mani re synchrone ou asynchrone en g rant par exemple les perceptions de la m me mani re que les messages qu il regoit des autres agents De plus un 3 7 Rapprochement avec les autres travaux de l quipe SMAC 79 artifact n utilise a priori pas les services d autres entit s du syst me ou tout du moins ne les exhibe pas a l ext rieur Il n y a donc pas d quivalent des r ceptacles et des puits d v nements Les attributs repr sentent les propri t s configurables du composant Ils se rapprochent des at tributs d finis pour les artifacts mais leur s mantique est moins pr cise dans les composants ils pourraient ne pas exister et tre remplac s par des m thodes appel es en mode synchrone pour lire ou modifier un attribut Ce qui diff rencie clairement un artifact d un composant ce sont les instructions op ratoires qu il exhibe Les autres diff rences sont somme toute assez mineures En d finitive et pour r sumer un artifact peut tre consid r comme un composant disposant d un mode d emploi formel r ifi que les agents peuvent manipuler Cette
22. agent intelligent utilisant conjointement les r sultats des diff rents sous domaines de l IA De ce point de vue un agent serait un syst me d IA complet capable d utiliser ses diff rentes capacit s intelligentes de base pour voluer dans un environnement complexe Ainsi un agent peut tre basiquement vu de l ext rieur comme 1 une entit qui agit dans un environnement au travers de capteurs et d actionneurs figure 1 1 Le programme d un agent doit donc d cider des actions r aliser dans l environnement en fonction des informations qu il en per oit On parle aussi de fonction de l agent Il est souvent remarqu qu il n y a pas encore de consensus sur la d finition des propri t s que doit avoir une entit informatique pour pouvoir tre nomm e agent Cette difficult aboutir un consensus provient de la diversit des environnements dans lesquels nous pouvons plonger les agents Les d finitions donner aux propri t s d autonomie de r activit de pro activit de prise en compte des changements dans l environnement extraversion et donc la d finition m me de la notion d agent varient avec l environnement dans lequel se trouvent les agents Agent vient du Latin agere agir faire 1 2 Le g nie logiciel l am lioration des techniques de programmation 3 Fonction de l agent Actions Perceptions Y Environnement FIG 1
23. aliser une t che si on nous le demande et supprimer de la file tous les autres messages en r pondant qu on ne les comprend pas do any arg gt T arg done gt gt replyto any Other gt unrecognized Other gt gt replyto 42 Chapitre 2 Contexte April poss de quelques fonctionnalit s permettant de g rer le temps on peut activer un processus a une date donn e et on peut param trer la dur e d attente de nouveau message l aide de timeouts Cependant comme il n est pas possible de pr dire la dur e des op rations entreprises April n est pas adapt aux applications o le temps est une dimension critique Il est possible de d finir des procedure abstractions et des pattern abstractions Ces fonctionnalit s permettent respectivement de construire dynamiquement une nouvelle proc dure et un nouveau mod le de message Ainsi en se partageant des pattern abstractions les agents peuvent apprendre reconna tre de nouveaux types de messages ce qui revient a extraire de ces messages les valeurs des variables En partageant des procedure abstractions un agent peut ex cuter du code de mani re transparente l int rieur du code d un autre agent Par exemple consid rons un agent serveur qui fournit une correspondance entre le nom d un agent et ses comp tences Un autre agent peut lui envoyer ses propres crit res de choix qui permettent de faire le tri entre les r ponses possibles Chaque t che pl
24. besoin_info NOM INFO Nous utilisons ce lien s mantique dans le chapitre suivant et on pourra trou ver un exemple concret d utilisation dans la section 4 1 7 2 Cette solution est simple et fonctionnelle mais elle oblige conna tre au moment de la mise au point de l artifact la structuration de la base de croyances des agents De plus elle impose un fonctionnement tr s proc dural o pour d cider de la prochaine action r aliser agent a juste a consulter sa base de connaissances 3 4 3 4 2 Utilisation de Design to Criteria Pour palier les limitations du mod le pr c dent nous proposons une m thode qui permet aux agents d utiliser les possibilit s de raisonnement et d ordonnancement offerts par Design to Criteria d j pr sent dans la section 2 2 3 4 4 Design to Criteria prend en entr e un arbre de t ches exprim dans le formalisme de TAEMS Nous proposons donc une m thode permettant de traduire une instruc tion op ratoire exprim e dans notre langage base d alg bre de processus en un arbre TEMS Dans notre alg bre de processus les actions et perceptions sont des primitives atomiques et sans dur e La dur e des taches ex cut es par les artifacts apparait grace a la succession d une action et de la perception associ e L utilisation du timeout et de lattente entre une action et une perception permet d expliciter la dur e des t ches Dans TAEMS les m thodes repr sente
25. du FIG 3 6 Mode d emploi d un lave vaisselle prenant en compte l historique Pour notre exemple de mode d emploi d un lave vaisselle la figure 3 6 illustre le mode d emploi que nous obtenons en utilisant historique L instruction op ratoire est la suivante lave_vaisselle_historique llaver fin_lavage remettre_du_sel fin_remplissage lave vaisselle historique La r gle a_remettre_du_sel p_fin_remplissage gt activate laver deactivate remettre_du_sel permet de d sactiver le remplissage du sel et d autoriser de nouveau les lavages lorsque la toute derni re action a consist a remettre du sel Le permet d indiquer une correspondance avec la fin de l historique La r gle a_remettre_du_sel p_fin_ remplissage a_laver p_fin_lavage 10 gt deactivate laver activate remettre_du_sel permet quant elle de faire l inverse lorsque l on a d tect dix cycles de lavages apr s un remplis sage du sel Ce m canisme permet d introduire de mani re simple des boucles dans nos instructions op ra toires Nous tudions actuellement comment flexibiliser celui ci en ne conservant dans l historique que certaines informations ou pour pouvoir purger les parties les plus anciennes de I historique qui ne sont plus n cessaires Remarquons que l introduction de ce m canisme d inhibition de n uds dans I inst
26. es qui viennent un rapprochement d j amorc entre diff rentes communaut s C est par exemple le cas entre la communaut agent et la communaut compo sant Un agent peut tre constitu de plusieurs composants ou un composant peut disposer de capacit s cognitives Nous avons le sentiment que les r ponses que nous apportons pour les syst mes d agents avec nos travaux sur les artifacts se placent au bon niveau d abstraction pour pouvoir tre r utilis es et pour ajouter de l intelligence aux syst mes composants ou aux Web Services par exemple Un 7 4 Rapprochement avec d autres communaut s 125 rapprochement serait galement possible avec la communaut qui travaille sur les architectures diri g es par les mod les MDA MDE et qui uvre sur des sp cifications d claratives des syst mes Cette communaut utilise les mod les pour sp cifier s par ment l application et l architecture mat rielle qui va la supporter Le code final est obtenu de mani re automatique en mappant petit petit un mod le software sur un mod le hardware Le concept d artifact devrait galement pouvoir tre adapt cette approche pour obtenir des fonctionnalit s sym triques c t software permettant des raisonnements sur les mod les Le domaine des calculs intensifs sur grilles de calcul est galement un domaine dont les techniques de base sont matures d ploiement et quilibrage des calculs h t rog n it d
27. ga lement de g rer les d faillances mat rielles en red marrant les processus d un n ud d faillant sur un autre n ud 2 2 Travaux connexes 27 Ces syst mes sont tr s int ressants car ils ne requi rent aucune modification des applications et que la vue propos e l utilisateur est tr s simple Cependant les logiciels de clustering actuellement propos s ne sont pas tr s flexibles Ils tentent uniquement de faire de l quilibrage de charge pour que tous les processeurs soient utilis s de la m me mani re et sont incapables de g rer des ordon nancements plus complexes requis par exemple quand on veut donner des priorit s aux taches ou que Pon a des d lais respecter pour certaines t ches et pas pour d autres Les logiciels de clustering sont donc plut t handicapants pour nos syst mes dans lesquels les agents devraient pouvoir d cider eux m me du processeur sur lequel ils vont s ex cuter Nous ne pouvons pas encore utiliser nos sys t mes multi agents sur des grappes de serveurs mais nous aurons dans avenir la possibilit de le faire En effet les grappes sont g r es de mani re logicielle Certains projets sont m me accessibles de mani re totalement libres comme openMosix Buytaert 2005 qui est con u comme une extension du noyau Linux pour permettre d obtenir une image unique du syst me d exploitation sur un r seau de machines Single System Image ou SSI en anglais Nous pouvons d s
28. pr sent planifier dans nos travaux futurs l laboration d un logiciel hybride gestion de grappe syst me multi agent permettant de combiner les avantages des deux approches simplicit efficacit et robustesse des grappes d une part et gestion intelligente des ressources processeur adapt e aux syst mes multi agents d autre part Nous pr sentons dans la suite les deux biblioth ques les plus connues pour programmer des pro grammes parall les sur les machines multiprocesseurs et les grappes de serveurs Ce sont des biblio th ques standards qui sont port es sur la plupart des architectures MPI MPI signifie Message Passing Interface C est une biblioth que dans laquelle la m moire est dis tribu e et la communication entre les processus se fait par change de messages de mani re explicite dans les programmes Les deux primitives de base sont MPI_Send et MPI_Recv Elles per mettent respectivement d envoyer un message un ou plusieurs destinataires et d attendre la r ception d un message Cette structuration autour des messages chang s entre les entit s est tr s proche de nos syst mes multi agents o les agents ne communiquent entre eux que par messages et ne partagent pas de don n es En ce sens MPI pourrait tre vu comme un syst me simple mais robuste de gestion de systeme multi agent g rant le cycle de vie des agents le placement sur diff rents processeurs et assurant le passage de messages ent
29. re pr cise sur les instances des donn es en entr e Nous ne limiterons pas notre tude de l encapsulation des t ches de calcul aux probl mes difficiles Les probl mes plus faciles ont galement de l int r t par exemple pour contr ler de mani re intelligente des calculs scientifiques tr s volumineux 2 2 1 3 Utilisation d heuristiques Si un probl me peut tre exprim sous la forme de la recherche d un l ment maximisant ou minimisant une fonction dans un grand espace de recherche la seule m thode s re pour trouver le bon l ment consiste parcourir de mani re exhaustive l espace de recherche Ceci est inconcevable lorsque l espace de recherche est tr s grand 18 Chapitre 2 Contexte On essaye alors en utilisant les propri t s de l espace de recherche sp cifiques au probl me pos de trouver l l ment recherch en se rapprochant petit petit de lui partir d un l ment initial Si l heuristique est bien choisie la complexit moyenne peut ventuellement tre dans une classe inf rieure par exemple polyn miale au lieu d exponentielle celle de l algorithme qui explorerait l ensemble dans un ordre inappropri Cheeseman et al ont essay de donner une m thode pour d terminer o se trouvent les pro bl mes vraiment durs Cheeseman et al 1991 Ils ont d couvert que des probl mes comme la K colorabilit d un graphe ou le voyageur de commerc
30. rer l aspect situ des simulations Elle sp cifie la distance la cible qu il faut respecter avant de pouvoir r aliser une interaction les actions Ce sont les cons quences de l ex cution de l interaction Elles portent sur les pro pri t s des agents ou les agents eux m mes cr ation destruction Devigne et al 2005c s attaque principalement au probl me de la gestion d quipes pour les quelles un chef distribue des t ches aux autres membres de l quipe L autonomie des membres de l quipe s exprime par le fait que le chef ne conna t pas les actions atomiques pour atteindre un but Il poss de seulement la connaissance de t ches abstraites Il d l gue aux autres agents la r alisation de chacun des sous buts qu il aura d termin s Les agents pourront ainsi d terminer eux m me la meilleure strat gie pour mener bien leur mission Ils disposent tous pour cela d un moteur de pla nification en chainage arri re A tout moment le chef peut d cider de r affecter une nouvelle t che 11 un agent_ celle ci rempla ant le but pr c dent Leur autonomie est donc une autonomie de d cision dans le cadre donn par le chef de l quipe SimuLE Simulation Large chelle applique le mod le de IODA aux syst mes r actifs et s at tache particuli rement montrer son int r t dans les simulations tr s grand nombre d individus Le domaine d ap
31. s pour qu ils soient ais ment utilisables par les agents De plus d une mani re g n rale nous pensons qu il convient d essayer de ne conserver l in t rieur des agents que ce qui est du niveau agent Cela permet d en simplifier la programmation et d identifier plus clairement o il faut porter les efforts pour am liorer les performances des agents concernant la repr sentation des connaissances la prise de d cision le suivi de contextes ou le focus d attention rapide 3 6 Comparaison avec les objets et les composants Dans le but d claircir encore plus la distinction entre les diff rents types d entit s d un syst me nous tendons notre comparaison aux objets et aux composants La distinction entre agent et objet a d j clairement t d finie notamment dans Odell 2002 Jennings ef al 1998 Nous la r sumerons ainsi les objets font les choses gratuitement les agents le font pour de l argent Lorsque qu un objet A appelle une m thode sur un autre objet B c est l objet A qui dispose du contr le Dans le cas agent l agent A doit demander l agent B de r aliser une action Celui ci peut refuser s il ne voit aucun profit r aliser l action Les artifacts se rapprochent en cela des objets puisque ce sont les agents qui en ont le contr le Les artifacts ne peuvent pas refuser de r aliser une action 78 Chapitre 3 Des outils de calcul pour les agents Les
32. temps donn 3 Le nombre d agents et le nombre de t ches planifi es partir de la date courante Ces informations sont partag es entre tous les APRC intervalles r guliers ou sur demande de l un d eux Un agent peut demander tout moment son APRC s il lui serait favorable de migrer sur un autre processeur L APRC remet jour ses informations sur les autres processeurs et propose l agent de migrer sur le processeur qui dispose des meilleures mesures de charge l ordre de pr f rence tant l ordre dans lequel nous avons d fini les mesures L APRC peut galement prendre l initiative d indiquer un agent auquel il vient de refuser l ex cution d une t che qu un autre processeur moins charg pourrait l accueillir Cela sera fait uniquement si le taux de requ tes refus es pour cet agent d passe un seuil fix l avance Lorsqu un agent a migr il attend la confirmation de 1 APRC avant de poursuivre son ex cution tout comme nous l avons vu dans la section 4 1 4 1 lorsque nous parlions de la cr ation de nouveaux agents et de leur prise en compte dans l ordonnancement Un nouvel arrivant sur un processeur doit galement se synchroniser avec l horloge temps APRC de celui ci pour que les requ tes de t che qu il va effectuer l avenir soient correctement dat es Avec ce m canisme nous n avons donc pas besoin d horloge globale pour l ensemble des processe
33. tude 2 2 3 4 1 Agent 0 Agent 0 est le langage propos par Shoham en 1993 dans Shoham 1993 pour mettre en pratique ses id es sur la mani re de concevoir et d impl menter des agents Cet article souvent consid r comme celui ayant initi l tude de la programmation orient e agent propose d utiliser une extension de la logique pist mique standard pour d crire l tat mental de l agent et la th orie des actes de langage pour communiquer avec les autres agents Shoham pense que la programmation orient e agent doit tre vue comme une extension de la programmation orient e objet et que l agenttitude est dans la t te du programmeur Nous pensons au contraire qu il fait essayer de r ifier le concept d agent pour b n ficier des avantages du paradigme agent jusque dans la programmation Malgr cette diff rence de positionnement le langage propos par Shoham poss de des carac t ristiques int ressantes notamment pour la gestion du temps Il comporte des op rateurs pour les croyances les obligations et les comp tences des agents chacun tant temporellement situ Le temps est discr tis Du point de vue de l agent les actions ne s inscrivent pas dans la dur e Du point de vue pratique il faut qu elles durent moins longtemps que le pas de temps qui est d termin une fois pour toute pour une application donn e Il peut tr s bien tre fix 50ms comme plusieurs jours
34. 4 4 Algorithme interruptible 3 4 4 5 Algorithme anytime 3 5 M thodologie de mod lisation d une application avec des agents et des artifacts 3 5 1 Diff rences entre agent et artifact 3 5 2 Classement des entit s d une application 3 6 __ Comparaison avec les objets et les composants 3 7 Rapprochement avec les autres travaux de l quipe SMAC A a aa a Bw Bm a te a de DINAN im La gestion des ressources processeur 4 1 Gestion des ressources processeur avec des d lais respecter 4 1 1 Besoin d une entit g rant les ressources processeur 4 1 2 Un artifact de coordination pour le partage du processeur 4 1 3 Algorithme d ordonnancement 4 1 3 1 Propri t s n cessaires 4 1 3 2 Un algorithme qui r pond nos besoins x Table des mati res 4 1 3 2 1 Mod lisation 87 4 1 3 2 2 Pr paration de la r solution 88 4 1 3 2 3 R
35. C est l valuation qui fait des tr sors et des joyaux de toutes choses valu es Friedrich Nietzsche Ce chapitre est consacr la description de l impl mentation des propositions des chapitres pr c dents sur notre plate forme multi agents Cela nous permettra de d crire comment nous avons valu e nos propositions et quels sont les r sultats de cette valuation 5 1 Mise en uvre Nous avons mis en place nos artifacts de calcul et APRC d crits pr c demment dans la pla teforme multi agents d velopp e au sein de Thales Division A ronautique Celle ci est constitu e d ALBA une librairie g n rique pour la cr ation d agents mobiles en Prolog et de diff rentes autres biblioth ques pour mettre en uvre le mod le d agent choisi ainsi que les protocoles de communi cation entre les agents Nous d crivons dans les paragraphes suivants les principales caract ristiques d Alba le mod le d agent que nous utilisons actuellement et la mani re dont nous y avons int gr les artifacts 5 1 1 ALBA 5 1 1 1 Une plateforme pour Prolog La premi re exigence quand il a t question de d ployer une plateforme multi agents a t de pouvoir impl menter des agents en Prolog En effet il tait tr s important de pouvoir r utiliser l im portante base de code Prolog qui a t constitu e au fil des ann es de recherche dans le domaine de Intelligence Artificielle au sein de Thales 105 106 Chapitre 5
36. Les interactions ont une existence propre en dehors des agents qui les r alisent ou les subissent Leur r ification permet de les r utiliser dans diff rents contextes Il en est de m me avec les artifacts de calcul qui r ifient dans l environnement du syst me multi agent les outils de calcul utilis s par les agents pour atteindre leurs buts On note une grande grande similitude avec nos artifacts de calcul En effet on peut consid rer que dans IODA un agent qui ne peut rien effectuer est en quelque sorte un artifact Il est compl tement passif On retrouve dans ces travaux une classification en deux types d entit s que nous pouvons rappro cher de celle propos e dans cette th se Les agents anim s sont comparer aux agents d crits dans 80 Chapitre 3 Des outils de calcul pour les agents cette th se et les agents inanim s sont 4 comparer aux artifacts introduits pr c demment Nos agents sont des entit s autonomes cognitives et pro actives Ce sont les acteurs du syst me multi agent tout comme les agents anim s de IODA Les artifacts sont les objets du monde que peuvent utiliser les agents pour atteindre leurs buts Il en est de m me avec les objets inanim s de IODA Les agents inanim s peuvent subir des interactions mais sont incapables d en effectuer tandis que les agents anim s sont capables de subir et d effectuer des interactions Les agents inanim s sont les objets pr sents dans la simulation avec le
37. On crit f x O g x si et seulement s il existe des constances C et N telles que Va gt N f lt Clg x Ce qui signifie intuitivement que f ne cro t pas plus vite que g La classification que nous obtenons est la suivante notation complexit O 1 constante O log n logarithmique O nlog n parfois appel e lin arithmique O log n polylogarithmique O n lin aire O n quadratique O n polynomiale parfois g ometrique O c exponentielle O n factorielle Les algorithmes en O 1 ont un temps d ex cution qui est ind pendant de la taille des donn es Ils ne sont pas tr s courants mais on peut notamment noter que l algorithme d ordonnancement int gr dans le noyau de Linux est maintenant en O 1 ce qui lui permet de rester efficace sur des machines massivement parall les Les algorithmes logarithmiques ou lin aires sont consid r s comme facile ment exploitables Les difficult s commencent a apparaitre lorsque les algorithmes sont quadratiques ou polynomiaux Et les algorithmes exponentiels ou factoriels sont impraticables en dehors des ins tances de probl mes jouets ne contenant que quelques donn es La complexit peut tre calcul e dans le meilleur des cas ce qui a peu d int r t en moyenne ou au pire des cas La complexit au pire des cas permet d obtenir une borne sup rieure qui peut tre utilis e quand on
38. Organizations chapitre 4 CLAIM and SyMPA a programming environment for intelligent and mobile agents Springer Faure 1979 FAURE R 1979 Pr cis de recherche op rationnelle Dunod Ferber 1995 FERBER J 1995 Les Syst mes Multi Agents Vers une intelligence collective In terEditions Ferguson 1992 FERGUSON I A 1992 Touring machines Autonomous agents with attitudes Computer 25 5 51 55 Fisher et al 2005 FISHER M GABBAY D M et VILA L diteurs 2005 Handbook of Tem poral Reasoning in Artificial Intelligence Elsevier Fokkink 2000 FOKKINK W 2000 Introduction to Process Algebra Springer Verlag Foster et al 2004 FOSTER L JENNINGS N R et KESSELMAN C 2004 Brain meets brawn Why grid and agents need each other In AAMAS 04 Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems pages 8 15 Washington DC USA IEEE Computer Society Foster et al 2002 FOSTER I KESSELMAN C NICK J et TUECKE S 2002 The physiology of the grid An open grid services architecture for distributed systems integration Gamma et al 1993 GAMMA E HELM R JOHNSON R et VLISSIDES J 1993 Design pat terns Abstraction and reuse of object oriented design Lecture Notes in Computer Science 707 406 431 Garvey et Lesser 1996 GARVEY A et LESSER V R 1996 Design to time scheduling and any time algorithms SIGART Bul
39. agent Tous les messages arrivants de l ext rieur sont trait s par un aiguilleur qui est charg de dispatcher les messages aux bons FDR en fonction d un ensemble de r gles de grammaire qui peuvent prendre en compte l exp diteur la syntaxe et le contenu des messages entrants Si un message ne peut tre filtr par l aiguilleur il est automatiquement envoy au FDR par d faut Celui ci est principalement charg d identifier de nouveaux contextes et de g rer les messages inconnus Les FDR sont instanci s et d truits dynamiquement selon l volution du syst me Les r gles de grammaires de l aiguilleur et les mod les de FDR peuvent galement tre ajout s supprim s ou mo difi s pendant que l agent s ex cute permettant ainsi d adapter dynamiquement le comportement de P agent Ce mod le d agent propose une vision concurrente des diff rents contextes d ex cution ceci sans utiliser le m canisme des processus l gers Cela permet d viter l apparition d ind terminisme comme nous l avions voqu dans la section 2 2 2 1 1 5 1 Mise en ceuvre s Message i AAA Signal interne Aiguilleur R gles de grammaire E LE M moire P M moire Ae M moire Led LY lt gt locale O lt gt locale Q locale 9 D faut T FDR1 FH FDR2 gt 4 D faut FDR1 FDR2 4 7 SD M moire globale del agent le Horloge Timeout HHO a
40. agents d velopp e au sein de Thales Les exp rimentations que j ai men es sur la plateforme sont pr sent es Elles concernent l utilisation de notre artifact de coordination dans une application existante d velopp e par Thales Je montre que cela permet d am liorer le respect des ch ances Je montre galement comment notre artifact de coordination peut tre utilis en mode multi machine pour quilibrer la charge entre les diff rents processeurs disponibles Enfin les chapitres 6 et 7 concluent sur les r sultats de cette tude et indiquent quelles sont les nouvelles pistes aborder par la suite dans les trois directions suivantes gestion du temps dans les syst mes multi agents l volution du mod le d agent et la mani re avec laquelle les agents mani pulent les artifacts de calcul Chapitre 2 Contexte Concevez toujours une chose en la consi d rant dans un contexte plus large une chaise dans une pi ce une pi ce dans une maison une maison dans un quartier un quartier dans une ville Eliel Saarinen Nous d crivons dans ce chapitre les probl mes que pose la gestion du temps dans les syst mes multi agents L expos des principaux r sultats de la th orie de la complexit nous permettra de d finir de mani re plus formelle quelles sont les difficult s auxquelles nous avons faire face lorsque l on s int resse la r solution d un unique probl me Nous verrons que
41. algorithme renvoie une r ponse m me si le point fixe n a pas t atteint A cette r ponse est associ e une information sur l tat du calcul afin que l agent puisse d cider de la suite donner Cet tat peut prendre trois valeurs disponible le dernier calcul demand est termin en cours le calcul n est pas termin mais un minimum de temps processeur a t utilis pour garantir une qualit minimum de la solution 114 Chapitre 5 Mise en ceuvre et valuation satur dans le cas contraire Le mode d emploi devient alors le suivant OI2 stop WORK_OI add_constraint C syntax_error success O12 WORK_OI propagate T T T result E 1 Contrairement au premier cas l agent peut relancer le calcul m me sans avoir ajout de contrainte Pr c demment cette possibilit n tait pas n cessaire car le r sultat obtenu tait toujours le point fixe et donc relancer le calcul ne servirait rien Notons qu en analysant ce nouveau mode d emploi l agent peut d terminer que s il lance la r solution avec un contrat de T secondes il aura le r sultat dans au maximum T secondes La derni re caract ristique de I artifact est sa fonction Cela est sp cialement utile dans un syst me ouvert o il est n cessaire pour un agent de d couvrir les artifacts susceptibles de l aider r soudre son probl me Ce n est pas le type d utilisation dont nous avons
42. appeler et t t la liste de ses param tres Des r gles de congruence sont d finies pour exprimer la commutativit et la transitivit des dif f rents op rateurs de d finir le comportement de l instruction vide et de invocation d une autre instruction op ratoire DELLE T I AABT SA P TO Parl IL GP 0 1 1I 1 0 17 I T I I I T I D t1 tn 1 t1 01 tn Un si Gist T Il est possible de donner une s mantique op rationnelle ce langage Dans les r gles suivantes la notation I 2 T signifie que l tat de l instruction op ratoire I Z se transforme en l tat I T par Poccurrence de l acte d interaction 6 A La notation t t est utilis e pour indiquer la substitution de t par t dans la suite des instructions IL 2 VE sil z T PAR I I sil z I et I 27 1 ECH I UI il zI etI 251 LCH la I B al a a I ACT a 2m I I I E JE 1 COMP La r gle PAR sp cifie qu une seule instruction op ratoire est suivie un instant donn La r gle ECH d finit la s mantique du choix exclusif si J est ex cut e les choix l int rieur de J sont exclus La r gle LCH au contraire d finit le choix retard si l interaction 6 permet plusieurs choix est ex cut et le choix est retard une prochaine interaction La r gle ACT sp cifie que si a est la prochaine action ex cuter une sp cialisation a de a
43. artifacts se placent cependant un niveau d abstraction diff rent de celui des objets Les com posants se placent au m me niveau d abstraction que les artifacts et leur structuration se rapproche tr s fortement de celle des artifacts La figure 3 8 pr sente la structure d un composant ici un composant CORBA Interface Composant Facettes R ceptacles OFFERTS REQUIS _ Puits d v nements Sources d v nements Attributs FIG 3 8 Caract ristiques d un composant Un composant permet d encapsuler des traitements Il dispose d une enveloppe le conteneur fournissant un certain nombre de services de base comme les possibilit s de communication de s curit ou de persistance On retrouve cette enveloppe dans les artifacts et les artifacts de calcul Elle permet principalement les interactions avec les agents Et dans le cas des artifacts de calcul elle g re directement certaines actions comme la mise en pause ou le red marrage de l artifact qui sont des op rations de niveau syst me Les composants disposent de quatre types de ports Une facette est une interface fournie par un type de composant et qui est utilis e par des clients en mode synchrone Un r ceptacle est une interface utilis e par un type de composant en mode synchrone Un puits d v nement est une interface fournie par un type de composant et utilis e par ses clients en mode asynchrone
44. au point de programme complexes gr ce un agencement de traitements de base Pefficacit Le programmeur doit disposer de structures de donn es de biblioth ques et de langages permettant de cr er des programmes qui utilisent au mieux les ressources disponibles l ex cution la maintenabilit Les besoins qui ont conduit 4 la cr ation d un programme voluent Un programme doit donc pouvoir tre modifi apr s la mise en production initiale Cela concerne aussi bien la documentation du code en vue de la reprise par d autres programmeurs que la modification ou l ajout de fonctionnalit s la r utilisabilit Le d veloppement logiciel est une activit tr s chronophage Il faut le plus possible essayer de r utiliser ce qui a d j t d velopp dans des projets pr c dents la portabilit Cela concerne la possibilit d ex cuter un programme sur plusieurs types d ar chitectures mat rielles et logicielles diff rentes Ce point nous concerne dans son extension aux syst mes multi agents distribu s dans lesquels les agents se trouvant sur diff rentes architec tures doivent pouvoir communiquer en utilisant un langage commun la fiabilit Ce point est certainement un des plus importants Le d veloppement logiciel est un processus extr mement complexe soumis une quantit faramineuse d erreurs possibles Pour viter les bugs il faut fournir aux programmeurs des outils les contraignants
45. aupr s d une compagnie a rienne propos par Shoham Cela nous permettra d identifier les particularit s du langage La syntaxe utilis e est proche du Lisp On dispose d op rateurs pour les croyances B pour lV obligation OBL pour le choix DEC et pour les comp tences CAN Tous ces op rateurs sont tem poralis s par exemple CAN action repr sente le fait que l agent a est capable de r aliser action au temps t 2 2 Travaux connexes 39 On peut galement utiliser des actions priv es ou de communication qui sont plac es dans l agenda de l agent et ex cut es automatiquement au bon moment DO t action permet de r aliser action au temps t INFORM t a fact permet d informer l agent a du fait fact au temps t REQUEST t a action permet de demander au temps t l agent a de r aliser action On peut galement d crire des r gles d engagement sous cette forme COMMIT msg cond mental cond action x o msg cond est une condition sur les messages entrants mental cond une condition sur l tat mental de l agent et action une liste d actions r aliser si les conditions sont v rifi es Un programme Agent 0 est en d finitive constitu de la liste des comp tences de l agent de ses croyances initiales et de la liste de ses r gles d engagement Nous d finissons maintenant 3 macros qui seront utilis es dans la suite de l exemple issue_bp pass flightnum
46. c est le syst me d exploitation qui d cide quand attribuer le processeur un autre programme Cette m thode permet tout comme le multi t che coop ratif de donner Putilisateur l illusion de plusieurs programmes s ex cutant en m me temps Il est important de noter que cette illusion est maintenant propag e jusqu a la program mation des diff rents programmes pendant la phase de programmation on n a plus a se soucier du fait qu il y aura d autres programmes qui vont s ex cuter en m me temps que celui qu on est en train de cr er Le couplage entre les programmes est ainsi tr s fortement diminu et la robustesse est accrue car un processus ne peut plus bloquer toute la machine et emp cher les autres de s ex cuter L illusion de programmes s ex cutant en parall le est obtenue en attribuant 4 chaque processus de tout petits quanta de temps Le passage r gulier d un processus l autre permet d assurer une certaine r activit chacun des programmes Le multi t che pr emptif peut tre utilis pour parall liser l ex cution de plusieurs programmes ind pendants mais aussi pour parall liser l ex cution d un seul programme On utilise pour cela la technologie des processus l gers threads Chaque processus l ger est un fil d ex cution qui peut s ex cuter en parall le des autres tout comme avec les processus normaux La diff rence se situe au niveau de l acc s a la m moire deux proc
47. celle propos e par Russell et Whitehead dans Principia Mathematica Malheureusement l article que Newell et Simon avaient fait co sign par leur programme Logic Theorist n a pas t accept par les diteurs du Journal of Symbolic Logic Cela montre bien l ambigu t li e au choix de l expression Intelligence Artificielle Beaucoup pensent que rationalit computationelle aurait t un meilleur choix Quoi qu il en soit la communaut IA s est ensuite moins pr occup e du choix des termes des implications philosophiques des r sultats possibles et s est structur e autour de la r solution de sous probl mes la planification l apprentissage automatique le diagnostic et les syst mes experts les jeux checs jeux de cartes jeux de mots jeu de go la reconnaissance de formes et le traitement automatique des langues Les r sultats de PIA ont t fluctuants tant t extraordinaires avec les premiers syst mes d aide a la r solution de probl mes math matiques de reconnaissance de la parole de r solution de puzzles tant t d cevants lorsque les chercheurs s apercevaient qu ils ne pouvaient r soudre des probl mes que dans des micro mondes tant la combinatoire est importante dans des mondes r els Depuis le milieu des ann es 1990 certainement gr ce des r sultats convaincants en planifica tion notamment un regain d int r t est apparu pour la constitution d un
48. complet des agents 2 2 3 1 2 Raisonnement sur des dur es incertaines De nombreux travaux ont port sur l incertain dans les raisonnements des agents et en particulier sur les dur es incertaines des calculs Nous pr sentons ici les travaux dont la philosophie se rapproche le plus de la n tre Horvitz 1990 et Horvitz et Rutledge 1991 traitent du probl me de l action dans l incertain dans un cadre o l utilit de l action d pend du temps Ils ont exp riment leur programme Protos sur une application m dicale simplifi e Consid rons le cas o le programme doit recommander un traitement pour un patient qui montre soudainement une pression sanguine extr mement basse et de la tachycardie Nous consid rons que le probl me a t r duit deux syndromes exclusifs d faillance cardiaque congestive H1 et hypovol mie H2 Bien que ces deux syndromes aient les m mes symp tomes les traitements pour chacun d eux entrent en conflit Le traitement pour l hypovol mie A2 consiste injecter au patient du liquide physiologique pour faire revenir le volume du sans une va leur normale Au contraire le traitement pour la d faillance cardiaque congestive consiste r duire la quantit de liquide dans le corps en administrant un diur tique Bien videmment une erreur dans la d cision de traitement r aliser met la vie du patient en jeu Protos prend la d cision en fonction des di
49. d ordonnancement 4 1 3 1 Propri t s n cessaires L ordonnanceur dont nous avons besoin doit disposer de propri t s particuli res En se pla ant au dessus de celui du syst me d exploitation il peut prendre en compte le fait qu son niveau plusieurs t ches peuvent s ex cuter en parall le Notamment il doit prendre en compte de mani re particuli re les agents qui doivent toujours tre consid r s comme actifs pour conserver leur propri t d extraver sion Il doit pouvoir g rer des dates limites tout en tant facilement extensible d autres contraintes temporelles Contrairement ce que font la plupart des ordonnanceurs utilis s pour g rer des dates limites nous consid rons qu il est int ressant de commencer les t ches au plus t t En effet si nous consid rons des algorithmes incr mentaux ou dont le temps d ex cution est tr s variable il est int ressant pour l agent de commencer ex cuter ses t ches de calcul au plus t t et ainsi avoir le plus t t possible des informations quant au comportement de l algorithme convergence lente ou rapide par exemple Le comportement d un ordonnanceur comme EDF Liu et Layland 1973 qui va ex cuter enti re ment la t che dont la date limite est la plus proche puis enti rement la t che suivante n est notamment pas adapt la r solution d un m me probl me par diff rents artifacts avec diff rentes heuristiques Dans ce gen
50. d une perception quelconque pour z ro ou plusieurs occurences de ce qui pr c de pour z ro ou une occurence de ce qui pr c de pour une ou plusieurs occurences de ce qui pr c de n pour une r p tition n fois de ce qui pr c de pour la succession pour le choix pour une correspondance avec le d but de l historique pour une correspondance avec la fin de I historique Au moment de chaque transition dans l instruction op ratoire les conditions pour chacun des n uds sont valu es L valuation est faite en commen ant par la fin de l historique pour identifier V emplacement le plus r cent de la condition Lorsqu une condition est valid e les actions compos es correspondantes sont ex cut es On dispose de deux actions primitives qu il est possible d utiliser pour masquer deactivate ou r activer activate des actions ou perceptions possibles C est Pinstruction op ratoire finalement obtenue apr s application de toutes les r gles qui est utilis e par l agent pour prendre la d cision de la conduite tenir dans l tat courant regular expression ou regex en anglais 68 Chapitre 3 Des outils de calcul pour les agents a_remplir_sel p_fin_remplissage a_laver p_fin_lavage 10 gt a_remplir_sel p_fin_remplissage gt A r activate laver deactivate remettre_du_sel deactivate laver activate remettre_du_sel Remettre
51. dans I orga nisation Il permet de contraindre ce que l agent peut faire dans l organisation Il peut tre vu comme une interface fronti re entre l agent et l environnement Les artifacts de ressource R sont des moyens de m diation d acc s aux ressources physiques ou pour donner une existence une partie de l environnement du SMA correspondant une ressource partageable Ce type d artifact est important pour apporter au niveau d abstraction des agents toutes les entit s physiques et de calcul qui peuvent tre utilis es par les agents Les artifacts de ressource remplacent avantageusement les agents wrappers couramment utilis s pour r soudre ce probl me 3 3 Les artifacts de calcul Je pr sente maintenant la notion d artifact de calcul que j introduis comme une sp cialisation de la notion d artifact Contrairement aux premiers travaux de l quipe de Bologne sur les artifacts qui portaient principalement sur les possibilit s de coordination entre agents au travers des artifacts je m int resse dans cette partie aux artifacts comme des outils de calculs disponibles dans l environne ment et utilis s par les agents pour atteindre leurs buts 3 3 1 Utilit Les artifacts de calcul vont nous permettre d externaliser les t ches de calcul des agents pour qu ils puissent conserver un comportement extraverti Nous r ifions la notion d outil de calcul dans le but de d finir des m canismes g
52. de temps en temps Les syst mes de traitement de flux vid o sont par exemple souvent consid r s comme des syst mes temps r el mous car si le traitement d une image prend trop de temps la sui vante est simplement saut e pour rattraper le retard Ce comportement est acceptable si la fr quence des images saut es n est pas trop importante La gestion du respect des dates limites assign es aux t ches est d volue un ordonnanceur Ils peuvent tre class s de diff rentes mani res Tout d abord ils peuvent fonctionner en ligne online ou hors ligne offline On utilise un algorithme hors ligne lorsque l ensemble des processus qui vont tourner sur le syst me est fixe et que les propri t s des traitements effectu s par les processus sont galement fixes Ainsi en sachant que l on aura n processus g rer avec pour chaque processus un besoin p riodique de p riode P de la quantit W de ressources processeur l ordonnanceur dispose de toutes les informations n cessaires pour calculer et optimiser un ordonnancement qui convient l ex cution l ordonnanceur ne fait qu utiliser les informations pr calcul es pour d terminer quand 24 Chapitre 2 Contexte lancer ou stopper les processus Ce type de technique est utilis dans les syst mes extr mement cri tiques car on garantit hors ligne qu il n y aura pas de mauvaise surprise l ex cution on prouve que le syst me respectera les d lais
53. des couples temps de calcul qualit dans R ou 0 1 L algorithmique anytime semble r soudre bon nombre des probl mes pos s par les algorithmes lorsqu ils sont mis en pratique Il y a cependant deux probl mes qui emp chent d utiliser de mani re syst matique des algorithmes anytime trouver un algorithme incr mental et interruptible pour un probl me donn n est pas toujours tr s ais et lorsque l on a trouv l algorithme c est la d termination du crit re de qualit et du profil de performance qui pose probl me Delhay 20001 Qualit 0 60 0 55 0 50 0 45 0 40 0 35 0 30 FIG 2 2 Qualit de l algorithme du voyageur de commerce construit avec la m thode statis tique Grass 1996 La figure 2 2 nous permet d illustrer les difficult s pos es par ce dernier point Elle montre la carte de qualit obtenue en utilisant une m thode statistique sur le probl me du voyageur de com merce Le crit re de qualit est le rapport du co t du chemin optimal sur le co t du chemin courant 2 2 Travaux connexes 21 Le probl me provient du choix des donn es en entr e utilis es pour cette phase d apprentissage des performances de l algorithme Delhay 2000 montre que les m thodes statistiques sont rarement la bonne m thode pour obtenir un profil de performance qui pr disent efficacement un comport
54. des traitements internes quand bon lui semble Il faut seulement que ceux ci ne soient pas visibles de l ext rieur et que l artifact puisse continuer r pondre imm diatement aux commandes qui lui sont envoy es L entit est elle extravertie Si l entit que nous avons identifi e a besoin d tre r guli rement l coute du monde ext rieur on la concevra plut t comme un agent Si elle doit r aliser des t ches longues elle seront d l gu es des artifacts de calcul pour lui permettre de rester extravertie Au contraire un artifact est une entit introvertie qui r alise enti rement la t che qu on lui a donn e avant de pouvoir dialoguer de nouveau Cet aspect introverti appara t nettement dans le mode d emploi formel que l on doit d crire pour tout artifact comme une succession d actions de r alisation d action et d envoi l agent d une perception indiquant que la t che est termin e Le comportement de l entit est il dirig par des buts Si c est le cas l entit sera un agent De plus nous consid rons qu id alement les agents doivent avoir une repr sentation explicite de leurs buts Si cette repr sentation explicite des buts convient il 3 6 Comparaison avec les objets et les composants 17 est clair que l entit sera un agent Les artifacts seront au contraire orient service Ils n ont aucun but explicite et se contentent de r aliser docilement les t ches q
55. el ne soit pas celui nonc par le mod le de fonctionnement ventuel dont il dispose Les possibilit s d interaction avec un artifact sont diff rentes de celles possibles avec un agent voire augment es Notons par exemple que l autonomie des agents ne permet pas de les mettre en pause de ext rieur alors que cela devient possible avec les artifacts D autres propri t s diff rencient les agents des artifacts Elles d coulent pour la plupart de la distinction autonome pas autonome ci dessus C est le cas de la pro activit qui est une autre pro pri t g n ralement attribu e aux agents Elle est la capacit d cider seul d initier un comportement particulier prise d initiative Ce nouveau comportement est d cid en interne par l expiration d un timeout ou par un m canisme de d lib ration mais il ne peut tre pr vu de l ext rieur Il n y a donc que les entit s autonomes qui peuvent tre pro actives Un artifact ne peut pas d s lors tre pro actif et ceci d coule de la d finition de l autonomie que nous utilisons La r activit est une autre propri t attribu e aux agents Elle est utilis e dans deux sens diff rents Un agent est dit r actif quand il a un comportement du type stimulus gt r ponse C est le comporte ment des objets de la POO Les artifacts sont dans ce sens hyper r actifs une action lanc e est automatiquement ex cut e Les agents que nous concevons sont plu
56. emploi d un algorithme pour lequel on ne connait pas le temps d ex cution est le suivant black_box_algorithm start_computation INPUT_DATA finished RESULT error ERROR_INFO stop_computation computation_stopped pause_restart black _box_ algorithm pause _restart i pause paused restart restarted pause_computation paused restart_computation restarted pause_restart test_finished test_finished finished RESULT error ERROR_INFO computation_stopped Tout d abord l agent n a qu une action possible d marrer le calcul Il le fait quand bon lui semble Ensuite il sait qu il recevra soit le r sultat du calcul soit un rapport d erreur Aucun d lai n est garanti pour cela A tout moment il a la possibilit d arr ter le calcul ou d effectuer des cycles de mise en pause et de red marrage selon l un des deux modes propos s Quand un calcul est termin on reboucle pour pouvoir en relancer un nouveau 3 4 Le langage de mode d emploi des artifacts 73 Lutilisation de test_finished permet de garantir que l on ne pourra plus tenter de mettre en pause un calcul d j termin Remarquons que nous faisons l hypoth se que pause est imm diate ment suivi de paused sans que finished ou error puisse se produire entre les deux 3 4 4 2 Algorithme dur e d ex cution connue On ajoute juste l instruction op r
57. es La r gle suivante indique par exemple qu une nouvelle requ te de conversation 36 Chapitre 2 Contexte est servie s il existe une classe de conversation qui accepte le premier message dans la file d attente de l agent def continuation rule cont 1 input queue test lambda queue if queue exists conv class initially accepting first queue nil Chaque instance de conversation poss de un identifiant COOL permet Putilisation de multiples instances d automates simultan ment dans un agent Quand un agent re oit un message destin une instance dont l identifiant est inconnu une instance de la bonne classe de conversation est cr e la classe utilis e tant indiqu e dans chaque message Les transitions des automates ne sont activ es que par r ception de message sauf l initiation des conversations pour pouvoir envoyer le premier message Les syst mes r alis s avec COOL sont donc uniquement r actifs 2 2 3 3 2 AgenTalk AgenTalk Kuwabara et al 1995 poursuit le m me but que COOL fournir un langage de des cription et d impl mentation des protocoles de communicatoin entre les agents Il s en diff rencie en apportant un m canisme d h ritage permettant de d crire de mani re incr mentale ces protocoles AgenTalk est crit en Common Lisp Chaque protocole est d fini d un point de vue local a chaque agent par un automate tendu automate simple tendu pour po
58. eu besoin dans l application de localisation de bateaux et nous n avons donc pas eu a sp cifier la fonction de nos artifacts L approche agent artifact que nous avons utilis e dans cette application a permis de r duire consi d rablement la difficult de la programmation des agents et donc d autoriser une d lib ration beau coup plus pouss e que lorsque le calcul tait partie int grante de l agent La prise en compte des contraintes temporelles s en est trouv e galement tr s simplifi e 5 4 Exp rimentations 5 4 1 Avec et sans APRC Nous avons lanc des exp riences dans une version simplifi e d Interloc pour exhiber les b n fices li s Pusage de l APRC dans cette application Nous avons compar les r sultats obtenus dans les cas suivants quand aucun m canisme de coordination n est utilis pour g rer les ressources processeur allou es aux artifacts de calcul Il n y a aucune garantie que le calcul pour une mesure sera termin avant qu une nouvelle mesure arrive Quand c est le cas l artifact continue son calcul jusqu a ce que le contrat de temps ait expir La nouvelle mesure est ignor e quand les services de APRC sont utilis s Quand 1 APRC accepte d ordonnancer une t che il garantit que celle ci sera termin e avant l arriv e de la prochaine mesure Si la nouvelle t che ne peut tre ins r e dans l ordonnancement la mesure correspondante est ignor e Nous calculon
59. ex traversion et de conscience du temps en d l guant leurs d lib rations longues des outils de calculs 119 120 Chapitre 6 Conclusion d di s Ceux ci disposent de modes d emploi qui permettent aux agents de les instancier et de contr ler l ex cution des algorithmes qu ils encapsulent Les modes d emploi d crivent galement les pro pri t s temporelles des algorithmes utilis s ce qui peut permettre aux agents de raisonner dessus Jal galement introduit un m canisme de conversion d un mode d emploi d artifact de calcul vers une structure de t che T MS qui propose d autres types de raisonnements Le formalisme base d alg bre de processus propos dans Omicini ef al 2004 est extensible et nous avons propos des extensions suffisantes pour g rer le temps dans cette tude Nous propo sons galement une extension qui autorise l utilisation d informations sur l historique des actions et perceptions li es au mode d emploi pour activer ou d sactiver des branches de celui ci Nous avons cependant remarqu que les possibilit s d extension sont limit es et qu il sera difficile de plus flexi biliser ce langage et de permettre en m me temps des raisonnements plus fins De plus un mode d emploi d crit dans ce langage n est pas directement compr hensible par l agent et l on doit four nir un lien s mantique entre les donn es du mode d emploi et la base de connai
60. ex cution peuvent tre longs et variables En effet des agents qui mettraient en ceuvre ce type d algorithmes sans outils sp cifiques pourraient perdre conscience et seraient incapables de rester en phase avec leur environnement Pour r soudre ces probl mes nous proposons d introduire dans les syst mes multi agents une nouvelle classe d entit s qui jouent le r le d outils de calcul que les agents peuvent utiliser pour externaliser leurs calculs longs et ainsi rester l coute de leur environnement Nous tendons pour cela le concept d artifact propos par Omicini Ricci et Viroli en 2004 Nous proposons galement utiliser un artifact de coordination qui permet d attribuer les ressources processeur en fonction des contraintes de chaque agent Lorsque cet artifact ne peut respecter toutes les contraintes pos es les agents peuvent par son interm diaire r soudre les conflits en sacrifiant une partie des ressources qui leur ont t attribu es Les propositions ont t mises en ceuvre sur la plateforme de d veloppement d agents ALBA mise en place au sein de Thales Division A ronautique et valu es en r impl mentant une application existante Mots cl s Syst mes multi agents partage de processeur ordonnancement interaction coordination sacrifice artifacts alg bre de processus Abstract In this thesis we raise the problem of meeting deadlines in cognitive multi agent systems Time management sys
61. fourni par l quipe italienne Il est possible de palier quelques uns d entre eux gr ce aux possibilit s d extension faciles mettre en uvre dans les alg bres de processus C est ce que nous d crivons dans cette section Nous terminons en d crivant les fonctionnalit s plus difficiles mettre en place dans le mod le actuel 3 4 3 1 L attente Comme nous le verrons dans le chapitre suivant quand nous voudrons utiliser plusieurs artifacts sur le m me processeur nous avons besoin de pouvoir mettre en pause et red marrer les artifacts aux limites d intervalles qui seront donn s par un ordonnanceur La gestion des timeouts d crite pr c demment signifie intuitivement que les agents ont une action r aliser ou qu une perception arrivera avant une date donn e Cela peut permettre d indiquer l agent de mettre en pause artifact avant la fin de l intervalle qui lui est imparti Nous avons aussi besoin de la possibilit d indiquer un agent qu il doit faire une action apr s une date donn e Tout comme pour le timeout nous tendons donc la d finition d une instruction avec la nouvelle instruction atomique W n et nous ajoutons deux r gles op rationnelles I W n W n I si W n m I sin gt m_ W T PASS Wet eT sin gt m_ W T EXP La r gle W T PASS g re le passage du temps pendant que l attente n est pas finie La r gle W T EXP g re l expiration du d lai impos avant de
62. instance NP les probl mes de d cision pour lesquels la r ponse oui peut tre d cid e par un algorithme non d terministe en un temps po lynomial par rapport la taille de l instance PSPACE les probl mes d cidables par un algorithme d terministe en es pace polynomial par rapport la taille de son instance NPSPACE les probl mes d cidables par un algorithme non d terministe en espace polynomial par rapport la taille de son instance EXPTIME les probl mes d cidables par un algorithme d terministe en temps exponentiel par rapport la taille de son instance Nous connaissons un certain nombre de relations entre ces ensembles Elles sont r sum es ici LCNLCPCNPCPSPACE NPSPACE Le probl me toujours irr solu actuellement est de d terminer si P NP Pour l instant on consid re que ce n est pas le cas Nous verrons dans les sections suivantes que beaucoup d efforts sont faits pour pouvoir trouver des solutions au probl mes de la classe NP Cependant notons que ce ne sont pas les seuls probl mes qui posent des difficult s de gestion du temps D un certain point de vue la gestion par un agent de l ex cution de calculs polynomiaux sur de tr s grands ensembles de donn es n est pas tr s diff rente de l utilisation d un algorithme exponentiel sur un probl me de petite taille Dans les deux cas la dur e d ex cution peut tre longue et difficile estimer de mani
63. la date limite DL On parlera galement pour ET d nergie de calcul totale attribuer la t che i On consid re n requ tes dont les dates limites sont tri es par ordre croissant DL 1 gt DL 1 lt i lt n 1 On obtient n intervalles To DL1 DL DL DIn 1 DL avec To la date de d but de l ordonnancement On consid re galement un nombre nb_agents fixe d agents actifs en permanence 88 Chapitre 4 La gestion des ressources processeur Nous voulons respecter les dates limites associ es chaque t che pour le intervalle le but est donc de terminer la t che avant la fin de l intervalle Nous voulons aussi donner le plus possible de temps processeur aux t ches 1 n et ceci le plus t t possible dans l intervalle On partitionne l intervalle consid r en sous intervalles correspondants toutes les possibilit s de faire tourner la t che i en parall le d une ou plusieurs autres des t ches i 1 n Pour le intervalle il y a 2 sous intervalles On ordonne les sous intervalles par ordre d croissant du nombre de t ches en faisant partie Pour un sous intervalle comportant T t ches chaque t che dispose d une part P de la puissance processeur disponible gale le 1 tant pr sent pour prendre en compte 1 14 T nb_agents l utilisation processeur de l APRC Utilisation processeur 100 APRC APRC Agent Agent Artifa
64. les deux op rateurs de chemin suivants Ap pest vrai dans tous les chemins temporels commen ant dans l tat courant Ep il existe un chemin temporel commen ant dans l tat courant dans lequel p est vrai Dans CTL les op rateurs doivent tre group s par deux un op rateur de chemin et un op rateur d tat Cette contrainte est relach e dans CTL on peut mixer les op rateurs comme on veut CTL et LTL sont des sous ensembles de CTL Plus r cemment un nouveau type de logique temporelle a t d finie par Alur Henzinger et Kup ferman les Alternating time Temporal Logics Alur ef al 1998 ATL est interpr t sur des struc tures de jeux concurrents mettant en jeu un ensemble X de joueurs On dispose d un nouvel op rateur lt P gt gt avec P C Y Ce nouvel op rateur g n ralise les op rateurs de chemin de CTL lt lt 0 gt correspond l op rateur A et lt X gt gt correspond l op rateur E Enfin on peut citer d autres logiques bas es sur les intervalles plut t que sur des points C est le cas d Interval Temporal Logic ITL propos dans Moszkowski 1986 Dans ITL un intervalle est constitu d une s quence potentiellement infinie d tats Les logiques temporelles sont principalement utilis es dans le cadre de la v rification formelle des syst mes Elles ne peuvent g n ralement pas tre utilis es pour programmer le comportement
65. les m mes processus qui sont vinc s sans m me en tre avertis Cela n est pas satisfaisant lorsque les applications mettent en jeu des agents intelligents autonomes 2 2 2 1 3 Les processeurs multi c urs Nous mentionnons ici les processeurs multi c urs car ceux ci vont devenir de plus en plus pr pond rants l avenir dans les machines de bureau Nous en sommes actuellement deux ou quatre c urs par processeur et les fondeurs comme Intel parlent de 40 80 voire 100 c urs par processeur d ici une dizaine d ann es Leur architecture permet d ex cuter en parall le au moins un processus l ger sur chacun des c urs En th orie il n y a pas besoin de modifier les applications pour b n ficier du parall lisme apport par ces processeurs En pratique les applications actuelles n utilisent pour la plupart les pro cessus l gers que pour assurer la r activit de l interface graphique pendant que les calculs longs sont 26 Chapitre 2 Contexte r alis s par un seul d entre eux Les gains n apparaissent donc pour l instant que lorsque l on utilise en m me temps plusieurs applications gourmandes en temps processeur Pour b n ficier pleinement de la puissance de ces processeurs l avenir il faudra revoir l architecture de toutes les applications pour que les calculs longs soient r alis s par un nombre variable de processus l gers en fonction du nombre de c urs disponibles sur la machine Or nous
66. m thodes pour allier les avantages des deux approches autonomie des agents et maturit des composants par ex Lacouture et Aniort 2006 Cependant les sp cifications qui accompagnent un composant portent principalement sur les noms et param tres des appels de m thode sans donner un mode d emploi qui indiquerait l agent quel encha nement utiliser pour atteindre ses buts Ces sp cifications tr s bas niveau ne permettent pas non plus de d duire les propri t s temporelles des fonctionnalit s du composant Voir section 2 1 1 pour la d finition pr cise que nous donnons ce terme 3 1 Position du probl me 51 Le probl me de la r activit au sens de la prise en compte temps des changements dans l environnement tout en ayant des raisonnements long terme a d j t trait Nous avons no tamment pr sent dans la section 2 2 3 2 les principaux mod les couches propos s InTeRRaP et Touring Machines Nous rappelons que ces mod les pr sentent chacun trois couches qui inter agissent entre elles pour d cider de la prochaine action a r aliser D autres mod les ont t galement propos s pour combiner des capacit s cognitives et r actives comme Guessoum et Dojat 1996 ou Bussman et Demazeau 1994 Tous ces mod les permettent de trouver un compromis entre les r ac tions de type r flexe et les r actions d lib
67. n raux d utilisation de tels outils de r duire le foss qui existe entre les concepts et l impl mentation et enfin de pouvoir permettre la r utilisation des outils de calculs ainsi d finis dans diff rents contextes SUn agent wrapper encapsule l acc s un syst me logiciel non agent un SGBDR par exemple pour qu il soit accessible pour les entit s du SMA comme s il faisait partie int grante de celui ci 58 Chapitre 3 Des outils de calcul pour les agents 3 3 2 D finition Un artifact de calcul est un artifact charg d encapsuler l ex cution d un algorithme au sens o nous l avons d fini dans la section 2 2 1 1 Un artifact de calcul dispose au minimum des actions suivantes start_computation DATA qui permet de d marrer une t che de calcul stop_computation qui permet de stopper la t che de calcul en cours pause_computat ion qui permet de mettre en pause la t che de calcul en cours resume _computation qui permet de red marrer la t che de calcul o elle s tait arr t e lors de l appel pause _computation pause qui permet de mettre en pause l artifact resume qui permet de r veiller I artifact Nous faisons une distinction entre pause et pause_comput ation ainsi qu entre resume et resume_computation pause et resume sont des op rations qui peuvent tre trait es au niveau syst me sans qu il y ait besoin que artifact s en rende compte ta
68. p riode de temps entre deux mises en pause 4 1 Gestion des ressources processeur avec des d lais a respecter 85 4 1 Gestion des ressources processeur avec des d lais respecter Nous consid rons dans cette section que les agents d coupent les traitements aux dur es ind ter min es qu ils d l guent aux artifacts en t ches voir d finition 4 3 A notre niveau nous connaissons donc pour chaque tache r alis e par les artifacts la dur e exacte en temps artifact qui sera n cessaire Nous consid rons galement qu a chaque tache est associ e une date limite donn e en temps APRC a laquelle elle doit tre termin e Les dates limites concernent uniquement les calculs r alis s par les artifacts les calculs r alis s en interne par les agents n ont aucune contrainte temporelle a respecter 4 1 1 Besoin d une entit g rant les ressources processeur Les SMA tels que nous les avons d crits dans le chapitre pr c dent sont uniquement constitu s d agent et d artifacts de calcul Chaque agent tant autonome il peut prendre tout moment la d cision de faire effectuer une t che de calcul un de ses artifacts Si les agents ne disposent pas de moyens pour coordonner leur utilisation du processeur ils n arriveront pas respecter leurs d lais sur les t ches de calcul Le seul moyen d assurer que les agents pourront tenir leurs d lais est de calculer un ordonnance ment pour l ensemb
69. palier ces difficult s Nous les d taillons dans la section 2 2 1 Par exemple on peut tenter de trouver un algorithme incr mental pour notre probl me Celui ci sera plus facilement int grable dans un SMA qu un algorithme non incr mental Cependant les algorithmes de PIA sont la plupart du temps assez complexes et il n est pas toujours possible d en am liorer les propri t s temporelles facilement Nous voulons donc pouvoir int grer dans nos SMA les algorithmes issus de VIA tels quels L ex cution par les agents d algorithmes ayant des dur es d ex cution longues va l encontre du principe d extraversion d fini plus haut Les agents deviennent plut t introvertis ils se remettent en phase avec leur environnement une fois leurs calculs termin s En se comportant de cette mani re un agent risque par exemple de continuer un long calcul malgr le fait qu un autre agent lui ait envoy un message lui indiquant que le calcul est devenu inutile La dur e d ex cution d un algorithme tant une notion relative nous consid rerons qu un algorithme a une dur e d ex cution longue lorsqu elle d passe la dur e s parant deux v nements qu un agent doit prendre en compte pour conserver un comportement extraverti l agent le programmeur ne peut plus dans ce cas n gliger le temps pris par Pex cution de l algorithme consid r Il devra disposer d un moyen pour prendre en compte le nouvel v nement to
70. par exemple fournir des moyens pour lancer un agent sur une machine distante ou de faire migrer un agent d j d marr sur une autre machine des moyens pour mesurer la charge d un processeur et avertir un agent qu il pourrait disposer de plus de ressources de calcul sur une autre machine 2 1 4 Mod le des applications vis es Nous donnons dans cette section un mod le d application qui r sume les objectifs pr c demment cit s Nous donnons galement la liste des contraintes suppl mentaires que nous avons utilis es dans le cadre de cette tude Nous voulons impl menter ou r impl menter des applications avec le paradigme agent Il faudra permettre l int gration de code h rit dans les syst mes multi agents Les actions que les agents ont a r aliser peuvent tre r duites des t ches de calcul Les agents ne partagent pas de m moire et ne communiquent entre eux que par change de mes sages Ils doivent tre capables de g rer diff rents contextes simultan ment Ceux ci peuvent tre de deux types contexte de dialogue avec un autre agent ou contexte d ex cution d un calcul Les t ches de calcul doivent pouvoir encapsuler du code h rit aux propri t s temporelles plus ou moins bonnes et l agent doit tre capable de b n ficier au mieux des propri t s temporelles des algorithmes dont il dispose pour r aliser ses t ches de calcul Nos syst mes multi agents doivent fonctionner sur le
71. par les agents nous ne nous int ressons pas aux cas o les diff rents algorithmes auraient besoin de donn es calcul es par les autres et donc auraient besoin d interagir directement Les seuls cas qui nous int ressent sont les suivants les agents r alisent des t ches de calcul ind pendantes les agents r alisent des t ches de calcul qui d pendent les unes des autres mais les d pendances sont g r es au niveau agent dans le plan de l agent ou au niveau du SMA gr ce aux interactions entre les agents les agents utilisent diff rentes heuristiques pour r soudre un unique probl me mais les heuris tiques fonctionnent ind pendamment les unes des autres 2 2 Travaux connexes 2 2 1 La gestion du temps d ex cution des algorithmes 2 2 1 1 Algorithmes Le mot algorithme a t introduit par le moine Abelard de Bath par r f rence au nom du math ma ticien perse Abou Jafar Muhammad Ibn Musa al Khuwarizmi qui au neuvi me si cle crivit le pre mier ouvrage syst matique sur la solution des quations lin aires et quadratiques R tro activement on consid re que c est la m thode d Euclide pour d terminer le plus grand commun diviseur d entiers naturels qui est le premier algorithme a avoir t con u De mani re g n rale un algorithme est un nonc dans un langage bien d fini d une suite d op rations permettant de r soudre un probl me par calcul Les travaux des math maticie
72. petits quanta de temps chaque t che Nous d taillons ici des raisons suppl mentaires qui nous poussent a nous d tourner des syst mes d exploitation temps r el pour rester sur des syst mes d exploitation plus classiques et ajouter les fonctionnalit s manquantes sous forme de services fournis par l APRC 4 1 8 1 Hypoth ses de d part Les hypoth ses de d part sont tr s diff rentes dans notre probl me et dans ceux r solus par les syst mes temps r el Ces derniers se basent la plupart du temps sur le temps d ex cution au pire des cas des algorithmes WCET Worst Case Execution Time et sur des t ches p riodiques Cela permet de calculer un ordonnancement une fois pour toutes et d tre certain que toutes les t ches pourront respecter leurs d lais Dans notre cas o nous utilisons des algorithmes issus de l Intelligence Artificielle le temps d ex cution au pire des cas est g n ralement norme et tr s loign du temps d ex cution moyen De plus il est g n ralement irr aliste de consid rer que les t ches ex cut es dans un syst me multi agent sont p riodiques Cependant comme nous n utilisons pas les hypoth ses de base des syst mes temps r el nous ne pouvons garantir que toutes les t ches pourront s ex cuter Nous sommes donc oblig s de concevoir nos agents de telle mani re qu ils pourront toujours continuer leur travail m me si les t ches qu ils voulaient d l guer des artifa
73. peut tre ex cut e propageant la substi tution correspondante dans la suite des instructions La r gle COMP traite de mani re similaire la perception de la terminaison d une action Ces r gles permettent de construire un automate dont les tats sont les diff rentes formes que peut prendre une instruction op ratoire durant son ex cution L tat initial de l automate correspond l tat de d part de l instruction op ratoire lorsqu elle est instanci e L tat final S correspond la terminaison de l ex cution de l instruction op ratoire avec succ s Les transitions entre les tats correspondent l activation des r gles de la s mantique op rationnelle 62 Chapitre 3 Des outils de calcul pour les agents Prenons comme exemple les deux instructions op ratoires suivantes IOl al pl a2 p2 102 a3 p3 a4 p4 Nous pouvons construire a partir de ces instructions op ratoires les automates de la figure 3 4 qui donnent l ensemble des chemins d ex cution possibles de ces instructions op ratoires L automate de ACT PAR ACT PAR ACT ECH ACT ECH cones A act COMP PAR E2 E3 MS ACT ACT com ow Fonte aon COMP COMP FIG 3 4 Exemple d automates sous jacents des instructions op ratoires gauche correspond OT1 et celui de droite 102 Voici la correspondance entre les tats des automates de la figure et les diff rentes valeurs que
74. plus importante d un artifact r side dans ses instructions op ratoires Celles ci permettent de d finir de mani re formelle le mode d emploi de I artifact Ainsi le comportement de I artifact est pr visible L artifact s engage implicitement respecter son mode d emploi Nous consacrons la section 3 4 4 I tude des instructions op ratoires 3 2 2 Utilisations possibles La figure 3 3 illustre un certain nombre d utilisations possibles des artifacts Remarquons qu un artifact peut tre consid r selon diff rents angles et donc appartenir plusieurs cat gories Cette el classification n est donc pas une taxonomi E gt Ne FIG 3 3 Diff rents types d artifacts artifacts de coordination C artifacts de ressource R arti facts fronti re F Les artifacts ont d abord t utilis s pour la coordination entre les agents artifacts de type C sur la figure Les artifacts de coordination peuvent tre utilis s diff rents niveaux d abstraction pour Dans une taxonomie les cat gories n ont pas d intersection et donc un objet ne peut appartenir qu une unique cat gorie 3 3 Les artifacts de calcul 57 g rer des fonctions de communication blackboard bo tes de messages services de gestion d v nements des fonctio
75. point de vue mod lisation de lap plication et elle permet de limiter au maximum les appels aux m canismes de r veil du syst me d exploitation un r veil du syst me d exploitation correspond une limite d un sous intervalle de l ordonnancement et donc potentiellement plusieurs artifacts activer ou d sactiver Les syst mes d exploitation de permettent cependant de programmer qu une alarme par processus Il faut donc g rer de mani re explicite au niveau de l APRC la liste des alarmes pour l ensemble des artifacts et transf rer au syst me d exploitation chaque r veil la date du prochain r veil 4 1 5 2 Gestion par Partifact lui m me Si l on veut que ce soit I artifact qui se charge lui m me de se mettre en pause et de red marrer tout seul on peut utiliser un m canisme similaire celui pr c demment d crit mais dupliqu dans chacun des artifacts Cette solution est moins facile mettre en place car il faut ajouter dans chaque artifact une couche charg e de demander au syst me d exploitation de lui envoyer un signal d attention chaque limite d intervalle Elle est galement moins efficace que la solution o tout est g r par APRC car chacun des artifacts qui doivent se r veiller ou s endormir une date donn e vont planifier un r veil au niveau du syst me d exploitation La gestion des alarmes multiples est en grande partie d l gu e au syst me d exploitation et il devient
76. possible d utiliser d autres types d alarmes que les alarmes temps r el du syst me d exploitation On pourrait par exemple utiliser des alarmes en temps CPU pour assurer que les artifacts s ex cutent pendant un temps CPU donn 94 Chapitre 4 La gestion des ressources processeur 4 1 5 3 Gestion par l agent On peut enfin vouloir d l guer l ex cution de l ordonnancement d un artifact son agent propri taire On retrouve ainsi l avantage que nous avions lorsque c tait APRC qui en tait charg on peut g rer la pause et le red marrage enti rement de l ext rieur sans avoir modifier le code des artifacts Cette solution peut permettre de flexibiliser l attribution des tranches de temps aux artifacts d un agent En effet un agent pourrait estimer 4 un moment qu un de ses artifacts A1 aurait un besoin en ressources processeur un peu plus important que pr vu et qu il pourrait sacrifier pour cela une tranche de temps allou e un de ses autres artifacts A2 Dans ce cas avec le mode de fonctionnement normal il devrait indiquer APRC qu il renonce une partie des tranches temporelles allou es A2 et faire une requ te pour allouer de nouvelles tranches de temps pour Al Si au contraire c est l agent qui g re l ex cution de l ordonnancement il pourrait prendre la d cision de lancer A1 plut t qu A2 dans certaines tranches de temps et ceci sans en informer l APRC Cette sol
77. pour pouvoir tre r utilis es d un type de conversation l autre La r gle r1 est un exemple de r gle de conversation qui permet de passer de l tat sO l tat s1 si une proposition de produire quelque chose arrive et que l agent est capable de la produire Dans ce cas un message d acceptation est renvoy def conversation rule rl current state s0 received propose sender initiator content produce what such that achievable produce what next state sl transmit accept content produce what Les classes de conversation sont les types d automates que l agent peut instancier Une liste des instances de classes de conversations est conserv e Exemple de classe de conversation def conversation class conv 1 tinitiator initiator repsondent respondent variables vl v2 initial state s0 final state s1 conversaion rules s0 rl conversation rule applier CRA 1 rror rules el e2 rror rule applier ERA 1 Des r gles de continuation sp cifient la mani re dont les agents r agissent lors d une requ te de conversation venant d un autre agent et la mani re de choisir la prochaine conversation suivre Une seule conversation est suivie tout instant Pendant ce temps les autres sont suspendues Le program meur peut ainsi sp cifier la priorit 4 donner aux nouvelles conversations par rapport aux conversa tions d ja d but
78. prendre en compte des contraintes non lin aires en l occurrence trigonom triques Dans Interloc nous utilisons un propagateur de contraintes sur intervalles qui a t d velopp et mis en uvre depuis de nombreuses ann es Interlog Botella et Taillibert 1993 Il est possible de lui sp cifier un contrat de temps chaque fois qu une nouvelle contrainte est introduite Si le point fixe n a pas t atteint lorsque le contrat de temps expire Interlog s arr te et retourne un ensemble d intervalles sp cifiant la localisation obtenue 4 ce stade du traitement L agent peut alors d cider de relancer la propagation pour un nouveau contrat de temps afin d am liorer la pr cision de la localisation ou au contraire d introduire les contraintes correspondant une mesure nouvellement arriv e Pour prendre une telle d cision il estime l am lioration apport e la localisation par la r duction de sa surface obtenue au cours d un contrat de temps 112 Chapitre 5 Mise en ceuvre et valuation De mani re plus formelle le probl me est le suivant Soient B les bateaux dont le nombre peut varier en fonction du temps Soit p la p riode du radar du bateau B Quand une nouvelle mesure j arrive pour le bateau B une nouvelle t che T est cr e Son d lai est DL T 7 avec T la date d arriv e de la mesure et 7 la dur e du calcul r aliser Comme peu de choses sont connues
79. propose d aborder la gestion du temps dans les syst mes multi agents en regardant ce probl me l intersection de Intelligence Artificielle et du g nie logiciel Les algorithmes issus des recherches en Intelligence Artificielle posent souvent des probl mes d int gration notamment car leurs temps d ex cution peuvent tre longs et variables Le probl me crucial dans ces situations de concurrence est la gestion des d lais que les agents ont respecter Notre but est donc de proposer dans ce cadre des outils permettant d int grer facilement des al gorithmes de g rer leur ex cution simultan e et de contr ler leur temps d ex cution La th se que nous soutenons ici est que pour arriver cet objectif il faut distinguer les agents qui sont des entit s dou es de raisonnement des artifacts de calcul qui sont des entit s passives que les agents peuvent utiliser comme outils pour atteindre leurs buts Nous proposons une classification des modes d emploi associ s aux artifacts de calcul en fonction des propri t s temporelles des algorithmes qu ils encap sulent Notre travail apporte galement un syst me qui g re l attribution des ressources processeur de mani re sp cifique et qui est extensible des syst mes multi agents distribu s Ce m moire a t r alis au sein du Laboratoire d Informatique Fondamentale de Lille LIFL en collaboration avec la soci t Thales Division A ronautique et l Insti
80. proximit de concept doit certainement permettre d acc l rer le rapprochement dont nous parlions plus haut entre les communaut s agents et composants 3 7 Rapprochement avec les autres travaux de l quipe SMAC L un des autres axes de recherche de l quipe SMAC du LIFL concerne la mod lisation centr e interaction Dans cette approche l interaction entre deux entit s est concr tis e et d finie dans le SMA entre une source ex cutant l interaction et une cible la subissant Ce sont les interactions qui forment le c ur du mod le Une interaction est une r gle qui d crit formellement une action qu un agent acteur peut d clencher sur un autre agent cible SMAC propose dans Mathieu et Picault 2006 Mathieu et Picault 2005 une m thodologie nom m e IODA Interaction Oriented Design of Agent simulations utilisant les concepts peut subir peut effectuer pour la simulation multi agents La conception d une simulation se fait en trois phases 1 d termination des interactions Cela revient 4 constituer un tableau indiquant pour chaque in teraction la liste des agents qui pourraient la subir ou l effectuer 2 d termination des agents sources et des agents cibles On donne pour chaque agent la liste des interactions qu il peut subir et effectuer 3 d termination de la dynamique du syst me On dispose ici d un moyen pour faire voluer les possibilit s d interactions de chaque agent
81. que les agents doivent suivre au mieux Nous avons propos quelques extensions au mod le de base permettant de mieux prendre en compte les contraintes temporelles li es nos artifacts de calcul et galement pour lui apporter plus de flexibilit Cela nous permet d avoir un m canisme de r cup ration apr s une erreur et d utiliser des informations sur l historique des tats des instructions op ratoires pour g rer des boucles simples dans le mod le propos par l quipe italienne Les possibilit s d extension du mod le actuel ne seront pas suffisantes pour l avenir Nous avons notamment identifi quelques fonctionnalit s int ressantes pour lesquelles une refonte du mod le de description des modes d emploi des artifacts est n cessaire Enfin nous avons fait un point m thodologique qui d crit comment les agents et les artifacts se diff rencient de mani re conceptuelle Nous avons aussi d crit comment dans une application donn e on peut distinguer quelles entit s seront des agents et quelles autres seront des artifacts Nous avons galement fait une comparaison avec les objets les composants et d autres travaux de l quipe SMAC sur les syst mes multi agents centr s interaction Chapitre 4 La gestion des ressources processeur Il faut toujours plus de temps que pr vu m me en tenant compte de la loi de Hof stadter Loi r cursive de Hofstadter Le pr sent n est pas un pass en puis sanc
82. r_content Nous consid rons que r_content est un terme quatre variables un identifiant id une estimation load de la charge processeur n cessaire pour terminer la t che une liste t_c de contraintes temporelles respecter et ca_oi l instruction op ratoire qui est l objet de la requ te et qui est d termin e par 1 APRC quand aucune inconsistence n a t trouv e dans la d termination de l ordonnancement L agent attend une r ponse de l APRC pendant r_timeout tops d horloge La r ponse peut tre une acceptation ou un refus Dans le premier cas l agent peut 4 1 Gestion des ressources processeur avec des d lais a respecter 95 x LHH H Requ te de t che ou Refus FIG 4 5 Protocole d interaction sans conflit Def_CA_Management request r_content T r_timeout accepted r_content r_content ca_oi 0 Def_CA_Management rejected i_rejection Def_CA_Management Def_CA_Management FIG 4 6 Instruction op ratoire de base de l APRC d cider ou non de suivre l instruction op ratoire r_content ca_o1 cr e par 1 APRC Dans tous les cas un nouvel appel Def_CA_ Management permet l agent de faire une nouvelle requ te aupr s de l APRC 4 1 7 Gestion des conflits Nous consid rons dans cette partie qu un agent a demand l APRC d allouer des tranches de temps pour une t che mais que celui ci a refus 4 1 7 1 Propri
83. ratives mais ils ne sont pas adapt s lorsque les actions que l agent r alise sont elles m mes des d lib rations longues sur lesquelles les agents doivent raisonner ce qui est notre cas Les mod les propos s composants ou couches ne conviennent pas nos besoins On peut donc se demander si nous devons proposer un nouveau mod le d agent couche ou autre qui r ponde nos attentes En r alit les probl mes que nous voulons r soudre encapsulation des t ches de calcul et conservation de l extraversion des agents sont suffisamment g n raux pour que l on veuille proposer une solution ind pendante du mod le d agent choisi Il faudrait donc plut t utiliser d autres entit s du SMA pour ex cuter les t ches calculatoires 3 1 3 Un second agent S il vaut mieux que les d lib rations longues soient ex cut es par une autre entit consid rons qu elles le sont par un autre agent C est ce que nous avons propos dans Dinont et al 2006b Nous avons d fini deux classes d agents une au comportement extraverti qui ne peut s engager dans des traitements longs et une seconde au comportement introverti qui ne se remet en phase avec son environnement qu apr s avoir termin l ex cution de ses t ches Les agents extravertis doivent d l guer leurs t ches longues aux agents introvertis De plus pour g rer des dates limites sur les t ches l ex cution des agents introver
84. re consiste 4 prendre la m me instruction op ratoire que pour le cas d un algorithme bo te noire et l artifact exhibe un attribut qui repr sente le r sultat actuel que l agent peut lire tout moment On fera juste attention de red finir 74 Chapitre 3 Des outils de calcul pour les agents l instruction pause_restart pour que l on ne puisse utiliser que pause_computation et restart_computation Cela donne pause_restart i pause_computation paused restart_computation restarted pause_restart test_finished La seconde m thode consiste a rajouter une action get_current_result et une perception current_result qui peuvent tre appel es n importe quand tout comme pause_restart interruptible_algorithm start_computation INPUT_DATA finished RESULT error ERROR_INFO stop_computation computation_stopped pause_restart test_result interruptible_algorithm test_result get_current_result current_result RESULT test_result test_finished 3 4 4 5 Algorithme anytime Un algorithme anytime tant un algorithme interruptible ayant un profil de qualit de la solution en fonction du temps il suffit de reprendre l une des instructions op ratoires du paragraphe pr c dent et d ajouter artifact un attribut exhibant son profil de performance 3 5 M thodologie de mod lisation d une application avec des agents et des artifacts No
85. solution 89 4 1 3 2 4 Exemples de r solution 90 4 1 4 Extensions et variantes de l algorithme d ordonnancement 91 4 1 4 1 Apparition de nouveaux agents 92 4 1 4 2 Utilisation processeur des agents 92 4 1 5 Ex cution de l ordonnancement 93 4 1 5 1 _ Gestion par l APRC 93 4 1 5 2 Gestion par l artifact lui m me 93 4 1 5 3 Gestion par l agent 94 4 1 6 Mode d emploi de base de APRO 94 4 1 7 Gestion des conflits 95 4 1 7 1 _ Propri t s de la solution propos e 95 4 1 7 2 Extension des comp tences de l APRC 95 4 1 8 Positionnement par rapport aux syst mes temps r el 98 4 1 8 1 Hypoth ses de d part 99 4 1 8 2 Contraintes au niveau des syst mes 99 4 1 9 Critique ss a sue 4e Eds au nue dada a a a E 100 4 1 9 1 _ Implications sur la mod lisation de l application 100 4 1 9 2 Efficacit pratique de l algorithme d ordonnancement 100 4 1 9 3 Dela centralisation 101 4 2 Gestion des ressources processeur sans d lais respecter 101 4 3 Passage au multi processeur 101 44
86. sur les processus et les donn es et peuvent tre utilis s pour faire de la v rification des syst mes On pourra se reporter Fokkink 2000 pour plus d informations th oriques et pratiques sur les alg bres de processus 3 4 2 Le langage initial Nous allons maintenant d crire le formalisme base d alg bre de processus propos dans Viroli et Ricci 2004 pour d crire les instructions op ratoires des artifacts Soit l ensemble des actes d interaction possibles et Z l ensemble des instructions op ratoires Les d finitions d un acte d interaction A et d une instruction op ratoire J Z sont do T 0 lalal x 1 1 1 1 1 1 D t1 tn 3 4 Le langage de mode d emploi des artifacts 61 Un acte d interaction peut tre une action a ou une perception 7 Une instruction J peut tre une instruction atomique le comportement nul 0 le d clenchement de l ex cution de l action a la une action d but e mais pas encore termin e a et la perception 7 de la terminaison d une action 7 Une instruction peut galement tre structur e grace a diff rents op rateurs pour la composition s quentielle de deux instructions pour le choix et pour la composition parall le Enfin pour permettre la r cursion une instruction peut tre l invocation D t1 t d une autre instruction op ratoire avec D le nom de l instruction op ratoire
87. t s de la solution propos e L agent demandeur peut apr s le refus de 1 APRC d allouer une nouvelle t che d cider de n go cier avec les autres agents pour qu ils sacrifient une part des tranches de temps qui leur ont t allou es pour leurs artifacts L APRC jouera le r le d interm diaire dans ce protocole de n gociation 4 1 7 2 Extension des comp tences de APRC Nous tendons les comp tences de 1 APRC pour qu il soit le support du protocole d interaction entre les agents Le protocole est d crit de mani re informelle dans la figure 4 7 96 Chapitre 4 La gestion des ressources processeur O Requ te de t che Requ te de sacrifice Refus 5 Acceptation Lancement n gociation FIG 4 7 Protocole d interaction avec conflit Le mode d emploi de l APRC est tendu pour refl ter la nouvelle utilisation La figure 4 8 donne la nouvelle version des instructions op ratoires Def_CA Management request r_content T r_timeout accepted r_content r_content ca_oi 0 Def_CA_Management rejected i_rejection Def_Negotiation_Initiator i_rejection Def_CA Management Def_CA Management f Def_Negotiation_Initiator i_rejection start_negotiation i_negotiation i_rejection T n_timeout negotiation_failed negotiation_succeeded i_negotation Def_Negotiation Participant lget_sacrifice request finished new_ sacri
88. time gt IF AND B time h present pass B time flight from to flightnum DO time h physical_issue_bp pass flightnum time La compagnie a rienne dite les billets h heures avant le d part en effectuant l action basique physical_issue_ bp query_which t asker q gt REQUEST t askee IF B q INFORM t 1 asker q Cette macro permet d tre inform des faits qui valident q Si q contient une variable quantifi e universellement toutes les instances de r ponse a la requ te q seront retourn es query_whether t asker ask q gt REQUEST t askee IF B q INFORM t 1 asker q REQUEST t askee IF B NOT q INFORM t 1 asker NOT q Cette macro permet de demander confirmation ou infirmation d un fait 4 un autre agent Nous d finissons maintenant l agent compagnie a rienne Nous devons pour cela d finir les bases de croyances de comp tences et de r gles d engagements initiales La base de croyances contient les horaires des vols sous la forme time flight from to number et le nombre de si ges disponibles pour chaque vol sous la forme time remaining_seats timel flight_number seats La base des comp tences est d finie ainsi issue_bp a flight time true DO time update_remaining_seats timel flight_number 40 Chapitre 2 Contexte additional_seats B time remaining_seats timel flight_numb
89. utilisant GPGP MQ et T MS GPGP utilise une base de croyance un ordonnanceur local et un module de coordination pour la communication Chaque agent construit sa propre vision partielle de la sous t che qu il doit accomplir L ordonnanceur prend aussi bien en compte les effets locaux que non locaux des actions La partie MQ quant elle mod lise et raisonne sur les t ches au niveau organisationnel R solveur de probl mes Ordonnanceur Produit Utilise SA oie y Design to criteria fg 1 Sous syst me d ex cution 64 A a P g R equ tes de r ordonnancement O ait eas i Echange d informations A Das i du domaine APA i Met jo Information d tat du r solveur de probl mes et ig et jour Crit res des buts Contr leur de t ches Met j Structure de t ches Utilise Echange d informations de niveau m ta court terme MOQUE 1 rl o ne E S nd ee pe gt Engagements Met a jour de e cee coordination i E non locaux i i GPGP H Ordonnanceur f i i i MQ L gende i i i i i i ENORA i Met Jour i Composants i i i i Niveaux MQ i Croyances i i Dons i i 5 S de l agent i T ches MQ Connaissances 1 i organisationnelles i Hira i ot de i i donn es i S ye pecan pen ne FIG 2 7 Architecture d un agent T MS T M
90. venons de voir que la programmation des pro cessus l gers est sujette de nombreuses difficult s Les fondeurs sont conscients de ces difficult s et proposent des biblioth ques qui simplifient la programmation des processus l gers C est le cas d Intel avec sa biblioth que Threading Building Blocks Elle fournit des instructions pour paral l liser les boucles for et while des structures de donn es s res pour une utilisation concurrente vecteur file table de hachage et des primitives de synchronisation pour les cas d utilisation usuels Il y a galement la possibilit d utiliser des biblioth ques de plus haut niveau d ja d velopp es pour b n ficier du parall lisme des machines multiprocesseurs et des grappes de serveurs Nous les d crivons dans le paragraphe suivant Vheure actuelle ces processeurs n autorisent pas un contr le fin de l allocation des processus aux diff rents c urs au niveau de l utilisateur il est impossible d indiquer un processus de s ex cuter sur un coeur particulier moins de modifier l ordonnanceur du syst me d exploitation Cette derni re possibilit n est pas raisonnable la plupart du temps Putilisation de processeurs multi c urs dans notre cadre o nous voulons pouvoir raisonner sur les ressources processeur attribu es chaque agent est donc assez probl matique Esp rons qu l avenir nous disposerons sur ces processeurs de possibilit s de c
91. 0 flight lille nice 54 dinont REQUEST Imarch 3h00 airline issue_bp dinont 42 10april 8h30 airline DO 10april 7h30 issue_bp dinont 42 10april 8h30 Agent 0 poss de un certain nombre d inconv nients comme sa synchronisation l horloge mais c est un langage simple avec lequel les programmeurs ne peuvent pas tre surpris par les interactions entre les diff rentes instructions 2 2 Travaux connexes 41 2 2 3 4 2 April April Agent Process Interaction Language McCabe et Clark 1995 est un langage de program mation pour construire des applications d Intelligence Artificielle distribu e April peut se voir comme un langage concurrent bas sur les objets ces derniers tant des processus Il permet de programmer des applications distribu es et capables de r pondre a des v nements temps r els April est un lan gage symbolique orient processus Il permet de d finir des processus et leur permet de communiquer par un m canisme de passage de messages Les donn es sont fortement typ es Des fonctionnalit s d ordre sup rieur sont incorpor es Elles permettent la structuration des programmes et permettent de passer les fonctions et proc dures d un processus un autre pour qu il puisse les ex cuter April s appuie sur la programmation orient e acteur en l tendant L expansion de macros permet de construire des couches de langage a
92. 1 Un agent interagit avec son environnement au travers de capteurs et d actionneurs Nous d crivons dans cette th se une mani re particuli re de voir l environnement des agents Celui ci est vu au travers des probl mes que posent le temps et le partage des ressources de calcul dans la conception de la fonction d agents informatiques ayant des calculs lourds r aliser L en vironnement est constitu des processus des agents s ex cutant dans le SMA Le support de l envi ronnement tant l ensemble des processeurs utilis s par le SMA nous prendrons en compte dans sa repr sentation les ressources de calcul propos es par les processeurs Nous aborderons quand cela sera n cessaire les questions de terminologie Ce sera par exemple le cas lorsqu il nous faudra parler de l autonomie de la pro activit ou de l extraversion des agents Nous donnerons ces termes des d finitions adapt es l environnement particulier d crit ici Lorsque l on parle de la gestion du temps pour des agents intelligents il est in vitable d aborder la comparaison avec la mani re dont l Homme g re le temps Notre capacit la plus tonnante est certainement la fa on avec laquelle nous sommes capables de g rer plusieurs contextes simultan ment et de passer d un contexte l autre automatiquement d s que l on per oit un signal d attention pour un contexte particulier Par exemple nous sommes capables de nous arr ter de travaille
93. 76 3 8 Caract ristiques d un composant 78 3 9 Peut subir peut effectuern 80 xiv Table des figures 4 1 Exemple d ordonnancement obtenu avec Earliest Deadline First 87 4 2 Partitionnement du 1 intervalle dans le cas d 1 agent de 3 artifacts et de APRC 88 4 3 Prise en compte des contraintes sur les intervalles restants 91 4 4 Modification des dates de d but d intervalleS 91 4 5 Protocole d interaction sans conflit 95 4 6 Instruction op ratoire de base de APRC 95 4 7 Protocole d interaction avec conflit 96 4 8 Instructions op ratoires de l APRC 96 4 9 Lien s mantique entre les IO de l APRC et l tat mental de l agent 97 5 1 Un agent ALBA vivo 44 44 hehe ERA ui da n dba Dada 106 5 2 La migration des agents dans ALBA 107 5 3 P aiguilleur dispatche les messages vers les fils de raisonnement 109 5 4 Copie d cran d Interloci 111 5 5 Capture d cran de l interface de visualisation en mode 2 machines 116 Chapitre 1 Introduction Cette th se se
94. C 2005c Team of cognitive agents with leader how to let them acquire autonomy In Proceedings of 2005 IEEE Symposium on Computational Intelligence and Games Dev ze 2006 DEVEZE B 2006 Programmation d agents intelligents vers une refonte des fils de raisonnement M moire de D E A Universit Pierre et Marie Curie Dev ze et al 2006 DEVEZE B CHOPINAUD C et TAILLIBERT P 2006 Alba a generic li brary for programming mobile agents with prolog In AAMAS 06 Dinont 2003 DINONT C 2003 Un langage et un mod le d agent M moire de D E A Labora toire d Informatique Fondamentale de Lille Universit Lille 1 Dinont et al 2006a DINONT C DRUON E MATHIEU P et TAILLIBERT P 2006a Artifacts for time aware agents In AAMAS 06 Dinont et al 2006b DINONT C DRUON E MATHIEU P et TAILLIBERT P 2006b CPU sha ring for autonomous time aware agents In COGIS 06 Dix et al 2001 DIX J KRAUS S et SUBRAHMANIAN V S 2001 Temporal agent programs Artificial Intelligence 127 1 87 135 129 Eiter et Subrahmanian 1999 EITER T et SUBRAHMANIAN V S 1999 Heterogeneous active agents ii Algorithms and complexity Artif Intell 108 1 2 257 307 El Fallah Seghrouchni et Suna 2005 EL FALLAH SEGHROUCHNI A et SUNA A 2005 Multi Agent Programming Languages Platforms and Applications volume 15 de Multiagent Systems Artificial Societies and Simulated
95. D ailleurs elle prend tout son sens depuis les travaux de Herbert 2 2 Travaux connexes 19 Simon sur la notion de satisficing et la tendance a vouloir construire des agents rationnels plut t que des agents parfaits 2 2 1 4 Algorithmique anytime L utilisation d algorithmes exhaustifs ou d heuristiques pose le probl me de la bo te noire qui prend la main et ne la rend que quand elle a termin L id e serait de rendre la boite un peu transparente pour pouvoir voir de l ext rieur l tat d avancement du calcul et d autoriser quelques fonctions de contr le comme la pause la reprise et l arr t avec renvoi de la valeur courante C est ce que tente de r aliser l algorithmique anytime figure 2 1 Qualit Qualit Qualit du resultat final Qualit croissante Qualit nulle T temps temps Algorithme classique Algorithme anytime FIG 2 1 Diff rence entre un algorithme classique et un algorithme anytime Dean et Boddy donnent la d finition suivante Dean et Boddy 1988 Boddy et Dean 1989 D finition 2 4 Algorithme anytime Un algorithme anytime est un algorithme it ratif qui garantit de produire une r ponse toute tape de calcul o la r ponse est suppos e s am liorer chaque it ration Du point de vue de l implantation un algorithme anytime doit poss der les caract ristiques suivantes interruptibilit il peut tre interrompu
96. DA T 1995 Agentalk Describing multiagent coordination protocols with inheritance In TAI 95 Proceedings of the Seventh Inter national Conference on Tools with Artificial Intelligence page 460 Washington DC USA IEEE Computer Society Lacouture et Aniort 2006 LACOUTURE J et ANIORT P 2006 Vers l adaptation dynamique de services des composants monitor s par des agents In 2eme journ e multi agent et composant Lee 2006 LEE E A 2006 The problem with threads Computer 39 5 33 42 Lhomme 1993 LHOMME O 1993 Consistency techniques for numeric CSPs In IJCAT 93 Lhomme et al 1994 LHOMME O GOTLIEB A et RUEHER M 1994 Dynamic optimization of interval narrowing algorithms Journal of Logic Programming 19 20 Liu et Layland 1973 Liu C L et LAYLAND J W 1973 Scheduling algorithms for multipro gramming in a hard real time environment Journal of the ACM 20 1 46 61 131 Luck et d Inverno 2001 LUCK M et D INVERNO M 2001 Autonomy A nice idea in theory Lecture Notes in Computer Science 1986 Marson 2006 MARSON P E 2006 Artifacts abstractions pour la mod lisation et la mise en ceuvre d un environnement au sein d un syst me multi agents M moire de D E A Universit Paris Dauphine Mathieu et Picault 2005 MATHIEU P et PICAULT S 2005 Towards an interaction based design of behaviors In European workshop on Multi Agent systems EUMAS
97. LI M et OMICINI A 2005 Programming MAS with artifacts In ProMAS 05 Ricci et al 2006 RICCI A VIROLI M et OMICINI A 2006 CArtAgO An infrastructure for engineering computational environments in MAS In WEYNS D PARUNAK H V D et MICHEL F diteurs 3rd International Workshop Environments for Multi Agent Systems E4MAS 2006 pages 102 119 AAMAS 2006 Hakodate Japan Shoham 1993 SHOHAM Y 1993 Agent oriented programming Artificial Intelligence 60 1 51 92 Subrahmanian et al 2000 SUBRAHMANIAN V S BONATTI P DIX J EITER T KRAUS S OZCAN F et Ross R 2000 Heterogeneous Agent Systems MIT Press AAAI Press Cambridge MA USA 132 Bibliographie Suna 2005 SUNA A 2005 CLAIM et SyMPA Un environnement pour la programmation d agents intelligents et mobiles Th se de doctorat Universit Paris 6 Suna et al 2004 SUNA A KLEIN G et EL FALLAH SEGHROUCHNI A 2004 Using mobile agents for resource sharing In IAT pages 389 392 IEEE Computer Society Vincent et al 2001 VINCENT R HORLING B LESSER V R et WAGNER T 2001 Imple menting Soft Real Time Agent Control Proceedings of the 5th ICAA pages 355 362 Viroli et Ricci 2004 VIROLI M et RICCI A 2004 Instruction based semantics of agent media ted interaction In AAMAS 04 Wagner 2000 WAGNER T 2000 Toward Quantified Organizationally Centered Decision Ma king and C
98. Langages logiques 31 2 2 3 1 2 Raisonnement sur des dur es incertaines 32 2 2 3 2 Mod les d agents hybrides 33 2 2 3 2 1 InTeRRaP 33 2 2 3 2 2 Touring Machines 34 2 2 3 3 Langages pour la gestion de contextes de communication 34 223 31 COOL e sis Sous pandas amet 35 2 2 3 3 2 AgenTalK 36 2 2 3 4 Langages et architectures facilitant la gestion du temps dans les SMA 37 2 2 3 4 1 Agent 37 22342 April nues da sad ire de Aei 41 2 2343 PRS wie ss 4er ue vu pb saga mt eG 42 22 344 T EMS o runs ke ee ee ee aa 43 2 2 3 4 5 Temporal Agent Programs 46 2 2346 DECAH ie o cc macei e da ba baa ees 47 2 3 Synth se 2 ee 4 44 tee wie er AO ee AR A ee de e 48 3 Des outils de calcul pour les agents 49 3 1 Position du probl me 50 3 1 1 Besoin d un nouveau type d entit 50 3 1 2 Une partie de l agent 50 3 1 3 Un S cond p nt 4 4 24 ps kok La dada pets date a de 51 3 1 4 Une nouvelle entit 53 3 2 Les artifacts faasa p a la ha De est Oe Res a ae a 54 3 2 1 D mon e su Los spas eee dus we eh ms 54
99. Mise en ceuvre et valuation Nous pensons galement que Prolog poss de un grand nombre de qualit s n cessaires 4 un langage de programmation de SMA Pacc s aux m canismes syst me comme les sockets la gestion des processus les entr es sorties sont maintenant correctement g r es par la plupart des Prolog du march l introspection peut tre r alis e gr ce aux facilit s de modifications dynamique du code Prolog permet aussi bien la programmation d clarative que proc durale son efficacit naturelle permet de d velopper et de tester tr s rapidement de nouveaux propto types et id es sa nature interpr t e lui permet d tre ex cut sans modification sur une large vari t de plate formes 5 1 1 2 Caract ristiques principales ALBA est une biblioth que Prolog d di e la programmation d agents crits en Prolog Les fonctionnalit s d ALBA sont d crites en d tail dans Dev ze et al 2006 Nous pr sentons ici celles qui nous paraissent essentielles 5 1 1 2 1 D centralisation Nous avons remarqu que la plupart sinon la totalit des plateformes agents qui impl mentent des agents mobiles utilisent une forme de centralisation que ce soit par un serveur fournissant la gestion des agents pour chaque machine contexte ou par un serveur central g rant l ensemble des agents distribu es sur diff rents ordinateurs Dans tous les cas la migration la cr ation
100. Morgan Kaufmann Publishers Inc Dean et Boddy 1988 DEAN T et BODDY M S 1988 An analysis of time dependent planning In AAAI pages 49 54 Decker 1995 DECKER K 1995 Environment Centered Analysis and Design of Coordination Mechanisms Ph D Thesis Department of Computer Science University of Massachusetts Am herst Delhay 2000 DELHAY A 2000 Contribution l algorithmique anytime Contr le et Concep tion Th se de doctorat Universit Lille 1 Demazeau 1995 DEMAZEAU Y 1995 From interactions to collective behaviour in agent based systems In Proceedings of the First European conference on cognitive science pages 117 132 Saint Malo France Devigne et al 2004 DEVIGNE D MATHIEU P et ROUTIER J C 2004 Planning for spatially situated agents In IEEE WIC ACM International Conference on Intelligent Agent Technology IAT 04 pages 385 388 IEEE Press Devigne et al 2005a DEVIGNE D MATHIEU P et ROUTIER J C 2005a Interaction based approach for games agents In Proceedings of the 19th Europeen Conference on Modelling and Simulation Simulation in Wider Europe ECMS 2005 pages 705 714 Devigne et al 2005b DEVIGNE D MATHIEU P et ROUTIER J C 2005b Simulation de com portements centr e interaction In Journ es Francophones sur les Systemes Multi Agents JF SMA 05 Calais France Herm s Lavoisier Devigne et al 2005c DEVIGNE D MATHIEU P et ROUTIER J
101. R ER est gale la dur e de l intervalle 5 il n est pas n cessaire de consid rer d autres t ches que la t che 7 et les t ches k pour lesquelles C y 1 Par exemple dans le cas d g n r o la t che 7 ne peut tenir sa date limite qu en prenant toutes les ressources processeur du d but la fin de l intervalle il ne sert rien de faire le calcul de l ordon nancement sur cet intervalle en consid rant d autres t ches De plus il est n cessaire de limiter le nombre de t ches dans un intervalle pour que la solution trouv e dans celui ci n apporte pas un trop grand fractionnement Il doit subsister une diff rence entre les ordres de grandeur des p riodes de temps consid r es par ordonnanceur syst me et celui de P APRC Ce dernier ne doit pas empi ter sur le travail du premier en mettant en pause et en red marrant trop souvent les agents Nous limitons donc actuellement le nombre de t ches dans un intervalle 10 au maximum Ainsi il se peut que nous ne trouvions pas d ordonnancement alors qu il en existe r ellement un Ceci n est pas v ritablement un probl me car de toutes fa on si nous d terminions P ordonnancement possible il ne serait pas tenu en pratique cause de l empi tement sur le travail de l ordonnanceur du syst me d exploitation 4 2 Gestion des ressources processeur sans d lais a respecter 101 4 1 9 3 De la centralisation L APRC apporte un point de ce
102. S dispose d une documentation tr s compl te en commen ant par les articles sur Design to Time Garvey et Lesser 1996 et Design to Criteria Wagner et Lesser 2000 Une description et une analyse tr s compl te pourra tre trouv e dans la tr s volumineuse th se de Thomas Wag ner Wagner 2000 On y trouvera en particulier une explication sur la structure de boucle qu il n est pas facile introduire dans T MS T MS pr sente quelques inconv nients qui en limitent l usage dans notre cadre En effet Design to Time Design to Criteria et la structure de t ches ne sont int ressants que quand on dispose de plu 46 Chapitre 2 Contexte sieurs alternatives pour atteindre un but L impossibilit de d crire facilement des traitements it ratifs ou r cursifs est galement une limitation importante Enfin T MS ne propose aucun outil pour r duire le foss entre le niveau agent repr sent par la structure de t ches et le niveau du code h rit contr l par le niveau agent 2 2 3 4 5 Temporal Agent Programs Temporal Agent Program TAP Dix ef al 2001 est une extension de la plate forme IM PACT Arisha et al 1999 Subrahmanian et al 2000 Eiter et Subrahmanian 1999 IMPACT per met de construire des agents au dessus de tout type de code h rit Pour cela on d crit tout d abord la base de code sur laquelle vont tre bas s les age
103. Y e a Ai ete oh deb A 124 Bibliographie 127 xii Table des mati res Table des figures 1 1 Un agent interagit avec son environnement au travers de capteurs et d actionneurs 3 2 1 Diff rence entre un algorithme classique et un algorithme anytime 19 2 2 Exemple de carte de qualit d un algorithme anytime 20 2 3 Architecture d InteRRaP 33 2 4 Architecture de Touring Machines 34 2 5 Diagramme de flot d un agent Agent 0 38 2 6 _ Exemple d arbre T MS 44 2 7 Architecture d un agent TEMS 45 3 1 Les diff rents types d agents d finis par Ferber 53 3 2 Uncartilach s 4 4 acy a guise sue Du an sales ete de 55 3 3 Diff rents types d artifacts 56 3 4 Exemple d automates sous jacents des instructions op ratoires 62 3 5 Mode d emploi d un lave vaisselle sans utiliser l historique 67 3 6 Mode d emploi d un lave vaisselle utilisant l historique 68 3 7 Principales diff rences entre les agents et les artifacts
104. an d un agent est ex cut dans un processus s par Un processus particulier g re la m moire de l agent Les autres t ches lui envoient des messages pour r cup rer ou mettre jour les donn es Ne pas pouvoir acc der directement la m moire de l agent et devoir proc der par envoi de messages est une limitation importante pour les performances 2 2 3 4 3 PRS PRS Procedural Reasoning System Ingrand et al 1992 est une architecture g n rique pour repr senter et raisonner sur les actions dans un domaine dynamique Un agent PRS est constitu d une base de donn es des croyances actuelles de I agent d un ensemble des buts courants d une biblioth que de plans nomm s des proc dures ou Knowledge Areas KA qui d crivent les s quences de tests et d actions r aliser pour atteindre un but ou pour r agir des v nements en provenance de l environnement les KA disposent d une condition d invocation qui sp cifie dans quelles situations le KA est utile La condition d invocation est compos e de deux parties La partie d clenchement est une expression logique d crivant les v nements qui doivent survenir pour que le KA soit invocable Elle peut porter sur des changements dans la base des buts et ou sur la base de croyances La partie contextuelle est une expression logique sp cifiant les conditions devant tre vraies pour que le KA soit ex cutable d une struct
105. ans la prise de d cision de migration des agents Nous utilisons ici deux machines La premi re est notre machine de r f rence utilis e dans la section pr c dente La seconde machine dispose d un processeur AMD K6 2 cadenc 450 MHz et disposant de 256 Mo de m moire La pr paration de l exp rimentation consiste lancer un d mon ALBA et un APRC sur chacune des machines Les deux APRC se connaissent et peuvent s changer des informations par le r seau La figure 5 5 montre une capture d cran de l interface qui nous permet de visualiser les informations dont ils disposent Nous reprenons les m mes conditions que dans l exp rience pr c dente APRC est activ au lancement du syst me tous les agents et artifacts d marrent sur la premi re machine le nombre de bateaux est fix 10 les p vont de 5 30 secondes en temps r el PD est fix 2 secondes en temps processeur La seule diff rence est que nous autorisons maintenant les agents migrer de la premi re machine la seconde mais pas de la seconde la premi re La politique de migration est la suivante d s qu un agent se voit refuser l allocation de ressources processeur par l APRC il lui demande de migrer sans se pr occuper de la charge de la seconde machine L APRC accepte les migrations jusqu ce que les charges des deux machines soit gales Une fois l autorisation de migrer accord
106. ans le paragraphe pr c dent Ferber avait notamment propos dans Ferber 1995 une classification des agents en fonction de leur type de comportement qui est pertinente dans notre cas Elle est rappel e dans la figure 3 1 Relation au monde A on PREI Conduites gents cognitifs Agents r actifs T l onomiques Agents intentionnels Agents pulsionnels R flexes Agents modules Agents tropiques FIG 3 1 Les diff rents types d agents d finis par Ferber Pour Ferber ce qui diff rencie les agents cognitifs des agents r actifs c est leur relation au monde Un agent cognitif dispose d une repr sentation symbolique du monde partir de laquelle il peut raisonner Un agent r actif ne dispose que d une repr sentation sub symbolique du monde c est dire limit e ses perceptions Nous ne nous int ressons qu la colonne correspondant aux agents cognitifs Les agents extravertis d crits dans le paragraphe pr c dent sont des agents intentionnels car ils ont un comportement t l onomique leur comportement est dirig par des buts explicites Au contraire les agents introvertis pr c demment cit s entrent plut t dans la cat gorie des agents modules ils sont utilis s par les agents extravertis comme des sous traitants dociles qui ex cutent de mani re r flexe les travaux qu on leur donne Ferber conc de que ces agents se situent a la limite du concept d agent Nous pouvons no
107. aradigme agent Il existe un trop grand foss entre le concept g n ral d autonomie et le code qu il peut crire pour ses agents Il en reviendra se poser le m me type de questions que quand nous parlions dans la section 1 1 du sens donner l intelligence lorsque celle ci est implant e sous forme de programme dans un ordinateur comment programmer un agent pour qu il soit autonome Comment v rifier que l agent que j ai crit peut tre consid r comme autonome Nous voulons que notre discours autour de l autonomie permette facilement de trouver des r ponses aux questions pr c dentes Le concept d autonomie tant tr s vaste et notre probl matique tant de type g nie logiciel nous avons identifi une cons quence op rationnelle de l autonomie qui nous permet de manipuler ce concept abstrait de mani re concr te dans nos applications Un agent A est consid r comme tant autonome par rapport un agent B si l agent B ne peut pr dire coup s r le comportement de l agent A Avant de continuer il convient de pr ciser le sens que nous donnons ici un autre terme com portement Du point de vue d un agent B le comportement d un agent A sera d fini par ce que per oit B de A Comme nos agents n interagissent que par envoi de messages pr dire le comportement de A revient pr dire quand et quels messages seront transmis de A B Le comportement est en grande partie c
108. as autonome Proactif Non proactif Extraverti Introverti Dirig par des buts Orient service FIG 3 7 Principales diff rences entre les agents et les artifacts Notons enfin qu il y a d autres aspects pour lesquels les agents et les artifacts sont indiff renci s C est le cas pour l aspect situ 3 5 2 Classement des entit s d une application Nous avons identifi un certain nombre de questions qu il convient de se poser pour savoir si une entit de notre syst me doit tre consid r e comme un agent ou comme un artifact Le tableau 3 7 est un aide m moire des principales diff rences entre les agents et les artifacts Il est expliqu dans les questions et r ponses ci dessous L entit est elle autonome Comme nous l avons remarqu dans le paragraphe pr c dent une entit qui n est pas du tout autonome sera un artifact Une entit qui est autonome sera un agent Les agents peuvent avoir diff rents degr s d autonomie Il sera parfois difficile de diff rencier un agent d un artifact lorsque celui ci ne dispose que de tr s peu d autonomie On se tournera alors vers les autres caract ristiques qui d coulent de l autonomie pour classer l entit Par exemple la pro activit est r serv e aux agents Les comportements des artifacts sont tous d clench s par les actions demand es par les agents Attention cela n emp che pas un artifact de d clencher lui m me
109. atoire pr c dente un timeout qui garantit que l on aura soit la r ponse soit une erreur avant la fin du temps imparti Cela donne known_execution_time_algorithm Istart_computation INPUT_DATA T DURATION finished RESULT error ERROR_INFO stop_computation computation_stopped pause_restart known_execution_time_algorithm Nous consid rons ici que la dur e d ex cution DURATION est un attribut de artifact Elle peut tre fixe ou calcul e et mise jour par agent avant de lancer un nouveau calcul 3 4 4 3 Algorithme contrat Le mode d emploi d un algorithme a contrat est le suivant contract_algorithm start_computation INPUT DATA CONTRACT T CONTRACT finished RESULT error ERROR_INFO stop_computation computation_stopped end_contract contract pause_restart contract_algorithm contract continue CONTRACT T CONTRACT finished RESULT error ERROR_INFO stop_computation computation_stopped end_contract contract La structure de base est la m me que pr c demment part de l on ajoute comme param tre start_computation la dur e du premier contrat Ensuite tant que le calcul n est pas termin et qu il n y a pas eu d erreur il est possible de relancer de nouveaux contrats 3 4 4 4 Algorithme interruptible Nous avons ici deux mani res de faire La premi
110. aux actions et perceptions intro duite dans Viroli et Ricci 2004 et rappel e dans la section 3 4 3 4 1 Dans ce tableau les croyances de l agent permettent d exprimer des pr conditions aux actions des instructions op ratoires et les per ceptions ont des effets sur les croyances de l agent Pr conditions aux actions Un agent envoie une requ te l APRC s il croit qu il est possible de r aliser la t che Bpossible r_content et s il ne dispose pas encore d une instruction op ratoire pour ex cuter cette t che Bhave_oi r_content Avant de d marrer une n go ciation il remplit des champs dans le terme s_content l importance et la charge de calcul de la t che Un agent refuse de se sacrifier s il croit que ses travaux sont plus importants que ce lui associ la requ te B more_important s_content my_work Au contraire il pro pose de se sacrifier s il croit que ses t ches sont moins importantes La proposition qu il formule dans ce cas d pend de ses croyances sur la quantit de ressources de calcul qu il peut sacrifier Bcan_sacrifice_work_load s_content load Effets des perceptions Si un agent re oit la perception que sa requ te a t accept e ou que la n gociation a t fructueuse il met jour sa base de croyances pour croire que r_content ca_oi est une instruction op ratoire valide qu il va pouvoir utiliser pour r aliser sa t che de calcul Bhave_oi r_cont
111. cation Nous voulons que nos agents aient un comportement extraverti Il sera courant pour un agent d tre en conversation avec de multiples interlocuteurs simultan ment Il convient de structurer la gestion des communications autour des contextes de conversations entam es par les agents Nous nous attardons donc quelque peu sur les langages propos s pour g rer ces diff rents contextes de communication au sein d un agent 2 2 Travaux connexes 35 2 2 3 3 1 COOL COOL Barbuceanu et Fox 1995 est un langage permettant de sp cifier avec peu d efforts de programmation les m canismes de coordination entre les agents Chaque activit de coordination y est repr sent e par une machine a tat finie Les r gles de conversation sont la d finition des transitions de l automate le type de message qui active la transition dans un tat donn les actions r aliser lors du franchissement les messages en voyer et le nouvel tat apr s franchissement Les r gles de conversation poss dent des variables locales instanci es permettant de transmettre des valeurs entre les transitions Des constructions permettent de tester le premier message de la file d attente de l agent ou de chercher un message particulier dans la file Des r gles de r cup ration apr s erreur permettent de traiter les messages qui ne correspondent pas ceux attendus dans un tat donn Elles sont s par es des r gles de conversation
112. ce interm diaire Les agents doivent disposer de moyens de d marrer et d arr ter des artifacts Ces op rations ne font pas partie de l interface d usage des artifacts car ce sont des fonctionnalit s de plus haut niveau d abstraction L arr t brutal d un artifact peut tre demand tout moment par un agent Cela corres pond tuer le processus ou le processus l ger qui ex cute le programme de l artifact L arr t normal et non forc d un artifact pourra cependant tre pr vu dans l interface d usage de celui ci La mise en pause et le red marrage des artifacts est n cessaire pour pouvoir mettre en place des m canismes de partage du processeur comme nous le verrons dans le chapitre suivant La mise en pause se r alise id alement au niveau syst me sans que ce soit l artifact de g rer cela Sous Unix on peut par exemple utiliser le signal SIGSTOP pour mettre en pause un processus et le signal SIGCONT pour le red marrer Il faut faire attention que si le processus de artifact est mis en pause il devient impossible pour un agent d envoyer une commande d ex cution d une action et d inspecter les attributs de artifact C est pourquoi nous proposons un second m canisme avec les op rations pause_computation et resume_comput ation La mise en pause peut consister arr t mo mentan de la t che de calcul et l attente sur une socket de la commande de red marrage Avec ce syst me on pe
113. composants logiciels sont essentiellement des objets distribu s qui disposent de leur propre fil d ex cution g n ralement un processus l ger et encapsul s dans une couche g rant diff rents services comme la s curit ou les transactions Alors que les objets distribu s sont principalement utilis s en mode synchrone les composants fournissent des sources et des puits d v nements qui leur permettent de fonctionner en mode asyn chrone On se rapproche ainsi de la vision agent o l on fonctionne quasi uniquement par change de messages en mode asynchrone Les composants exhibent les services qu ils fournissent mais galement les services requis pour leur bon fonctionnement Cela permet de concevoir une application en conectant les ports fournis par des composants aux ports requis par d autres Nous utilisons dans la suite la notion d artifact qui se rapproche de la notion de composant logi ciel La section 3 6 donne d autres informations concernant les composants et compare en d tail notre approche avec l approche composant 2 2 2 2 3 Le GRID Alors qu une grappe est un ensemble de machines homog nes regroup es dans un m me lieu une grille de calcul est un ensemble de ressources de calcul h t rog nes d localis es On peut dire que le GRID est aux syst mes multi agents actuels ce que l Internet est aux r seaux locaux il y a un 30 Chapitre 2 Contexte diff rence d chelle t
114. con oit des syst mes temps r els durs L ordonnancement est alors effectu en prenant en compte le temps d ex cution au pire des cas WCET Worst Case Execution Time en anglais Ces techniques sont impraticables lorsque l on utilise des algorithmes aux complexit s au pire des cas tr s lev es C est d autant plus dommageable que la plupart du temps la complexit en moyenne est beaucoup plus limit e que la complexit au pire des cas On doit dans ce cas plut t utiliser comme base de calcul la complexit moyenne On renonce ainsi respecter des contraintes temps r elles dures La th orie de la complexit donne une classification compl mentaire de la premi re Elle diff rencie les algorithmes d terministes et les algorithmes non d terministes Alors qu un algorithme d terministe produit un seul calcul chaque tape un algorithme non d terministe produit un ensemble de calcul 2 2 Travaux connexes 17 La classification suivante permet de d terminer la difficult d un probl me Classe Description L les probl mes de d cision qui peuvent tre r solus par un algo rithme d terministe en espace logarithmique par rapport a la taille de l instance NL cette classe correspond la pr c dente mais pour un algorithme non d terministe P les probl mes de d cision qui peuvent tre d cid s par un algo rithme d terministe en un temps polynomial par rapport la taille de l
115. ct 3 Artifact 2 Artifact 3 Artifact 2 Artifact 1 Pi 4 33 P11 20 Artifact 1 Artifact 1 Artifact 1 Temps To Dil D12 D13 Di4 DL se FIG 4 2 Partitionnement du premier intervalle dans le cas d 1 agent de 3 artifacts et de l APRC Ce partitionnement d un intervalle correspond bien ce que nous voulons faire la priorit est donn e la terminaison de la t che puisqu elle appara t dans tous les sous intervalles et si on peut ex cuter une ou plusieurs autres t ches en parall le de la t che 7 on le fera le plus t t possible dans l intervalle Le probl me pour le intervalle revient donc d terminer les dur es Di j Di j tant la dur e du sous intervalle j de l intervalle 7 Les D peuvent s annuler 4 1 3 2 2 Pr paration de la r solution La r solution est faite intervalle par intervalle On calcule pour chaque intervalle les variables n cessaires la constitution d un syst me d quations et d in quations lin aires que l on r sout gr ce l algorithme du simplexe Faure 1979 On d finit tout d abord les limites de l intervalle consid r la date de fin est toujours gale DL la date effective de d but DD peut tre diff rente de DL _ si la t che 1 s est termin e avant la fin de son intervalle Elle est obtenue par 4 1 Gestion des ressources processeur avec des d lais a respecter 89
116. cts de calcul ne peuvent s ex cuter 4 1 8 2 Contraintes au niveau des syst mes Les contraintes sur la programmation des processus sur lesquels on pose des contraintes tempo relles sont galement tr s fortes sur les syst mes temps r el On ne peut par exemple r aliser aucune op ration pour laquelle on ne peut conna tre tr s pr cis ment le nombre de cycles processeur n ces saires C est le cas de toutes les op rations d entr e sortie Ainsi il est impossible pour un processus temps r el d effectuer directement un affichage sur l cran Pour cela il faut cr er un second proces sus sans contraintes temps r el qui va partager la m moire du processus temps r el et va tre capable d interagir avec les p riph riques d entr e sortie Ces contraintes sont tr s dures et irr alistes dans le cadre de programmes issus du domaine de Intelligence Artificielle Nous voulons pouvoir utiliser dans nos SMA toutes les facilit s propos es par les biblioth ques de programmation propos es sur les syst mes non temps r el classiques 100 Chapitre 4 La gestion des ressources processeur 4 1 9 Critique 4 1 9 1 Implications sur la mod lisation de l application La gestion des ressources processeur que nous proposons implique une structuration tr s stricte des applications Nous obligeons par exemple que les taches ayant des d lais soient d l gu es a des artifacts de calcul m me si ce sont des t ches courtes
117. d task task goto state walt_answer define script state wait_answer mon_script when msg ok do exit script Dans ce code on peut galement instancier d autres automates On peut ainsi r aliser une hi rar chie La m moire d un automate parent est accessible depuis un fils On peut partager de la m moire entre un parent et un enfant mais galement entre les enfants puisqu ils partagent l acc s la m moire de leur parent Un agent peut tre impliqu dans plusieurs protocoles simultan ment ceux ci partageant les m mes ressources AgenTalk permet de d crire un m canisme de r solution de conflits L h ritage d automate permet d tendre un script d j crit pour lui ajouter d autres tats Les auteurs avouent cependant eux m mes qu utiliser l h ritage d automate n est pas chose ais e car il n est pos sible que d tendre un automate en ajoutant des tats et qu il est difficile de modifier par h ritage les tats existants 2 2 3 4 Langages et architectures facilitant la gestion du temps dans les SMA Nous venons de pr senter les techniques de raisonnement sur le temps les mod les d agents per mettant de combiner r activit et cognition et les m canismes de gestion de contextes de conversation Nous proposons maintenant un tour d horizon des autres langages et architectures d agent pr sentant des fonctionalit s de gestion du temps qui ont un int r t pour notre
118. des agents et les communications sont r alis es au travers d une entit d di e qui conna t les agents locaux et leurs quivalents distants Notre plateforme est enti rement d centralis e Nous n utilisons pas d intergiciel auquel tous les agents devraient se connecter Au contraire le code impl mentant les fonctionnalit s de la plateforme est embarqu dans chacun des agents La figure 5 1 illustre l architecture tr s simple utilis e pour nos agents ALBA Comportement Biblioth que ALBA FIG 5 1 Un agent ALBA 5 1 Mise en ceuvre 107 5 1 1 2 2 G n ricit ALBA se veut g n rique il n est fait aucune hypoth se concernant le mod le d agent utilis par les applications d velopp es avec ALBA Ainsi ALBA peut tre utilis e avec n importe quel type de mod le d agent Agent 0 AgentSpeak BDI 3APL De plus la communaut agent n a pas encore propos de mod le universel qui pourrait tre utilis pour tous les types d applications possible Cette approche nous permet de pouvoir tester diff rents modeles et de les combiner pour atteindre nos buts La m me id e est utilis e pour ne pas tre d pendant du langage de communication utilis par les agents sur les canaux de communication ouverts par la biblioth que ALBA 5 1 1 2 3 La migration des agents Pour autoriser la migration nous plagons sur chaque machine du SMA un d mon ALBA Les d mons sont charg s d
119. dmise comme vraie en particulier parce que Church et Turing y sont parvenus par des chemins totalement diff rents Nous pouvons maintenant donner une d finition plus pr cise d un algorithme D finition 2 3 Algorithme de Knuth 1997 Un algorithme est un ensemble fini de r gles qui donnent la s quence d op rations pour r soudre un type de probl me particulier Un algorithme doit poss der toutes les caract ristiques suivantes un algorithme doit se terminer apr s un nombre fini d tapes les tapes de l algorithme doivent tre d finies pr cis ment le mieux tant d utiliser un langage de programmation pour les exprimer un algorithme doit prendre 0 ou plus valeurs en entr e un algorithme poss de une ou plusieurs valeurs de sortie qui sont en relation avec les valeurs en entr e l algorithme doit tre effectif c est dire que les op rations qui le composent sont suffisam ment simple pour pouvoir tre ex cut es de mani re atomique On peut classer les algorithmes en fonction du type de r sultat attendu La classe la plus remar quable est celle des probl mes de d cision puisque c est elle qui a permis a Turing d aboutir son r sultat sur le probl me de l arr t Elle est importante galement parce que tout les probl mes peuvent se ramener un probl me de d cision Par exemple le probl me de la k colorabilit d un graphe G peut tre formul ains
120. du probl me On peut par exemple alterner l exploration de l espace de recherche gr ce un algorithme g n tique et l exploitation gr ce un recuit simul Matthieu Basseur a r cemment propos ce type de fonctionnement coop ratif pour des probl mes d ordonnancement de type flow shop Basseur 2005 Il nous para t int ressant de voir ce type de probl mes dans une perspective multi agent o chaque m thode serait g r e par un agent et la coop ration entre les agents permettrait une alternance entre les m thodes intelligemment guid e Les techniques propos es dans cette th se constituent un premier pas dans cette direction Remarquons que l utilisation d heuristiques nous oblige la plupart du temps changer l nonc du probl me pour ne consid rer qu une restriction du probl me initial Par exemple pour le probl me du voyageur de commerce le probl me initial consiste trouver le circuit Hamiltonien le plus court dans un graphe dont les n uds repr sentent des villes et les arcs sont annot s par la distance entre les deux villes qu ils relient Ce probl me ne peut tre r solu en pratique pour des probl mes de grande taille On d cide donc de changer l nonc du probl me pour par exemple tenter de trouver un chemin le plus court possible Cette tendance r soudre mieux ou de mani re satisfaisante des probl mes restreints ne doit pas tre per ue comme un aveu d chec
121. e En dernier recours la main est donn e la derni re couche La figure 2 3 illustre cette organisation Agent Composant pour la coop ration D gt Connaissances cc pour la coop ration Composant bas plan i gt PBC Plans locaux Composant bas comportement Mod les de a gt BBC comportement v Actions Communication Perceptions gt Mod le du monde y VA A p Flot de contr le Environnement Sessa se Flot d information FIG 2 3 Architecture d InteRRaP 34 Chapitre 2 Contexte 2 2 3 2 2 Touring Machines Le modele de Touring Machines Ferguson 1992 utilise lui aussi trois couches pour les compor tements r actifs de planification et de r solution de conflits Le comportement de I agent est cyclique A chaque top d horloge chaque couche propose une action en fonction des donn es fournies par les capteurs de l agent figure 2 4 Un module base de r gles est charg d inhiber les entr es ou les sorties de chacun des blocs pour qu une seule action soit finalement s lectionn e Perceptions Couche mod lisation M Sous syst me Sous syst me Couche planification P de perception d action Couche r active R Actions FIG 2 4 Architecture de Touring Machines 2 2 3 3 Langages pour la gestion de contextes de communi
122. e il est le moment du choix et de l ac tion Simone de Beauvoir L avenir est ce qu il y a de pire dans le pr sent Gustave Flaubert Nous nous int ressons dans ce chapitre a la mani re dont nous devons g rer le partage des res sources processeur pour que nos agents puissent disposer d un comportement extraverti et que l on puisse donner des dates limites aux t ches effectu es par les artifacts de calcul Nous avons d ja re marqu dans les sections 2 1 3 1 et 2 2 2 1 2 que les syst mes temps r el ne sont d aucune utilit dans notre cadre En effet ils imposent des contraintes tr s fortes au niveau de la programmation des pro cessus pour lesquels on veut assurer des d lais d ex cution Nous pr f rons de plus que nos SMA puissent fonctionner sur les syst mes d exploitation classiquement install s sur les machines de bu reau comme Windows ou Unix qui ne sont pas temps r el Nous pouvons ainsi utiliser les propri t s li es a la fonctionnalit de temps partag fournie par ces syst mes Nous consid rons tout d abord que nous disposons d un unique processeur sur lequel s ex cutent les agents et les artifacts Nous verrons ensuite comment il est possible d tendre le mod le que nous proposons a de multiples processeurs Nous attendons des agents qu ils s int ressent a leur environnement Ils doivent tre en perma nence l coute de l ext rieur pour prendre rapide
123. e l agent attend que l ensemble des t ches de calcul ex cut es par ses artifacts se terminent Une fois qu il a migr avec ses artifacts vers la seconde machine il peut demander son nouvel APRC d allouer des ressources processeur pour ses t ches de calcul 116 Chapitre 5 Mise en ceuvre et valuation Visualisateur informations APRC Machine 1 192 168 0 1 Connecter Machine2 192 168 0 2 Connecter Type processeur Intel Pentium 4 Mobile CPU 1 60GHz L600 000MHz Type processeur AMD K6 tm 3D processor 451 065MHz Rapidit 1000 op rations seconde r f rence Rapidit 223 op rations seconde Agents 4 Artifacts 4 Agents 2 Artifacts 2 Agenti Artifactl Agent3 Anifaa3 Agent2 lartifact2 lagens lanifaas lAgent4 lartifacta lAgent6 lArtifac6 Agenda Agenda DL1 DL2 DL3 DL 4 DL1 DL2 DL3 Charge Charge Agents Lage pr cameur Agents Usage processeur Messages Messages 10 54 01 L agent agent 5 demande de migrer 10 54 01 J autorise l agent agent 5 migrer apr s la fin de ses travaux qui se terminent 10 54 32 10 54 55 L agent agent 5 m indique qu il a migr Je ne le prends plus en compte dans le calcul de l ardonn lancement 10 55 24 L agent agent 3 demande de migrer 10 54 32 L agent agent 5 me demande quelle date il peut commencer s ex cuter sur cette machine A l indique l agent agent 5 qu il est 10 54 32 sur ce
124. e bateaux Cette application est une bonne candidate pour mettre en uvre les propositions faites dans cette th se car les agents doivent respecter des d lais impos s par la cadence laquelle les capteurs envoient les informations traiter De plus les traitements peuvent tre longs et sont r alis s par un algorithme contrat 118 Chapitre 5 Mise en ceuvre et valuation Les exp rimentations que j ai men es sur cette application r elle montrent que l utilisation des artifacts de calcul permet d obtenir une mod lisation plus satisfaisante de application Elles montrent galement que la gestion par des APRC des ressources processeur disponibles permet d apporter un gain substanciel par rapport au respect des d lais impos s aux diff rentes taches de calcul entreprises par les agents Chapitre 6 Conclusion Une conclusion c est quand vous en avez assez de penser Herbert Fisher Nous avons pos dans cette th se le probl me du partage des ressources processeur dans les sys t mes multi agents qui ont des d lib rations longues Nous avons regard ce probl me intersection de deux domaines l Intelligence Artificielle car nos agents r alisent pour la plus grande part des t ches de calcul issus de ce domaine et le g nie logiciel puisque nous consid rons que le paradigme agent est une volution majeure pour une programmation simplifi e des syst mes complexes Dans ce cadre nous av
125. e dur e par des contraintes temporelles Ces contraintes temporelles pourraient galement tre plus globales par exemple pour sp cifier qu un artifact n est en fonctionnement qu entre 12 heures et 14 heures Nous aimerions galement pouvoir disposer dans les instructions op ratoires de certaines pos sibilit s du langage T MS La s mantique de l alternative pourrait par exemple tre tendue pour autoriser changer d alternative une fois que l on s est aper u que celle que l on avait choisi aupara vant n aboutit pas Il faut cependant remarquer que ce type d extension est au prix d une plus grande complexit de la partie de l agent charg e d analyser le mode d emploi de artifact 3 4 4 Mode d emploi des artifacts de calcul Nous avons vu dans la section 2 2 1 les diff rentes informations dont on peut disposer sur les algorithmes et quelles sont les diff rentes mani res de les classer Ce qui nous int resse dans cette tude ce sont les informations qui nous permettent de contr ler les algorithmes Nous classons les algorithmes ainsi en fonction de la quantit d information dont on dispose sur leur comportement temporel 72 Chapitre 3 Des outils de calcul pour les agents bo te noire Aucune information n est connue part que c est un algorithme au sens donn dans la section 2 2 1 et donc une fois lanc il se terminera au bout d un temps f
126. e ne pourra tre planifi e cause d une surcharge du syst me 1 APRC ne prendra aucune d cision relative aux t ches d j planifi es pour tenter d allouer du temps processeur 86 Chapitre 4 La gestion des ressources processeur la nouvelle t che Il laissera cette d cision aux agents eux m me Il jouera le r le d interm diaire entre les agents durant cette phase de n gociation Nous avons vu pr c demment que chaque artifact dispose d une horloge personnelle qui lui in dique son temps artifact Les agents quant a eux doivent se r f rer dans leurs raisonnements a une horloge quelconque pour tre conscients du temps L APRC va devoir collecter les dates limites des taches des diff rents artifacts Ces dates doivent toutes se r f rer 4 une horloge commune Nous d finissons cet effet le temps APRC D finition 4 4 Temps APRC Le temps APRC est un temps commun tous les agents qui utilisent les services de l APRC On choisira souvent l horloge syst me pour donner le temps APRC mais il est possible que ce soit une horloge virtuelle qui le donne par exemple dans le cas de simulations pour pouvoir com presser ou dilater le temps Le temps artifact peut tre utilis pour des raisonnements qui doivent tre ind pendants du processeur et de sa charge Au contraire le temps APRC est utilis par des raisonnements qui d pendent de la charge actuelle du processeur 4 1 3 Algorithme
127. e nous avons d velopp s ce jour ont mis en vidence la n cessit de faire cohabiter des agents cognitifs autonomes et des agents qui bien que s ex cutant en parall le et ne d pendant des autres que par des changes de messages ne pouvaient en aucun cas tre consid r s comme autonomes la sp cification de leur comportement tant connue lors de la programmation des autres agents A la diff rence des exemples trait s par l quipe de Bo logne nos artifacts concernaient moins la coordination que la mise en uvre d algorithmes complexes tels que ceux issus des recherches en Intelligence Artificielle propagation de contraintes recherche heuristique que nous ne voulions pas voir trait s directement par les agents afin de ne pas les bloquer si la dur e des traitements devenait prohibitive ce qui se produit assez souvent avec de tels algorithmes Parmi ces applications l une d entre elles m rite une mention particuli re Interloc figure 5 4 Elle concerne la localisation de bateaux partir d avions d observation par la seule utilisation de la direction relative du radar de veille du bateau observ Cette m thode permet l avion de rester dis cret et donc d viter que le bateau prenne conscience du rep rage auquel il est soumis Elle peut tre utilis e pour le rep rage de p troliers op rant un d gazage illicite et bien entendu galement dans de nombreuses applications de nature militaire Le pr
128. e poss dent des param tres d ordre et que les instances dures de ces probl mes se trouvent autour de certaines valeurs critiques de ces param tres Ils esp raient ainsi ouvrir une nouvelle voie o l on pourrait produire des diagrammes de phase que l on utiliserait pour pr dire la difficult de r solution d une instance donn e des probl mes Cette technique n a vraisemblablement pas t mise en oeuvre avec d autres types de probl mes pratiques La d termination d une heuristique tient donc encore beaucoup de r gles d termin es empirique ment en tudiant les propri t s statistiques du probl me sur des instances r alisables en pratique On a pu cependant trouver quelques mod les de conception d heuristiques notamment pour les probl mes d optimisation C est ce qu on appelle des m taheuristiques Les plus connues sont le recuit simul la recherche tabou et les algorithmes g n tiques Les m mes m taheuristiques peuvent tre utilis es pour r soudre des probl mes d optimisation multi objectifs Dans ce dernier cas on recherche un ensemble de solutions non domin es appel le front de Pareto Ce sont les solutions parmi lesquelles on ne peut d cider si une solution est meilleure qu une autre aucune n tant syst matiquement inf rieure aux autres sur tous les objectifs La tendance actuelle est l utilisation conjointe de plusieurs m taheuristiques collaborant la r solution
129. ement r aliste de l algorithme Mouaddib et Zilberstein ont propos le raisonnement progressif comme une alternative aux al gorithmes anytime Zilberstein et Mouaddib 1999 Le raisonnement progressif est utilis dans les cas o il est difficile de d terminer un profil de performance pr cis Il utilise plusieurs niveaux de traitements afin de transformer graduellement une solution impr cise en solution pr cise Nous verrons dans la suite que m me si on n utilise pas souvent dans la pratique des algorithmes anytime beaucoup d id es pr c demment cit es sont r utilis es dans les architectures d agent propo s es 2 2 2 La distribution des calculs approches et techniques L adage diviser pour r gner g n ralement vu de mani re n gative prend un sens int ressant lorsqu il est appliqu l informatique L id e de r soudre un probl me en le d composant en sous parties permet de s occuper de chaque sous probl me individuellement sans se pr occuper de la diffi cult du probl me initial On peut ainsi faire r soudre les sous probl mes par diff rents fils d ex cu tion Il para t aussi indispensable de pouvoir faire r soudre plusieurs probl mes en m me temps un ordinateur Nous pr sentons maintenant les diff rentes approches et techniques associ es qui ont t propo s es pour distribuer des calculs La pr sentation est d coup e en fonction du type de support
130. en existe un ceci pour tous les jeux de donn es d entr e possibles Liu et Layland ont pr sent en 1973 plusieurs algorithmes facilement impl mentables qui ont ces propri t s dont les algorithmes rate monotonic monotonique par taux et Earliest Deadline First premi re ch ance d abord Rate monotonic RM ne sait g rer que des taches p riodiques Le processus lu un instant donn est celui dont l inverse de la p riode est le plus fort C est un algorithme pr emptif et optimal dans la classe des algorithmes priorit s fixes Si l on consid re que les ch ances sont fix es la fin de chaque p riode Liu et Layland ont donn une condition suffisante pour que RM produise un ordonnancement qui respecte toutes les ch ances il suffit que le taux d occupation processeur pour l ensemble des t ches ne d passe pas 69 3 Si l on d passe ce taux d occupation on n est plus certain d obtenir un ordonnancement valide C est une condition n cessaire mais non suffisante il peut exister des ordonnancements valides avec un taux d occupation sup rieur 69 3 Si par contre les ch ances sont inf rieures aux p riodes il n existe plus de condition suffisante bas e sur la charge pour tre certain d obtenir un ordonnancement valide Earliest Deadline First EDF permet de g rer des t ches p riodiques et ap riodiques Il ex cute un instant donn la t che dont la date limite est la plus p
131. ent Dans le cas o la n gociation choue il met jour son tat mental pour ne plus croire qu il peut r aliser la t che demand e B possible r_content 4 1 8 Positionnement par rapport aux syst mes temps r el Nous proposons un ordonnanceur qui permet de respecter des d lais pour les diff rentes t ches ex cut es sur le syst me Or c est justement un des r les du syst me d exploitation que de g rer P ordonnancement des t ches sur le ou les processeurs disponibles Cela est fait diff remment selon les propri t s recherch es Ainsi des syst mes comme Windows ou Unix dits temps partag ga rantissent que tous les processus pourront disposer r guli rement d un quantum de temps processeur Ce qui est recherch ici est l illusion au niveau d abstraction de l utilisateur que tous les processus s ex cutent en m me temps Malheureusement ces syst mes ne garantissent rien sur les dates de fin des t ches 4 1 Gestion des ressources processeur avec des d lais a respecter 99 Cette garantie est en revanche fournie par les syst mes temps r el mais cela est souvent obtenu au prix de la perte de l illusion que les programmes sont toujours actifs En effet les algorithmes classiquement utilis s comme Earliest Deadline First propos dans Liu et Layland 1973 pr f rent lancer une t che jusqu a ce qu elle soit termin e et passer ensuite a la suivante plut t que d assigner de
132. ent systems CPU sharing scheduling interaction coordination sacrifice arti facts process algebra Table des mati res 1 Introduction 1 1 Le but de PIA concevoir des agents 1 2 Le g nie logiciel l am lioration des techniques de programmation 1 3 La combinaison des deux domaines pour am liorer la gestion du temps 1 4 Obj ctifshs scs moau imde e da D RA ee mb Sue 1 5 Organisation du document 2 Contexte 2 1 Expos du probl me 2 1 1 Des agents autonomes extravertis et conscients du temps 2 1 2 Le probl me des longs calculs 2 1 2 1 Utilisation d algorithmes complexes 2 1 2 2 Utilisation de code h rit 2 1 3 Le probl me du partage des ressources processeur 2 1 3 1 Partage d un processeur 2 1 3 2 Partage de plusieurs processeurs 2 1 4 Modele des applications al af paepe a a RM a aa af 2 2 Travaux CONNEXES s aaa a e EE O ae hu E 2 2 1 La gestion du temps d ex cution des algorithmes 2 2 1 1 Algorithmes
133. epr sentation choisie La gestion des signaux d attention permettant une r activit du syst me par rapport aux v ne ments ext rieurs Les contraintes temporelles que les agents peuvent avoir respecter Le partage des ressources de calcul d un ou plusieurs processeurs entre les agents qu ils aient des contraintes temporelles ou non 8 Chapitre 1 Introduction 1 5 Organisation du document Ce document est organis en 7 chapitres Le premier est le chapitre d introduction qui pr sente d une part l objectif et le cadre g n ral de la th se et d autre part la structuration choisie pour ce document Le probl me de la gestion du temps et plus particuli rement celui du partage des ressources processeur fait l objet du chapitre 2 La pr sentation des travaux connexes est organis e en trois parties la section 2 2 1 traite des difficult s qui apparaissent d s que l on utilise un algorithme Les solutions classiques pour g rer simultan ment plusieurs algorithmes et les probl mes qu elles apportent sont d taill es dans la section 2 2 2 La section 2 2 3 pr sente les langages et techniques propos s pour introduire le temps dans les raisonnements les comportements et l interaction des syst mes intelligents avec leur environnement Le chapitre 3 d crit la solution que je propose pour que les agents puissent g rer en paral l le plusieurs c
134. er current_seats La compagnie a rienne est capable d diter des billets et de mettre 4 jour le nombre de si ges disponibles pour un vol donn Les r gles d engagement sont les suivantes COMMIT pass REQUEST IF B p INFORM t pass p true pass IF B p INFORM t pass p COMMIT cust REQUEST issue_bp pass flight time AND B time remaining_seats flight n 2n gt 0 NOT CMT anyone issue_bp pass anyflight time myself DO now 1 update_remaining_seats time flight 1 cust issue bp pass flight time La premi re permet de r pondre une requ te d information sur les vols La seconde permet de prendre en compte un message de r servation d un billet s il y a encore des places disponibles pour le vol demand Le tableau suivant donne un exemple d change entre l agent compagnie a rienne et un agent client Le client r cup re aupr s de la compagnie a rienne les informations sur les vols de Lille Nice pour le 10 avril Il choisit le vol 42 de 8h30 et valide sa r servation La compagnie a rienne se charge enfin d diter le billet une heure avant le d part Agent Action dinont query_which 1march 1h00 dinont airline 10april time flight lille nice num airline INFORM lmarch 2h00 dinont 10april 8h30 flight lille nice 42 airline INFORM lmarch 2h00 dinont 10april 10h0
135. er que si l on met autant en avant le concept d autonomie la complexit qu on essaie de supprimer de la vision globale du syst me peut se reporter dans la conception de chacun des agents ou dans les interactions entre les agents Il est d s lors important de trouver les limites ne pas d passer et trouver un mod le d agent qui favorise l autonomie tout en restant simple 3 1 Position du probl me 53 Nous pensons que l autonomie est le point d orgue du paradigme agent qui lui permet de se diff rencier du paradigme objet au niveau de l impl mentation des syst mes Si on ne prend pas garde de pr server l autonomie jusqu au bout on n aura eu les b n fices de la programmation orient e agent que dans la phase de mod lisation et une bonne partie de ses bienfaits auront disparus dans l implantation finale La solution utilisant deux classes d agents ne para t pas satisfaisante et nous devons nous r soudre voir si l on aurait un int r t introduire un nouveau type d entit s dans les SMA 3 1 4 Une nouvelle entit L introduction d un nouveau type d entit s dans les SMA est d licate Il faut identifier de ma ni re pr cise un nouveau concept suffisamment diff rent de celui d agent ce qui est difficile tant le concept d agent est abstrait Il est d ailleurs tr s souvent possible de s en sortir en identifiant plu sieurs classes d agents diff rentes comme ce qui a t propos d
136. es ressources 4 4 Synth se 103 processeur qui leur ont t allou es Nous avons galement vu comment il tait possible de b n ficier des services de l APRC dans des SMA o les agents n ont pas de d lais respecter mais ont par moments des besoins plus importants en ressources processeur Le modele de base fonctionne avec un APRC pour g rer un unique processeur Nous pouvons tr s facilement tendre ce mod le plusieurs processeurs en utilisant un APRC par processeur Dans ce nouveau cadre il para t int ressant de donner la possibilit de lancer un nouvel agent ou un nouvel artifact sur un autre processeur si celui sur lequel on travaille devient surcharg La migration d agents et d artifacts est galement une possibilit de la plate forme multi agent Alba que nous utilisons et qui est d crite dans le chapitre suivant Un agent devrait donc disposer des informations n cessaires la d cision de migrer sur un autre processeur Nous tendons pour cela les comp tences de l APRC pour qu il soit capable de mesurer de diff rentes mani res la charge du processeur qu il g re qu il change ces informations avec les autres APRC du syst me et qu il puisse donner des indications aux agents sur les processeurs vers lesquels ils peuvent migrer 104 Chapitre 4 La gestion des ressources processeur Chapitre 5 Mise en uvre et valuation valuer c est cr er coutez donc vous qui tes cr ateurs
137. essus ne partagent pas de m moire tandis que tous les processus l gers qui constituent un processus partagent la m me m moire Cette possibilit de pouvoir partager de la m moire entre les diff rents fils d ex cution est tr s in t ressante mais elle pose un nombre incroyable de difficult s de programmation Lee 2006 effectue le constat que la programmation avec les processus l gers fait perdre des propri t s essentielles de la 2 2 Travaux connexes 23 programmation s quentielle compr hensibilit comportement pr dictible et d terminisme La pro grammation parall le revient donc en grande partie tenter de supprimer l ind terminisme apport par l introduction des processus l gers C est une t che fastidieuse m me sur des cas simples Lee montre sur l exemple pourtant minimaliste du mod le de conception observateur Gamma ef al 1993 les difficult s et subtilit s auxquelles on est confront s Il d taille les raisonnements qu il convient de mener pour passer d une impl mentation valide pour un processus l ger une impl mentation va lide avec plusieurs processus l gers Bien que l exemple est donn sur un mod le de conception tr s simple les raisonnements ne sont pas triviaux et mettent parfois en jeu 3 ou 4 processus l gers pour faire appara tre une situation d interblocage La programmation multi t che n est pas ais e mais elle apporte illu
138. est le cas des algorithmes que nous avons appel bo tes noires Un agent qui veut avoir la ma trise de ses calculs bo tes noires ne va pas se lancer dans l ex cution compl te et en une seule fois de ceux ci Il va plut t d cider de les commencer pendant un certain temps de voir o il en est arriv et d ventuellement les continuer pendant une nouvelle p riode de temps Il fera cela jusqu la terminaison de ses traitements ou jusqu ce qu il renonce les terminer C est pourquoi nous faisons dans la suite la distinction suivante entre les mots traitement et t che D finition 4 3 Traitement t che Un traitement est une instanciation d un algorithme sur des don n es d entr e particuli res Une t che est l ex cution d un traitement pendant un temps artifact fix Un traitement peut tre r alis en une ou plusieurs t ches Lorsqu une t che se termine une nou velle peut continuer le traitement o il en tait arriv Si l on fait le lien avec le langage de mode d em ploi des artifacts propos dans le chapitre pr c dent un traitement est la r alisation d une instance de mode d emploi d un artifact jusqu au bout de celui ci Les modes d emploi que nous fournissons pour nos artifacts de calcul sp cifient que l agent dispose tout moment de la possibilit d appeler les ac tions pause et resume ou pause_computation et resume_computation Une t che sera donc d finie sur la
139. etit a petit les diff rentes facettes de la gestion du temps Nous avons mis en place dans cette th se les m canismes les plus bas niveau pour faciliter la gestion du temps dans nos syst mes multi agents Cette tape nous permet de r duire le foss qui existe entre les niveaux d abstraction du syst me d exploitation et des syst mes multi agents Nous disposons ainsi de bases solides sur lesquelles nous pourrons l avenir ajouter d autres couches charg es de g rer les autres aspects li s au temps Dans cette d marche nous voulons utiliser au maximum sans les modifier les fonctionnalit s propos es par les syst mes d exploitation Cela concerne notamment la partie ordonnancement si l ordonnanceur du syst me d exploitation ne dispose pas de toutes les propri t s n cessaires nos syst mes multi agents nous fournirons les fonctionnalit s manquantes sous forme d une biblioth que de notre plateforme multi agents Du point de vue g nie logiciel la question laquelle nous voulons r pondre est la suivante com ment programmer des agents utilisant des techniques de l IA pour b n ficier des nouveaux principes li s ce paradigme comme le couplage tr s faible entre les agents tout en conservant ou am liorant les b n fices li s aux pr c dents principes simplicit productivit efficacit r utilisabilit Nous donnons une importance tr s grande aux principes de simplicit et de fiabilit No
140. eur mais du point de vue agent les agents devraient pouvoir dynamiquement apprendre utiliser de nouveaux outils de calcul disponibles dans le syst me multi agent pour atteindre leurs buts Pour cela les outils de calcul devraient disposer d un mode d emploi qui indique aux agents comment les utiliser 2 1 3 Le probl me du partage des ressources processeur 2 1 3 1 Partage d un processeur Les syst mes multi agents sont par d finition des syst mes distribu s mais il est tr s souvent inconcevable de consid rer que chaque agent dispose de son propre processeur et qu il sera libre d utiliser toutes les ressources disponibles pour son seul usage personnel Il arrive d ailleurs tr s fr quemment que l ensemble des agents d un SMA s ex cutent sur un unique processeur Nous devons donc nous r soudre ce que nos agents partagent les ressources de calcul d un unique processeur Nous devrons fournir des outils pour que les agents puissent respecter les d lais qu ils peuvent avoir sur leurs t ches de calcul tout en conservant au maximum leur autonomie Il faudra galement veiller un autre point tr s important si les agents parta gent un unique cerveau pendant le temps o un agent l utilise les autres perdent conscience Nous devons donc fournir aux concepteurs de SMA un niveau d abstraction auquel les agents pourront disposer de la propri t de conscience du temps dont nous parlions dans la sec
141. facilement et sans risque d apparition de dysfonctionnements non pr vus Le temps appara t de mani re transverse et sous de multiples formes dans les syst mes multi agents cognitifs Contrairement aux objets qui subissent le temps les agents cognitifs sont pro actifs Ils ont la responsabilit de d cider quand ex cuter les actions qui leur permettent d atteindre leurs buts Ils ont ainsi besoin d un module pour planifier des actions g rer leurs d pendances Un autre module peut tre charg d ordonnancer les diff rentes t ches La planification et l ordonnancement sont deux probl mes difficiles auxquels on se confronte dans la plupart des applications multi agent Lorsque les actions planifi es s inscrivent dans la dur e il faut mettre en place un dernier module trop souvent n glig charg de l ex cution des actions Ce module doit tre capable de d marrer des actions de suivre leur d roulement de lire leur tat et modifier leurs param tres pendant l ex cution de v rifier leur bonne terminaison et ventuellement de les arr ter si l agent le d cide Le fonctionnement d un agent peut tre cadenc par une horloge par l arriv e d v nements ex t rieurs ou les deux la fois Lorsque c est une horloge qui donne le rythme il convient d tre certain que l ensemble des traitements n cessaires un cycle pourront tre effectu s avant le prochain top d horloge Ce point peut poser p
142. ff rentes informations qui lui sont donn es courbes d utilit des actions en fonction du temps seuils au dessous desquels il faut absolument d clencher une action courbes de la pression du sang et du rythme cardiaque 2 2 Travaux connexes 33 2 2 3 2 Mod les d agents hybrides La dualit cognitif r actif des agents a t remarqu e d s le d but des travaux de recherche sur les agents En effet un agent doit tre capable d effectuer des raisonnements a long terme tout en tant capable de prendre en compte temps les changements dans l environnement La litt rature propose de construire un agent en plusieurs couches Les deux principaux mod les propos s sont InteRRaP Muller et Pischel 1993 et Touring Machines Ferguson 1992 Nous les d crivons dans les paragraphes suivants 2 2 3 2 1 InTeRRaP Un agent InTeRRaP est constitu de trois couches Muller et Pischel 1993 la premi re pour les comportements de type r flexe connus la seconde pour les comportements n cessitant de la planifi cation et la troisi me pour les comportements mettant en uvre la coop ration d autres agents Lors qu un agent per oit un changement dans l environnement une r action est d abord cherch e dans la premi re couche Si aucune r action n est pr vue dans cette couche la seconde couche tente d en trouver une en planifiant un ensemble de r actions de la premi re couch
143. fice request s_content T s_timeout lrefuse s_content lpropose_sacrifice s_ content commit_sacrifice s_ content cancel_sacrifice s_content Def_Negotiation_Participant FIG 4 8 Instructions op ratoires de l APRC Def_CA Management est l instruction op ratoire utilis e par les agents pour interagir avec P APRC lorsqu ils ont un travail donner un artifact de calcul Def_Negotiation_Initiator est l instruction op ratoire utilis e si une inconsistence est d tect e par 1 APRC lors de l ajout des 4 1 Gestion des ressources processeur avec des d lais a respecter 97 Action Pr condition request B possible r_content amp B have_oi r_content start_negotiation B work_importance r_content id amp B remain_work_load r_content s_content imp s_content load get_sacrifice_request refuse B more_important s_content my_work propose_sacrifice B more_important s_content my_work amp B can_sacrifice_work_load s_content load Perception Effet accepted B have_oi r_content ca_oi rejected ES negotiation_failed B possible r_content negotiation_succeeded have_oi i_negotiation r_content new_sacrifice_request commit_sacrifice Cancel_sacrifice FIG 4 9 Lien s mantique entre les IO de l APRC et l tat mental de l agent contraintes
144. g n ration s est plut t focalis e sur les API de gestion du cycle de vie des agents et sur la communication inter agents La seconde g n ration apporte une vision plus haut niveau en proposant une architecture compl te pouvant tre vue comme un syst me d exploitation pour syst mes multi agents L architecture des agents ainsi que l architecture interne de DECAF sont tr s modularis s et chaque module s ex cute dans un processus l ger distinct Cela autorise par exemple de pouvoir tr s facilement d ployer un simple agent sur une plateforme multi processeurs Cependant comme nous 48 Chapitre 2 Contexte l avons signal plus haut dans la section 2 2 2 1 1 cela complique norm ment criture du code des agents DECAF est int ressant lorsque l on veut rapidement d velopper des syst mes multi agents de mani re visuelle mais il ne propose pas d outils pour contr ler de mani re fine le lien entre le niveau agent et le niveau syst me 2 3 Synth se Nous avons d crit le probl me que nous voulons r soudre dans cette th se nous voulons int grer tous types d algorithmes complexes dans nos SMA en particulier ceux issus du domaine de l Intel ligence Artificielle Nous voulons que cela se fasse de mani re respecter des propri t s que nous attribuons nos agents autonomie extraversion et conscience du temps Enfin nos agents doivent tre capables de se partager les ressources proce
145. i existe t il une coloration k couleurs du graphe G o k et G sont tout les deux des param tres du probl me 2 2 1 2 Classes de complexit Pour r soudre un probl me avec un ordinateur il ne suffit pas de trouver un algorithme car les algorithmes eux m me posent probl me Un algorithme aura beau tre concis et l gant il ne sera d aucune utilit s il n est pas possible de le faire fonctionner en pratique sur les architectures mat rielles dont on dispose Cette impossibilit d utilisation peut notamment appara tre si l algorithme utilise trop de m moire ou s il s ex cute dans des temps irraisonnable C est pourquoi depuis les ann es 1970 une tude syst matique des propri t s des algorithmes a t men e Elle a aboutie une classification des probl mes et de leurs algorithmes associ s en fonction de leur difficult Tout d abord nous pouvons classer les algorithmes en fonction de la quantit de m moire ou du nombre d instructions dont ils vont avoir besoin pour s ex cuter Ces deux quantit s d pendent de la 16 Chapitre 2 Contexte taille des donn es en entr e De plus il est la plupart du temps inutile de comparer les performances des algorithmes sur des tailles de donn es petites C est essentiellement le comportement asympto tique qui nous int ressera Pour cela on utilise couramment la notation dite de Landau en r alit introduite un peu plus t t par Bachmann
146. ie Ici schedule static 5 indique que les 5 premi res it rations seront donn es au premier processus l ger les 5 suivantes au second Lorsque la quantit de calcul n est pas identique pour chaque tour de boucle il est possible d indiquer un ordonnancement dynamique o un nouveau travail est donn un processus l ger quand il a termin le pr c dent sans s occuper de l tat d avancement des autres OpenMP propose galement des primitives de synchronisation BARRIER pour indiquer un point qui doit tre atteint par tous les processus l gers avant de pouvoir continuer SINGLE END SINGLE pour indiquer une section de code qui ne doit tre ex cut e que par un seul processus l ger CRITICAL name END CRITICAL name pour encadrer les sections critiques dans lesquelles on ne peut avoir qu un seul processus l ger la fois OpenMP constitue une bonne encapsulation des processus l gers mais ne supprime pas totalement les probl mes d interblocages La philosophie a l oppos de celle de MPI est difficle rapprocher de ce que nous voulons pour nos syst mes Nous pr f rons voir nos agents comme des entit s qui d marrent des taches de calcul et dialoguent avec elles plut t que comme un programme unique dans lequel on fait appara tre du parall lisme quand le besoin s en fait sentir 2 2 2 2 Cas multi machine et solutions r seau Dans les sections pr c dentes nous avons vu comme
147. ils vont encapsuler dans le formalisme du langage de mode d emploi et g rer au niveau des agents la d l gation des t ches de calcul en suivant le mode d emploi pr c demment d crit L APRC est quant lui un artifact de coordination r utilisable permettant de g rer les ressources processeur affect es aux agents et aux artifacts de mani re g n rique 122 Chapitre 6 Conclusion Chapitre 7 Perspectives On ne fait jamais attention a ce qui a t fait on ne voit que ce qui reste a faire Marie Curie Lorsqu iln y a plus rien faire que faites vous Koan zen Nous avons utilis pour cette tude une approche ascendante Cette th se nous a permis de mettre en place les couches les plus basses permettant de g rer au mieux les d lib rations longues dans nos agents Nous pouvons d ja identifier quelques am liorations qui seront n cessaires dans ce que nous venons de proposer avant de pouvoir construire les couches sup rieures Cela concerne le mode d emploi des artifacts et le mod le d agent que nous utilisons Nous pourrons ensuite passer a une tude beaucoup plus globale sur la gestion du temps dans les syst mes multi agents qui utilisent des artifacts de calcul Nous pensons galement que notre approche utilisant les artifacts permet de nous rapprocher d autres communaut s travaillant sur d autres types de syst mes distribu s 7 1 Mode d emploi des artifacts Nous avons d j soule
148. incipe est simple gr ce un capteur sp cifique analogue un goniom tre l avion mesure intervalles r guliers correspondant la p riode du radar du bateau la direction de ce dernier par rapport l avion Les angles mesur s sont impr cis et peuvent m me manquer en raison des conditions ambiantes difficiles pr valant dans ce type d application Si le bateau tait immobile une simple triangulation permettrait tr s rapidement de le localiser Mais ce n est bien s r pas le cas N anmoins le calcul n est possible que si la vitesse du bateau est no tablement inf rieure celle de l avion un facteur 10 par exemple et si la trajectoire de l avion est correctement choisie conditions en g n ral faciles satisfaire Le calcul est effectu par un algorithme 5 2 Pr sentation de l application Interloc 111 Interloc 2 2 Map Explorer boat cherbour rapid FIG 5 4 Copie d cran d Interloc de propagation d intervalles sur les domaines continus Lhomme 1993 qui exploite la diff rence de vitesse entre bateaux et avion pour fournir une localisation qui est progressivement r duite au fur et mesure que les donn es arrivent La propagation d intervalle est particuli rement bien adapt e ce genre de calcul car d une part elle permet d injecter de nouvelles contraintes de mani re incr mentale contraintes tablies partir des mesures re ues et d autre part de
149. inge llancer_cycle fin_cycle laver_linge Nous voulons pouvoir indiquer a l agent quand il pourra d cider d ex cuter l action lancer_cycle Cela s exprime ainsi Action Pr condition Perception Effet lancer_cycle B linge_sale fin_cycle B linge sale L agent d cidera d ex cuter l action lancer_cycle s il croit op rateur B que son linge est sale Les effets li s la perception fin_cycle permettent de mettre jour la base de connaissances pour que l agent sache maintenant que son linge est propre Nous pouvons galement utiliser les param tres des actions et perceptions dans cette table Pre nons par exemple le cas d un agent qui aurait besoin de conna tre diff rentes informations d tenues par un artifact L instruction op ratoire qui lui permet de le faire est la suivante recuperer_info demande_info NOM_INFO valeur_info NOM INFO VALEUR Le lien s mantique entre cette instruction op ratoire et la base de connaissances de l agent permet d indiquer l agent qu il peut lancer l action demande_info NOM_ INFO lorsqu il a besoin de conna tre la valeur de l information dont le nom est NOM_INFO 70 Chapitre 3 Des outils de calcul pour les agents Action Pr condition demande_info NOM_INFO B besoin_info NOM_INFO Perception Effet valeur_info NOM_INFO VALEUR B valeur NOM_INFO VALEUR B
150. ini dur e d ex cution connue Nous ne disposons que de la dur e d ex cution mais pas d infor mations sur ce qui se passe entre le d but et la fin de l ex cution contrat L algorithme peut tre contr l en lui donnant une dur e au bout de laquelle il s arr te pour fournir le r sultat courant Il est possible de le relancer pour une nouvelle p riode de temps partir de l endroit o il s tait arr t On ne dispose pas d informations sur ce qui se passe pendant chaque p riode d ex cution Un agent qui utilise un tel algorithme doit correctement choisir la dur e des contrats Trop grandes on se retrouve dans le flou trop longtemps trop petites l agent va devoir reconsid rer trop souvent s il poursuit ou arr te le calcul interruptible On n a plus besoin de la notion de contrat car l algorithme est capable de fournir un r sultat tout moment anytime On dispose d une information suppl mentaire le profil de la qualit du r sultat en fonction du temps allou l ex cution de l algorithme On peut consid rer que cette classification est galement un classement des algorithmes du moins favorable bo te noire au plus favorable anytime Nous donnons dans les paragraphes suivants les modes d emploi g n riques pour l encapsulation des algorithmes de cette classification dans des arti facts de calcul 3 4 4 1 Algorithme bo te noire Le mode d
151. instants interm diaires des checkpoints auxquels on peut mettre jour l tat actuel de l action de mani re incr mentale Les checkpoints n interrompent pas les actions Ils peuvent tre rapproch s des interruptions utilis es dans les processeurs et les syst mes d exploitation en ce sens qu ils obligent certaines actions tre entreprises quand le checkpoint arrive Une checkpoint expression d crit les checkpoints associ s une action Ils peuvent tre sp cifi s de mani re absolue ou relative par rapport la date de d but de l action On peut galement les associer des v nements comme la r ception d un message 2 2 Travaux connexes 47 La mise jour d un tat est sp cifi e par un timed effect triple d fini ainsi lt cpe Add Del o cpe est une checkpoint expression et o Add et Del sp cifient les modifications effectuer sur l tat sous forme de listes de faits ajouter ou supprimer On d crit une action qui s inscrit dans la dur e avec un nom sous la forme a X1 Xn un sch ma sous la forme T1 Tn qui indique que la variable Xi doit tre du type Ti une condition d appel de code appel e la pr condition de l action une expression qui d finit la dur e de l action unensemble de timed effect triple L historique des tats est conserv et il est possible de I utiliser dans le programme de agent tout comme l his
152. ir de cet intervalle 4 6 Il faut absolument consacrer la quantit ES R de l nergie disponible dans l intervalle cou rant pour les t ches k dont la variable C y vaut 1 4 1 3 2 4 Exemples de r solution Nous consid rons pour ce paragraphe que le processeur peut ex cuter 1000 op rations par se conde Les requ tes de t ches ET DL sont formul es ainsi ET est une dur e en temps artifact donn e en nombre d instructions r aliser DL est la date limite pour la t che en temps APRC donn e en secondes Pour simplifier notre premier exemple nous occultons le fait que APRC et qu un agent s ex cutent Nous consid rons uniquement trois artifacts Al A2 et A3 qui ex cutent chacun une t che de calcul Les requ tes sont 3000ops 4s 27000ps 6s et 20000ps 8s Nous remarquons qu il est impossible d ex cuter enti rement la t che 2 uniquement dans le second intervalle Celui ci a une du r e de deux secondes et donc une capacit d ex cution de seulement 2000 op rations Il faut ex cuter au moins 700 op rations de la t che 2 dans le premier intervalle La figure 4 3 illustre cela on doit arr ter la t che 3 qui tournait en parall le de 1 et 2 pour que la somme des parties de la t che 2 dans le premier intervalle puisse atteindre la valeur de 700 op rations 4 1 Gestion des ressources processeur avec des d lais a respecter 91 Utilisation processeur
153. l 7 2 16 19 Graham 2001 GRAHAM J R 2001 Real time Scheduling in Distributed Multiagent Systems Th se de doctorat University of Delaware Graham et al 2003 GRAHAM J R DECKER K S et MERSIC M 2003 Decaf a flexible multi agent system architecture Autonomous Agents and Multi Agent Systems 1 1 2 1 27 Grass 1996 GRASS J 1996 Reasoning about computational resource allocation Crossroads 3 1 16 20 Guessoum et Dojat 1996 GUESSOUM Z et DOJAT M 1996 A real time agent model in an asynchronous object environment In van HOE R diteur Seventh European Workshop on Mo delling Autonomous Agents in a Multi Agent World Hewitt et al 1973 HEWITT C BISHOP P et STEIGER R 1973 A universal modular actor formalism for artificial intelligence In IJCAI pages 235 245 Horling 1999 HORLING B 1999 http mas cs umass edu research taems white 130 Bibliographie Horvitz et Rutledge 1991 HORVITZ E et RUTLEDGE G 1991 Time dependent utility and ac tion under uncertainty In Proceedings of the seventh conference 1991 on Uncertainty in artificial intelligence pages 151 158 San Francisco CA USA Morgan Kaufmann Publishers Inc Horvitz 1990 HORVITZ E J 1990 Reasoning about beliefs and actions under computational resource constraints n HENRION M SHACHTER R D KANAL L N et LEMMER J F diteurs Uncertainty in Artificial Intelligence 5 pages 301 324 El
154. l impl mentation de Prolog que nous utilisons ne les fournit pas Mon stage de DEA Dinont 2003 a consist 4 proposer un modele d agent et un langage sous forme de biblioth que Prolog pour g rer ces aspects Le mod le propos est base d automates tem poris s Les agents peuvent instancier diff rents automates pour leurs diff rentes conversations Les messages sont aiguill s vers le bon automate en fonction d un identifiant de conversation d fini par l initiateur d une conversation Une des sp cificit s de ce mod le consiste tre oblig de sp cifier un timeout et l action correspondante pour chaque transition de l automate correspondant une attente de message J ai galement propos une conversion automatique du fonctionnement global des agents utilisant ce mod le en r seaux de P tri color s Apr s mon DEA le mod le a continu voluer Il est actuellement bas sur la notion de Fil De Raisonnement FDR La figure 5 3 illustre l architecture d un agent utilisant les FDR Chaque FDR peut tre vu comme un contexte Un mod le de FDR est d crit comme une machine tats finis tendue repr sentant des connaissances proc durales associ es un contexte Quand un FDR est instanci une m moire locale est galement cr e Elle permet de stocker les donn es rela tives ce contexte De plus une m moire globale est partag e par les diff rents FDR de l
155. la qualit correspondante dans le profil de performance afin de les consid rer comme des m thodes diff rentes pour r aliser une t che Cette m me tude a mis en vidence la possibilit de consid rer Design to Time comme un algorithme anytime Design to Time utilise des heuristiques pour r duire la complexit initiale de O n une complexit polyno miale Design to Criteria peut tre vu comme une g n ralisation de Design to Time Le temps n est plus le seul crit re qui guide la recherche de solutions L agent dispose d une fonction objectif atteindre 2 2 Travaux connexes 45 Elle peut tre exprim e comme des contraintes sur la qualit le co t et la dur e de chaque t che On fournit galement un ensemble de param tres qui permettent Design to Criteria de diriger sa recherche dans la bonne direction Le probl me a une complexit tr s importante et l algorithme a t tr s fortement optimis Il est capable de trouver une solution des probl mes ayant une centaines de t ches en quelques secondes Vincent ef al 2001 utilise Design to Criteria dans un cadre temps r el mou T MS a t int gr dans un framework pour la coordination entre agents nomm MQ Dans ce syst me la coordination est centr e ordonnancement et utilise GPGP Generalized Partial Global Planning Decker 1995 La figure 2 7 donne une vue simplifi e de l architecture d un agent
156. la r gle T A EXP pour viter l tat d erreur e il le fait en ex cutant l action attendue avant l expiration du timeout Les r gles T P PASS et T P EXP ont la m me fonction mais quand une perception est atten e T P PASS g re le passage du temps et T P EXP fait tomber l instruction op ratoire dans l tat d erreur y quand le timeout expire Les artifacts tant con us pour respecter la lettre leur mode 64 Chapitre 3 Des outils de calcul pour les agents d emploi il n y a aucune raison pour que l tat d erreur y soit atteint L agent peut donc interpr ter ces r gles dans le sens ot il dispose de la garantie que la perception qu il attend se produira avant l expiration du timeout La r gle T ACT supprime le timeout quand l agent d cide d ex cuter la sp cialisation a de Paction a La r gle T COMP fait de m me quand une perception est r alis e avant que le timeout expire 3 4 3 Nos extensions Le mod le th orique pour d crire les modes d emploi des artifacts base d alg bre de processus nous parait incomplet Nous pensons que cette base de travail est peut tre trop rigide pour pouvoir d crire des modes d emploi complexes et flexibles Nous avons cependant d cid de travailler dans un premier temps avec ce mod le en attendant de trouver un autre langage qui nous conviendra mieux Nous avons identifi un certain nombre de manquements au langage de base
157. le cadre de IODA il n a pas t n cessaire d introduire la notion d artifact La notion la plus centrale est celle d interaction et la s paration des agents en deux classes suffit D ailleurs il n y a pas du tout de diff rence entre effectuer une action si la cible est un agent anim ou un agent inanim Par exemple un agent peut indiff remment effectuer l interaction taper 3 8 Synth se 81 sur une porte ou sur un autre agent Avec les agents et les artifacts il y a une diff rence soulign e plus haut entre les interactions avec d autres agents ou avec un artifact Dans le premier cas on interagit au moyen d actes de langages et dans le second cas au travers des actions et des perceptions Cette approche centr e interaction est utilis e chez SMAC 4 la fois dans des syst mes cognitifs projet CoCoA et dans des syst mes r actifs projet SimuLE CoCoA a pour objectif d appliquer cette approche aux syst mes cognitifs Dans Co CoA l interaction est compos e de trois parties Devigne et al 2005a Devigne et al 2005b Devigne et al 2004 les conditions Ce sont les conditions n cessaires l ex cution de interaction Elles portent sur des propri t s des agents de la simulation L agent qui veut d clencher une interaction doit d abord r soudre ces conditions la garde C est une condition particuli re qui a t isol e des autres pour g
158. le des t ches ex cut es sur le processeur Le calcul de l ordonnancement pourrait tre d centralis au sein de chaque agent Lorsqu un agent aurait une nouvelle t che r aliser il calculerait le nouvel ordonnancement et indiquerait aux autres agents les informations sur la planification de la nouvelle t che Cette solution bien que tout fait dans l esprit agent est pourtant totalement inefficace et tr s difficile mette en uvre En effet il faudrait diffuser des informations tous les agents chaque nouvelle t che planifi e Il serait galement tr s difficile d assurer que tous les agents disposent bien des toutes derni res informations avant de lancer le calcul de l ordonnancement pour une nouvelle t che Comme nous nous pla ons dans un premier temps sur un unique processeur nous consid rons que la meilleure solution est d int grer le calcul de l ordonnancement au sein d une entit d di e et unique 4 1 2 Un artifact de coordination pour le partage du processeur Nous proposons d utiliser un artifact de coordination pour g rer l acc s aux ressources du proces seur Il sera nomm Artifact de Partage des Ressources de Calcul APRC Son r le sera de calculer l ordonnancement pour l ensemble des processus s ex cutant au sein du SMA les agents les arti facts de calcul et APRC lui m me Il ne devra pas nuire l autonomie des agents C est pourquoi lorsqu une nouvelle t ch
159. lles sont les techniques qui ont t propos es pour contourner ces difficult s Dans un second temps nous verrons quelles approches et techniques ont t propos es pour b n ficier des capacit s de distribution des calculs des syst mes informatiques actuels Nous verrons enfin quelles sont les solutions actuellement propos es pour que des agents puissent g rer plusieurs contextes d ex cution simultan s 2 1 Expos du probl me 2 1 1 Des agents autonomes extravertis et conscients du temps Le paradigme agent appara t comme un moyen de r duire la complexit structurelle des syst mes En concevant une application comme un ensemble d entit s ind pendantes lors de l ex cution on r duit le couplage entre les diff rents l ments du syst me et donc la programmation des entit s du syst me se fait de mani re plus ind pendante galement Nous avons remarqu que la gestion du temps appara t de mani re transverse aux diff rentes fonctionnalit s des agents intelligents Nous visons des applications dans lesquelles les agents ont des calculs longs r aliser principa lement des calculs issus d algorithmes de l Intelligence Artificielle et peuvent avoir des contraintes 9 10 Chapitre 2 Contexte temporelles respecter pour ces t ches de calcul Le paradigme agent repose sur des principes comme P autonomie ou la r action rapide aux changements de l environnement Si l on perd ces propri t s on a
160. mat riel de la distribution Nous mettons en vidence les avantages et les inconv nients du point de vue g nie logiciel et du point de vue de l utilisateur du syst me Cela nous permettra de d terminer dans les chapitres suivants comment nous voulons implanter le parall lisme l int rieur de nos agents et aussi entre eux 2 2 2 1 Cas d une machine Il n est pas n cessaires de disposer de plusieurs processeurs pour voir des avantages la s paration de ce qui est ex cut sur le processeur en plusieurs contextes Cette s paration permet d ex cuter plusieurs programmes ind pendants par exemple pour tre capable de g rer plu sieurs utilisateurs simultan ment d ex cuter des fils d ex cution qui d pendent les uns des autres et sont capables d acc der aux m mes zones de m moire On peut ainsi d couper un programme en plusieurs sous programmes qui s ex cutent de mani re concurrente Les fils d ex cution programmer contiennent moins de code mais il faut faire attention la complexit importante apport e par les m canismes de synchronisation qu il faut mettre en place Nous d taillons maintenant les techniques propos es pour r aliser ce parall lisme et la synchronisa tion associ e 22 Chapitre 2 Contexte 2 2 2 1 1 Le multi t che La mani re la plus simple pour g rer plusieurs programmes simultan ment consiste demander aux programmeurs d indiquer au syst me d
161. ment en compte les changements dans l environne ment et r pondre aux sollicitations des autres agents Pour des agents logiciels cela revient disposer 83 84 Chapitre 4 La gestion des ressources processeur r guli rement d assez de temps processeur qu ils utiliseront pour se remettre en phase avec leur envi ronnement Nous d finissons les p riodes d activit et d inactivit des entit s de nos syst mes et nous as socions aux artifacts une horloge temps artifact qui permet d valuer la quantit de travail qu un artifact a r alis un instant donn D finition 4 1 Entit active entit inactive Une entit du SMA est inactive sur une p riode de temps donn e si elle ne dispose d aucun acc s processeur sur cette p riode Elle est active sur la p riode consid r e dans le cas contraire D finition 4 2 Temps artifact Le temps artifact avance au rythme des op rations ex cut es par L artifact Le temps artifact est propre chaque artifact il y a une horloge temps artifact par artifact qui peut avancer un rythme diff rent pour chacun d eux Nous avons pr sent dans le chapitre pr c dent comment il est possible de d crire le mode d em ploi de tous types d algorithmes encapsul s dans les artifacts En particulier les agents sont capables de d l guer des calculs dont les dur es en temps artifact ne sont pas forc ment connues avant de les avoir r alis s C
162. mming on numeric intervals 3rd Int Workshop on Software Engineering Artificial Intelligence and Expert Systems for High Energy and Nuclear Physics Bussman et Demazeau 1994 BUSSMAN S et DEMAZEAU Y 1994 An agent model combining reactive and cognitive capabilities In Intelligent Robots and Systems 94 Advanced Robotic Sys tems and the Real World Buytaert 2005 BUYTAERT K 2005 openmosix past present and future In UKUUG 05 Cappello et al 2005 CAPPELLO F DJILALI S FEDAK G HERAULT T MAGNIETTE F NORI V et LODYGENSKY O 2005 Computing on large scale distributed systems Xtrem web architecture programming models security tests and convergence with grid Future Gener Comput Syst 21 3 417 437 Carabelea et al 2003 CARABELEA C BOISSIER O et FLOREA A 2003 Autonomy in multi agent systems A classification attempt Jn NICKLES M ROVATSOS M et WEISS G diteurs Agents and Computational Autonomy volume 2969 de Lecture Notes in Computer Science pages 103 113 Springer 127 128 Bibliographie Cheeseman et al 1991 CHEESEMAN P KANEFSKY B et TAYLOR W M 1991 Where the Really Hard Problems Are In Proceedings of the Twelfth International Joint Conference on Arti ficial Intelligence IJCAI 91 Sidney Australia pages 331 337 Culler et al 1999 CULLER D E SINGH J P et GUPTA A 1999 Parallel Computer Architec ture A hardware software approach
163. mpte un nombre d agents variable Il faut cependant prendre garde a ce que les nouveaux agents ne d marrent pas n importe quand car cela emp cherait les artifacts de tenir leurs d lais Il faut donc l autorisation de l APRC pour que les nouveaux agents d marrent un moment o ils ne perturbent pas les engagements pris auparavant Cela apporte juste quelques modifications dans la primitive qui permet de lancer l ex cution d un nouvel agent Cette primitive ne lance pas tout de suite le nouveau processus mais envoie une requ te 1 APRC pour savoir quelle date planifier la cr ation du nouvel agent Dans l impl mentation actuelle 1 APRC renvoie syst matiquement en r ponse cette requ te la date limite la plus lointaine pour l ensemble des engagements actuels Cela permet de ne pas devoir recalculer un nouvel ordonnancement pour l ensemble des t ches d j planifi es L APRC prend en compte qu partir de la date qu il a renvoy e il y aura un agent de plus sur le processeur et donc les futures t ches seront planifi es en prenant en compte cette information 4 1 4 2 Utilisation processeur des agents Nous avons galement tudi la port e de l hypoth se faite sur l utilisation processeur des agents Nous consid rons dans l algorithme d ordonnancement qu un agent dispose de 1 1 nb_agents nb_artifacts du processeur Quand il y a une proportion plus importante d agents que d artifacts la
164. n place un syst me de priorit entre les processus temps r el pour garantir que certains pourront tou jours s ex cuter m me en cas de surcharge Il convient cependant de remarquer que dans ce cas la synchronisation entre les t ches par utilisation de s maphore peut faire appara tre un probl me connu sous le nom d inversion de priorit En effet une tache de plus faible priorit peut bloquer une tache de plus haute priorit si elle acc de en section critique a une ressource partag e Cet expos des principes de fonctionnement des syst mes temps r els permet de se rendre compte que ceux ci ne peuvent tre utilis s que dans un cadre bien particulier o l on est capable de fournir a l ordonnanceur toutes les informations n cessaires ses calculs L obligation de fournir le temps d ex cution au pire des cas pour garantir le respect des contraintes temporelles est une limitation importante pour l utilisation de syst mes temps r el pour ex cuter des syst mes intelligents utilisant des algorithmes complexes En effet ces derniers peuvent avoir des temps d ex cution au pire des cas extr mement lev s par rapport au temps d ex cution en moyenne De plus les syst mes temps r el ne sont pas tous pr emptifs et sont incapables de fournir l illusion que les processus sont actifs en permanence Enfin les solutions propos es en cas de surcharge du syst me sont des solutions tr s autoritaires o ce sont toujours
165. namiquement des artifacts un ensemble d attributs ce sont des variables internes que l agent exhibe l ext rieur un ensemble d instructions op ratoires la description formelle de la mani re dont les agents peuvent utiliser l artifact Cela constitue le mode d emploi de I artifact une sp cification de son comportement la description formelle du comportement interne de l artifact non perceptible de ext rieur La figure 3 2 montre comment on repr sente un artifact et ses caract ristiques associ es Fonction et Interface d usage instructions op ratoires Agents o O O Attributs FIG 3 2 Un artifact L interface d usage indique la nature des changes entre les agents et les artifacts Ceux ci sont dissym triques puisque les agents peuvent ex cuter des actions et les artifacts peuvent fournir des perceptions de la terminaison d une action Un agent qui d cide d ex cuter une action oblige l agent a l ex cuter imm diatement C est un lien quasi physique comme quand on appuie sur un bouton pour d marrer un appareil lectrique Les communications sont ainsi d un type totalement diff rent de la communication entre agents qui se fait par actes de langage On retrouve d ailleurs cette distinction dans la programmation orient e objet lorsqu on appelle une m thode d un autre objet celui ci est oblig de l ex cuter imm dia
166. ndis que pause_comput ation et resume_computation doivent tre g r es par artifact lui m me Il n y a aucune diff rence conceptuelle entre ces deux couples d actions Cette distinction est uniquement apport e par notre souci de rester proche de l impl mentation Des explications plus d taill es sur la n cessit de cette distinction sont donn es dans le paragraphe suivant Les perceptions minimales sont finished RESULT Cette perception est re ue lorsque le travail de calcul initi par start_computation DATA a t termin avec succ s RESULT est unifi avec la r sultat donn par l algorithme lanc error ERROR_INFO Cette perception permet de transmettre les erreurs d ex cution de l algorithme l agent paused Cette perception est mise au moment o l artifact se met en pause resumed Cette perception permet de confirmer le red marrage de artifact Les actions et perceptions pr c dentes constituent une base minimale qu il est possible d tendre en fonction du type particulier d artifact de calcul auquel on a affaire Par exemple pour un artifact qui encapsule un algorithme a contrat on introduira deux nouvelles actions start_computation DATA CONTRACT et continue CONTRACT qui sp cifient toutes les deux la dur e du contrat La section 3 4 4 d taille instruction op ratoire utilis e pour manipuler un algorithme contrat ainsi que d autres exem
167. ngages logiques Lorsque l on veut raisonner sur le temps on se tourne g n ralement vers une des nombreuses logiques temporelles propos es dans la litt rature Fisher et al 2005 Les logiques temporelles peuvent d crire des v nements discrets continus ou les deux Les logiques temporelles sont des logiques de propositions Les propositions bool enne atomiques sont combin es par des connecteurs logiques comme ET OU NON et par d autres op rateurs de modalit Les logiques temporelles sont donc galement des logiques modales On peut classer les logiques temporelles en diff rentes cat gories Tout d abord on peut d finir des logiques lin aires comme Linear Temporal Logic LTL Elles permettent de d crire l volution d un chemin temporel Les op rateurs modaux que l on peut utiliser sont les suivants Xp p sera vrai imm diatement apr s l instant courant Fp p sera vrai un jour Gp pest toujours vrai pUq p doit tre vrai jusqu ce que q devienne vrai pRq q est vrai jusqu ce que p devienne vrai On appelle ces op rateurs des op rateurs d tat 32 Chapitre 2 Contexte Les logiques branchement du temps branching time temporal logics comme Computational Tree Logic CTL permettent quant elles de d crire plusieurs chemins temporels se s parant dif f rents instants On utilise les op rateurs d crits pr c demment et on ajoute
168. nous utilisons le formalisme d crit dans la section 3 4 Il faut tout d abord d crire l interface d usage qui sp cifie les actions et perceptions en direction et provenant de l artifact Dans notre application de localisation de bateaux les actions possibles sur P artifact de calcul sont 5 3 Nouvelle mod lisation d Interloc avec les artifacts 113 add_constraint C introduction d une contrainte C propagate propagate T lancement de la propagation sans ou avec un contrat de temps T pause suspension du traitement restart red marrage du traitement stop arr t normal de artifact Par ailleurs tout artifact peut tre interrompu d finitivement destruction du processus ou du pro cessus l ger mais cette action au m me titre que la cr ation initiale ne fait pas 4 proprement parler de l interface d usage Les perceptions possibles sont syntax_error perception d une erreur de syntaxe si la contrainte introduite par l action add_constraint est incorrecte success perception du succ s de l introduction d une nouvelle contrainte result E I fournie la fin du contrat de temps et repr sentant l tat du calcul E et l ensemble des intervalles de localisation I comprenant les coordonn es cart siennes de la zone et ses coordonn es polaires relatives la derni re position de l avion L l ment essentiel n cessaire la programma
169. ns de la premi re moiti du si cle dernier ont permis de pr ciser et de formaliser la notion d algorithme en ne consid rant que les m thodes effectivement implantables sur une machine Le premier r sultat important est plut t d cevant puisqu il nous indique qu il existe des fonctions qui ne sont pas calculables C est le cas notamment avec le probl me de l arr t Turing a d montr qu il n existe pas de programme universel qui prenne n importe quel programme en ar gument et qui en temps fini renvoie oui si l ex cution du programme re u en argument finit par s arr ter et non s il ne finit pas Un programme informatique peut tre vu comme la r alisation d un algorithme sur une machine donn e On consid re que c est la comtesse Augusta Ada Lovelace qui aurait crit ou particip a P criture du premier programme informatique en 1843 Celui ci permettait de calculer les nombres de Bernoulli avec la machine analytique que Charles Babbage avait entrepris de construire 2 2 Travaux connexes 15 L autre r sultat important a t propos de mani re ind pendante par Turing et Church La th se de Church Turing dans sa formulation la plus courante indique que les machines de Turing formalisent correctement la notion de m thode effective de calcul Et donc que toute fonction calculable l est sur une machine de Turing qui termine Cette th se ne peut tre d montr e mais elle est commun ment a
170. ns de synchronisation ordonnancement s maphores ou des fonctions de coordination de haut niveau syst mes d ench res de workflow d infrastructures de ph romones Viroli et Ricci 2004 montre par exemple comment utiliser un artifact pour encapsuler l impl menta tion du protocole Contract Net Les agents n ont pas se pr occuper de toute la m canique interne du protocole L initiateur demande artifact d initier le protocole en lui indiquant le contenu du contrat Il re oit des rapports lui indiquant les propositions faites L artifact g re les messages d acceptation ou de refus envoy s chacun des participants Ricci et al 2005 donne un autre exemple avec le probl me des philosophes initialement propos et r solu par Edsger Dijkstra grace aux s maphores L artifact repr sente la table laquelle sont assis les philosophes Elle permet de coordonner les agents philosophes pour l acc s aux fourchettes L impl mentation est donn e en ReSpecT et en 3APL Un artifact fronti re F est utilis pour caract riser et contr ler la pr sence d un agent dans un contexte organisationnel en r ifiant un contrat entre un agent et une organisation Dans les environ nements bas s sur les r les un artifact fronti re embarque le contrat pour les r les que l agent joue dans l organisation Il est fourni l agent quand celui ci d marre une session de travail
171. nt est g r le parall lisme sur une unique machine r elle ou virtuelle Nous pr sentons maintenant les techniques utilis es pour g rer le paral 2 2 Travaux connexes 29 l lisme lorsque l on dispose d un syst me r ellement distribu On ne se base plus ici sur la parall lisation d un unique algorithme sur plusieurs processus ou processus l gers mais sur les technologies r seau qui permettent d acc der a des ressources distantes 2 2 2 2 1 Objets distribu s Le paradigme objet est le plus utilis actuellement pour mod liser toutes sortes d applications Il a d abord t utilis dans le cadre d applications centralis es On dispose maintenant d intergiciels comme CORBA permettant de faire des appels de m thodes sur des objets distants Lorsque l on veut faire un appel de m thode distance on se connecte l intergiciel et on r cup re une r f rence locale l objet distant Ensuite on effectue les appels de m thode directement sur l objet local Le but de ces intergiciels est de masquer totalement le fait que les appels sont effectu s distance en dehors de Pinitialisation rien ne diff rencie un appel de m thode local ou distant Ces outils sont tr s pratiques lorsque l on veut continuer programmer les applications comme si elles taient centralis es mais ils ont le d faut de ne plus autoriser de raisonnement sur l aspect distribu de celles ci 2 2 2 2 2 Composants Les
172. nt les actions primitives qui peuvent s inscrire dans la dur e Nous traduisons une s quence a T n p par une m thode nomm e a et en indiquant que sa dur e minimale est 0 et sa dur e maximale est n L attente W n sera quant elle traduite par une m thode Wait de dur e minimale n Dans T EMS les fonctions d accumulation de qualit FAQ permettent d indiquer comment est calcul e la qualit pour un n ud de l arbre en fonction de la qualit obtenue par chacun de ses fils Il en existe 11 Leur s mantique pr cise est d finie dans Horling 1999 L op rateur parall le peut tre traduit par les FAQ q_min q sumou g_all_sum Lalter native pourra tre traduite par deux FAQ diff rentes en fonction de son type Si c est un choix exclusif ce sera q_exactly_one et si c est un choix retard ce sera q_max L op rateur de s quence sera traduit par une des FAQ de s quence q_seq_min q_seq_max q seq sumou a_seg_last 3 4 Le langage de mode d emploi des artifacts 71 Il n est pas possible d automatiser cette traduction car un op rateur de notre alg bre de proces sus peut tre traduit en plusieurs FAQ diff rentes Par exemple la s quence peut tre traduite par q_seq_min qui sp cifie que les sous t ches doivent tre r alis es en s quence et que la t che prend ensuite la qualit minimale de toutes les qualit s obtenues pour les sous t ches On peut aussi la tra
173. ntralisation Nous avons d ja discut du bien fond de son intro duction dans la section 4 1 1 Nous avions remarqu qu une solution totalement d centralis e serait tres difficile 4 mettre en place et serait certainement inefficace Il est important de v rifier que la centralisation que nous avons faite ne nuit pas l aspect agent de nos applications Nous voulons donc insister sur le fait que nous n avons centralis que les informa tions n cessaires au calcul de l ordonnancement mais que nous n avons pas centralis les d cisions li es l ordonnancement Les agents gardent l entier contr le sur le sacrifice ventuel de leurs res sources de calcul qu il peuvent avoir faire 4 2 Gestion des ressources processeur sans d lais respecter Notre cadre est celui o l on donne une date limite chaque t che de calcul d l gu e un artifact Cependant lorsque les t ches que l on doit ex cuter dans un SMA ne sont pas soumises des d lais stricts on peut quand m me continuer b n ficier des services de l APRC si ponctuellement un agent a un besoin un peu plus important en ressources processeur Notre APRC est pr vu pour fonctionner en mode simplifi dans ce type d applications On ne passe plus par la premi re partie du protocole qui permet de d terminer un ordonnancement pour une nouvelle t che On utilise uniquement les facilit s de n gociation propos es par l APRC Ainsi un agent p
174. nts les types de donn es et les fonctions fournies L tat d un agent un instant t est ensuite d crit par l ensemble des objets de la base de code r f renc es dans les structures de donn es de l agent Un agent est d crit par un ensemble de contraintes d int grit que l tat d un agent doit v rifier pour pouvoir tre consi d r comme valide une notion de concurrence qui sp cifie comment on peut combiner un ensemble d actions en une seule action un ensemble de contraintes d action qui d finit les circonstances dans lesquelles des actions peuvent s ex cuter de mani re concurrente un programme d agent qui d termine les actions que l agent doit peut ou ne peut pas entre prendre On utilise pour cela les op rateurs d ontiques P F O W et Do respectivement pour la permission interdiction obligation l annulation d une obligation et la r alisation actuelle d une action Les premi res versions d IMPACT poss dent quelques limitations les actions n ont pas de dur es et on est incapable de les placer dans un agenda pour qu elles soient ex cut es dans le futur Temporal Agent Program l ve ces limitations Dans TAP les actions s inscrivent donc dans la dur e L tat associ une action volue de mani re continue C est le cas par exemple de la position d un v hicule qui r alise l action drive Lille Paris On peut d crire des
175. ocesseur avec des d lais a respecter 93 4 1 5 Ex cution de l ordonnancement L ordonnancement est calcul par l APRC Il doit ensuite tre ex cut c est dire qu une des entit s du SMA doit se charger d envoyer les commandes de pause et de red marrage aux artifacts aux limites des intervalles de temps d termin s par l APRC Nous proposons trois modes de fonc tionnement gestion par artifact lui m me gestion par 1 APRC et gestion par l agent qui d l gue sa t che a artifact concern Nous d taillons dans les paragraphes suivants ces trois modes de fonctionnement et donnons pour chacun d eux les avantages et inconv nients 4 1 5 1 Gestion par PAPRC On peut tr s facilement charger 1 APRC de d marrer et arr ter les artifacts au bon moment puis qu il dispose de toutes les informations sur l ordonnancement du syst me Il suffit qu il fasse appel au syst me d exploitation pour tre r veill au moment d effectuer une mise en pause ou un red marrage d un artifact Cela peut se faire au moyen des signaux syst me ou des m canismes d alarme fournis par le syst me d exploitation La mise en pause et le r veil des artifacts se fera comme d crit dans la section 3 3 3 soit par envoi de signaux syst mes SIGSTOP et SIGCONT soit par envoi de messages sur une socket constamment surveill e par l artifact L encapsulation de ce travail dans l APRC est correcte du
176. ompos des r actions de A aux requ tes de B L expression de l autonomie de A dans son com portement appara t par des r actions impr vues Par exemple A peut ne pas r pondre un message de B ou y r pondre en d passant les d lais Nous pouvons d duire de cette cons quence op rationnelle de l autonomie qu un agent ne dispose donc que d un mod le approximatif d un autre agent S il disposait d un mod le pr cis l autre agent ne pourrait plus tre consid r comme autonome par rapport lui Or nous avons d crit pr c demment nos t ches calculatoires comme des bo tes translucides un algorithme vu comme une bo te noire non modifiable accompagn de ses caract ristiques et de son mode d emploi Un algorithme n est pas vu ici comme une entit autonome et ses caract ristiques sont un mod le pr cis sur lequel un agent peut compter pour effectuer ses raisonnements Lorsque l on programme un agent il faut prendre en compte l autonomie des autres agents Dans notre cas cette id e s exprime par le fait que l on devrait se refuser arr ter et red marrer un autre agent celui ci perdant son autonomie par rapport l agent qui le commande Or nos agents introvertis sont command s par les agents extravertis D un point de vue conceptuel le fil d ex cution qui ex cute nos t ches calculatoires se d tache donc de l id e que l on se fait du concept d agent SIL est important de not
177. ons identifi des propri t s importantes pour nos agents l autonomie l extraversion et la conscience du temps Nous consid rons que si nous perdons ces propri t s nous perdons en m me temps une grande partie des b n fices apport s par le paradigme agent Les outils propos s par les syst mes d exploitation pour g rer le partage des ressources processeur se placent un niveau d abstraction bien trop bas pour pouvoir tre compatibles avec les exigences cit es pr c demment au niveau agent Par exemple si l ordonnancement des t ches est uniquement d cid par le syst me d exploitation les agents lui sont totalement soumis et ne peuvent exercer aucune autonomie sur leur propre utilisation des ressources processeur Il convient donc de proposer une interface entre ces deux niveaux d abstraction Je soutiens la th se qu il est n cessaire pour cela d introduire un nouveau type d entit dans les syst mes multi agents pour prendre en compte au mieux les sp cificit s des SMA que nous voulons construire Le concept d artifact introduit dans Omicini et al 2004 permet justement d int grer dans les SMA des entit s utilis es par les agents comme des outils les aidant a atteindre leurs buts J introduis une sp cialisation de ce concept pour les d lib rations longues La nouvelle classe d artifacts ainsi d finie les artifacts de calcul permet aux agents de conserver leurs propri t s d
178. ontextes de calcul tout en restant l coute du monde ext rieur Cette proposition repose sur le concept d artifact initialement d velopp par une quipe italienne pour la coordina tion Omicini et al 2004 Les artifacts peuvent tre vus comme des outils que les agents utilisent pour atteindre leurs buts Ils disposent de modes d emploi qui permettent aux agents de comprendre comment les utiliser Je d cris dans ce chapitre les extensions que j ai apport es pour adapter les ar tifacts l externalisation des calculs longs Je propose un ensemble de modes d emploi d artifacts de calcul utiliser en fonction des propri t s temporelles de l algorithme encapsul dans l artifact Le chapitre 4 traite plus particuli rement du partage efficace des ressources processeur entre les entit s du syst me multi agent Ce probl me est tudi selon que les agents ont des d lais respecter pour l utilisation des ressources processeur section 4 1 ou qu ils n en ont pas section 4 2 Pour r soudre ce probl me je propose d utiliser un artifact de coordination qui centralise les demandes de ressources processeur Je fournis un algorithme d ordonnancement qui respecte les contraintes sp cifiques nos syst mes Le chapitre 5 d crit la mise en uvre des artifacts de calcul et des techniques de partage des ressources processeur propos es dans la plateforme multi
179. ontr le au niveau utilisateur 2 2 2 1 4 Les machines multiprocesseurs et les syst mes de gestion de grappes de serveurs La mise au point de machines multiprocesseurs ou massivement multiprocesseurs se fait sou vent de mani re conjointe aux niveaux mat riel et logiciel La pr occupation principale est le partage efficace de la m moire pour obtenir des gains de performance les plus proches possibles des gains th oriques En effet en th orie avec n processeurs on doit pouvoir obtenir un r sultat n fois plus vite qu avec un unique processeur En pratique on n obtient pas cette acc l ration cause des temps de communication et la synchronisation n cessaire entre les diff rents processeurs Ces aspects d velop p s de mani re sp cifique dans Culler et al 1999 ne nous int ressent pas ici Nous nous int ressons plut t aux biblioth ques logicielles fournies avec les architectures mat rielles Les machines multiprocesseurs sont souvent tr s on reuses Pour limiter les co ts on peut regrou per plusieurs ordinateurs ind pendants appel s n uds au sein d une grappe de serveurs Les grappes sont g r es par un logiciel de clustering qui permet l utilisateur de ne voir qu une unique machine multiprocesseur m moire partag e Il est charg de g rer le cycle de vie des processus placement des processus sur les n uds passage des donn es traiter et r cup ration des r sultats Il permet
180. oordination Th se de doctorat University of Massachusetts Wagner et Lesser 2000 WAGNER T et LESSER V R 2000 Design to Criteria Scheduling Real Time Agent Control Proceedings of AAAI 2000 Spring Symposium on Real Time Autono mous Systems Williamson et al 1996 WILLIAMSON M DECKER K et SYCARA K 1996 Unified informa tion and control flow in hierarchical task networks In Theories of Action Planning and Robot Control Bridging the Gap Proceedings of the 1996 AAAI Workshop pages 142 150 Menlo Park California AAAI Press Wooldridge et al 2000 WOOLDRIDGE M JENNINGS N R et KINNY D 2000 The gaia me thodology for agent oriented analysis and design Autonomous Agents and Multi Agent Systems 3 3 285 312 Zilberstein et Mouaddib 1999 ZILBERSTEIN S et MOUADDIB A I 1999 Reactive control of dynamic progressive processing In Proceedings of the 16th IJCAI pages 1268 1273 Morgan Kaufmann Publishers Inc
181. ourra d cider de stopper ses calculs pendant quelques temps pour laisser l autre finir plus rapidement ses calculs Ce mode de fonctionnement peut permettre de g rer tr s facilement des priorit s d acc s aux res sources processeur entre les diff rents agents et ceci de mani re d centralis e Les diff rents niveaux de priorit entre les agents sont d finis au niveau de chaque agent Un agent qui re oit une demande de sacrifice pour un autre agent plus prioritaire que lui accepte toujours et il refuse toujours si la demande provient d un agent moins prioritaire 4 3 Passage au multi processeur Notre mod le peut tre tendu plusieurs processeurs Nous pla ons pour cela un APRC sur chacun des processeurs du syst me Chaque APRC s occupe de l allocation des ressources du pro cesseur sur lequel il s ex cute Ils sont galement charg s de mesurer la charge de leur processeur de diff rentes mani res 1 Pour les t ches planifi es le rapport DIT ou E est le nombre d op rations affecter la t che P la puissance du processeur en nombre d op rations par secondes et DL To Vintervalle de temps autoris pour l ex cution de la t che Ce rapport permet de mesurer la marge de man uvre dont dispose APRC pour planifier d autres t ches 102 Chapitre 4 La gestion des ressources processeur 2 Pour les agents le taux de requ tes de t ches qui aboutissent 4 un refus sur un intervalle de
182. part de ressources r serv e ces derniers devient tr s faible Cette hypoth se est valable si l on consid re que les agents ont toujours des traitements r aliser Cependant en pratique on remarque que les agents se limitent des automates de traitement des messages entrants Le traitement d un message entrant ne n cessite souvent que tr s peu de ressources puisque les traitements longs sont d l gu s aux artifacts Les agents sont donc souvent en pause en attente d un message traiter Ce ph nom ne est accentu d s lors que les agents sont synchronis s par l utilisation de protocoles un agent envoie un message un autre agent et attend sa r ponse pour continuer La synchronisation uniformise la quantit de ressource totale r ellement utilis e par les agents il n y aura pas de moments o tous les agents vont s ex cuter en m me temps Dans ces conditions il serait plus judicieux d utiliser l hypoth se que l ensemble des agents n uti lise pas plus qu une certaine fraction des capacit s du processeur Il est juste n cessaire que cette hy poth se soit vraie en moyenne sur chaque intervalle s parant deux dates limites D autres hypoth ses peuvent tre imagin es en fonction du SMA en construction Le choix d une hypoth se particuli re se fait tr s facilement dans un SMA donn en changeant l attribution des FP dans l algorithme d ordonnancement 4 1 Gestion des ressources pr
183. permettent de structurer l environnement qu ils sont utilis s dans toute activit hu maine et qu il est m me possible de comprendre les activit s humaines simplement en observant les outils de m diation utilis s Si l on transpose cela aux agents et leur environnement nous pouvons d s lors faire l hypoth se que placer la notion d outil comme type d entit de premier plan au sein des syst mes multi agents ne peut tre que b n fique Cela nous permettra tout du moins de mieux structurer les syst mes et d identifier les am liorations possibles au niveau des outils que les agents utilisent Si un agent est g n ralement vu comme un syst me dirig ou orient par des buts un artifact est une entit qu un agent ufilise pour atteindre ses buts Un artifact persiste au sein du syst me ind pendamment du cycle de vie des agent De mani re plus pr cise un artifact est caract ris par une interface d usage d finie comme un ensemble d op rations Les op rations sont de deux types l ex cution d une action et la perception de la terminaison d une action SNous conservons ici l orthographe artifact pour viter la confusion avec l acception usuelle du mot artefact de la langue fran aise ph nom ne d origine humaine 3 2 Les artifacts 55 sa fonction la description du ou des services rendus par I artifact Elle peut tre utilis e pour rechercher et d couvrir dy
184. peuvent prendre les instructions op ratoires durant leur ex cution nous avons consid r ici un choix exclusif entre a1 et a2 tat de 1 automate Instruction op ratoire El al pl a2 p2 E2 fal pl E3 a2 p2 M1 a3 p3 a4 p4 M2 a3 p3 a4 p4 M3 a4 p4 M4 a3 p3 a4 p4 M5 a3 p3 M6 a3 p3 M7 a4 p4 M8 a3 p3 a4 p4 Viroli et Ricci ont propos dans Viroli et Ricci 2004 une extension l alg bre pr c dente pour prendre en compte la notion de timeout dans les instructions op ratoires Ils d finissent un timeout ainsi 3 4 Le langage de mode d emploi des artifacts 63 D finition 3 1 Timeout Un timeout d finit une p riode de temps a la fin de laquelle une action peut tre associ e Un timeout peut tre utilis pour se mettre en attente pendant une dur e maximale d un v nement Il peut galement tre utilis pour r aliser une action pendant une dur e maximale Un timeout peut tre d sactiv tout instant avant l expiration de sa p riode de temps Dans ce cas l action associ e Pexpiration de la p riode de temps n est pas ex cut e L extension pour g rer les timeouts est obtenue en tendant les d finitions des instructions et des actes d interaction de la mani re suivante I T n e 7y T m T n est l instruction timeo
185. ples d instructions op ratoires classiquement utilis es avec les artifacts de calcul 3 3 3 Notes d impl mentation et contraintes suppl mentaires Nous pr sentons dans ce chapitre les concepts que nous voulons mettre en place dans nos sys t mes la mise en uvre effective tant pr sent e dans le chapitre 5 N anmoins notre but est de 3 4 Le langage de mode d emploi des artifacts 59 r duire le foss entre les concepts et l impl mentation Et comme le concept d artifact de calcul a des implications tr s proches du niveau syst me nous pr f rons tout de suite les identifier et adapter le concept en cons quence Tout d abord nous avons d cid d externaliser les t ches de calcul afin de simplifier la program mation des agents Il faut viter de reporter la complexit de r alisation sur les artifacts de calcul Nous prendrons donc comme hypoth se qu un artifact de calcul appartient l agent qui l utilise Les autres agents n en ont pas connaissance et ne peuvent donc pas tenter de lui faire ex cuter des actions pendant qu il est en train de r aliser une tache De plus un artifact de calcul ne pourra r aliser qu une tache de calcul a la fois Cette contrainte pourra tre supprim e par la suite Dans un premier temps si l on veut pouvoir avoir l illusion qu un artifact de calcul est partag par plusieurs agents il faudra recourir un artifact de coordination ou de ressour
186. plication principalement cibl est celui de la biologie cellulaire 3 8 Synth se Nous avons identifi le besoin d isoler et de traiter de mani re particuli re les t ches de calcul de nos agents Nous nous sommes donc pos s la question de la nature des entit s qui r alisent ces calculs Nous nous sommes aper us que ces traitements avaient int r t tre externalis s pour notamment ne pas trop complexifier l architecture des agents Les t ches externalis es pourraient tre attribu es Notons que les replanifications faites par le chef tentent de minimiser le nombre de r affectations n cessaires Cette r affectation intelligente se fait de mani re incr mentale tout en garantissant une solution qui minimise le nombre de r affectations et constitue une partie des travaux de th se de Damien Devigne 82 Chapitre 3 Des outils de calcul pour les agents une classe particuli re d agents mais cela ne convient pas notamment cause de la propri t d au tonomie des agents a laquelle nous donnons une d finition qui convient a notre contexte d tude J ai propos de r utiliser la notion d artifact introduite par Ricci Viroli et Omicini en 2004 Celle ci nous permet d introduire dans nos syst mes des artifacts de calcul qui prennent en charge les t ches calculatoires longues des agents Les artifacts disposent d instructions op ratoires qui d crivent leur mode d emploi pr cis et garanti
187. porte ment interne de l APRC Def_Negotiation_Participant Un participant au protocole de n gociation ex cute l action get_sacrifice request de mani re r cursive Les perceptions associ es cette action sont finished qui indique que la participation de l agent au protocole est termin e et new_sacrifice_ request qui indique qu une nouvelle requ te de sacrifice s_content est 98 Chapitre 4 La gestion des ressources processeur disponible Le terme s_content contient les informations de i_negotiation et galement l in formation s_result calcul e par le participant sur le sacrifice qu il est capable de consentir Quand une nouvelle requ te de sacrifice est re ue l agent dispose de s_timeout tops d horloge pour r pondre Il peut refuser de se sacrifier ou il peut accepter et dans ce cas il doit fournir une proposition qui sera utilis e par 1 APRC pour v rifier si avec le sacrifice la nouvelle t che peut s ex cuter Selon le cas 1 APRC demande l agent de valider ou d annuler le sacrifice propos Les instructions op ratoires donn es seules ne sont pas suffisantes pour les agents Il faut en effet donner aux agents suffisamment d informations pour comprendre les instructions op ratoires qu ils ex cutent Nous donnons donc un lien entre les instructions op ratoires et l tat mental de l agent La figure 4 9 d crit ce lien Nous utilisons la s mantique mentale li e
188. pour la nouvelle t che dans l agenda Dans ce cas les autres agents s engagent dans l ins truction op ratoire Def_Negotiation_Participant pour ventuellement sacrifier une part des ressources processeur qu ils utilisent Def_CA_Management Nous avons apport une l g re modification la version pr sent e dans la section Quand un refus est re u 1 agent essaie de n gocier avec les autres agents en d clenchant l instruction op ratoire Def_Negotiation_Initiator Def_Negotiation_Initiator Pour simplifier le processus de n gociation nous consid rons que les agents ont un moyen commun pour exprimer l importance d une t che de calcul Cela permet un agent qui re oit une requ te pour sacrifier une partie de ses ressources processeur de pouvoir comparer l importance de ses t ches avec l importance des t ches pour lesquelles on lui demande de se sacri fier Le terme i_negotiation contient les informations de r_content et de imp calcul es par l agent Celles ci repr sentent l importance de la nouvelle t che L agent demandeur ex cute simple ment l action start_negotiation et attend une r ponse pendant n_timeout tops d horloge Si la n gociation a t fructueuse 1 APRC g n re une instruction op ratoire pour contr ler l artifact de calcul et l affecte ca_oi dans i_negotiation Notons que l initiateur n a aucune vue du processus de n gociation celui ci est enti rement g r par le com
189. pour toutes les t ches Lorsque le nombre de processus l ex cution est variable ou que l on ne conna t pas l avance tous les param tres li s aux t ches on utilise un ordonnanceur en ligne c est dire un ordonnanceur qui recalcule l ex cution un nouvel ordonnancement chaque fois qu un param tre est modifi Les contraintes temporelles sont fournies l ordonnanceur en sp cifiant l ex cution temporelle des actions Une action peut tre p riodique si elle doit tre ex cut e un intervalle donn La date limite pour chaque ex cution peut tre diff rente de la p riode Ce type d action est par exemple utilis lorsque les traitements doivent respecter la fr quence d chantillonage de donn es capt es ap riodique si le temps entre chaque nouvelle ex cution est al atoire par exemple quand l ac tion correspond au traitement d un v nement sporadique si elle est ex cut e un intervalle donn mais avec une variation jitter Comme on veut garantir que les d lais seront respect s on utilise le temps d ex cution au pire des cas WCET Worst Case Execution Time en anglais comme donn e d utilisation du processeur pour chacune des taches de calcul Pour pouvoir tre mis en ceuvre un algorithme en ligne doit disposer au moins de deux propri t s il doit tre correct et complet Il doit donner un r sultat correct et trouver un ordonnancement lorsqu il
190. pouvoir ex cuter la prochaine instruction Notons 9 voir section 3 4 3 5 pour plus de d tails 3 4 Le langage de mode d emploi des artifacts 65 qu il n y a pas de r gle W ACT Dans le cas du timeout une action peut tre r alis e avant que le timeout n expire gr ce la r gle T ACT Ici agent ne peut pas d marrer une action avant la fin de l attente Pour clarifier ces notions voici l exemple d une instruction op ratoire qui peut tre utilis e pour contr ler et interagir avec un artifact de calcul OI W 10 start data T 5 lpause W 10 restart T 5 stop finished result failure error_info TD agent doit attendre 10 tops d horloge avant d ordonner artifact de d marrer sa t che de calcul avec DATA comme donn es d entr e Il doit ordonner l artifact de se mettre en pause moins de 5 tops d horloge apr s le d marrage de la t che et de red marrer pas moins de 10 tops d horloge plus tard Enfin si la t che de calcul ne s est pas termin e correctement ou la suite d une erreur en moins de 5 tops d horloge instruction de timeout l agent doit lui ordonner de mettre un terme son calcul courant action stop 3 4 3 2 L alternative apr s un timeout Les tats d erreurs introduits pour g rer l expiration d un timeout posent probl me car une fois qu on les a atteint il n est plus possible d en res
191. que des agents 110 Chapitre 5 Mise en ceuvre et valuation Paul Edouard Marson a propos durant son master recherche Marson 2006 une biblioth que qui compl te celle d ALBA et des fils de raisonnement pour la cr ation d artifact Ceux ci utilisent la biblioth que ALBA pour communiquer avec les agents Les instructions op ratoires sont d crites sous la forme de pr dicats Prolog Chaque instruction op ratoire dispose d un identifiant unique Le comportement interne des artifacts est impl ment sous forme de FDR La grammaire lie l identifiant d une instruction op ratoire avec le FDR correspondant Ainsi lorsqu une action est demand e par un agent pour une instruction op ratoire donn e le message est automatiquement envoy au bon FDR La nouvelle biblioth que integre galement les outils n cessaires pour que les agents puissent utiliser les artifacts Paul douard Marson a mis au point un m canisme de conversion automatique d instructions op ratoires vers des fils de raisonnements Ainsi le pilotage d un artifact se fait de mani re transparente au travers d un contexte quelconque de l agent 5 2 Pr sentation de l application Interloc Les artifacts ont t utilis s dans diverses applications d velopp es chez Thales Division A ronautique Cela concerne par exemple la planification de mission ou encore la coordination d un ensemble de drones Il appara t m me que tous les SMA qu
192. que l agent aurait pu r aliser lui m me sans perdre sa propri t d extraversion Nous avons galement consid r jusqu maintenant que toutes les t ches d l gu es aux artifacts disposent d un d lai Il se peut que dans certaines applications ceci ne soit pas r aliste et oblige d finir des d lais de mani re fictive La relaxation de cette contrainte est discut e dans la section 4 2 Comme nous voulons pr server l autonomie de d cision des agents nous ne pouvons d l guer enti rement toutes les questions d ordonnancement l APRC Cela implique que quand on con oit un SMA on doit pr voir pour chaque agent soit qu il sera capable de continuer travailler sans avoir pu r aliser une de ses t ches de calcul soit qu au moins un autre agent du syst me va s tre sacrifi pour qu il puisse r aliser sa t che 4 1 9 2 Efficacit pratique de l algorithme d ordonnancement Nous avons tudi les limites de l ordonnanceur La complexit provient principalement du d coupage en sous intervalles qui est en O 2 Le temps de calcul devient tr s vite prohibitif Il est cependant possible en pratique de faire baisser cette complexit en tudiant les contraintes pos es En effet il est souvent possible de pr d terminer apr s le calcul de ESR et des Ci qu un cer tain nombre de t ches ne pourront pas du tout s ex cuter dans l intervalle consid r Si la somme ES
193. r s importante La communaut agent ayant beaucoup de probl mes de passage l chelle des architectures d agent et des protocoles d interaction tude du mod le GRID para t importante Foster et al 2004 La fusion des deux mod les est encore pr matur e mais quelques tudes comme celle men e l universit de Montpellier Jonquet et al 2006 vont dans ce sens en se focalisant sur la notion de service qui est commune aux approches agent et GRID Open Grid Services Architecture Open Grid Services Architecture OGSA est l architecture adopt e par de nombreux projets concernant le GRID Les concepts d OGSA sont d riv s des travaux pr sent s dans Foster ef al 2002 L infrastucture se base sur la technologie des Web Services et les tech nologies assci es comme WSDL et SOAP Dans OGSA tout est d crit sous forme de service une entit capable de communication r seau dont les comp tences peuvent tre utilis es par changes de messages les ressources de calcul les ressources de stockage les gestionnaires de bases de donn es les programmes Cela permet de virtualiser tous les constituants de l environnement GRID En particulier on parle d organisations virtuelles Les fonctionnalit s d OGSA sont galement fournies sous forme de services On dispose ainsi de services de base pour authentification en mode single sign on la tol rance au
194. r le futur et qu elles se d clenchent au bon moment de mani re automatique comme cela est fait dans Agent 0 des moyens pour se constituer des biblioth ques de fils de raisonnement r utilisables la gestion de la m moire li e chacun des fils de raisonnement et l agent complet 7 3 Gestion du temps dans les syst mes multi agents Une fois que notre mod le d agent disposera des fonctionnalit s d crites ci dessus nous pour rons mettre en place le niveau m ta permettant de raisonner sur les actions de l agent Les capacit s intelligentes des agents d velopper concerneront alors les buts de l agent Ceux ci doivent appara tre de mani re explicite contrairement ce qui est fait actuellement les buts sont exprim s de mani re implicite dans le code L agent pourrait ainsi manipuler ses buts et raisonner dessus l utilisation et le raisonnement sur les plans de l agent Les agents devraient tre capables de manipuler des plans hypoth tiques les instancier les valuer les comparer les mettre en uvre Ils devraient galement tre capables de raisonner sur des plans qui leur sont fournis l utilisation des informations sur l historique des actions et des perceptions Ces informations souvent utilis es pour l apprentissage nous serviraient plut t comme aide aux d cisions de l agent 7 4 Rapprochement avec d autres communaut s Nous devrions assister dans les ann
195. r pour r pondre au t l phone de changer de contexte pour s adapter la conversation que l on tient au t l phone puis de revenir notre contexte de travail lorsque la conversation t l phonique est termin e Nous prendrons garde de ne pas tomber dans les travers dont nous parlions pr c demment et de n utiliser la m taphore humaine que lorsqu elle sera pertinente Rappelons nous simplement que l environnement dans lequel nous vivons n est pas celui dans lequel se trouvent nos agents 1 2 Le g nie logiciel am lioration des techniques de programmation Le domaine du g nie logiciel est apparu dans les ann es 1970 lorsque les premiers projets in formatiques d envergure ont affront d normes difficult s pour arriver leur terme Le but est de 4 Chapitre 1 Introduction proposer des m thodes techniques et outils pour concevoir et r aliser des syst mes informatiques de plus en plus complexes Le g nie logiciel pr ne des principes comme la simplicit Cette citation de Dave Small dans ST Magazine r sume bien ce principe Un langage de programmation est cens tre une fagon conventionnelle de donner des ordres a un ordinateur Il n est pas cens tre obscur bizarre et plein de pi ges subtils a ce sont les attributs de la magie la productivit Les traitements simples et r currents ne doivent pas prendre beaucoup de temps impl menter Il faut galement faciliter la mise
196. re d application il est int ressant de d marrer au plus t t les diff rentes heuristiques et d arr ter la r solution d s qu un artifact a trouv la solution recherch e 4 1 Gestion des ressources processeur avec des d lais a respecter 87 Utilisation processeur 100 Temps FIG 4 1 Exemple d ordonnancement obtenu avec Earliest Deadline First La figure 4 1 donne un exemple d ordonnancement obtenu avec EDF pour trois t ches T1 T2 et T3 dont les dates limites respectives sont DL DL et DL3 L ordonnancement r alis par 1 APRC doit prendre en compte l utilisation qu il fait lui m me du processeur Il en utilisera en effet une part non n gligeable pour r aliser l ordonnancement pour dialoguer avec les agents se trouvant sur le m me processeur que lui et galement pour dialoguer avec les autres APRC se trouvant sur d autres processeurs voir la section 4 3 pour ce dernier point 4 1 3 2 Un algorithme qui r pond nos besoins Nous pr sentons maintenant l algorithme que nous avons mis au point pour r pondre notre besoin d ordonnancement Le but est ici de prouver la faisabilit d un syst me prenant en compte les contraintes pr c demment cit es Nous d taillons plus loin les avantages et les inconv nients de notre solution 4 1 3 2 1 Mod lisation Les requ tes sont sous la forme ET DL ET est le temps artifact affecter la t che 7 avant
197. re les agents OpenMP OpenMP OpenMP propose un mod le de programmation m moire partag e Il se pr sente sous la forme d une biblioth que C C ou Fortran qui encapsule la gestion de processus l gers et rend la communication entre les fils d ex cution implicite 28 Chapitre 2 Contexte Un programme OpenMP classique commence son ex cution de mani re s quentielle Cela corres pond a la tache maitre charg e de lancer une quipe de taches filles qui s ex cutent toutes en m me temps dans la r gion parall le du programme A la fin des calculs toutes les taches se synchronisent et seule la t che ma tre continue son ex cution OpenMP propose des directives que l on rajoute un programme s quentiel pour le transformer en un programme parall le On peut ainsi tr s facilement parall liser des boucles L exemple suivant montre comment utiliser n processus l gers en parall le pour parcourir une boucle for int 1 Cr d omp_set_num_threads n pragma omp parallel pragma omp for schedule static 5 private c for i 0 i lt max itt c i d f c La variable c est priv e chacun des processus l gers il y aura une copie ind pendante de c pour chaque processus l ger En revanche la variable d est partag e par l ensemble des processus l gers Les indices des it rations donn es chaque processus l ger sont d termin s selon la politique d or donnancement chois
198. rer d une machine l autre Cela ouvre des perspectives quant V utilisation de nos techniques dans le cadre de l quilibrage de charges sur un r seau de machines Les propositions pr c dentes ont t valu es sur la plate forme multi agent ALBA d velopp e au sein de Thales Division A roport e Nous avons implant dans cette plate forme un mod le d agent bas sur des Fils De Raisonnement qui permettent de g rer de mani re d terministe un ensemble de contextes de communication et de raisonnements J ai r impl ment application Interloc de localisation passive de bateaux en utilisant les artifacts de calcul et l APRC La nouvelle version apporte une meilleure gestion des temps de calcul ainsi que des gains susbtanciels au niveau de la clart de la mod lisation Les propositions faites dans cette th se pourront l avenir tre utilis es dans les syst mes multi agents pour lesquels les dur es des calculs entrepris par les agents posent probl me et ou lorsque 121 l on veut pouvoir imposer des d lais aux t ches de calcul Elles permettent de r duire le foss qui existe entre le niveau agent et le niveau syst me tout en ayant la possibilit de consid rer les agents selon un haut niveau d abstraction Les artifacts de calcul sont un nouveau type d entit s que l on peut int grer dans les syst mes multi agents existants Il faut pour cela d crire le fonctionnement des algorithmes qu
199. rer notre pratique de l enseignement Je suis impressionn par notre capacit nous entraider et nous soutenir dans les moments o nous sommes d bord s Je suis extr mement heureux que l aventure puisse continuer apr s cette th se Merci surtout C cile qui m a soutenu durant ces trois ann es Je n aurais certainement pas pu aller au bout de ce travail sans ses encouragements Ce travail de th se a t financ par Thales Syst mes A roport s le conseil r gional du Nord Pas de Calais et l Institut Sup rieur de l lectronique et du Num rique il 111 A mon fils Mathieu concu durant la r daction de cette these iv R sum Nous posons dans cette th se le probl me du respect de d lais dans les syst mes multi agents cognitifs Les syst mes de gestion du temps utilis s dans ce cadre doivent r pondre a un certain nombre de contraintes principalement li es aux sp cificit s attribu es aux agents Ainsi le syst me d attribution des ressources processeur charg de garantir des d lais aux t ches de calcul doit respecter l autonomie et la conscience du temps de nos agents Notre but est de proposer aux programmeurs de syst mes base d agents intelligents des outils permettant de g rer l ex cution simultan e d algorithmes complexes en particulier ceux issus des recherches en Intelligence Artificielle Ces derniers posent souvent des probl mes d int gration tant leur temps d
200. robl me notamment dans les simulations o l on veut pouvoir com presser le temps en jouant sur la rapidit d avancement de l horloge virtuelle utilis e pour cadencer la simulation D un autre c t on associe g n ralement la notion de r activit l arriv e d v nements ext rieurs L id e est de g rer au mieux la file d attente des messages entrants en fonction du temps Qui ne s est jamais exclam C est une usine gaz en lisant la description d une architecture complexe M me en ayant une vision tr s litiste de la programmation il para t clair qu un programmeur ne doit jamais se sentir d pass par le syst me qu il utilise 6 Chapitre 1 Introduction de latence maximal que l on s autorise avant qu un v nement ne soit trait Il convient toujours de trouver le bon compromis entre r activit et cognition un agent qui est en train de concevoir ou d ex cuter un plan doit rester capable de prendre en compte les v nements ext rieurs quitte devoir remettre en cause ce qu il avait d j planifi Les travaux sur les protocoles de communication entre agents ont permis de mieux structurer la mani re de prendre en compte l v nement particulier qu est l arriv e d un message Notons que le comportement d un agent pro actif ne peut pas tre exclusive ment dirig par l arriv e de messages En effet si ses interlocuteurs d cident de ne pas envoyer les mes
201. roche ceci jusqu sa terminaison compl te Il supprime de la liste des t ches celle qui vient de se terminer d termine celle dont la date limite est maintenant la plus proche et d bute son ex cution EDF permet de respecter toutes les ch ances jusqu un taux d occupation de 100 et il est optimal dans la classe des algorithmes priorit s dynamiques 2 2 Travaux connexes 25 Less Laxity First LLE est une variante d EDF qui dispose des m mes propri t s On favorise ici les t ches urgentes en ex cutant un instant donn la tache dont la marge ch ance dur e d ex cution restant est la plus faible Il est possible de lancer sur un syst me temps r el des processus qui n ont pas de contraintes temporelles On fait pour cela apparaitre la notion de priorit entre les deux classes de processus Les processus temps r el ont une priorit stricte par rapport aux processus non temps r el Ainsi les seconds ne peuvent s ex cuter que dans les trous laiss s par les premiers dans ordonnancement Lorsque le syst me est en surcharge ce sont tout d abord les processus non temps r el qui ne peuvent plus s ex cuter Si cela ne suffit pas il faut accepter que certaines ch ances ne soient pas respect es Rate monotonic est plus int ressant qu EDF en cas de surcharge car ce dernier va p na liser les autres taches pour favoriser la tache qui va manquer son ch ance On peut aussi mettre e
202. ruction op ra toire limite consid rablement les possibilit s de raisonnement que agent peut effectuer sur l instruc tion op ratoire ceci car elle n est plus fixe Le plus simple est d utiliser dans l agent un comportement r actif qui r value chaque tape la bonne action r aliser C est ce que nous faisons actuellement dans nos syst mes voir section 5 1 3 3 4 Le langage de mode d emploi des artifacts 69 3 4 3 4 Possibilit s de raisonnement pour Pagent 3 4 3 4 1 Lien s mantique avec la base de connaissances de l agent Les instructions op ratoires donn es seules ne sont d aucune utilit aux agents Il faut leur donner des informations suppl mentaires leur permettant de d cider des actions qu ils vont lancer sur les artifacts et de comprendre les perceptions qu ils vont recevoir en retour On utilise pour cela une s mantique mentale associ e aux actions et percep tions Viroli et Ricci 2004 Elle est d finie dans une table qui indique pour chaque action l tat mental dans lequel l agent doit tre pour d cider de lancer cette action et pour chaque perception les modifications apporter l tat mental Prenons l exemple d un mode d emploi rudimentaire pour un lave linge On peut lancer un cycle de lavage et percevoir sa terminaison puis recommencer autant de fois que l on veut L instruction op ratoire correspondante est la suivante laver_l
203. s il ne tombe pas dans un tat d erreur mais est autoris suivre les ins tructions op ratoires R Les autres r gles sont calqu es sur celles pr sent es dans la section 3 4 2 En particulier la r gle P EXP EXT indique que l on tombe bien dans l tat d erreur y quand une perception n arrive pas temps l artifact reste oblig de respecter son mode d emploi Nous pouvons remarquer que T n R est une g n ralisation de T n En effet T n subsume T n R avec R 3 4 3 3 Utilisation de l historique Comme nous I avions d j soulign dans le cas de T MS l utilisation de boucles avec des struc tures arborescentes n est pas ais e Nous aimerions cependant pouvoir exprimer dans les modes d emploi de nos artifacts des utilisa tions r p titives de certaines fonctionnalit s et galement pouvoir exprimer des conditions d utilisa tion en fonction de l utilisation pass e qui a t faite de l artifact Par exemple concernant le mode d emploi d un lave vaisselle il serait int ressant de pouvoir y sp cifier qu il faut remplir le bac sel tous les dix lavages Cela peut tre r alis en utilisant un tat de l instruction op ratoire par lavage apr s le premier lavage on se retrouve dans un tat identique au pr c dent mais correspondant au second lavage Apr s le dixi me lavage il n est plus possible de remettre en route un nouveau lavage Il faut remplir le bac
204. s applications Ces travaux se concentrent sur la mobilit d agents intelligents Les agents CLAIM peuvent ex cuter plusieurs pro cessus de mani re concurrente et sont organis s en hi rarchies Les primitives de mobilit inspir es du calcul des ambients permettent de quitter ou d entrer dans une hi rarchie CLAIM se place un niveau d abstraction auquel on peut d finir une s mantique op rationnelle dans le but de pouvoir faire de la v rification des programmes La plateforme SyMPA permet de d ployer des hi rarchies d agents sur un syst me distribu Plusieurs hi rarchies peuvent tre plac es sur une m me machine et l on diff rencie donc la migration locale et la migration distance 5 5 Synth se Nous avons pr sent la plateforme multi agent d velopp e au sein de Thales Division A ronau tique Elle se base sur la biblioth que ALBA embarqu e dans chacun des agents Elle est ainsi to talement d centralis e Elle se focalise sur la conception d agents programm s en Prolog et autorise le prototypage rapide de SMA en tant ind pendant du mod le d agent utilis Elle fournit les m ca nismes n cessaires pour que les agents puissent migrer d une machine une autre sur un r seau Nous avons montr comment les artifacts ont pu tre tr s facilement int gr s nos syst mes multi agents d velopp s sur cette plateforme Nous avons pr sent l application Interloc de localisation passive d
205. s dans ces deux cas le pourcentage de mesures ignor es Nous avons utilis s les valeurs suivantes qui sont repr sentatives de ce que l on peut avoir en r alit pour les param tres de l application pr c demment pr sent s 5 4 Exp rimentations 115 nombre de bateaux 10 pi 5 30 secondes en temps r el PD 2 secondes en temps processeur Notre machine de r f rence utilise un processeur Intel Pentium 4 Mobile cadenc 1 6 GHz et disposant de 768 Mo de m moire Dans le premier cas 42 des mesures sont ignor es A cause de la d synchronisation des radars il y a des moments o beaucoup de mesures arrivent peu pr s au m me moment ce qui augmente le nombre de mesures ignor es A d autres moments tous les calculs sur les mesures ant rieures peuvent tre termin s et aucune nouvelle mesure n arrive Le processeur peut ainsi tre inutilis pendant plu sieurs secondes L utilisation des m canismes de coordination de l APRC apporte un gain significatif puisqu il n y a plus que 7 des mesures qui sont ignor es L utilisation du processeur est optimis e car il est utilis constamment sa charge maximum 5 4 2 Equilibrage de charge sur plusieurs processeurs Nous avons r alis d autres exp riences pour mettre en vidence l change d information de charge processeur entre diff rents APRC d ploy s sur plusieurs machines et l utilisation de ces in formations d
206. s le cas contraire Cette d finition implique qu un agent extraverti ne peut s engager aveugl ment dans des t ches de calcul longues qui l emp cheraient de consulter r guli rement sa bo te aux lettres Nous voulons enfin que nos agents soient conscient du temps Nous d finissons cette propri t ainsi D finition 2 2 Agent conscient du temps Un agent est conscient du temps si ses raisonnements et donc son comportement d pendent du temps qui s coule Il ne suffit pas qu un agent raisonne sur le temps pour qu il soit conscient du temps qui passe Il faut de plus que ses raisonnements prennent en compte l coulement du temps pendant ses actions et prises de d cision La connaissance de l coulement du temps s acquiert en consultant l heure aupr s d une horloge L horloge laquelle un agent conscient du temps se r f re n a que peu d importance En particulier il n est pas n cessaire qu elle soit la m me pour les diff rents agents conscients du temps d un m me SMA Remarquons cependant que si des agents conscients du temps doivent partager des informations temporelles pour se coordonner par exemple ils vont devoir se synchroniser sur une horloge commune Nous utiliserons d ailleurs une horloge commune l ensemble des agents se trouvant sur une machine dans le chapitre 4 Un agent conscient du temps pourra planifier des t ches de calcul estimer la dur e n cessaire leur ex c
207. s sur ces travaux notamment ces fameuses trois questions si essentielles Je remercie Patrick pour avoir accept de me prendre en stage de DEA et pour m avoir propos le sujet de cette th se J appr cie ta mani re de conduire des recherches notamment au travers de s ances de brainstorming parfois d stabilisantes mais 6 combien importantes pour faire appara tre de nouvelles id es identifier les failles des propositions et apporter petit petit les am liorations n cessaires Emmanuel tu as t tr s disponible pour me conseiller efficacement tout au long de cette th se Tu as su me soutenir et m encourager aux moments o j en avais besoin Je suis impatient de me mettre travailler sur les nouveaux projets qui nous int ressent tous deux Merci aussi aux autres membres de l quipe SMAC actuels ou pass s Jean Paul Jean Christophe Yann Bruno S bastien Damien Julien Marie H l ne La titia Tony Maxime et tous les autres stagiaires ou tudiants qui ont fait un petit bout de chemin avec nous Je n oublierai pas ambiance qu il peut y avoir dans ce bureau surtout d s que Bruno ou Philippe sont l J ai galement de tr s bons souvenirs des repas d quipe du jeudi midi Les membres du d partement informatique de l ISEN m ont galement beaucoup apport Em manuel Fr d ric les trois Dominique et Pascal Nous avons une vision commune de la p dagogie qui nous pousse toujours am lio
208. s syst mes d exploitation couramment uti lis s sur les machines de bureau Nous ne voulons pas d velopper de syst me large chelle et nous consid rons qu une limite d une dizaine d agents s ex cutant sur un unique processeur est raison nable Nos applications fonctionnent principalement sur une unique machine mais nous sommes la recherche d un syst me permettant de b n ficier de la puissance de calcul de plusieurs processeurs de mani re assez simple Les agents peuvent avoir des contraintes temporelles respecter Celles ci s expriment par le res pect de d lais pour les t ches de calcul Les contraintes temporelles sont molles c est dire qu elles seront satisfaites au plus pr s des dates limites mais pourront les d passer l g rement en fonction de la politique du syst me d exploitation sous jacent qui ne garantit pas le respect de contraintes temporelles dures Un d passement maximal de l ordre de la seconde est autoris dans nos syst mes 14 Chapitre 2 Contexte Les contraintes temporelles sont attach es des taches de calcul g n ralement longues et de toute facon de dur es sup rieures a la seconde La gestion du respect des contraintes temporelles doit tre ind pendante de la mani re avec laquelle l agent d termine ses besoins en ressources processeur Nous consid rons dans la suite qu il n y a pas d interactions directes entre les diff rents algo rithmes mis en uvre
209. sages requis ou qu ils sont perdus l agent resterait bloqu en attente d un message qui n arrivera jamais Il convient de syst matiquement sp cifier le comportement de l agent dans ce cas On met g n ralement en place un syst me de r veil qui r active l agent au bout d un certain temps Ce m me m canisme de r veil peut tre utilis par les autres modules de l agent qui ont besoin d tre activ s des dates donn es Le temps peut galement appara tre dans la base de connaissances de l agent en datant chaque information ou en conservant diff rents historiques croyances actions v nements La base de connaissances est utilis e pour effectuer des raisonnements qui peuvent porter ou tre conditionn s par le temps Le temps est aussi une composante importante dans la v rification des syst mes puisque l on veut pouvoir v rifier qu un agent respectera bien ses sp cifications temporelles et qu aucune condition temporelle ne pourra affecter son fonctionnement Enfin lorsque l on con oit un syst me multi agent qui doit s ex cuter sur un ordinateur on se confronte des aspects beaucoup plus syst me de la gestion du temps comme la gestion et le partage des ressources processeur disponibles ce niveau la difficult principale provient de la confronta tion entre les niveaux d abstraction agent et syst me Au niveau syst me on dispose des notions de processus ou processus l ger
210. seconde machine nous obtenons maintenant un taux de 56 de mesures trait es Ces exp rimentations montrent que les possibilit s de migration offertes par la biblioth que ALBA peuvent tre mises profit pour r aliser de l quilibrage de charge dans nos SMA Ceci n tait pas notre pr occupation principale dans cette tude mais les r sultats encourageants ouvrent de nouvelles pistes de recherche dans ce sens en particulier pour d terminer s il est possible de trouver des politiques d quilibrage de charge d centralis es qui respectent l autonomie de d ci sion des agents Pour poursuivre dans la voie de l quilibrage de charge par migration d agents on pourra s inspirer des travaux sur la mobilit r alis s au LIP6 par Amal El Fallah Seghrouchni Alexandru Suna et Gilles Klein Klein et al 2004 Suna et al 2004 Klein 2005 Suna 2005 El Fallah Seghrouchni et Suna 2005 Cette quipe propose un langage de programmation d agents nomm CLAIM Computational Language for Autonomous Intelligent and Mobile agents et une plateforme d ex cution distribu e nomm e SyMPA System Multi Platform of Agents On retrouve dans ces travaux des motivations identiques celles qui nous animent proposer des techniques de programmation sp cifiques aux syst mes multi agents qui permettent de retrouver dans impl men tation des agents les concepts utilis s au niveau de la mod lisation de
211. sevier Science Publishers B V North Holland Ingrand et al 1992 INGRAND F F GEORGEFF M P et RAO A S 1992 An architecture for real time reasoning and system control IEEE Expert Intelligent Systems and Their Applications 07 6 34 44 Jennings ef al 1998 JENNINGS N R SYCARA K et WOOLDRIDGE M 1998 A roadmap of agent research and development Journal of Autonomous Agents and Multi Agent Systems 1 1 7 38 Jonquet et al 2006 JONQUET C DUGENIE P et CERRI S A 2006 Int gration orient e service des mod les grid et multi agents In JFSMA 06 Journ es Francophones sur les Syst mes Multi Agents Hermes Joseph et Kawamura 2001 JOSEPH S et KAWAMURA T 2001 Agent Engineering chapitre Why Autonomy Makes the Agent World Scientific Publishing Kaptelinin ef al 1995 KAPTELININ V KUUTTI K et BANNON L J 1995 Activity theory Basic concepts and applications In EWHCI pages 189 201 Klein 2005 KLEIN G 2005 Distributed Multiagent Systems and Multiagent Distributed Sys tems Th se de doctorat Universit Paris Dauphine Klein et al 2004 KLEIN G SUNA A et EL FALLAH SEGHROUCHNI A 2004 Resource sha ring and load balancing based on agent mobility In ICEIS 4 pages 350 355 Knuth 1997 KNUTH D E 1997 The Art Of Computer Programming Addison Wesley Longman Publishing Co Inc Boston MA USA Kuwabara et al 1995 KUWABARA K OSATO N et ISHI
212. sion de programmes ind pen dants s ex cutant en parall le bien qu au final il n y ait qu un seul processeur Nous pensons que ce point est tr s important dans notre cadre Quand nous concevons nos agents nous voulons nous placer ce niveau d abstraction pour pouvoir consid rer que les agents s ex cutent en parall le sur le pro cesseur C est cette condition qu on peut les voir comme constamment conscients et qu on peut les programmer de mani re ind pendante Cependant nous voulons que les programmeurs aient le moins de difficult s possible pour construire de tels syst mes Nous nous attacherons dans la suite ce que les outils propos s soient simples comprendre et que leur utilisation soit sans surprise c est dire qu ils devront limiter au maximum l ind terminisme inh rent la programmation multi t che 2 2 2 1 2 Les syst mes d exploitation temps r el Lorsque l on parle de gestion du temps dans les syst mes informatiques on en vient tr s rapide ment voquer les syst mes d exploitation temps r el Un syst me est dit temps r el s il est capable de r aliser les traitements qu on lui demande un rythme adapt aux donn es d entr e qui lui par viennent Un syst me est temps r el dur si toutes les t ches doivent se terminer avant une date donn e sans aucun d passement de d lai Il est temps r el mou s il supporte que les d lais soient l g rement d pas s s
213. sortir D un c t il est important que I artifact respecte son mode d emploi mais d un autre c t il serait int ressant de sp cifier ce qui se passe lorsque c est agent qui a des obligations qu il ne respecte pas Par exemple si l agent dispose de deux secondes pour ex cuter une action et qu il ne le fait pas l artifact ne va pas forc ment cesser d exister ou de fonctionner On aimerait aussi pouvoir sp cifier des comportements de l artifact un peu plus complexes comme l artifact r pond normalement en deux secondes sinon il donnera une r ponse partielle une seconde plus tard Paul douard Marson a propos durant son Master Recherche une g n ralisation de l instruction de timeout permettant d am liorer la gestion des cas o l agent ne respecte pas les d lais qui lui sont impos s Marson 2006 Nous ajoutons une nouvelle instruction T n R o R est une instruction op ratoire et les r gles op rationnelles suivantes I T n R 66 Chapitre 3 Des outils de calcul pour les agents Ta R ma sin gt m A PASS EXT T m R 1 OR sin gt m A VIO EXT a T n R I A a T n m R I sin gt m P PASS EXT a T m RB y y sin gt m_ P EXP EXT T n R lo 1 7 a a 0 1 T ACT EXT am a T n R m I T oz 1 1 1 1 T COMP EXT La r gle A VIO EXT sp cifie que si un agent ne respecte pas les temporisations d finies dans les instructions op ratoire
214. squels interagissent les agents anim s qui sont eux les acteurs de la simulation Ne confondons pas ici anim avec mobile et inanim avec statique En effet un objet anim peut tr s bien rester statique C est le cas par exemple d un pommier qui produit des pommes Par contre un objet inanim ne peut pas tre mobile 4 moins d tre d plac par un agent anim En effet ne pouvant effectuer aucune interaction il ne peut en particulier pas effectuer de d placement ouvrir couper couper casser FIG 3 9 Peut subir peut effectuer La figure 3 9 montre un exemple avec un agent anim b cheron et un agent inanim arbre Le b cheron peut ouvrir couper et tre tu L arbre peut tre coup br l et cass La seule interaction possible en pr sence de ces deux agents est l abattage de l arbre par le b cheron Les actions qu un agent peut subir et effectuer sont exhib es l ext rieur Cela est rapprocher de l interface d usage des artifacts qui indique les actions et perceptions disponibles au sein de I artifact Il n y a cependant pas dans IODA d quivalent des instructions op ratoires car pour l instant les interactions entre les agents sont ind pendantes les unes des autres et s il fallait interagir de mani re continue et ordonn e avec un autre agent la suite des interactions serait d termin e par le moteur de planification de l agent Remarquons cependant que dans
215. ssances de l agent Ceci n est pas satisfaisant Il serait plus int ressant que le formalisme utilis permette de d crire des modes d emploi auto descriptifs Nous avons galement identifi d autres points qui manquent encore pour g rer les interactions du couple agent artifact de mani re satisfaisante En particulier la d cou verte de nouveaux artifacts de calculs l ex cution et leur mise en uvre de mani re automatique gr ce la compr hension de leur mode d emploi est un probl me difficile pour lequel le formalisme actuellement utilis ne propose pas de solution J ai propos dans un second temps des outils bas s sur les artifacts pour g rer le partage des res sources processeur en prenant en compte toutes les contraintes que pose pour cela le paradigme agent En effet il est important que les agents puissent conserver leur autonomie de d cision m me s il existe une entit l Artifact de Partage des Ressources de Calcul APRC qui calcule l ordonancement des t ches sur le processeur Je propose un algorithme d ordonnancement qui permet aux artifacts de calcul de respecter des contraintes de calcul tout en permettant de consid rer que les agents sont actifs en permanence Le syst me initialement d velopp pour un unique processeur peut tre tendu plusieurs ma chines en changeant au niveau des diff rents APRC les informations de charge de leur processeur et en autorisant les agents mig
216. sseur disponibles qu elles soient centralis es ou dis tribu es Nous avons ensuite rappel ce qu est un algorithme et quelles sont les classifications qui ont t propos es Nous avons d crit comment il est possible de r soudre des probl mes ayant des complexi t s lev es en des temps raisonnables et contr lables en utilisant des heuristiques et des algorithmes incr mentaux voire m me anytime Nous avons parcouru les diff rentes techniques propos es pour distribuer des calculs dans plu sieurs fils d ex cution ceux ci s ex cutant sur une unique machine ou dans un environnement dis tribu Nous avons remarqu que la programmation de syst mes distribu s est tr s complexe et qu il convient d utiliser des outils qui permettent de d coupler au maximum les diff rentes entit s et qui suppriment au maximum l ind terminisme Nous nous sommes pench s sur les m thodes de gestion et de raisonnement sur le temps dans les syst mes intelligents Les techniques de base permettent de raisonner sur le temps de mani re discr te ou continue et m me sur des dur es incertaines mais elles ne prennent pas en compte la dualit cognitif r actif n cessaire au bon fonctionnement d un SMA Cette dualit est prise en compte par les mod les d agent hybrides Enfin nous avons identifi un certain nombre de fonctionnalit s int ressantes pour notre tude dans les langages et architectures d agents propos s dans la li
217. st utilis e que pendant la phase de mod lisation Et ce sont les techniques objet classiques qui sont utilis es 1 3 La combinaison des deux domaines pour am liorer la gestion du temps 5 pour l impl mentation Nous pensons au contraire que comme le paradigme agent utilise un haut niveau d abstraction les d veloppeurs devraient avoir a leur disposition des outils galement de haut niveau qui leur permettent de s abstraire des difficult s de plus bas niveau Le foss r duit entre la mod lisation et l impl mentation est certainement une des caract ristiques qui fait le succ s d un paradigme comme c est le cas avec l objet 1 3 La combinaison des deux domaines pour am liorer la gestion du temps dans les SMA Nous aimerions pouvoir utiliser dans nos syst mes multi agents le plus grand nombre possible de r sultats des recherches en IA qui am liorent la gestion du temps Nous aimerions galement pouvoir apporter aux syst mes issus de l IA des outils de niveau m ta permettant d am liorer leur comportement temporel Les principes du g nie logiciel entrent cependant parfois en conflit avec les m thodes imagin es 2 Si on ne pour r soudre des probl mes en particulier les probl mes tr s complexes trait s par PIA prend pas garde aux probl mes de mise en uvre des techniques que nous utilisons et proposons on risque de se retrouver avec un syst me trop complexe pour pouvoir tre utilis
218. sur la dur e du calcul pour converger vers la valeur finale la m me valeur PD est utilis e comme contrat de temps pour le propagateur de contraintes pour chaque nouvelle t che Donc VV Tij PD A la fin du contrat un r sultat est toujours disponible car gr ce la monotonie de la proc dure de r tr cissement de la zone de localisation utilis par le propagateur sur intervalles il y a tout moment un intervalle valide contenant la position actuelle du bateau qui peut tre retourn 5 3 Nouvelle mod lisation d Interloc avec les artifacts La gestion des temps de traitement est primordiale pour un agent utilisant le type d algorithme d crit dans le paragraphe pr c dent En effet la dur e des calculs peut changer de mani re consid rable car des ph nom nes de convergence lente peuvent appara tre lors du processus de propagation Lhomme et al 1994 Pour conserver son autonomie ne serait ce que pour pouvoir d cider d aban donner la poursuite d un bateau donn si celle ci devient inutile l agent doit donc se prot ger de blocages ventuels La cr ation d un artifact de calcul est donc apparue comme une bonne solution car elle permettait de d coupler la partie cognitive de l agent de celle charg e d effectuer les calculs laissant l agent la possibilit d une d lib ration pour d cider d arr ter un calcul devenu trop long ou de prendre en compte ou non une mesure nouvellemen
219. t ristiques essentielles de T MS q_exactly_one T EMS sera principalement utilis dans des cas o il existe diff rentes alterna tives pour r aliser une t che C est le cas ici avec l eau qui peut tre prise chaude ou froide L ordon nanceur pourra ainsi choisir entre les deux en fonction de l tat des ressources et des crit res fournis pour la recherche de solution Nous voyons galement que certaines actions doivent tre ordonn es gr ce la relation Permet on ne peut pas moudre les grains de caf avant de les poss der Notons enfin que T MS permet de g rer des ressources qui sont utilis es par les diff rentes t ches Les ressources peuvent tre consom mables ou non consommables Il est possible d indiquer les limites hautes et basses ainsi que le niveau 3Ce qui a actuellement une raisonnance particuli re pour l auteur 44 Chapitre 2 Contexte Acqu rir les ingredients gt a Permet 277 q min ye Ne j S LE l Obtenir du caf pens Faire passer le caf N A _ _ Prendre de Prendre de jee 7 Utiliser du caf Peau chaude Peau froide Acqu rir du caf moulu instantan Limite Consomme 4 min 1 Permet Limite
220. t t cognitifs que r actifs La r activit d un agent est galement vue comme la capacit de prendre en compte les change ments de l environnement a temps L introduction des artifacts de calcul a t faite initialement dans le but de permettre la r activit des agents en les d chargeant des calculs longs qui les emp che raient de prendre en compte les informations venant de l ext rieur Les artifacts sont plut t introvertis et ne garantissent aucune r activit par rapport aux changements dans l environnement Un des autres points fondamentaux qui diff rencient les artifacts des agents est la mani re dont on interagit avec eux Suivant la tradition initi e par les travaux de John Searle les agents interagissent entre eux par actes de langages tell request Les agents ont le choix de prendre en compte ou non les messages qui leur parvienne Au contraire un agent interagit avec un artifact au moyen des actions et des perceptions Lors qu un agent effectue une action sur un artifact celle ci est automatiquement r alis e sans que l ar tifact ait le choix de refuser La diff rence existe galement au niveau des perceptions puisque les r ponses faites par les artifacts sont pr vues dans leur mode d emploi Aucun message ne peut arriver un moment impr vu ou d passer sa date limite d arriv e 76 Chapitre 3 Des outils de calcul pour les agents Agent Artifact Autonome P
221. t arriv e L artifact peut bien s r tre impl ment comme un agent ne poss dant pas de capacit de d cision propres c est d ailleurs ainsi que nous avions proc d initialement Cependant le type d interaction r gissant les rapports entre larti fact et les autres agents est diff rent des rapports entre agents Ainsi comme nous l avons montr dans Dinont ef al 2006a il doit tre possible de suspendre puis relancer l ex cution de l artifact afin de pouvoir exploiter au mieux les ressources offertes par la machine h te ce qui n est pas souhaitable pour un agent r ellement autonome souhaitant pouvoir r agir aux changements de son environnement Par ailleurs le comportement des artifacts est connu l avance et la programmation de la d lib ration de l agent peut donc en tenir compte ce qui la rend notablement plus ais e Dans l article Dinont et al 2006a nous avons montr comment le contr le d un tel artifact et Putilisation d un artifact de coordination permettait la fois de garantir que l agent tait en mesure de d cider de son comportement lors de l arriv e d une nouvelle mesure contrat de temps termin et une meilleure utilisation de la puissance de calcul Nous nous pla ons ici dans le cas o il n y a pas d artifact de coordination et donc o l agent g re lui m me ses relations avec l artifact de calcul Pour d crire ce dernier
222. te des m canismes fondamentaux de la concurrence ainsi qu un calcul pour raisonner sur les programmes concurrents A sa suite s est d velopp e une approche alg braico axiomatique de la th orie de la concurrence connue sous le nom d alg bre de processus La diff rence entre les travaux initiaux de Milner et les alg bres de processus actuelles r side dans l approche suivie pour d crire la concurrence Dans les premiers travaux tous les processus sont synchronis s sur une horloge universelle et on se donne des outils pour rompre cette organisation de mani re pouvoir exprimer l asynchronisme Dans les alg bres de processus les processus sont vus comme des entit s autonomes donc asynchrones et l on se donne les moyens d organiser la coh rence du syst me de processus Un processus p est con u abstraitement comme un objet qui accomplit certaines actions a et ce faisant se reconfigure en un autre processus p Cette relation est d not e par p gt p Un processus se termine avec succ s tat s il n est plus constitu que d une action atomique et que celle ci est ex cut e a La plupart des alg bres de processus contiennent des op rateurs de base pour construire des pro cessus finis des op rateurs de communication pour exprimer la concurrence et une certaine notion de r cursion pour repr senter les comportements infinis Les alg bres de processus permettent un raisonnement formel
223. tement alors que lorsqu on utilise la programmation v nementielle les messages peuvent tre consid r s de mani re asynchrone ou m me tre compl tement ignor s Les attributs n existent pas dans la d finition de base propos e par l quipe italienne Nous les ajoutons pour fournir de mani re simple la propri t d inspectabilit indiqu e dans Omicini et al 2004 Pour tre inspectable un artifact doit exhiber des propri t s qui peuvent tre statiques ou dynamiques Les propri t s statiques comprennent l interface d usage les instruc tions op ratoires et la fonction Les propri t s dynamiques sont repr sent es par les attributs Ceux ci ont deux fonctions Ils permettent tout d abord aux agents de configurer un artifact avant de I utiliser Ils permettent ensuite l inspectabilit des propri t s dynamiques de artifact pendant son utilisation A ce moment ils passent en lecture seule pour viter les conflits d acc s lorsque I artifact veut mo 56 Chapitre 3 Des outils de calcul pour les agents difier les valeurs de ses attributs Nous consid rons que l tat actuel des instructions op ratoires de l artifact constitue un attribut obligatoire La sp cification du comportement peut permettre de faire des v rifications formelles sur le fonc tionnement interne de l agent Nous n utilisons pas cette possibilit dans nos syst mes A nos yeux la caract ristique la
224. tems used within this context must meet constraints mainly linked with the properties attributed to agents Thus the CPU resources allocation system that ensures deadlines meeting have to respect the autonomy and time awareness of our agents Our aim is to propose tools allowing to manage the simultaneous execution of complex algorithms especially algorithms stemming from the Artificial Intelligence field Those algorithms are often hard to integrate in multi agent systems as their execution times can be long and hard to predict Indeed agents which would use this kind of algorithms without specific tools could lose consciousness and would be unable to stay aware of their environment To solve these problems we propose to introduce in multi agent systems a new entity that can be viewed as a computational tool the agents can use to do their heavy computations and thus staying aware of their environment For this purpose we extend the artifact concept proposed by Omicini Ricci and Viroli in 2004 We also propose to use a coordination artifact which allows to attribute CPU resources according to the constraints of every agent When there is an inconsistency in the set of constraints agents can use the coordination artifact as an intermediary to solve it Our propositions have been implemented using the agent development platform ALBA designed at Thales Airborne Division and validated by re engineering an existing application Keywords Multi ag
225. threads de priorit d ordonnancement de processus avec respect de d lais ou non de temps partag Au niveau agent on parlera plut t d autonomie de pro activit de r activit de contextes de communication ou de raisonnement Les solutions propos es au niveau du syst me d exploitation pour g rer le partage des ressources proces seur entrent en conflit avec les propri t s recherch es au niveau agent Par exemple la notion de priorit g r e de mani re centralis e au niveau de l ordonnanceur du syst me limite consid rablement l autonomie des agents De plus le syst me ne dispose pas des informations qui pourraient tre utiles pour prendre de bonnes d cisions En effet le syst me se trouve un niveau d abstraction inf rieur au niveau agent et n a pas acc s aux connaissances des agents sur leurs besoins en ressources processeur sur les d lais qu ils doivent respecter sur la marge de man uvre dont ils disposent sur leurs interactions Cela peut galement poser des limites par rapport aux autres propri t s des agents 1 4 Objectifs Nous avons remarqu dans la section pr c dente que la gestion du temps est multi forme Nous nous int ressons dans cette th se uniquement a l aspect syst me la gestion et le partage des ressources 1 4 Objectifs 7 processeur entre les diff rents agents Nous avons en effet choisi d utiliser une approche ascendante pour pouvoir prendre en compte p
226. ticipation 2 2 Travaux connexes 31 des migrations Ce dernier point est tr s important si on n utilise pas de r seau d di large bande passante car le co t des communications devient plus grand que le co t des calculs Les projets de recherche actuels comme XtremWeb Cappello et al 2005 d velopp au LRI a Paris tendent a rendre ces syst mes totalement distribu s en se reposant sur les techniques des sys t mes pair pair Dans ce type d architecture les applications qui proposent des calculs r aliser sont elles m mes int gr es au syst me comme des pairs volontaires 2 2 3 Gestion du temps dans les syst mes intelligents Nous pr sentons dans cette section un tour d horizon de la mani re dont peut tre g r le temps dans les syst mes intelligents Les syst mes intelligents peuvent tout d abord tre con us pour raison ner sur le temps et ceci ind pendamment de l ex cution effective des actions d cid es par l agent Les agents peuvent galement avoir besoin de r agir rapidement aux v nements qui se produisent dans leur environnement ou de g rer de mani re efficace leurs conversations avec les autres agents Nous verrons galement comment les diff rents langages et architectures d agents propos s g rent le temps et la dur e des actions que les agents entreprennent dans leur environnement 2 2 3 1 Langages et techniques pour le raisonnement temporel 2 2 3 1 1 La
227. tion 2 1 1 Nous trouvons galement tr s important que les applications multi agents que nous d veloppons puissent s ex cuter sur des machines de bureau classiques et donc sur les syst mes d exploitation classiquement install s sur ce type de machines Windows Unix Il ne parait pas concevable de devoir installer un syst me d exploitation particulier temps r el par exemple pour que nos applications fonctionnent L architecture de nos SMA devra donc s adapter ce type de syst me en tentant d utiliser au mieux les fonctionnalit s de gestion des processus propos s S il manque des fonctionnalit s comme la gestion de d lais sur les t ches voir section 4 1 elles devront tre apport es par les biblioth ques de nos SMA sans avoir toucher au syst me d exploitation lui m me 2 1 Expos du probl me 13 2 1 3 2 Partage de plusieurs processeurs Nous venons d indiquer que nous devons fournir des outils pour que nos agents puissent partager un unique processeur I ne faut cependant en aucun cas se limiter l utilisation d un unique processeur si plusieurs autres sont disponibles Nous devons galement fournir des outils permettant de r partir les agents sur diff rentes machines La politique de r partition effective doit tre laiss e au concepteur de chaque application mais nous pouvons fournir des outils aidant la mise en place de telle ou telle politique de r partition Nous pouvons
228. tion de l agent utilisant un artifact est le mode d emploi de I artifact les instructions op ratoires Deux situations ont t consid r es La premi re correspond une utilisation de l artifact de propagation de contraintes sans contrat de temps En cas de convergence lente l agent n est pas bloqu mais le calcul continue jusqu son terme qui peut tre tr s lointain L agent a n anmoins la possibilit de tuer d finitivement I artifact Le mode d emploi correspondant est le suivant OIl stop add_constraint C syntax_error OIl success OIl propagate result E I O11 Lorsque l artifact est au repos l agent peut le stopper ou ajouter une nouvelle contrainte Apr s l ajout d une contrainte il peut percevoir qu il y avait une erreur de syntaxe dans sa contrainte et dans ce cas il reboucle sur la m me instruction op ratoire pour arr ter l artifact ou lui reproposer une nouvelle contrainte Dans le cas o la nouvelle contrainte est correcte l agent peut ajouter de nouvelles contraintes ou lancer le calcul Il est important de remarquer qu en disposant de cette instruction op ratoire l agent peut d terminer qu une fois le calcul lanc par l action propagate il recevra obligatoirement un r sultat mais dans un temps ind termin La seconde situation correspond au cas o la r solution s accompagne d un contrat de temps au bout duquel l
229. tion que nous avons choisie ce sont les agents qui ont le moins de marge de manceuvre qui vont migrer vers la seconde machine la marge de manceuvre est la diff rence entre le d lai donn a la tache et le temps n cessaire 4 son ex cution On va donc se retrouver dans une situation de d s quilibre les bateaux pour lesquels les p sont grands vont tre trait s sur la premi re machine tandis que les bateaux pour lesquels les p sont petits vont tre trait s sur la seconde machine Les calculs effectu s ont moins de marge de man uvre pour tre ordonnanc es et APRC est oblig de refuser norm ment de nouvelles taches de calcul Cela est aggrav par la diff rence de rapidit entre les deux machines Au final on n obtient que 22 de mesures trait es Nous avons enfin test une politique de migration qui arrive mieux s lectionner les agents qui doivent migrer pour limiter le nombre de mesures ignor es Les agents ont toujours comme objectif de migrer d s qu ils voient une de leur t che refus e par APRC mais ils demandent auparavant P APRC s ils ont int r t le faire ou non L APRC concern va demander son homologue sur l autre 5 5 Synth se 117 machine la moyenne des marges de manceuvre pour les t ches qu il a ordonnanc es Il la compare a la sienne et autorise l agent migrer si la migration permet de r duire l cart entre les deux valeurs Pour un m me nombre d agents ayant migr sur la
230. tis est command e par les agents extravertis Un agent extraverti n gocie des tranches de temps pour des t ches calculatoires r alis es par des agents introvertis aupr s d un agent de services temporels AST L utilisation de l AST permet de garantir que les t ches se terminent avant leur date limite Les agents extravertis ont la charge de d marrer et de mettre en pause les agents introvertis qui travaillent pour eux Cette solution correcte pose cependant plusieurs probl mes conceptuels d s principalement au fait que l on attribue g n ralement aux agents la propri t d autonomie La question de l autonomie a d j t beaucoup trait e et de nombreuses d finitions ont t pro pos es Luck et d Inverno 2001 Carabelea et al 2003 Joseph et Kawamura 2001 Nous posons ici une fois de plus ce probl me dans le but d aboutir une vision pragmatique de l autonomie qui peut avoir un sens du point de vue op rationnel et qui s adapte bien notre cadre d tude 52 Chapitre 3 Des outils de calcul pour les agents Le probl me provient du fait que l on pr sente le paradigme agent comme une solution pour casser la complexit structurelle des syst mes et ceci grace a la propri t d autonomie des agents L autonomie serait ainsi le gage d un couplage le plus faible possible entre les agents Mettons nous maintenant a la place d un programmeur fraichement initi au p
231. torique des actions entreprises par l agent Il est possible de sp cifier dans le programme de l agent des actions a r aliser dans le futur Cela se fait en ajoutant des annotations temporelles aux pr conditions des actions Celles ci peuvent tre sp cifi es sous forme de dates ou d intervalles entre deux dates TAP poss de bon nombre de propri t s int ressantes dans notre cadre on dispose d une en capsulation de code h rit qui permet de raisonner dessus les actions s inscrivent dans la dur e on peut suivre leur d roulement et prendre des d cisions en fonction des informations conserv es dans Vhistorique Il est cependant dommage que ce syst me soit compl tement d corell du syst me d exploitation 2 2 3 4 6 DECAF DECAF Distributed Environment Centered Agent Framework Graham et al 2003 Graham 2001 est une infrastructure pour le d veloppement de syst mes multi agents d velopp e a l universit du Delaware DECAF propose de programmer les agents de mani re graphique dans un module nomm Plan Editor Celui ci permet de d crire un r seau de t che hi rarchique semblable aux structures de t ches de T EMS et l ex cution des plans est dirig e la mani re de RETSINA Reusable Environment for Task Structured Intelligent Networked Agents Williamson et al 1996 DECAF peut tre vue comme une infrastructure agent de seconde g n ration La premi re
232. tt rature C est le cas par exemple de la gestion tr s simple de l agenda dans Agent 0 de la structure de t che de T MS annot e de telle mani re que l agent peut raisonner sur les diff rentes alternatives en fonction de ses contraintes ou encore de la mani re avec laquelle Temporal Agent Programs lie un langage logique du code h rit Chapitre 3 Des outils de calcul pour les agents Un mauvais ouvrier a toujours de mauvais outils Proverbe Si l homme ne faconne pas ses outils les outils le faconneront Arthur Miller Mains outils de l esprit sans lesquels la pens e n est que chimere Alain Aslan Dans ce chapitre nous nous demandons comment doivent tre consid r es les fonctionnalit s de calcul des agents Nous ne nous pr occupons pas des probl mes de gestion des d lais donn s aux t ches de calcul qui seront trait s dans le prochain chapitre Nous nous int ressons plus particuli rement la mani re de les encapsuler pour faciliter leur manipulation par les agents Dans ce cadre nous aimerions pouvoir fournir des modes d emploi des algorithmes utilis s sur lesquels les agents pourront raisonner Les algorithmes ne seront ainsi plus consid r s comme des boites pour lesquelles on ne dispose d aucune information sur le d roulement du calcul des bo tes noires Ils seront au contraire consid r s comme des bo tes pour lesquelles on dispose de certaines informations sur le d roulement d
233. tte machine et qu il pourra s ex cuter ici parti envoie un message de rappel l agent agent 5 pour lui indiquer qu il peut migrer maintenant i L agent agent 5 a commenc migrer Je le prends d sormais en compte dans le calcul de l ordon 10 54 01 J autorise l agent agent 3 migrer apr s la fin de ses travaux qui se terminent 10 55 06 10 55 24 L agent agent 3 m indique qu il a migr Je ne le prends plus en compte dans le calcul de l ordonn 6 L agent agent 3 me demande quelle date il peut commencer s ex cuter sur cette machine lancement 3 06 J indique l agent agent 3 qu il est 10 5 ur cette machine et qu il pourra s ex cuter ici parti 0 l envoie un message de rappel l agent agent 3 pour lui indiquer qu il peut migrer maintenant 10 55 10 L agent agent 3 a commenc migrer Je le prends d sormais en compte dans le calcul de l ordon nancement FIG 5 5 Capture d cran de l interface de visualisation en mode 2 machines Les r sultats font apparaitre que la migration d un agent sur la seconde machine permet de limiter a moins de 1 le nombre de mesures ignor es et que la migration de deux agents permet d obtenir 100 de mesures trait es Nous avons dans un second temps augment le nombre de bateaux jusqu a 20 Dans cette situation il y aun plus grand nombre d agents qui migrent vers la seconde machine Cependant avec la politique de migra
234. tut Sup rieur de l lectronique et du Num rique ISEN 1 1 Le but de PIA concevoir des agents La question de l intelligence des machines a t soulev e avant m me que le premier ordinateur ne soit construit La vision premi re sous tendue par le fameux test de Turing tait qu une machine pourrait tre consid r e comme intelligente si son comportement vu par un observateur pouvait tre confondu avec celui d un Homme Cette vision a regu de nombreuses critiques en particulier parce qu une machine pourrait r ussir a passer le test de Turing en trouvant les r ponses aux questions qu on lui pose dans une immense table ce qui a peu d int r t du point de vue de la recherche 2 Chapitre 1 Introduction Par la suite c est une vision plus scientifique qui a vu le jour Le but de copier le comportement humain a t mis de c t pour tre remplac par tude syst matique de deux th matiques la repr sentation et la manipulation des connaissances ainsi que la recherche de solutions un probl me dans un espace contenant norm ment d l ments Le nom Intelligence Artificielle pour ce nouveau domaine de recherche a t choisi lors de la r union d un groupe de travail organis par John McCarthy au Darthmouth College durant t 1956 Newell et Simon y ont pr sent leur programme nomm Logic Theorist qui a t capable de trouver une preuve pour un th or me qui tait plus courte que
235. u on leur ordonne de r aliser Puis je d finir un mode d emploi pr cis que l entit respectera Lorsque le comportement d une entit est tr s clairement d fini et qu il peut s exprimer dans le langage de mode d emploi fourni il est pr f rable de consid rer cette entit comme un artifact Nous avions remarqu que concevoir des agents r ellement autonomes pouvait poser beaucoup de pro bl mes dans l impl mentation des agents pour g rer toutes les r actions possibles des autres agents LV introduction d un maximum d artifacts permet de limiter la complexit de programmation de cha cune des entit s Attention cependant qu il peut arriver que l on arrive d finir un mode d emploi pr cis pour une entit mais que celui ci ne soit pas exprimable dans le langage de mode d emploi disponible On ne pourra dans ce cas pas consid rer l entit comme un artifact mais comme un agent La fonctionnalit identifi e a t elle une persistance en dehors du cycle de vie des agents La r ponse cette question permet d avoir un argument suppl mentaire pour choisir d externaliser une fonctionnalit et ainsi cr er un artifact pour la g rer La fonctionnalit que j ai identifi e utilise t elle du code h rit sur lequel je n ai pas ou peu de contr le Si c est le cas il faut l instancier dans un artifact de calcul puisque ceux ci ont t propos s pour fournir une encapsulation des codes h rit
236. u calcul des bo tes translucides Nous voulons galement trouver un moyen pour que les agents puissent lancer de multiples t ches de calcul tout en conservant un comportement extraverti c est dire qu il doivent rester capables de prendre en compte les changements de l environnement Concernant ce dernier point nous nous attacherons ce que la solution permette une programmation ais e des agents Les travaux de cette partie se basent sur la notion d artifact introduite dans Viroli et Ricci 2004 et d crite dans la section 3 2 Nous r utilisons le formalisme initialement introduit par Omicini Ricci et Viroli Il est d crit dans la section 3 4 Je propose dans la section 3 3lune nouvelle classe d artifacts 49 50 Chapitre 3 Des outils de calcul pour les agents pour l encapsulation des calculs longs les artifacts de calcul Je pr sente dans la section 3 4 3 les extensions que nous avons apport es au formalisme pour le flexibiliser et le rendre compatible avec les artifacts de calcul Je propose dans la section 3 4 4 une classification des algorithmes que nous encapsulons dans les artifacts de calcul et je fournis les modes d emploi qui permettent de les contr ler 3 1 Position du probleme 3 1 1 Besoin d un nouveau type d entit ES Nous voulons que les agents conservent un comportement extraverti tout en tant capable d ex
237. u dessus du niveau basique Chaque processus poss de sa file d attente de messages entrants Des mod les de message patterns sont utilis s pour filtrer les messages entrants accept s un moment donn Ainsi on peut retirer de la file d attente certains messages et en laisser d autres Quand aucun message ne correspond aux mod les le processus est suspendu Il sera r activ lorsqu un nouveau message arrivera Comme il est tr s difficile de pr server l ordre des messages dans un SMA distribu pouvoir acc der toute la file des messages en attente para t tre important Avec le syst me propos par April le programmeur n a plus se soucier de reconstituer l ordre cela est fait automatiquement car quand un message arrive en avance par rapport un autre son traitement peut tre diff r L exemple suivant d crit un serveur qui ex cute ind finiment une t che T lorsqu il re oit un mes sage lui indiquant de la r aliser avec les param tres params puis qui renvoie un message indiquant que l action a t r alis e server any T repeat do any params gt T arg Done gt gt replyto until quit Le mod le de message utilis est do any arg any indique que la variable params peut tre de n importe quel type Lorsqu un moment du programme on s attend recevoir plusieurs types de messages on utilise le ou sur les patterns L exemple suivant indique comment r
238. u mat riel Les cher cheurs dans ce domaine sont maintenant demandeurs de techniques permettant d ajouter une couche d intelligence leurs syst mes et de d centraliser le contr le des calculs La encore les travaux sur les artifacts de calculs pourraient tre transf r s ce type d applications 126 Chapitre 7 Perspectives Bibliographie Alur ef al 1998 ALUR R HENZINGER T A et KUPFERMAN O 1998 Alternating time tem poral logic Lecture Notes in Computer Science 1536 23 60 Arisha et al 1999 ARISHA K A OZCAN F ROSS R SUBRAHMANIAN V S EITER T et KRAUS S 1999 IMPACT A platform for collaborating agents IEEE Intelligent Systems 14 2 64 72 Barbuceanu et Fox 1995 BARBUCEANU M et Fox M S 1995 Cool A language for descri bing coordination in multiagent systems In LESSER V et GASSER L diteurs Proceedings of the First International Conference oil Multi Agent Systems ICMAS 95 pages 17 24 San Fran cisco CA USA AAAI Press Basseur 2005 BASSEUR M 2005 Conception d algorithmes coop ratifs pour l optimisation multi objectif Application aux probl mes d ordonnancement de type Flow shop Th se de docto rat Universit Lille 1 Boddy et Dean 1989 BoDDY M et DEAN T 1989 Solving time dependent planning problems Rapport technique Botella et Taillibert 1993 BOTELLA B et TAILLIBERT P 1993 Interlog Constraint logic pro gra
239. ura perdu une bonne partie de l int r t du paradigme agent Nous nous attacherons donc ce que ces propri t s soient conserv es dans nos syst mes quitte faire des sacrifices sur d autres aspects La question du sens pr cis que nous donnons l autonomie dans nos SMA sera trait e en profon deur dans la section 3 1 3 lorsque nous aurons clairement d fini l environnement dans lequel s ex cutent nos agents Nous pouvons pour l instant nous contenter du sens g n ral commun ment admis un agent est consid r comme autonome s il est capable d agir seul en fonction des informations lui provenant de l environnement Un agent ne peut tre autonome que s il est capable de pro activit c est dire qu il peut avoir un comportement pilot par des buts et ainsi prendre l initiative des actions qu il ex cute Nous voulons galement que nos agents aient un comportement extraverti Nous consid rerons dans la suite que les agents interagissent avec l environnement uniquement par envoi et r ception de messages Chaque agent dispose d une bo te aux lettres dans laquelle s empilent les messages qu il n a pas encore pris en compte Nous utilisons la d finition suivante pour la propri t d extraversion D finition 2 1 Agent extraverti agent introverti Un agent est extraverti si le temps processeur qui s pare deux consultations de sa bo te aux lettres est born Il est introverti dan
240. ure pour les intentions compos e d un ensemble partiellement ordonn de plans Un interpr teur se charge de mani re cyclique de mettre jour la base de croyances et des buts en fonction des v nements ext rieurs et des informations post es la fin du cycle pr c dent s lectionner dans les KA dont les conditions d activation sont v rifi es ceux qui vont tre plac s dans la structure d intention choisir une t che de la racine de la structure d intentions et ex cuter une tape de cette t che Cela d clenche une action primitive la formation d un nouveau sous but ou de nouvelles croyances qui seront int gr es dans les bases de croyances et de buts au prochain cycle 2 2 Travaux connexes 43 Chaque intention de la structure d intentions repr sente une pile de KA invoqu s L ex cution d un KA entraine la formation de sous buts qui eux m me invoquent d autres KA ce qui forme une pile de KA la mani re d une pile d appels de proc dures des langages de programmation traditionnels Lorsque le syst me traite plusieurs taches il g re ces piles dynamiquement en ex cutant suspendant et relan ant ces proc dures la mani re d un syst me d exploitation PRS ne permet pas de prendre en compte des actions primitives qui s inscrivent dans la dur e mais il poss de une particularit int ressante puisque le niveau m ta est r ifi les KA peuvent permettre de raisonner sur d
241. urs Nous verrons dans la section 5 4 2 un exemple d utilisation de la migration dans lequel tous les agents d butent leur ex cution sur un seul processeur puis quelques uns d entre eux migrent vers un second processeur jusqu ce que la charge des deux soit comparable 44 Synth se Nous avons pos dans ce chapitre le probl me du respect de contraintes temporelles sur les calculs longs que les agents d l guent aux artifacts Nous avons propos un algorithme d ordonnancement bas sur l algorithme du simplexe Il est utilis par un artifact de coordination de l acc s aux ressources processeur nomm APRC pour r partir les ressources entre les agents et les artifacts Les agents font obligatoirement appel APRC pour d l guer une partie de leurs traitements longs sous forme de t ches de calcul dont les dur es sont d termin es par l agent L APRC permet de garantir que les d lais sur les t ches de calcul des artifacts seront respect es tout en pr servant l acc s permanent des agents au processeur Nous avons d taill le mode d emploi de l APRC Celui ci permet aux agents de r aliser des re qu tes pour de nouvelles t ches Si celles ci ne peuvent tre satisfaites 1 APRC pr serve l autonomie des agents en refusant la nouvelle t che L agent demandeur peut dans ce cas utiliser 1 APRC comme interm diaire dans la n gociation avec les autres agents pour qu ils sacrifient un part d
242. us n h siterons donc pas contraindre tr s fortement les programmeurs pour que la programmation d agents g rant plusieurs contextes simultan ment ne soit pas un casse t te et que l apparition d interblocages deadlocks soit tr s limit e Nous nous attacherons galement ce que les propri t s que nous at tribuons aux agents restent visibles au niveau de la programmation Ce sera notamment le cas de l autonomie qu il est tr s facile de perdre au niveau de l impl mentation mais qui est un des piliers du d couplage des entit s du syst me Nous consid rerons dans la suite que nos agents sont des agents logiciels dont les actions dans l environnement peuvent tre ramen es des interactions avec les autres agents par envoi de messages et des t ches de calcul Les calculs peuvent tre de toutes sortes mais nous nous pr occupons principalement de ceux r alis s par les algorithmes de I Intelligence Artificielle Nous nous int ressons plus particuli rement dans cette th se aux aspects suivants La gestion simultan e de plusieurs contextes au sein d un agent Cela concerne les contextes de dialogue avec les autres agents ainsi que les contextes d ex cution des actions planifi es de l agent Les actions que r alisent nos agents tant des calculs potentiellement longs nous nous int ressons la repr sentation de ceux ci et aux raisonnements qu il est possible de r aliser sur la r
243. us ne faisons qu introduire un nouveau type d entit s dans les syst mes multi agents Et les m thodologies de conception de syst mes multi agents d j propos es comme Gaia Wooldridge et al 2000 ou Voyelles Demazeau 1995 sont suffisamment g n rales pour prendre en compte les agents et l environnement que nous d crivons ici Nous n avons donc pas red finir une nouvelle m thodologie compl te Nous nous contenterons simplement de bien mettre en vidence les diff rences entre les agents et les artifacts pour qu il soit ais de d terminer l attribution des r les et fonctionnalit s du syst me aux agents et aux artifacts 3 5 M thodologie de mod lisation d une application avec des agents et des artifacts 75 3 5 1 Diff rences entre agent et artifact La principale caract ristique qui diff rencie les agents des artifacts est l autonomie au sens d fini plus haut Les agents sont autonomes alors que les artifacts ne le sont pas Un artifact du fait qu il ne soit pas du tout autonome dispose d un comportement pr visible de l ext rieur Il peut donc exhiber un mode d emploi qui permet d interagir avec lui et de savoir l avance comment il va r agir A l inverse un agent peut avoir un comportement impr visible On ne pourra donc pas disposer d un mode d emploi s r Lorsqu un agent interagit avec un autre agent il doit s attendre ce que son comportement r
244. us poser la question de savoir ce que sont des agents modules qui ne seraient pas autonomes comme nos boites translucides Faut il toujours les consid rer comme des agents ou y a t il un b n fice a les consid rer comme un nouveau type d entit Les remarques du paragraphe pr c dent sur le manque d autonomie ainsi que le fait que l on doive disposer d un modele pr cis des entit s qui r alisent les taches calculatoires sont des arguments suffisamment forts pour se permettre d introduire un nouveau type d entit dans les SMA Celle ci ne sera pas autonome pourra tre utilis e par les agents comme outil de calcul pour atteindre leurs buts et disposera d un mode d emploi sur lequel l agent pourra compter et raisonner 54 Chapitre 3 Des outils de calcul pour les agents 3 2 Les artifacts Il est apparu pendant l tude que les travaux du groupe de recherche aliCE bas au laboratoire DEIS de l universit de Bologne portant sur une probl matique diff rente s adaptent parfaitement a notre situation Leurs travaux portaient au d part sur la coordination entre agents Ils se sont apergus qu il y avait un gain du point de vue conceptuel et du point de vue g nie logiciel externaliser toute la m ca nique qui sert la coordination entre les agents Ils ont ainsi introduit la notion d artifact de coordi nation Omicini et al 2004 et l ont plac comme un autre type d entit de premier plan
245. ut le param tre n tant la dur e du timeout r m est la perception de m unit s de temps e est un tat d erreur dans lequel l instruction op ratoire tombe si un timeout a ex pir pendant qu elle tait en attente du lancement d une action Cela correspond une faute de l agent qui n a pas respect le mode d emploi de l artifact y est l tat d erreur dans lequel on se retrouve si un timeout expire alors qu on tait en attente d une perception Cet tat ne doit normalement jamais tre atteint car on consid re que les artifacts n ont aucune latitude par rapport leurs sp cifications ils respectent obligatoirement leur mode d emploi Comme pour les instructions pr c dentes les r gles suivantes donnent une s mantique op ration nelle l instruction timeout T m Tinj I se T n m I sin gt m T A PASS T m 1 Tr sin gt m T A EXP a T n 1 TMS a T n m I sin gt m T P PASS a T m I A sin gt m T P EXP T n a I sy a a a I T ACT a T n m D T I Jr 4 I E COMP La r gle T A PASS g re le passage du temps pendant le temps o le timeout n a pas encore expir et qu une action doit tre r alis e Quand le timeout expire la r gle T A EXP fait passer l instruction op ratoire dans l tat d erreur e L agent doit tout faire pour ne pas se retrouver en si tuation d chec dans l utilisation de l artifact Il doit donc interpr ter
246. ut en laissant l algorithme continuer son ex cution 2 1 2 2 Utilisation de code h rit Un paradigme tel que celui d agent ne peut tre facilement adopt qu la condition que l on puisse r utiliser la base de code dont on dispose dans de nouvelles applications ou dans la refonte 12 Chapitre 2 Contexte d une application avec le paradigme agent La capacit de pouvoir agentifier du code existant est un l ment essentiel l utilisation du paradigme agent dans des applications industrielles Le fait de consid rer l utilisation de code h rit n est cependant pas qu une probl matique indus trielle car nous avons vu dans le paragraphe pr c dent que la plupart du temps il n est pas envisageable de modifier l algorithme dont on dispose pour qu il ait de meilleures propri t s temporelles Il faut donc se r soudre devoir int grer dans nos syst mes des bo tes noires pour lesquelles on ne peut toucher au code soit parce qu on ne peut le faire code h rit soit parce qu on se refuse le faire algorithme complexe L architecture du syst me multi agent doit donc tre suffisamment flexible pour introduire du code non agent Elle doit galement apporter des outils pour supporter l ex cution de tous types d al gorithmes sans que leur mauvaises propri t s nuisent l int grit du syst me Le concept de r utilisabilit peut galement tre vu non pas du point de vue du programm
247. ut toujours envoyer d autres commandes I artifact au travers de la socket notamment pour inspecter ses attributs Cette solution poss de cependant l inconv nient de rendre plus difficile le codage de l artifact en particulier quand on veut encapsuler du code h rit En effet dans la pre mi re solution la gestion des signaux syst mes est enti rement la charge du syst me et ce syst me fonctionne sur n importe quel programme sans avoir apporter de modification au code Dans la se conde solution il faudra au moins recompiler le code h rit en y ajoutant la gestion des commandes de pause qui sera enti rement la charge du processus de l artifact 3 4 Le langage de mode d emploi des artifacts Nous d taillons maintenant le langage formel qui est utilis pour d crire les instructions op ratoires Nous d crivons tout d abord le formalisme base d alg bre de processus introduit dans Viroli et Ricci 2004 Ensuite nous pr sentons les extensions que nous y avons introduit nous faisons une analyse critique permettant de mettre en vidence les lacunes et nous pr sentons de ma ni re plus d taill e la mani re d exprimer le mode d emploi des artifacts de calcul 60 Chapitre 3 Des outils de calcul pour les agents 3 4 1 Les alg bres de processus Milner a initi l tude des syst mes concurrents communicants Milner 1982 Il a voulu mettre en vidence une description abstrai
248. ution les lancer les surveiller et prendre des d cisions en fonction de ses observations Un 2 1 Expos du probl me 11 agent doit par exemple pouvoir d tecter qu un traitement dure anormalement longtemps et d cider de le stopper d finitivement Il doit pouvoir continuer de fonctionner sans les donn es qu il attendait en sortie d un traitement s il d cide de le stopper en cours d ex cution Nous avons d cid d adopter dans cette tude une approche ascendante dans laquelle nous propo sons des outils g n riques assez bas niveau et ind pendants du mod le d agent utilis Notre priorit est d obtenir des agents ayant les trois propri t s d crites pr c demment autonomie extraversion et conscience du temps tout en tant capable de r aliser des calculs complexes potentiellement longs 2 1 2 Le probl me des longs calculs 2 1 2 1 Utilisation d algorithmes complexes Nous voulons faciliter l int gration de tous types d algorithmes dans les syst mes multi agents en particulier ceux issus du domaine de l Intelligence Artificielle Ces algorithmes peuvent avoir des temps d ex cution longs ainsi que de mauvaises propri t s temporelles Par mauvaises propri t s temporelles nous entendons que les algorithmes utilis s peuvent avoir des dur es d ex cution haute ment variables en fonction des donn es en entr e et que ces dur es sont difficiles pr voir Il existe des techniques pour
249. ution peut galement permettre aux agents de raisonner sur les tranches de temps qui sont allou es leurs artifacts Pour cela on peut exprimer l ordonnancement sous la forme d une instruc tion op ratoire que l on vient ins rer sous la forme d une branche parall le dans le mode d emploi de V artifact Cette solution a cependant un inconv nient majeur En effet 4 chaque ajout d une tache dans le planning du processeur les intervalles de temps dans lesquels les artifacts doivent tre lanc s peuvent tre modifi s pour l ensemble des t ches pr c demment valid es Cela implique que si un agent veut raisonner sur les intervalles de temps allou s ses artifacts il doit remettre jour ses raisonnements a chaque fois qu une nouvelle tache est allou e et qu un nouveau tissage a t effectu sur les modes d emploi de ses artifacts 4 1 6 Mode d emploi de base de APRC Nous pr sentons ici la partie du mode d emploi de 1 APRC qui permet un agent de faire une requ te pour une nouvelle t che Si la tache peut tre r alis e 1 APRC renvoie les intervalles de temps dans lesquels la tache peut s ex cuter Si la tache ne peut tre allou e la r ponse est simplement un message de refus Def_CA Management est l instruction op ratoire utilis e par les agents pour interagir avec P APRC lorsqu ils ont un travail donner un artifact de calcul L agent ex cute tout d abord l action request
250. uvoir utiliser des variables globales automate dans les transitions appel un script Les r gles de transition sont des r gles ST condition ALORS action qui permettent de d crire les automates Les conditions possibles sont arriv e d un message ch ance d un timeout et condition sur les variables de l instance d automate Pour impl menter un script on dispose de deux macros Lisp define script pour d clarer le script ses variables son tat initial et le script parent ventuel duquel h rite ce nouveau script et define script state pour d crire chaque tat de l automate Le code ex cut lors du franchissement des transitions peut tre personnalis l aide de fonctions d agent crites par le programmeur de l agent Elles jouent le r le de gestionnaires d v nements Les fonctions d agent constituent une fonctionnalit utile si l on veut se constituer une biblioth que de protocoles de com munications personnalisables Le script mon_script est un exemple de script Il d bute dans l tat start Il y envoie un autre agent par l interm diaire d une fonction d agent une t che sous traiter puis passe dans l tat wait_answer Lorsque la r ponse ok arrive le script se termine define script mon_script task initial state start script vars ma_var define script state start mon_script on entry 2 2 Travaux connexes 37 progn setf sen
251. v dans la section 3 4 3 3 un certain nombre de limitations du langage actuellement utilis pour d crire les modes d emploi des artifacts Nous aimerions tre capables de d crire des conseils d utilisation en compl ment des r gles d utilisation qu il est obligatoire de res pecter Nous aimerions galement largir la s mantique du langage pour utiliser certaines possibilit s du langage T EMS Nos agents utilisent pour l instant les artifacts de mani re inconsciente Nous aimerions qu ils soient capables d identifier le besoin d utiliser un outil de les d couvrir dynamiquement et d inter pr ter de nouveaux modes d emploi d artifacts 123 124 Chapitre 7 Perspectives 7 2 Mod le d agent Le stage de Master Recherche de Benjamin Dev ze a permis d identifier des fonctionnalit s man quantes ou am liorer dans le mod le d agent que nous utilisons actuellement Dev ze 2006 Celles ci concernent la gestion des signaux Les seuls signaux qui parviennent actuellement aux agents sont les mes sages qu ils re oivent Il serait int ressant de pouvoir g rer d autres types de signaux hautement prioritaires la fa on des interruptions syst mes ou encore donner la possibilit l agent de se programmer l envoi d un signal d attention une date donn e la gestion de l agenda Cela concerne la possibilit de pouvoir facilement programmer des actions pou
252. x fautes la gestion du cycle de vie des services Le calcul distribu a la maison Les ordinateurs de bureau tant largement sous exploit s des projets scientifiques ayant de grands besoins en calculs proposent d installer sur nos machines un programme qui va utiliser la puissance de milliers de machines pendant qu elles sont inactives pour r aliser ces calculs On peut citer dans les plus connus Seti home Folding Home D crypthon On parle de desktop GRID Comme toute application GRID les ressources de calcul sont h t rog nes mais contrairement aux autres projets de GRID ces syst mes sont ouverts et plut t cen tralis s L ouverture des clients pour lesquels on ne peut pas v rifier l identit oblige de la redon dance les calculs sont envoy s sur plusieurs clients puis leurs r sultats sont compar s pour d tecter un ventuel biais Cela permet galement de g rer la volatilit des clients La plupart de ces projets fonctionne en mode centralis et il n est pas possible que les serveurs centraux calculent eux m me l ordonnancement des t ches sur les diff rents clients Cette t che est donc galement d l gu e aux machines clientes Cela permet d utiliser de nombreux crit res dans I or donnancement comme le type de t che la puissance et la taille m moire des clients les biblioth ques de calcul scientifiques install es sur les clients le clouage des donn es sur un client ou l an

Calculs longs et partage des ressources processeur dans les

Contents

Download Pdf Manuals

Related Search

Related Contents