Developing unmanned vehicles in high school with LEGO EV3
Robomobili without drivers deliver pizza. Taxis without drivers carry people. Wagons without drivers delivering multi-ton loads. If we analyze all these spectacular projects, we will come to different typical tasks, of which the important thing is finding and optimizing routes. Such problems are solved using graph theory . This topic is not an easy one, it is studied mainly at the university or, at least, in the senior specialized classes. But in this post I will show how to learn graph theory in high school using LEGO EV3. And without cramming, but at an exciting, applied level.
Danny's LAB EV3 based conveyor. Really collects LEGO-typewriter. But it's not about him.
In order for the unmanned vehicle to reach where it should be, it must be able to build a route between the given points. Preferably the shortest and consistent with the rules of the road. To simulate and solve this problem, we need the LEGO EV3 mobile platform and, in fact, the map on which this platform will move.
Our mobile platform must be equipped with sensors and servos. Everything you need can be found in the LEGO Mindstorms EV3 45544 basic educational set. This is how the platform looks like:
')
The assembly does not require knowledge of electronics and takes no more than half an hour. The platform has everything you need to rise to a high level of abstraction in solving the problem.
Draw a road map as a grid. Lines are roads, intersections are intersections of roads:
All segments of the road between intersections have the same length, the movement on them is two-way. Some roads are blocked - they are marked with "brick". In addition, all the turns on our map are multiples of 90 degrees. The complexity of the road grid will not affect the principle of solving the problem, and for clarity, we will manage a fairly simple option. Our task is to travel from point A to point B about the shortest path.
Each intersection has its own coordinates - line numbers horizontally and vertically. In graph theory, such intersections are called vertices . Roads between intersections are indicated by arrows. In graph theory, these are edges . All roads are two-way (arrows in both directions) means the graph is undirected . The cost (travel time) for all road sections is the same, so the unweighted graph.
The graph represented by the picture clearly shows the map and the connections inside it. But on a computer - including on EV3 - it is laborious to process graphic information. The best way to encode a graph is a matrix, an adjacency matrix.
If there is no direct communication between intersections, we put 0 at the point of intersection. If there is - 1. We agreed that all distances between neighboring intersections are 1. If we had a weighted graph, then instead of one in each intersection we would put “ weight "plot. And if they took into account the direction of movement, then the matrix above would be asymmetric - in one direction there could be 1, and in the other 0.
With the adjacency matrix, our robot can already solve the problem - find the shortest path from A to B. But we have a two-dimensional matrix, and only one-dimensional arrays can be stored in EV3. We can easily go to a one-dimensional array through the shift n * Y + X, where n is the size of the matrix.
For the solution, Dijkstra's algorithm will be used - the algorithm for finding the shortest path between one vertex of the graph and all the others. The algorithm was invented in 1956 by the Dutch scientist Edsger Dijkstra. If it is as simple to explain as possible, then the algorithm is based on the sequential advancement to the neighboring vertices of the graph with a constant assessment of the distance traveled. A good illustrative example and the basic flowchart of the algorithm can be found in an article on Wikipedia.
In our case, the flowchart of Dijkstra’s algorithm (our “dijkstra”) will look as follows:
According to the algorithm, and better according to its mathematical model, we can already create a program for the robot. Input data will be adjacency matrix, starting and ending points. After all the described actions, the search for the shortest path between any points on the same map can be found quickly.
Of course, in addition to the Dijkstra algorithm, our LEGO EV3 based robot will need a number of simpler software modules (subroutines): moving along the line to the intersection, counting intersections, turning in both directions, determining its location relative to the absolute coordinate system X, Y, Θ, where X, Y - coordinates on the grid, Θ - current direction of the robot (expressed through a code, for example 1 - up, 2 - to the right, 3 - down, 4 - to the left).
But a live demonstration of the problem. The input data is somewhat different, but essentially it does not change.
Odometry capabilities can be integrated into the task of moving on the ground - for example, so that the robot in the maze understands where it is and where it is going. Using odometry, the movement of the robot is estimated based on the data on the movement of the drives (rotation of the engines). Knowing the diameter of the wheels, we can calculate the distance that the robot traveled for a certain time. Knowing the angular velocity of the wheels, we can determine the angle at which the robot turned relative to the initial one. And by setting different angular speeds, we can adjust the movement of the robot in an arc and, at the same time, define “loops” as the robot moves, as in the video below:
In schools, much attention is paid to trigonometry, but its practical application is not covered in any way. The odometry tasks solved with the help of LEGO EV3 show why trigonometry may be needed at all. In practice, odometry is used not only in transport, but also, for example, to track the tool position in CNC machines (numerical control).
Beg a little advertising. The task described above and more complex tasks can be solved by the guys of 7-9 classes, who have been trained in the clubs of robotics. I run one such club, Robit, in Yekaterinburg — this is our training program . Video from the demo to the task above, we filmed in one of the classes. Then one eighth-grader from our club for 6 hours studied the basics of graph theory and solved a similar problem.
Problem solving is impossible without choosing an appropriate programming environment for the LEGO EV3. About the news in this area there is a separate material . I try to teach the guys to choose a programming language for a task, and not a task for that programming language, the syntax of which they learned. But in the lower grades it is difficult to immediately work in a text-based programming language, so we begin to study algorithms in graphical languages, where the threshold of entry is lower. From the age of 10, students master the graphic environment of EV3 Mindstorms. Some robotics competitions limit the toolkit to this environment only.
From the age of 12, they are starting to master the environment of EV3 Basic. The environment is relatively easy to learn, and Basic offers powerful functionality for the LEGO EV3 platform. In addition, we program in the EV3Dev environment, where you can install many different languages - Python, Java, C. With the help of EV3Dev, the guys get their first experience in trending, in-demand languages. The only minus of EV3Dev is a relatively lower scanning speed of sensors compared to other environments. With the right approach, the LEGO EV3 becomes an excellent tool for learning about programming. When students see their code breathing life into the constructor, this is an excellent motivation.
Having studied these algorithms in high school, the children will be able to further consolidate their knowledge and, for example, participate in design and subject Olympiads, which give real bonuses - for example, 100 points on the Unified State Exam by entering the universities.
Danny's LAB EV3 based conveyor. Really collects LEGO-typewriter. But it's not about him.
In order for the unmanned vehicle to reach where it should be, it must be able to build a route between the given points. Preferably the shortest and consistent with the rules of the road. To simulate and solve this problem, we need the LEGO EV3 mobile platform and, in fact, the map on which this platform will move.
Mobile platform LEGO EV3
Our mobile platform must be equipped with sensors and servos. Everything you need can be found in the LEGO Mindstorms EV3 45544 basic educational set. This is how the platform looks like:
')
The assembly does not require knowledge of electronics and takes no more than half an hour. The platform has everything you need to rise to a high level of abstraction in solving the problem.
Road map
Draw a road map as a grid. Lines are roads, intersections are intersections of roads:
All segments of the road between intersections have the same length, the movement on them is two-way. Some roads are blocked - they are marked with "brick". In addition, all the turns on our map are multiples of 90 degrees. The complexity of the road grid will not affect the principle of solving the problem, and for clarity, we will manage a fairly simple option. Our task is to travel from point A to point B about the shortest path.
Graph
Each intersection has its own coordinates - line numbers horizontally and vertically. In graph theory, such intersections are called vertices . Roads between intersections are indicated by arrows. In graph theory, these are edges . All roads are two-way (arrows in both directions) means the graph is undirected . The cost (travel time) for all road sections is the same, so the unweighted graph.
Adjacency matrix
The graph represented by the picture clearly shows the map and the connections inside it. But on a computer - including on EV3 - it is laborious to process graphic information. The best way to encode a graph is a matrix, an adjacency matrix.
If there is no direct communication between intersections, we put 0 at the point of intersection. If there is - 1. We agreed that all distances between neighboring intersections are 1. If we had a weighted graph, then instead of one in each intersection we would put “ weight "plot. And if they took into account the direction of movement, then the matrix above would be asymmetric - in one direction there could be 1, and in the other 0.
With the adjacency matrix, our robot can already solve the problem - find the shortest path from A to B. But we have a two-dimensional matrix, and only one-dimensional arrays can be stored in EV3. We can easily go to a one-dimensional array through the shift n * Y + X, where n is the size of the matrix.
Dijkstra's Algorithm
For the solution, Dijkstra's algorithm will be used - the algorithm for finding the shortest path between one vertex of the graph and all the others. The algorithm was invented in 1956 by the Dutch scientist Edsger Dijkstra. If it is as simple to explain as possible, then the algorithm is based on the sequential advancement to the neighboring vertices of the graph with a constant assessment of the distance traveled. A good illustrative example and the basic flowchart of the algorithm can be found in an article on Wikipedia.
In our case, the flowchart of Dijkstra’s algorithm (our “dijkstra”) will look as follows:
According to the algorithm, and better according to its mathematical model, we can already create a program for the robot. Input data will be adjacency matrix, starting and ending points. After all the described actions, the search for the shortest path between any points on the same map can be found quickly.
Of course, in addition to the Dijkstra algorithm, our LEGO EV3 based robot will need a number of simpler software modules (subroutines): moving along the line to the intersection, counting intersections, turning in both directions, determining its location relative to the absolute coordinate system X, Y, Θ, where X, Y - coordinates on the grid, Θ - current direction of the robot (expressed through a code, for example 1 - up, 2 - to the right, 3 - down, 4 - to the left).
But a live demonstration of the problem. The input data is somewhat different, but essentially it does not change.
Bonus Theme: Odometry
Odometry capabilities can be integrated into the task of moving on the ground - for example, so that the robot in the maze understands where it is and where it is going. Using odometry, the movement of the robot is estimated based on the data on the movement of the drives (rotation of the engines). Knowing the diameter of the wheels, we can calculate the distance that the robot traveled for a certain time. Knowing the angular velocity of the wheels, we can determine the angle at which the robot turned relative to the initial one. And by setting different angular speeds, we can adjust the movement of the robot in an arc and, at the same time, define “loops” as the robot moves, as in the video below:
In schools, much attention is paid to trigonometry, but its practical application is not covered in any way. The odometry tasks solved with the help of LEGO EV3 show why trigonometry may be needed at all. In practice, odometry is used not only in transport, but also, for example, to track the tool position in CNC machines (numerical control).
Where can you learn all this
Beg a little advertising. The task described above and more complex tasks can be solved by the guys of 7-9 classes, who have been trained in the clubs of robotics. I run one such club, Robit, in Yekaterinburg — this is our training program . Video from the demo to the task above, we filmed in one of the classes. Then one eighth-grader from our club for 6 hours studied the basics of graph theory and solved a similar problem.
How to choose a programming environment LEGO EV3
Problem solving is impossible without choosing an appropriate programming environment for the LEGO EV3. About the news in this area there is a separate material . I try to teach the guys to choose a programming language for a task, and not a task for that programming language, the syntax of which they learned. But in the lower grades it is difficult to immediately work in a text-based programming language, so we begin to study algorithms in graphical languages, where the threshold of entry is lower. From the age of 10, students master the graphic environment of EV3 Mindstorms. Some robotics competitions limit the toolkit to this environment only.
From the age of 12, they are starting to master the environment of EV3 Basic. The environment is relatively easy to learn, and Basic offers powerful functionality for the LEGO EV3 platform. In addition, we program in the EV3Dev environment, where you can install many different languages - Python, Java, C. With the help of EV3Dev, the guys get their first experience in trending, in-demand languages. The only minus of EV3Dev is a relatively lower scanning speed of sensors compared to other environments. With the right approach, the LEGO EV3 becomes an excellent tool for learning about programming. When students see their code breathing life into the constructor, this is an excellent motivation.
What's next?
Having studied these algorithms in high school, the children will be able to further consolidate their knowledge and, for example, participate in design and subject Olympiads, which give real bonuses - for example, 100 points on the Unified State Exam by entering the universities.
Source: https://habr.com/ru/post/427471/
All Articles