Newer
Older
imgURL_disclaimer: "Image from https://www.hippopx.com/en/signposts-directory-path-direction-paths-direction-trail-target-direction-384390, License to use Creative Commons Zero - CC0"
excepit: "Optimized algorithm for finding designated path"
keywords: "Distribution, modelling"
affiliation: "Ghindea Ioana-Sinziana, Ionescu Radu, Zavacki Raul"
video_embed: '<iframe width="560" height="315" src="https://www.youtube.com/embed/w7sCaVkvcDE" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>'
<iframe width="560" height="315" src="https://www.youtube.com/embed/w7sCaVkvcDE" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>
Drohnen werden heutzutage immer häufiger bei verschiedenen Aktivitäten wie Videoproduktion oder bei der Lieferung von kleineren Dingen eingesetzt.
Unser Ziel ist die Lieferung von Honig in der ganzen Welt und das wollen wir durch Drohnen erreichen. Drohnen sind intelligent genannt, wenn sie von Stelle A zur Stelle B sich bewegen, ohne die Hilfe von einem Menschen zu brauchen.
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
Wir haben Unity 3D gewählt, um zu simulieren, wie unsere Drohnen fliegen.
Am Anfang haben wir eine kleine Karte mit zwei Drohnen, ein paar Baume und zwei Hauser, die mit A und B markiert sind, entwerft. Unser Ziel ist, dass die Drohnen von Stelle A zur Stelle B der kleine Abstand finden und von A zu B ankommen. Die Karte wurde mit Hilfe von Asset Store erstellt.
Der nächste Schritt ist zu definieren, wie unsere Drohnen von einem Punkt zu dem anderen fliegen. Dafür haben wir 2 Entscheidungen getroffen: einen NavMesh zu erstellen oder WayPoints zu bauen. Jede Entscheidung hat sowohl Vorteile als auch Nachteile.
NavMesh
NavMesh ist eine Klasse, die verwendet werden kann, um räumliche Abfragen wie Pathfinding und Begehbarkeitstests durchzufuhren, die Pathfinding Costs für bestimmte Gebietstypen festzulegen und das globale Verhalten der Pfadfindung und Vermeidung zu optimieren.
Das NavMesh wird in der Szene als blaue Überlagerung auf der darunterliegenden Ebenengeometrie angezeigt, wenn das Navigationsfenster geöffnet und sichtbar ist.
Der NavMesh stellt den Bereich dar, in dem sich das Zentrum des Agenten bewegen kann. Konzeptionell spielt es keine Rolle, ob Sie den Agenten als Punkt auf einem geschrumpften NavMesh oder als Kreis auf einem NavMesh in voller Große betrachten, da beide gleichwertig sind. Die Punktinterpretation ermöglicht jedoch eine bessere Laufzeiteffizienz und ermöglicht es dem Designer auch sofort zu sehen, ob sich ein Agent durch Lücken hindurchzwangen kann, ohne sich um seinen Radius kümmern zu müssen.
WayPoints (Wegpunkte)
WayPoints im Sinne der Wegfindung sind Positionen in einer Ebene, die ein Wegfindungssystem verwendet, um Bereiche der Ebene zu verbinden. Bei der normalen Wegfindung werden sie im Wesentlichen verwendet, um einer AI zu sagen, wie sie von Punkt A zu Punkt B kommt, ohne durch Wände zu gehen oder eine Route zu nehmen, die einem Spieler unvernünftig erscheint. Wegpunkt-Taktik ist die Idee, Wegpunkten mehr Informationen zu geben, damit die AI komplexere und fundiertere Entscheidungen treffen kann. Beispiele für Wegpunkte sind Scharfschutznnester und Orte, die sicher geheilt werden können. Diese Art von System ist für Designer wahnsinnig hilfreich, da sie wichtige Interessenpunkte in der Ebene platzieren können, wo immer sie mochten, ohne dass die Programmierer für jedes von ihnen neue Systeme implementieren müssen. Es macht auch die Kontrolle der Gewohnheiten größerer Gruppen von AI viel einfacher.
A*
Die Implementierung des Haupt-Laufzeit-Pfadfindungsalgorithmus erfordert wenige Hilfsmethoden.
Erstens benötigen wir eine Methode, die die Spielweltposition des Charakters in die Zellenposition in einem Raster umwandelt. Dies ist wichtig, da wir die Position der Zelle innerhalb unseres Gitters kennen müssen, zu der wir unseren Weg berechnen mochten. Zu diesem Zweck verwenden wir die integrierte Tilemap-Membermethode „WorldToCell()” und extrahiere die erforderlichen Zelldaten, die in meiner Datenstruktur gespeichert sind.
Zweitens brauchen wir eine Funktion, die den Abstand zwischen zwei beliebigen Zellen in einem Raster zurückgibt. Wie wir uns aus dem vorherigen Artikel erinnern, muss der Algorithmus möglicherweise die Kosten einer bestimmten Zelle anpassen, wenn sie auf einem kürzeren Pfad als dem bereits festgelegten liegt.
Drittens müssen wir die Reihenfolge der Zellen umkehren, die einen endgültigen Pfad bilden, den der Algorithmus gefunden hat. Dies soll unseren Feind dazu bringen, dem Weg vom Anfang bis zum Ende zu folgen, anstatt umgekehrt.
Als nächstes steht eine Methode, mit der wir einen Abstand zwischen zwei beliebigen Zellen ermitteln werden. Wir verwenden die Kosten der Bewegungen, um die Summen zu berechnen. Diese basieren auf der Anzahl der einzelnen Bewegungen, die der Algorithmus ausführen muss, um eine Zelle von einer anderen Zelle aus zu erreichen.
Das Core von Pfadfindung-Algorithmus ist in dem nächsten Bild dargestellt.
Wir haben A* Algorithmus in drei verschiedenen Arten implementiert:
Naiv: durch WayPoints (Wegpunkte) - jede Drohne kommt zu einem Transferpunkt an und hat ein Easybox, wo sie den Honig geliefert wird, zugewiesen. Die Wegpunkt werden (manuell) von uns hinzugefügt und sie bedeuten ein schon definierter Weg.
Smart distance: In der zweiten Methode wird der Abstand zu einem bestimmten Lieferungspunkt berechnet. Die Methode liefert basierend sowohl auf die Verfügbarkeit der Drohnen als auch der Produkte. Zum Beispiel: Wenn wir drei Bestellungen bekommen und zwei davon sind ganz eng zueinander, eine Drohne liefert die Produkte zu den Orten, die nahe zueinander sind. Eine andere Drohne liefert die Produkte zu dem gebliebenen Ort.
Smart priority: Diese Methode ist ähnlich zu dem Smart Distance-Methode, aber zusätzlich basiert sich die Lieferung auch auf einer Priorität, die als Parameter gegeben wird. Smart Priority-Methode ist besonders wichtig, wenn der Kunde eine so schnell wie mögliche Lieferung verlangt.
C# Service
Der C# Service ist verwendet innerhalb unseres Unternehmens von Mitarbeitern. Es hat eine Schnittstelle, welche die Verbindung zwischen unsere Datenbank und Bestellungen ist. Hier in dieser Schnittstelle, wir als Besteller, können Bestellungen hinzufügen und diese sind gespeichert in unserer Datenbank. Von der Datenbank, unsere Mitarbeiter nehmen die Daten (Informationen) und bereiten die Drohnen mit der Bestellungen. Nachher senden die Mitarbeiter die Drohnen zu der Lieferungsstelle.
Wir haben .NET framework verwendet, um dieses Service zu erstellen. .Net ist eine freie, cross-platform, open source Entwicklungsplattform für Bauen von verschiedenen Typen von Anwendungen. .Net wird von Microsoft unter Windows, macOS und Linux unterstützt. Es wird regelmäßig am zweiten Dienstag im Monat aus Sicherheits- und Qualitätsgründen aktualisiert. .NET Binärdistributionen von Microsoft verwalteten Servern in Azure erstellt und getestet und folgen das Engineering und Sicherheitspraktiken von Microsoft.
A diagram of .NET Framework Architecture with ASP.NET displayed. | Download Scientific Diagram
ASP.net
ASP.NET ist ein kostenloses Web-Framework zum Erstellen großartiger Websites und Webanwendungen mit HTML, CSS und JavaScript. Sie können auch Web-APIs erstellen und Echtzeittechnologien wie Web Sockets verwenden.ASP.NET Core ist eine Alternative zu ASP.NET.
In ASP.net haben wir zwei Services erstellt. Eins davon ist “DroneService”, das die Bestellungen bearbeitet und die Route, die von den Drohnen gewählt wird, bis zu der Kunde. Das zweite Service beschäftigt sich mit der Bestellung Aufnahme. Das besitzt eine graphische Schnittstelle, die mit Hilfe von Angular implementiert wurde.