AF: Medium: Collaborative Research: Algorithmic Foundations for Trajectory Collection Analysis

AF：媒介：协作研究：轨迹收集分析的算法基础

• 批准号: 1513816
• 负责人: Pankaj Agarwal
• 金额: $ 53.91万
• 依托单位: Duke University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-01 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1513816&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Algorithmic

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.

该项目聘请了杜克大学和斯坦福大学的计算几何、优化和计算机视觉专家，开发一个理论和算法框架，用于分析来自传感器或模拟的大量轨迹数据。轨迹是从时间间隔到多维空间的函数，出现在对随时间演变的任何系统的描述中。如今，轨迹数据是从数亿个传感器、交通监控系统和蜂窝上的 GPS 传感器中记录或推断的。监控系统中的电话、摄像头、智能手机中的摄像头、战地士兵头盔中的摄像头、医疗设备中的摄像头，以及科学实验和模拟（例如生物学中的分子动力学计算）。轨迹数据分析算法可用于视频检索系统、活动识别、设施监控和监视、医学调查、交通导航辅助、军事分析和部署工具、娱乐等等。其中许多应用领域与国家安全领域以及更广泛的社会效益领域相交叉。该项目追求一种变革性方法，将个体轨迹的几何形状与整个轨迹集合提供的有关其成员的信息相结合。重点是简单而快速的算法，这些算法可以很好地适应大小和尺寸，可以处理数据中的不确定性，并适应噪声和非均匀采样测量流。研究人员与许多学科的应用科学家有着长期的合作记录，并将继续通过联合出版物和研究研讨会以及与多个工业合作伙伴合作将他们的新研究转移到这些科学领域。该项目将在很大程度上依赖研究生和本科生的参与。参与的本科生将通过定向项目、软件开发和实地研究来补充他们的教育。该项目使用和获取的数据集将通过在线存储库向社区提供。开发的软件也将公开。理解轨迹数据集并从中提取有意义的信息需要许多计算挑战。部分问题与可用数据的巨大规模有关，而且这些数据在不断增长，但还有其他几个问题。轨迹数据集因其质量、格式和时间支持的不确定性和异质性而受到损害。同时，各个轨迹可以具有复杂的形状，即使是很小的细微差别也可能在语义上产生很大差异。因此，理解轨迹数据的主要矛盾在于捕获各个轨迹的精细细节的需要和利用轨迹数据的能力之间的矛盾。集合的智慧，即利用嵌入在大量轨迹集合中但在任何单个轨迹中缺失的信息。对集合智慧的强调是该项目的主题之一，并导致计算几何、组合和数值优化以及计算机视觉方面的许多重要问题。该项目的另一个主题是学习和利用轨迹数据的连续和离散变化模式。将开发确定性和概率表示来总结轨迹集合，捕获它们之间的共性和差异，并将设计有效的算法来计算这些轨迹交涉。基于这些总结，将开发方法来估计给定集合中的轨迹，在集合的上下文中相互比较轨迹，以及响应于查询从集合中检索轨迹。轨迹集合还将用于推断有关环境和这些运动中涉及的移动实体的信息。