Teilprojekt 2: Suchalgorithmen für kooperierende Unterwasserfahrzeuge

Teilprojektleiter Prof. Dr. Lars Nolle
Teilprojektmitarbeiter Dr. Tarek El-Mihoub
Christoph Tholen, M.Eng.
Teilprojektvolumen 245.724 €
Fördermittelgeber Nds. Ministerium für Wissenschaft und Kultur - VW-Vorab/Wissenschaft für nachhaltige Entwicklung
Teilprojektlaufzeit 01/2017 bis 06/2021

Motivation und Anwendungsszenario

Abbildung1: Systemkomponenten

Dieses Teilprojekt zielte darauf ab, Suchstrategien für Schwärme von autonomen Unterwasserfahrzeugen (AUV) zu entwickeln, um unterseeische Suchaufgaben effizient und effektiv zu lösen. Motiviert durch den Erfolg populationsbasierter Suchmethoden, zum Beispiel Particle-Swarm-Optimisation, bei der Lösung realer Probleme, sollten diese Methoden der Künstlichen Intelligenz hinsichtlich ihrer Verwendbarkeit auf die aktuelle Aufgabenstellung untersucht werden. Die Suchstrategien sind in diesem Kontext für die Bereitstellung von neuen Wegpunkten zuständig. Diese Wegpunkte werden dann an die kognitive Steuerung (Teilprojekt1) übergeben. Die kognitive Steuerung führt die Bahnplanung durch und gibt die Sollwerte für die Regler vor. Dieses Zusammenspiel der einzelnen Blöcke zeigt Abbildung 1.

Das Anwendungsszenario für dieses Projekt wurde gemeinsam mit dem Kooperationspartner Insti­tut für Chemie und Biologie des Meeres (ICBM) der Universität Oldenburg definiert. Es besteht darin, dass ein Schwarm von AUV einen unterseeischen Grundwasseraustritt lokalisieren soll. Hierbei dienen verschiedene Umweltparameter, zum Beispiel die Temperatur, die Salinität oder die Fluoreszenz gelöster organischer Materie, als Indikator für das austretende Grundwasser. Der Grundwasseraustritt befindet sich in einem Areal von 400 m x 400 m. In dem Szenario wird angenommen, dass dieses Gebiet bereits durch luftgestützte Fernerkundung identifiziert wurde.

Simulationsumgebung

Aufbauend auf dem definierten Anwendungsszenario wurde eine Simulationsumgebung für die Bewertung der zu entwickelnden Suchstrategien implementiert. Im Rahmen der Simulationen wurden verschiedene statische und dynamische Fitnessfunktionen für die Bewertung der Suchstrategien implementiert. Des Weiteren können Kommunikations- und Lokalisierungsfehler im Rahmen der Simulationen flexibel verändert werden, um den Einfluss dieser Fehler auf die Performance zu untersuchen.

Suchstrategien

Es wurden verschiedene Suchalgorithmen entwickelt und bewertet. Es konnte im Rahmen der Simulationen gezeigt werden, dass die entwickelten Suchstrategien den etablierten Suchmustern im Bezug auf die Suchgeschwindigkeit und den Sucherfolg in vielen Szenarien überlegen sind. Bei den populationsbasierten Varianten haben Lokalisierungsfehler und Kommunikationsausfälle negative Auswirkungen auf die Perfomanz der Algorithmen. Zusätzlich wurde das Worst-Case-Szenario eines vollständigen Kommunikationsausfalls simuliert. In diesem Fall wechseln die AUV in einen neuen Suchmodus, in welchem sie unabhängig vom Rest des Schwarms operieren können. Die entwickelten Suchstrategien wurden, zusammen mit den Simulationsergebnissen in insgesamt elf begutachteteten wissenschaftlichen Veröffentlichungen publiziert. Eine Übersicht über die entwickelten Suchstrategien, die Ergebnisse und die jeweiligen Veröffentlichungen findet sich Tabelle 1.

Integration in DUNE Framework

Abbildung 2: Übersicht der für die Suche benötigten Module und IMC-Kommunikation

Um die entwickelten Suchstrategien auf den zur Verfügung stehenden Fahrzeugen einsetzten zu können, wurde das eingesetzte Softwareframe DUNE um mehrere Module erweitert. Hierbei handelt es sich zum einen um einen Search Handler und zum anderen um einzelne Module für die jeweiligen Suchstrategien. Der Search Handler übernimmt die Kommunikation mit den anderen Modulen des Frameworks und den anderen Fahrzeugen und schaltet, je nach Auftrag und Einstellung, die einzelnen Suchstrategien zu. Die durch die Suchstrategien berechneten Koordinaten werden als neue Wegpunkte an den Path Controller weitergegeben. Dieser berechnet unter Zuhilfenahme der aktuellen Position des Fahrzeugs den benötigten Kurs und die erforderliche Geschwindigkeit und gibt beides für die Regelung an das Modul BROV2Control weiter. Zusätzlich wurden Module für die verwendeten Sensoren entwickelt und integriert. Die Kommunikation zwischen den einzelnen Modulen und den unterschiedlichen Fahrzeugen nutzt das IMC Protokoll. Abbildung 1 zeigt eine Übersicht über die für die Suche eingesetzten Module. Diese Erweiterungen wurden in das Framework integriert und auf den zur Verfügung stehenden Fahrzeugen getestet.

Im Rahmen von Experimenten im Hallenbad konnte gezeigt werden, dass die Implementierung der Integration von Suchalgorithmen in das Gesamtframework wie erwartet funktioniet. Die Suchalgorithmen berechnen neue Wegpunkte und geben diese mittels IMC Nachrichten über den Search Handler an die nachfolgenden Module weiter. Nach erreichen eines Wegpunktes werden automatisiert neue Wegpunkte berechnet.

Entwickelte Suchstrategien

Search Strategy Fitness Function Discussion Publication
Particle Swarm Optimisation Cellular Automata PSO was the first tested search strategy for a small swarm (3 vehicles) of AUVs. Influence of different error sources was investigated [1]. In addition, studies were undertaken to identify best parameter settings for the success of the search strategy [2].

[1] Tholen, C., Nolle, L. and Werner, J. (2019) On the Influence of Localisation and Communication Error on the Behaviour of a Swarm of Autonomous Underwater Vehicles. doi.org/10.1007/978-3-319-97888-8_6

[2] Tholen, C., Nolle, L. (2017) Parameter Search for a Small Swarm of AUVs Using Particle Swarm Optimisation. doi.org/10.1007/978-3-319-71078-5_32

Levy-flight

Self-adaptive Levy-flight

Inertia Levy-flight		 Static Conductivity distribution based on measurements from Black Point SGD (Hawaii) A search strategy for a single AUV, based on Levy flight, was developed. Performance was improved utilising feedback gained from the environment. Inertia Levy-flight was able to outperform pre planned path search strategy. A static fitness function was used in this research.

[3] Tholen, C., El-Mihoub, T. A., Nolle, L. and Zielinski, O. (2018) On the robustness of self-adaptive Levy flight. doi.org/10.1109/OCEANSKOBE.2018.8559485
Combined PSO and Inertia Levy flight Static Conductivity distribution based on measurements from Black Point SGD (Hawaii) In the combination, inertia Levy-flight is used as scout vehicle updating the best-known position of the swarm. Results shows, that the combined strategy outperforms pure PSO and pure inertia Levy-flight.

[4] Tholen, C., El-Mihoub, T.A. and Nolle, L. (2017) On a Novel Search Strategy Based on a Combination of Particle Swarm Optimisation and Levy-Flight. doi.org/10.7148/2018-0190

Levy-flight

Inverse Levy-flight

Seed-Spreader search  

Random walk		 A static environment with three phenomena of interest each with different importance.  No gradient information was used. Different blind search techniques have been developed and tested. Compared with cooperative search, the simulations show that the probability of locating a phenomenon of interest using a single AUV with blind search-patterns is very small. However, Levy-flight and inverse Levy can be used as a backup search in the worst-case scenario. [5] El-Mihoub, T. A., Tholen, C. and Nolle, L. (2018) Blind Search Patterns for Off-Line Path Planning.  doi.org/10.7148/2018-0121

Deterministic informed search

(Hybrid of deterministic blind search and a simple exploitation  search mechanism)		 One hundred samples of a multimodal static environment. Simple exploitation search methods are developed and incorporated within different predefined search patterns.  The impact of localisation errors on their search performance is studied. The simulations show that the impact of the localisation problem can be lightened by designing an algorithm that relays on other search information rather than the exact position of the promising solutions. [6] El-Mihoub, T. A., Tholen, C. and Nolle, L. (2019) Informed search patterns for alleviating the impact of the localisation problem.  doi.org/10.7148/2019-0037
Combined Inertia Levy-flight and Braitenberg search Static Conductivity distribution based on measurements from Black Point SGD (Hawaii) This study includes a scanning vehicle and a combination of inertia Levy-flight and Braitenberg search for the AUV. However, this combination was not able to outperform pure inertia Levy-flight. [7] Tholen, C., Nolle, L., El-Mihoub, T. A., Zielinski, O. and Wellhausen, J.: (2019) Development of an intelligent and distributed low-cost platform for marine observation. doi.org/10.1109/OCEANSE.2019.8867466
The Covariance Matrix Adaption Evolution Strategy (CMA-ES) 100 different samples of a static temperature fitness landscape with two SGDs each has a different discharge rate. The robustness of the performance of the CMA-ES against some constrains of the task of locating SGDs is evaluated. The simulations show that using an off the shelf state of-the-art search algorithm cannot guarantee locating SGDs. The number of AUVs and their energy capacities together with the resolution of sensors and the localisation errors can have a great impact on the search results [8] El-Mihoub, T. A., Tholen, C. and Nolle, L. (2020) Using the CMA evolutionary strategy for locating submarine groundwater discharge. doi.org/10.7148/2020-0032

Particle Swarm Optimization (PSO)

All-to-one Self-Organising Migrating Algorithm (SOMA)

Pure Predefined Path (PPP)

Adaptive Predefined Path (APP)

 100 different samples of a static temperature fitness landscape with two SGDs each has a different discharge rate.   A search strategy is developed to alleviate the impact of localisation error on the search results. In this strategy, a high-level mechanism, for building a global view of the search space, is combined with low-level search algorithms with exploring roles. Hybrids of PSO and SOMA, from one side, and PPP and APP, from the other side are studied. The impact of the localisation errors on the search behaviour of these hybrids is studied. The simulations demonstrate that the effect of the localisation problem can be alleviated by light use of location information. [9] El-Mihoub, T., Tholen, C. and Nolle, L. 2020. Towards Reducing the Impact of Localisation Errors on the Behaviour of a Swarm of Autonomous Underwater Vehicles. MENDEL. 26, 2 (Dec. 2020), 1-8. DOI:https://doi.org/10.13164/mendel.2020.2.001.

The simplex search method (Melder-Mead algorithm)

Particle Swarm Optimization (PSO)

All-to-one Self-Organising Migrating Algorithm (SOMA)

Pure Predefined Path (PPP)

 100 different samples of a static temperature fitness landscape with two SGDs each has a different discharge rate Following the strategy used in [9], a hybrid of the simplex search method and PPP algorithm is developed. The performance of this hybrid is compared with hybrids of PSO, SOMA, the simplex search method and PPP algorithm. The impact of localisation error on AUVs navigation and its influence of the search performance is also studied. The simulations show that small localisation errors can introduce small shifts in PPP and can improve the performance.   

[10] El-Mihoub, T.A., Tholen, C., Nolle, L. (2020) On Localisation Errors and Cooperative Search for a Swarm of AUVs.  https://doi.org/10.1109/IEEECONF38699.2020.9389227

Evolutionary Strategy  (ES)

Real-coded Genetic Algorithms (GA)

Pure Predefined Path (PPP)

PSO

Simplex Method		 Static Conductivity distribution and Temperature distribution based on measurements from Black Point SGD (Hawaii) Combinations of ES and GA sequential algorithms as exploring search algorithms is combined with PSO and Simplex as high cooperative search algorithms are  constructed and evaluated. The evaluation of the EA-based algorithms demonstrates that they improve the performance of the PPP algorithm within different cooperation scenarios. They show a robust behaviour against a range of localisation and navigation

[11] El-Mihoub, T.A., Tholen, C. and Nolle, L. (2020) A Sequential Population-Based Search for AUVs.

doi.org/10.1109/IEEECONF38699.2020.9389365

 

Publikationen

  • El-Mihoub, T., Tholen, C., Nolle, L. (2018): Blind Search Patterns for Off-Line Path Planning. 32nd. European Conference on Modelling and Simulation ECMS 2018,doi.org/10.7148/2018-0121
     
  • El-Mihoub, T., Tholen, C., Nolle, L. (2019): Informed search patterns for alleviating the impact of the localisation problem. 33rd INTERNATIONAL ECMS Conference on Modelling and Simulation, doi.org/10.7148/2019-0037
     
  • El-Mihoub, T., Tholen, C., Nolle, L. (2020): Using the CMA evolutionary strategy for locating submarine groundwater discharge. 34th INTERNATIONAL ECMS Conference on Modelling and Simulation, doi.org/10.7148/2020-0032
     
  • El-Mihoub, T., Tholen, C., Nolle, L. (2020): A Sequential Population-Based Search for AUVs. Global Oceans 2020: Singapore – U.S. Gulf Coast, doi.org/10.1109/IEEECONF38699.2020.9389365
     
  • El-Mihoub, T., Tholen, C., Nolle, L. (2020): On Localisation Errors and Cooperative Search for a Swarm of AUVs. Global Oceans 2020: Singapore – U.S. Gulf Coast, doi.org/10.1109/IEEECONF38699.2020.9389227
     
  • El-Mihoub, T., Tholen, C., Nolle, L. (2020): Towards Reducing the Impact of Localisation Errors on the Behaviour of a Swarm of Autonomous Underwater Vehicles. MENDEL 26,2, doi.org/10.13164/mendel.2020.2.001
     
  • Tholen, C., El-Mihoub, T., & Nolle, L. (2018): On a Novel Search Strategy Based on a Combination of Particle Swarm Optimisation and Levy-Flight. 32nd. European Conference on Modelling and Simulation ECMS 2018,doi.org/10.7148/2018-0190
     
  • Tholen, C., El-Mihoub, T., Nolle, L., Zielinski, O. (2018): On the robustness of self-adaptive Levy-flight, 2018 OCEANS - MTS/IEEE Kobe Techno-Oceans (OTO), Kobe, Japan, doi.org/10.1109/OCEANSKOBE.2018.8559485
     
  • Tholen, C., Nolle, L., El-Mihoub, T. A., Zielinski, O.,Wellhausen, J. (2019): Development of an intelligent and distributed low-cost platform for marine observation, OCEANS 2019 - Marseille, Marseille, France, doi.org/10.1109/OCEANSE.2019.8867466
     
  • Tholen, C., El-Mihoub, T.A., Nolle, L., Ralle, O., & Rofallski, R. (2020): „Optimal Receiver Configuration Of Short-Baseline Localisation Systems Using Particle Swarm Optimisation“, In: Steglich et al. (Eds.),34th INTERNATIONAL ECMS Conference on Modelling and Simulation, Wildau, Germany, doi.org/10.7148/2020-0025
     
  • Tholen, C., Rofallski, R., Nolle, L., El-Mihoub, T.A., Parnum, I. & Zielinski, O. (2020): „On the investigation of artificial submarine groundwater discharge sites using a low-cost multi-sensor-platform“ – Global Oceans 2020, Singapore – U.S. Gulf Coast,doi.org/10.1109/IEEECONF38699.2020.9389450