Des motos sans chauffeur livrent des pizzas. Les taxis sans chauffeur transportent des personnes. Les camions sans chauffeur transportent des charges de plusieurs tonnes. Si nous analysons tous ces projets spectaculaires, nous arriverons à différentes tâches typiques, dont la plus importante est la recherche et l'optimisation des itinéraires. Ces problèmes sont résolus en utilisant la
théorie des graphes . Ce sujet n'est pas simple, il est étudié principalement à l'université ou, du moins, dans les classes supérieures spécialisées. Mais dans ce post, je montrerai comment utiliser le LEGO EV3 pour apprendre la théorie des graphes déjà au lycée. Et sans bourrage, mais à un niveau appliqué fascinant.
Convoyeur automobile LAB EV3 de Danny Collectionne vraiment les voitures LEGO. Mais ce n'est pas un peu pour lui.Pour que le transport sans pilote arrive là où il est nécessaire, il doit être capable de construire un itinéraire entre les points donnés. Le plus court et conforme aux règles de circulation est souhaitable. Pour simuler et résoudre un tel problème, nous avons besoin de la plateforme mobile LEGO EV3 et, en fait, de la carte sur laquelle cette plateforme se déplacera.
Plateforme mobile LEGO EV3
Notre plateforme mobile doit être équipée de capteurs et de servos. Tout ce dont vous avez besoin se trouve dans l'ensemble éducatif de base de LEGO Mindstorms EV3 45544. Voici à quoi ressemble la plate-forme:
L'assemblage ne nécessite pas de connaissances en électronique et ne prend pas plus d'une demi-heure. La plateforme a tout ce dont vous avez besoin pour atteindre un niveau d'abstraction élevé dans la résolution d'un problème.
Carte routière
Dessinons une feuille de route sous forme de grille. Les lignes sont des routes, les points d'intersection sont des intersections de routes:
Toutes les sections de la route entre les intersections sont de la même longueur, la circulation y est à double sens. Certaines routes sont bloquées - elles sont marquées d'une "brique". De plus, tous les virages sur notre carte sont des multiples de 90 degrés. La complication de la grille des routes n'affectera pas le principe de résolution du problème, et pour plus de clarté, nous ferons avec une option assez simple. Notre tâche est de conduire du point A au point B sur le chemin le plus court.
Compter
Chaque intersection a ses propres coordonnées - les numéros de ligne horizontale et verticale. En théorie des graphes, ces intersections sont appelées
sommets . Les routes entre les intersections sont indiquées par des flèches. En théorie des graphes, ce sont des
arêtes . Toutes les routes sont à double sens (flèches dans les deux sens) signifie que le graphique n'est
pas orienté . Le coût (temps de trajet) est le même pour toutes les sections de la route, ce qui signifie que le graphique n'est pas
pondéré .
Matrice d'adjacence
Le graphique représenté par l'image montre clairement la carte et les connexions à l'intérieur. Mais sur un ordinateur - y compris EV3 - il est difficile de traiter les informations graphiques. Il est optimal de coder un graphe avec une matrice, une matrice d'adjacence.
S'il n'y a pas de connexion directe entre les intersections, nous mettons 0. S'il y a - 1. S'il y a - 1. Nous avons convenu que toutes les distances entre les intersections adjacentes sont égales à 1. Si le graphique était pondéré, au lieu de l'unité à chaque intersection, nous mettrions « poids »de l'intrigue. Et si la direction du mouvement était prise en compte, alors la matrice ci-dessus serait asymétrique - dans un sens, elle pourrait être 1 et dans l'autre 0.
Avec une matrice d'adjacence, notre robot peut déjà résoudre le problème - trouver le chemin le plus court de A à B. Mais nous avons une matrice à deux dimensions, et dans EV3, seuls les tableaux à une dimension peuvent être stockés. Nous pouvons facilement accéder à un tableau unidimensionnel par le biais du décalage n * Y + X, où n est la taille de la matrice.
Algorithme de Dijkstra
L'algorithme de Dijkstra, l'algorithme pour trouver le chemin le plus court entre un sommet d'un graphe et tous les autres, sera utilisé pour la résolution. L'algorithme a été inventé en 1956 par le scientifique néerlandais Edsger Dijkstroy. Si l'explication est aussi simple que possible, alors l'algorithme est basé sur une progression séquentielle vers les sommets voisins du graphique avec une évaluation constante de la distance parcourue. Un bon exemple illustratif et un organigramme de base de l'algorithme peuvent être trouvés dans l'article Wikipedia.
Dans notre cas, l'organigramme de l'algorithme Dijkstra (notre «Dijkstra») ressemblera à ceci:
Selon l'algorithme, et mieux selon son modèle mathématique, on peut déjà créer un programme pour le robot. L'entrée sera la matrice d'adjacence, les points de début et de fin. Après toutes les actions décrites, la recherche du chemin le plus court entre n'importe quel point sur la même carte peut être trouvée rapidement.
Bien sûr, en plus de l'algorithme Dijkstra, notre robot basé sur LEGO EV3 aura besoin d'un certain nombre de modules de programme plus simples (sous-programmes): se déplacer le long de la ligne jusqu'à l'intersection, compter les intersections, tourner dans les deux directions, déterminer votre emplacement par rapport au système de coordonnées absolues X, Y, Θ, où X, Y - coordonnées sur la grille, Θ - la direction actuelle du robot (exprimée à travers le code, par exemple 1 - haut, 2 - à droite, 3 - bas, 4 - à gauche).
Et voici une démonstration en direct de la solution au problème. Les données d'entrée sont légèrement différentes, mais cela ne change pas l'essence.Thème bonus: odométrie
Les capacités d'odométrie peuvent être intégrées dans des tâches de déplacement sur le terrain - par exemple, pour que le robot dans le labyrinthe comprenne où il se trouve et où il se déplace. A l'aide de l'odométrie, le mouvement du robot est estimé à partir de données sur le mouvement des entraînements (rotation des moteurs). Connaissant le diamètre des roues, nous pouvons calculer la distance parcourue par le robot dans un certain temps. Connaissant la vitesse angulaire des roues, nous pouvons déterminer l'angle de rotation du robot par rapport à l'original. Et en réglant différentes vitesses angulaires, nous pouvons ajuster le mouvement du robot le long de l'arc et en même temps déterminer les «boucles» lors du déplacement du robot, comme dans la vidéo ci-dessous:
Dans les écoles, une grande attention est accordée à la trigonométrie, mais son application pratique n'est en aucun cas couverte. Les problèmes d'odométrie résolus avec LEGO EV3 montrent pourquoi la trigonométrie peut être nécessaire. En pratique, l'odométrie est utilisée non seulement dans les transports, mais aussi, par exemple, pour suivre la position d'un outil dans des machines CNC (commande numérique).
Où puis-je apprendre tout cela?
Je m'autorise de la publicité. La tâche décrite ci-dessus, et des tâches plus complexes peuvent très bien être résolues par des enfants de la 7e à la 9e année qui ont été formés dans des clubs de robotique. Je dirige un de ces clubs, Robit, à Iekaterinbourg - c'est notre
programme de formation . Nous avons tourné la vidéo de la démo pour la tâche ci-dessus dans l'une des classes. Un élève de huitième de notre club en 6 heures a étudié les bases de la théorie des graphes et résolu un problème similaire.
Comment choisir un environnement de programmation LEGO EV3
La résolution de problèmes est impossible sans choisir le bon environnement de programmation pour LEGO EV3. Il existe
des informations distinctes sur les dernières nouveautés dans ce domaine. J'essaie d'enseigner aux enfants à choisir un langage de programmation pour la tâche, et non une tâche pour ce langage de programmation, dont ils ont appris la syntaxe. Mais dans les classes inférieures, il est difficile de travailler immédiatement dans un langage de programmation basé sur du texte, nous commençons donc à étudier les algorithmes dans les langages graphiques, où le seuil d'entrée est plus bas. À partir de 10 ans, les élèves apprennent l'environnement graphique d'EV3 Mindstorms. Certaines compétitions de robotique limitent les kits d'outils à cet environnement uniquement.
Dès l'âge de 12 ans, les gars commencent à maîtriser l'environnement EV3 Basic. L'environnement est relativement facile à apprendre et Basic offre des fonctionnalités puissantes pour la plate-forme LEGO EV3. De plus, nous programmons dans l'environnement EV3Dev, où vous pouvez installer de nombreux langages différents - Python, Java, C. Avec EV3Dev, les gars ont leur première expérience dans les langages populaires et tendances. Le seul inconvénient d'EV3Dev est un taux d'interrogation du capteur relativement plus faible par rapport à d'autres environnements. Avec la bonne approche, LEGO EV3 devient un excellent outil pour apprendre à connaître la programmation. Lorsque les élèves voient leur code donner vie à un constructeur, c'est une excellente motivation.
Et ensuite?
Après avoir étudié de tels algorithmes au lycée, les enfants pourront consolider davantage leurs connaissances et, par exemple, participer à des olympiades de conception et de sujet qui donnent de vrais bonus - par exemple, 100 points automatiquement à l'examen lors de leur entrée dans les universités.