Analyzing Hierarchical Clustering Algorithm for Track-to-Track Association in Diverse Scenarios

Abstract

In applications such as self-driving cars and swarms of aerial vehicles involving a network of sensors, the concept of track-to-track association plays an important role in their accurate surveillance and threat evaluation. The basic idea is to efficiently group together redundant tracks associated with the track of an object in a network of multiple sensors tracking multiple objects. Tracks are either local tracks (observed by the sensor itself) or shared tracks (shared by other sensors in the network), and they record the location of the objects under observation. Due to sensor inaccuracies and network biases, the shared tracks and local tracks are often mismatched, and it is not clear whether the objects being tracked are the same or different. Various researchers have worked on the problem of track-to-track association and have developed multiple association algorithms with the primary focus on increasing the accuracy as the number of sensors and targets increases. Among these approaches, the HAC algorithm has been used for some specific scenarios but not generalized to multiple sensors and targets. In this thesis, an indigenously developed scenario generator has been utilized to create scenarios and perform HAC-based associations on the corresponding network packets. The performance measurement of the HAC algorithm in different scenarios in terms of quantified accuracy calculation using ground truth data is the main contribution of this work. The HAC algorithm starts with the pre-processing of network packets, which involves extraction of tracks; conversion of location from latitude, longitude, and altitude (LLA) to Earth-Centered Earth-Fixed (ECEF) frame and then to sensor local frame; finally, computation of sensor-specific standard deviations. The next step is time synchronization, where each track is estimated at a fixed association time using a Kalman filter or other estimation technique. This means that the track data from shared and local tracks have been estimated/projected at a specific time. The next step is hierarchical top-down cluster formation based on a predefined threshold, allowing the merger of clusters to obtain the resulting associated clusters/tracks. The final step is accuracy calculation, where the associated tracks and ground truth data are compared to validate the association results. Multiple scenarios have been created to validate the performance of track-to-track association, and the clustering algorithm’s accuracy has been computed for each scenario. The accuracy varies with estimation and threshold calculations. It is shown that by carefully selecting the threshold, the hierarchical agglomerative clustering (HAC) algorithm results in an accuracy of more than 95%. This is also observed in multiple sensors and multiple target cases.