[Expertenkommentar]: Genetische Algorithmen sind hochgradig parallele, stochastische und adaptive Suchalgorithmen, die auf den Mechanismen der natürlichen Selektion und Evolution in der Biologie basieren. Sie eignen sich besonders für die Lösung komplexer und nichtlinearer Probleme, mit denen traditionelle Suchalgorithmen Schwierigkeiten haben. In diesem Beitrag wird ein genetischer Algorithmus zur Planung des Hindernisvermeidungspfads eines Tiefseebergbau-LKW eingesetzt. Der Ansatz und der Prozess werden detailliert erläutert. Die Ergebnisse, die durch Computersimulationen erzielt wurden, belegen die Machbarkeit des Verfahrens. Dieser Beitrag stellt einen vielversprechenden und effektiven Versuch dar, fortgeschrittene Regelungsalgorithmen im Bereich der Automatisierung anzuwenden.
Zusammenfassung:
Diese Arbeit untersucht hauptsächlich die Methode und den Ansatz zur Nutzung genetischer Algorithmen für die Hindernisvermeidungs-Pfadplanung von Tiefsee-Bergbaufahrzeugen. Die kontinuierlichen Pfade werden diskretisiert, und Zufallszahlen simulieren die Population jedes Pfades. Die zweidimensionalen Pfade werden in eindimensionale Pfade transformiert, wodurch einfache Pfadgene entstehen. Eine physikalisch sinnvolle Fitnessfunktion und entsprechende Mutationsoperatoren werden vorgeschlagen, um den genetischen Algorithmus schnell zur optimalen Lösung zu führen. Experimentelle Simulationen zeigen, dass der Algorithmus den benötigten optimalen Pfad schnell und stabil finden kann.
Schlüsselwörter: Mobiler Roboter, Genetischer Algorithmus, Pfadplanung zur Hindernisvermeidung
Zusammenfassung: In dieser Arbeit wird ein auf einem genetischen Algorithmus basierendes Pfadplanungsverfahren für mobile Roboter unter Berücksichtigung von Hindernissen in der Umgebung analysiert und entwickelt. Der kontinuierliche Pfad wird durch Streupunkte simuliert und durch Zufallszahlen repräsentiert. Der zweidimensionale Pfad wird auf eine Dimension reduziert, um ein einfaches Pfadgen zu erzeugen. Das Verfahren beinhaltet eine Fitnessfunktion mit expliziten physikalischen Modellen und einen entsprechenden Mutationsoperator, sodass der genetische Algorithmus schnell zu einem optimalen Ergebnis führt. Die Experimente zeigen, dass dieser Algorithmus schnell und zuverlässig einen optimalen Pfad findet. Schlüsselwörter: Mobiler Roboter, Genetischer Algorithmus, Pfadplanung
1. Einleitung
Bei der Navigation und Steuerung von Tiefseebergbaufahrzeugen ist die Pfadplanung von entscheidender Bedeutung. Die Hauptaufgabe der Pfadplanung für Tiefseebergbaufahrzeuge besteht darin, in einer Umgebung mit Hindernissen gemäß bestimmter Bewertungskriterien einen kollisionsfreien Pfad vom Ausgangszustand zum Zielzustand zu finden.
Im Allgemeinen gibt es viele Wege, die der Muldenkipper befahren kann, aber in der Realität muss der Muldenkipper einen optimalen Weg finden, der Hindernissen ausweicht und mit dem geringsten Aufwand (z. B. Zeit) zum vorgegebenen Weg zurückkehrt.
Die Routenplanung für Muldenkipper im Bergbau stellt ein schwieriges, nichtlineares Problem dar. Herkömmliche Optimierungsstrategien sind komplex und zeitaufwändig[1], weshalb sie sich nur schwer für die Echtzeitnavigation von Muldenkippern eignen.
Der in diesem Artikel vorgeschlagene Pfadplanungsalgorithmus verwendet einen einfachen genetischen Code und verfügt über eine Fitnessfunktion mit einer klaren physikalischen Bedeutung.
Computersimulationen haben gezeigt, dass diese Methode das Problem der Pfadplanung für Tiefseebergbau-LKW in dynamischen Umgebungen lösen kann.
2. Ein auf einem genetischen Algorithmus basierendes Pfadplanungsverfahren für Tiefseebergbau-Lkw
2.1 Pfadkodierungsverfahren
Die Umwandlung der Problemlösung in ein Chromosom eines Kodierungsausdrucks und die damit verbundene Erleichterung nachfolgender Optimierungsoperationen unter Berücksichtigung von Nebenbedingungen ist die zentrale Herausforderung genetischer Algorithmen. Die Länge der Kodierungszeichenkette und der Suchraum sind für die Systemgeschwindigkeit von entscheidender Bedeutung [2]. Daher muss ein einfaches und praktisches Kodierungsverfahren entwickelt werden, um die Planungszeit zu verkürzen und eine Echtzeitsteuerung zu ermöglichen. In realen Bewegungen sind die Pfadpunkte zweidimensional. Eine Dimensionsreduktion der Pfadkoordinatenpunkte führt zu einer deutlichen Steigerung der Berechnungsgeschwindigkeit. In dieser Arbeit wird das Koordinatensystem XOY verwendet, dessen Ursprung mit dem Startpunkt übereinstimmt und dessen X-Achse auf der Verbindungsgeraden zwischen Start- und Zielpunkt liegt. Die Verbindungsgeraden werden in zwei gleich große Abschnitte Xj (j = 1, 2, …, n-2) unterteilt. Durch jeden Abschnitt Lj wird eine Gerade Lj senkrecht zur X-Achse gezogen. Auf jedem Abschnitt Lj wird zufällig ein Punkt Pj ausgewählt, sodass insgesamt n-2 Punkte entstehen. Seien Po und Pn-1 der Start- bzw. Endpunkt, wie in der folgenden Abbildung dargestellt: Pfadkodierungsdiagramm
Die y-Koordinaten jedes Punktes seien yi,j, wodurch ein zufälliger Pfad Rj entsteht. Dieser Pfad wird anschließend in eine eindimensionale y-Koordinatenkodierung umgewandelt. Die Kodierung verwendet Gleitkommazahlen, wie im folgenden Diagramm dargestellt: yi,o im Diagramm repräsentiert die aktuelle y-Koordinate des mobilen Roboters und yi,n-1 die y-Koordinate des Zielpunkts des Roboters. Der Pfad lautet:
2.2 Bestimmung der Fitnessfunktion
Die Wahl der Fitnessfunktion beeinflusst direkt die Konvergenzgeschwindigkeit und den Erfolg des genetischen Algorithmus. Unter Berücksichtigung der Eigenschaften des jeweiligen Problems sollte die Fitnessfunktion folgende Faktoren berücksichtigen:
2.2.1 Pfadlänge
Die Pfadlängenmetrikfunktion ist wie folgt definiert:
2.2.2 Pfadglätte
Die Pfadglättungsindexfunktion wird in diesem Artikel definiert.
Bei der Planung muss der Einfluss der Pfadglätte auf die Bewegungsleistung des Roboters berücksichtigt werden. Beim Drehen des Roboters sollte der Winkel so klein wie möglich sein, weshalb sich der generierte Pfad möglichst gleichmäßig ändern muss. Daher sind Gene mit geringeren kumulativen Drehwinkeldifferenzen φ(vi) überlegen.
2.3 Pfadsicherheit und entsprechende Strafstrategien
Vor der Entwicklung der Sicherheitsstrategie wird zunächst angenommen, dass die Anzahl und Position der Hindernisse durch die am Roboter installierten Sonarsensoren erfasst wurden. Ziel der Strafstrategie ist es, einen sicheren, kollisionsfreien Pfad zu erstellen, indem der geplante Pfad des Roboters mit dem Hindernisabdeckungsbereich verglichen wird. Ein solcher Pfad muss gewährleisten, dass kein Teil des Roboters mit einem Hindernis kollidiert; das heißt, der Abstand zwischen Roboter und Hinderniskante muss größer als der minimale Sicherheitsabstand sein, d. h.: Mi∩O=0
Dabei ist Mi eine bestimmte Bewegungstrajektorie des Roboters; O bezeichnet die Menge aller Hindernisabdeckungsbereiche unter Berücksichtigung der Sicherheitsabstandsbedingung.
Für zufällige Punkte, die in den vom Hindernis abgedeckten Bereich gelangen, siehe folgendes Diagramm:
(Anmerkung: Die schattierte Fläche in der Abbildung stellt den Hindernisbereich dar, Pi,j ist ein zufälliger Pfadpunkt und P,i,j ist der diesem Punkt entsprechende Hinderniskantenpunkt.) In dieser Arbeit wird eine Straffunktion φ(vi) entworfen und Folgendes definiert:
2.2.4 Auswahl der Fitnessfunktion
Aus den obigen Punkten ergibt sich die Fitnessfunktion wie folgt:
Wobei α, β und γ die entsprechenden Gewichtungskoeffizienten sind.
Diese Fitnessfunktion vereint auf organische Weise drei Nebenbedingungen, hat eine klare physikalische Bedeutung und ist einfach zu berechnen.
2.3 Crossover-Methode
Neue Individuen werden mittels arithmetischer Rekombination erzeugt. Die Elemente der beiden Chromosomen werden folgendermaßen kombiniert, um die entsprechenden Elemente des neuen Chromosoms zu erhalten:
2.4 Auswahl des Mutationsoperators
2.4.1 Reparaturbediener:
Verschiebe einen Punkt. Bewerte den Punkt innerhalb des Hindernisbereichs anhand einer bestimmten Wahrscheinlichkeit neu, um ihm die Chance zu geben, dem Hindernis auszuweichen.
2.4.2 Optimierung des Betriebsoperators:
Ein Punkt wird gelöscht. Ebenso wird mit einer bestimmten Wahrscheinlichkeit der Mittelpunkt der Verbindungslinie zwischen dem ersten und letzten Punkt gelöscht, wenn diese außerhalb des Erfassungsbereichs des Hindernisses liegen. Die beiden Mutationsoperationen sind in den folgenden Abbildungen dargestellt:
2.5 Schritte der Funktionsweise des genetischen Algorithmus
Zusammenfassend lässt sich der Algorithmus wie folgt beschreiben:
1. Kodierung: Generieren Sie eine Menge von Zufallszahlen und wandeln Sie diese in Chromosom VI in Form eines eindimensionalen Arrays um.
2. Bewertung und Auswahl:
3. Mit einer gewissen Wahrscheinlichkeit kommt es in der neuen Population zu Crossover und Mutation.
4. Führe genetische Iterationsoperationen durch, und nach mehreren Suchgenerationen kann ein optimaler Pfad gefunden werden.
3. Simulationsexperiment
Diese Arbeit präsentiert eine Simulation, die in der VC++ 6.0-Umgebung durchgeführt wurde. Zwei elliptische Objekte repräsentieren Hindernisse, und ein genetischer Algorithmus wird verwendet, um den Pfad zur Hindernisvermeidung zu ermitteln. Das Ergebnis ist unten dargestellt:
(Hinweis: P o ist der Startpunkt, P n-1 ist der Zielpunkt, und die Hindernisse sind mit BLOCK1 bzw. BLOCK2 gekennzeichnet.)
4. Schlussfolgerung
Diese Arbeit entwirft einen auf genetischen Algorithmen basierenden Pfad.
Das vorgeschlagene Verfahren, das mithilfe einer geeigneten Fitnessfunktion durch genetische Suche gesteuert wird, lieferte den optimalen Pfad zur Hindernisvermeidung für das Erzsammelfahrzeug. Simulationsversuche belegten die Stabilität und Effektivität des Verfahrens. Dessen Anwendung ermöglicht es Tiefsee-Erzsammelfahrzeugen, ein gewisses Maß an autonomer Navigation und Hindernisvermeidung zu erlangen und bietet somit einen wertvollen Ansatz für die Forschung zur Entwicklung intelligenter Systeme.
Referenzen:
[1] Sun Ming, Sun Shudong. Prinzipien und Anwendungen genetischer Algorithmen. National Defense Industry Press, 1999: 45-47.
[2] Xuan Guangnan (Japan), Cheng Runwei. Genetische Algorithmen und Ingenieurdesign. Science Press, 2000: 64-66.
[3] Zhong Xin, Lü Tiansheng. Eine Pfadplanungsmethode für fahrzeugartige mobile Roboter basierend auf einem genetischen Algorithmus. Journal of Shanghai Jiaotong University, Juli 1999.
[4] Bauer, R. Genetische Algorithmen und Anlagestrategien. John Wiley & Sons, New York. 1994: 102–105. [5] Allbrecht, R., C. Reeves und N. Steele (Hrsg.), Künstliche neuronale Netze und genetische Algorithmen. Springer-Verlag, New York, 1993: 88–91.
