| Titre : | Navigation réactive d'humain virtuel par planification locale |
| Auteurs : | ALI GAGUI, Auteur ; Foudil Cherif, Directeur de thèse |
| Type de document : | Thése doctorat |
| Editeur : | Biskra [Algérie] : Faculté des Sciences Exactes et des Sciences de la Nature et de la Vie, Université Mohamed Khider, 2013 |
| ISBN/ISSN/EAN : | TINF/62 |
| Format : | 1 vol. (129 p.) / ill. / 29 cm |
| Langues: | Français |
| Résumé : |
Dans la littérature, le problème général de la navigation est abordé principalement suivant deux perspectives, celle des techniques délibératives et celle des techniques réactives. Les techniques réactives ont été originellement motivées par la nécessité des humains virtuel à pouvoir réagir à l’environnement afin d’éviter les obstacles. Ces techniques nécessitent d’être rapides ce qui limite fortement le temps de calcul disponible tout en évitant de rentrer en collision avec les obstacles de l’environnement. La première difficulté consiste donc à structurer l’environnement pour gérer efficacement les requêtes, comme par exemple trouver un chemin ou détecter les obstacles proches. L’autre difficulté réside dans son peuplement avec des entités pouvant interagir entre elles et avec l’environnement. Nous avons étudié les différentes méthodes de représentations de l’environnement adaptées au calcul de chemins. Notre choix est fait sur la décomposition cellulaire « grille », cette décomposition cellulaire nous a permis de construire un graphe sur lequel on a appliqué les dernières techniques de calcul de chemin optimum. Pour arriver à une navigation réaliste, on a étudié au premier lieu les caractéristiques et les comportements des personnes en déplacement dans un environnement avec des obstacles statiques, dynamiques et imprévisibles. La carte de cheminement est utilisée pour avoir des chemins libres d’obstacles statiques. On a développé notre approche pour l’évitement des obstacles dynamiques et imprévisibles. |
| Sommaire : |
INTRODUCTION GÉNÉRALE 1 1. INTRODUCTION 5 2. REPRESENTATION DES PARTIES STATIQUES DE L’ENVIRONNEMENT : 6 2.1. DECOMPOSITION EN CELLULES 6 2.1.1. Décompositions approximatives : 6 2.1.2. Décomposition exacte : 8 2.2. CARTES DE CHEMINEMENT : 12 2.2.1. Cartes de cheminement déterministes. 13 2.2.2. Les diagrammes de Voronoï 13 2.2.3. Cartes de cheminement probabilistes 14 3. LA PLANIFICATION DE MOUVEMENT : 14 3.1. LA PLANIFICATION GLOBALE 14 3.1.1. Recherche dans un graphe 14 4. CONCLUSION 18 1. INTRODUCTION : 20 2. MODELISER LE COMPORTEMENT : 20 2.1. GENERALITES 20 3. MODELISATION DU COMPORTEMENT : 21 4. ARCHITECTURES REACTIVES 22 4.1. STIMULUS/REPONSES : 22 4.2. LES MODELES A BASE DE REGLES : 23 4.3. LES AUTOMATES : 24 4.4. SYNTHESE 24 5. LES MODELES COGNITIFS : 25 5.1. CALCUL SITUATIONNEL ET DERIVES : 25 5.1.1. STRIPS 26 5.1.2. Les réseaux de tâches hiérarchiques : 26 5.1.3. Synthèse : 27 5.2. SELECTION D’ACTIONS : 28 5.2.1. BCOOL 28 5.2.2. Synthèses 29 5.3. SYSTEMES BDI 29 6. OBJETS INFORMES 30 6.1. LES SMART OBJECTS 30 6.2. LE MODELE STARFISH 31 7. EMOTIONS ET PERSONNALITE 31 7.2. CARTES EMOTIONNELLES FLOUES 33 8. CONCLUSION 35 1. INTRODUCTION 37 2. MODELE A BASE DE PARTICULES 37 2.1. MODELISATION COMPORTEMENTALE 39 2.1.1. Le modèle à base de règles : 40 2.1.2. Un modèle géométrique prédictif 41 3. CLASSIFICATION DES TECHNIQUES DE NAVIGATION 43 3.1. Techniques Actives ou Passives 44 3.2. Techniques Physiques ou virtuelles 44 3.3. En fonction de la tâche à accomplir 44 3.4. CLASSIFICATION PAR METAPHORE 45 4. DIFFERENTES MODELISATIONS : PERSONNE, GROUPE, FOULE 46 4.1. MODELES D’AGENTS VIRTUELS 46 4.2. MODELES DE GROUPES 47 4.3. MODELES DE FOULES 47 4.3.1. Classification des méthodes de foule 48 5. ÉVITEMENT D’OBSTACLES 48 5.1. METHODE DES CHAMPS DE POTENTIEL 48 5.2. METHODE VECTOR FIELD HISTOGRAM 49 5.3. METHODE DE LA FENETRE DYNAMIQUE 51 6. DETECTIONS DE VOISINAGE ET EVITEMENT 53 6.1. DETECTION DE LA COLLISION 53 6.2. TYPE DETECTIONS DE LA COLLISION : 53 6.2.1. Intersection d'objets convexes 55 6.2.2. Partitionnement de l'espace 58 6.2.3. Hiérarchie de volumes englobants 59 6.2.4. Approximation 62 6.2.5. Accélération matérielle 63 7. EVITEMENT DE LA COLLISION 66 7.1. ADAPTATION POUR L’EVITEMENT 67 8. CONCLUSION 68 LE MODELE PROPOSE 70 1. INTRODUCTION 70 1.1. VUE GLOBALE SUR LE MODELE : 71 2. LA REPRESENTATION DE L’ENVIRONNEMENT ET PLANIFICATION DE CHEMIN : 72 2.1. GENERATION DE LA CARTE DE CHEMINEMENT « GRILLE » 72 2.1.1. Structure et fonctionnement du nœud 73 2.1.2. La diffusion des nœuds 76 2.1.3. La connexion des nœuds 77 2.1.4. L'inondation se remplit « Flood fill » 77 2.1.5. Exporté la carte de cheminement sur un support physique 78 3. NOTRE MODELE D’HUMAIN VIRTUEL 80 3.1.1. Perception : 81 3.2. CONCLUSION 83 4. NAVIGATION REACTIVE 84 4.1. ARCHITECTURE DE NAVIGATION 84 4.2. MODELISATION DE LA NAVIGATION 87 4.2.1. L’exploitation de la carte de cheminement 87 4.2.2. La recherche d’un chemin optimal « Algorithme de A* » 87 4.2.3. Comment éviter les obstacles ? 92 Evitement d’obstacles statiques 95 Evitement d’obstacles dynamiques 95 Evitement d’obstacles imprévisibles 98 5. Comment atteindre la cible ? 99 6. CONCLUSION 101 1. INTRODUCTION 103 2. IMPLEMENTATION DU SYSTEME 103 2.1. LANGAGE DE PROGRAMMATION ET BIBLIOTHEQUE GRAPHIQUE 104 2.1.1 APERÇU SUR L’OUTIL DE DEVELOPPEMENT DE L’APPLICATION 104 2.1.1.1 UNITY 3D 104 2.2. DESCRIPTION DES LANGAGES DE DEVELOPPEMENT 106 2.2.1. Langage C# 106 2.2.2. Langage XML 106 3. PRESENTATION DE SYSTEME 107 3.1. PRESENTATION DE DIFFERENTS SCRIPTES UTILISES 108 3.2. PRESENTATION DE DIFFERENTS PREFABRIQUES « PREFABS » 112 3.3. LA MISE EN ŒUVRE DE LA CARTE DE CHEMINEMENT 114 3.3.1. Présentation et fonctionnement du nœud réalisé 114 3.3.2. La diffusion et la connexion des nœuds 116 3.3.3. L'inondation se remplit « Flood fill » 118 3.3.4. Le contenu du fichier XML 119 3.4. LA NAVIGATION 120 3.4.1. Trouver la cible 121 3.4.2. Peaufiner le chemin proposé 121 3.4.3. Evitement des obstacles 122 4. PRESENTATION DU RESULTAT FINAL 125 5. CONCLUSION 127 CONCLUSION GENERALE ET PERSPECTIVES 128 BIBLIOGRAPHIE 131 |
| En ligne : | http://thesis.univ-biskra.dz/id/eprint/544 |
Disponibilité (1)
| Cote | Support | Localisation | Statut |
|---|---|---|---|
| TINF/62 | Mémoire de magister | bibliothèque sciences exactes | Consultable |
