Nouvelles de l'industrie
0102030405
Comment un robot peut-il localiser, cartographier et se déplacer dans un environnement inconnu ?
2023-12-08
1. Avant-propos Avec le développement rapide de la technologie informatique, l'approfondissement de la recherche sur les robots et l'expansion de la demande de robots, les robots capables de se déplacer intelligemment et de naviguer de manière autonome sont devenus le centre de la recherche. Il existe des solutions pratiques pour la localisation autonome des robots dans un environnement connu et la création de cartes de la position connue du robot. Cependant, dans de nombreux environnements, le robot ne peut pas utiliser le système de positionnement global pour le positionnement et il est difficile d'obtenir à l'avance la carte de l'environnement de travail du robot. À ce stade, le robot doit créer une carte dans un environnement complètement inconnu dans des conditions de position incertaine et utiliser la carte pour un positionnement et une navigation autonomes. La technologie Slam (positionnement synchrone et création de cartes) est considérée comme la technologie de base et clé pour réaliser un robot mobile véritablement autonome.
Le robot commence à se déplacer depuis une position inconnue dans un environnement inconnu. En cours de déplacement, il se localise en fonction de l'estimation de position et des données du capteur, et améliore et construit progressivement une carte complète. C’est un processus de claquement. En slam, le robot utilise son propre capteur pour identifier la marque caractéristique dans un environnement inconnu, puis estime les coordonnées globales du robot et de la marque caractéristique en fonction de la position relative entre le robot et la marque caractéristique et de la lecture du compteur kilométrique. Ce positionnement en ligne et cette création de carte doivent conserver les informations détaillées entre le robot et la marque caractéristique. Ces dernières années, la recherche sur le slam a fait de grands progrès et a été appliquée à divers environnements, tels que les robots, AR, VR, UAV, pilote automatique, etc.2. Les enjeux clés du chelem 2.1 représentation de la carte À l'heure actuelle, les méthodes courantes de représentation cartographique peuvent être grossièrement divisées en trois catégories : la représentation en grille, la représentation d'informations géométriques et la représentation topologique. Chaque méthode a ses propres avantages et inconvénients. (1) Carte d'informations géométriques La représentation cartographique d'informations géométriques signifie que le robot collecte les informations de perception de l'environnement, extrait des caractéristiques géométriques plus abstraites, telles que des segments de ligne ou des courbes, et utilise ces informations géométriques pour décrire l'environnement. avantage : il est plus compact et pratique pour l'estimation de position et la reconnaissance de cibles ; La méthode géométrique utilise le filtre de Kalman pour obtenir une grande précision et une faible quantité de calculs dans la zone locale ; Inconvénients : L'extraction d'informations géométriques nécessite un traitement supplémentaire d'informations perceptuelles, et une certaine quantité de données perceptuelles est nécessaire pour obtenir les résultats ; Il est difficile de conserver des informations de coordonnées précises dans un environnement étendu ; (2) Carte quadrillée La carte quadrillée consiste à diviser l'ensemble de l'environnement en plusieurs grilles de même taille et à indiquer s'il y a des obstacles pour chaque grille. avantage : facile à créer et à maintenir, et essayer de conserver toutes sortes d'informations sur l'ensemble de l'environnement ; À l'aide de la carte, l'auto-positionnement et la planification du chemin peuvent être effectués facilement ; Inconvénients : Lorsque le nombre de grilles augmente (dans un environnement à grande échelle ou lorsque l'environnement est divisé en détail), il deviendra difficile de maintenir la carte. Dans le même temps, il existe un grand espace de recherche dans le processus de positionnement. Sans un bon algorithme simplifié, il est difficile de réaliser une application en temps réel. (3) Carte topologique Les cartes topologiques sont très abstraites, surtout lorsque l'environnement est vaste et simple. Dans cette méthode, l'environnement est représenté sous forme de graphe au sens de topologie, et les nœuds du graphe correspondent à un état et un emplacement caractéristiques dans l'environnement. S'il existe un chemin de connexion direct entre les nœuds, cela équivaut aux nœuds de connexion en arc sur la figure. avantage : Propice à une planification ultérieure du chemin et des tâches ; L'espace de stockage et de recherche est relativement petit et l'efficacité informatique est élevée ; De nombreux algorithmes de recherche et de raisonnement matures et efficaces peuvent être utilisés ; Inconvénients : lors de son utilisation, il doit être basé sur l'identification et la correspondance des nœuds topologiques. Par exemple, lorsqu'il y a deux endroits très similaires dans l'environnement, il sera difficile pour la méthode de carte topologique de déterminer s'il s'agit du même point ;2.2 description des informations incertaines Lorsque l'environnement est complètement inconnu, si le robot veut construire une carte et marcher, il doit obtenir des informations à l'aide d'autres capteurs, tels qu'un odomètre, un sonar, un télémètre laser, une vision, etc. En raison des limites du capteur lui-même, il existe différents degrés d'incertitude dans les informations de détection. Par exemple, l'incertitude du télémètre laser provient principalement de l'erreur de mesure de la distance et de l'erreur d'angle de mesure provoquée par la rotation du réflecteur et la diffusion laser. Comme le montre la figure ci-dessus, l'incertitude des informations perçues conduira inévitablement à l'impossibilité que le modèle d'environnement construit soit complètement précis. De même, lorsque l’on prend des décisions basées sur un modèle et une perception, il existe une incertitude, c’est-à-dire que l’incertitude est transitive. Les méthodes permettant de mesurer l'incertitude comprennent principalement la mesure de la probabilité, la mesure de la confiance, la mesure des possibilités, la mesure floue et la théorie des preuves. À l’heure actuelle, les mesures de probabilité et les mesures floues sont largement utilisées dans la construction de cartes AMR. Il existe deux formes principales de mesure de probabilité : (1) Les informations incertaines sont décrites par des caractéristiques de probabilité telles que la moyenne, la variance et la covariance. L'avantage de cette méthode de mesure est que les caractéristiques de probabilité telles que la moyenne ont une signification géométrique claire, mais l'inconvénient est que la formule de calcul discrète des caractéristiques de probabilité n'a pas été déterminée ; (2) Le modèle de probabilité est utilisé pour décrire des informations incertaines, principalement en utilisant la règle de Bayes et l'hypothèse de Markov. L'avantage de cette méthode de mesure est que la position, l'attitude et les informations environnementales du robot sont décrites par le modèle de probabilité aléatoire et que la robustesse est très bonne. L'inconvénient est que la quantité de calcul du modèle probabiliste est très importante et que la probabilité a priori du modèle doit être connue à l'avance, ce qui rend son application pratique difficile.2.3 Extraction de localisation et de caractéristiques environnementales L'autolocalisation des robots mobiles est étroitement liée à la modélisation environnementale. La précision du modèle d'environnement dépend de la précision du positionnement, et la mise en œuvre du positionnement est indissociable du modèle d'environnement. Dans un environnement inconnu, le robot n'a aucune référence et ne peut s'appuyer que sur ses propres capteurs imprécis pour obtenir des informations externes, tout comme un aveugle tâtonnant dans un environnement inconnu. Dans ce cas, le positionnement est difficile. Le positionnement sur carte et la création de carte avec positionnement sont faciles à résoudre, mais le positionnement sans carte et la création de carte sans positionnement sont comme le problème de « l'œuf de poule ». Dans les recherches existantes, les solutions à de tels problèmes peuvent être divisées en deux catégories : (1) Tout en s'appuyant sur des capteurs internes pour estimer leur propre mouvement, des capteurs externes (tels qu'un télémètre laser, une vision, etc.) sont utilisés pour percevoir l'environnement. , analysez les informations obtenues, extrayez les caractéristiques environnementales et enregistrez-les. À l'étape suivante, leur propre position est corrigée en comparant les caractéristiques environnementales. Mais cette méthode dépend de la capacité à obtenir des caractéristiques environnementales. (2) En utilisant une variété de capteurs internes (y compris un odomètre, une boussole, un accéléromètre, etc.) portés par lui-même, l'erreur de positionnement est réduite grâce à la fusion d'une variété d'informations de capteur. La plupart des algorithmes de fusion utilisés sont basés sur le filtre de Kalman. Étant donné que ces méthodes ne font pas référence à des informations externes, l'accumulation d'erreurs sera importante après une itinérance de longue durée. Les méthodes d'extraction de caractéristiques environnementales comprennent : 1) . La transformation de Hough est une sorte de méthode pour détecter des lignes et autres courbes basées sur une image grise. Cette méthode nécessite un groupe de courbes spécifiques pré-préparées qui peuvent être recherchées et génère des paramètres de courbe en fonction d'un groupe de courbes dans l'image grise affichée. 2) . L'analyse de regroupement est un outil de détection de données efficace pour les échantillons non classés. Dans le même temps, son objectif est de diviser les objets ciblés en catégories naturelles ou classes de clusters en fonction de la similitude ou de la distance. Lorsque la catégorie de l'objet extrait est inconnue, la technologie de clustering est une technologie plus efficace que houghtransform. Les classes groupées devraient être centrées sur la « cohésion », plutôt que fragmentées et disjointes. Les caractéristiques environnementales sont parfois difficiles à extraire. Par exemple, lorsque les caractéristiques environnementales ne sont pas suffisamment évidentes ou qu’il existe peu d’informations provenant des capteurs, il est difficile d’obtenir des caractéristiques environnementales à partir d’informations de perception ponctuelles.2.4 Association de données L'association de données consiste à faire correspondre deux marques caractéristiques pour déterminer si elles correspondent au même objet dans l'environnement. L'association de données en slam doit principalement accomplir trois tâches : (1) Correspondance entre les cartes ; (2) Correspondance des marques caractéristiques ; (3) Détection de nouvelles marques de caractéristiques ; Bien que l'association de données ait été bien résolue dans les domaines du suivi de cibles et de la fusion de capteurs, ces méthodes nécessitent une grande quantité de calcul et ne peuvent pas répondre aux exigences en temps réel du slam. La complexité d'association des données entre M signes et cartes à n signes est exponentielle avec M. en supposant que chaque signe observé I ait une correspondance possible, pour M signes, il faut rechercher la bonne correspondance dans l'espace exponentiel =. L'espace de recherche d'association de données est lié à la complexité de l'environnement et à l'erreur de positionnement du robot. L’augmentation de la complexité de l’environnement augmentera m, et l’augmentation de l’erreur augmentera Ni.2,5 erreur cumulée Les erreurs en slam proviennent principalement de trois aspects : (1) erreur d'observation ; (2) Erreur du compteur kilométrique ; (3) Erreurs causées par une association de données incorrecte ; Lorsque le robot se localise dans l'environnement d'une carte connue, le robot peut compenser l'erreur de l'odomètre en observant la marque caractéristique avec une position connue. Chaque observation fait tendre l'erreur de position du robot vers la somme de l'erreur d'observation et de l'erreur de position de la marque caractéristique. Cependant, en slam, comme la position du robot et la position de la marque caractéristique dans l'environnement sont inconnues, les informations d'observation ne peuvent pas corriger efficacement l'erreur de l'odomètre et l'erreur de position du robot augmente avec la distance de déplacement de le robot. L'augmentation de l'erreur de position du robot entraînera une mauvaise association de données, ce qui augmentera l'erreur de position de la marque caractéristique ; à son tour, l’erreur de la marque caractéristique augmentera l’erreur de position du robot. Par conséquent, l’erreur de position du robot est étroitement liée à l’erreur de position de la marque caractéristique. L'interaction entre eux fait que l'estimation de la position du robot et la marque caractéristique produisent une erreur cumulative, ce qui est difficile à garantir la cohérence de la carte. 3. Méthode de mise en œuvre du slam À l'heure actuelle, les méthodes de slam peuvent être grossièrement divisées en deux catégories : (1) Méthodes basées sur un modèle probabiliste : slam complet basé sur un filtre de Kalman, un filtre de compression, FastSLAM, etc. (2) Méthodes de modèle non probabiliste : sm -slam, scan matching, association de données, basé sur la logique floue, etc.Méthode d'implémentation 3.1 basée sur le filtre de Kalman Du point de vue statistique, le slam est un problème de filtrage, c'est-à-dire estimer l'état actuel du système en fonction de l'état initial du système et des informations d'observation et de contrôle (lecture du compteur kilométrique) de 0 à t. En slam, l'état du système est composé de la pose du robot R et des informations cartographiques m (y compris les informations de position de chaque marque caractéristique). En supposant que le modèle de mouvement et le modèle d'observation du système sont des modèles linéaires avec un bruit gaussien et que l'état du système obéit à la distribution gaussienne, le claquement peut être réalisé par le filtre de Kalman. Le filtre SLAM basé sur Kalman comprend deux étapes : la prédiction et la mise à jour de l'état du système. Dans le même temps, il doit également gérer les informations cartographiques, telles que l'ajout de nouveaux repères caractéristiques et la suppression de repères caractéristiques. Le filtre de Kalman suppose que le système est un système linéaire, mais en pratique, le modèle de mouvement et le modèle d'observation du robot sont non linéaires. Par conséquent, le filtre de Kalman étendu est généralement utilisé. Le filtre de Kalman étendu représente approximativement le modèle non linéaire via le développement de Taylor du premier ordre. Un autre filtre Kalman adapté aux modèles non linéaires est l'UKF (filtre Kalman non parfumé). UKF utilise la distribution gaussienne conditionnelle pour approximer la distribution de probabilité a posteriori. Comparé à l'EKF, l'UKF a une précision de linéarisation plus élevée et n'a pas besoin de calculer la matrice jacobienne. Le filtre de Kalman est devenu la méthode de base pour réaliser le slam. Sa matrice de covariance contient les informations incertaines sur la position et la carte du robot. Lorsque le robot observe en permanence les signes caractéristiques de l'environnement, le déterminant de toute sous-matrice de la matrice de covariance diminue de façon monotone. Théoriquement, lorsque le nombre d'observations tend vers l'infini, la covariance de chaque marque caractéristique n'est liée qu'à la covariance de la position de départ du robot. La complexité temporelle du filtre de Kalman est O (). Étant donné que le robot ne peut observer que quelques marques de caractéristiques à chaque fois, la complexité temporelle du SLAM basé sur le filtre de Kalman peut être optimisée comme O (), et N représente le nombre de marques de caractéristiques sur la carte.3.2 Méthode de sous-carte locale La méthode des sous-cartes locales décompose le slam en sous-problèmes plus petits du point de vue de l'espace. Les problèmes suivants doivent être pris en compte dans la méthode des sous-cartes : (1) Comment diviser les sous-cartes ; (2) Comment représenter la relation entre les sous-cartes ; (3) Comment transférer les informations de la sous-carte vers la carte globale et si la cohérence de la carte globale peut être garantie ; La méthode de sous-carte locale la plus simple consiste à diviser la carte globale en sous-cartes indépendantes comprenant un nombre fixe de marqueurs de caractéristiques sans tenir compte de la relation entre les sous-cartes, et à implémenter le slam dans chaque sous-carte respectivement. La complexité temporelle de cette méthode est O (1). Cependant, en raison de la perte d’informations utiles représentant la corrélation entre les différentes sous-cartes, cette méthode ne peut garantir la cohérence globale de la carte. À cet égard, Leonard et al. Méthode DSM (cartographie stochastique découplée) proposée. Chaque sous-carte dans DSM enregistre sa propre estimation de la position du robot. Lorsque le robot entre dans une autre sous-carte B à partir d'une sous-carte a, la méthode basée sur EKF est utilisée pour transmettre les informations de la sous-carte a à la sous-carte B ; B. Williams et coll. Proposition d'une méthode de slam basée sur CLSF (filtre de sous-carte locale contrainte). CLSF crée une sous-carte avec des coordonnées globales connues dans la carte. Pendant la progression du robot, seules les informations d'observation sont utilisées pour mettre à jour la position des marques caractéristiques dans le robot et la sous-carte locale, et les informations de la sous-carte locale sont transmises à la carte globale à un certain intervalle de temps. Bien que les expériences montrent que les deux algorithmes ont de bonnes performances, il n’a pas été prouvé théoriquement qu’ils pouvaient maintenir la cohérence des cartes. J. Guivant et al. Proposition d'un algorithme d'optimisation de slam cekf (filtre de Kalman étendu compressé) sans aucune perte d'information. Cekf divise les marques de caractéristiques observées en parties A et B. A représente la zone adjacente à la position actuelle du robot, appelée sous-carte active. Lorsque le robot se déplace dans la sous-carte active a, la position du robot et la sous-carte a sont mises à jour en temps réel à l'aide des informations d'observation, et l'influence des informations d'observation sur la sous-carte B est enregistrée par un procédé récursif ; Lorsque le robot quitte la sous-carte active a, les informations d'observation sont transmises à la sous-carte B sans perte, de manière à mettre à jour la sous-carte B en même temps et à créer une nouvelle sous-carte active en même temps. Le temps de calcul de cette méthode se compose de deux parties : le claquement dans la sous-carte d'activité, dont la complexité temporelle est O (), qui est le nombre de marques caractéristiques dans la sous-carte d'activité a ; La complexité temporelle de la mise à jour de la sous-carte B est O (), qui correspond au nombre de marques de caractéristiques dans la carte B. Lorsque l'intervalle de temps de fusion des sous-cartes est grand, cekf peut réduire efficacement la quantité de calcul de claquement.3.3 méthode de décorrélation Une autre façon de réduire la complexité du slam consiste à ignorer certains éléments avec des valeurs plus petites dans la matrice de covariance représentant la relation de corrélation et à la transformer en une matrice clairsemée. Cependant, la cohérence de la carte sera également perdue en raison de la perte d’informations. Cependant, si la représentation de la matrice de covariance peut être modifiée de manière à ce que plusieurs de ses éléments soient proches ou égaux à zéro, elle peut être ignorée en toute sécurité. SLAM Based on Extended Information Filter (EIF) est basé sur cette idée. EIF est l’expression informationnelle d’EKF. La différence entre eux est qu’ils représentent les informations sous différentes formes. EIF utilise la matrice inverse de la matrice de covariance pour représenter les informations incertaines en slam, appelée matrice d'information. La fusion de deux matrices d’informations indépendantes peut être simplement exprimée comme l’addition de deux matrices. Chaque élément non diagonal dans la matrice d'informations représente une relation de contrainte entre le robot et la marque caractéristique ou entre la marque caractéristique et la marque caractéristique. Ces relations de contraintes peuvent être mises à jour localement via la relation de signal de l'état du système. Cette mise à jour locale rend la matrice d'informations proche de la matrice clairsemée, et l'erreur provoquée par son amincissement est très faible. Selon cela, S. Thrun et al. Proposition d'une méthode de slam basée sur un filtre d'informations clairsemées seif (filtre d'informations étendues clairsemées) et prouvé que la complexité temporelle du slam utilisant une matrice d'informations clairsemées est O (1). Bien que l'EIF puisse réduire efficacement la complexité temporelle du slam, certains problèmes subsistent dans la représentation et la gestion des informations cartographiques. Premièrement, la valeur moyenne de l’état du système ne peut être calculée qu’approximativement en temps constant ; Deuxièmement, dans la méthode slam basée sur EIF, l'ajout et la suppression de marques de caractéristiques ne sont pas pratiques.
Le robot commence à se déplacer depuis une position inconnue dans un environnement inconnu. En cours de déplacement, il se localise en fonction de l'estimation de position et des données du capteur, et améliore et construit progressivement une carte complète. C’est un processus de claquement. En slam, le robot utilise son propre capteur pour identifier la marque caractéristique dans un environnement inconnu, puis estime les coordonnées globales du robot et de la marque caractéristique en fonction de la position relative entre le robot et la marque caractéristique et de la lecture du compteur kilométrique. Ce positionnement en ligne et cette création de carte doivent conserver les informations détaillées entre le robot et la marque caractéristique. Ces dernières années, la recherche sur le slam a fait de grands progrès et a été appliquée à divers environnements, tels que les robots, AR, VR, UAV, pilote automatique, etc.2. Les enjeux clés du chelem 2.1 représentation de la carte À l'heure actuelle, les méthodes courantes de représentation cartographique peuvent être grossièrement divisées en trois catégories : la représentation en grille, la représentation d'informations géométriques et la représentation topologique. Chaque méthode a ses propres avantages et inconvénients. (1) Carte d'informations géométriques La représentation cartographique d'informations géométriques signifie que le robot collecte les informations de perception de l'environnement, extrait des caractéristiques géométriques plus abstraites, telles que des segments de ligne ou des courbes, et utilise ces informations géométriques pour décrire l'environnement. avantage : il est plus compact et pratique pour l'estimation de position et la reconnaissance de cibles ; La méthode géométrique utilise le filtre de Kalman pour obtenir une grande précision et une faible quantité de calculs dans la zone locale ; Inconvénients : L'extraction d'informations géométriques nécessite un traitement supplémentaire d'informations perceptuelles, et une certaine quantité de données perceptuelles est nécessaire pour obtenir les résultats ; Il est difficile de conserver des informations de coordonnées précises dans un environnement étendu ; (2) Carte quadrillée La carte quadrillée consiste à diviser l'ensemble de l'environnement en plusieurs grilles de même taille et à indiquer s'il y a des obstacles pour chaque grille. avantage : facile à créer et à maintenir, et essayer de conserver toutes sortes d'informations sur l'ensemble de l'environnement ; À l'aide de la carte, l'auto-positionnement et la planification du chemin peuvent être effectués facilement ; Inconvénients : Lorsque le nombre de grilles augmente (dans un environnement à grande échelle ou lorsque l'environnement est divisé en détail), il deviendra difficile de maintenir la carte. Dans le même temps, il existe un grand espace de recherche dans le processus de positionnement. Sans un bon algorithme simplifié, il est difficile de réaliser une application en temps réel. (3) Carte topologique Les cartes topologiques sont très abstraites, surtout lorsque l'environnement est vaste et simple. Dans cette méthode, l'environnement est représenté sous forme de graphe au sens de topologie, et les nœuds du graphe correspondent à un état et un emplacement caractéristiques dans l'environnement. S'il existe un chemin de connexion direct entre les nœuds, cela équivaut aux nœuds de connexion en arc sur la figure. avantage : Propice à une planification ultérieure du chemin et des tâches ; L'espace de stockage et de recherche est relativement petit et l'efficacité informatique est élevée ; De nombreux algorithmes de recherche et de raisonnement matures et efficaces peuvent être utilisés ; Inconvénients : lors de son utilisation, il doit être basé sur l'identification et la correspondance des nœuds topologiques. Par exemple, lorsqu'il y a deux endroits très similaires dans l'environnement, il sera difficile pour la méthode de carte topologique de déterminer s'il s'agit du même point ;2.2 description des informations incertaines Lorsque l'environnement est complètement inconnu, si le robot veut construire une carte et marcher, il doit obtenir des informations à l'aide d'autres capteurs, tels qu'un odomètre, un sonar, un télémètre laser, une vision, etc. En raison des limites du capteur lui-même, il existe différents degrés d'incertitude dans les informations de détection. Par exemple, l'incertitude du télémètre laser provient principalement de l'erreur de mesure de la distance et de l'erreur d'angle de mesure provoquée par la rotation du réflecteur et la diffusion laser. Comme le montre la figure ci-dessus, l'incertitude des informations perçues conduira inévitablement à l'impossibilité que le modèle d'environnement construit soit complètement précis. De même, lorsque l’on prend des décisions basées sur un modèle et une perception, il existe une incertitude, c’est-à-dire que l’incertitude est transitive. Les méthodes permettant de mesurer l'incertitude comprennent principalement la mesure de la probabilité, la mesure de la confiance, la mesure des possibilités, la mesure floue et la théorie des preuves. À l’heure actuelle, les mesures de probabilité et les mesures floues sont largement utilisées dans la construction de cartes AMR. Il existe deux formes principales de mesure de probabilité : (1) Les informations incertaines sont décrites par des caractéristiques de probabilité telles que la moyenne, la variance et la covariance. L'avantage de cette méthode de mesure est que les caractéristiques de probabilité telles que la moyenne ont une signification géométrique claire, mais l'inconvénient est que la formule de calcul discrète des caractéristiques de probabilité n'a pas été déterminée ; (2) Le modèle de probabilité est utilisé pour décrire des informations incertaines, principalement en utilisant la règle de Bayes et l'hypothèse de Markov. L'avantage de cette méthode de mesure est que la position, l'attitude et les informations environnementales du robot sont décrites par le modèle de probabilité aléatoire et que la robustesse est très bonne. L'inconvénient est que la quantité de calcul du modèle probabiliste est très importante et que la probabilité a priori du modèle doit être connue à l'avance, ce qui rend son application pratique difficile.2.3 Extraction de localisation et de caractéristiques environnementales L'autolocalisation des robots mobiles est étroitement liée à la modélisation environnementale. La précision du modèle d'environnement dépend de la précision du positionnement, et la mise en œuvre du positionnement est indissociable du modèle d'environnement. Dans un environnement inconnu, le robot n'a aucune référence et ne peut s'appuyer que sur ses propres capteurs imprécis pour obtenir des informations externes, tout comme un aveugle tâtonnant dans un environnement inconnu. Dans ce cas, le positionnement est difficile. Le positionnement sur carte et la création de carte avec positionnement sont faciles à résoudre, mais le positionnement sans carte et la création de carte sans positionnement sont comme le problème de « l'œuf de poule ». Dans les recherches existantes, les solutions à de tels problèmes peuvent être divisées en deux catégories : (1) Tout en s'appuyant sur des capteurs internes pour estimer leur propre mouvement, des capteurs externes (tels qu'un télémètre laser, une vision, etc.) sont utilisés pour percevoir l'environnement. , analysez les informations obtenues, extrayez les caractéristiques environnementales et enregistrez-les. À l'étape suivante, leur propre position est corrigée en comparant les caractéristiques environnementales. Mais cette méthode dépend de la capacité à obtenir des caractéristiques environnementales. (2) En utilisant une variété de capteurs internes (y compris un odomètre, une boussole, un accéléromètre, etc.) portés par lui-même, l'erreur de positionnement est réduite grâce à la fusion d'une variété d'informations de capteur. La plupart des algorithmes de fusion utilisés sont basés sur le filtre de Kalman. Étant donné que ces méthodes ne font pas référence à des informations externes, l'accumulation d'erreurs sera importante après une itinérance de longue durée. Les méthodes d'extraction de caractéristiques environnementales comprennent : 1) . La transformation de Hough est une sorte de méthode pour détecter des lignes et autres courbes basées sur une image grise. Cette méthode nécessite un groupe de courbes spécifiques pré-préparées qui peuvent être recherchées et génère des paramètres de courbe en fonction d'un groupe de courbes dans l'image grise affichée. 2) . L'analyse de regroupement est un outil de détection de données efficace pour les échantillons non classés. Dans le même temps, son objectif est de diviser les objets ciblés en catégories naturelles ou classes de clusters en fonction de la similitude ou de la distance. Lorsque la catégorie de l'objet extrait est inconnue, la technologie de clustering est une technologie plus efficace que houghtransform. Les classes groupées devraient être centrées sur la « cohésion », plutôt que fragmentées et disjointes. Les caractéristiques environnementales sont parfois difficiles à extraire. Par exemple, lorsque les caractéristiques environnementales ne sont pas suffisamment évidentes ou qu’il existe peu d’informations provenant des capteurs, il est difficile d’obtenir des caractéristiques environnementales à partir d’informations de perception ponctuelles.2.4 Association de données L'association de données consiste à faire correspondre deux marques caractéristiques pour déterminer si elles correspondent au même objet dans l'environnement. L'association de données en slam doit principalement accomplir trois tâches : (1) Correspondance entre les cartes ; (2) Correspondance des marques caractéristiques ; (3) Détection de nouvelles marques de caractéristiques ; Bien que l'association de données ait été bien résolue dans les domaines du suivi de cibles et de la fusion de capteurs, ces méthodes nécessitent une grande quantité de calcul et ne peuvent pas répondre aux exigences en temps réel du slam. La complexité d'association des données entre M signes et cartes à n signes est exponentielle avec M. en supposant que chaque signe observé I ait une correspondance possible, pour M signes, il faut rechercher la bonne correspondance dans l'espace exponentiel =. L'espace de recherche d'association de données est lié à la complexité de l'environnement et à l'erreur de positionnement du robot. L’augmentation de la complexité de l’environnement augmentera m, et l’augmentation de l’erreur augmentera Ni.2,5 erreur cumulée Les erreurs en slam proviennent principalement de trois aspects : (1) erreur d'observation ; (2) Erreur du compteur kilométrique ; (3) Erreurs causées par une association de données incorrecte ; Lorsque le robot se localise dans l'environnement d'une carte connue, le robot peut compenser l'erreur de l'odomètre en observant la marque caractéristique avec une position connue. Chaque observation fait tendre l'erreur de position du robot vers la somme de l'erreur d'observation et de l'erreur de position de la marque caractéristique. Cependant, en slam, comme la position du robot et la position de la marque caractéristique dans l'environnement sont inconnues, les informations d'observation ne peuvent pas corriger efficacement l'erreur de l'odomètre et l'erreur de position du robot augmente avec la distance de déplacement de le robot. L'augmentation de l'erreur de position du robot entraînera une mauvaise association de données, ce qui augmentera l'erreur de position de la marque caractéristique ; à son tour, l’erreur de la marque caractéristique augmentera l’erreur de position du robot. Par conséquent, l’erreur de position du robot est étroitement liée à l’erreur de position de la marque caractéristique. L'interaction entre eux fait que l'estimation de la position du robot et la marque caractéristique produisent une erreur cumulative, ce qui est difficile à garantir la cohérence de la carte. 3. Méthode de mise en œuvre du slam À l'heure actuelle, les méthodes de slam peuvent être grossièrement divisées en deux catégories : (1) Méthodes basées sur un modèle probabiliste : slam complet basé sur un filtre de Kalman, un filtre de compression, FastSLAM, etc. (2) Méthodes de modèle non probabiliste : sm -slam, scan matching, association de données, basé sur la logique floue, etc.Méthode d'implémentation 3.1 basée sur le filtre de Kalman Du point de vue statistique, le slam est un problème de filtrage, c'est-à-dire estimer l'état actuel du système en fonction de l'état initial du système et des informations d'observation et de contrôle (lecture du compteur kilométrique) de 0 à t. En slam, l'état du système est composé de la pose du robot R et des informations cartographiques m (y compris les informations de position de chaque marque caractéristique). En supposant que le modèle de mouvement et le modèle d'observation du système sont des modèles linéaires avec un bruit gaussien et que l'état du système obéit à la distribution gaussienne, le claquement peut être réalisé par le filtre de Kalman. Le filtre SLAM basé sur Kalman comprend deux étapes : la prédiction et la mise à jour de l'état du système. Dans le même temps, il doit également gérer les informations cartographiques, telles que l'ajout de nouveaux repères caractéristiques et la suppression de repères caractéristiques. Le filtre de Kalman suppose que le système est un système linéaire, mais en pratique, le modèle de mouvement et le modèle d'observation du robot sont non linéaires. Par conséquent, le filtre de Kalman étendu est généralement utilisé. Le filtre de Kalman étendu représente approximativement le modèle non linéaire via le développement de Taylor du premier ordre. Un autre filtre Kalman adapté aux modèles non linéaires est l'UKF (filtre Kalman non parfumé). UKF utilise la distribution gaussienne conditionnelle pour approximer la distribution de probabilité a posteriori. Comparé à l'EKF, l'UKF a une précision de linéarisation plus élevée et n'a pas besoin de calculer la matrice jacobienne. Le filtre de Kalman est devenu la méthode de base pour réaliser le slam. Sa matrice de covariance contient les informations incertaines sur la position et la carte du robot. Lorsque le robot observe en permanence les signes caractéristiques de l'environnement, le déterminant de toute sous-matrice de la matrice de covariance diminue de façon monotone. Théoriquement, lorsque le nombre d'observations tend vers l'infini, la covariance de chaque marque caractéristique n'est liée qu'à la covariance de la position de départ du robot. La complexité temporelle du filtre de Kalman est O (). Étant donné que le robot ne peut observer que quelques marques de caractéristiques à chaque fois, la complexité temporelle du SLAM basé sur le filtre de Kalman peut être optimisée comme O (), et N représente le nombre de marques de caractéristiques sur la carte.3.2 Méthode de sous-carte locale La méthode des sous-cartes locales décompose le slam en sous-problèmes plus petits du point de vue de l'espace. Les problèmes suivants doivent être pris en compte dans la méthode des sous-cartes : (1) Comment diviser les sous-cartes ; (2) Comment représenter la relation entre les sous-cartes ; (3) Comment transférer les informations de la sous-carte vers la carte globale et si la cohérence de la carte globale peut être garantie ; La méthode de sous-carte locale la plus simple consiste à diviser la carte globale en sous-cartes indépendantes comprenant un nombre fixe de marqueurs de caractéristiques sans tenir compte de la relation entre les sous-cartes, et à implémenter le slam dans chaque sous-carte respectivement. La complexité temporelle de cette méthode est O (1). Cependant, en raison de la perte d’informations utiles représentant la corrélation entre les différentes sous-cartes, cette méthode ne peut garantir la cohérence globale de la carte. À cet égard, Leonard et al. Méthode DSM (cartographie stochastique découplée) proposée. Chaque sous-carte dans DSM enregistre sa propre estimation de la position du robot. Lorsque le robot entre dans une autre sous-carte B à partir d'une sous-carte a, la méthode basée sur EKF est utilisée pour transmettre les informations de la sous-carte a à la sous-carte B ; B. Williams et coll. Proposition d'une méthode de slam basée sur CLSF (filtre de sous-carte locale contrainte). CLSF crée une sous-carte avec des coordonnées globales connues dans la carte. Pendant la progression du robot, seules les informations d'observation sont utilisées pour mettre à jour la position des marques caractéristiques dans le robot et la sous-carte locale, et les informations de la sous-carte locale sont transmises à la carte globale à un certain intervalle de temps. Bien que les expériences montrent que les deux algorithmes ont de bonnes performances, il n’a pas été prouvé théoriquement qu’ils pouvaient maintenir la cohérence des cartes. J. Guivant et al. Proposition d'un algorithme d'optimisation de slam cekf (filtre de Kalman étendu compressé) sans aucune perte d'information. Cekf divise les marques de caractéristiques observées en parties A et B. A représente la zone adjacente à la position actuelle du robot, appelée sous-carte active. Lorsque le robot se déplace dans la sous-carte active a, la position du robot et la sous-carte a sont mises à jour en temps réel à l'aide des informations d'observation, et l'influence des informations d'observation sur la sous-carte B est enregistrée par un procédé récursif ; Lorsque le robot quitte la sous-carte active a, les informations d'observation sont transmises à la sous-carte B sans perte, de manière à mettre à jour la sous-carte B en même temps et à créer une nouvelle sous-carte active en même temps. Le temps de calcul de cette méthode se compose de deux parties : le claquement dans la sous-carte d'activité, dont la complexité temporelle est O (), qui est le nombre de marques caractéristiques dans la sous-carte d'activité a ; La complexité temporelle de la mise à jour de la sous-carte B est O (), qui correspond au nombre de marques de caractéristiques dans la carte B. Lorsque l'intervalle de temps de fusion des sous-cartes est grand, cekf peut réduire efficacement la quantité de calcul de claquement.3.3 méthode de décorrélation Une autre façon de réduire la complexité du slam consiste à ignorer certains éléments avec des valeurs plus petites dans la matrice de covariance représentant la relation de corrélation et à la transformer en une matrice clairsemée. Cependant, la cohérence de la carte sera également perdue en raison de la perte d’informations. Cependant, si la représentation de la matrice de covariance peut être modifiée de manière à ce que plusieurs de ses éléments soient proches ou égaux à zéro, elle peut être ignorée en toute sécurité. SLAM Based on Extended Information Filter (EIF) est basé sur cette idée. EIF est l’expression informationnelle d’EKF. La différence entre eux est qu’ils représentent les informations sous différentes formes. EIF utilise la matrice inverse de la matrice de covariance pour représenter les informations incertaines en slam, appelée matrice d'information. La fusion de deux matrices d’informations indépendantes peut être simplement exprimée comme l’addition de deux matrices. Chaque élément non diagonal dans la matrice d'informations représente une relation de contrainte entre le robot et la marque caractéristique ou entre la marque caractéristique et la marque caractéristique. Ces relations de contraintes peuvent être mises à jour localement via la relation de signal de l'état du système. Cette mise à jour locale rend la matrice d'informations proche de la matrice clairsemée, et l'erreur provoquée par son amincissement est très faible. Selon cela, S. Thrun et al. Proposition d'une méthode de slam basée sur un filtre d'informations clairsemées seif (filtre d'informations étendues clairsemées) et prouvé que la complexité temporelle du slam utilisant une matrice d'informations clairsemées est O (1). Bien que l'EIF puisse réduire efficacement la complexité temporelle du slam, certains problèmes subsistent dans la représentation et la gestion des informations cartographiques. Premièrement, la valeur moyenne de l’état du système ne peut être calculée qu’approximativement en temps constant ; Deuxièmement, dans la méthode slam basée sur EIF, l'ajout et la suppression de marques de caractéristiques ne sont pas pratiques.