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.

• 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]