Reporting leadership patterns among trajectories

ABSTRACT

Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects, opening new options for a better understanding of the processes involved. In this paper we investigate spatio-temporal movement patterns in large tracking data sets. We present a natural definition of the pattern 'one object is leading others', and discuss how such leadership patterns can be computed from a group of moving entities. The proposed definition is based on behavioural patterns discussed in the behavioural ecology literature. We also present several algorithms for computing the pattern, and they are analysed both theoretically and experimentally.

REFERENCES

• 1: Wildlife tracking projects with GPS GSM collars, 2006. www.environmental-studies.de/projects/projects.html.
• 2: Marc Benkert , Joachim Gudmundsson , Florian Hübner , Thomas Wolle, Reporting flock patterns, Proceedings of the 14th conference on Annual European Symposium, p.660-671, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_59]
• 3: B. Dumont, A. Boissy, C. Achard, A. M. Sibbald, and H. W. Erhard. Consistency of animal order in spontaneous group movements allows the measurement of leadership in a group of grazing heifers. Applied Animal Behaviour Science, 95(1--2):55--66, 2005.
• 4: A. U. Frank. Socio-Economic Units: Their Life and Motion. In A. U. Frank, J. Raper, and J. P. Cheylan, editors, Life and motion of socio-economic units, volume 8 of GISDATA, pages 21--34. Taylor & Francis, 2001.
• 5: Joachim Gudmundsson , Marc van Kreveld, Computing longest duration flocks in trajectory data, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183479]
• 6: S. Gueron and S. A. Levin. Self-Organization of Front Patterns in Large Wildebeest Herds. Journal of theoretical Biology, 165(4):541--552, 1993.
• 7: R. H. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann Publishers, 2005.
• 8: Y. Inada and K. Kawachi. Order and flexibility in the motion of fish schools. Journal of theoretical Biology, 214(3):371--387, 2002.
• 9: G. Kollios, S. Sclaroff, and M. Betke. Motion mining: discovering spatio-temporal patterns in databases of human motion. In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2001.
• 10: P. Laube, S. Imfeld, and R. Weibel. Discovering relative motion patterns in groups of moving point objects. International Journal of Geographical Information Science, 19(6):639--668, 2005.
• 11: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 12: S. Tisue and U. Wilensky. NetLogo: A Simple Environment for Modeling Complexity. In International Conference on Complex Systems, Boston, 2004.
• 13: U. Wilensky. NetLogo (and NetLogo User Manual), 1999. http://ccl.northwestern.edu/netlogo.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

Keywords:
agent-based simulation, computational geometry, leadership, movement patterns, tracking data