Les secrets de l’algorithme d’un robot aspirateur…

13 Juil 2018/
-- HIgh Tech
Remerciez l'auteur en lui donnant votre vote ;-) ------>
7 0

Comprendre le cerveau d’un aspirateur robot.

DanyTech n’est pas seulement dédié aux tests de produits High tech, mais essaye aussi de nous éclairer sur le coté obscur de la tech !

Après l’article sur l’aspirateur robot Ilife, nous nous sommes demandé hier avec Nesquick, comment pouvait être conçu le programme et avec quel langage ? J’ai donc fait quelques recherches et suis tombé sur un rapport complet de l’université de Bourgogne qui tente de répondre à la question de ces algorithmes.

Je vais essayer de vous en faire un résumé :

Qu’est ce qu’un algorithme ?

Un algorithme est une suite finie et non ambiguë d’opérations ou d’instructions permettant de résoudre un problème ou d’obtenir un résultat.
Il est dit correct lorsque, pour chaque instance du problème, il se termine en produisant la bonne sortie, c’est-à-dire qu’il résout le problème posé.

Etude de projet

Voici l’introduction du projet

“A l’heure où le monde continue son ascension vers la robotique, l’aspirateur manuel se voit concurrencé par des robots aspirateurs autonomes. Néanmoins l’adaptation dans la vie courante des robots aspirateur stagne un peu.
Les causes principales sont le coût élevé d’un robot mais également la rapidité du robot pour effectuer un nettoyage complet d’une pièce. En effet, la grande majorité des robots effectuent un déplacement aléatoire. C’est pourquoi, beaucoup de personnes doutent de leur efficacité et préfèrent la méthode traditionnelle, plus contraignante mais néanmoins efficace.

Ce projet ayant pour but la création d’un programme de simulation du fonctionnement d’un robot chargé de faire le ménage dans une pièce, nous a permis d’étudier les différentes méthodes permettant de concevoir le déplacement d’un robot.
Cette démarche d’étude a abouti à la construction de trois types de robots différents.

Le premier, n’ayant aucune mémoire, a été élaboré à l’image des robots existants, c’est-à-dire avec un déplacement aléatoire.
Les deux autres types de robots possèdent une mémoire.
Celui du deuxième type, avec une mémoire limitée, se rapproche des robots haut de gamme actuels alors que celui du troisième type utilise une mémoire utopique, celle-ci étant infinie.

Cette étude fut très intéressante car elle a permis de réfléchir sur l’évolution possible des robots mais plus particulièrement de comparer différentes façons de nettoyer une pièce contenant des obstacles et ainsi d’étudier la rentabilité des robots en fonction de leur mémoire.

Et l’on peut alors se demander s’il existe une différence transcendante entre ces trois grandes catégories de robots : les robots sans mémoire, les robots à mémoire limitée, et les robots idéaux ? Pour essayer d’y répondre nous avons conçu un programme de simulation du fonctionnement d’un robot aspirateur.”

Langage utilisé pour l’algorithme

Le langage est le Java :

Java est un langage de programmation orienté objet créé par James Gosling et Patrick Naughton, employés de Sun Microsystems, avec le soutien de Bill Joy (cofondateur de Sun Microsystems en 1982), présenté officiellement le 23 mai 1995 au SunWorld.
La particularité et l’objectif central de Java est que les logiciels écrits dans ce langage doivent être très facilement portables sur plusieurs systèmes d’exploitation tels que Unix, Windows, Mac OS ou GNU/Linux, avec peu ou pas de modifications, mais qui ont l’inconvénient d’être plus lourds à l’exécution (en mémoire et en temps processeur) à cause de sa machine virtuelle. Pour cela, divers plateformes et frameworks associés visent à guider, sinon garantir, cette portabilité des applications développées en Java.

Déplacement aléatoire

Le Ilife V7S pro utilise un algorithme aléatoire qui est analysé par l’université de cette manière :

“Nous avons longuement cherché un algorithme pour le robot aspirateur de type 1 sans mémoire.

Après de nombreux essais, nous nous sommes rendus compte qu’un seul algorithme permettait le nettoyage complet d’une pièce, celui d’un déplacement aléatoire, les autres finissant soit par faire boucler le robot sur lui même, soit par oublier de laver une ou plusieurs cases.

Le fonctionnement de l’algorithme consiste à choisir une case aléatoirement et si celle-ci n’est pas envisageable, il en choisit une autre parmi celles restantes, et ce jusqu’à ce qu’il en trouve une qui soit accessible. Pour cela, les 4 déplacements envisageables pour le robot sont caractérisés par un chiffre entre 0 et 3 inclus, puis placés dans un tableau.

Ensuite, par un tirage aléatoire nous sélectionnons un déplacement et regardons s’il est accessible ou pas. S’il l’est, le robot exécute le déplacement sélectionné, sinon il supprime le déplacement testé et recommence la même opération sur les déplacements restants.

L’utilisation de cet algorithme nécessite une création de la pièce correcte, c’est-à-dire sans que le robot soit entouré, dés le début, par des obstacles.”

Algorithme des fourmis

Les fourmis utilisent l’environnement comme support de communication : elles échangent indirectement de l’information en déposant des phéromones, le tout décrivant l’état de leur « travail ». L’information échangée a une portée locale, seule une fourmi située à l’endroit où les phéromones ont été déposées y a accès.

Pour notre sujet :
“Cet algorithme est ainsi nommé car il imite le mode de déplacement des fourmis, de leur fourmilière jusqu’à un point de nourriture.En effet, lorsqu’une fourmi se déplace elle laisse derrière elle une trace de son passage. Plus elle passe par un chemin plus il est marqué.
Nous avons donc attribué cette caractéristique à notre deuxième robot (le robot de type 2) dans la limite de sa mémoire, afin que contrairement à une fourmi il évite de repasser sur les cases marquées (les cases sur lesquelles il est déjà passé). Le fonctionnement de cet algorithme repose sur une liste chainée « coo » qui représente sa mémoire, elle est donc d’une taille limitée.”

Conclusion

“Suite à l’analyse des statistiques sur plusieurs jeux d’essais, nous pouvons constater une différence colossale du point de vue du rendement entre un robot sans mémoire et un robot dont sa taille de mémoire est proportionnelle au périmètre de la pièce.

En effet, pour un robot qui n’aurait pas une mémoire infinie, la taille optimale de sa mémoire serait le périmètre interne de la pièce. Si sa taille est inférieure, ses performances chuteront mais resteront malgré tout supérieures à celle du robot sans mémoire.
Dans le cas d’un robot utopique, ses performances sont incomparables aux deux autres et ce quelque soit la pièce utilisée. L’élaboration des différents algorithmes permettant le déplacement du robot, et les problèmes rencontrés suite au contraintes de chaque robot, nous sensibilise davantage à la complexité algorithmique que pose la réalisation d’un programme permettant de guider un robot dans la réalité.”

Pour ceux qui souhaitent voir le projet en totalité avec le code Java, je vous livre le PDF SimulationRobot de 65 pages!

Remerciez l'auteur en lui donnant votre vote ;-) ------>
7 0
Publié par : Le Capitaine

Dany, fondateur du Danyvape. Plus de clopes depuis le 1er jour, le 21 sept 2012... A l'abordage !!

Comments

Cet article a 5 commentaires.

Les rangs correspondent au nombre de commentaires :Nouveau contributeur/Bronze clair-foncé/Argent clair-foncé/Or clair-foncé/Saphir/Rubis/Emeraude/Diamant.
  • Fil - Rang : Saphir 14 juillet 2018 14 h 09 min Répondre

    Oh purrrééée !! j’entrave que couic !
    Mais chapeau à vous deux, pour ceux qui kiffent les algorithmes.
    À part ça, j’aime bien la section high-tech, c’est une sacrée bonne idée !

  • LanciaB - Rang : Argent clair 14 juillet 2018 19 h 33 min Répondre

    Très intéressant. Je comprends mieux pourquoi quand je passe l’aspirateur c’est pas génial, ma mémoire est très limitée et mes algorithmes datent de la fin des 60’s, efficacité réduite !

  • Nesquick - Rang : Diamant 14 juillet 2018 22 h 24 min Répondre

    Nous autres, on ne se pose pas de question quand on rentre dans une pièce. On regarde et s’il faut l’arpenter en passant partout, on se débrouille en se disant même “tiens, je passerai le long de la fenêtre tout à l’heure” si on le souhaite.
    C’est rigolo de voir combien il est difficile de reproduire ce comportement naturel par une programmation informatique mais un jour on y arrivera.
    Les voitures autonomes sont déjà aux portes de notre quotidien, je ne sais pour ma part s’il faut ou non s’en réjouir. :scratch:

    • Le Capitaine - Rang : Diamant 21 juillet 2018 11 h 16 min Répondre

      Le problème du “je repasserais ici tout à l’heure” c’est que le cerveau pense à tellement de choses en même temps que l’on oublie la plupart du temps de le faire. On s’en souvient qu’une fois rangé l’aspiro…
      C’est déjà galère pour celui qui a un sans fil, alors pour moi avec mon gros Dyson filaire, je laisse tomber!
      Le Ilife ne peut pas remplacer un tradi, surtout un avec suceur et tuyau souple comme le mien pour se faufiler partout sur les meubles qui ont autant de poussière que par terre.
      Mais il est très pratique car silencieux, on peut le passer la nuit s’en reveiller personne, l’enfermer dans la cuisine 15mn pendant qu’on fait autre chose.
      Disons que ça réduit considerablement le travail du gros qui ne servira qu’une fois par semaine au lieu de tous les jours.

  • Le Capitaine - Rang : Diamant 15 juillet 2018 22 h 09 min Répondre

    Le Ilife est impressionnant! il semble aller au hasard mais en fait, il fait toute la pièce!
    Je pense qu’il a du type I mais aussi du 2 avec de la mémoire :yes:

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

:bye:  :good:  :negative:  :scratch:  :wacko:  :yahoo:  B-)  :heart:  :rose:  :-)  :whistle:  :yes:  :cry:  :mail:  :-( 
:unsure:  ;-)