Multi-drones path finding algorithm explained

When trying to solve a multi-drones path finding algorithm!

Have you ever seen how a robot works “in real life”?
Have you thought about how an object – inanimate by definition – moves through space?
How do you move their fingers, how do you make them move forward?
Alternatively, how can we make drones fly, for instance?

This work is not easy, because every step, every movement must be calculated and coded.

What is an “autonomous navigation algorithm”?

Autonomous navigation algorithm refers to a set of techniques and methods used by robots or vehicles to navigate and perform tasks without human interference. It allows them to observe, orient, decide, and take actions in their environment

These algorithms are designed to ensure safety and efficiency in executing tasks.

Let's go into a little more detail on the subject.
Anything related to space is relatively simple – simpler than machine learning, for example, because it simply relies on geometric calculations, graph calculations or trigonometric calculations.
These calculations are actually more precise and allow us to find the entire solution to a given problem.
This is the conviction formed from one of my experiments, which consisted of trying to create a trajectory search algorithm for drones.

This trajectory search algorithm was commissioned from me for a light show.
The challenge was to find a route so that all the drones could move within the same space without colliding with each other.
The algorithm was supposed to move the drones from one place to another and thus generate the light show.

The algorithm allows multiple drones to move within the same space from point A to point B without colliding.

Knowing that there is already a trajectory search algorithm for drones, I thought it might be relevant to use it.

The original idea was to create a 3-dimensional matrix. This divides the space into squares and each square includes the size of the drone as well as the safety zone.

Then we move the drone little by little, each time on one dimension, and we place a flag in the matrix to indicate that the place is occupied. In this way, we signal to the other drones that they should not move to this space.

We can simply perform this graph calculation: x + 1 or y + 1 or z + 1.

The navigation algorithms currently used for drone flight consist of finding the trajectory in space to go from point A to point B, using the algorithm to find the shortest path.

To do this, we divide the space into cubes. Each cube is a node, and each node is connected to all other nodes that are physically close to it. In a graph, for example, x is connected to x + 1, etc.

We then try to find the shortest path between node A and node B.
Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and another nodes in a graph. This algorithm uses the weights of the edges to find the path that minimizes the total distance (weight) between the source node and all other nodes.

This algorithm did not provide the solution to the problem posed.

Here the algorithm is different. We don't need to use the trajectory algorithm for a particular drone, but to find an algorithm to synchronize all drones together.
Moreover, we do not need, in all cases, to use the node algorithm, but rather to use graph functions. Thus we can calculate the line between 2 points of the graph and easily find the next point. Then to easily move from point A to point B within a graph, we can do it using one dimension each time: x+y, y+1, z+1.

We can also find the path by moving 3 dimensions each time and using the distance calculation D in a 3D graph. We can thus, for each step, find the next point using the formula D. In this way, the path is shorter, because instead of moving one dimension each time, which is x + 1, y + 1, z + 1 Which means: up, down, right or left, in front or behind, as in the graph, we go directly to the goal. For this, we need to calculate the next point with the distance calculation and the step length. This solution has not been implemented in the algorithm, but it is an improvement idea that has been partially implemented, so I could tell you, if it will succeed without any further problems.

There is also no need to try to find the shortest path by looking at all the possibilities, because usually one drone will have to wait or move, or another one will have to move out of the way, so it doesn't matter which drone it is.
So the shortest path is to go straight to the destination and then solve the collision problem.
Typically, for all drones, this will be the shortest path, and an algorithm can be obtained very quickly, without the need for brute force (testing all possibilities by recursion) or something similar.

So the solution here is to find an algorithm that synchronizes all the drones together. For this we will use graphical functions.

Moreover, it is not necessary to check all the nodes to know what is the shortest path, because if we move each drone on the graph directly from point A to point B, then we get the shortest path. Here we only need to handle the collision problem and answer the following question: how to handle the fact that a point of the matrix can be used by another drone and how to avoid this?


So we have a lot of options here, and a lot of different algorithms.
I invented several algorithms that were more complicated and not necessarily efficient enough. Finally I found two that actually work, and that were easy to implement.

As an example, I will present you with a problem and its solution.
If we generate a collision with a drone that has already reached its destination, what should we do?
We cannot wait for him to leave, because having already reached his destination, he will not move again.
It is also true that we can move around it, but we have found a better solution, which is easier to solve: we simply move the fixed drone one place, in order to let the mobile drone pass, then put the fixed drone back in its place.

If in this example it was not a drone, but a tree, then of course we could not move the tree, but only move around it.
This is why, when building an algorithm, one must always find the solution to a specific problem, and not just copy another algorithm that is designed to solve another problem.

Sometimes genius is simply finding the simplest, most efficient solution to the problem, not the most complex one.

It's also a golden rule: don't complicate things if you can simplify them!


A problem that is located in physical space could be solved using a graph, geometry or trigonometry. It is always necessary to perform a calculation to move an object in space.
Don't try to solve a problem in space using simple node algorithms, instead use a geometric solution if possible, which should give a faster and more performant solution.

For example, when it comes to getting around an obstacle, why not use parabolic functions? When it comes to finding a point on a parabola, I am convinced that mathematics offers solutions to multiple problems in space. You just need to know all the formulas. In any case, you can find solutions in very simple ways.

I have developed many solutions for this algorithm, but have only completed two of them.
I won't go into the details of the 2 algorithms, which I will probably do in one of the future articles.
The idea in this article is to explain to you how to solve a similar problem.

In summary:

1. Don't try to copy an existing algorithm if it doesn't exactly fit your need. Instead, try to find a solution to a specific situation.
2. Don't try brute force (testing all possibilities) on the first try, especially in cases like this where the solution can be found quickly just by moving straight as on a graph.
3. An algorithm issue goes beyond just writing code.
It's also about figuring out how to solve problems.
Be creative and try to find solutions as if you were in reality. Forget about the code for a bit and think of it as a game.
Try to represent all this concretely on a paper or also in real life. This is how you will be able to find a concrete solution to each problem (like moving the fixed drone and not trying to go around it).
First approach the question as if it were a real-life problem, and only then think about how you can code this.

In this article I present an example of an algorithm, but I would especially like to detail the different elements to take into account when building a robot.

If he is expected to be able to perform an action in space (move, manipulate something, etc.), this requires sophisticated skills in graphing, geometry and trigonometry, in order to know how to make him manipulate elements in space.

In robotics, we have absolutely no intention of reinventing calculations in space, since everything has already been said a long time ago. It is enough to learn mathematics and know how to use it to code.

Here are some examples of how calculations are used in space.

Movements in space of a robot or drone.
If I were to develop a tool like a robot lawnmower, the work would probably include graphical calculations, geometry, calculations in space, etc.

And why not use more complex formulas for robots? Not just distance on a graph or something like that, but for example parabolic formulas for moving around objects?

What about a driverless car? On construction sites, autonomous vehicles need algorithms to generate a navigation graph.
These algorithms are used to find the shortest collision-free routes within dynamic environments.
One approach is to use the “Visibility Graph”, which computes the entire graph and then actively searches for routes using algorithms like A* or Dijkstra.

It is possible to use this algorithm whenever we need to synchronize several elements with each other.
For example, you can do this in a studio if you want all the light to be able to move around the room.
Or on a performance stage, if you want all the elements to be able to move around the stage.
It might even make a choreography easier, allowing the different dancers to move from one place to another…
the algorithm can map the dance onto the stage.

This algorithm was specifically designed to synchronize drones as part of a light show…
But it could be used for any project that requires moving different elements within a given space.

Examples of use cases with multiple drones:

• Perimeter security

Testing anti-drone systems involves safeguarding airports, industrial facilities, and other essential infrastructure by concurrently deploying drones from various directions towards the secured target.

• Agriculture

Utilizing multiple drones to concurrently spray the crops in parallel.

• Mapping

Utilizing several drones concurrently for the mapping of extensive regions.

• Construction company

The incorporation of drones within the construction sector has marked the beginning of a new age characterized by enhanced efficiency, precision, and safety across the different stages of construction projects.

• The Promise of Aerial Filmmaking through Drones in the Film and Entertainment Sector.

In recent years, the film and entertainment sector has experienced a significant increase in the utilization of drones for cinematographic purposes. The capacity to obtain breathtaking aerial imagery from an elevated perspective has transformed the methods employed in the filming of movies and television programs. Additionally, drones are employed to enhance the concert experience, being programmed to elevate on-site visuals through spectacular light displays, coordinated drone movements, and comprehensive 360-degree documentation.