Nous publions régulièrement sur notre blog des articles rédigés par les équipes techniques, qui donnent vie à Keecker, dans nos locaux au coeur de Paris. Bonne lecture !

----------------------------------------------------------------------------------------

Algorithmes de Keecker:

Navigation Autonome

 

Pour patrouiller dans votre maison ou se rendre à sa station de charge, Keecker doit connaître sa position exacte et se déplacer en toute sécurité. Cela implique des tâches variées, comme trouver son chemin et comprendre le monde réel perçu par ses capteurs.

La recherche sur ces sujets a commencé il y a plus de cinquante ans, ils sont toujours activement étudiés. Quelque chose est tout de même en train de changer. Le progrès des capteurs développés pour l’industrie du mobile permet aux robots grand public d’intégrer la technologie que l’on trouvait habituellement sur des robots bien plus sophistiqués. Naviguer dans un environnement imprévu n’est plus réservé aux rovers martiens !

 

Pourquoi la navigation autonome est-elle un challenge pour Keecker?

 

Bien que cela vous semble simple de trouver votre chemin dans une maison ou des bureaux, la tâche est plus compliquée qu’il n’y parait pour un robot. Elle doit être exprimée de manière analytique, avec des algorithmes. Comme nous n’avons pas l’habitude de réfléchir à la manière dont nous nous déplaçons, ce n’est pas si naturel d’expliquer comment faire à un robot.

Des méthodes robustes ont été développées pour l’industrie, mais elles impliquent des environnements connus, des conditions contrôlées et une interaction limitée avec des personnes. Pour un robot, sans parler des ressources déployées, se déplacer dans un environnement imprévisible comme une maison ou des bureaux n’est pas un problème complètement résolu.

Explorer un environnement inconnu rappelle le problème de l’oeuf et la poule. Pour construire la carte, il faut savoir où l’on se trouve pour enregistrer les données des capteurs. Mais pour savoir où l’on se trouve, il faut une représentation de l’environnement dans laquelle on peut se localiser.

Keecker doit trouver son chemin, que ce soit en plein soleil ou pendant la nuit avec d’éventuels tapis et chaises sur son passage. Bien que ces variations soient un problème, elles représentent aussi une opportunité très intéressante. Rencontrer ces situations variées permettra à Keecker de s’améliorer bien plus que les robots cantonnés dans les usines et entrepôts.

 

Perception

 

Commençons par une rapide présentation des capteurs embarqués dans Keecker.

  • Une caméra couleur pour voir vers l’avant. Les mesures dépendent de l’éclairage, elles varient donc en permanence au cours de la journée.

  • Une caméra couleur à 360° sur le dessus, pour voir tout autour.

  • Une caméra de profondeur dirigée vers l’avant. Au lieu de mesurer une couleur, chaque pixel mesure une distance en fonction du temps mis par une lumière projetée pour revenir. Il peut ainsi percevoir des obstacles à quelques mètres, mais les mesures peuvent être fausses sur des surfaces un peu transparentes, réfléchissantes ou éclairées par le soleil.

  • Des capteurs de proximité tout autour, détectant les obstacles à quelques centimètres de distance.

  • Des encodeurs magnétiques, qui mesurent la rotation des deux roues motrices. La source d’erreur la plus importante est le glissement des roues sur le sol.

  • Une IMU (ou Matrice inertielle) composée d’un accéléromètre, d’un gyromètre et d’un magnétomètre.

Étonnement, tous ces capteurs ont été développés pour des téléphones mobiles haut de gamme, mais peuvent être détournés de leur fonction principale. Les prochaines sections montrent comment Keecker les utilise pour la navigation autonome.

 

Planification de mouvement

 

Keecker se déplace avec deux roues motrices. En contrôlant la vitesse de chacune indépendamment, il peut aller en ligne droite, trouver sur lui même ou suivre une trajectoire circulaire.

La planification de mouvements consiste à trouver comment enchainer ces éléments de trajectoire pour atteindre une destination donnée, en évitant les obstacles en cours de route.

Planifier un chemin optimal en considérant chaque conséquence possible de chaque commande possible étant donné chaque lecture de capteur possible serait trop complexe — bien trop long à calculer par Keecker pour être utile. Dans notre cas, trouver la solution optimale n’est de toute façon pas très important, nous voulons juste trouver un chemin suffisamment bon. Ceci nous permet d’apporter quelques simplifications au problème.

Tout d’abord, les données de la caméra de profondeur et des capteurs de proximité sont projetées sur une carte à deux dimensions, appelée grille d’occupation. Cela réduit la quantité de données à analyser par les algorithmes de planification. Cette représentation sert aussi à se souvenir des obstacles que l’on ne voit plus, mais qui sont surement toujours là.

Une grille d’occupation en deux dimensions intégrant des obstacles du monde réel perçus par la caméra de profondeur et les capteurs de proximité. Keecker est représenté par la forme jaune, il est autorisé à se déplacer sur les cases claires et ne peut aller sur les cases noires.

 

À partir de cette grille d’occupation, nous utilisons un algorithme appelé A* pour calculer un chemin grossier à suivre. Ce chemin tient compte des obstacles, mais ne tient pas compte des commandes qui seront nécessaires pour le suivre.

Le problème restant est donc de générer les commandes pour suivre ce chemin de façon naturelle, tout en évitant les obstacles imprévus. Dix fois par seconde, nous tirons au sort un ensemble de commandes possibles, en fonction de la vitesse actuelle. Pour chacune de ces commandes, nous simulons ce qui arriverait dans les prochaines secondes si on l’exécutait. Nous sélectionnons celle qui suivrait au mieux le chemin tout en restant assez loin des obstacles.

  • Le chemin grossier évitant les obstacles est affiché en grid clair.

  • La destination est indiquée par la flèche au bout du chemin.

  • Les commandes tirées au sort, simulées par Keecker sont représentées en bleu.

  • La ligne en pointillé montre celle qui progresse le mieux sur le chemin sans trop s’approcher des obstacles.

Cette commande sélectionnée est finalement envoyée à un microcontrôleur dédié. De cette manière, elle peut être exécutée précisément même si le processeur principal est utilisé par une autre application. Les capteurs de proximités sont lus en temps réel par ce microcontrôleur, pour éviter les obstacles non perçus lorsque la commande a été planifiée.

 

Localisation et cartographie

 

Pour savoir où est chaque pièce et trouver un chemin, Keecker a besoin de construire une représentation de l’environnement. Les roboticiens appellent ce problème le SLAM (Simultaneous Localization And Mapping), parce que, dans un environnement inconnu, les deux doivent être faits en même temps. Le problème est de construire une carte utilisable à partir de capteurs qui ne sont pas toujours fiables.

Une première sorte d’information est appelée position relative. Elle indique la quantité de déplacement, indépendamment de l’environnement alentour. C’est l’information que vous auriez en marchant, sans rien voir, entendre, ni toucher. Ces capteurs donnent constamment une information précise :

  • La vitesse des roues mesurée par les encodeurs peut donner une assez bonne estimation du déplacement.

  • Les vitesses angulaires mesurées par le gyromètre peuvent être intégrées pour estimer une rotation.

  • Les accélérations linéaires mesurées par l’accéléromètre peuvent être utilisées pour détecter des chocs, indiquant que les autres données peuvent être erronées.

  • En faisant correspondre deux nuages de points consécutifs acquis par la caméra de profondeur, on peut estimer le déplacement effectué entre les deux.

Au cours du temps, de petites erreurs dans ces mesures aboutissent à une erreur importante de la position estimée. Pour corriger cette erreur accumulée, nous avons aussi besoin d’informations de position absolue, indiquant une position précise dans un environnement. Elle peut être déduite à partir de points de repères et de caractéristiques de l’environnement que l’on suppose stable au cours du temps.

  • Les points de repère sont des endroits que l’on peut identifier avec assurance, comme la station de charge.

  • Les caractéristiques ne sont pas suffisantes pour identifier un endroit, mais donnent une indication. Cela peut être un obstacle qui ressemble à un mur ou un meuble, la puissance des signaux Wi-Fi aux alentours ou le champ magnétique terrestre.

Un exemple de représentation interne construite par Keecker. Elle montre les obstacles et leur caractéristique: mur (noir), meuble (rouge), choses plus basses (gris clair) et zones inconnues (gris foncé). Cette représentation intègre d’autres informations non représentées ici, comme les signaux Wi-Fi et le champ magnétique.

 

Toutes ces informations sont bruitées et ne sont pas complètement sûres. Des méthodes probabilistes sont souvent utilisées pour les fusionner en fonction de leur fiabilité. Keecker utilise un algorithme appelé filtre à particule :

  1. Disons que Keecker est dans un environnement inconnu et que vous venez de lancer une cartographie.

  2. Keecker commence à une position initiale arbitraire et une carte vide. C’est notre première particule. Elle transporte une carte et une position par rapport à cette carte. La carte et la position sont toutes les deux des hypothèses à propos de la situation réelle.

  3. Pour chaque particule, enregistrer les caractéristiques disponibles dans la carte: les obstacles, signaux Wi-Fi et le champ magnétique.

  4. Après s’être un peu déplacé, pour chaque particule, utiliser les informations de position relative pour imaginer de nouvelles situations possibles. Keecker va par exemple créer plusieurs particules à partir de la même carte, en déplaçant la position en fonction de l’erreur supposée sur le déplacement mesuré par les roues.

  5. Pour chaque particule, calculer un score en fonction de la correspondance entre les nouvelles caractéristiques perçues et celles qui étaient déjà enregistrées dans la carte.

  6. Garder les meilleures particules, oublier les autres.

  7. Répéter à partir de l’étape (3.).

Le nombre et l’étalement des particules à un moment donné dépendent de la confiance de Keecker dans ses suppositions. Il utilise la particule ayant le meilleur score comme sa meilleure représentation de la situation réelle.

À la fin de la cartographie, nous utilisons ce qui est appelé un algorithme de fermeture de boucle pour faire correspondre les points de repère qui ne sont pas souvent vus, comme la station de charge.

 

Et la suite ?

 

Ces algorithmes tournent en ce moment sur chaque Keecker. En fonction de leur performance en conditions réelles, nous développons les prochaines mises à jour logicielles pour améliorer la compréhension de l’environnement par Keecker.

La cartographie en continu. Pour l’instant, l’algorithme de SLAM ne tourne qu’une fois pendant la cartographie. Cette carte est ensuite utilisée par une version simplifiée de l’algorithme pour la localisation. Nous sommes en train de travailler sur la cartographie en continu pour intégrer les changements de l’environnement en permanence. Cela permettra aussi à Keecker d’ajouter des informations non disponibles au moment de la cartographie comme les zones souvent obstruées qui devraient être évitées.

SLAM visuel. La caméra couleur n’est pas encore utilisée pour la cartographie et la localisation, principalement parce que l’algorithme doit aussi fonctionner dans le noir. Quand elle est disponible, l’information visuelle est portant très utile, nous sommes en train de développer des algorithmes capables de reconnaitre des points de repère.

Si vous avez une question ou des idées à propos de Keecker et de la robotique grand public, n’hésitez pas à contacter notre équipe support. Si vous êtes intéressés pour développer les prochaines itérations, nous recrutons !