Evolutionary many-objective optimisation for pathfinding problems

Abstract

It has always been challenging to determine a path across an area or within a medium—whether on a road map for route planning, in a 3D CAD model to generate wire paths, or by surgeons on medical scans for treatment planning. In such scenarios, a decision-maker must consider multiple objectives simultaneously to make an informed decision. In multi-objective optimisation, several objectives are considered, and a set of solutions is produced. Such problems can have large search spaces, as they typically consider a well-defined data structure representing the connections between entities. Classic exact optimisation approaches can result in relatively long computation times. To counteract this, metaheuristics, such as evolutionary algorithms, can generate good solutions in a reasonable time. However, pathfinding problems can be deceptive, resulting in relatively poor performance when using such methodologies. This thesis addresses the optimisation of many-objective pathfinding problems using evolutionary algorithms. In the related literature, several works on multi-objective pathfinding problems have been proposed. They are outlined and categorised in this thesis. Furthermore, various techniques accounting for different aspects of pathfinding optimisation problems have been addressed by other authors. Yet in many works, only specific use-case tailored problems have been considered, with specialised environments. This thesis proposes methodologies to generate variable and scalable pathfinding benchmark problems and techniques to improve the optimisation process. The result is an increased quality of solutions. The benchmark generator was developed using real-world knowledge and can be employed by the research community to evaluate new algorithms. The techniques to improve the optimisation can be divided into two parts. First, various approaches to represent pathfinding problems for optimisation algorithms are proposed. Second, new techniques that can be used with existing algorithms to increase the quality and maintain the diversity of the solution set are presented. The results show an improvement in the solution set’s quality. Furthermore, this thesis addresses the challenge for decision-makers to choose one solution among many that are all Pareto-optimal. Approaches to identifying interesting paths are presented and evaluated, based on a real-world road network. The results indicate that computing sets of various alternatives or robust solutions can be helpful for human decision-makers in real life.

Es war schon immer eine Herausforderung, einen Weg über ein Gebiet oder innerhalb eines Mediums zu bestimmen - sei es auf einer Straßenkarte zur Routenplanung, in einem 3D-CAD-Modell zur Erstellung von Drahtwegen oder von Ärzten auf medizinischen Scans zur Behandlungsplanung. In solchen Szenarien muss ein Entscheidungsträger mehrere Ziele gleichzeitig berücksichtigen, um eine fundierte Entscheidung zu treffen. Bei der multikriteriellen Optimierung werden mehrere Ziele berücksichtigt, und es wird eine Reihe von Lösungen erstellt. Solche Probleme können große Suchräume haben, da sie typischerweise eine wohldefinierte Datenstruktur berücksichtigen, die die Verbindungen zwischen den Einheiten darstellt. Klassische exakte Optimierungsansätze können zu relativ langen Berechnungszeiten führen. Um dem entgegenzuwirken, können Metaheuristiken, wie z. B. evolutionäre Algorithmen, in angemessener Zeit gute Lösungen erzeugen. Pfadfindungsprobleme können jedoch trügerisch sein, was zu einer relativ schlechten Leistung beim Einsatz solcher Methoden führt. Diese Arbeit befasst sich mit der Optimierung von multikriteriellen Pfadfindungsproblemen durch evolutionäre Algorithmen. In der einschlägigen Literatur sind mehrere Arbeiten zu multikriteriellen Wegfindungsproblemen vorgeschlagen worden. Sie werden in dieser Arbeit beschrieben und kategorisiert. Darüber hinaus haben sich andere Autoren mit verschiedenen Techniken befasst, die unterschiedliche Aspekte von Pfadfindungsoptimierungsproblemen berücksichtigen. In vielen Arbeiten wurden jedoch nur auf bestimmte Anwendungsfälle zugeschnittene Probleme mit speziellen Umgebungen berücksichtigt. In dieser Arbeit werden Methoden zur Erzeugung variabler und skalierbarer Pfadfindungs-Benchmark-Probleme und Techniken zur Verbesserung des Optimierungsprozesses vorgeschlagen. Das Ergebnis ist eine höhere Qualität der Lösungen. Der Benchmark-Generator wurde unter Verwendung vonWissen aus der Praxis entwickelt und kann von der Forschungsgemeinschaft zur Bewertung neuer Algorithmen eingesetzt werden. Die Techniken zur Verbesserung der Optimierung können in zwei Teile unterteilt werden. Erstens werden verschiedene Ansätze zur Darstellung von Pfadfindungsproblemen für Optimierungsalgorithmen vorgeschlagen. Zweitens werden neue Techniken vorgestellt, die mit bestehenden Algorithmen verwendet werden können, um die Qualität zu erhöhen und die Vielfalt der Lösungsmenge zu erhalten. Die Ergebnisse zeigen eine Verbesserung der Qualität der Lösungsmenge. Darüber hinaus befasst sich diese Arbeit mit der Herausforderung für Entscheidungsträger, eine Lösung unter vielen zu wählen, die alle Pareto-optimal sind. Es werden Ansätze zur Identifizierung interessanter Pfade vorgestellt und anhand eines realen Straßennetzes bewertet. Die Ergebnisse zeigen, dass die Berechnung von Gruppen von verschiedenen Alternativen oder robusten Lösungen für menschliche Entscheidungsträger im Alltag hilfreich sein kann.