Quel algorithme dois-je implémenter pour programmer un robot de nettoyage de pièce?

Pour cette question, supposez que les choses suivantes sont inconnues:

• La taille et la forme de la pièce
• L'emplacement du robot
• La présence d'obstacles

Supposons également que les éléments suivants sont constants:

• La taille et la forme de la pièce
• Le nombre, la forme et l'emplacement de tous les obstacles (le cas échéant)

Et supposez que le robot possède les propriétés suivantes:

• Il ne peut avancer que par incréments d'unités absolues et tourner en degrés. De plus, l'opération qui se déplace reviendra vraie si elle a réussi ou fausse si elle n'a pas bougé en raison d'une obstruction
• Une source d'énergie raisonnablement illimitée (disons que c'est un robot à énergie solaire placé sur une station spatiale qui fait face au soleil à tout moment sans plafond)
• Chaque mouvement et rotation est effectué avec une précision absolue à chaque fois (ne vous inquiétez pas des données non fiables)

Enfin, veuillez considérer les propriétés suivantes de l'environnement du robot:

• Étant sur une station spatiale sans plafond, la pièce est à une distance sûre mais frustrante des comètes qui passent, de sorte que la poussière (et la glace) jonchent constamment l'environnement.

On m'a demandé une version beaucoup plus simple de cette question (la pièce est un rectangle et il n'y a pas d'obstacles, comment vous y déplaceriez-vous en garantissant que vous pourriez recouvrir chaque partie au moins une fois) et après avoir commencé à me demander comment vous aborderiez cela si vous ne pouviez pas 'garantissent pas la forme ou la présence d'obstacles. J'ai commencé à regarder cela avec l'algorithme de Dijkstra , mais je suis fasciné d'entendre comment les autres abordent cela (ou s'il existe une réponse bien acceptée à cela? (Comment Roomba le fait-il?)

Autant que je sache, ce problème n'a pas été «résolu».

Formellement, il s'agit d'un problème de couverture en ligne. Couverture, car nous devons couvrir chaque point sur le sol, et en ligne car nous n'avons pas accès hors ligne à la carte. Si vous êtes intéressé par les résultats les plus récents, je vous suggère de rechercher des " algorithmes de couverture robotique en ligne ", peut-être dans google scholar (il y a beaucoup, beaucoup de bons résultats). En plus du (re) post très coloré de @ embedded.kyle, j'ajouterai quelques détails (j'essaierai également de trouver rapidement quelques résultats simples):

• Dijkstra vous donnera un chemin, mais pas nécessairement une couverture. Par exemple, comment spécifiez-vous à Dijkstra que vous devez visiter chaque point du graphique, au lieu de visiter un point le plus rapidement possible? Vous pouvez exécuter les chemins les plus courts toutes paires, mais quels sont les points? Vous n'avez pas de carte.

• Les algorithmes en ligne comme celui-ci sont souvent appelés algorithmes de "bogue" car ils ont tendance à ressembler à un bogue errant dans une zone, se heurtant à quelque chose, puis errant un peu autour.

• Sans obstacles, et une salle rectangulaire, et en supposant que vous commencez sur la frontière, un chemin de boustrophédon (chemin du bœuf) est optimal.

C'est drôle que les agriculteurs le fassent depuis toujours, non? http://en.wikipedia.org/wiki/Boustrophedon . Cela peut être étendu aux pièces avec des obstacles en trouvant une zone à peu près rectangulaire qui est libre d'obstacles. Howie Choset y a un peu travaillé .

• $\pi*d^2$$d$ frontière , non?). Cela est utile: vous êtes maintenant assuré de trouver la frontière la plus proche et de la tracer.
• C'est un domaine immense et fascinant. Je suis désolé, je ne peux pas fournir un meilleur résumé!

Le plus gros problème est que vous n'avez pas de carte. Sans carte, vous êtes limité à des actions simples comme suivre le périmètre et vous déplacer le long d'un chemin (comme la spirale mentionnée). Il existe donc des robots qui construisent la carte pendant le nettoyage, décomposent la zone tracée en formes, puis couvrent chaque forme pour assurer la couverture. Voir: http://mintcleaner.com/

Roomba commence dans une spirale jusqu'à ce qu'il frappe quelque chose, puis effectue un balayage de périmètre. Ensuite, il rebondit. Le Roomba étant la norme de facto dans les aspirateurs robotiques ménagers, je suppose que vous pourriez l'appeler la "solution acceptée". Mais par expérience personnelle (j'en possède deux), il y a certainement place à amélioration.

De façon dont fonctionne Stuff :

Extrait d' une entrevue avec Nancy Dussault Smith, vice-présidente des communications marketing chez iRobot:

Quand il commence, vous remarquerez un motif en spirale, il s'étendra sur une zone de plus en plus grande jusqu'à ce qu'il touche un objet. Quand il trouve un objet, il suivra le long du bord de cet objet pendant un certain temps, puis il commencera à traverser, essayant de déterminer la plus grande distance qu'il peut parcourir sans toucher un autre objet, et cela l'aide à comprendre la taille de l'espace, mais s'il passe trop de temps sans heurter un mur, il recommencera à tourner en spirale, car il figure qu'il est dans un grand espace ouvert, et il calcule et comprend constamment cela.

C'est similaire avec les capteurs de saleté en dessous, lorsque l'un de ces capteurs se déclenche, il change ses comportements pour couvrir cette zone. Il partira alors à la recherche d'une autre zone sale en ligne droite. La façon dont ces différents motifs s'empilent au fur et à mesure, nous savons que c'est le moyen le plus efficace de couvrir une pièce.

Les modèles que nous avons choisis et la façon dont l'algorithme a été développé à l'origine étaient basés sur des algorithmes comportementaux nés de l'étude des animaux par le MIT et sur la façon dont ils recherchent les zones de nourriture. Lorsque vous regardez comment les fourmis et les abeilles sortent et qu'elles recherchent des zones, ce type de couverture et tout cela ressort de cette recherche. Ce n'est pas exact, évidemment, je ne dis pas que nous sommes des abeilles, mais c'est cette compréhension de la façon de rechercher une zone dans la nature qui est à la base du développement de notre technologie adaptative.

Quelques photos de longue exposition de Roombas avec des LEDs sur eux illustrent comment cela fonctionne dans la pratique:

Neato utilise une approche organisée. À l'aide de SLAM et de pare-chocs, il cartographie la pièce «actuelle», le périmètre d'abord, puis applique un algorithme de nettoyage aussi efficacement que possible. Je n'ai jamais possédé de Roomba, mais étant donné ce que j'ai lu sur son algorithme, je ne changerais jamais de Neato.

Le télémètre laser dans le neato est souvent cannabilisé pour la robotique, car il s'agit d'un capteur rentable pour les algorithmes SLAM.

Si on me confiait votre tâche, je trouverais d'abord une implémentation SLAM appropriée , basée sur le matériel que j'avais.

Ensuite, j'utiliserais un algorithme de planification de mouvement CNC ISLAND . D'après mon expérience, ils ont tendance à être très efficaces pour couvrir une zone arbitraire avec le moins de mouvement.

La première chose que vous devez établir est le but du robot - pas tout à fait clair à partir de votre question. Il y a deux tâches principales que votre robot doit accomplir: découvrir la forme de la zone nettoyable, puis la nettoyer.

Mais la quantité de saleté est-elle constante? La saleté est-elle constamment ajoutée? Votre objectif est-il de minimiser le temps moyen pendant lequel la saleté reste sur le sol ou le temps médian? Le but est-il de garder le sol également propre? Ou s'agit-il simplement de nettoyer une fois, le plus rapidement possible? Y a-t-il des modèles d'accumulation de saleté que vous pouvez mesurer et utiliser à votre avantage pour atteindre votre objectif?

La réponse à ces questions aidera à guider l'algorithme que vous choisissez. Dans le cas du robot du Roomba, il pourrait être inutile d'apprendre la disposition exacte de la pièce car les meubles (comme les chaises autour d'une table), les personnes et autres obstacles se déplacent très souvent. Cependant, dans votre cas, il pourrait être préférable d'explorer l'espace pour construire une carte complète (une combinaison d'un modèle de tondeuse à gazon avec trouver des bords), puis utilisez cette carte pour calculer le chemin le plus court à travers l'espace (le terme est "couverture", et il existe plusieurs façons de le faire, par exemple l' algorithme de spanning tree ).

Une autre chose dont vous devrez vous soucier est de savoir comment discrétiser l'espace dans lequel vous vous trouvez. Parce que vous pouvez vous déplacer dans toutes les directions - même avec des degrés et des unités de distance entiers - vos positions X et Y peuvent avoir des fractions valeurs. Vous devrez décider de la façon de représenter les obstacles sur cette carte sans la faire passer à un nombre infini de points de données.

Je ne sais pas si vous en avez toujours besoin, mais pour ceux qui sont passés par google pour ce fil, j'ai fait une version simple de l'algorithme.

Fondamentalement, il essaie de construire la carte de la zone pendant qu'il nettoie, et il utilise la carte pour trouver le nœud non visible le plus proche (une partie de la pièce). Lorsqu'il n'en trouve pas, cela signifie que la pièce est nettoyée (ou que les pièces non nettoyées sont inaccessibles au robot).

Il peut être plus lent que les autres algorithmes, mais il peut garantir la couverture indépendamment de la position de départ, de la direction et des obstacles.

https://github.com/dungba88/cleaner_robot

MISE À JOUR: J'ai fait une démo ici et je la compare avec un DFS de retour en arrière. Donc, même si mon algorithme est O (N ^ 2), il est beaucoup plus optimisé en termes de nombre de mouvements et de tours.

http://jenova.dungba.org/cleaner/showdown

En regardant le problème le plus simple qui vous a été posé - une pièce rectangulaire, sans obstacle et nettoyez chaque pièce au moins une fois.

La solution est de trouver un coin de la pièce, et trouver un coin ne sera pas un gros problème. Une fois cela réalisé, il vous suffit de suivre un chemin en spirale jusqu'au centre de la pièce.