Robot aspirateur domestique dans un environnement dynamique

Le problème de la planification du chemin pour la couverture complète

       Comme indiqué plus haut, la problématique de la planification du chemin pour la couverture complète d’un environnement nécessite comme condition indispensable de trouver un chemin sans collision qui permet à un robot de passer au-dessus de tous les points dans un espace ou volume d’intérêt cible. Dans l’une des premières œuvres sur cette planification dans la littérature, les exigences que doit respecter un robot pour effectuer une opération de couverture ont été définies dans [9]. Dans le présent document nous allons traiter du robot mobile qui se déplace dans un environnement à deux dimensions et qui est soumis aux différentes exigences suivantes :
1. Le robot doit passer par tous les points couvrant complètement la zone cible.
2. Le robot doit couvrir la surface sans chevauchement des chemins.
3. L’opération de couverture continue et séquentielle sans aucune répétition des chemins, est nécessaire.
4. Des trajectoires avec un mouvement simple (par exemple, des lignes droites ou des cercles) doivent être utilisés pour plus de simplicité dans le contrôle.
5. Le robot doit éviter tous les obstacles.
6. Un chemin optimal est souhaité dans certaines conditions.
Cependant, dans des environnements complexes, il n’est pas toujours possible de satisfaire tous ces critères. Par conséquent, parfois une considération prioritaire est nécessaire. Le problème de la planification du chemin de couverture est liée au problème de satisfaction de contraintes (CSP), une variante du problème du voyageur de commerce (TSP), où, un agent doit visiter toutes les villes [10]. Rappelons que, compte tenu de la liste des villes et les distances entre chaque paire de villes, la TSP appelle à la route la plus courte qui visite chaque ville exactement une fois et revient à la ville de départ. Durant cette planification du chemin, l’agent doit passer par tous les points dans la zone cible au lieu de visiter tous les voisins. Depuis, la TSP est NP-complet, le temps de calcul nécessaire pour résoudre le problème augmente considérablement lorsque la dimension du problème augmente aussi. En effet, la planification d’un chemin pour tendre toute l’herbe d’une surface donnée couverte est connue sous l’expression «problème de la tondeuse », et prouvé par NPcomplet [11]. A noter que le problème de la tondeuse ne tient pas compte des obstacles. Il en est de même pour « le problème de piano-mover» qui est approuvé pour être PSPACEcomplet, ce qui implique NP-complet [12]. Deux autres problèmes similaires supplémentaires liés à cette planification sont le problème de « la galerie d’art » et « le veilleur de la route ». Le premier exige un nombre minimum de gardiens à la station dans une galerie polygonale de sorte que chaque point dans la galerie est visible par au moins un gardien [13]. Le deuxième exige le chemin le plus court entre un point donné et le veilleur lui-même de telle sorte que chaque point dans un espace donné est visible à partir d’au moins un point de la route [14]. En général, nous pouvons considérer que ces deux problèmes de la galerie d’art et du veilleur de la route sont NP-complet et qu’ils ont des algorithmes pour la couverture complète d’un environnement. Les algorithmes de couverture peuvent être classés comme heuristique ou complet qui garantissent ou non mathématiquement une couverture complète de l’espace libre. Indépendamment de cela, ils peuvent être classés comme étant soit offline ou online. Cette classification a été initialement proposée dans [15]. Les algorithmes offline reposent uniquement sur les informations stationnaires ; dans ce cas, l’environnement est supposé être connu à l’avance. Cette pleine connaissance préalable de l’environnement pourrait être irréaliste dans de nombreux scénarios. Tandis que les algorithmes online ne tiennent pas en pleine connaissance préalable l’environnement à couvrir et utilisent les mesures de capteurs en temps réel pour balayer l’espace cible. Ces algorithmes online sont également appelés algorithmes de couverture à base de capteurs. Dans certains scénarios, une approche valable pour résoudre le problème de couverture complète est de le rendre aléatoire. Cette approche a connu certains avantages : pas de capteurs de localisation complexes ni de ressources informatiques coûteuses. Cependant, pour couvrir une surface complexe, en particulier pour le nettoyage d’une chambre en utilisant un robot aspirateur autonome qui traite un espace plein d’obstacles, il est difficile de penser qu’un « algorithme » randomisé pourrait être utilisable, pour cela nous devons réfléchir à une approche ou à un algorithme très puissant pour planifier le chemin de ce robot aspirateur. La plupart des algorithmes de planification de chemin de couverture décomposent l’espace cible en sous-régions (appelées cellules) pour obtenir une couverture, Choset dans [15] a classé les algorithmes de couverture selon le type de décomposition utilisé. Par conséquent, sa taxinomie comprend des approches heuristiques et randomisées, des décompositions approximatives, semi-approximatives et exactes des cellules. Cette taxinomie de Choset est couramment utilisée dans la littérature, dans le présent document nous fournissons également la classification Choset correspondant pour les méthodes examinées.

Décomposition cellulaire basée-Morse Combinée avec le diagramme de Voronoi généralisé

           Les auteurs de [33,34] ont présenté une approche de couverture à base de capteurs avec extension. Ils soulignent que, « avant de faire la couverture à extension vous allez tomber dans l’un des deux extrêmes : la couverture avec un effecteur de la même taille du robot, et l’autre avec un effecteur qui a une portée infinie. » ils considèrent les résultats de leur travail comme une couverture au milieu de ce spectre : la couverture avec une portée de détecteur qui va au-delà du robot, et pourtant qu’elle soit encore limitée dans cette portée. Ils appellent ces capteurs : des capteurs de portée étendue. Selon ses résultats, la couverture est réalisée en deux étapes : la première étape considère des espaces vastes et ouverts, où le robot peut utiliser toute la portée de son détecteur ; le robot couvre alors ces espaces comme si ils étaient aussi grands que sa portée de détecteur (voir Figure 2.15, à droite). Un travail précédent dans l’utilisation des décompositions cellulaires Morse [18] où ils ont utilisé pour couvrir les espaces inconnus. Comme expliqué ci-dessus, les cellules de cette décomposition peuvent être couvertes par de simples mouvements de va-et-vient, et la couverture du vaste espace se réduit pour assurer que le robot visite chaque cellule dans le vaste espace. La deuxième étape considère les espaces étroits ou encombrés où les obstacles se trouvent à portée de détection, et donc ; le détecteur remplit le pourtour de la région. Dans ce cas, le robot peut couvrir l’espace étroit en suivant simplement le diagramme de Voronoi généralisé (GVD) de cet espace qui sont des ensembles de points équidistants aux deux obstacles [35, 36](voir Figure 2.15, à gauche). Le GVD peut être construit en ligne à l’aide des informations de capteur et il a été déjà utilisé pour l’exploration à base de capteurs [35] et l’inspection des structures en 3D [37]. Une décomposition hiérarchique qui combine les décompositions Morse et les GVDs est introduite pour s’assurer que le robot en effet visite touts des espaces grands, ouverts, ainsi que étroits, encombrés. Dans leur résultats, ils montrent comment construire cette décomposition en ligne en utilisant les données des capteurs accumulées pendant que le robot couvre l’environnement.

Couverture basée-grille en utilisant l’algorithme de bloc d’ondes

        Dans [47] Zelinsky et al ont présenté la première méthode basée sur les grilles pour la planification de chemin de couverture. Dans leur méthode hors ligne, ils utilisent une représentation grille et ils appliquent un algorithme complet de planification de chemin de couverture à la grille. La méthode nécessite une cellule de départ et une cellule d’arrivée. Une transformée de distance qui propage un bloc d’onde à partir de la cellule d’arrivée vers le départ, est utilisée pour attribuer un numéro spécifique à chaque élément de grille. Autrement dit, l’algorithme attribue un 0 à la cellule d’arrivée, puis un 1 à l’ensemble de ses voisins. Ensuite, toutes les cellules voisines de 1 non encore marquées seront marquées avec un 2. Le processus se répète incrémentiellement jusqu’à ce que la cellule de départ soit atteinte par le bloc d’onde. La figure 2.20.a illustre cette procédure sur un exemple d’environnement. Une fois que la transformée de distance est calculée, un chemin de couverture peut être trouvé à partir de la cellule de départ et la sélection de la cellule voisine qui a la plus haute étiquette non encore visitée. Si deux ou plus de cellules voisines non encore visitées partagent la même étiquette, l’une d’elles est sélectionnée de manière aléatoire. Ce processus de trouver un chemin de couverture est équivalent à l’utilisation de pseudo-descente de gradient à partir du point de départ sur la fonction de potentiel numérique, constitué par l’étiquetage, en suivant les courbes équipotentielles de haut en bas. La figure 2.20.b montre le parcours de la couverture générée pour un exemple d’environnement sur la figure 2.20.a. Une caractéristique unique de cet algorithme de couverture est qu’un point de départ et d’arrivé peuvent être spécifiés. Dans [48] Shivashankar et al. ont introduit une généralisation de l’algorithme de bloc d’onde à des environnements inconnus pour atteindre la couverture en ligne avec un robot mobile.

Applications du modèle PCNN

       Le PCNN a été utilisé pour une variété d’applications de traitement d’images, incluant : segmentation d’images, extraction de visage, détection de mouvement, croissance de région, réduction de bruit, etc. [79]. Une revue complète sur les PCNN et ses applications depuis 1999 à 2015 est exposée dans l’article de Wang et al [80]. Le PCNN est un sujet de recherche intéressant dans le domaine de l’intelligence artificielle. Le PCNN est utilisé dans les algorithmes de construction pour diverses applications comme la segmentation, l’amélioration, la fusion, extraction de caractéristiques, détection de bord, débruitage, la reconnaissance des formes, le décodage, l’amincissement d’image, etc. d’une façon générale dans les techniques de traitement d’image représentées sur la figure3.5. Les applications sont divisées en deux sections. La première section aborde l’utilisation du PCNN dans les procédures de traitement d’image, la segmentation, la fusion, la détection de caractéristiques, la suppression du bruit et la reconnaissance des formes des images ; tandis que la deuxième section examine les applications purement diverses. Le réseau trouve ses applications largement partout dans la médecine, la recherche, la surveillance, la reconnaissance des formes, etc.

Table des matières

Résumé en Arabe (Abstract in Arabic)
Abstract
Résumé
1. Introduction Générale 
1.1 Introduction 
1.2 Contexte et problématique de la thèse 
1.3 Organisation de la thèse 
2. Chapitre 2 : La couverture complète d’un environnement (planification du chemin)
2.1 Introduction
2.2 Le problème de la planification du chemin pour la couverture complète
2.3 Décomposition cellulaire exacte 
2.3.1 Décomposition trapézoïdale
2.3.2 Décomposition boustrophédonne
2.4 Décomposition cellulaire à base de morse 
2.4.1 Décomposition boustrophédonne basée Morse en ligne
2.4.2 Décomposition cellulaire basée-Morse Combinée avec le diagramme de Voronoi généralisé
2.5 Couverture topologique basée repère
2.5.1 Décomposition de Tranche
2.5.2 Algorithme de couverture topologique en ligne
2.6 Couverture des environnements rectilignes basée sur le contact du capteur (CCR)
2.7 Méthodes basées-grille
2.7.1 Couverture basée-grille en utilisant l’algorithme de bloc d’ondes
2.7.2 Couverture basée-grille en utilisant la construction des arbres
2.7.3 Couverture basée-réseau de neurones sur cartes de grille
2.7.4 Décomposition hexagonale de Grille pour les robots équipés de capteurs de vision latérale
2.8 Couverture basée-graphe
2.9 Couverture optimale 
2.10 Couverture dans l’incertitude
2.11 Discussion & Conclusion 
3. Chapitre 3 : PCNN : Un réseau neuronal à impulsions-couplées
3.1 Introduction 
3.2 Architecture du réseau 
3.3 Modèle mathématique d’un PCNN
3.4 Modifications au niveau du modèle PCNN
3.5 Applications du modèle PCNN
3.5.1 La segmentation par le modèle PCNN
3.5.2 Planification du chemin entre deux positions par le modèle PCNN
3.6 Conclusion
4. Chapitre 4 : Modélisation et simulation du modèle PCNN 
4.1 Introduction 
4.2 Modélisation cinématique
4.2.1 Contraintes cinématiques
4.2.2 Conception des roues
4.2.3 Robots mobiles à roues
4.2.4 Position du robot
4.2.5 Robot mobile de type tricycle
4.2.5.1 Centre instantané de rotation (CIR)
4.3 Architecture du robot 
4.4 Modélisation de l’environnement 
4.5 La couverture complète
4.5.1 Le modèle PCNN
4.5.2 Algorithme de Couverture complète
4.6 Planification du chemin pour la couverture complète 
4.7 Conclusion
5. Chapitre 5 : Tests et Résultats
5.1 Introduction
5.2 Application développée 
5.3 Configuration du matériel 
5.4 Configuration paramétrique 
5.5 Tests dans différents environnements
5.5.1 Dans un environnement connu
5.5.2 Dans un environnement inconnu
5.5.3 Dans un environnement dynamique
5.6 Comparaison avec autres méthodes
5.6.1 Comparaison avec les algorithmes LSSP, BA* et CAC
5.6.1.1 Algorithme LSSP
5.6.1.2 Algorithme BA*
5.6.1.3 Algorithme CAC
5.6.1.4 Test de comparaison
5.6.2 Comparaison avec la méthode Luo et Yang
5.7 Conclusion
6. Chapitre 6 : Conclusion Générale 
6.1 Conclusion générale 
6.2 Résumé des parties traitées tout au long de cette thèse 
6.3 Perspectives
Bibliographie

Télécharger le rapport complet