Weighted continuous coverage path planning using multi-objective optimization

Abstract

Mobile robots are increasingly deployed across diverse domains, including underwater pool cleaning, agricultural field operations, and aerial remote sensing using unmanned aerial vehicles (UAVs). Many such applications require paths that cover an entire area, leading to the well-known challenge of coverage path planning (CPP). However, uniform coverage is often insufficient in time- and resource-constrained scenarios such as search and rescue, where certain regions must be prioritized. In these cases, a value function can be used to weight coverage according to criteria such as the probability distribution of a missing person’s location. Moreover, these scenarios require free-form, continuous paths that can respond to variable environmental conditions and can be directly traversed by mobile robots. This gives rise to the novel problem of weighted continuous coverage path planning (WCCPP). The theoretical formulation of the WCCPP problem is derived from two real-world domains: precision farming and UAV-based search and rescue in forested environments. Both domains involve complex terrains characterized by spatially distributed features such as elevation and vegetation density and impose additional constraints on path feasibility and effectiveness. Due to the complexity of the solution space and the practical relevance of the resulting paths, both solution quality and human acceptance are crucial, placing high demands on the optimization algorithm. In addition to formalizing the WCCPP problem, this dissertation presents methodologies to solve it, explores potential improvements based on divide-and-conquer strategies, and demonstrates the applicability of the proposed methodologies to real-world-inspired extensions of the WCCPP problem.

Mobile Roboter finden zunehmend Einsatz in unterschiedlichen Anwendungsfeldern: unter Wasser bei der Reinigung von Schwimmbecken, an Land in der Landwirtschaft oder in der Luft als unbemannte Luftfahrzeuge zur Fernerkundung. In vielen dieser Szenarien ist ein Pfad erforderlich, der das gesamte Einsatzgebiet abdeckt. Dieses Problem wird als coverage path planning (CPP) bezeichnet. Eine gleichmäßige Abdeckung, etwa mittels eines Zickzack-Musters, genügt jedoch häufig nicht. In zeit- und ressourcenbeschränkten Situationen, wie bei Such- und Rettungseinsätzen, müssen bestimmte Bereiche priorisiert werden. Dazu lassen sich Zielfunktionen einsetzen, die eine Abdeckung nach Kriterien wie der Wahrscheinlichkeitsverteilung des möglichen Aufenthaltsortes einer vermissten Person gewichten. Ferner erfordern solche Szenarien flexible, kontinuierliche Pfade, die sich an verschiedene Umweltbedingungen anpassen und von mobilen Robotern direkt zur Navigation genutzt werden können. Daraus ergibt sich das hier behandelte Problem des Weighted Continuous Coverage Path Plannings (WCCPP). Ziel dieser Dissertation ist die Entwicklung umfassender Methodiken zur Lösung der gewichteten und kontinuierlichen Varianten des CPP-Problems. Die Formulierung des WCCPP basiert auf zwei praxisrelevanten Anwendungsfeldern: der Optimierung von Abdeckungspfaden für autonome Roboter in der Präzisionslandwirtschaft sowie der Planung von Such- und Rettungsmissionen mit unbemannten Luftfahrzeugen in bewaldeten Gebieten. Beide Bereiche zeichnen sich durch komplexe Topografien mit heterogenen Eigenschaften wie Geländehöhe und Vegetationsdichte aus und stellen hohe Anforderungen an Machbarkeit und Effizienz der erzeugten Pfade. Angesichts des komplexen Lösungsraums sind sowohl eine hohe Lösungsqualität als auch die Akzeptanz durch menschliche Anwender entscheidend. Diese Dissertation stellt die formale Problemdefinition des WCCPP vor, beschreibt die entwickelten algorithmischen Strategien zu dessen Lösung, diskutiert potenzielle Verbesserungsansätze und demonstriert die Übertragbarkeit der Methodiken auf reale Szenarien.