This project engages experts in computational geometry, optimization, and computer vision from Duke and Stanford to develop a theoretical and algorithmic framework for analyzing large collections of trajectory data from sensors or simulations. Trajectories are functions from a time interval to a multi-dimensional space that arise in the description of any system that evolves over time.
Trajectory data is being recorded or inferred from hundreds of millions of sensors nowadays, from traffic monitoring systems and GPS sensors on cell phones to cameras in surveillance systems or those embedded in smart phones, in helmets of soldiers in the field, or in medical devices, as well as from scientific experiments and simulations, such as molecular dynamics computations in biology. Algorithms for trajectory-data analysis can lead to video retrieval systems, activity recognition, facility monitoring and surveillance, medical investigation, traffic navigation aids, military analysis and deployment tools, entertainment, and much more. Many of these application fields intersect areas of national security, as well as domains of broader societal benefit.
This project pursues a transformational approach that combines the geometry of individual trajectories with the information that an entire collection of trajectories provides about its members. Emphasis is on simple and fast algorithms that scale well with size and dimension, can handle uncertainty in the data, and accommodate streams of noisy and non-uniformly sampled measurements.
The investigators have a long track record of collaboration with applied scientists in many disciplines, and will continue to transfer their new research to these scientific fields through joint publications and research seminars, also in collaboration with several industrial partners. This project will heavily rely on the participation of graduate and undergraduate students. Participating undergraduates will supplement their education with directed projects, software development, and field studies. Data sets used and acquired for this project will be made available to the community through online repositories. Software developed will also be made publicly available.
Understanding trajectory data sets, and extracting meaningful information from them, entails many computational challenges. Part of the problem has to do with the huge scale of the available data, which is constantly growing, but there are several others as well. Trajectory data sets are marred by sensing uncertainty and heterogeneity in their quality, format, and temporal support. At the same time, individual trajectories can have complex shapes, and even small nuances can make big differences in their semantics.
A major tension in understanding trajectory data is thus between the need to capture the fine details of individual trajectories and the ability to exploit the wisdom of the collection, i.e., to take advantage of the information embedded in a large collection of trajectories but missing in any individual trajectory. This emphasis on the wisdom of the collection is one of the main themes of the project, and leads to a multitude of important problems in computational geometry, combinatorial and numerical optimization, and computer vision. Another theme of the project is to learn and exploit both continuous and discrete modes of variability in trajectory data.
Deterministic and probabilistic representations will be developed to summarize collections of trajectories that capture commonalities and differences between them, and efficient algorithms will be designed to compute these representations. Based on these summaries, methods will be developed to estimate a trajectory from a given collection, compare trajectories to each other in the context of a collection, and retrieve trajectories from a collection in response to a query. Trajectory collections will also be used to infer information about the environment and the mobile entities involved in these motions.
