Approche centrée individu et systèmes multi-agents 

Simulation de trafic routier

L’étude des mécanismes du trafic et de ses acteurs, les conducteurs, est un domaine largement étudié [Salvucci et al., 2001, Elvik, 2004, Summala, 2005, Bazzan, 2005]. Ces études ne répondent pas toutes aux mêmes besoins, et sont abordées suivant différents axes.  L’ingénierie du trafic a pour objectifs de répondre à des problématiques de planification des transports (prévision du trafic, comme par exemple Bison futé [Danech-Pajouh, 2003]) ou de conception de nouveaux aménagements routiers [Hourdakis & Michalopoulos, 2002]. Pour répondre à ces problématiques, la modélisation des caractéristiques du trafic est un des axes de recherche fondamentaux, qui vise à reproduire et prédire son fonctionnement [Cohen, 1993].
Dans une perspective différente, la psychologie de la conduite vise à comprendre et expliquer le comportement des conducteurs [Letirand & Delhomme, 2005]. Identifier les facteurs conduisant à l’apparition de comportements à risque permet en effet de développer des techniques de prévention. Ces études mettent souvent en jeu l’observation du comportement de conducteurs réels, confrontés à des situations particulières comme la conduite dans le brouillard, et dont on analyse le comportement et les réactions [Saad, 1992, Priez et al., 1998, Caro et al., 2007]. Elles passent également par la conception de simulateurs dédiés à la simulation des conducteurs, visant à reproduire les processus cognitifs mis en œuvre [Salvucci, 2001, Bellet et al., 2005].
Dans ce contexte, la simulation du trafic trouve une place importante. Elle permet par exemple d’évaluer de nouvelles solutions de régulation du trafic, comme des stratégies de signalisation innovantes [Saunier, 2005]. Elle offre également un moyen de développer des systèmes en rupture, comme la prise en compte de la présence de véhicules robotisés dans un trafic réel [Dresner & Stone, 2007, Dresner & Stone, 2008]. Dans la plupart des cas, ces études ne peuvent pas être menées dans des situations réelles, principalement pour des contraintes de coût et de sécurité. La simulation offre une solution peu coûteuse et sûre pour mener ce type d’expérimentation, ainsi que la possibilité de tester de multiples possibilités de manière reproductible.

Modélisation du trafic

Int´eressons nous maintenant aux diff´erents ´el´ements sur lesquels repose la simulation du trafic : la repr´esentation de l’environnement, le mod`ele de trafic, et les caract´eristiques du conducteur prises en compte.

Représentation de l’environnement routier

Afin d’évoluer dans le monde simulé, les véhicules autonomes doivent percevoir l’environnement qui les entoure. Pour cela, ils peuvent utiliser différentes techniques.
Tout d’abord, le conducteur simulé peut analyser directement la scène visuelle virtuelle, comme un humain le ferait. Il en extrait les informations dont il a besoin, et les interprété en temps réel. Ces techniques sont utilisées en vision artificielle, par exemple dans Animat [Terzopoulos & Rabie, 1997], et permettent d’étudier comment les êtres vivants analysent leur environnement et en retirent des informations . Cependant ces méthodes mettent en œuvre des algorithmes complexes de vision et requièrent d’importantes capacités de calcul. Elles ne sont pas adaptées à notre contexte, où l’objectif ne se focalise pas sur les modalités de perception, mais sur la restitution d’un comportement réaliste.
Afin d’éviter ces problèmes de performances, les environnements de simulation de conduite sont généralement construits sous forme de bases de données multi-couches [Carles & Espié, 1999, Willemsen et al., 2003]. Une des couche contient une description logique de l’environnement, sur laquelle se base le modèle de décision des véhicules. Cette description logique est couplée à une couche contenant une représentation graphique, qui est présentée au conducteur dans le simulateur . La description logique présente l’avantage de pouvoir fournir aux véhicules autonomes une vue simplifiée de l’environnement, incluant en particulier la signalisation (lignes de marquage, panneaux. . .) et la structure du réseau (nombre de files, largeur des voies. . .).
Cela permet de limiter la charge de calcul liée à l’analyse du réseau. De plus, s’appuyer sur une description de ce type permet de contrôler la perception que les agents ont de l’environnement : ils ne pourront percevoir que les éléments définis par le concepteur. Enfin, il est possible de fournir aux véhicules une description sémantique de l’environnement, qui leur permet de réaliser des raisonnement sur des éléments de plus haut niveau, comme le type d’intersection duquel ils approchent.

Les modèles de trafic

Une fois qu’il possède une représentation de son environnement, le conducteur virtuel peut décider de quelle façon il va se déplacer. En situation de conduite, il a le choix entre différentes actions : continuer tout droit, changer de voie, dépasser, s’arrêter. . . Cette prise de décision est réalisée de façon variée suivant les modèles.
Approche par sous-modèles Une approche classique consiste à utiliser des sous-modèles des tâches de conduite, et de les appliquer en fonction du contexte. Le conducteur dispose d’un modèle pour le suivi de véhicule, d’un autre pour le changement de voie, d’un troisième pour s’engager en carrefour. . .
Par exemple, dans le cas du changement de voie, le processus de décision peut se baser sur la nécessité d’un changement (pour atteindre une sortie, pour doubler un véhicule trop lent), le désir d’un changement (va-t-on y gagner si l’on change de voie ?), et enfin sa faisabilité (existe-t-il un écart suffisant pour effectuer le changement ?) [Gipps, 1986]. Les paramètres utilisés prennent en compte la distance à la prochaine intersection : plus on s’en rapproche, plus la nécessité de se placer correctement pour sortir est important. Cela permet d’intégrer dans le modèle les contraintes auxquelles est soumis un conducteur réel.
Un autre de ces sous-modèles de tâche de conduite concerne le suivi de véhicule. Il décrit le comportement du conducteur lorsqu’il suit le véhicule le précédant dans la même voie. Ce type de modèle est fondamental en simulation de trafic, et a été largement étudié. Différentes classes peuvent être distinguées :
– les modèles Gazis-Herman-Rothery, qui considèrent que l’accélération du véhicule est proportionnelle à la vitesse du véhicule suivi, la différence de vitesse entre les véhicules, et la distance inter-véhiculaire [Chandler et al., 1958, Gazis et al., 1961],
– les modèles basés sur la distance de sécurité, qui reposent sur l’hypothèse que le suiveur garde toujours une distance de sécurité avec le véhicule précédant [Gipps, 1981],
– et les modèles de suivi de véhicule dits « psycho-physiques », qui utilisent des limites de  déclenchement afin de lisser le comportement du véhicule [Wiedemann, 1974, Fritzsche, 1994] : tant que la différence (de vitesse, par exemple) n’est pas trop importante, il n’y a pas de réaction. Notons que [Brackstone & McDonald, 1999a] propose une revue très complète de ces modèles. Approche par automates Une autre méthode de prise de décision est basée sur l’utilisation d’automates [Kemeny, 1993, Cremer et al., 1995]. Dans ce cas, les états de l’automate représentent les différentes actions qui peuvent être réalisées : par exemple rouler sur une zone libre, suivre un véhicule, rester dans une voie, tourner `a une intersection, et dépasser sur une auto-route [Cremer & Joseph Kearney, 1996]. Le choix de l’état est basé sur des fonctions de scoring, d’éventuels conflits étant résolus par une priorisation a priori des actions. Par exemple, doubler peut être considéré comme systématiquement plus intéressant que de rester sur la même voie.
Les automates permettent de décrire de manière simple le fonctionnement du système, mais présentent des limites dans le cas de comportements complexes. Un conducteur peut en effet être confronté à des actions mettant en jeu un équilibre entre plusieurs actions, ce qui n’est pas envisageable avec une structure d’automate.
Approche par minimisation des interactions D’autres approches s’appuient sur des modes de décision visant à se rapprocher de ceux mis en œuvre par les conducteurs réels. Par exemple, la méthode utilisée dans l’application de simulation de conduite Archisim est basée sur la minimisation des interactions [Espié et al., 1994]. Elaborée à partir d’études menées par des psychologues de la conduite, elle s’appuie sur l’hypothèse qu’un conducteur prend ses décisions sur la base des conditions de trafic dans différentes zones autour du véhicule . A partir de la distribution des vitesses et de la vitesse minimale dans la zone, la durée de l’interaction est évaluée. En y ajoutant la distance temporelle estimée de l’interaction, le modèle décide s’il est nécessaire de réagir. Par exemple, si l’interaction est estimée de courte durée, aucune adaptation n’a lieu : cela évite qu’un véhicule change sans cesse de file en fonction des conditions très locales de circulation. Ce mécanisme permet aux conducteurs de ne pas réagir instantanément aux variations de l’environnement, et d’anticiper certains changements en intégrant la durée des interactions dans leur processus de décision.

Les systèmes multi-agents

Caractéristiques

Afin de présenter les différents aspects d’un système multi-agents, nous considérons l’approche voyelles [Demazeau, 1995]. Dans cette approche, le système s’articule autour de quatre dimensions : l’Agent, l’Environnement, l’Interaction et l’Organisation. Le système multi-agents peut alors être défini par un ensemble A d’entités autonomes dotées de capacités de perception et d’action, évoluant dans un environnement E et Interagissant dans le cadre d’une organisation .  Un système multi-agents est caractérisé par l’absence de contrôle global. La prise de décision est décentralisée, et chaque agent possède un certain degré d’autonomie dans ses actions. Une des conséquences directes de l’aspect décentralisé de la prise de décision est l’émergence : cette notion caractérise l’apparition de phénomènes au niveau du système, alors que les caractéristiques individuelles des agents ne contiennent aucune référence à ce phénomène. L’émergence représenté donc le passage du niveau local au niveau global, ou encore du niveau microscopique au macroscopique.

Catégorisation

Différentes catégories de systèmes multi-agents peuvent être distinguées, en fonction du type de problème ciblé. La première catégorie concerne la résolution de problèmes distribués. Dans ce cadre, l’objectif est que les agents coopèrent et se coordonnent pour résoudre ensemble un problème global. Chaque agent se voit typiquement confier une sous-tâche de l’objectif, sans nécessairement connaître le but final. Les problématiques soulevées sont liées à la communication, la coordination, ou encore l’allocation des tâches.
La seconde catégorie contient les applications dans lesquelles les agents sont conçus pour jouer un rôle similaire à celui d’un être humain. Cela peut concerner par exemple la conception d’assistants virtuels, auxquels est délégué la tâche de maintenir l’agenda de leur correspondant humain, ou des agents destinés à enchérir sur des plateformes comme eBay lors de l’absence du propriétaire du compte. Les problématiques concernent ici en particulier la sécurité et les communications.
Enfin, la dernière catégorie regroupe les applications dont le but est de simuler des phénomènes issus du monde réel, l’objectif étant de les reproduire pour les comprendre ou les expliquer. Les systèmes multi-agents ont ainsi rencontré un fort intérêt dans des domaines comme la simulation sociale ou l’éthologie, où l’apparition de phénomènes macroscopiques n’est pas expliquée simplement par les compétences des agents. La simulation centrée individus permet de comprendre quels éléments ou quelles interactions conduisent à l’apparition de ces propriétés globales.
Notre application se situe dans cette dernière catégorie. Nous reviendrons donc plus loin sur l’intérêt de la simulation centrée individu.

Composition d’un système multi-agents

Intéressons nous maintenant aux différents éléments constituant un système multi-agent selon l’approche voyelles : les agents, l’environnement, les interactions et l’organisation.

Les agents

Diverses définitions ont été proposées pour la notion d’agent. En effet, ce concept est utilisé dans des domaines variés : agents conversationnels animés, applications réparties, simulation informatique, résolution de problème par émergence, etc. Ces contextes présentent des particularités qui conduisent à adapter la définition utilisée. Ferber propose la définition suivante [Ferber, 1995] : « On appelle agent une entité physique ou virtuelle : qui est capable d’agir dans un environnement, qui peut communiquer directement avec d’autres agents, qui est mue par un ensemble de tendances (sous la forme d’objectifs individuels ou d’une fonction de satisfaction, voire de survie, qu’elle chercher à optimiser), qui possède de ressources propres, qui est capable de percevoir (mais de manière limitée) son environnement, qui possède des compétence et offre des services, qui peut éventuellement se reproduire, dont le comportement tend `a satisfaire ses objectifs, en tenant compte des ressources et des compétences dont elle dispose, et en fonction de sa perception, de ses représentations et des communications qu’elle reçoit.»
Cette définition présente l’intérêt de présenter l’ensemble des éléments clés relatifs au concept d’agent. Suivant l’accent mis sur les différents points de la définition, différentes catégories d’agents peuvent être distinguées [Wooldridge, 2002] : les agents réactifs, les agents cognitifs, et les agents hybrides.
Pour les agents réactifs, la perception entraîne l’action par un couplage direct. La phase de cognition est réduite au minimum, voire est inexistante : elle est restreinte au déclenchement de règles comportementales. L’utilisation d’agents réactifs repose sur le fait que l’émergence d’un comportement au niveau global ne s’appuie pas nécessairement sur des comportements individuels complexes. C’est le cas par exemple dans les colonies de fourmis : le dépôt de phéromones par les agents fourmis sur leur trajet vers les sources de nourriture, couplé à l’action de suivre les pistes les plus odorantes, suffit à faire émerger un comportement global [Dorigo et al., 1996].

L’environnement

L’environnement décrit le contexte dans lequel les agents évoluent. En fonction de l’application, il correspond à des ensembles très différents : par exemple, dans le cadre d’agents communicationnels, il est constitué par le réseau entre les agents; pour des agents géographiquement situés, il contient la description du contexte, comme la base de données, les éléments logiques. . . Il peut par ailleurs être utilisé comme vecteur de communication entre les agents : c’est le cas par exemple dans les approches utilisant un tableau noir [Corkill, 1991].
L’environnement possède différentes propriétés [Russell & Norvig, 1995] :
– il peut être accessible ou inaccessible : dans un environnement accessible, il est possible d’obtenir des informations complètes, précises et à jour sur l’état de l’environnement. Les agents reposent sur la précision des informations à leur disposition pour prendre leurs décisions : si ces informations sont incomplètes ou imprécises, leurs décisions peuvent être erronées. Notons que la plupart des environnements réels sont inaccessibles,
– l’environnement peut être déterministe ou non-déterministe : dans un environnement déterministe, toutes les actions ont un effet garanti et reproductible. Si l’environnement est non déterministe, un agent ne peut pas être sûr que l’action qu’il a réalisé a été prise en compte dans l’environnement : il doit considérer qu’elle peut avoir échoué,
– l’environnement peut être statique, ou dynamique : un environnement statique reste inchangé tant que l’agent ne réalise pas d’action. Dans le cadre multi-agent, l’environnement est le plus souvent dynamique : les autres agents pouvant eux-mêmes agir sur le monde, aucun agent ne peut supposer son environnement statique,
– enfin l’environnement peut être discret ou continu : un environnement est discret s’il existe un nombre fini d’actions possibles. Par exemple, un jeu d’échec est un environnement discret : le nombre d’états et d’actions possibles dans l’environnement est fini, même s’il est très élevé.

Table des matières

Introduction 
1 Contexte 
1.1 Simulation de trafic et simulateurs de conduite 
1.1.1 Simulation de trafic routier
1.1.2 La simulation de trafic dans les simulateurs de conduite
1.1.3 Modélisation du trafic
1.1.4 Exemples d’applications existantes
1.1.5 Le cas des jeux vidéos
1.2 Approche centrée individu et systèmes multi-agents 
1.2.1 Les systèmes multi-agents
1.2.2 Composition d’un système multi-agents
1.2.3 La simulation centrée individus
1.3 Travaux connexes 
1.3.1 Gestion de configuration
1.3.2 Génération de paramétrage de modèles complexes
1.3.3 Variété et simulation de foules
1.3.4 Des personnalités virtuelles pour les conducteurs
2 Une description normative 
2.1 Les approches normatives 
2.1.1 Introduction
2.1.2 Normes et systèmes multi-agents
2.1.3 Exemples d’applications
2.2 Description normative des comportements 
2.2.1 Notre approche
2.2.2 Sémantique
2.2.3 Violations de la norme
2.3 Génération des comportements
2.3.1 Présentation
2.3.2 Application à la structure de données
3 Variété et conformité 
3.1 Gestion du système
3.1.1 Introduction
3.1.2 Les cartes auto-adaptatives ou réseaux de Kohonen
3.1.3 Applications
3.2 Variété et conformité
3.2.1 Variété
3.2.2 Conformité
3.3 Utilisation de l’outil 
3.3.1 Différents modes d’utilisation
3.3.2 Utilisation de l’outil
3.4 Généricité 
3.4.1 Variété dans la simulation de foules
3.4.2 Un créateur de créature
4 Application à la simulation de trafic 
4.1 La suite logicielle SCANeR
4.1.1 Présentation
4.1.2 La simulation de trafic dans SCANeR
4.1.3 Le modèle de trafic
4.1.4 Le cas des piétons
4.2 Application du modèle à SCANeR
4.2.1 Objectif
4.2.2 Implémentation
4.2.3 Intégration du modèle dans SCANeR
4.2.4 Synthèse
5 Evaluation, discussion et perspectives 
5.1 Démarche de validation 
5.1.1 Calibration des modèles
5.1.2 Collecte de données
5.1.3 Validation du trafic dans les simulateurs de conduite
5.2 Evaluation de l’apport des normes dans scaner
5.2.1 Description des simulations
5.2.2 Apports du modèle
5.2.3 Apprentissage des normes
5.3 Evaluation du trafic dans scaner
5.3.1 Objectif
5.3.2 Congestion sur autoroute
5.3.3 Influence des voies d’insertion
5.3.4 Synthèse
5.4 Discussion
5.4.1 Discussion du modèle de différenciation comportementale
5.4.2 Discussion de l’application à la simulation de trafic
5.5 Perspectives 
5.5.1 Perspectives du modèle de différenciation comportementale
5.5.2 Perspectives de l’application à la simulation de trafic
5.5.3 Evolutions complémentaires du trafic
Conclusion 
Bibliographie

Télécharger le rapport complet