Sc´enario des agents voyageurs dans une gare

Télécharger le fichier pdf d’un mémoire de fin d’études

L’interaction dans les SMA

L’interaction est un processus dans lequel les agents s’engagent afin de s’assurer que, prises ensemble, leurs actions s’ex´ecutent d’une mani`ere coh´erente. Ferber propose la d´efinition suivante de l’interaction :
D´efinition Interaction [Ferber, 1995]
Une interaction est une mise en relation dynamique de deux ou plusieurs agents par le biais d’un ensemble d’actions r´eciproques.
Les agents interagissent a` travers un ensemble d’´ev´enements pendant lesquels les agents sont en relation les uns avec les autres soit directement soit par le biais de l’environnement. La notion d’interaction suppose :
– La pr´esence d’agents capables d’agir et/ou de communiquer
– Des situations susceptibles de servir de point de rencontre entre agents : collaboration, d´eplacement de v´ehicules amenant a` une collision, utilisation de ressources limit´ees, r´egu-lation de la coh´esion d’un groupe.
– Des el´ements dynamiques permettant des relations locales et temporaires entre agents : communication, choc, champ attractif ou r´epulsif, etc.
– Un certain jeu dans les relations entre les agents leur permettant a` la fois d’ˆetre en relation, mais aussi de pouvoir se s´eparer de cette relation, c’est-a-dire de disposer d’une certaine autonomie.

L’interaction directe

La communication est un outil permettant `a des agents d’interagir directement. L’interaction est directe dans le cas o`u un agent envoie intentionnellement un message vers un autre agent. Ce type d’interaction est appel´ communication « point `a point » ou dyadique. La diﬀusion ou broadcast est aussi une communication directe et consiste en l’envoi d’un message par un agent vers tous les autres agents du syst`eme. Le multicast consiste en l’envoi d’un message par un agent vers un sous-ensemble des agents du syst`eme.
L’un des champs de recherche en SMA est le d´eveloppement de langages de communication agent. Les langages de communication les plus connus sont KQML et le langage FIPA-ACL.

Mod`eles et m´ecanismes de coordination multi-agent

Un langage de communication agent fournit un ensemble d’actes de communication que les agents peuvent utiliser. Le but de ces actes est d’acheminer des informations sur l’´etat mental de l’agent avec l’objectif d’aﬀecter l’´etat mental du partenaire. Les actions de communication des langages de communication agent sont constitu´es d’un ensemble de couches distinctes. Par exemple, KQML est compos´e de trois couches. La premi`ere concerne le contenu informationnel de l’action de communication. Le contenu est exprim´ dans un langage commun´ement agr´e´e, e.g. logique propositionnelle, du premier ordre, etc. La seconde couche exprime une attitude particuli`ere envers le contenu sous forme d’un « acte de langage ». Par exemple, l’acte tell exprime que le contenu est tenu pour valide, untell exprime que le contenu est tenu pour non valide ou ask afin de demander l’avis du partenaire concernant le contenu. Enfin, la troisi`eme couche traite du m´ecanisme de communication, impliquant des aspects tels que le canal sur lequel la communication est ´etablie ainsi que sa direction (envoi ou r´eception).

L’interaction indirecte

L’interaction indirecte divise un acte d’interaction en deux parties, en intercalant un troisi`eme protagoniste qui s’en fait l’interm´ediaire. Le besoin d’avoir une troisi`eme entit´ se fait sentir dans plusieurs situations. Par exemple, dans un syst`eme ouvert, un nouvel agent ne peut connaˆıtre les autres agents, ni ses possibilit´es de communication. Ce probl`eme est connu sous le nom de « probl`eme de connexion » [Davis and Smith, 1983] ou comment « trouver les autres agents qui ont l’information dont tu as besoin »5 [Wong and Sycara, 2000]. C’est dans ce but que les agents interm´ediaires ont et´ introduits. Dans [Sycara et al., 1997], les auteurs d´efinissent un agent interm´ediaire comme une entit´ qui n’est ni demandeur ni fournisseur d’un service mais qui participe a` l’interaction entre un demandeur et un fournisseur. Le demandeur a des pr´ef´erences et le fournisseur a des capacit´es, et l’agent interm´ediaire se charge de l’appariement entre les pr´ef´erences de l’un et les capacit´es de l’autre.
L’interaction indirecte englobe ´egalement l’utilisation « tableau noir » [Hayes-Roth, 1985] et l’utilisation de l’environnement (voir e.g. [Balbo, 2000b; Weyns, 2006]). La « stigmergie » permet aux agents de laisser des traces dans l’environnement qui peuvent peut ˆetre utilis´es par les autres agents afin de guider leurs actions. L’interaction indirecte englobe aussi l’´ecoute flottante et l’attention mutuelle (mutual awareness) [Ricci et al., 2006; Saunier et al., 2006; Zargayouna et al., 2006a]. Dans ces travaux, de nouveaux modes d’interaction indirecte sont envisag´es qui permettent a` des agents, qui ne sont pas protagonistes de la communication, de participer, en recevant certains messages qui ne leur sont pas destin´es.
Etant donn´e des agents en interaction, les mod`eles et m´ecanismes de coordination permettent un SMA d’avoir un comportement coh´erent, i.e. o`u les interactions ne m`enent pas a` des situations non d´esir´ees.

Mod`eles et m´ecanismes de coordination multi-agent

Selon [Nwana, 1994; Jennings, 1996], il y a diﬀ´erentes raisons pour lesquelles des agents ont besoin de se coordonner :
– Empˆecher un comportement chaotique du syst`eme. Par d´efinition, aucun agent n’a de vue globale de tout le syst`eme. Dans cette situation, il est assez simple de tomber dans des configurations chaotiques, o`u le comportement du syst`eme en tant que tout n’est pas pr´evisible.
– Satisfaire a` des contraintes globales. Ces contraintes existent tr`es souvent, et un groupe d’agents est consid´er´ comme ayant r´eussi sa tˆache s’il ne les viole pas. Un budget ou une date butoir a` ne pas d´epasser sont autant de contraintes globales a` satisfaire par un syst`eme multi-agent, et pour y parvenir, les agents doivent interagir.
– Atteindre un objectif global, que chaque agent isol´e ne peut atteindre tout seul. Diﬀ´erents agents peuvent avoir des expertises et/ou sources d’information diﬀ´erentes, la mutualisa-tion de ces expertises et sources d’information est n´ecessaire afin de parvenir a` l’objectif global.
– Respecter les d´ependances entre les actions individuelles des agents.
– Am´eliorer l’eﬃcacit´ du syst`eme. Quand des agents d´ecouvrent des informations que les autres peuvent utiliser pour accomplir leurs tˆaches, les partager fait gagner du temps a` tous, acc´el´erant la r´esolution du probl`eme trait´e.
Nous pr´esentons dans ce qui suit les mod`eles et m´ecanismes de coordination dans un SMA.

Mod`eles de coordination

Mod`eles orient´es-tˆaches
Dans les mod`eles de coordination orient´ee-tˆaches, on pr´esuppose la pr´esence d’un but global partag´e par tous les agents. Ainsi, tous les agents ont pour tˆache de satisfaire l’objectif global du probl`eme. Un agent gestionnaire alloue des sous-tˆaches de la tˆache correspondant a` l’objectif global aux autres agents. Les agents dans ce cas sont dans une situation de coop´eration, puisque le but est d’optimiser l’eﬃcacit´ du groupe d’agents. Ces mod`eles sont applicables dans les cas de r´esolution distribu´ee de probl`emes (Distributed Problem Solving).
Mod`eles orient´es-agent
Dans les mod`eles de coordination orient´ee-agents les agents sont autonomes ou semi-autonomes, et ne partagent donc pas forc´ement un objectif global souhait´e. Dans cette configuration, chaque agent cherche a` optimiser ses propres objectifs. La coordination est n´ecessaire pour qu’un agent ne pouvant satisfaire une tˆache par ses propres moyens puisse augmenter son gain en accomplis-sant cette tˆache avec d’autres agents.

M´ecanismes de coordination multi-agents

Les mod`eles de coordination orient´ee-agent se focalisent sur le comportement des agents afin d’aboutir a` un syst`eme coordonn´e. Plusieurs approches existent pour la coordination des agents dans un SMA. Dans [El Fallah-Seghrouchni, 2001], Fallah-Seghrouchni les classe dans six cat´egories :
– R´esolution distribu´ee de probl`emes
– Structuration organisationnelle
– Protocoles
– N´egociation
– Formation de coalitions
– Planification multi-agent
R´esolution distribu´ee de probl`emes
Dans la r´esolution distribu´ee de probl`emes, les agents sont coop´eratifs et essaient d’aboutir collectivement a` une solution au probl`eme global. Notre probl`eme du transport a` la demande se situe dans cette cat´egorie. Lesser [Lesser and Corkill, 1988] a propos´e le mod`ele FA/C (Functio-nally Accurate Model) (mod`ele fonctionnellement exact) o`u les activit´es des agents sont interd´-pendantes, ces derniers ´echangeant des informations de haut niveau (niveau m´eta) tels que leurs choix, buts, etc. Le niveau m´eta est d´efini ici d’une mani`ere statique. Durfee et Lesser [Durfee and Montgomery, 1991] ont propos´e le mod`ele PGP (Partial Global Planning) (planification globale partielle) o`u le niveau m´eta est dynamique. Les agents coordonnent leurs plans, en ´echangeant les informations pertinentes a` leur ex´ecution. Trois niveaux de repr´esentation de plans sont g´er´es par un agent. Le plan local d´efinissant les actions de l’agent, le plan nodal est une abstraction du plan local destin´ee a` ˆetre communiqu´ee avec les autres agents et le plan global partiel contenant les buts des autres agents susceptibles d’interagir avec l’agent propri´etaire du plan.
Decker [Decker and Lesser, 1992] a propos´e une g´en´eralisation de ce mod`ele appel´ee GPGP (Generalized Global Partial Planing) o`u la coordination doit respecter des contraintes d’ex´ecution temps r´eel. Dans GPGP, les buts sont organis´es en hi´erarchie et incluent des informations telles que l’ordre des buts, leurs dur´ees, leurs priorit´es etc. GPGP oﬀre l’avantage de permettre aux agents de pr´edire voire d’anticiper les comportements des autres agents [El Fallah-Seghrouchni, 2001].
Structuration organisationnelle
C’est le sc´enario le plus simple car il exploite une cat´egorisation pr´eexistante. Cette cat´egorie exploite le fait que, lorsqu’elles existent, les structures organisationnelles d´efinissent (implicite-ment) les responsabilit´es, les capacit´es, la connectivit´ et les flux de contrˆole de chaque agent, selon le rˆole qu’il joue dans le syst`eme. L’organisation y est vue comme une relation a` long terme, pr´ed´efinie, entre les agents [Durfee et al., 1987]. Trois dimensions permettent de d´efinir une typologie des structures organisationnelles [El Fallah-Seghrouchni, 2001] :
– fonctionnelle : consiste `a organiser les agents selon leurs rˆoles ou leurs fonctions au sein du syst`eme, en prenant en compte leurs capacit´es et la nature des tˆaches qui leur incombent ;
– spatiale : consiste `a aﬀecter des agents `a des r´egions bien d´elimit´ees de l’environnement dans lequel ils ´evoluent ;
– temporelle : consiste `a des organisations dynamiques, c’est `a dire qui ´evoluent dans le temps, dans les cas o`u les agents ´evoluent, apprennent ou acqui`erent des connaissances nouvelles, influen¸cant ainsi la structure de l’organisation.
Dans [Durfee et al., 1987], l’organisation est hi´erarchique (cas le plus trait´e) et dans [Ferber et al., 2000], chaque agent joue un rˆole dans un groupe (mod`ele AGR – Agent, Groupe, Rˆole). Dans ce dernier cas, la communication est un multicast qui d´epend des groupes et des rˆoles des agents `a contacter. Dans le premier cas, celui de la structuration hi´erarchique, l’impl´e-mentation est eﬀectu´ee de deux mani`eres :
– Configuration maˆıtre-esclave. L’agent maˆıtre planifie et distribue des fragments de plans aux esclaves. Les esclaves peuvent – ou pas – communiquer entre eux mais doivent `a la fin de leur ex´ecution renvoyer leurs r´esultats a` l’agent maˆıtre,
– Tableau noir. Cette impl´ementation exploite l’architecture en tableau noir [Hayes-Roth, 1985]. Les sources de connaissances sont remplac´es par des agents qui ´ecrivent et lisent depuis le tableau noir. L’agent scheduler ordonnance les lectures/´ecritures.Ce sch´ema est utilis´e par des syst`emes tels que DFI6 [Werkman, 1990] et SMAK7 [Kearney et al., 1994].
Protocoles
Le principe de la coordination par protocoles est de d´efinir un ordonnancement de messages echang´es, qui doit ˆetre respect´ par les agents participants. Une technique d´esormais classique pour l’allocation de tˆaches et des ressources a` un ensemble d’agents est le Contract Net Protocol (CNP) [Smith, 1980], que les auteurs dans [Aknine et al., 2004a] ont ´etendu au cas o`u les agents sont impliqu´es dans plusieurs n´egociations. Dans cette approche, un agent peut assumer un des deux rˆoles suivants :
– Un manager qui transforme un probl`eme en sous-probl`emes et cherche des « sous-traitants » pour les r´esoudre, il assume ´egalement le pilotage du processus de r´esolution du probl`eme initial,
– Un sous-traitant qui accomplit une sous-tˆache. Il peut `a son tour devenir un manager pour son sous-probl`eme et chercher des sous-traitants pour en accomplir les sous-tˆaches.
Afin de localiser les sous-traitants, les managers, proc`edent comme suit :
– Le manager annonce la tˆache,
– Les sous-traitants ´evaluent la tˆache par rapport `a leurs capacit´es et engagements,
– Les sous-traitants proposent une oﬀre au manager,
– Le manager ´evalue les oﬀres re¸cues, choisit un sous-traitant et lui alloue le contrat,
– Enfin, le manager suit l’ex´ecution et attend le r´esultat du contrat.
Bien que tr`es simple, le CNP oﬀre plusieurs avantages. D’une part, il convient aux syst`emes ouverts puisque les agents peuvent ˆetre introduits et extraits dynamiquement du syst`eme. Par cons´equent, il oﬀre une forte tol´erance aux pannes. D’autre part, il oﬀre un m´ecanisme naturel d’´equilibrage de charges, puisqu’un agent d´ej`a occup´e ne proposera pas d’oﬀres.
Cependant, le m´ecanisme de coordination par les contrats n’est applicable que dans un nombre restreint d’applications. Il peut ˆetre utilis´e lorsque [Huhns and Singh, 1994] :
– Le probl`eme a une structure hi´erarchique bien d´efinie,
– Le probl`eme peut ˆetre d´ecompos´ en des sous-probl`emes de grande granularit´e,
– Il existe un couplage minimal entre sous-tˆaches.
Fond´ee sur un sch´ema de communication par diﬀusion, la coordination par contrats est fortement gourmande en bande passante, et est donc irr´ealiste pour nombre d’applications r´eelles.
N´egociation
Bussman et Miller [Bussmann and Muller,¨ 1993] d´efinissent la n´egociation comme « le pro-cessus de communication d’un groupe d’agents afin d’atteindre un accord mutuellement accept´ sur un certain sujet » 8, elle constitue une ´etape importante dans un processus de coordina-tion [Davis and Smith, 1983]. Sycara [Sycara, 1990] met l’accent sur le fait que, afin de n´ego-cier eﬀectivement, les agents doivent raisonner sur les croyances, d´esirs et intentions des autres agents. Ainsi, diﬀ´erents travaux traitent de la repr´esentation et la maintenance des mod`eles de croyance, du raisonnement sur les croyances des autres agents et sur la mani`ere d’influencer ces intentions et ces croyances. Ainsi, toutes sortes de techniques d’Intelligence Artificielle ont et´e utilis´ees telles que le raisonnement a` partir de cas, la r´evision de croyances, le raisonnement a` partir de mod`eles, etc. [Nwana et al., 1996]. Dans les approches fond´ees sur la n´egociation, les agents poss`edent une strat´egie de prise de d´ecision, leur objectif est de maximiser leur « fonction d’utilit´e locale ». Parmi les travaux les plus significatifs dans ce domaine figurent les mod`eles de n´egociation inspir´es de la th´eorie des jeux et de la th´eorie d’aide a` la d´ecision.
Les approches fond´ees sur la th´eorie d’aide a` la d´ecision se fondent essentiellement sur des mo-d`eles de d´ecision multicrit`eres [El Fallah-Seghrouchni et al., 2000; Moraitis and Tsouki`as, 1996; Moraitis and Tsouki`as, 1999]. Par exemple, [Moraitis and Tsouki`as, 1999] proposent une repr´-sentation des plans des agents fond´ee sur un graphe multicrit`ere. Dans les approches fond´ees sur la th´eorie des jeux (e.g. [Beaufils et al., 1996]), l’objectif est de trouver une solution « consensus » acceptable par tous les participants au jeu. La solution trouv´ee doit satisfaire des crit`eres tels que le crit`ere d’eﬃcacit´ Pareto. Une solution est dite « Pareto optimale » si elle n’est domin´ee par aucune autre solution, i.e. aucune autre solution possible ne donne plus a` un agent sans en donner moins a` un autre. Les mod`eles issus de la th´eorie des jeux appliqu´es aux SMA mod´elisent la n´egociation comme un jeu o`u les int´erˆets des joueurs (agents) est repr´esent´ par une fonction d’utilit´e. Sous les conditions th´eoriques fix´ees par la th´eorie des jeux, il est possible de garantir la convergence d’une n´egociation vers une situation o`u aucune fonction d’utilit´e n’est aﬀaiblie. N´eanmoins, ces conditions th´eoriques restreignent grandement le cadre applicatif des mod`eles issus de la th´eorie des jeux, soit car trop complexes pour ˆetre appliqu´es, soit car les conditions r´eelles ne satisfont pas aux conditions th´eoriques du mod`ele (telles que la rationalit´e des agents ou la sym´etrie de l’information, e.g. ´equilibre de Nash [Nash, 1950]).
Formation de coalitions
Dans [El Fallah-Seghrouchni, 2001], El Fallah d´efinit une coalition comme une organisation a` court terme fond´ee sur des engagements sp´ecifiques et contextuels, qui permet aux agents de coexister tout en profitant de leurs comp´etences respectives. Les recherches sur la formation de coalitions essaient d’optimiser la formation de coalition (maximisation de profit total g´en´erale-ment), qui n´ecessite des algorithmes de grande complexit´. Des hypoth`eses sont donc ´emises afin de trouver des solutions en des temps raisonnables. Les hypoth`eses formul´ees sont notamment l’altruisme des agents, leur coop´eration, avoir la mˆeme rationalit´e pour tous les agents, avoir la mˆeme strat´egie [Shehory and Kraus, 1996] ou une strat´egie impos´ee [Zlotkin and Rosenschein, 1994], l’utilisation d’int´egrations incr´ementales des agents a` une coalition (ne prenant pas en compte les ´eventuels futurs participants) [Ketchpel, 1994] ou la contrainte d’appartenir a` une seule coalition.
[Vauvert and El Fallah-Seghrouchni, 2000a] n’impose pas l’application d’une mˆeme strat´egie par tous les agents, ni le partage des mod`eles de pr´ef´erence ou de crit`eres a` optimiser. Chaque agent dispose de sa propre rationalit´e ´economique individuelle, ses crit`eres ne sont pas connus par les autres et seules ses pr´ef´erences sont communiqu´ees. Il peut changer de strat´egie, changer ses crit`eres, leurs pond´eration ou ses pr´ef´erences. L’algorithme propos´e garantie la convergence vers un consensus grˆace a` l’introduction du concept d’alliances : coalitions minimales regroupant deux agents ayant les pr´ef´erences les plus proches (par rapport a` une distance entre pr´ef´erences).
Dans [Aknine et al., 2004b], les auteurs proposent un algorithme qui permet de former des coalitions `a partir des pr´ef´erences des agents. Dans [Caillou et al., ], ils proposent un algo-rithme qui permet de restructurer des coalitions dans les syst`emes ouverts, sans avoir a relancer l’algorithme lors de l’apparition de nouveaux agents.

Les langages de coordination

Dans le domaine des langages de coordination, il est maintenant admis qu’une application parall`ele est principalement divis´ee en deux parties : le calcul et la coordination [Gelernter and Carriero, 1992]. Un langage de coordination est orthogonal a` un langage de calcul, c’est a` dire qu’un langage de coordination ´etend un langage de calcul avec des fonctionnalit´es facilitant l’impl´ementation d’applications distribu´ees. On dit ´egalement qu’un langage de coordination forme le pendant linguistique d’un mod`ele de coordination [Gelernter and Carriero, 1992], c’est a` dire qu’un langage de coordination doit oﬀrir des constructeurs linguistiques, soit sous forme d’appels de librairies, soit sous forme d’extensions (des primitives), afin de mat´erialiser le mod`ele de coordination. Dans ces domaines, la d´efinition la plus largement accept´ee de la notion de coordination est la suivante.
D´efinition Coordination [Gelernter and Carriero, 1992]
La coordination est le processus de construire des programmes en collant ensemble des composantes actives9.
Un mod`ele de coordination peut ˆetre vu comme un triplet hE, M, Li o`u E repr´esente les enti-t´es coordonn´ees, M le m´edia utilis´e afin de les coordonner, et L le cadre s´emantique auquel le mod`ele adh`ere [Wegner, 1996]. Deux principales cat´egories de mod`eles de coordination ont et´ identifi´ees : les mod`eles de coordination orient´ee-contrˆole et les mod`eles de coordination orient´ee-donn´ees [Papadopoulos and Arbab, 1998]. Dans la suite de ce chapitre, nous donnons une br`eve pr´esentation des mod`eles de coordination orient´ee-contrˆole, puis d´etaillons les mod`eles de co-ordination orient´ee-donn´ees. Dans cette famille des langages de coordination, les termes agents et processus sont utilis´es d’une mani`ere interchangeable. Le lecteur int´eress´ peut trouver une ´etude qui couvre une grande partie de ces deux types de mod`eles dans [Papadopoulos and Arbab, 1998].

La coordination orient´ee-contrˆole

Dans les mod`eles de coordination orient´ee-contrˆole, un syst`eme coordonn´e ´evolue en obser-vant des changements dans les ´etats des processus, et ´eventuellement en diﬀusant des ev´ene-ments, les processus sont vus comme des boˆıtes noires. Les processus communiquent avec leur environnement avec des interfaces bien d´efinies, g´en´eralement appel´ees des « ports d’entr´ee » et « ports de sortie ». Les relations producteur-consommateur sont form´ees par des canaux entre les ports de sortie des producteurs et les ports d’entr´ee des consommateurs. Ces canaux sont point-a`-point, ou parfois ils forment une relation un-a`-plusieurs, dans le cadre d’une diﬀusion restreinte. Outre les ports, les processus g´en´erent des ev´enements qu’ils envoient a` leur envi-ronnement, avec pour objectif d’informer les processus a` propos de leur ´etat actuel, ou d’un changement de leur ´etat. La figure 1.1 illustre ces concepts, elle pr´esente une configuration avec un producteur et deux consommateurs. Le producteur (processus1) a un port d’entr´ee et deux ports de sortie. Le premier consommateur (processus2) a un port d’entr´ee et un port de sortie, tandis que le deuxi`eme consommateur (processus3) a deux ports d’entr´ee et un port de sortie. Les canaux (repr´esent´es par des fl`eches) connectent les ports de sortie du producteur aux ports d’entr´ee des consommateurs avec ´eventuellement plusieurs canaux sortant ou entrant du mˆeme port. De plus, processus1 et processus3 d´eclenchent et/ou observent des ev´enements (Ev1, Ev2 et Ev3). La plupart des mod`eles de coordination instancient ce mod`ele, et se diﬀ´erencient par la
9 Coordination is the process of building programs by gluing together active pieces. mani`ere de le mettre en oeuvre. Un processus ex´ecute g´en´eralement un programme s´equentiel, envoie des donn´ees sur son port de sortie et en re¸coit sur ses ports d’entr´ees. Cette famille de langages introduit une entit´ appel´ee coordinateur, qui g`ere dynamiquement les canaux entre les producteurs et consommateurs en ex´ecution. Ainsi, le coordinateur orchestre les actions du syst`eme en r´eagissant a` des ev´enements d´eclench´es par les entit´es qui sont sous son contrˆole. Des ev´enements typiques sont des op´erations d’entr´ee-sortie, ou l’atteinte d’un ´etat particulier par l’entit´. Les mod`eles les plus connus dans cette cat´egorie sont Manifold [Arbab et al., 1993], ConCoord [Holzbacher, 1996] et RAPIDE [Shaw et al., 1995].

La coordination orient´ee-donn´ees

Linda [Gelernter, 1985; Carriero et al., 1986], le premier mod`ele qui a et´ propos´e illustre le principe g´en´eral des mod`eles de coordination orient´ee-donn´ees. Linda est un mod`ele et un langage de coordination, dans lequel des processus parall`eles communiquent en ´echangeant des tuples via une abstraction d’une m´emoire partag´ee appel´ee tuplespace. Un tuplespace est un espace partag´e compos´e d’un multi-ensemble de tuples (la duplication de tuples est permise). Chaque tuple est une s´equence d’une ou de plusieurs valeurs typ´ees, et n’a de sens que pour le producteur et le consommateur du tuple. La communication dans Linda est dite communication g´en´erative : un processus g´en`ere un tuple et la dur´ee de vie de celui-ci devient ind´ependante de celle du processus l’ayant cr´e´. L’acc`es aux donn´ees du tuplespace est associatif i.e. par contenu. Comme le montre la figure 1.2, relative `a l’une des premi`ere impl´ementations de Linda [Carriero et al., 1986], la m´emoire partag´ee consiste en une clique des m´emoires locales des processus, mais elle est consid´er´ee comme une seule m´emoire pour un processus donn´e. Linda est une alternative aux deux m´ethodes traditionnelles de programmation parall`ele, viz. le passage de messages entre processus et l’usage d’une m´emoire partag´ee.
La diﬀ´erence de Linda avec l’´echange dyadique de messages est double. D’une part, lors d’un ´echange de message point `a point, les processus doivent ˆetre synchronis´es pour que l’´emission d’un message par le premier processus corresponde `a sa r´eception par le second. D’autre part, l’´emetteur doit connaˆıtre l’emplacement physique du processus r´ecepteur. Alors qu’avec un tu-plespace, la communication est d´ecoupl´ee dans le temps et dans l’espace. Le d´ecouplage dans le temps oﬀre la possibilit´e aux processus de communiquer `a travers le temps i.e., leurs temps d’ex´ecution n’ont pas `a se chevaucher (les processus n’ont pas `a ˆetre synchronis´es par un m´eca-nisme de rendez-vous) afin d’´etablir une communication. Le d´ecouplage dans l’espace est relatif `a la g´en´eration et au retrait anonymes de tuples i.e. les processus n’ont pas `a connaˆıtre l’empla-cement des autres processus pour communiquer, la communication a donc lieu ind´ependamment de l’emplacement des processus impliqu´es.
La diﬀ´erence entre l’usage des tuplespaces et l’utilisation d’une m´emoire partag´ee est que la premi`ere est une m´emoire associative i.e. l’acc`es `a la m´emoire se fait par contenu et non par adresse. Dans Linda, la r´ecup´eration d’un tuple n’est pas nominative mais r´esulte d’un appariement avec un template, et le premier tuple satisfaisant le template est retourn´e, d’une mani`ere non d´eterministe.
Le langage pionnier : Linda
Comme nous l’avons expos´ plus haut, Linda est un mod`ele de coordination qui propose de relaxer la synchronisation entre deux processus, pour la remplacer par deux synchronisations entre chaque processus et le tuplespace. Le langage associ´e a` ce mod`ele est compos´e d’un ensemble minimal de primitives, ce qui ne constitue pas un langage stricto sensu, mais une extension d’un langage de programmation. Aucune s´emantique op´erationnelle n’est associ´ee au langage Linda original. Cependant, quelques langages qui ´etendent Linda (e.g. Klaim [De Nicola et al., 1998]) en proposent une. La pr´esentation de la s´emantique de ces langages de coordination fait l’objet du chapitre 2.
Les primitives du langage
Le langage Linda oﬀre trois primitives aux processus afin d’interagir avec le tuplespace.
– out(t) permet a` un processus d’ins´erer le tuple t dans le tuplespace,
– in(template) permet de retirer le premier tuple satisfaisant le template. C’est une op´eration bloquante i.e. si aucun tuple ne satisfait le template, le processus ayant invoqu´e le processus appelant est suspendu jusqu’`a ce qu’un tuple appropri´e est cr´e´ par un autre processus,
– rd(template) se comporte comme in, `a la diﬀ´erence que rd lit une copie du premier tuple satisfaisant le template, mais ne le retire pas. C’est une op´eration bloquante ´egalement.
Un template est un tuple compos´e partiellement ou totalement de param`etres formels i.e. non instanci´es. Il repr´esente et est capable de s’apparier avec les tuples de mˆeme arit´e i.e. ayant le mˆeme nombre d’´el´ements que lui. Chaque el´ement du template est donc soit une valeur (´el´ement instanci´e), soit un type de champ (´el´ement formel ou libre). Par exemple, soit la s´equence d’instructions string s; f loat x; x ← 10.01; Dans ce contexte, avec l’instruction in(hs, xi); le template en param`etre de in sera appareill´ avec n’importe quel tuple compos´e de deux el´ements, a` condition que son premier el´ement soit de type chaˆıne de caract`eres et que son second el´ement soit un r´eel evalu´ a` 10.01.
Lorsque deux processus sont suspendus avec deux op´erations de in/rd et qu’un tuple satis-faisant leur template devient disponible, l’un des deux processus est choisi d’une mani`ere non d´eterministe pour continuer son traitement. Lorsque plusieurs tuples sont appariables avec le template d’un in/rd, seul l’un des tuples est s´electionn´.
Une primitive additionnelle est g´en´eralement impl´ement´ee, mais elle ne fait pas partie de Linda, c’est la primitive eval ; eval(t) permet d’´evaluer des expressions contenues dans le tuple t avant de l’ajouter. Elle prend en param`etre un tuple contenant une ou plusieurs expressions, une expression ´etant un traitement `a eﬀectuer sur une valeur avant de la mettre dans le tuple `a ajouter au tuplespace. Par exemple, eval(h“carre”, sqrt(4), sqrt(9)i) cr´ee d’abord deux pro-cessus concurrents qui ´evalueront les deux racines carr´es de 4 et de 9 avant de mettre le tuple h“carre”, 2, 3i dans le tuplespace pour qu’il soit disponible aux autres. Tant que ce calcul n’est pas eﬀectu´e, aucun appariement (pattern matching) ne peut ˆetre eﬀectu´ sur ce tuple.
Cependant, la primitive eval est d´esormais utilis´ee afin de lancer un nouveau processus (e.g dans Klaim [De Nicola et al., 1998] : l’op´eration eval(P ) permet d’ex´ecuter le processus P qui peut d´esormais interagir avec le tuplespace.
D’un point de vue applicatif, les primitives pr´ecit´ees sont des extensions pour des langages de programmation s´equentielle, permettant `a ces derniers de se transformer en des langages de programmation parall`ele (e.g. C-Linda, Fortran-Linda, pour n’en citer que quelques-uns).
Exemple
Nous choisissons l’exemple traditionnel du dˆıner de philosophes, pour illustrer l’utilisation des primitives de Linda (il y a N um philosophes). Chaque processus ex´ecute le code relatif a` l’algorithme 1. Le programme est instanci´e par l’algorithme 2. Comme on le voit, les instructions de calcul (manger et r´efl´echir) sont mix´ees avec les instructions de coordination (in et out). Ce fait a et´e reproch´ a` Linda par certains auteurs [Papadopoulos and Arbab, 1998], puisque le langage n’oﬀre pas de s´eparation claire entre instructions de calcul et instructions de coordination.
Afin d’´eviter une situation d’interblocage, des « tickets » sont utilis´es. Leur nombre est ´egal au nombre de philosophes pr´esents sur la table moins un, un philosophe ne pouvant manger que s’il dispose d’un ticket. Ce dernier est lib´er´ par le philosophe quand il a fini de manger.

Multiplier les tuplespaces

Avec les tuplespaces multiples, chaque tuplespace est identifi´ par un nom unique. Soit Space un ensemble d´enombrable de noms, que nous d´enotons par r, s, . . . . Une configuration d’un syst`eme devient un sous-ensemble de Conf = Space × M(Agent) × M(Data) avec comme el´ement typique s.(Ag, DS), il repr´esente un tuplespace ayant pour nom s qui contient les donn´ees de DS et les agents de Ag. Nous parcourons les noms de tuplespaces par C, D, . . . . La syntaxe de la formulation basique est ´etendue avec les nouvelles versions des primitives de coordination ayant maintenant un tuplespace associ´e. L’id´ee est que la primitive consid´er´ee est ex´ecut´ee au niveau du tuplespace sp´ecifi´e, quand le nom est omis, la primitive est ex´ecut´ee dans le tuplespace depuis lequel l’op´eration a et´ ex´ecut´ (dans Klaim [De Nicola et al., 1998], ceci est eﬀectu´ en sp´ecifiant explicitement la localit´e sp´ecifique self). µ ::= · · · | out(a)@s | in(a)@s | rd(a)@s | eval(A)@s | newloc(s) newloc(s) est une primitive qui cr´ee dynamiquement un nouveau tuplespace avec pour nom unique s. Le nom s est une variable libre, la valeur qui lui est associ´ee (le nom) est choisie du-rant l’ex´ecution de telle sorte que l’unicit´e des el´ements de Space est pr´eserv´ee. La s´emantique du nouveau langage est donn´ee dans la table 2.2. A[u/s] d´esigne l’agent A ou chaque occurrence de s est remplac´ee par u. Dans [Busi et al., 2001], les auteurs observent que la vraie nouveaut´ des tuplespaces multiples r´eside dans l’introduction de la primitive qui permet la cr´eation dyna-mique de tuplespaces (viz. newloc). Sans cette primitive, il existe un encodage du langage avec tuplespaces multiples en utilisant seulement les primitives de Linda et en rempla¸cant in(a)@s par in(ha, si). Une autre alternative utilisant des tuplespaces multiples est celle utilis´ee dans e.g. Bauhaus Linda [Carriero et al., 1995]. Dans de telles approches, les tuplespaces sont orga-nis´es hi´erarchiquement. Dynamiquement, un tuplespace peut ˆetre transf´er´ dans un autre. Les espaces fr`eres (dans la hi´erarchie) peuvent interagir en d´eposant et en retirant un tuple de leur espace p`ere commun. Les primitives du langage basique peuvent ˆetre ´etendues avec le signe ↑ signifiant que la primitive doit s’ex´ecuter, non pas dans son espace, mais dans l’espace p`ere (e.g. eval(out(a) ↑) ↑).

Exp´eriences op´erationnelles

Exp´eriences aux Etats-Unis

Aux Etats-Unis, plusieurs exp´eriences de syst`emes TAD ont et´ implant´es, et ce depuis les ann´ees 1970 en r´eaction au choc p´etrolier. Les syst`emes les plus importants sont Haddonfield dans le New Jersey, Rochester `a New York and Ann Arbor dans le Michigan. Dans aucun de ces syst`emes, la rentabilit´ ´economique n’a et´ atteinte, mais ils ont servis comme base d’exp´erimentationafin de tester des algorithmes d’ordonnancement de v´ehicules [Diana, 2002]. D’autres syst`emes ont et´ impl´ement´es depuis, les plus grands ´etant El Cajon en Californie, Danville dans l’Illinois et Davenport dans l’Iowa. Mais la rentabilit´ ´economique n’´etait toujours pas au rendez-vous, et une augmentation des tarifs empirait la situation. Par exemple, il est report´ dans [Cervero, 1997] que lorsque dans El Cajon, le tarif par voyage a doubl´e, passant de 2$ `a 4$, le d´eficit par voyage est pass´e de 3$ `a 10$. En g´en´eral, les diﬃcult´es financi`eres finissaient par avoir raison de ces syst`emes.
Dans les ann´ees 1990, le TAD a connu une renaissance grˆace au American with Disabilities Act qui obligea toutes les soci´et´es de transport a` fournir un service de transport a` la demande pour les personnes a` mobilit´e r´eduite (PMR) qui ne peuvent utiliser les syst`emes de transport existants. A la fin des ann´ees 1990, il existait des centaines de tels syst`emes. Mˆeme si ces syst`emes ont connu un vif succ`es (en termes de fr´equentation), les caract´eristiques spartio-temporelles des demandes faisaient en sorte que les possibilit´es de covoiturage ´etaient minimes, et le coˆut exorbitant, i.e. ´equivalent a` un taxi. De nouveaux cr´edits f´ed´eraux ont et´ donc allou´es a` des recherches visant a` am´eliorer la rentabilit´ de ces syst`emes, en automatisant les tˆaches eﬀectu´ees jusque l`a manuellement. Cependant, le niveau d’´equipement technologique demeurait relativement bas, mˆeme pour des tˆaches typiquement automatisables telles que le dispatching des v´ehicules.

Exp´eriences Europ´eennes

En Europe, les projets europ´eens SAMPO23 et SAMPLUS24 (1995-1999) ont stimul´e l’im-plantation de syst`emes de petites ou moyennes tailles en Belgique, en Italie, en Finlande et en Su`ede, dont la majorit´e sont toujours en service (voir [Mageean and Nelson, 2003] pour une ´evaluation des syst`emes TAD en Europe). En suisse, le service Car Postal oﬀre ses services sur tout le territoire national. Le syst`eme allemand Ruf-Bus a et´ impl´ement´ dans les ann´ees 1970 et a connu diﬀ´erentes remises `a niveau et est toujours en service. Il peut passer d’un service avec des itin´eraires fixes pour devenir un syst`eme TAD pendant le week-end. Les types de v´ehicules utilis´es varient selon les circonstances.
L’exp´erience britannique rejoint les exp´eriences europ´eennes en terme d’historique, de d´efis et de barri`eres au d´eveloppement. Une ´etude sp´ecifique `a cette exp´erience a et´ conduite [Enoch et al., 2004], dont le but ´etait de regarder le potentiel pour le TAD comme syst`eme alternatif pour les transports en commun, en termes de march´e ou d’espace de demande, du point de vue du service public et des op´erateurs commerciaux. L’´etude vise `a d´eterminer comment le TAD pourrait ˆetre d´evelopp´ pour servir les voyageurs qui ne sont pas bien servis par les transports en communs (TC) et explore les raisons pour lesquelles le TAD n’ont pas eu beaucoup d’impact jusqu’alors, et comment le gouvernement et d’autres services publics pourraient rectifier le tir [Enoch et al., 2004].
Diﬀ´erentes cat´egories de TAD ont et´ identifi´ees. La cat´egorie des TAD dits « de rechange » survient quand, au lieu de compl´eter les services de bus conventionnels, un syst`eme de TAD remplace – totalement ou partiellement – ceux-ci. La cat´egorie des TAD « d’´echange » vise a` assurer l’´echange avec les r´eseaux de transports en commun (TC). Pour cette derni`ere cat´egorie, il est appropri´e d’avoir des prix mod´er´ement au dessus des taux tarifaires des bus, mais avec des concessions pour les groupes et des rabais pour les dessertes pr´e-r´eserv´ees a` des arrˆets fixes. Une autre cat´egorie de TAD est celle a` « destination sp´ecifique » : ces services ne tendent pas a` assurer des chaˆınes de voyage (inter-connectivit´e), et donc les syst`emes de prix, les billets et/ou les horaires peuvent ˆetre ind´ependants.
En France, le rapport du Certu [Certu, 2002] dresse un bilan de 15 exp´eriences dans le do-maine des syst`emes TAD en France (plus 4 exp´eriences Europ´eennes). Les types de dessertes sont tr`es h´et´erog`enes, allant des services qui se substituent au r´eseau r´egulier de TC `a certaines heures ou dans certaines zones, jusqu’aux services d´edi´es aux Personnes `a Mobilit´e R´eduite (PMR), en passant par les services sp´ecialement organis´es pour les trajets domicile-travail. Plu-sieurs cat´egories de v´ehicules sont utilis´es, tels que les taxis avec des v´ehicules standard, les monospaces et les minibus sp´ecialement am´enag´es pour les PMR. Plusieurs mode de fonctionne-ment existent, des statiques (des lignes virtuelles avec itin´eraires, arrˆets et horaires fixes activ´ees `a la demande) aux dynamiques (des services sur mesure : porte `a porte mis au point avec chaque client, mais qui reste inchang´e pendant la p´eriode d’abonnement), mais aucun ne propose de syst`emes compl`etement flexible et automatis´e.
La client`ele utilisatrice de ces syst`emes est majoritairement constitu´ee des scolaires, repr´-sentant plus de la moiti´e des usagers des syst`emes de TAD etudi´es, mais aussi les plus de 65 ans, essentiellement de sexe f´eminin, les travailleurs (trajets domicile – travail ou aﬀaires) et les PMR. Les taux de fr´equentation observ´es des syst`emes TAD sont de 1,2 `a 1.5 personnes transport´ees par course pour les taxis dits collectifs, le taux fr´equentation des TAD par rapport aux TCs varie de 1 pour mille `a 5 pour cent selon les sites.
La majorit´e des services de TAD pratiquent la mˆeme tarification que les TCs et acceptent les mˆemes abonnements. Quelques services TAD pratiquent des tarifications de l’ordre de deux a` quatre fois le prix des tickets TC. Enfin, certains services aﬃchent des prix forfaitaires elev´es pour des destinations particuli`eres (90 euros pour un aller-retour par des navettes vers les a´e-roports parisiens, depuis Reims). Il est a` noter ici que la pratique de la mˆeme tarification que les TCs constitue un plus quant a` la compl´ementarit´ avec eux, qui est un crit`ere essentiel dans l’´evaluation de la viabilit´e d’un syst`eme TAD op´erationnel.
Les syst`emes de gestion dans les exp´eriences recens´ees par le Certu int´egr´ee se caract´erisent en trois groupes : les syst`emes propri´etaires, les syst`emes avec logiciels sp´ecifiques et les syst`emes d’exploitation simples.
Les syst`emes propri´etaires sont d´evelopp´es en interne apr`es ´etude des besoins du TAD `a mettre en place. C’est le cas de Routair `a Reims. Ce syst`eme poss`ede les grandes fonctions de logiciels dits sp´ecifiques, `a savoir : r´eservation, planification et gestion. Le syst`eme int`egre un module de calcul de prix de revient de chaque tourn´ee.
Dans les syst`emes avec logiciels sp´ecifiques, les exploitants utilisent ici des logiciels qui ont et´ d´evelopp´es sp´ecifiquement pour optimiser les transports a` la demande. Les fonctions de pla-nification, optimisation des courses, suivi de client`ele, cartographie voire localisation, facturation pour certains se rencontrent fr´equemment.
Dans le cas d’utilisation d’un syst`eme d’exploitation simple, les exploitants n’utilisent pas de logiciels d´edi´es aux TAD. C’est une simple gestion des courses avec utilisation de logiciels bureautiques de type tableur et base de donn´ees. La prise en charge de la client`ele est eﬀectu´ee via une centrale de r´eservation ou par appel t´el´ephonique. Certains sites n’utilisent pas de syst`emes de gestion int´egr´ee et travaillent seulement avec un centre d’appel qui se charge de r´epercuter la demande vers le transporteur. Il est `a remarquer que l’oﬀre sur le march´e souvent ne r´epond pas aux besoins sp´ecifiques de l’exploitant. Cette oﬀre ne lui est souvent pas visible, il ne connaˆıt donc pas l’oﬀre r´eelle disponible sur le march´e.

Bilan

Les services de TAD sont typiquement plus coˆuteux par passager que les bus conventionnels. Cependant, ´etant plus flexibles, ils peuvent assurer eﬃcacement un service « pilote » de bus dans une zone jusqu’`a ce que le niveau de demande sur certaines routes ou dans des arrˆets particuliers peut ˆetre totalement assur´e avec des ressources allou´ees a` un service a` route fixe [Enoch et al., 2004]. Ce passage entre TAD et TC est tr`es important, et il est bidirectionnel dans le sens o`u un syst`eme TAD ne cherche pas seulement a` combler des manques a` gagner (pour raisonner en termes ´economiques seulement), mais aussi en traquant le gaspillage sur les lignes fixes (de TC a` TAD).
La majorit´e des services TAD ont et´ mis en place pour des consid´erations sociales et se sont donc concentr´es sur des usagers cibles, qui ont par d´efinition un choix de transport limit´e, et en particulier ceux qui ont un acc`es limit´e aux voitures personnelles. En revanche, nombre de services TAD ont comme cible des voyageurs de choix, dont beaucoup pourrait faire le trajet en voiture. Ce dernier groupe est particuli`erement int´eressant dans le cadre d’une politique environnementale [Enoch et al., 2004].
Dans tous les syst`emes etudi´es en Europe et aux Etats-Unis, la proportion relativement faible de l’utilisation de solutions informatiques g´en´eriques `a la probl´ematique de TAD est frappante, et le gap entre recherche et industrie demeure assez net. Dans [Enoch et al., 2006], d’autres conclusions ont et´ d´egag´ees (72 exp´eriences recens´ees). Il est conclu que les projets TAD sont souvent trop coˆuteux ou alors con¸cus sans une compr´ehension totale du march´e qu’ils vont servir. La tentation d’oﬀrir un service trop flexible et d’introduire des syst`emes technologiques coˆuteux, quand il n’y en a pas r´eellement besoin, est dangereuse. Les syst`emes TAD requi`erent ´egalement un eﬀort de marketing plus important que pour les services de bus r´eguliers, mais plus que tout, ils n´ecessitent des capacit´es importantes de travail en partenariat avec les op´erateurs en place. Ce dernier point a et´ identifi´ comme la source principale de l’´echec d’une grande partie des exp´eriences op´erationnelles de syst`emes TAD.

Formulation du probl`eme TAD

Dans [Cordeau, 2006], Cordeau et al. donnent une formulation du probl`eme du TAD, nous renvoyons le lecteur `a [Desaulniers et al., 2002] pour une formulation du VRPTW. Soit n le nombre de clients du probl`eme. Le probl`eme TAD peut ˆetre d´efini comme un graphe complet dirig´e G = (N, A) o`u N = P ∪ D ∪ {0, 2n + 1}. P = {1, . . . , n} et D = {n + 1, . . . , 2n}. Les sous-ensembles de P et D contiennent respectivement les noeuds de d´epart et d’arriv´ee, tandis que les noeuds 0 et 2n + 1 repr´esentent le d´epˆot. Avec chaque client sont associ´es le noeud de d´epart i et le noeud d’arriv´ee n + i. Soit K l’ensemble des v´ehicules. Chaque v´ehicule k ∈ K a une capacit´e Qk et la dur´ee totale de sa tourn´ee ne peut d´epasser Tk. Avec chaque noeud i ∈ N est associ´ee une quantit´e qi et une dur´ee de service positive si telles que q0 = q2n+1 = 0, qi = −qn+i (i = 1, . . . , n) et s0 = s2n+1 = 0. Une fenˆetre de temps [ei, li] est ´egalement associ´ee avec les noeuds i ∈ N o`u ei et li repr´esentent respectivement le temps au plus tˆot et au plus tard auquel le service doit commencer au niveau du noeud i. Avec chaque arc (i, j) ∈ A sont associ´es un coˆut cij et un temps de parcours tij . Enfin, L est le temps de parcours maximal du client.
Pour chaque arc (i, j) ∈ A et chaque v´ehicule k ∈ K, soit xkij = 1 si le v´ehicule k se d´eplace du le noeud i au noeud j directement, et 0 sinon. Pour chaque noeud i ∈ N et chaque v´ehicule k ∈ K, soit Bki le temps auquel le v´ehicule k commence son service au niveau du noeud i, et Qki la charge du v´ehicule k apr`es avoir termin´ son service au niveau du noeud i. Finalement, pour chaque client i, soit Lki le temps pass´e par le client i `a bord du v´ehicule k. La fonction objectif minimise le coˆut total et est d´efinie ainsi : min X X X (3.1).

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction g´en´erale
I ´Etat de l’art
Chapitre 1 La coordination et les Syst`emes Multi-Agents
1.1 Introduction
1.2 Les Syst`emes Multi-Agents
1.3 L’interaction dans les SMA
1.3.1 L’interaction directe
1.3.2 L’interaction indirecte
1.4 Mod`eles et m´ecanismes de coordination multi-agent
1.4.1 Mod`eles de coordination
1.4.2 M´ecanismes de coordination multi-agents
1.5 Les langages de coordination
1.5.1 La coordination orient´ee-contrˆole
1.5.2 La coordination orient´ee-donn´ees
1.6 Conclusion
Chapitre 2 Alg`ebres de processus pour la coordination
2.1 Introduction
2.2 Introduction aux alg`ebres de processus
2.3 Une alg`ebre de processus pour Linda
2.4 Extension des primitives du langage
2.5 Multiplier les tuplespaces
2.6 Tuplespaces r´eactifs
2.7 Introduction du temps
2.8 Principaux r´esultats
2.9 Conclusion
Chapitre 3 Le probl`eme du transport `a la demande
3.1 Introduction
3.2 Exp´eriences op´erationnelles
3.2.1 Exp´eriences aux ´Etats-Unis
3.2.2 Exp´eriences Europ´eennes
3.2.3 Bilan .
3.3 Formulation du probl`eme TAD
3.4 Approches exactes et complexit´e
3.5 Approches centralis´ees
3.5.1 Approches statiques
3.5.2 Approches dynamiques
3.6 Approches distribu´ees
3.6.1 Configuration maˆıtre-esclave
3.6.2 Segmentation a priori
3.6.3 Protocoles
3.6.4 Formation de coalitions
3.7 Conclusion
II Contributions
Chapitre 4 Mod`ele de coordination Acios
4.1 Introduction
4.2 Motivations
4.3 Sc´enario des agents voyageurs dans une gare
4.4 Mod`ele basique
4.4.1 Structure de donn´ees
4.4.2 Expressions et appariement
4.4.3 Primitives du langage
4.5 Prise en compte du contexte
4.5.1 Motivation
4.5.2 Syntaxe
4.6 S´ecurit´e
4.6.1 Ajouts frauduleux
4.6.2 Restrictions d’acc`es
4.7 Interaction avec un syst`eme externe
4.8 Synth`ese
4.9 Discussion
4.9.1 Structure de donn´ees et appariement
4.9.2 Interaction contextuelle
4.9.3 S´ecurit´e
4.10 Conclusion
Chapitre 5 Langage de coordination Lacios
5.1 Introduction
5.2 Comportements des agents
5.2.1 Op´erateurs de composition de processus
5.2.2 SMA coordonn´e
5.3 S´emantique du langage
5.3.1 ´Evaluation des expressions
5.3.2 S´emantique op´erationnelle
5.4 Impl´ementation du langage
5.4.1 Description g´en´erale
5.4.2 Structure de donn´ees
5.4.3 Op´erateurs
5.4.4 Ouverture
5.4.5 Appariement et respect de la s´emantique
5.5 Complexit´e de l’appariement
5.5.1 Premi`ere solution : cr´eation d’index
5.5.2 Deuxi`eme solution : d´efinition d’un ensemble statique de propri´et´es
5.5.3 Troisi`eme solution : d´efinition d’un ensemble statique de cat´egories
5.6 Conclusion
Chapitre 6 Le syst`eme Lacios-TAD
6.1 Introduction
6.2 Motivation
6.3 Description du syst`eme
6.3.1 Param`etres
6.3.2 Fonctionnement g´en´eral
6.3.3 Les contraintes
6.3.4 Comportement des agents
6.3.5 Adaptation au TAD
6.3.6 Suivi d’ex´ecution
6.3.7 Calcul du prix d’insertion
6.4 Mise en oeuvre avec Lacios
6.4.1 Gestion du temps
6.4.2 Syst`eme coordonn´e
6.4.3 Comportement des agents
6.4.4 Adaptation au TAD
6.5 Outil et exp´erimentation
6.5.1 Outil .
6.5.2 Exp´erimentation
6.6 Conclusion
Annexe A Le langage Java-Lacios
A.1 Mode d’utilisation
A.2 Syntaxe .
A.3 Interface graphique
Annexe B Calcul des champs de perception dans le cas euclidien
B.1 Illustration du probl`eme
B.2 Calcul de l’´equation du plan
B.3 Calcul du volume
Conclusion g´en´erale et perspectives
Bibliographie