TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 16022

Geometric and Graph-based Approaches to Collective Motion

( Jan 10 – Jan 15, 2016 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/16022

Organizers

Contact



Motivation

A trajectory is a time-stamped sequence of locations which represents the movement of entities in space. Trajectories are often created by sampling GPS locations and attaching a time-stamp, but they can also originate from RFID tags, video, or radar analysis. Huge data sets exist for entities as diverse as birds, deer, traveling humans, sports players, vehicles, and hurricanes.

During recent years analysis tools for trajectory data have been developed within the areas of GIScience and algorithms. Analysis objectives include clustering, performing similarity analysis, segmenting a trajectory into characteristic sub-trajectories, finding patterns like flocking, and several others. Since these computations are mostly spatial, algorithmic solutions have been developed in the areas of computational geometry and GIScience. Although trajectories store only the location of a single point of reference on a moving entity, this is acceptable for the common large-scale analysis tasks. However, for the study of more complex phenomena like interaction and collective motion, it is often insufficient and the basic trajectory representation must be extended.

Simultaneously, in the area of ecology the study of motion of animals has also become a topic of increasing interest. Many animal species move in groups, with or without a specific leader. The motivation for motion can be foraging, escape from predators, changing climate, or it can be unknown. The mode of movement can be determined by social interactions, energy efficiency, possibility of discovery of resources, and of course the natural environment. The more fascinating aspects of ecology include interaction between entities and collective motion. These are harder to grasp in a formal manner, needed for modelling and automated analysis.

Research approach and questions to be addressed

We plan to adopt the following view on collective motion in groups of moving entities. Based on geometric aspects like position, speed and heading, we will be able to say that an interaction may take place. An interaction between two entities may cause a change in movement for one or both of the entities. Such a change can occur almost simultaneously or with a delay. When there is an interaction between two entities, we can model this as an edge in a graph that has the entities as its nodes. Interactions will start and stop, hence the graph will be dynamic with new edges appearing and existing edges ceasing to be present. Furthermore, interactions may involve more than two entities simultaneously, leading to hypergraphs. The study of dynamic graphs and hypergraphs with temporal associated information can reveal more about the type of interaction, and perhaps the motivation for the inter-action. Existing graph measures like centrality and clustering coefficient may play a role, so techniques from the area of network science may be useful. It is likely that new, relevant graph measures and patterns must also be designed, along with algorithms to compute them. There are many aspects in the study of interaction and collective motion:

  • Interaction between entities can occur spontaneously or be caused partly by external factors, in particular the spatial environment.
  • The scale of interaction can be anything between interactions of pairs of entities and large groups, leading to different types of collective motion.
  • The degree of interaction can be close contact, where the shape of the entity plays a role too, or just proximity and other aspects, where entities can be modeled as point objects.
  • Semantically meaningful interactions are different for different organisms, but it is useful to have generic, abstract patterns of interaction.
  • Interaction can be direct or via other entities.
  • Interaction can be dependent on similar heading, speed, inter-visibility, proximity, …
  • Interactions can cause a change in heading or speed, or something else.

In the seminar we suggest to explore the following questions. Answering all of these questions will be too ambitious, but we hope to develop an understanding and make partial progress on several of them.

  • How do we obtain interactions from moving entities using geometric and other characteristics?
  • How do we define useful characteristics of collective motion from the trajectories of its entities and how can we compute these efficiently?
  • What is needed in a dynamic graph model for interactions in order to derive collective motion characteristics from such interaction graphs efficiently?
  • How should we formalize grouping motion such that it can be compared across two separate populations of moving entities?
  • How can we infer and model individual's interactions from trajectory or graph analysis?
  • How do we model collective and group motion in relation to the environment?
  • Can we couple types of interactions to types of behavior of the entities?
  • How can we do validation in (semi-)automated ways?

Although the emphasis of the seminar is on movement in ecology, we plan to study the topics with a certain generality. This implies that the results may also have impact to human movement studies and social networks.

Objectives, prospective outcomes

The topics outlined are mostly unexplored when it comes to those aspects of mutual interest to ecologists and computer scientists. Collective motion has not been viewed from an algorithmic perspective, and we plan to set the first steps toward establishing real collaboration between researchers from these fields. We hope and expect that the cross-fertilization will lead to new insights and new directions in either area. Similarly, we hope that new collaborations can lead to joint research projects where different fields of computer science and biology jointly solve interdisciplinary problems in movement analysis.


Summary

A trajectory is a time-stamped sequence of locations which represents the movement of entities in space. Trajectories are often created by sampling GPS locations and attaching a time-stamp, but they can also originate from RFID tags, video, or radar analysis. Huge data sets exist for entities as diverse as birds, deer, traveling humans, sports players, vehicles, and hurricanes.

During recent years analysis tools for trajectory data have been developed within the areas of GIScience and algorithms. Analysis objectives include clustering, performing similarity analysis, segmenting a trajectory into characteristic sub-trajectories, finding patterns like flocking, and several others. Since these computations are mostly spatial, algorithmic solutions have been developed in the areas of computational geometry and GIScience. Although trajectories store only the location of a single point of reference on a moving entity, this is acceptable for the common large-scale analysis tasks. However, for the study of more complex phenomena like interaction and collective motion, it is often insufficient and the basic trajectory representation must be extended.

Simultaneously, in the area of ecology the study of motion of animals has also become a topic of increasing interest. Many animal species move in groups, with or without a specific leader. The motivation for motion can be foraging, escape from predators, changing climate, or it can be unknown. The mode of movement can be determined by social interactions, energy efficiency, possibility of discovery of resources, and of course the natural environment. The more fascinating aspects of ecology include interaction between entities and collective motion. These are harder to grasp in a formal manner, needed for modelling and automated analysis.

The seminar brought together a group of enthusiastic researchers with a diverse background. To create a shared body of knowledge the seminar featured a number of survey talks that were planned early in the week. The survey talks were rather engaging: the audience learned for instance at what scale one should look at a painting of Van Gogh, how bats chase each other, what size of clumps mussels make and why, and how to interact with a computational geometer.

Probably the main research result was a momentum started up by interaction and awareness of an exciting direction of research where a lot can still be accomplished.

More specific research accomplishments included a methodology for evaluating whether fish or other animals have their movement mostly influenced by closest neighbors, and how to reconstruct movement just based on counts at different time steps.

Copyright Giuseppe F. Italiano, Bettina Speckmann, Guy Theraulaz, and Marc van Kreveld

Participants
  • Martin Beye (Universität Düsseldorf, DE)
  • Karl Bringmann (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Kevin Buchin (TU Eindhoven, NL) [dblp]
  • Maike Buchin (Ruhr-Universität Bochum, DE) [dblp]
  • Oliver Burkhard (Universität Zürich, CH)
  • Somayeh Dodge (University of Colorado - Colorado Springs, US) [dblp]
  • Matt Duckham (RMIT University - Melbourne, AU) [dblp]
  • Anael Engel (The Hebrew University of Jerusalem, IL)
  • Ramon Escobedo (Université Paul Sabatier - Toulouse, FR) [dblp]
  • Brittany Terese Fasy (Montana State University - Bozeman, US) [dblp]
  • Sándor Fekete (TU Braunschweig, DE) [dblp]
  • Luca Giuggioli (University of Bristol, GB) [dblp]
  • Giuseppe F. Italiano (University of Rome "Tor Vergata", IT) [dblp]
  • Maarten Löffler (Utrecht University, NL) [dblp]
  • Richard Philip Mann (University of Leeds, GB) [dblp]
  • Martin Nöllenburg (TU Wien, AT) [dblp]
  • Tim Ophelders (Eindhoven Univ. of Technology, NL) [dblp]
  • Nicholas Ouellette (Stanford University, US) [dblp]
  • Andrea Perna (Paris Diderot University, FR) [dblp]
  • Bettina Speckmann (TU Eindhoven, NL) [dblp]
  • Frank Staals (Aarhus University, DK) [dblp]
  • Guy Theraulaz (Université Paul Sabatier - Toulouse, FR) [dblp]
  • Goce Trajcevski (Northwestern University - Evanston, US) [dblp]
  • Johan van de Koppel (Royal Netherlands Inst. for Sea Research - Yerseke, NL) [dblp]
  • Marc van Kreveld (Utrecht University, NL) [dblp]
  • Kevin Verbeek (TU Eindhoven, NL) [dblp]
  • Robert Weibel (Universität Zürich, CH) [dblp]
  • Carola Wenk (Tulane University, US) [dblp]

Related Seminars
  • Dagstuhl Seminar 08451: Representation, Analysis and Visualization of Moving Objects (2008-11-02 - 2008-11-07) (Details)
  • Dagstuhl Seminar 10491: Representation, Analysis and Visualization of Moving Objects (2010-12-05 - 2010-12-10) (Details)
  • Dagstuhl Seminar 12512: Representation, Analysis and Visualization of Moving Objects (2012-12-16 - 2012-12-21) (Details)
  • Dagstuhl Seminar 14132: Interaction and Collective Movement Processing (2014-03-23 - 2014-03-28) (Details)
  • Dagstuhl Seminar 17282: From Observations to Prediction of Movement (2017-07-09 - 2017-07-14) (Details)

Classification
  • bioinformatics
  • data structures / algorithms / complexity
  • modelling / simulation

Keywords
  • trajectories
  • movement
  • data analysis
  • geometric algorithms
  • graph algorithms
  • collective motion