Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data

Jeremy Martin Kubica, Andrew Moore, Andrew J. Connolly, and Robert Jedicke
tech. report CMU-RI-TR-05-10, Robotics Institute, Carnegie Mellon University, March, 2005


Download
  • Adobe portable document format (pdf) (168KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
In this paper we examine the problem of spatial data association - identifying which track/observations pairs could feasibly be associated. Efficiently and accurately finding these potential associations is vital for most tracking applications, because these associations both identify which target caused a given observation and update the estimate of a target's position and trajectory. However, previous work on efficiently answering this query often makes the limiting assumption that observations arrive in batches at discrete time steps. In many real world applications this may not be the case. Observations may arrive individually or in small batches distributed over a range of time. In this paper we focus on the question of efficiently identifying potential track/observations pairs in data where the observations can occupy a range of times.

We examine the new data structures and algorithms for efficient spatial data association on this type of data. We show that it is possible to adapt algorithms designed for discrete time data, providing the benefits of continuous time while retaining the tractability of discrete approaches. We introduce a novel data structure for dealing with large sets of tracks these queries. Empirically we show that these data structures provide a significant benefit both in decreased computational cost and increased accuracy when contrasted with treating the observations as arriving at a single time. Further, we show that in some cases it is more efficient to treat observations that do arrive at discrete time steps as if it were continuous time data and apply our techniques.


Notes
Associated Lab(s) / Group(s): Auton Lab
Associated Project(s): Auton Project
Number of pages: 23

Text Reference
Jeremy Martin Kubica, Andrew Moore, Andrew J. Connolly, and Robert Jedicke, "Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data," tech. report CMU-RI-TR-05-10, Robotics Institute, Carnegie Mellon University, March, 2005

BibTeX Reference
@techreport{Kubica_2005_4931,
   author = "Jeremy Martin Kubica and Andrew Moore and Andrew J Connolly and Robert Jedicke",
   title = "Efficient Algorithms for the Identification of Potential Track/Observation Associations in Continuous Time Data",
   booktitle = "",
   institution = "Robotics Institute",
   month = "March",
   year = "2005",
   number= "CMU-RI-TR-05-10",
   address= "Pittsburgh, PA",
}