Découvrez notre Chaîne YouTube "Ingénierie et Projets"
Découvrez notre Chaîne Secondaire "Information Neuronale et l'Ingénierie du Cerveau"

Titre: Algorithmes SLAM (Simultaneous Localization et Mapping): Vers une Implémentation Embarquée

Auteurs: M. ABOUZAHIR MOHAMED

Ecole/Université: Université Paris Sud

Résumé: La navigation autonome est un axe de recherche principal dans le domaine de la robotique mobile. Dans ce contexte, le robot doit disposer des algorithmes qui lui permettent d’évoluer de manière autonome dans des environnements complexes et inconnus. Les algorithmes de SLAM (Simultaneous Localization et Mapping) permettent à un robot de cartographier son environnement tout en se localisant dans l’espace. Les algorithmes SLAM sont de plus en plus performants, mais aucune implémentation matérielle ou architecturale complète n’a eu lieu.

Une telle implantation d’architecture doit prendre en considération la consommation d’énergie, l’embarquabilité et la puissance de calcul. Ce travail scientifique vise à évaluer des systèmes SLAM embarqués. La méthodologie adoptera une approche A3 (Adéquation Algorithme Architecture) pour améliorer l’efficacité de l’implantation des algorithmes. Le système SLAM embarqué doit disposer d’une architecture électronique et logicielle permettant d’assurer la production d’information pertinentes à partir de données capteurs, tout en assurant la localisation de l’embarquant dans son environnement. Les premiers travaux de cette thèse ont consisté à explorer les différentes approches algorithmiques permettant la résolution du problème de SLAM. Cette étude, nous a permet d’évaluer quatre algorithmes de différente nature: FastSLAM2.0, ORB SLAM, RatSLAM et le SLAM linéaire.

Ces algorithmes ont été ensuite évalués sur plusieurs architectures pour l’embarqué afin d’étudier leur portabilité sur des systèmes de faible consommation énergétique et de ressources limitées. Après avoir analysé profondément les évaluations temporelles de chaque algorithme, le FastSLAM2.0 est finalement choisi, pour un compromis temps d’exécution-consistance de résultat de localisation, comme candidat pour une étude plus approfondie sur une architecture hétérogène embarquée.

La seconde partie de cette thèse est consacré à l’étude d’un système embarqué implémentant le FastSLAM2.0 monoculaire dédié aux environnements larges. Une réécriture algorithmique du FastSLAM2.0 a été nécessaire afin de l’adapter au mieux aux contraintes imposées par les environnements de grande échelle. Dans une démarche A3, le FastSLAM2.0 a été implanté sur une architecture hétérogène CPU-GPU. Grâce à un partitionnement efficace, un facteur d’accélération global de l’ordre de 22 a été obtenu sur une architecture récente dédiée pour l’embarqué. Une deuxième instance matérielle basée sur une architecture programmable FG est proposée. Les gains obtenus sont conséquent, même par rapport aux GPU haut-de-gamme qui disposent actuellement d’un grand nombre de ceours. Le système résultant peut cartographier des environnements larges tout en garantissant le compromis entre la consistance des résultats de localisation et le temps réel. Ces travaux de thèse ont permis de mettre en avant l’intérêt des architectures hétérogènes parallèles (multicoeurs-GPU) pour le portage des algorithmes SLAM. Les architectures hétérogènes à base du FPGA peuvent particulièrement devenir des candidats potentiels pour porter des algorithmes complexes traitant des données massives.

Extrait du sommaire:

1 Algorithmes SLAM et architectures dédiées : état de l’art 7
1.1 Localisation et cartographie simultanées 8
1.2 Nécessité du SLAM pour la navigation autonome 9
1.3 Le problème SLAM est-il résolu ? 10
1.4 Formalisation d’un système de SLAM moderne 11
1.4.1 Phase d’acquisition des données capteurs 12
1.4.2 Phase de prétraitement : 12
1.4.3 Coeur SLAM 17
1.5 Résolution du SLAM 19
1.5.1 L’approche probabiliste 19
1.5.2 Approche de structuration à partir du mouvement 20
1.5.3 Approche bio-inspirée 21
1.6 Architectures de calcul embarqué pour le SLAM 21
1.7 Synthèse 22
1.8 Conclusion 23
2 Méthodologie d’évaluation et de conception 27
2.1 Introduction 28
2.2 Adéquation Algorithme Architecture : Application au SLAM 28
2.2.1 Modèle et spécifications algorithmiques 29
2.2.2 Factorisation algorithmique 30
2.2.3 Modèle Architecturale 31
2.2.4 Modèle d’implémentation 32
2.2.5 Transformation de graphe et adéquation 33
2.3 Outils de Prototypage et méthodologie d’évaluation 33
2.3.1 Outils de simulation 33
2.3.2 Données Expérimentales 35
2.3.3 Validation Hardware In the Loop 37
2.3.4 Critères d’évaluation 39
2.3.5 Évaluation des temps d’exécution 40
2.4 Outils de développement et de conception 41
2.4.1 Optimisation logicielle sur architectures multicoeurs 41
2.4.2 Calcul sur GPU 41
2.4.3 Outils de synthèse et de conception sur FPGA 43
2.5 Bilan 44
3 Étude algorithmique et choix des architectures 46
3.1 Introduction 48
3.2 Prétraitement des données capteurs 48
3.2.1 Extraction des amers 48
3.2.2 Appariement des amers 49
3.2.3 Étape d’initialisation 49
3.3 Algorithme FastSLAM2.0 50
3.3.1 Approche de l’indépendance conditionnelle 50
3.3.2 Structure de données 50
3.3.3 Échantillonnage des particules 50
3.3.4 Mise à jour de la position des particules 51
3.3.5 Estimation des amers 51
3.3.6 Gestion de la carte et représentation par arbre binaire 51
3.3.7 Rééchantillonnage 52
3.4 Algorithme ORB SLAM 52
3.4.1 Présentation du système 52
3.4.2 Tâche de suivi 54
3.4.3 Cartographie locale 55
3.4.4 Fermeture de boucle 56
3.5 Algorithme Bio-inspiré : RatSLAM 56
3.5.1 L’architecture du RatSLAM 57
3.5.2 La dynamique du RatSLAM 58
3.6 Le SLAM Linéaire 61
3.6.1 Structure des cartes locales 61
3.6.2 Principe de fusion de deux cartes locales 61
3.6.3 Fusion d’une séquence de cartes locales 62
3.7 Évaluation de l’aspect fonctionnel des algorithmes 64
3.8 Découpage en blocs fonctionnels 65
3.9 Choix des architectures et évaluation temporelle 68
3.9.1 Choix des architectures 68
3.9.2 Évaluation des temps d’exécution 70
3.10 Comparaison des performances 74
3.11 Bilan 78
4 FastSLAM2.0 : Vers une implantation embarquée 81
4.1 Introduction 82
4.2 Définition du problème 82
4.3 Analyses des dépendances de l’algorithme 84
4.4 Implémentation sur une architecture multi-coeurs homogène 86
4.4.1 Temps d’exécution global 86
4.4.2 Optimisation parallèle 88
4.4.3 Évaluation des résultats de l’optimisation parallèle 90
4.4.4 Analyses des résultats 91
4.4.5 Évaluation des résultats de cartographie et de localisation 92
4.5 Le FastSLAM2.0 monoculaire à grande échelle 94
4.5.1 Convergence du FastSLAM2.0 94
4.5.2 Convergence de l’incertitude des particules 95
4.5.3 Gestion de rééchantillonnage 96
4.5.4 Évaluation des Résultats de cartographie et de localisation 96
4.6 Implémentation sur une architecture massivement parallèle 97
4.6.1 Choix d’une architecture adaptée 97
4.6.2 Adéquation algorithme architecture 99
4.6.3 Résultats expérimentaux 118
4.7 Accélération matérielle sur une architecture programmable 128
4.7.1 Modèle d’implémentation 128
4.7.2 Conception de haut-niveau par OpenCL 129
4.7.3 Spécifications matérielle 131
4.7.4 Techniques et stratégies d’optimisation 133
4.8 Résultat expérimentaux et comparaison de performance 134
4.9 Bilan 137
5 Conclusion Générale 140
5.1 Conclusion et résumé des contributions 140
5.2 Perspectives 141
6 Références 143
7 Annexes 155
7.1 Annexe A 155
7.1.1 Codeur Optique 155
7.1.2 Télémètre Laser 155
7.2 Annexe B 156
7.2.1 Exemple de factorisation algorithmique 156
7.2.2 Exemple de modélisation architecturale 158
7.2.3 Formalisme mathématique du graphe 159
7.2.4 Formalisation mathématique de la distribution 160
7.2.5 Formalisme mathématique de l’ordonnancement 161
7.3 Annexe C 162
7.3.1 Détection à partir d’un flux Laser 162
7.3.2 Détection des amers par FAST 162
7.3.3 Appariement des amers 163
7.3.4 Initialisation des amers 166
7.3.5 Représentation en arbre binaire 167
7.3.6 Méthode linéaire pour la fusion de deux cartes locales 168
7.3.7 Recherche active des amers dans le système ORB SLAM 171
7.4 Annexe D 172
7.4.1 Intégration de bruit dans la trajectoire odométrique 172
7.4.2 Calcule de la nouvelle distribution probabiliste 172
7.4.3 Estimation et correction des amers 173
7.4.4 Rééchantillonnage 176
7.4.5 Implémentation OpenGL 176
7.4.6 Résultats de comparaison entre l’implémentation OpenCL et OpenGL 179

Cours accélération matérielle (19)

Télécharger le fichier PDF: Algorithmes SLAM (Simultaneous Localization et Mapping): Vers une Implémentation Embarquée

Le blog contient des publicités, elles permettent de financer l'hébergement et maintenir le blog en fonctionnement. Vous pouvez utiliser adblock pour une lecture sans publicités.
We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.
Cookies settings
Accept
Decline
Privacy & Cookie policy
Privacy & Cookies policy
Cookie name Active

Privacy Policy

What information do we collect?

We collect information from you when you register on our site or place an order. When ordering or registering on our site, as appropriate, you may be asked to enter your: name, e-mail address or mailing address.

What do we use your information for?

Any of the information we collect from you may be used in one of the following ways: To personalize your experience (your information helps us to better respond to your individual needs) To improve our website (we continually strive to improve our website offerings based on the information and feedback we receive from you) To improve customer service (your information helps us to more effectively respond to your customer service requests and support needs) To process transactions Your information, whether public or private, will not be sold, exchanged, transferred, or given to any other company for any reason whatsoever, without your consent, other than for the express purpose of delivering the purchased product or service requested. To administer a contest, promotion, survey or other site feature To send periodic emails The email address you provide for order processing, will only be used to send you information and updates pertaining to your order.

How do we protect your information?

We implement a variety of security measures to maintain the safety of your personal information when you place an order or enter, submit, or access your personal information. We offer the use of a secure server. All supplied sensitive/credit information is transmitted via Secure Socket Layer (SSL) technology and then encrypted into our Payment gateway providers database only to be accessible by those authorized with special access rights to such systems, and are required to?keep the information confidential. After a transaction, your private information (credit cards, social security numbers, financials, etc.) will not be kept on file for more than 60 days.

Do we use cookies?

Yes (Cookies are small files that a site or its service provider transfers to your computers hard drive through your Web browser (if you allow) that enables the sites or service providers systems to recognize your browser and capture and remember certain information We use cookies to help us remember and process the items in your shopping cart, understand and save your preferences for future visits, keep track of advertisements and compile aggregate data about site traffic and site interaction so that we can offer better site experiences and tools in the future. We may contract with third-party service providers to assist us in better understanding our site visitors. These service providers are not permitted to use the information collected on our behalf except to help us conduct and improve our business. If you prefer, you can choose to have your computer warn you each time a cookie is being sent, or you can choose to turn off all cookies via your browser settings. Like most websites, if you turn your cookies off, some of our services may not function properly. However, you can still place orders by contacting customer service. Google Analytics We use Google Analytics on our sites for anonymous reporting of site usage and for advertising on the site. If you would like to opt-out of Google Analytics monitoring your behaviour on our sites please use this link (https://tools.google.com/dlpage/gaoptout/)

Do we disclose any information to outside parties?

We do not sell, trade, or otherwise transfer to outside parties your personally identifiable information. This does not include trusted third parties who assist us in operating our website, conducting our business, or servicing you, so long as those parties agree to keep this information confidential. We may also release your information when we believe release is appropriate to comply with the law, enforce our site policies, or protect ours or others rights, property, or safety. However, non-personally identifiable visitor information may be provided to other parties for marketing, advertising, or other uses.

Registration

The minimum information we need to register you is your name, email address and a password. We will ask you more questions for different services, including sales promotions. Unless we say otherwise, you have to answer all the registration questions. We may also ask some other, voluntary questions during registration for certain services (for example, professional networks) so we can gain a clearer understanding of who you are. This also allows us to personalise services for you. To assist us in our marketing, in addition to the data that you provide to us if you register, we may also obtain data from trusted third parties to help us understand what you might be interested in. This ‘profiling’ information is produced from a variety of sources, including publicly available data (such as the electoral roll) or from sources such as surveys and polls where you have given your permission for your data to be shared. You can choose not to have such data shared with the Guardian from these sources by logging into your account and changing the settings in the privacy section. After you have registered, and with your permission, we may send you emails we think may interest you. Newsletters may be personalised based on what you have been reading on theguardian.com. At any time you can decide not to receive these emails and will be able to ‘unsubscribe’. Logging in using social networking credentials If you log-in to our sites using a Facebook log-in, you are granting permission to Facebook to share your user details with us. This will include your name, email address, date of birth and location which will then be used to form a Guardian identity. You can also use your picture from Facebook as part of your profile. This will also allow us and Facebook to share your, networks, user ID and any other information you choose to share according to your Facebook account settings. If you remove the Guardian app from your Facebook settings, we will no longer have access to this information. If you log-in to our sites using a Google log-in, you grant permission to Google to share your user details with us. This will include your name, email address, date of birth, sex and location which we will then use to form a Guardian identity. You may use your picture from Google as part of your profile. This also allows us to share your networks, user ID and any other information you choose to share according to your Google account settings. If you remove the Guardian from your Google settings, we will no longer have access to this information. If you log-in to our sites using a twitter log-in, we receive your avatar (the small picture that appears next to your tweets) and twitter username.

Children’s Online Privacy Protection Act Compliance

We are in compliance with the requirements of COPPA (Childrens Online Privacy Protection Act), we do not collect any information from anyone under 13 years of age. Our website, products and services are all directed to people who are at least 13 years old or older.

Updating your personal information

We offer a ‘My details’ page (also known as Dashboard), where you can update your personal information at any time, and change your marketing preferences. You can get to this page from most pages on the site – simply click on the ‘My details’ link at the top of the screen when you are signed in.

Online Privacy Policy Only

This online privacy policy applies only to information collected through our website and not to information collected offline.

Your Consent

By using our site, you consent to our privacy policy.

Changes to our Privacy Policy

If we decide to change our privacy policy, we will post those changes on this page.
Save settings
Cookies settings

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

FPGA | Arduino | Matlab | Cours will use the information you provide on this form to be in touch with you and to provide updates and marketing.