Quelle est la meilleure façon de naviguer et d'éviter les obstacles pour un robot de service?
Les robots sont des systèmes mécaniques et logiciels qui interagissent avec le monde réel. Pour un robot de service, il est extrêmement important de comprendre votre position actuelle dans l'espace, la position de la cible et la possibilité de construire un itinéraire vers la cible en évitant les éventuels obstacles. Nous développons un
robot de collecte de balles de golf sur le practice . Nous avons envisagé différentes options pour construire un itinéraire afin de trouver le meilleur pour nous-mêmes, peut-être que ces informations seront intéressantes pour quelqu'un.
La façon la plus simple d'amener le robot à atteindre son objectif ultime dans un espace à deux dimensions. Le rover lui-même est ici un petit point devant lequel il n'y a pas d'obstacles. Par conséquent, le robot dans cette situation se déplace en ligne droite et lorsqu'il atteint le but, il s'arrête.
Cette méthode convient s'il n'y a qu'un robot dans le monde et le but qu'il doit atteindre. Direct vous permettra d'atteindre la configuration finale le plus rapidement possible.
Mais cet algorithme ne peut pas être appliqué si un obstacle surgit soudainement devant le robot. Se déplaçant en ligne droite, le rover ne pourra pas le contourner ni le traverser. À cet égard, il s'arrête simplement devant un obstacle et ne bouge pas.
Comment contourner un obstacle? La façon la plus simple de résoudre le problème est l'option de comportement appelée «Évitement des obstacles». En pratique, il est représenté par différents algorithmes.
Marche vers l'algorithme
Si l'objectif n'est pas atteint:
- Avancez vers l'objectif.
- Sinon: arrêtez.
Cette méthode convient s'il n'y a qu'un robot dans le monde et le but qu'il doit atteindre. Direct vous permettra d'atteindre la configuration finale le plus rapidement possible. Mais quel algorithme appliquer si un obstacle surgit devant la cible devant le robot?
Un obstacle ne permet pas au robot d'atteindre sa destination en ligne droite, le rover dans cette situation s'arrête juste devant lui. Dans ce cas, vous pouvez également utiliser l'algorithme «Walk To», mais il doit être complété.
Algorithme de bogue
Dans la vie ordinaire, une personne, lorsqu'elle passe d'un point à un autre vers le but et rencontre un obstacle, la contourne simplement. Ce comportement est appelé «éviter les obstacles». Il s'avérera être appliqué pour atteindre l'objectif par le robot. La façon la plus simple d'appliquer l'algorithme du scarabée.
L'algorithme Bug est appelé par les experts de cette manière parce que le comportement du scarabée est pris comme base - s'il voit un obstacle, il le contourne.
Les étapes que le robot prend en se déplaçant vers la cible (y compris lorsqu'il contourne un obstacle) sont appelées trajectoire.
L'algorithme de bogue a servi de base aux concepts utilisés dans la construction de routes d'un type plus complexe. Cela comprend:
Concept de trajectoire. Il s'agit d'une simple séquence de mouvements du robot, qu'il exécute afin d'atteindre le but ultime. L'algorithme du coléoptère est également un «planificateur de trajectoire». Ayant reçu les coordonnées des points où se trouvent le robot et sa cible, l'algorithme développe une trajectoire de mouvement appropriée.
Concept politique . Si en utilisant l'algorithme du scarabée, certaines instructions de mouvement sont transmises au robot, alors cette façon de construire l'itinéraire est appelée la «Politique de gestion».
Concept heuristique. Il s'agit du nom de la règle utilisée pour informer le robot de la prochaine étape de l'algorithme. Dans cette situation, l'heuristique est la ligne le long de laquelle se déplace l'objet. Lors de la création d'un chemin, vous devez déterminer correctement l'heuristique. Si cela n'est pas fait correctement, l'itinéraire construit sera inopérant.
Cependant, un tel algorithme limite le développeur, car avec son aide, il sera possible de construire un itinéraire de taille limitée. Lorsque vous utilisez un tel algorithme pour construire un chemin, il est nécessaire que tous les obstacles prennent la forme d'un polygone convexe.
L'algorithme Bug a également ses limites:
- les obstacles doivent être à une certaine distance les uns des autres, il est impossible qu'ils aient un terrain d'entente;
- les limites des obstacles sont des courbes fermées, alors qu'elles doivent être telles que la ligne droite le long de laquelle le robot se déplace croise chacun d'eux un nombre limité de fois;
- un robot est un point disproportionnellement petit, il peut donc se déplacer entre les obstacles quel que soit le passage entre eux.
Certaines de ces limitations peuvent être surmontées en utilisant l'algorithme avancé DH-Bug. Sa caractéristique est qu'avec son aide, le robot sera capable de faire face aux obstacles en mouvement. De plus, un tel algorithme se compose de deux couches. Le premier est consultatif. Il vous permet de pré-évaluer l'itinéraire sans utiliser d'informations supplémentaires. La deuxième couche est adaptative. Grâce à lui, le robot répond en temps opportun à des obstacles qui n'étaient pas initialement prévus dans le programme.
Algorithme CBUG
L'algorithme CBUG est une version de la construction de l'itinéraire d'une manière qui prend en compte tous les détails. Lors de son développement, des spécialistes ont pris en compte la taille du robot, et ont également résolu des problèmes liés à l'optimisation du chemin créé. Une caractéristique distinctive d'un tel algorithme amélioré est que pour générer un itinéraire, il est nécessaire que le point de départ reste toujours dans la mémoire de l'objet. Invariablement pour l'algorithme CBUG, seulement que pour son application, il est nécessaire d'avoir une quantité fixe de mémoire.
Algorithme de Dijkstra
L'algorithme utilisé sur les graphiques a été créé par E. Dijkstroy dans la seconde moitié du siècle dernier. Avec son aide, il sera possible de déterminer le chemin le plus court d'un des sommets du graphe à d'autres. Un tel algorithme se termine lorsque le robot a visité tous les pics. Si ceux qu'il n'a pas encore visités roulent, un pic avec une note minimale est sélectionné.
Les avantages de l'algorithme Deister incluent:- faire attention à la longueur du chemin et à son coût;
- les nœuds sont mis à jour si un plus optimal est trouvé.
L'inconvénient de cette méthode de construction d'un itinéraire est qu'elle ne convient qu'aux graphiques où il n'y a pas de bords de poids négatif. Il n'est pas pratique qu'il soit mal orienté lors de la recherche en largeur.
Algorithme de Bellman-Ford
Mais il arrive souvent des situations dans lesquelles il est nécessaire de construire un itinéraire où il y a des côtes avec un poids négatif. L'algorithme Bellman-Ford aidera à résoudre un tel problème. Si, par conséquent, la somme des poids des bords du chemin final prend une valeur négative, alors on l'appelle un cycle négatif.
Algorithme de Johnson
Cet algorithme a été introduit par DB Johnson afin d'identifier tous les itinéraires les plus courts d'un pic à l'autre. Dans ce cas, la méthode peut être utilisée pour les bords avec des poids positifs et négatifs. Le seul inconvénient de l'algorithme est qu'il n'y a pas de cycles négatifs.
Algorithme A *
Pour trouver la manière la plus optimale d'utiliser des graphiques, vous devez appliquer l'algorithme A *. Il vous permet de déterminer le meilleur itinéraire du robot à la cible par la première correspondance sur le graphique. La base de cet algorithme est la formule heuristique, qui est la suivante:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .Cet algorithme vous permet de trouver le chemin le plus court vers l'objectif jusqu'à ce que h (n) prenne la valeur maximale autorisée. Une caractéristique de l'algorithme A * est sa flexibilité. Le plus souvent, l'état est la cellule ou l'emplacement du robot. Mais cela peut aussi être la vitesse ou l'orientation.
Dans le même temps, les États voisins varient en fonction du cas spécifique.
La flexibilité de l'algorithme se manifeste également dans le fait que l'objectif que le robot doit atteindre peut consister en plusieurs positions à la fois. Dans une telle situation, l'approximation heuristique h (n) devrait être valide immédiatement pour toutes les fins disponibles.
Le bon fonctionnement de l'algorithme A * dépend de l'exposant h (n). Plus la qualité d'approximation heuristique est meilleure, plus l'efficacité est élevée. De plus, la quantité de mémoire libre et le temps processeur affectent le fonctionnement de l'algorithme.
Algorithme de suivi des vagues
De plus, un algorithme d'onde est souvent utilisé pour tracer un itinéraire sur un graphique. Lorsque vous créez un chemin de cette manière, la méthode de recherche en largeur est utilisée.
L'algorithme lui-même comprend les étapes suivantes:- initialisation
- construction de vagues;
- récupération d'itinéraire.
Au stade initial, l'image de nombreuses cellules est créée, chacune devenant passable ou infranchissable pour le robot.
Le robot, se déplaçant d'une cellule à l'autre, détermine séquentiellement s'il est possible de le passer et s'il ne l'a pas marqué auparavant.
Après cela, le chemin le plus court de la cellule de départ à la cellule finale est créé par la force brute, dont la réalisation est le but du rover.
Discrétiser l'algorithme spatial
- L'espace de configuration a une taille constante dans toutes les dimensions.
- Discrétisez toutes les mesures afin qu'elles aient un nombre constant de cellules.
- Toutes les cellules situées dans l'espace de configuration à l'intérieur de l'obstacle doivent être marquées comme infranchissables.
- En conséquence, toutes les cellules passables se sont transformées en nœuds.
- Chaque nœud se connecte à tous les voisins du graphique.
Recherche de chemin aléatoire
Les aspects les plus difficiles lors de la planification d'un itinéraire sont le calcul de l'espace de configuration et la détermination du chemin le plus pratique lors du passage dans cet espace. Grâce aux feuilles de route, il sera possible de résoudre ces problèmes. L'essence de la méthode consiste à diviser l'espace en carrés identiques, reliant tous les sommets les plus proches. Itérer sur tous les chemins. Triez tous les chemins pour trouver le chemin avec la plus petite valeur.
Algorithme des cartes routières probabilistes
- 1. Créez un graphique vide G.
- 2. Ajoutez au graphique G les nœuds du robot et son objectif final.
- 3. Pour le Nième nombre d'intégrations:
- Trouvez un échantillon aléatoire uniforme de l'espace de configuration et donnez-lui le nom R.
- Si le robot est en conflit avec la configuration R, vous pouvez continuer.
- Sinon: ajoutez R à la colonne G.
- 4. Identifiez tous les nœuds du graphe situés à l'intérieur des points d et R.
- 5. Pour tous les N nœuds qui correspondent à ce paramètre:
Exploration rapide de l'algorithme d'arbres randomisés
Parfois, vous devez créer un chemin sans appliquer les requêtes de planification précédentes. Dans de telles situations, vous devez utiliser la méthode suivante:
- Créer un arbre T. vide
- Ajouter à la configuration initiale du robot T.
- Jusqu'à ce que l'objectif soit atteint:
- Récupérer pour le nœud R.
- Définissez en T le nœud situé le plus près de R. Donnez-lui le nom K.
- Déplacez le robot de K à R jusqu'à ce que la condition suivante soit remplie:
- En cas de collision, passez à la définition d'un échantillon aléatoire.
- Sinon: ajoutez un nouveau nœud à T dans cette configuration.
- Si la distance maximale entre d et K est atteinte, recommencez à travailler sur l'échantillonnage aléatoire.
- La solution est obtenue si le nœud de chaîne est situé à la distance d de tout nœud T.
Conclusion
Pour nous, il est optimal de séparer la question de la construction de routes entre globale et locale. Un itinéraire global est une liste de points cibles pour contourner le terrain ou l'objectif de revenir à la base. Un itinéraire local démarre lorsque des capteurs à ultrasons ou un pare-chocs détectent un obstacle.
Puisque dans nos spécificités tous les obstacles sont convexes, nous utilisons l'algorithme BUG le plus simple, et encore plus simple. Une certaine méthode de navigation «boyish». Lorsqu'une échographie détecte un obstacle, le mobile tourne à 90 degrés dans le sens des aiguilles d'une montre, passe 1 m, tourne à 90 dans le sens antihoraire. Si un obstacle est détecté par le pare-chocs, avant de faire reculer le robot de 0,5 mètre.
Plans
Lors du démarrage du projet à l'été 2018. Un grand nombre d'événements se sont produits. Nous préparons un article sur le développement de notre projet. Merci de votre attention!
Les références