Efficient algorithms for analyzing the movement of groups
Final Report Abstract
In diesem Projekt wurden Algorithmen zur Analyse der Bewegung von Gruppen entwickelt. Dabei haben wir vor allem drei Fragestellungen betrachtet: die Darstellung von Gruppenbewegungen, Ähnlichkeit von Gruppenbewegungen und das Entdecken linearer Formationen in der Bewegung von Gruppen. Diese Probleme waren insbesondere durch die Kooperation mit der Projektpartnerin Dr. Andrea Kölzsch am Max-Planck-Institut für Verhaltensbiologie in Radolfzell motiviert. Dr. Kölzsch untersucht das Verhalten von Gänsen, welche zweimal jährlich in Familiengruppen migrieren. Unsere Algorithmen waren darauf ausgelegt, zur Analyse dieser Daten beizutragen. Dazu wurden die entwickelten Algorithmen größtenteils implementiert und auf diesen Daten ausgewertet. Auch wurden zusätzliche Daten von Familiengruppen benötigt und erzeugt, da das Ausstatten von Familiengruppen mit GPS-sendern relativ aufwendig und teuer und daher bisher noch relativ selten ist. Mit Hilfe unserer Algorithmen konnten neue Methoden und Erkenntnisse in der Analyse der Daten gewonnen werden. Zur Lösung der drei betrachteten Fragestellungen haben wir diese zunächst mathematisch formuliert und anschließend deren algorithmische Komplexität untersucht. Dabei stellte sich bei allen drei heraus, dass sie in manchen Varianten NP-schwer zu entscheiden sind und sich in anderen Varianten effizient lösen lassen. Dazu wurden verschiedene Techniken angewandt, u.a. die Reduktion auf andere Probleme, Parametrisierung oder Einschränkung des Problems. Ebenfalls haben wir dabei neue Konzepte vorgestellt, und zwar das Group Diagram, Varianten des Graph Abstandes und den Fréchet Abstand von Punktmengen. Diese Konzepte lassen sich für die Analyse von Bewegungsdaten von Gruppen verwenden, haben aber auch darüber hinaus Anwendungen, z.B. in der Analyse von Straßennetzwerken. Insgesamt wurden also mehrere neue Methoden und Konzepte zur Analyse der Bewegung von Gruppen entwickelt. Natürlich bleiben noch offene Fragen. Bezogen auf die betrachteten Konzepte, stellt sich die Frage nach effzienteren Algorithmen, da die vorgestellten Algorithmen teilweise recht hohe Laufzeiten haben. Interessant wäre auch eine Auswertung auf weiteren Datensätzen, da wir diese bisher überwiegend auf den Daten der Projektpartnerin ausgewertet haben. Ebenfalls bleiben noch weitere offene Fragen in der Analyse von Gruppen, die in diesem Projekt nicht betrachtet wurden, z.B. die Segmentierung von Gruppenbewegungen, die Verfeinerung und Vergröberung von Gruppensystemen, sowie die Erkennung weiterer Muster zwischen und innerhalb von Gruppen.
Publications
- Group Diagrams for Representing Trajectories ACM SIGSPATIAL International Workshop on Computational Transportation Science (IWCTS), 2018
Maike Buchin, Bernhard Kilgus, Andrea Kölzsch
- Group Diagrams for Representing Trajectories. European Workshop on Computational Geometry (EuroCG), 2018
Maike Buchin and Bernhard Kilgus
- Group Diagrams for Representing Trajectories. International Journal of Geographical Information Science (IJGIS), 2019
Maike Buchin, Bernhard Kilgus, Andrea Kölzsch
(See online at https://doi.org/10.1080/13658816.2019.1684498) - Distance Measures for Embedded Graphs - Revisited. European Workshop on Computational Geometry (EuroCG), 2019
Hugo Akitaya, Maike Buchin and Bernhard Kilgus
- Distance Measures for Embedded Graphs - Optimal Graph Mappings. European Workshop on Computational Geometry (EuroCG), 2020
Maike Buchin and Bernhard Kilgus
- Fréchet Distance of Point Sets. Canadian Conference on Computational Geometry (CCCG), 2020
Maike Buchin and Bernhard Kilgus
