Quelle est une manière efficace de visiter chaque espace accessible sur une grille avec des obstacles inconnus?

J'essaie de créer une carte des obstacles dans un espace de grille 2D assez grossier, en utilisant l'exploration. Je détecte des obstacles en essayant de passer d'un espace à un espace adjacent, et si cela échoue, il y a un obstacle dans l'espace de destination (il n'y a pas de concept de capteur de télémétrie dans ce problème).

exemple de grille http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (par exemple)

Le processus est terminé lorsque tous les carrés accessibles ont été visités. En d'autres termes, certains espaces peuvent être complètement inaccessibles même s'ils n'ont pas d'obstacles car ils sont entourés. Cela est attendu.

Dans le cas le plus simple, je pourrais utiliser un algorithme DFS , mais je crains que cela prenne trop de temps à terminer - le robot passera plus de temps à revenir en arrière qu'à explorer de nouveaux territoires. Je m'attends à ce que cela soit particulièrement problématique lorsque vous tentez d'atteindre les carrés inaccessibles, car le robot épuisera toutes les options.

Dans la méthode la plus sophistiquée, la bonne chose à faire semble être la décomposition des cellules de Boustrophedon .

Cependant, je n'arrive pas à trouver une bonne description de l'algorithme de décomposition des cellules de Boustrophedon (c'est-à-dire une description complète en termes simples). Il existe des ressources comme celle-ci , ou celle plus générale sur la décomposition verticale des cellules, mais elles n'offrent pas beaucoup d'informations sur les algorithmes de haut niveau ni sur les structures de données de bas niveau impliquées.

Comment visiter (cartographier) efficacement cette grille? S'il existe, je voudrais un algorithme qui fonctionne mieux que par rapport au nombre total de carrés de grille ( c'est-à-dire meilleur que pour une grille ).$O(n^2)$$O(n^4)$$n*n$

La décomposition des cellules de boustrophédon consiste simplement à diviser un environnement en zones qui peuvent être efficacement couvertes par un chemin de boustrophédon. Une décomposition trapézoïdale fera l'affaire et peut être accomplie en utilisant un algorithme de balayage de ligne. Voir [Choset 2000], ce site Web , ou (je recommande!) L'excellent livre "Computational Geometry" de Mark de Berg, et. al, pour une description complète des structures de données et des algorithmes nécessaires.

Choset, Howie. "Couverture des espaces connus: la décomposition cellulaire de Boustrophedon" Autonomous Robots , 2000.

Par exemple, considérez l'ensemble des obstacles comme des arêtes et des sommets. Disons que l'environnement est également délimité par un polygone spécial. Nous avons quelque chose comme ce qui suit. Pour décomposer cet espace, nous ajoutons simplement des arêtes verticales entre chaque sommet et la ligne ou le sommet le plus proche.

Pour cela dans le code, vous n'avez besoin que d'un test d'intersection de segment de ligne, d'une liste triée d'arêtes et d'une liste triée de sommets.

1. $v_i$
2. $l_i$$v_i$
3. À chaque intersection, créez un nouveau sommet.

Lorsque cela est fait, l'ensemble des nouvelles arêtes et sommets ne renferme que des trapèzes. Mais je souligne, vous ne pouvez pas le faire en ligne (sans connaissance préalable des obstacles). Si vous voulez faire une couverture robuste sans connaissance préalable, vous pouvez regarder les "algorithmes de bogue". En particulier, voici un algorithme simple, en supposant que l'environnement est borné.

1. Depuis la position de départ, déplacez-vous vers le haut et vers la gauche jusqu'à ce que vous atteigniez le coin supérieur gauche de l'environnement. Si vous rencontrez un obstacle en premier, vous devez le contourner. Vous savez que quelque chose est un obstacle s'il peut être contourné (cogner et bouger).

2. En haut à gauche, déplacez-vous vers la droite jusqu'à ce que vous rencontriez la limite. Ensuite, déplacez-vous vers le bas et à gauche (nous faisons un boustrophédon de tout l'espace).

3. Lorsque vous êtes sur une ligne gauche-droite et rencontrez un obstacle, vous avez deux options. (i) Nous pouvons faire le tour jusqu'à ce que nous atteignions la ligne gauche-droite que nous essayons de couvrir, puis continuer. (ii), Nous pouvons faire demi-tour et couvrir une nouvelle ligne gauche-droite jusqu'à ce que nous trouvions notre chemin devant l'obstacle ou que nous nous retrouvions à nouveau dans cette situation. Je vais illustrer.

Sur la gauche, nous contournons l'obstacle jusqu'à ce que nous puissions revenir à la "ligne" que nous essayions de suivre. A droite, nous continuons à couvrir la (plus petite) zone d'un côté de l'obstacle.

L'avantage de la première méthode est que vous traitez toujours complètement l'obstacle avant de prendre une décision sur la façon de le contourner, vous pouvez donc emprunter le chemin le plus court. L'avantage de la deuxième méthode est que vous n'avez pas du tout à contourner l'obstacle, vous pouvez simplement continuer à couvrir la zone dans laquelle vous vous trouvez.

Notez que cela définit votre décomposition de boustrophédon de manière en ligne : vous couvrez la zone entre les obstacles ou entre les obstacles et la frontière.

Cependant, à ma connaissance, la première méthode est plus facile à analyser. Les algorithmes les plus compliqués (comme BFS, etc.) sont choisis soit parce que l'environnement n'est pas illimité (vous ne voulez pas passer indéfiniment à chercher une frontière), soit qu'il y a un obstacle vraiment désagréable dans la manière de partitionner fondamentalement l'environnement. Pourquoi est-ce mauvais? regardez cet exemple:

Se déplacer de gauche à droite, puis encercler chaque obstacle produit beaucoup trop de couvertures des petites pièces entre chaque obstacle. En fait, sans planification de chemin globale, vous pouvez rendre cela aussi mauvais que la résolution de votre grille en plaçant ces colonnes de 1 px de large, aussi hautes que l'environnement entier et à 1 px de distance. Ensuite, vous devez contourner l'obstacle à chaque fois que vous le heurtez.

C'est pourquoi j'ai demandé si vous aviez une idée de l'endroit où vous vous trouviez dans l'environnement ou si vous pouviez faire une planification globale du chemin. Mais la discussion en ligne vs hors ligne et les algorithmes optimaux pour ce n'est pas ce que vous vouliez vraiment.

Mise à jour: j'ai dû supprimer les images (pas https), et publierai cela qui est souvent utilisé dans des applications pratiques du monde réel. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf

En fin de compte, j'ai trouvé que la meilleure façon de procéder était d'employer un concept très simple: Flood Fill . J'ai utilisé une approche itérative basée sur la pile au lieu de l'option récursive et l' ai modifiée pour l'espace physique en utilisant une recherche A * pour trouver un chemin de l'emplacement actuel à l'emplacement suivant dans la pile (en utilisant uniquement les carrés de la grille qui ont déjà été visité, car je suis assuré d'avoir un chemin entre eux).

L'efficacité semble assez raisonnable.