Erläuterung des Algorithmus zur Trajektorienplanung für mehrere Drohnen.

Wenn Sie versuchen, einen Algorithmus zur Pfadsuche für mehrere Drohnen zu entwickeln!

Haben Sie schon einmal gesehen, wie ein Roboter „in der Realität“ funktioniert?
Haben Sie darüber nachgedacht, wie man ein Objekt – per Definition unbeweglich – im Raum bewegt?
Wie bewegt man ihre Finger, wie bringt man sie dazu, sich vorwärts zu bewegen?
Wie ermöglicht man es beispielsweise, dass Drohnen fliegen können?

Diese Aufgabe ist herausfordernd, da jeder Schritt und jede Bewegung sorgfältig geplant und im Rahmen einer umfassenden und langfristigen Perspektive codiert werden muss.

Was versteht man unter einem „autonomen Navigationsalgorithmus“?

Es handelt sich um eine Sammlung von Techniken und Methoden, die von Robotern oder Fahrzeugen eingesetzt werden, um sich fortzubewegen und Aufgaben ohne menschliches Eingreifen auszuführen.
Dieser Algorithmus ermöglicht es ihnen, ihre Umgebung zu beobachten, sich zu orientieren, Entscheidungen zu treffen und zu handeln.
Diese Algorithmen sind darauf ausgelegt, die Sicherheit und Effizienz bei der Ausführung der ihnen übertragenen Aufgaben zu gewährleisten.

Lassen Sie uns das Thema etwas ausführlicher betrachten.
Alles, was mit dem Raum zu tun hat, ist relativ einfach – einfacher beispielsweise als das maschinelle Lernen, da es lediglich auf geometrischen Berechnungen, Graphberechnungen oder trigonometrischen Berechnungen basiert.
Diese Berechnungen sind tatsächlich wesentlich präziser und ermöglichen es, eine vollständige Lösung für ein gegebenes Problem zu finden. Dies steht in keinem Zusammenhang mit dem Versuch, das menschliche Gehirn, seine Denkweise und Intelligenz nachzuahmen.
Dies ist die Überzeugung, die aus einer meiner Erfahrungen entstanden ist, bei der ich versuchte, einen Algorithmus zur Trajektorienbestimmung für Drohnen zu entwickeln.

Dieses Trajektorien-Suchalgorithmus wurde für eine Lichtshow in Auftrag gegeben.
Das Ziel bestand darin, eine Route zu entwickeln, die es allen Drohnen ermöglicht, sich innerhalb eines gemeinsamen Raumes zu bewegen, ohne dass es zu Kollisionen zwischen ihnen kommt.
Der Algorithmus sollte es ermöglichen, die Drohnen von einem Ort zum anderen zu bewegen und auf diese Weise das Lichtspiel zu erzeugen.

Der Algorithmus ermöglicht es mehreren Drohnen, sich innerhalb desselben Raums von Punkt A nach Punkt B zu bewegen, ohne miteinander zu kollidieren.

Angesichts der Tatsache, dass bereits ein Algorithmus zur Trajektorienbestimmung für Drohnen existiert, erschien es mir sinnvoll, diesen zu nutzen.

Die ursprüngliche Idee bestand darin, eine dreidimensionale Matrix zu schaffen. Hierbei wird der Raum in Quadrate unterteilt, wobei jedes Quadrat die Größe des Drohnen sowie den Sicherheitsbereich umfasst.

Zunächst bewegen wir die Drohne schrittweise, jeweils in eine Dimension, und setzen ein Flagge in der Matrix, um anzuzeigen, dass der Ort besetzt ist. Auf diese Weise informieren wir die anderen Drohnen, dass sie sich nicht in diesen Bereich bewegen sollen.

Man kann diesen Graphen einfach berechnen: x + 1 oder y + 1 oder z + 1.

Die gegenwärtig verwendeten Navigationsalgorithmen für den Flug von Drohnen bestehen darin, die Route im Raum zu bestimmen, die es ermöglicht, vom Punkt A zum Punkt B zu gelangen, wobei der Algorithmus eingesetzt wird, um den kürzesten Weg zu ermitteln.

Um dies zu erreichen, unterteilen wir den Raum in Würfel. Jeder Würfel stellt einen Knoten dar, und jeder Knoten ist mit allen anderen Knoten verbunden, die sich in seiner physischen Nähe befinden. In einem Graphen ist beispielsweise x mit x + 1 verbunden, und so weiter.

Man versucht anschließend, den kürzesten Weg zwischen dem Knoten A und dem Knoten B zu ermitteln.
Der Dijkstra-Algorithmus dient dazu, den kürzesten Weg zwischen einem bestimmten Knoten (dem sogenannten „Startknoten“) und anderen Knoten im Graphen zu ermitteln. Dieser Algorithmus nutzt die Gewichte der Kanten, um den Pfad zu finden, der die Gesamtdistanz (Gewicht) zwischen dem Startknoten und den anderen Knoten am stärksten verringert.

Dieser Algorithmus hat keine Lösung für das aufgeworfene Problem geliefert.

Hier ist der Algorithmus anders. Wir müssen nicht den spezifischen Trajektorienalgorithmus für einen einzelnen Drohnen verwenden, sondern einen Algorithmus finden, der es ermöglicht, alle Drohnen miteinander zu synchronisieren.
Darüber hinaus benötigen wir im physischen Raum nicht den Knotenalgorithmus, sondern sollten stattdessen Graphfunktionen verwenden. Auf diese Weise können wir die Verbindungslinie zwischen zwei Punkten im Graphen berechnen und den nächsten Punkt mühelos finden. Um sich effizient von Punkt A nach Punkt B innerhalb eines Graphen zu bewegen, können wir dies schrittweise in einer Dimension tun: x+y, y+1, z+1.

Es ist ebenfalls möglich, den Weg zu finden, indem man sich in jedem Schritt um drei Dimensionen bewegt und die Distanz D in einem 3D-Grafen berechnet. Auf diese Weise kann man für jeden Schritt den nächsten Punkt unter Verwendung der Formel D ermitteln. Dadurch wird der Weg verkürzt, da man nicht in jeder Dimension einzeln voranschreitet, was x + 1, y + 1, z + 1 entspricht. Dies bedeutet, dass man sich nach oben, unten, rechts oder links, vorne oder hinten bewegt, wie im Diagramm dargestellt, und direkt zum Ziel gelangt. Um dies zu erreichen, müssen wir den nächsten Punkt unter Berücksichtigung der Distanzberechnung und der Schrittweite bestimmen. Diese Lösung wurde nicht in den Algorithmus integriert, stellt jedoch eine Verbesserungsidee dar, die teilweise umgesetzt wurde. Daher könnte ich Ihnen mitteilen, ob sie ohne weitere Probleme erfolgreich sein wird.
Es ist ebenfalls nicht erforderlich, den kürzesten Weg zu suchen, indem man alle Möglichkeiten prüft, da ein Drohne in der Regel warten oder sich bewegen muss, oder ein anderer Drohne ausweichen muss. Daher spielt es keine Rolle, um welche Drohne es sich handelt.
Der direkteste Weg führt also geradewegs zur Zieladresse, gefolgt von der Lösung des Kollisionproblems.
Im Allgemeinen wird für alle Drohnen der kürzeste Weg angestrebt, und es ist möglich, einen Algorithmus sehr schnell zu entwickeln, ohne auf eine brute-force-Methode (das Testen aller Möglichkeiten durch Rekursion) oder eine ähnliche Vorgehensweise zurückgreifen zu müssen.

Die Lösung besteht darin, einen Algorithmus zu entwickeln, der alle Drohnen miteinander synchronisiert. Zu diesem Zweck werden wir grafische Funktionen einsetzen.

Zusätzlich ist es nicht erforderlich, alle Knoten zu überprüfen, um den kürzesten Weg zu bestimmen. Wenn jeder Drohne direkt von Punkt A nach Punkt B auf dem Graphen bewegt wird, ergibt sich der kürzeste Weg. Hier müssen wir lediglich das Problem der Kollisionen bewältigen und die folgende Frage beantworten: Wie kann verhindert werden, dass ein Punkt in der Matrix von einer anderen Drohne genutzt wird?

Wir haben hier tatsächlich eine Vielzahl von Optionen und eine große Anzahl unterschiedlicher Algorithmen.
Ich habe mehrere komplexere Algorithmen entwickelt, die jedoch nicht unbedingt effizient genug waren. Letztendlich habe ich zwei gefunden, die tatsächlich funktionieren und einfach umzusetzen sind.

Als Beispiel werde ich Ihnen ein Problem sowie dessen Lösung vorstellen.
Wenn eine Kollision mit einem Drohnen auftritt, die bereits ihr Ziel erreicht hat, welche Maßnahmen sollten dann ergriffen werden?
Man kann nicht darauf warten, dass er geht, denn nachdem er bereits sein Ziel erreicht hat, wird er sich nicht mehr bewegen.
Es ist ebenfalls möglich, sich um ihn herum zu bewegen, jedoch haben wir eine bessere und einfachere Lösung gefunden: Man muss lediglich den stationären Drohnenstandort ändern, um der mobilen Drohne den Durchgang zu ermöglichen, und anschließend die stationäre Drohne wieder an ihren ursprünglichen Platz zurücksetzen.

Wenn in diesem Beispiel kein Drohne, sondern ein Baum vorhanden wäre, könnte man den Baum selbstverständlich nicht versetzen, sondern lediglich um ihn herum bewegen.
Deshalb ist es wichtig, beim Entwurf eines Algorithmus stets eine Lösung für ein spezifisches Problem zu entwickeln, anstatt lediglich einen bestehenden Algorithmus zu übernehmen, der für ein anderes Problem konzipiert wurde.

Manchmal besteht Genialität darin, die einfachste und effektivste Lösung für ein Problem zu finden, anstatt die komplexeste.

Es ist ebenfalls eine goldene Regel: Verkomplizieren Sie die Dinge nicht, wenn Sie sie vereinfachen können!


Ein Problem, das im physischen Raum auftritt, kann durch den Einsatz von Graphen, Geometrie oder Trigonometrie gelöst werden. Es ist stets erforderlich, Berechnungen anzustellen, um ein Objekt im Raum zu bewegen.
Versuchen Sie nicht, ein Problem im Raum mit einfachen Knotenantalgorithmen zu lösen. Nutzen Sie stattdessen, wenn möglich, eine geometrische Lösung, da dies in der Regel zu einer schnelleren und effizienteren Lösung führt.

Wenn es darum geht, ein Hindernis zu umgehen, warum sollten wir nicht die parabolischen Funktionen nutzen? Bei der Suche nach einem Punkt auf einer Parabel bin ich überzeugt, dass die Mathematik Lösungen für zahlreiche Probleme im Raum bereitstellt. Es ist lediglich erforderlich, alle Formeln zu kennen. Nichtsdestotrotz lassen sich Lösungen auf sehr einfache Weise finden.

Ich habe zahlreiche Lösungen für diesen Algorithmus entwickelt, jedoch habe ich lediglich zwei davon abgeschlossen.
Ich werde nicht auf die Einzelheiten der beiden Algorithmen eingehen, was ich wahrscheinlich in einem der zukünftigen Artikel tun werde.
Die Absicht dieses Artikels besteht darin, Ihnen zu erläutern, wie Sie ein ähnliches Problem lösen können.
Zusammenfassend lässt sich sagen:

1. Versuchen Sie nicht, einen bestehenden Algorithmus zu kopieren, wenn er nicht genau Ihren Anforderungen entspricht. Suchen Sie stattdessen nach einer Lösung für eine spezifische Situation.
Versuch nicht, die brute Kraft (das Testen aller Möglichkeiten) beim ersten Versuch anzuwenden, insbesondere in Fällen wie diesem, wo die Lösung schnell gefunden werden kann, indem man einfach geradeaus wie auf einem Graphen geht.
1. Ein Algorithmusproblem ist nicht lediglich eine Angelegenheit des Codes.
Es besteht auch darin, Wege zur Lösung von Problemen zu finden.
Seien Sie kreativ und versuchen Sie, Lösungen zu finden, als ob Sie sich in der Realität befinden. Vergessen Sie vorübergehend den Code und betrachten Sie dies alles als ein Spiel.
Versuchen Sie, all dies konkret auf Papier oder auch im realen Leben darzustellen. Nur so können Sie eine greifbare Lösung für jedes Problem finden, wie beispielsweise das Bewegen des feststehenden Drohnen anstatt zu versuchen, sie zu umgehen.
Zunächst sollten Sie die Fragestellung betrachten, als ob es sich um ein reales Problem handelt. Erst danach sollten Sie darüber nachdenken, wie Sie dies programmatisch umsetzen können.

In diesem Artikel präsentiere ich ein Beispiel für einen Algorithmus, möchte jedoch insbesondere die verschiedenen Aspekte erläutern, die bei der Konstruktion eines Roboters zu berücksichtigen sind.

Wenn von ihm erwartet wird, dass er eine Handlung im Raum ausführen kann (sich bewegen, etwas manipulieren usw.), erfordert dies ausgefeilte Fähigkeiten in den Bereichen Graphentheorie, Geometrie und Trigonometrie, um zu verstehen, wie er Objekte im Raum handhaben kann.

In der Robotik haben wir keineswegs die Absicht, Berechnungen im Raum neu zu erfinden, da bereits vor langer Zeit alles dazu gesagt wurde. Es genügt, die Mathematik zu erlernen und zu wissen, wie man sie zur Programmierung anwendet.

Hier sind einige Beispiele für die Anwendung von Berechnungen im Raum.

Bewegungen im Raum eines Roboters oder eines Drohnen.
Wenn ich ein Werkzeug wie einen Rasenmähroboter entwickeln müsste, würde die Arbeit wahrscheinlich grafische Berechnungen, Geometrie, räumliche Berechnungen und ähnliches umfassen.

Warum sollten wir nicht komplexere Formeln für Roboter verwenden? Anstatt uns lediglich auf die Distanz in einem Graphen oder Ähnliches zu beschränken, könnten wir beispielsweise parabolische Formeln nutzen, um sich um Objekte zu bewegen.

Und was ist mit einem fahrerlosen Auto?
Auf Baustellen benötigen autonome Fahrzeuge Algorithmen zur Erstellung eines Navigationsgraphen. Diese Algorithmen dienen dazu, die kürzesten kollisionsfreien Routen in dynamischen Umgebungen zu ermitteln. Eine der Methoden besteht darin, den „Visibility Graph“ (Sichtbarkeitsgraph) zu verwenden, der den gesamten Graphen berechnet und anschließend aktiv Routen mithilfe von Algorithmen wie A* oder Dijkstra sucht.

Es ist möglich, diesen Algorithmus jedes Mal zu verwenden, wenn mehrere Elemente synchronisiert werden müssen. Beispielsweise kann dies in einem Studio geschehen, wenn man möchte, dass das gesamte Licht in den Raum bewegt werden kann. Auch auf einer Bühnenaufführung kann dieser Algorithmus eingesetzt werden, um sicherzustellen, dass sich alle Elemente auf der Bühne bewegen können.
Darüber hinaus könnte er möglicherweise eine Choreografie erleichtern, indem er den verschiedenen Tänzern ermöglicht, sich von einem Ort zum anderen zu bewegen. Der Algorithmus kann die Bewegungen der Tänzer auf der Bühne kartografieren.

Dieser Algorithmus wurde speziell entwickelt, um Drohnen im Rahmen einer Lichtshow zu synchronisieren.
Es könnte jedoch im Rahmen eines beliebigen Projekts eingesetzt werden, das die Bewegung verschiedener Elemente innerhalb eines bestimmten Raums erfordert.

Beispiele für Anwendungsfälle mit mehreren Drohnen:

Sicherheitsbereich

Die Prüfung von Anti-Drohnen-Systemen, die Flughäfen, Industrieanlagen und andere kritische Infrastrukturen schützen, erfolgt durch das gleichzeitige Senden von Drohnen aus verschiedenen Richtungen in den zu schützenden Bereich.

Agrarwirtschaft

Es ist möglich, verschiedene Kulturen gleichzeitig parallel mit mehreren Drohnen zu besprühen.

Kartographie

Die gleichzeitige Kartografierung großer Flächen unter Einsatz mehrerer Drohnen.

Bauunternehmen.

Die Integration von Drohnen in die Bauindustrie hat eine neue Ära in Bezug auf Effizienz, Präzision und Sicherheit während der verschiedenen Phasen von Bauprojekten eingeleitet.

Topographische Projekte.

Geländekartierung.

Sicherheit und Überwachung.

Gemeinsame Nutzung mehrerer Drohnen zu Inspektionszwecken.

• Überprüfung von Vermögenswerten.

Drohnen sind in der Lage, detaillierte visuelle Inspektionen verschiedener Objekte durchzuführen, um schnell Mängel wie Risse, strukturelle Probleme, Leckagen, beschädigte Dachziegel, Korrosion und ähnliche Defekte zu identifizieren.

. Dachinspektion.

Dieses Luftsystem eignet sich besonders gut für die Inspektion von Dächern. Drohnen können Bereiche erreichen, die für den Menschen unzugänglich sind. Dies verringert oder beseitigt das Verletzungsrisiko und stellt zudem eine erhebliche Zeitersparnis dar.

• Elektrizitätswerk, Übertragung und Verteilung.

Die Drohnentechnologie ermöglicht die Überprüfung der ordnungsgemäßen Funktion von Übertragungsleitungen. Die Betreiber haben die Möglichkeit, Störungen vom Boden aus zu analysieren, bevor sie zur Behebung der Probleme hinaufsteigen. Somit steigern Drohnen die Effizienz und Schnelligkeit der Wartungsarbeiten.

• Überprüfung der Telekommunikations- und Rundfunktürme.

Die Inspektion von Türmen mittels Drohnen ermöglicht die Erfassung hochauflösender Bilder zur Beurteilung der Betriebsbedingungen, wodurch Unternehmen die Ergebnisse analysieren und fundierte Entscheidungen treffen können.

• Erdöl- und Erdgasindustrie

Drohnen sind in der Lage, Öl- und Gasanlagen zu inspizieren, wodurch konsolidierte Daten schneller erlangt werden können. Dies trägt zur Verlängerung der Lebensdauer der Anlagen bei und verringert gleichzeitig die Risiken sowie die Ausfallzeiten.

• Abfallbewirtschaftung

Drohnen, die in der Abfallwirtschaft eingesetzt werden, können zahlreiche Abläufe vereinfachen, insbesondere das Einsammeln von Müll und die Überwachung von Deponien. Zudem können sie zur Reinigung von Abfallbehältern sowie zur Identifizierung und Sammlung von zu entsorgendem Müll verwendet werden.

• Straßensicherheit.

Die Verwendung von Drohnen im Bereich der Verkehrssicherheit umfasst die Risikobewertung, die Durchführung umfassender Untersuchungen zu Unfällen sowie die allgemeine Überwachung des Straßennetzes.

• Überwachung und Verkehrsmanagement.

Drohnen werden zur Überwachung und Verfolgung des Verkehrs eingesetzt. Verkehrsdaten – sowohl online als auch offline – werden aus den Videodaten der Drohnen extrahiert, um die Mechanismen zur Verfolgung und Verwaltung des Verkehrs zu optimieren.

• Verwaltung der Autobinfrastruktur

Die Drohnentechnologie wird eingesetzt, um die Überwachung und Verwaltung von Straßeninfrastrukturen zu unterstützen. Besonders hervorzuheben ist ihr Einsatz bei der Inspektion von Brücken sowie der Erkennung von Schäden an der Fahrbahn.

• Landwirtschaft

Die in der Landwirtschaft eingesetzten Drohnen ermöglichen es Landwirten, Forschern und Dienstleistern, ihre Felder schnell und effizient zu überwachen, das Pflanzenwachstum zu verfolgen, Stresszustände zu identifizieren, Behandlungspläne zu erstellen und vieles mehr.

• Umwelt

Die Drohnentechnologie stellt die schnellste, sicherste und kosteneffektivste Methode dar, um große Flächen im Rahmen von Umweltstudien, -schutz und -management zu kartieren und zu überwachen. Dies ist besonders vorteilhaft in gefährlichen und schwer zugänglichen Gebieten für Menschen und Fahrzeuge.

• Natürliche Risiken und Naturkatastrophen.

Drohnen ermöglichen eine schnelle Intervention vor Ort im Falle von Naturkatastrophen, und zwar in einem ungleich schnelleren Tempo als die manuelle Erkennung, Analyse und Intervention. Ihr Einsatz verringert erheblich die Reaktionszeit auf Katastrophen und somit auch das potenzielle Ausmaß der Schäden. Ausgestattet mit Sensoren wie Infrarot können Drohnen Personen in Not präzise lokalisieren und visuell identifizieren, um ihnen anschließend medizinisches Material, Medikamente, Ausrüstung und Nahrung bereitzustellen sowie sie zu retten.

• Forstwirtschaft.

Drohnen werden eingesetzt, um sowohl natürliche Wälder als auch von Menschenhand geschaffene Wälder zu kartieren. Dadurch werden präzise und relevante Daten für die Analyse der Baumgesundheit, die Zählung der Bäume, die Schätzung der Biomasse, die Berechnung des Kronenindex und die Verwaltung von Plantagen bereitgestellt.

• Das Potenzial der Drohnenfilmografie in der Film- und Unterhaltungsindustrie.

In den letzten Jahren hat die Film- und Unterhaltungsindustrie einen signifikanten Anstieg der Nutzung von Drohnen zur Filmproduktion verzeichnet. Die Fähigkeit, beeindruckende Luftaufnahmen aus der Vogelperspektive zu erstellen, hat die Art und Weise, wie Filme und Fernsehsendungen gedreht werden, revolutioniert.