# 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 you analyze all these spectacular projects, we will come to different typical tasks, the most important of which is the search and optimization of 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 using LEGO EV3 to master the theory of graphs already in high school. And without cramming, but at an exciting, applied level.

In order for an 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 basic educational set LEGO Mindstorms EV3 45544. This is how the platform looks:

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. The lines are roads, the points of intersection are intersections of roads:

All sections 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 with 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

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).

Odometry capabilities can be integrated into the tasks of moving on the terrain - for example, so that the robot in the maze understands where it is and where it moves. 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 robot's movement 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 position of a tool 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 shot 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 work right away 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 learn 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 trend, 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 that 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 an 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 basic educational set LEGO Mindstorms EV3 45544. This is how the platform looks:

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. The lines are roads, the points of intersection are intersections of roads:

All sections 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 with 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 sections of the road is the same, which means 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 tasks of moving on the terrain - for example, so that the robot in the maze understands where it is and where it moves. 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 robot's movement 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 position of a tool 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 shot 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 LEGO EV3 programming environment

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 work right away 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 learn 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 trend, 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 that give real bonuses - for example, 100 points on the Unified State Exam by entering the universities.