Show simple item record

dc.contributor.authorChevaleyre, Yann
dc.date.accessioned2011-09-16T10:20:21Z
dc.date.available2011-09-16T10:20:21Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6961
dc.description.abstractfrLe problème multi-agents de la patrouille a été récemment introduit dans [2]. Ce problème consiste a faire se déplacer un ensemble d'agents ou de robots sur un territoire prédéfini de telle sorte, informellement, que chaque partie de ce territoire soit visitée par des agents le plus souvent possible. Pour résoudre ce problème, des approches basées sur des architectures d'agents réactifs et cognitifs avaient été décrites dans [2]. Ce problème est ici abordé comme une tâche d'optimisation combinatoire. Pour cela, le territoire est modélisé sous forme d'un graphe. Différentes stratégies d'exploration du graphe sont envisagées, en particulier basées sur des cycles issus du voyageur de commerce. Avec ces dernières et dans le cas où le graphe est métrique, nous obtenons en temps polynomial une stratégie d'exploration dont la valeur est bornée par 3 × opt + 4 × maxij{cij}, avec cij désignant le poids de l'arête (i, j). On montre enfin qu'avec une autre approche basée sur un partitionnement du graphe en régions distinctes, le problème devient 15-approximable, même dans le cas de graphes non métriques.en
dc.language.isofren
dc.subjectSystèmes Multiagentsen
dc.subjectProblème de la Patrouilleen
dc.subjectOptimisation combinatoireen
dc.subjectApproximation polynomialeen
dc.subject.ddc003en
dc.titleLe problème multi-agents de la patrouilleen
dc.typeDocument de travail / Working paper
dc.publisher.nameUniversité Paris-Dauphineen
dc.publisher.cityParisen
dc.identifier.citationpages121-144en
dc.relation.ispartofseriestitleAnnales du LAMSADEen
dc.relation.ispartofseriesnumber4-5en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00115783/en/en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record