Institut für Theoretische Informatik, Algorithmik

Erkennung von Herdenmustern

Herdenerkennung durch Bereichsabfragen in höher-dim. Räumen

Eine Studie in Alaska bildete die Motivation zu dieser Forschungsarbeit: Karibus wurden mit GPS-Sensoren ausgestattet und deren Zugverhalten über einen längeren Zeitraum beobachtet, um Rückschlüsse auf Herdenbildung und soziales Verhalten der Tiere ziehen zu können.

Unsere Idee zur algorithmischen Durchführung der Herdenanalyse ist, die Zuglinie jedes Tieres für t Zeitschritte zunächst kanonisch als Punkt im 2t-dimensionalen Raum einzubetten. Nachdem dies für alle Tiere geschehen ist, werden Bereichs(zähl)anfragen geeignet durchgeführt, die das Bestehen von Herden erkennen und die Tiere einer Herde ausgeben können. Eine Herde ist dabei eine Ansammlung einer vorgegebenen Anzahl von Tieren, die für einen Mindestzeitraum nahe genug beieinander bleiben, wie im folgenden Beispiel dargestellt.

Die Objekte p,q und r bilden über ein Zeitintervall von 3 Schritten eine Herde.

Die Innovation unserer Arbeit gegenüber früheren Algorithmen liegt dabei in der simultanen Betrachtung der Zeitintervalle. Frühere Arbeiten haben jeden einzelnen Zeitschritt unabhängig voneinander analysiert und dabei versucht, durch den momentanen Aufenthaltsort der Tiere sowie die Interpolation ihrer Bewegungsrichtung Rückschlüsse auf Herdenbildungen zu ziehen.

In Zusammenarbeit mit Joachim Gudmundsson, Florian Hübner und Thomas Wolle.

Publikationen

  1. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. In Yossi Azar and Thomas Erlebach, editors, Proc. 14th Annu. Europ. Symp. on Algorithms (ESA'06), volume 4168 of Lecture Notes in Computer Science, pages 660-671. Springer-Verlag, 2006. [ bib | pdf ]
  2. Marc Benkert, Joachim Gudmundsson, Florian Hübner, and Thomas Wolle. Reporting flock patterns. Technical Report 2006-14, Fakultät für Informatik, Universität Karlsruhe, 2006. Available at http://www.ubka.uni-karlsruhe.de/cgi-bin/psview?document=/ira/2006/14. [ bib | html ]