Emergency rapid mapping with drones: models and solution approaches for offline and online mission planning

Die Verfügbarkeit von unbemannten Luftfahrzeugen (unmanned aerial vehicles oder UAVs) und die Fortschritte in der Entwicklung leichtgewichtiger Sensorik eröffnen neue Möglichkeiten für den Einsatz von Fernerkundungstechnologien zur Schnellerkundung in Großschadenslagen. Hier ermöglichen sie es beispielsweise nach Großbränden, Einsatzkräften in kurzer Zeit ein erstes Lagebild zur Verfügung zu stellen. Die begrenzte Flugdauer der UAVs wie auch der Bedarf der Einsatzkräfte nach einer schnellen Ersteinschätzung bedeuten jedoch, dass die betroffenen Gebiete nur stichprobenartig überprüft werden können. ... mehrIn Kombination mit Interpolationsverfahren ermöglichen diese Stichproben anschließend eine Abschätzung der Verteilung von Gefahrstoffen.

Die vorliegende Arbeit befasst sich mit dem Problem der Planung von UAV-Missionen, die den Informationsgewinn im Notfalleinsatz maximieren. Das Problem wird dabei sowohl in der Offline-Variante, die Missionen vor Abflug bestimmt, als auch in der Online-Variante, bei der die Pläne während des Fluges der UAVs aktualisiert werden, untersucht. Das übergreifende Ziel ist die Konzeption effizienter Modelle und Verfahren, die Informationen über die räumliche Korrelation im beobachteten Gebiet nutzen, um in zeitkritischen Situationen Lösungen von hoher Vorhersagegüte zu bestimmen.

In der Offline-Planung wird das generalized correlated team orienteering problem eingeführt und eine zweistufige Heuristik zur schnellen Bestimmung explorativer UAV-Missionen vorgeschlagen. In einer umfangreichen Studie wird die Leistungsfähigkeit und Konkurrenzfähigkeit der Heuristik hinsichtlich Rechenzeit und Lösungsqualität bestätigt. Anhand von in dieser Arbeit neu eingeführten Benchmarkinstanzen wird der höhere Informationsgewinn der vorgeschlagenen Modelle im Vergleich zu verwandten Konzepten aufgezeigt.

Im Bereich der Online-Planung wird die Kombination von lernenden Verfahren zur Modellierung der Schadstoffe mit Planungsverfahren, die dieses Wissen nutzen, um Missionen zu verbessern, untersucht. Hierzu wird eine breite Spanne von Lösungsverfahren aus unterschiedlichen Disziplinen klassifiziert und um neue effiziente Modellierungsvarianten für die Schnellerkundung ergänzt. Die Untersuchung im Rahmen einer ereignisdiskreten Simulation zeigt, dass vergleichsweise einfache Approximationen räumlicher Zusammenhänge in sehr kurzer Zeit Lösungen hoher Qualität ermöglichen. Darüber hinaus wird die höhere Robustheit genauerer, aber aufwändigerer Modelle und Lösungskonzepte demonstriert.

The increasing availability of unmanned aerial vehicles (UAVs) and the progress in the development of lightweight sensor systems have opened new possibilities for emergency surveillance. After chemical emergencies or large fires, rotary-wing UAVs can provide emergency response units with a quick first assessment of the contaminated area and the affected population. However, unless the affected area is small, the limited flight time and the time-sensitive situation mean that UAVs can only take a limited number of samples. Combined with spatial interpolation methods, these samples allow an estimate of the distribution of contaminants and hazardous substances across the affected area.
... mehr

This thesis addresses the problem of planning UAV missions that maximize the information gain in emergency surveillance. We study this planning problem both in an offline fashion, where missions are determined before takeoff, and in the online variant where plans are updated while the UAVs are in flight. Our main interest lies in the design of efficient models and solution heuristics that use information about the spatial correlations between observed and unobserved locations to determine high-quality solutions with low prediction errors in time-sensitive situations.

For offline planning, we introduce the generalized correlated team orienteering problem and propose an efficient two-stage solution approach for quickly determining explorative UAV missions. In an extensive study, we confirm the competitiveness of our heuristic in terms of computation time and solution quality compared to state-of-the-art approaches for the team orienteering problem. We introduce new benchmark instances and show the higher information gain of our model compared to related concepts. We demonstrate that it is possible to achieve reliable predictions within computation times that allow the use of these approaches in practice.

In the context of online planning, we study the adaptive mission planning problem, which combines online learning of the surveyed contamination and online planning of UAV missions. We classify a wide range of solution concepts from different disciplines and complement them with new modeling variants. We demonstrate that computationally efficient models yield high-quality solutions within very short computation times, thus enabling their use in emergency surveillance. Furthermore, we show the added value of more accurate but computationally expensive models and solution concepts {in case of uncertain initial beliefs and strongly varying processes.