{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Multi-Target Tracking: Data Association and Tracking\n", "\n", "This notebook covers multi-target tracking techniques using the Tracker Component Library:\n", "\n", "1. **Data Association Problem** - Matching measurements to tracks\n", "2. **Global Nearest Neighbor (GNN)** - Simple greedy association\n", "3. **Joint Probabilistic Data Association (JPDA)** - Soft association with probabilities\n", "4. **Multiple Hypothesis Tracking (MHT)** - Deferred decision tracking\n", "5. **Track Management** - Initiation, confirmation, and deletion\n", "\n", "## Prerequisites\n", "\n", "```bash\n", "pip install nrl-tracker plotly numpy scipy\n", "```" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import plotly.graph_objects as go\n", "from plotly.subplots import make_subplots\n", "from scipy.stats import chi2\n", "\n", "from pytcl.dynamic_estimation import kf_predict, kf_update\n", "from pytcl.assignment_algorithms import (\n", " gnn_association, gated_gnn_association,\n", " hungarian,\n", " jpda, jpda_update,\n", " compute_likelihood_matrix, jpda_probabilities,\n", ")\n", "from pytcl.performance_evaluation import ospa\n", "\n", "np.random.seed(42)\n", "\n", "# Plotly dark theme template\n", "dark_template = go.layout.Template()\n", "dark_template.layout = go.Layout(\n", " paper_bgcolor='#0d1117',\n", " plot_bgcolor='#0d1117',\n", " font=dict(color='#e6edf3'),\n", " xaxis=dict(gridcolor='#30363d', zerolinecolor='#30363d'),\n", " yaxis=dict(gridcolor='#30363d', zerolinecolor='#30363d'),\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1. The Data Association Problem\n", "\n", "In multi-target tracking, we must determine which measurements correspond to which tracks. This is challenging due to:\n", "\n", "- **Clutter**: False alarms that don't correspond to any target\n", "- **Missed detections**: Targets that aren't detected\n", "- **Close targets**: Ambiguous associations when targets are near each other\n", "\n", "### Scenario Setup" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Simulating 3 targets over 50 time steps\n", "P_d = 0.9, λ_clutter = 2\n" ] } ], "source": [ "# Simulation parameters\n", "dt = 1.0 # Time step\n", "n_steps = 50\n", "n_targets = 3\n", "\n", "# Detection parameters\n", "P_detection = 0.9 # Probability of detection\n", "lambda_clutter = 2 # Average number of clutter points per scan\n", "surveillance_area = [[-50, 50], [-50, 50]] # x and y bounds\n", "\n", "# Motion model: constant velocity\n", "F = np.array([\n", " [1, dt, 0, 0],\n", " [0, 1, 0, 0],\n", " [0, 0, 1, dt],\n", " [0, 0, 0, 1]\n", "])\n", "\n", "q = 0.1 # Process noise\n", "Q = q * np.array([\n", " [dt**3/3, dt**2/2, 0, 0],\n", " [dt**2/2, dt, 0, 0],\n", " [0, 0, dt**3/3, dt**2/2],\n", " [0, 0, dt**2/2, dt]\n", "])\n", "\n", "# Measurement model: position only\n", "H = np.array([\n", " [1, 0, 0, 0],\n", " [0, 0, 1, 0]\n", "])\n", "\n", "R = np.eye(2) * 2.0 # Measurement noise covariance\n", "\n", "print(f\"Simulating {n_targets} targets over {n_steps} time steps\")\n", "print(f\"P_d = {P_detection}, λ_clutter = {lambda_clutter}\")" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "line": { "color": "#00d4ff", "width": 2 }, "mode": "lines", "name": "Target 1", "type": "scatter", "x": { "bdata": "AAAAAAAARMCp0liTm1BDwMIOjzDQlkLAL/i+v4fjQcAk3AM3li5BwNAV42WOmkDAe77vN+3nP8D6ZN3ecHY+wPON9zczOz3AeTTd5t7UO8Bv1dGOa2E6wHRlMpAwaTnA3ilo/pQoOMDN5T9jqs42wJCUuQKm2zXAdhMqyPU0NcD8ywYkaKU0wBKyk/OvVzTAe7q0a0bbM8DB6nFn0PIywA2+njT+zjHAO1XgdSGMMMAA47SY4bkuwCSSfRdvdS3AMWz2BBLWK8CNFlEINVIqwFAzUIkTwyjAUmGzHM5CJ8CsoYPNsoolwCrjUfF4DiPAummgUPUKIMDEDFSb/NEZwJh0leEhfxXAynPgNYupEMBX/GBYERoEwBQ7pjXJMea/IdnGAWty6z9zVDzfpCYAQCP6r0j/nQxA9yyvDbexFUCbjxSSmVUdQH7H4iC42iJAImuceIZ7JkCkCZJjyLkqQNz7QF2j2C5Am+hTavhUMUCvRTueORgzQCyzL4C/kjRA8/Y6VMbcNUCpXJEfmdE2QA==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAPsDSmYgZ7ZU9wOpF2MVSnzzA+lFNvbJ8O8DqqyTh+wI6wBqqW2yr5zfAvviHt3F3NcCVjulAOXQzwPvPUtTKhDHAy0j0S6IAL8AKgLY2/hArwP7QHRPAmybAYr1hqM6SIsCWFvorJNIcwML2on9yCRbAO8zxNsMADcDUfAnA+Mj5vzcBKEI9Yug/i1ZLtefXC0CghlMaO7QZQD20vTMrkiJAI6O88ssNKECgcsE6j3stQOTGG+ZTkDFAPSFGPCuKNEBRjEI2aLM3QG/9JLP58jpALd9ouj41PkD/8W55ub9AQKnPwGyxkkJA/Cz5t9VaREC+5OqGDRdGQKjO+ouurkdAMr7Z3DYVSUC0qsyY2mpKQHNTSjXTt0tALoDK78C8TEAf7YCEcJ5NQNFYoRH3bU5ANjsX1ABFT0CPBVVB/x9QQGkFN18LnFBAMLOFDz0pUUAIvWRwc8tRQAURWWs3c1JA9MEkf7Y6U0Dh1FTliARUQC7JJhou4lRA2HUMcY7DVUBqlNpMJJRWQA==", "dtype": "f8" } }, { "marker": { "color": "#00d4ff", "size": 12, "symbol": "circle" }, "mode": "markers", "name": "Start 1", "showlegend": false, "type": "scatter", "x": [ -40 ], "y": [ -30 ] }, { "marker": { "color": "#00d4ff", "size": 12, "symbol": "square" }, "mode": "markers", "name": "End 1", "showlegend": false, "type": "scatter", "x": [ 22.818742726315268 ], "y": [ 90.31471558900526 ] }, { "line": { "color": "#ff4757", "width": 2 }, "mode": "lines", "name": "Target 2", "type": "scatter", "x": { "bdata": "AAAAAAAAPkB0b0BoK+08QPug8zWhSzxAM7QNEkHbO0BLr20hxFI7QJMUZ5ywtTpAHP/g1DwtOkBJSxRN/X45QHwoNCUT5ThAkPYcgdGkOEBxuCkku5A4QFqjX8TgbThAfME2qhIsOEAL04o7WQM4QBR0TJXh4jdAq6vZoJ8FOEA3D6Ep+DM4QB3SM5fnnDhAd0TeHuQHOUAXz8OIkv84QJoT0lzhijhA9GbcgQiNOEBxt51wEXA4QHybdXDMKDhAUxJkD434N0AXWLqFbwM4QO1Dya3hFzhAqvvlJ74tOEDPvA0Qnxg4QNj86sG4CjhAp2+u/OD9N0DfaDwQr643QHkrAEVq/jZAnxLK7KZSNkDX3giOn641QGF1GqYxgjVAaVlekU6ONUDrMrK/VUA1QO/PcrjrnDRA8i0Tfz/DM0AAKzXWlq8yQBDXk2EaLzJAKOaMJFb1MUDzjKpGrcIxQKxGeOe56TFAqGjTWElLMkBCiDFJvfwyQKgUlZt6KDRA2HRIYaLBNUAquxc1DIc3QA==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAANMC1EqGb+QMzwF3nbelP3THAxVzaO2v/MMCH+R515sgvwDTjTAJiBy7AvFZWd57YLMDzH71bUXQrwOn9H3b2uCrAUJUdKfqrKcC5O+n4jospwJzcI0LluSrAzuZF9+9iLMCYrbCkTl8uwM+fu4YHQjDA4maf+6umMcBOtJoVMR4zwM05JyAfpDTAjKq3xGEKN8C+PHn003I5wM5/9fNpsjvAyD5tN4KtPcB2BtmqNJ4/wEpizaAGpUDAmHVv/niUQcDxVIFQmq1CwMBHNJ5x3UPAbMEtaOwPRcAX7kL4vENGwNBt2lt+kEfAdD+eBk/cSMC2jdkRtSpKwOSOMmb7bUvAKgXolCG4TMBYpGULI+RNwPOAgQ/qGE/A3cFqX+NJUMAh8qUzMABRwN2ODfb4olHAqIXM34M2UsAGdAXrcNZSwMTl5+KjcFPA/R94Fcj8U8D9fAamsYdUwE2aqv+mE1XAJX+Pi9+TVcDZAHWf9P5VwHNErhdyXVbAgn1Tdr6+VsBBvHih6BZXwA==", "dtype": "f8" } }, { "marker": { "color": "#ff4757", "size": 12, "symbol": "circle" }, "mode": "markers", "name": "Start 2", "showlegend": false, "type": "scatter", "x": [ 30 ], "y": [ -20 ] }, { "marker": { "color": "#ff4757", "size": 12, "symbol": "square" }, "mode": "markers", "name": "End 2", "showlegend": false, "type": "scatter", "x": [ 23.527530020040253 ], "y": [ -92.35794865408481 ] }, { "line": { "color": "#00ff88", "width": 2 }, "mode": "lines", "name": "Target 3", "type": "scatter", "x": { "bdata": "AAAAAAAAAAArIJ74yPfTP8tmh2Ri/9g/buovlN5kyj+nmtbG103ZP40UZlOzvus/l7MT3weT9j8PxWLvc/f9P33aGEO0ZgVAI2WvrK5uC0D4trfvtVkRQAqT3BgR4hVAGxowPND7GUB69+fndJ4dQM43hbrdciBAmw/Vf0sFIkDSeo2UD+EjQO4/zK2UnCVAWJGe0LUzJ0A6++OiGJgoQAK+GHHD6SpAojaSLdRDLUAS1D97hZkvQMVUctQanzBA6g2i7HfRMEDZcbQUVHowQKbN48ngBDBA+hOfqlv/LkAAMvXwhpUtQAw8VtNXuixAe0pAuMKmK0B6hxplZZ0qQG1OSt0TJCpARjE+74m4KUCJdB1psD8qQI0/4wDj+ylA+Dc2T71WKUAQG7f0q0ooQKbPtQ7wFSdASYPsyzoAJkC8Dwy0I3MkQB1mqi0n1yJAdFt0sDSgIECNwPknS/4bQGl+56KAmRdAapuPATM6E0DSw2answwPQFgaJw5TZgZA1IzCR3qG+j9+50bEO/bhPw==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAREDjYWee/l5DQBHC77I0v0JAGWVLDokxQkA/BYZ+RqxBQKzlJyYIQUFAtebH4xDpQECwpvQ00a9AQPlyK18OfUBAfftd45ExQEDUPQz2euY/QF8BW2v/vj9AF5JI66ZwP0C6+9nOwPk+QIoo+eekMT5As7p7GR0fPUBXGvyQMFQ8QGLm06WBrjtAEY1zLZTnOkDcMDO9iAI6QHO4PpDqvjhAU4NvexFqN0AazAcFMDU2QN7PIW7a3DRAD/iQfk7aM0Cizb4ddxgzQLxmpBxsUTJAnyw54ulwMUBuFQ0fxtQwQDfj5vaSXTBAT9R4QG+jL0BEx7fQEKMuQDUpDQc6Py5A0TYCjUNeLUB3BPKhwakrQEealjRMsilALvyRMeiXKEAHEg6KZJQnQMDNM3L6fyZAvo/Sa6MQJUCWQofGnpgjQKYQVNlBxiFAN0GKdLGYHkCvNWfNrisZQMQyCT0izhVALBXSVQrwE0DjoUYH330SQBWF9yVJBxBAvGIGDQ/7CUBN7/hKEF8CQA==", "dtype": "f8" } }, { "marker": { "color": "#00ff88", "size": 12, "symbol": "circle" }, "mode": "markers", "name": "Start 3", "showlegend": false, "type": "scatter", "x": [ 0 ], "y": [ 40 ] }, { "marker": { "color": "#00ff88", "size": 12, "symbol": "square" }, "mode": "markers", "name": "End 3", "showlegend": false, "type": "scatter", "x": [ 0.5613077958616797 ], "y": [ 2.2964177949160445 ] } ], "layout": { "height": 500, "template": { "layout": { "font": { "color": "#e6edf3" }, "paper_bgcolor": "#0d1117", "plot_bgcolor": "#0d1117", "xaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" }, "yaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" } } }, "title": { "text": "True Target Trajectories" }, "xaxis": { "range": [ -50, 50 ], "scaleanchor": "y", "scaleratio": 1, "title": { "text": "X position" } }, "yaxis": { "range": [ -50, 50 ], "title": { "text": "Y position" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Generate target trajectories\n", "initial_states = [\n", " np.array([-40, 1.5, -30, 0.5]), # Target 1: moving right-up\n", " np.array([30, -1.0, -20, 1.0]), # Target 2: moving left-up\n", " np.array([0, 0.2, 40, -1.2]), # Target 3: moving right-down\n", "]\n", "\n", "true_tracks = [[] for _ in range(n_targets)]\n", "states = [s.copy() for s in initial_states]\n", "\n", "for k in range(n_steps):\n", " for i in range(n_targets):\n", " true_tracks[i].append(states[i].copy())\n", " states[i] = F @ states[i] + np.random.multivariate_normal(np.zeros(4), Q)\n", "\n", "true_tracks = [np.array(t) for t in true_tracks]\n", "\n", "# Visualize true trajectories\n", "colors = ['#00d4ff', '#ff4757', '#00ff88']\n", "\n", "fig = go.Figure()\n", "\n", "for i, track in enumerate(true_tracks):\n", " # Trajectory line\n", " fig.add_trace(\n", " go.Scatter(x=track[:, 0], y=track[:, 2], mode='lines',\n", " name=f'Target {i+1}', line=dict(color=colors[i], width=2))\n", " )\n", " # Start marker\n", " fig.add_trace(\n", " go.Scatter(x=[track[0, 0]], y=[track[0, 2]], mode='markers',\n", " marker=dict(color=colors[i], size=12, symbol='circle'),\n", " name=f'Start {i+1}', showlegend=False)\n", " )\n", " # End marker\n", " fig.add_trace(\n", " go.Scatter(x=[track[-1, 0]], y=[track[-1, 2]], mode='markers',\n", " marker=dict(color=colors[i], size=12, symbol='square'),\n", " name=f'End {i+1}', showlegend=False)\n", " )\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='True Target Trajectories',\n", " xaxis_title='X position',\n", " yaxis_title='Y position',\n", " height=500,\n", " xaxis=dict(range=surveillance_area[0], scaleanchor='y', scaleratio=1),\n", " yaxis=dict(range=surveillance_area[1]),\n", ")\n", "fig.show()" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Total detections: 136 / 150 (90.7%)\n", "Total clutter: 96\n", "Average measurements per scan: 4.6\n" ] } ], "source": [ "# Generate measurements with missed detections and clutter\n", "all_measurements = []\n", "detection_flags = [] # Track which targets were detected\n", "\n", "for k in range(n_steps):\n", " scan_measurements = []\n", " scan_detections = []\n", " \n", " # Target-originated measurements\n", " for i, track in enumerate(true_tracks):\n", " detected = np.random.random() < P_detection\n", " scan_detections.append(detected)\n", " \n", " if detected:\n", " true_pos = H @ track[k]\n", " z = true_pos + np.random.multivariate_normal(np.zeros(2), R)\n", " scan_measurements.append(z)\n", " \n", " # Clutter\n", " n_clutter = np.random.poisson(lambda_clutter)\n", " for _ in range(n_clutter):\n", " x_clut = np.random.uniform(*surveillance_area[0])\n", " y_clut = np.random.uniform(*surveillance_area[1])\n", " scan_measurements.append(np.array([x_clut, y_clut]))\n", " \n", " # Shuffle to remove ordering information\n", " if scan_measurements:\n", " perm = np.random.permutation(len(scan_measurements))\n", " scan_measurements = [scan_measurements[j] for j in perm]\n", " \n", " all_measurements.append(scan_measurements)\n", " detection_flags.append(scan_detections)\n", "\n", "# Statistics\n", "total_detections = sum(sum(d) for d in detection_flags)\n", "total_clutter = sum(len(m) for m in all_measurements) - total_detections\n", "print(f\"Total detections: {total_detections} / {n_steps * n_targets} ({100*total_detections/(n_steps*n_targets):.1f}%)\")\n", "print(f\"Total clutter: {total_clutter}\")\n", "print(f\"Average measurements per scan: {np.mean([len(m) for m in all_measurements]):.1f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2. Global Nearest Neighbor (GNN)\n", "\n", "The simplest association method: assign each track to its nearest measurement using the Hungarian algorithm. Drawbacks:\n", "- Hard decisions can lead to track swaps\n", "- Doesn't handle ambiguity well" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "class Track:\n", " \"\"\"Simple track class for demonstration.\"\"\"\n", " def __init__(self, x0, P0, track_id):\n", " self.x = x0.copy()\n", " self.P = P0.copy()\n", " self.id = track_id\n", " self.history = [x0.copy()]\n", " self.missed_count = 0\n", " \n", " def predict(self, F, Q):\n", " pred = kf_predict(self.x, self.P, F, Q)\n", " self.x, self.P = pred.x, pred.P\n", " \n", " def update(self, z, H, R):\n", " upd = kf_update(self.x, self.P, z, H, R)\n", " self.x, self.P = upd.x, upd.P\n", " self.history.append(self.x.copy())\n", " self.missed_count = 0\n", " \n", " def coast(self):\n", " self.history.append(self.x.copy())\n", " self.missed_count += 1\n", "\n", "def mahalanobis_distance(track, z, H, R):\n", " \"\"\"Compute Mahalanobis distance from track to measurement.\"\"\"\n", " z_pred = H @ track.x\n", " S = H @ track.P @ H.T + R\n", " residual = z - z_pred\n", " d2 = residual @ np.linalg.solve(S, residual)\n", " return d2\n", "\n", "def gnn_associate(tracks, measurements, H, R, gate_threshold=9.21): # chi2(2, 0.99)\n", " \"\"\"Global Nearest Neighbor association.\"\"\"\n", " n_tracks = len(tracks)\n", " n_meas = len(measurements)\n", " \n", " if n_tracks == 0 or n_meas == 0:\n", " return {}, list(range(n_meas))\n", " \n", " # Build cost matrix (Mahalanobis distances)\n", " cost_matrix = np.full((n_tracks, n_meas), np.inf)\n", " for i, track in enumerate(tracks):\n", " for j, z in enumerate(measurements):\n", " d2 = mahalanobis_distance(track, z, H, R)\n", " if d2 < gate_threshold:\n", " cost_matrix[i, j] = d2\n", " \n", " # Handle case where no valid assignments exist\n", " if np.all(np.isinf(cost_matrix)):\n", " return {}, list(range(n_meas))\n", " \n", " # Replace remaining inf with large value for Hungarian algorithm\n", " cost_matrix_clean = cost_matrix.copy()\n", " cost_matrix_clean[np.isinf(cost_matrix_clean)] = 1e10\n", " \n", " # Hungarian algorithm\n", " row_ind, col_ind, total_cost = hungarian(cost_matrix_clean)\n", " \n", " # Build associations (only for valid gated assignments)\n", " associations = {}\n", " assigned_meas = set()\n", " for i, j in zip(row_ind, col_ind):\n", " if cost_matrix[i, j] < gate_threshold:\n", " associations[i] = j\n", " assigned_meas.add(j)\n", " \n", " unassigned = [j for j in range(n_meas) if j not in assigned_meas]\n", " return associations, unassigned" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GNN tracking complete. 3 tracks maintained.\n" ] } ], "source": [ "# Run GNN tracker\n", "# Initialize with first measurements (simplified - assume first 3 are targets)\n", "P0 = np.diag([R[0,0], 1.0, R[1,1], 1.0]) # Initial covariance\n", "\n", "gnn_tracks = []\n", "for i, state in enumerate(initial_states):\n", " # Initialize near true state (cheating slightly for demo)\n", " x0 = state + np.random.multivariate_normal(np.zeros(4), P0 * 0.1)\n", " gnn_tracks.append(Track(x0, P0.copy(), i))\n", "\n", "# Process all scans\n", "for k, measurements in enumerate(all_measurements):\n", " # Predict\n", " for track in gnn_tracks:\n", " track.predict(F, Q)\n", " \n", " # Associate\n", " associations, unassigned = gnn_associate(gnn_tracks, measurements, H, R)\n", " \n", " # Update associated tracks\n", " for track_idx, meas_idx in associations.items():\n", " gnn_tracks[track_idx].update(measurements[meas_idx], H, R)\n", " \n", " # Coast unassociated tracks\n", " for i, track in enumerate(gnn_tracks):\n", " if i not in associations:\n", " track.coast()\n", "\n", "print(f\"GNN tracking complete. {len(gnn_tracks)} tracks maintained.\")" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "line": { "color": "#00d4ff", "width": 2 }, "mode": "lines", "name": "True 1", "opacity": 0.5, "type": "scatter", "x": { "bdata": "AAAAAAAARMCp0liTm1BDwMIOjzDQlkLAL/i+v4fjQcAk3AM3li5BwNAV42WOmkDAe77vN+3nP8D6ZN3ecHY+wPON9zczOz3AeTTd5t7UO8Bv1dGOa2E6wHRlMpAwaTnA3ilo/pQoOMDN5T9jqs42wJCUuQKm2zXAdhMqyPU0NcD8ywYkaKU0wBKyk/OvVzTAe7q0a0bbM8DB6nFn0PIywA2+njT+zjHAO1XgdSGMMMAA47SY4bkuwCSSfRdvdS3AMWz2BBLWK8CNFlEINVIqwFAzUIkTwyjAUmGzHM5CJ8CsoYPNsoolwCrjUfF4DiPAummgUPUKIMDEDFSb/NEZwJh0leEhfxXAynPgNYupEMBX/GBYERoEwBQ7pjXJMea/IdnGAWty6z9zVDzfpCYAQCP6r0j/nQxA9yyvDbexFUCbjxSSmVUdQH7H4iC42iJAImuceIZ7JkCkCZJjyLkqQNz7QF2j2C5Am+hTavhUMUCvRTueORgzQCyzL4C/kjRA8/Y6VMbcNUCpXJEfmdE2QA==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAPsDSmYgZ7ZU9wOpF2MVSnzzA+lFNvbJ8O8DqqyTh+wI6wBqqW2yr5zfAvviHt3F3NcCVjulAOXQzwPvPUtTKhDHAy0j0S6IAL8AKgLY2/hArwP7QHRPAmybAYr1hqM6SIsCWFvorJNIcwML2on9yCRbAO8zxNsMADcDUfAnA+Mj5vzcBKEI9Yug/i1ZLtefXC0CghlMaO7QZQD20vTMrkiJAI6O88ssNKECgcsE6j3stQOTGG+ZTkDFAPSFGPCuKNEBRjEI2aLM3QG/9JLP58jpALd9ouj41PkD/8W55ub9AQKnPwGyxkkJA/Cz5t9VaREC+5OqGDRdGQKjO+ouurkdAMr7Z3DYVSUC0qsyY2mpKQHNTSjXTt0tALoDK78C8TEAf7YCEcJ5NQNFYoRH3bU5ANjsX1ABFT0CPBVVB/x9QQGkFN18LnFBAMLOFDz0pUUAIvWRwc8tRQAURWWs3c1JA9MEkf7Y6U0Dh1FTliARUQC7JJhou4lRA2HUMcY7DVUBqlNpMJJRWQA==", "dtype": "f8" } }, { "line": { "color": "#ff4757", "width": 2 }, "mode": "lines", "name": "True 2", "opacity": 0.5, "type": "scatter", "x": { "bdata": "AAAAAAAAPkB0b0BoK+08QPug8zWhSzxAM7QNEkHbO0BLr20hxFI7QJMUZ5ywtTpAHP/g1DwtOkBJSxRN/X45QHwoNCUT5ThAkPYcgdGkOEBxuCkku5A4QFqjX8TgbThAfME2qhIsOEAL04o7WQM4QBR0TJXh4jdAq6vZoJ8FOEA3D6Ep+DM4QB3SM5fnnDhAd0TeHuQHOUAXz8OIkv84QJoT0lzhijhA9GbcgQiNOEBxt51wEXA4QHybdXDMKDhAUxJkD434N0AXWLqFbwM4QO1Dya3hFzhAqvvlJ74tOEDPvA0Qnxg4QNj86sG4CjhAp2+u/OD9N0DfaDwQr643QHkrAEVq/jZAnxLK7KZSNkDX3giOn641QGF1GqYxgjVAaVlekU6ONUDrMrK/VUA1QO/PcrjrnDRA8i0Tfz/DM0AAKzXWlq8yQBDXk2EaLzJAKOaMJFb1MUDzjKpGrcIxQKxGeOe56TFAqGjTWElLMkBCiDFJvfwyQKgUlZt6KDRA2HRIYaLBNUAquxc1DIc3QA==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAANMC1EqGb+QMzwF3nbelP3THAxVzaO2v/MMCH+R515sgvwDTjTAJiBy7AvFZWd57YLMDzH71bUXQrwOn9H3b2uCrAUJUdKfqrKcC5O+n4jospwJzcI0LluSrAzuZF9+9iLMCYrbCkTl8uwM+fu4YHQjDA4maf+6umMcBOtJoVMR4zwM05JyAfpDTAjKq3xGEKN8C+PHn003I5wM5/9fNpsjvAyD5tN4KtPcB2BtmqNJ4/wEpizaAGpUDAmHVv/niUQcDxVIFQmq1CwMBHNJ5x3UPAbMEtaOwPRcAX7kL4vENGwNBt2lt+kEfAdD+eBk/cSMC2jdkRtSpKwOSOMmb7bUvAKgXolCG4TMBYpGULI+RNwPOAgQ/qGE/A3cFqX+NJUMAh8qUzMABRwN2ODfb4olHAqIXM34M2UsAGdAXrcNZSwMTl5+KjcFPA/R94Fcj8U8D9fAamsYdUwE2aqv+mE1XAJX+Pi9+TVcDZAHWf9P5VwHNErhdyXVbAgn1Tdr6+VsBBvHih6BZXwA==", "dtype": "f8" } }, { "line": { "color": "#00ff88", "width": 2 }, "mode": "lines", "name": "True 3", "opacity": 0.5, "type": "scatter", "x": { "bdata": "AAAAAAAAAAArIJ74yPfTP8tmh2Ri/9g/buovlN5kyj+nmtbG103ZP40UZlOzvus/l7MT3weT9j8PxWLvc/f9P33aGEO0ZgVAI2WvrK5uC0D4trfvtVkRQAqT3BgR4hVAGxowPND7GUB69+fndJ4dQM43hbrdciBAmw/Vf0sFIkDSeo2UD+EjQO4/zK2UnCVAWJGe0LUzJ0A6++OiGJgoQAK+GHHD6SpAojaSLdRDLUAS1D97hZkvQMVUctQanzBA6g2i7HfRMEDZcbQUVHowQKbN48ngBDBA+hOfqlv/LkAAMvXwhpUtQAw8VtNXuixAe0pAuMKmK0B6hxplZZ0qQG1OSt0TJCpARjE+74m4KUCJdB1psD8qQI0/4wDj+ylA+Dc2T71WKUAQG7f0q0ooQKbPtQ7wFSdASYPsyzoAJkC8Dwy0I3MkQB1mqi0n1yJAdFt0sDSgIECNwPknS/4bQGl+56KAmRdAapuPATM6E0DSw2answwPQFgaJw5TZgZA1IzCR3qG+j9+50bEO/bhPw==", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAREDjYWee/l5DQBHC77I0v0JAGWVLDokxQkA/BYZ+RqxBQKzlJyYIQUFAtebH4xDpQECwpvQ00a9AQPlyK18OfUBAfftd45ExQEDUPQz2euY/QF8BW2v/vj9AF5JI66ZwP0C6+9nOwPk+QIoo+eekMT5As7p7GR0fPUBXGvyQMFQ8QGLm06WBrjtAEY1zLZTnOkDcMDO9iAI6QHO4PpDqvjhAU4NvexFqN0AazAcFMDU2QN7PIW7a3DRAD/iQfk7aM0Cizb4ddxgzQLxmpBxsUTJAnyw54ulwMUBuFQ0fxtQwQDfj5vaSXTBAT9R4QG+jL0BEx7fQEKMuQDUpDQc6Py5A0TYCjUNeLUB3BPKhwakrQEealjRMsilALvyRMeiXKEAHEg6KZJQnQMDNM3L6fyZAvo/Sa6MQJUCWQofGnpgjQKYQVNlBxiFAN0GKdLGYHkCvNWfNrisZQMQyCT0izhVALBXSVQrwE0DjoUYH330SQBWF9yVJBxBAvGIGDQ/7CUBN7/hKEF8CQA==", "dtype": "f8" } }, { "line": { "color": "#00d4ff", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN Track 1", "type": "scatter", "x": { "bdata": "Jd+HgEIiRMDwCoJflGNDwBGKIIJzkELAnXej3FjrQcACcvCzyOJBwGqjjVEBkUHATOUJI8lbQMDj23JgGM8/wLVNsqtcmz7ASB6nqpyfPcDF2jmd/Vk7wJiNy839iznAsWz+RBzrOMARURjWpFc3wBg0VtO3wTXArQS4n956M8DdQnisa8MxwEZMNlRXhjLANfe6qQXyMsBVSyVRL14ywBI5lHjCRjPAi6M3W62DMcCZIiIeipMuwGbJ4glk4yzAXPjLzb5pK8ArbIM+2uIqwGmHYxxogSrA++WWyRnAKcBvEa9PFP8lwPwsLynDGyTAf6cgPW4IIcAwAQMvKokgwNaYx/DMxBjAhqCsZi1LEsB0pMJCX2YJwFBB4HZb0fy/mB0P3nHlpb8MN4XQzFLqP4sENmQXfwdA+V9iqSMuBUDbK2DNgbcQQAiNZ+vMfhZAFNhbKi6NIUAnvmLuSpEmQIGSWIuGayxAsELpuru6MEAQB+NspXwyQNF0O1r2rjNAGwA+GCJWNED9lTYRYM41QCy597PZQjZA", "dtype": "f8" }, "y": { "bdata": "I5BKuVHHPsDWtYqtcCw9wE4LoUS2bDzA/qjM3bQePsBgiTegQPg7wEYfWctihTrA4txNhNmgOMB8M6sn3K82wJxtdLjINTXAVSj89wddMsCNAD4jFjMvwDWfPtJvLCvAA4V3vVx2JsBExASRLgwhwC+FRKe5ISDATj1oWtq7GMD6fkPkFp4RwKb6quLHpOy/3Qwbc5qc8z+MuiCuoK4LQE/n8D5dzxtATGV8L0VzIkDg+9P477MmQKww4jr0wStAweD+C3ocMkC6QOMrV+ozQNJoDWi5bTVA9FyuHiwGOkAZC4sM3qo+QBEr6PCdHEFAQqB0POwEREBSO8Yb9B5FQMicSqUDaEZAcNt/CU1LSEC1+uITg5RJQItkKKAIKUtAYIXyF8abS0D9Ij52PeZMQIwMHN21Ik5AZkS7qmBKT0BWHKOeM+ZPQJuTUqIGG1BAGyr3z0FwUEClbH8cMMJQQJntTGAVulFA9hhoNXdGUkBL6a6lECtTQA2Q2gfdt1NAwKDizF10VEAz1C9aJR5VQFoaxAbEXlZA", "dtype": "f8" } }, { "line": { "color": "#ff4757", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN Track 2", "type": "scatter", "x": { "bdata": "k4IHo8w+PkA5UXweXj4+QKCLcWq5yjxA3FHO6c7xO0Bv16tjl8A7QGxqnlxHZDxAL8ajG3MlPECVQHQrRvk6QNDFLf97tjpAjysmuRYdO0DCjAy+EvA6QFfmg0QFEDpAU8MiEhgIOUC74rGZgDw5QCXDQMqThDhA3PW0pSkNOEBvHk8Oe0Q5QBmBbgA1mzpAOsheKl2mOUBo7k6CCvc4QAjkPH37sDhAcAlebsPgOECmMi2KBjs4QNpM0Nt99jhAoRIYH9PBN0BaAiV5j844QGK5n0GPLTlAGagOuGFhOUBtxm0ZMcQ5QMUF5Xq3cTlAux/5CtC8OEDSWsJz4iM4QGC/z9Sg7zhAiPOCDIRGOEBCDIHXLyM3QDNyL9c3RjZAgzcQeuinNUBUEe2iM4g1QJqrno6yDjVA6r38d96cNUC0fY21rXQzQESUx285VzFAZlwzijQNMUC/+XJbHy4wQAh/aTAKHjBAec0/biMoMUB01WFjDt4wQNIv8+KwNzBAN1elTEa3MEAC2jKezjwzQH7d7/rrpTRA", "dtype": "f8" }, "y": { "bdata": "XoSaM5tpNMCdW0UKY/8xwDJsUajvTjLAhNVwxB59McAbC6T5Tn8ywHbZELMUFTPAw8mNf2kaM8DEw+Wr4oIvwCqJww0zPy3AbIHASXMMKsCkE26CRX0mwBpLIbQ2ZibAdCtKqOccJcAtw38bDWUmwMfucdxwiSjATHhS7FvFKMAGCL1ZMLMwwNrg4tu+QjLAPgPRCXAUNMDm5A4UcN41wE2J9/xK2jjApjKHUvfIO8D7DjKlZgc+wGjruhOBFT/At2+PT4GDQMBcelSFpAFBwDPUVSiHnELAorlmM0aUQ8Bf+MdHw6NEwIoLy6MWKkbAjcJTwl2XR8DHgtJA6SdJwG/UafEc0knAWJeHqlsKS8Csc9xvI9BMwL2bOwODnU7A+1rUctAPUMC++lvRIE9QwCK0kLl36lDA5sEMZekQUcCPja5hYzlSwJ3jdk6ezFLAWAgA1PZNU8CDu1ngkRBUwG5M8qLo3FTAVAmyFGJfVcB4VvSHFQNWwIqFOg+6albAZk9g8muXVsDUFxgISMRWwEKc1L3UGFfA", "dtype": "f8" } }, { "line": { "color": "#00ff88", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN Track 3", "type": "scatter", "x": { "bdata": "RNHW9Nf61L8Y09XY3W/wv4UbhWqrHee/0fCwhZst8D/Wo4fQMbz7P5w1aIQU7wFATxWl4b+o+D8dex3QVDPqP9zaubtpJQFA8/bUFELKBUBUYGLxxTsAQAHo55oivf8/SCNlCyoKBUAIOm3ofbMRQMKlOfb6CR1AQqDs0lZZIECZ42dL1zoiQL/a21KsXiRA/yY0+S9iJ0C3YbxOmOMpQGCE15NAdClAkNQLGRXKK0DcJO7HSg8vQFEjvyujsjBAvTLSYqVfMkDIFTAxykMxQEnRhGd8ejBA2ZKI+zKLMEAkUNkxb4kxQIt4nHJhcDJA33D2cYakMUAMfLyKQxYxQCdv92GSUS1Akae02KB1KkCqg43oPVooQG6/wgG44CZAKMfmzha1JkCLfV5uWk0lQKykc1qbKyhAnVappXuPJ0BIcDQnC+opQJiyAmdtISZA3l3ASAVvI0D7puDpSmoiQBzjnxObAiBAu9XeGChsHEB9glGuucoaQLnbQu59ORZA4UiPwD0MFUAI3w8F+1IOQH/B+kmCQvc/", "dtype": "f8" }, "y": { "bdata": "3WLkm3PVQ0Cc2gYy8nFDQN39AC6FkUNAnkK4wqWhQkCP2XdryBdCQECz+DNLlkBA4k4FxGcEQUCaOgM6HPZAQDld4g4ybEBAcMjHE8ovQEDi/6r7NSQ/QHcdytxq+z5AjlXWwe7APkCIX3wnfOk+QIJQ1p6Bez1ANxW4rPVLPUAAX0XmGWI8QL3JJtnS2TpAbXMuNJvNOkDMKlO3SCk6QHokRNUjCTlADlnwYhkLOEAy+wpg0fs2QEtf0CziETZAkdIj3mZNM0B+F1F1zgIzQGBPi/bhcjJAf1AD7cz/MUD8pcOORjAxQEaJIK94izBAPmUBjK1hMECXjVf0em8wQM/MQztNXy5Ajn4myh0sLkANRJgt6zwtQNru1DhrDyxAYyGzXGI7LUDw6eexwN4sQPd3HFcGnihAk0Wo2y1zJkB3KiE2lPIlQPAULFoEbyVAQCTXJ+ezJECg3SlV/8wgQPML0gY7ghtA9ipwBD7BEkAjnaBpwnERQKjZqf4DzBFAMZA4kb+xCEBVg6gC5Wj5Pyyc7/ILIPk/", "dtype": "f8" } }, { "marker": { "color": "gray", "opacity": 0.5, "size": 6 }, "mode": "markers", "name": "Last scan", "type": "scatter", "x": [ -49.96674938795106, 10.255316384286495, -30.82175444081394, 21.688023940262852, 21.291294117640785, -0.02145065964672177, -11.353915884085286 ], "y": [ -48.231219038674276, -13.520178085547052, -28.824464933452166, 90.81187948020141, -92.30688115439327, 2.7230791464587165, 6.444109067888249 ] } ], "layout": { "height": 550, "template": { "layout": { "font": { "color": "#e6edf3" }, "paper_bgcolor": "#0d1117", "plot_bgcolor": "#0d1117", "xaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" }, "yaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" } } }, "title": { "text": "GNN Multi-Target Tracking" }, "xaxis": { "scaleanchor": "y", "scaleratio": 1, "title": { "text": "X position" } }, "yaxis": { "title": { "text": "Y position" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize GNN results\n", "fig = go.Figure()\n", "\n", "# True trajectories (semi-transparent)\n", "for i, track in enumerate(true_tracks):\n", " fig.add_trace(\n", " go.Scatter(x=track[:, 0], y=track[:, 2], mode='lines',\n", " name=f'True {i+1}', line=dict(color=colors[i], width=2),\n", " opacity=0.5)\n", " )\n", "\n", "# GNN estimates (dashed)\n", "for i, track in enumerate(gnn_tracks):\n", " history = np.array(track.history)\n", " fig.add_trace(\n", " go.Scatter(x=history[:, 0], y=history[:, 2], mode='lines',\n", " name=f'GNN Track {i+1}', line=dict(color=colors[i], width=2, dash='dash'))\n", " )\n", "\n", "# Measurements from last scan\n", "last_meas = all_measurements[-1]\n", "fig.add_trace(\n", " go.Scatter(x=[z[0] for z in last_meas], y=[z[1] for z in last_meas], mode='markers',\n", " name='Last scan', marker=dict(color='gray', size=6, opacity=0.5))\n", ")\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='GNN Multi-Target Tracking',\n", " xaxis_title='X position',\n", " yaxis_title='Y position',\n", " height=550,\n", " xaxis=dict(scaleanchor='y', scaleratio=1),\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 3. Joint Probabilistic Data Association (JPDA)\n", "\n", "JPDA computes the probability of each measurement-to-track association and uses a weighted combination for the update:\n", "\n", "$$\\hat{x}_{k|k} = \\hat{x}_{k|k-1} + K \\sum_{j=0}^{m} \\beta_j (z_j - H\\hat{x}_{k|k-1})$$\n", "\n", "where $\\beta_j$ is the probability that measurement $j$ originated from the track." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "JPDA tracking complete. 3 tracks maintained.\n" ] } ], "source": [ "def compute_likelihood_matrix(states, covs, meas_array, H, R, gate_threshold=9.21):\n", " \"\"\"Compute likelihood matrix for JPDA.\"\"\"\n", " n_tracks = len(states)\n", " n_meas = len(meas_array)\n", " \n", " # Likelihood matrix\n", " L = np.zeros((n_tracks, n_meas))\n", " gated = np.zeros((n_tracks, n_meas), dtype=bool)\n", " \n", " for i in range(n_tracks):\n", " z_pred = H @ states[i]\n", " S = H @ covs[i] @ H.T + R\n", " \n", " for j in range(n_meas):\n", " residual = meas_array[j] - z_pred\n", " d2 = residual @ np.linalg.solve(S, residual)\n", " \n", " # Gating\n", " if d2 < gate_threshold:\n", " gated[i, j] = True\n", " # Likelihood: Gaussian probability\n", " det_S = np.linalg.det(S)\n", " L[i, j] = 1.0 / np.sqrt(2*np.pi*det_S) * np.exp(-0.5*d2)\n", " \n", " return L, gated\n", "\n", "def jpda_probabilities(L, gated, P_detection, clutter_density):\n", " \"\"\"Compute association probabilities for JPDA.\"\"\"\n", " n_tracks = L.shape[0]\n", " n_meas = L.shape[1] if L.shape[0] > 0 else 0\n", " \n", " # Add dummy element for null hypothesis (no association)\n", " beta = np.zeros((n_tracks, n_meas + 1))\n", " \n", " for i in range(n_tracks):\n", " # Sum of detector-originated likelihoods\n", " sum_lik = 0.0\n", " for j in range(n_meas):\n", " if gated[i, j]:\n", " sum_lik += P_detection * L[i, j]\n", " \n", " # Sum of clutter likelihoods\n", " sum_clutter = (1 - P_detection) + clutter_density\n", " \n", " # Normalization constant\n", " c_i = sum_lik + sum_clutter\n", " \n", " # Association probabilities\n", " for j in range(n_meas):\n", " if gated[i, j]:\n", " beta[i, j] = P_detection * L[i, j] / (c_i + 1e-10)\n", " \n", " # Null hypothesis (no associated measurement)\n", " beta[i, -1] = (1 - P_detection) / (c_i + 1e-10)\n", " \n", " return beta\n", "\n", "# Initial covariance matrix (not yet defined in skeleton)\n", "P0 = np.eye(4)\n", "P0[0, 0] = P0[2, 2] = 25.0 # Position variance\n", "P0[1, 1] = P0[3, 3] = 1.0 # Velocity variance\n", "\n", "# Run JPDA tracker\n", "jpda_tracks = []\n", "for i, state in enumerate(initial_states):\n", " x0 = state + np.random.multivariate_normal(np.zeros(4), P0 * 0.1)\n", " jpda_tracks.append(Track(x0, P0.copy(), i))\n", "\n", "# Clutter density\n", "area = (surveillance_area[0][1] - surveillance_area[0][0]) * \\\n", " (surveillance_area[1][1] - surveillance_area[1][0])\n", "clutter_density = lambda_clutter / area\n", "\n", "for k, measurements in enumerate(all_measurements):\n", " # Predict\n", " for track in jpda_tracks:\n", " track.predict(F, Q)\n", " \n", " if len(measurements) == 0:\n", " for track in jpda_tracks:\n", " track.coast()\n", " continue\n", " \n", " # Get track states and covariances\n", " states = [t.x for t in jpda_tracks]\n", " covs = [t.P for t in jpda_tracks]\n", " meas_array = np.array(measurements)\n", " \n", " # Compute likelihood matrix and association probabilities\n", " L, gated = compute_likelihood_matrix(states, covs, meas_array, H, R)\n", " beta = jpda_probabilities(L, gated, P_detection, clutter_density)\n", " \n", " # JPDA update for each track\n", " for i, track in enumerate(jpda_tracks):\n", " # Weighted innovation\n", " z_pred = H @ track.x\n", " S = H @ track.P @ H.T + R\n", " K = track.P @ H.T @ np.linalg.inv(S)\n", " \n", " # Weighted sum of innovations\n", " innovation = np.zeros(2)\n", " for j in range(len(measurements)):\n", " innovation += beta[i, j] * (measurements[j] - z_pred)\n", " \n", " # Update state\n", " track.x = track.x + K @ innovation\n", " \n", " # Update covariance (spread of the means + innovation uncertainty)\n", " P_c = (1 - sum(beta[i, :-1])) * track.P # Coast term\n", " P_u = (np.eye(4) - K @ H) @ track.P # Update term\n", " track.P = beta[i, -1] * track.P + (1 - beta[i, -1]) * P_u\n", " \n", " track.history.append(track.x.copy())\n", " \n", "print(f\"JPDA tracking complete. {len(jpda_tracks)} tracks maintained.\")" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "line": { "color": "#00d4ff", "width": 2 }, "mode": "lines", "name": "True 1", "opacity": 0.4, "showlegend": true, "type": "scatter", "x": { "bdata": "AAAAAAAARMCp0liTm1BDwMIOjzDQlkLAL/i+v4fjQcAk3AM3li5BwNAV42WOmkDAe77vN+3nP8D6ZN3ecHY+wPON9zczOz3AeTTd5t7UO8Bv1dGOa2E6wHRlMpAwaTnA3ilo/pQoOMDN5T9jqs42wJCUuQKm2zXAdhMqyPU0NcD8ywYkaKU0wBKyk/OvVzTAe7q0a0bbM8DB6nFn0PIywA2+njT+zjHAO1XgdSGMMMAA47SY4bkuwCSSfRdvdS3AMWz2BBLWK8CNFlEINVIqwFAzUIkTwyjAUmGzHM5CJ8CsoYPNsoolwCrjUfF4DiPAummgUPUKIMDEDFSb/NEZwJh0leEhfxXAynPgNYupEMBX/GBYERoEwBQ7pjXJMea/IdnGAWty6z9zVDzfpCYAQCP6r0j/nQxA9yyvDbexFUCbjxSSmVUdQH7H4iC42iJAImuceIZ7JkCkCZJjyLkqQNz7QF2j2C5Am+hTavhUMUCvRTueORgzQCyzL4C/kjRA8/Y6VMbcNUCpXJEfmdE2QA==", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "AAAAAAAAPsDSmYgZ7ZU9wOpF2MVSnzzA+lFNvbJ8O8DqqyTh+wI6wBqqW2yr5zfAvviHt3F3NcCVjulAOXQzwPvPUtTKhDHAy0j0S6IAL8AKgLY2/hArwP7QHRPAmybAYr1hqM6SIsCWFvorJNIcwML2on9yCRbAO8zxNsMADcDUfAnA+Mj5vzcBKEI9Yug/i1ZLtefXC0CghlMaO7QZQD20vTMrkiJAI6O88ssNKECgcsE6j3stQOTGG+ZTkDFAPSFGPCuKNEBRjEI2aLM3QG/9JLP58jpALd9ouj41PkD/8W55ub9AQKnPwGyxkkJA/Cz5t9VaREC+5OqGDRdGQKjO+ouurkdAMr7Z3DYVSUC0qsyY2mpKQHNTSjXTt0tALoDK78C8TEAf7YCEcJ5NQNFYoRH3bU5ANjsX1ABFT0CPBVVB/x9QQGkFN18LnFBAMLOFDz0pUUAIvWRwc8tRQAURWWs3c1JA9MEkf7Y6U0Dh1FTliARUQC7JJhou4lRA2HUMcY7DVUBqlNpMJJRWQA==", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#ff4757", "width": 2 }, "mode": "lines", "name": "True 2", "opacity": 0.4, "showlegend": true, "type": "scatter", "x": { "bdata": "AAAAAAAAPkB0b0BoK+08QPug8zWhSzxAM7QNEkHbO0BLr20hxFI7QJMUZ5ywtTpAHP/g1DwtOkBJSxRN/X45QHwoNCUT5ThAkPYcgdGkOEBxuCkku5A4QFqjX8TgbThAfME2qhIsOEAL04o7WQM4QBR0TJXh4jdAq6vZoJ8FOEA3D6Ep+DM4QB3SM5fnnDhAd0TeHuQHOUAXz8OIkv84QJoT0lzhijhA9GbcgQiNOEBxt51wEXA4QHybdXDMKDhAUxJkD434N0AXWLqFbwM4QO1Dya3hFzhAqvvlJ74tOEDPvA0Qnxg4QNj86sG4CjhAp2+u/OD9N0DfaDwQr643QHkrAEVq/jZAnxLK7KZSNkDX3giOn641QGF1GqYxgjVAaVlekU6ONUDrMrK/VUA1QO/PcrjrnDRA8i0Tfz/DM0AAKzXWlq8yQBDXk2EaLzJAKOaMJFb1MUDzjKpGrcIxQKxGeOe56TFAqGjTWElLMkBCiDFJvfwyQKgUlZt6KDRA2HRIYaLBNUAquxc1DIc3QA==", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "AAAAAAAANMC1EqGb+QMzwF3nbelP3THAxVzaO2v/MMCH+R515sgvwDTjTAJiBy7AvFZWd57YLMDzH71bUXQrwOn9H3b2uCrAUJUdKfqrKcC5O+n4jospwJzcI0LluSrAzuZF9+9iLMCYrbCkTl8uwM+fu4YHQjDA4maf+6umMcBOtJoVMR4zwM05JyAfpDTAjKq3xGEKN8C+PHn003I5wM5/9fNpsjvAyD5tN4KtPcB2BtmqNJ4/wEpizaAGpUDAmHVv/niUQcDxVIFQmq1CwMBHNJ5x3UPAbMEtaOwPRcAX7kL4vENGwNBt2lt+kEfAdD+eBk/cSMC2jdkRtSpKwOSOMmb7bUvAKgXolCG4TMBYpGULI+RNwPOAgQ/qGE/A3cFqX+NJUMAh8qUzMABRwN2ODfb4olHAqIXM34M2UsAGdAXrcNZSwMTl5+KjcFPA/R94Fcj8U8D9fAamsYdUwE2aqv+mE1XAJX+Pi9+TVcDZAHWf9P5VwHNErhdyXVbAgn1Tdr6+VsBBvHih6BZXwA==", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#00ff88", "width": 2 }, "mode": "lines", "name": "True 3", "opacity": 0.4, "showlegend": true, "type": "scatter", "x": { "bdata": "AAAAAAAAAAArIJ74yPfTP8tmh2Ri/9g/buovlN5kyj+nmtbG103ZP40UZlOzvus/l7MT3weT9j8PxWLvc/f9P33aGEO0ZgVAI2WvrK5uC0D4trfvtVkRQAqT3BgR4hVAGxowPND7GUB69+fndJ4dQM43hbrdciBAmw/Vf0sFIkDSeo2UD+EjQO4/zK2UnCVAWJGe0LUzJ0A6++OiGJgoQAK+GHHD6SpAojaSLdRDLUAS1D97hZkvQMVUctQanzBA6g2i7HfRMEDZcbQUVHowQKbN48ngBDBA+hOfqlv/LkAAMvXwhpUtQAw8VtNXuixAe0pAuMKmK0B6hxplZZ0qQG1OSt0TJCpARjE+74m4KUCJdB1psD8qQI0/4wDj+ylA+Dc2T71WKUAQG7f0q0ooQKbPtQ7wFSdASYPsyzoAJkC8Dwy0I3MkQB1mqi0n1yJAdFt0sDSgIECNwPknS/4bQGl+56KAmRdAapuPATM6E0DSw2answwPQFgaJw5TZgZA1IzCR3qG+j9+50bEO/bhPw==", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "AAAAAAAAREDjYWee/l5DQBHC77I0v0JAGWVLDokxQkA/BYZ+RqxBQKzlJyYIQUFAtebH4xDpQECwpvQ00a9AQPlyK18OfUBAfftd45ExQEDUPQz2euY/QF8BW2v/vj9AF5JI66ZwP0C6+9nOwPk+QIoo+eekMT5As7p7GR0fPUBXGvyQMFQ8QGLm06WBrjtAEY1zLZTnOkDcMDO9iAI6QHO4PpDqvjhAU4NvexFqN0AazAcFMDU2QN7PIW7a3DRAD/iQfk7aM0Cizb4ddxgzQLxmpBxsUTJAnyw54ulwMUBuFQ0fxtQwQDfj5vaSXTBAT9R4QG+jL0BEx7fQEKMuQDUpDQc6Py5A0TYCjUNeLUB3BPKhwakrQEealjRMsilALvyRMeiXKEAHEg6KZJQnQMDNM3L6fyZAvo/Sa6MQJUCWQofGnpgjQKYQVNlBxiFAN0GKdLGYHkCvNWfNrisZQMQyCT0izhVALBXSVQrwE0DjoUYH330SQBWF9yVJBxBAvGIGDQ/7CUBN7/hKEF8CQA==", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#00d4ff", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN 1", "showlegend": true, "type": "scatter", "x": { "bdata": "Jd+HgEIiRMDwCoJflGNDwBGKIIJzkELAnXej3FjrQcACcvCzyOJBwGqjjVEBkUHATOUJI8lbQMDj23JgGM8/wLVNsqtcmz7ASB6nqpyfPcDF2jmd/Vk7wJiNy839iznAsWz+RBzrOMARURjWpFc3wBg0VtO3wTXArQS4n956M8DdQnisa8MxwEZMNlRXhjLANfe6qQXyMsBVSyVRL14ywBI5lHjCRjPAi6M3W62DMcCZIiIeipMuwGbJ4glk4yzAXPjLzb5pK8ArbIM+2uIqwGmHYxxogSrA++WWyRnAKcBvEa9PFP8lwPwsLynDGyTAf6cgPW4IIcAwAQMvKokgwNaYx/DMxBjAhqCsZi1LEsB0pMJCX2YJwFBB4HZb0fy/mB0P3nHlpb8MN4XQzFLqP4sENmQXfwdA+V9iqSMuBUDbK2DNgbcQQAiNZ+vMfhZAFNhbKi6NIUAnvmLuSpEmQIGSWIuGayxAsELpuru6MEAQB+NspXwyQNF0O1r2rjNAGwA+GCJWNED9lTYRYM41QCy597PZQjZA", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "I5BKuVHHPsDWtYqtcCw9wE4LoUS2bDzA/qjM3bQePsBgiTegQPg7wEYfWctihTrA4txNhNmgOMB8M6sn3K82wJxtdLjINTXAVSj89wddMsCNAD4jFjMvwDWfPtJvLCvAA4V3vVx2JsBExASRLgwhwC+FRKe5ISDATj1oWtq7GMD6fkPkFp4RwKb6quLHpOy/3Qwbc5qc8z+MuiCuoK4LQE/n8D5dzxtATGV8L0VzIkDg+9P477MmQKww4jr0wStAweD+C3ocMkC6QOMrV+ozQNJoDWi5bTVA9FyuHiwGOkAZC4sM3qo+QBEr6PCdHEFAQqB0POwEREBSO8Yb9B5FQMicSqUDaEZAcNt/CU1LSEC1+uITg5RJQItkKKAIKUtAYIXyF8abS0D9Ij52PeZMQIwMHN21Ik5AZkS7qmBKT0BWHKOeM+ZPQJuTUqIGG1BAGyr3z0FwUEClbH8cMMJQQJntTGAVulFA9hhoNXdGUkBL6a6lECtTQA2Q2gfdt1NAwKDizF10VEAz1C9aJR5VQFoaxAbEXlZA", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#ff4757", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN 2", "showlegend": true, "type": "scatter", "x": { "bdata": "k4IHo8w+PkA5UXweXj4+QKCLcWq5yjxA3FHO6c7xO0Bv16tjl8A7QGxqnlxHZDxAL8ajG3MlPECVQHQrRvk6QNDFLf97tjpAjysmuRYdO0DCjAy+EvA6QFfmg0QFEDpAU8MiEhgIOUC74rGZgDw5QCXDQMqThDhA3PW0pSkNOEBvHk8Oe0Q5QBmBbgA1mzpAOsheKl2mOUBo7k6CCvc4QAjkPH37sDhAcAlebsPgOECmMi2KBjs4QNpM0Nt99jhAoRIYH9PBN0BaAiV5j844QGK5n0GPLTlAGagOuGFhOUBtxm0ZMcQ5QMUF5Xq3cTlAux/5CtC8OEDSWsJz4iM4QGC/z9Sg7zhAiPOCDIRGOEBCDIHXLyM3QDNyL9c3RjZAgzcQeuinNUBUEe2iM4g1QJqrno6yDjVA6r38d96cNUC0fY21rXQzQESUx285VzFAZlwzijQNMUC/+XJbHy4wQAh/aTAKHjBAec0/biMoMUB01WFjDt4wQNIv8+KwNzBAN1elTEa3MEAC2jKezjwzQH7d7/rrpTRA", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "XoSaM5tpNMCdW0UKY/8xwDJsUajvTjLAhNVwxB59McAbC6T5Tn8ywHbZELMUFTPAw8mNf2kaM8DEw+Wr4oIvwCqJww0zPy3AbIHASXMMKsCkE26CRX0mwBpLIbQ2ZibAdCtKqOccJcAtw38bDWUmwMfucdxwiSjATHhS7FvFKMAGCL1ZMLMwwNrg4tu+QjLAPgPRCXAUNMDm5A4UcN41wE2J9/xK2jjApjKHUvfIO8D7DjKlZgc+wGjruhOBFT/At2+PT4GDQMBcelSFpAFBwDPUVSiHnELAorlmM0aUQ8Bf+MdHw6NEwIoLy6MWKkbAjcJTwl2XR8DHgtJA6SdJwG/UafEc0knAWJeHqlsKS8Csc9xvI9BMwL2bOwODnU7A+1rUctAPUMC++lvRIE9QwCK0kLl36lDA5sEMZekQUcCPja5hYzlSwJ3jdk6ezFLAWAgA1PZNU8CDu1ngkRBUwG5M8qLo3FTAVAmyFGJfVcB4VvSHFQNWwIqFOg+6albAZk9g8muXVsDUFxgISMRWwEKc1L3UGFfA", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#00ff88", "dash": "dash", "width": 2 }, "mode": "lines", "name": "GNN 3", "showlegend": true, "type": "scatter", "x": { "bdata": "RNHW9Nf61L8Y09XY3W/wv4UbhWqrHee/0fCwhZst8D/Wo4fQMbz7P5w1aIQU7wFATxWl4b+o+D8dex3QVDPqP9zaubtpJQFA8/bUFELKBUBUYGLxxTsAQAHo55oivf8/SCNlCyoKBUAIOm3ofbMRQMKlOfb6CR1AQqDs0lZZIECZ42dL1zoiQL/a21KsXiRA/yY0+S9iJ0C3YbxOmOMpQGCE15NAdClAkNQLGRXKK0DcJO7HSg8vQFEjvyujsjBAvTLSYqVfMkDIFTAxykMxQEnRhGd8ejBA2ZKI+zKLMEAkUNkxb4kxQIt4nHJhcDJA33D2cYakMUAMfLyKQxYxQCdv92GSUS1Akae02KB1KkCqg43oPVooQG6/wgG44CZAKMfmzha1JkCLfV5uWk0lQKykc1qbKyhAnVappXuPJ0BIcDQnC+opQJiyAmdtISZA3l3ASAVvI0D7puDpSmoiQBzjnxObAiBAu9XeGChsHEB9glGuucoaQLnbQu59ORZA4UiPwD0MFUAI3w8F+1IOQH/B+kmCQvc/", "dtype": "f8" }, "xaxis": "x", "y": { "bdata": "3WLkm3PVQ0Cc2gYy8nFDQN39AC6FkUNAnkK4wqWhQkCP2XdryBdCQECz+DNLlkBA4k4FxGcEQUCaOgM6HPZAQDld4g4ybEBAcMjHE8ovQEDi/6r7NSQ/QHcdytxq+z5AjlXWwe7APkCIX3wnfOk+QIJQ1p6Bez1ANxW4rPVLPUAAX0XmGWI8QL3JJtnS2TpAbXMuNJvNOkDMKlO3SCk6QHokRNUjCTlADlnwYhkLOEAy+wpg0fs2QEtf0CziETZAkdIj3mZNM0B+F1F1zgIzQGBPi/bhcjJAf1AD7cz/MUD8pcOORjAxQEaJIK94izBAPmUBjK1hMECXjVf0em8wQM/MQztNXy5Ajn4myh0sLkANRJgt6zwtQNru1DhrDyxAYyGzXGI7LUDw6eexwN4sQPd3HFcGnihAk0Wo2y1zJkB3KiE2lPIlQPAULFoEbyVAQCTXJ+ezJECg3SlV/8wgQPML0gY7ghtA9ipwBD7BEkAjnaBpwnERQKjZqf4DzBFAMZA4kb+xCEBVg6gC5Wj5Pyyc7/ILIPk/", "dtype": "f8" }, "yaxis": "y" }, { "line": { "color": "#00d4ff", "width": 2 }, "mode": "lines", "opacity": 0.4, "showlegend": false, "type": "scatter", "x": { "bdata": "AAAAAAAARMCp0liTm1BDwMIOjzDQlkLAL/i+v4fjQcAk3AM3li5BwNAV42WOmkDAe77vN+3nP8D6ZN3ecHY+wPON9zczOz3AeTTd5t7UO8Bv1dGOa2E6wHRlMpAwaTnA3ilo/pQoOMDN5T9jqs42wJCUuQKm2zXAdhMqyPU0NcD8ywYkaKU0wBKyk/OvVzTAe7q0a0bbM8DB6nFn0PIywA2+njT+zjHAO1XgdSGMMMAA47SY4bkuwCSSfRdvdS3AMWz2BBLWK8CNFlEINVIqwFAzUIkTwyjAUmGzHM5CJ8CsoYPNsoolwCrjUfF4DiPAummgUPUKIMDEDFSb/NEZwJh0leEhfxXAynPgNYupEMBX/GBYERoEwBQ7pjXJMea/IdnGAWty6z9zVDzfpCYAQCP6r0j/nQxA9yyvDbexFUCbjxSSmVUdQH7H4iC42iJAImuceIZ7JkCkCZJjyLkqQNz7QF2j2C5Am+hTavhUMUCvRTueORgzQCyzL4C/kjRA8/Y6VMbcNUCpXJEfmdE2QA==", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "AAAAAAAAPsDSmYgZ7ZU9wOpF2MVSnzzA+lFNvbJ8O8DqqyTh+wI6wBqqW2yr5zfAvviHt3F3NcCVjulAOXQzwPvPUtTKhDHAy0j0S6IAL8AKgLY2/hArwP7QHRPAmybAYr1hqM6SIsCWFvorJNIcwML2on9yCRbAO8zxNsMADcDUfAnA+Mj5vzcBKEI9Yug/i1ZLtefXC0CghlMaO7QZQD20vTMrkiJAI6O88ssNKECgcsE6j3stQOTGG+ZTkDFAPSFGPCuKNEBRjEI2aLM3QG/9JLP58jpALd9ouj41PkD/8W55ub9AQKnPwGyxkkJA/Cz5t9VaREC+5OqGDRdGQKjO+ouurkdAMr7Z3DYVSUC0qsyY2mpKQHNTSjXTt0tALoDK78C8TEAf7YCEcJ5NQNFYoRH3bU5ANjsX1ABFT0CPBVVB/x9QQGkFN18LnFBAMLOFDz0pUUAIvWRwc8tRQAURWWs3c1JA9MEkf7Y6U0Dh1FTliARUQC7JJhou4lRA2HUMcY7DVUBqlNpMJJRWQA==", "dtype": "f8" }, "yaxis": "y2" }, { "line": { "color": "#ff4757", "width": 2 }, "mode": "lines", "opacity": 0.4, "showlegend": false, "type": "scatter", "x": { "bdata": "AAAAAAAAPkB0b0BoK+08QPug8zWhSzxAM7QNEkHbO0BLr20hxFI7QJMUZ5ywtTpAHP/g1DwtOkBJSxRN/X45QHwoNCUT5ThAkPYcgdGkOEBxuCkku5A4QFqjX8TgbThAfME2qhIsOEAL04o7WQM4QBR0TJXh4jdAq6vZoJ8FOEA3D6Ep+DM4QB3SM5fnnDhAd0TeHuQHOUAXz8OIkv84QJoT0lzhijhA9GbcgQiNOEBxt51wEXA4QHybdXDMKDhAUxJkD434N0AXWLqFbwM4QO1Dya3hFzhAqvvlJ74tOEDPvA0Qnxg4QNj86sG4CjhAp2+u/OD9N0DfaDwQr643QHkrAEVq/jZAnxLK7KZSNkDX3giOn641QGF1GqYxgjVAaVlekU6ONUDrMrK/VUA1QO/PcrjrnDRA8i0Tfz/DM0AAKzXWlq8yQBDXk2EaLzJAKOaMJFb1MUDzjKpGrcIxQKxGeOe56TFAqGjTWElLMkBCiDFJvfwyQKgUlZt6KDRA2HRIYaLBNUAquxc1DIc3QA==", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "AAAAAAAANMC1EqGb+QMzwF3nbelP3THAxVzaO2v/MMCH+R515sgvwDTjTAJiBy7AvFZWd57YLMDzH71bUXQrwOn9H3b2uCrAUJUdKfqrKcC5O+n4jospwJzcI0LluSrAzuZF9+9iLMCYrbCkTl8uwM+fu4YHQjDA4maf+6umMcBOtJoVMR4zwM05JyAfpDTAjKq3xGEKN8C+PHn003I5wM5/9fNpsjvAyD5tN4KtPcB2BtmqNJ4/wEpizaAGpUDAmHVv/niUQcDxVIFQmq1CwMBHNJ5x3UPAbMEtaOwPRcAX7kL4vENGwNBt2lt+kEfAdD+eBk/cSMC2jdkRtSpKwOSOMmb7bUvAKgXolCG4TMBYpGULI+RNwPOAgQ/qGE/A3cFqX+NJUMAh8qUzMABRwN2ODfb4olHAqIXM34M2UsAGdAXrcNZSwMTl5+KjcFPA/R94Fcj8U8D9fAamsYdUwE2aqv+mE1XAJX+Pi9+TVcDZAHWf9P5VwHNErhdyXVbAgn1Tdr6+VsBBvHih6BZXwA==", "dtype": "f8" }, "yaxis": "y2" }, { "line": { "color": "#00ff88", "width": 2 }, "mode": "lines", "opacity": 0.4, "showlegend": false, "type": "scatter", "x": { "bdata": "AAAAAAAAAAArIJ74yPfTP8tmh2Ri/9g/buovlN5kyj+nmtbG103ZP40UZlOzvus/l7MT3weT9j8PxWLvc/f9P33aGEO0ZgVAI2WvrK5uC0D4trfvtVkRQAqT3BgR4hVAGxowPND7GUB69+fndJ4dQM43hbrdciBAmw/Vf0sFIkDSeo2UD+EjQO4/zK2UnCVAWJGe0LUzJ0A6++OiGJgoQAK+GHHD6SpAojaSLdRDLUAS1D97hZkvQMVUctQanzBA6g2i7HfRMEDZcbQUVHowQKbN48ngBDBA+hOfqlv/LkAAMvXwhpUtQAw8VtNXuixAe0pAuMKmK0B6hxplZZ0qQG1OSt0TJCpARjE+74m4KUCJdB1psD8qQI0/4wDj+ylA+Dc2T71WKUAQG7f0q0ooQKbPtQ7wFSdASYPsyzoAJkC8Dwy0I3MkQB1mqi0n1yJAdFt0sDSgIECNwPknS/4bQGl+56KAmRdAapuPATM6E0DSw2answwPQFgaJw5TZgZA1IzCR3qG+j9+50bEO/bhPw==", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "AAAAAAAAREDjYWee/l5DQBHC77I0v0JAGWVLDokxQkA/BYZ+RqxBQKzlJyYIQUFAtebH4xDpQECwpvQ00a9AQPlyK18OfUBAfftd45ExQEDUPQz2euY/QF8BW2v/vj9AF5JI66ZwP0C6+9nOwPk+QIoo+eekMT5As7p7GR0fPUBXGvyQMFQ8QGLm06WBrjtAEY1zLZTnOkDcMDO9iAI6QHO4PpDqvjhAU4NvexFqN0AazAcFMDU2QN7PIW7a3DRAD/iQfk7aM0Cizb4ddxgzQLxmpBxsUTJAnyw54ulwMUBuFQ0fxtQwQDfj5vaSXTBAT9R4QG+jL0BEx7fQEKMuQDUpDQc6Py5A0TYCjUNeLUB3BPKhwakrQEealjRMsilALvyRMeiXKEAHEg6KZJQnQMDNM3L6fyZAvo/Sa6MQJUCWQofGnpgjQKYQVNlBxiFAN0GKdLGYHkCvNWfNrisZQMQyCT0izhVALBXSVQrwE0DjoUYH330SQBWF9yVJBxBAvGIGDQ/7CUBN7/hKEF8CQA==", "dtype": "f8" }, "yaxis": "y2" }, { "line": { "color": "#00d4ff", "dash": "dash", "width": 2 }, "mode": "lines", "showlegend": false, "type": "scatter", "x": { "bdata": "Uaf0558/Q8CBPCTifHRCwCfc5G9nqEHAc2QGWbzbQMCUnLeq+B9AwI1qRTK90z7AhTTqp4FIPcDj7ijg+/s7wNC99GBqYDrASTr7d1boOMAGzttxm2M3wEAmimcx4DXACXYenMNZNMDhC7kefeMywMUCGSA+bTHAusgree/ZL8APlmRqTLsswBBT6CGFnCnArDJddp3TJsCPzONoWJ4jwFQpXh9fdiDAXBVssRJQGsCshL5nZy4UwIpXEbZhigvAbOvyww0V/b/D3I2gYdHQv+IoSxJ8NPY/Yyom+P7yB0CQPPwnoDwSQG28imUBWhhAqBPxYAjhHkDclvfNfZciQFrg6hJrjCVAeXexosmpKEBpWuHa58MrQCP0SHT64S5ABk8lp08AMUAhJ6vI2oEyQOz7634YCTRArj4Nwj+SNUAVcaggbQE3QFTNP1fjejhARgs5+if2OUD+uWaaBnE7QLt1CSVQ6zxA2HLGI39cPkCc/vTSxtg/QN6fQeiiqEBASbAr2RVmQUCE/3htoyZCQAJ7hR8/2kJA", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "N8o2wtZTPcBHhwgciJ08wLkYCv5q+TvA6/+MNoSRO8CsDgG+3406wGir4pa61jnA0n0y/JcJOcApUrQOb0M4wH8KI8qqhzfA6jttfAutNsBPbDw2JsI1wKEztzuC1zTAW/9hm23pM8DY8GZJsQ8zwCQD722/+DHAjK865rEiMcBK9Bg14FwwwBrWdtoslS7Ast4NmxHeLMBrl9nH7TcrwBQJYBcHVynA+iU31MZuJ8AqSfoR+H4lwPQ0t9jLeiPAeqb9spCVIcD/Sfj/EB0fwB3MhP1T3BrAuqDS0nwGF8A8+8aWl8oSwDobmGOn9Q3Ao6A2kbnRBsBJaaKs12z+v9IBML7Rku2/lPFwnw3XlD+F8jZ2V4HtPy8gjtOsDP0/qooXX6OrBkBC8X3CBIkOQLJM3Is1AhNATdLt8hiwFkB/4ldfLqYaQHB5yCbPaR5A7+uYe5UTIUCVBGXsGdQiQJWtWOCLpiRA4jxNOHCIJkAx5y8G4W8oQATwHMFITSpAxMdByjYNLEAtPX1OQsUtQCRtVjrvfS9A", "dtype": "f8" }, "yaxis": "y2" }, { "line": { "color": "#ff4757", "dash": "dash", "width": 2 }, "mode": "lines", "showlegend": false, "type": "scatter", "x": { "bdata": "kuIT8v5aQEA/oKdigrs/QJiQPdkWmT5A2zpmutaxPUA7DhvjE7o8QMhr7NFq6jtAItOf7GQEO0CdmmZRciI6QObbltmOTDlAXaVZRz6GOEDebBC8Brk3QNzmtbHC6DZAWh0VOhXuNUB2DaGuZiU1QOAoCmRiRjRAuYFYhFFjM0AEwtCnE5wyQE4sdjzKqzFAQ5xQ3dXHMEAMfRDI+fAvQKvhGTE6Ny5AU0UXt9aKLEAzFQ8KHbkqQDj5cqd9+ShA9bbSTdVEJ0AP+EZkwW4lQB9P6xuNtyNAFjExCTUGIkCrIoS4kj0gQKD0J/Ql1xxAOUdgOG21GUAydIGWaFsWQG/jAFzYtBJAhXDDxt62DkBVlYkjwu0HQCGCok5WQgFAI9qZMlHZ9T8MkfaClo/fP1yOQcB6mNS/BlW7uvjO8b+Flh9GwNf/v3b+Uif/zQbAZZWPPYG4DcBzfZT8+gcSwLINA4+0WRXAvWkVoe6tGMCP4koKzu4bwOjQ+FQbJx/AyIE+XicDIcCVfcbYKJ0iwPIBG6V/SyTA", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "cLpkIs+sNcCrWgT3WAs1wGyh56khoTTAVXAewQhMNMD+AI+vj+UzwHVi0/8OkDPASELpUxQ5M8AAiHeGv68ywML604mQLjLAdVjuHiisMcC/MevGMCAxwMwD7yaFnzDAfSe2PKYTMMBKunP3zk8vwDrCzg7XWy7AnNgZqseTLcBYoLzQA44swEpPLl6svCvAMD1DCmDfKsB3842NHyIqwHxORjJ2PynAtH/hyhw3KMDcgQOK0jwnwFpJqJmdLSbAao8AbjYuJcA924/gwBMkwLkNr5B40SLAD7Cfh1THIcCXypqTK4UgwCDjHQif5B7ALMB7OErrHMBrQ1yhN9AawO1zPqsRhRjA4rMdlFRrFsCPXhshGXcUwOlTE+rWjhLAlmvU0CEjEMDe36ExBakLwM6nirZIZQfAES80LeQ7A8ATZhOe9QL9v33tzZ9dXPS/PjtODxi+5797pd+8dPnQv1nkh3zfVM4/5cr284Ij6T8734R4I0D1PyuaCQRE3/0/9OjcQyXLAkDTpWdLFH0GQPvZh4UtCwpA", "dtype": "f8" }, "yaxis": "y2" }, { "line": { "color": "#00ff88", "dash": "dash", "width": 2 }, "mode": "lines", "showlegend": false, "type": "scatter", "x": { "bdata": "P6yScoeoAMBdcw8uxZP7v75jqFT0t/S//t8niXgO5r9Jp27ahC7hvyhncQ6RLaO/fYszWbl11T96dy5xAiDlPzi+trbg+fE/mRg71cy0+D+kizrSijT+P6Gdj+zRHQJAJMZQPXw2BUD97VqzeHoHQELbjOTRQwpAf6oZ4Y17DUAC7B1TYLEQQMkwfXaPMBJAOgXg7SSAE0DBloKF3QsVQM03Nj1gbBZAWJGwU3EKGEACefq47kkZQGANcN+OZhpAWqOqQrrVG0D3YUJfIOQcQHs4glgrTx5A9BeIznO4H0DFhE3lXXsgQInpQ4E4IiFAb8rFjajqIUB6CXV+b6IiQC78DGYvKyNAp9EtD4HgI0C+7vqfo5AkQE2i3mcASiVA1yDH8GsOJkAhO3xZ9a8mQFOWeqQpZidABovT6LUlKEBisEHPvbIoQDtz12PeTilACN4aWKPsKUA3PRXcd5kqQDekjG2gOytAQrrP8sTUK0AMZcsoKoAsQIX2h83wKS1AyadCKT7rLUDK2U64CaAuQOoYxoLTIC9A", "dtype": "f8" }, "xaxis": "x2", "y": { "bdata": "i+oVytnwQ0B1ninYfVtDQKsBHvTe3EJA4EiXhf8/QkD+OEOlwo9BQLPoV7pc5UBA5jbKZjZeQECuadIO6qo/QNvjkN/Viz5ATaPnpEN4PUCg2fELI1w8QBSRQtl5TTtAntmgsF8/OkCzzLTyl0M5QCnS9neGPDhA7uvc3mcqN0C5GmQd6vw1QGp5RuMSxzRACWWp+kPHM0CXl8a2s6AyQKLysdHofjFAPP7MSrNIMEDF0qeYkT8uQEwwHBOCNCxAwwWNUqL2KUAP5OVO77onQNZCiB6JgCVAX3s/DuVUI0CI++i3/EYhQH6KxKydFx5AiNEdGaBaGUAg9JLooA0VQE3YFIB2zhBAc2gPRsf+CEBqAVkaIhsAQAzORRRuXuw/vwJD3DbIu7+SMKMwHTHyv4XsM8arpAHATDCIdzNHCsAdVAbRLy0RwFOt2k+zaBXAo7HLvSetGcCVd68KSxsewJ2yfoNhOCHAGqloeD1JI8CIchm+amElwHQ25YgxdCfAiRJlP+6UKcC4zI0sh9ArwEHTKhLVAC7A", "dtype": "f8" }, "yaxis": "y2" } ], "layout": { "annotations": [ { "font": { "size": 16 }, "showarrow": false, "text": "GNN Tracking", "x": 0.225, "xanchor": "center", "xref": "paper", "y": 1, "yanchor": "bottom", "yref": "paper" }, { "font": { "size": 16 }, "showarrow": false, "text": "JPDA Tracking", "x": 0.775, "xanchor": "center", "xref": "paper", "y": 1, "yanchor": "bottom", "yref": "paper" } ], "height": 450, "template": { "layout": { "font": { "color": "#e6edf3" }, "paper_bgcolor": "#0d1117", "plot_bgcolor": "#0d1117", "xaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" }, "yaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" } } }, "xaxis": { "anchor": "y", "domain": [ 0, 0.45 ], "title": { "text": "X position" } }, "xaxis2": { "anchor": "y2", "domain": [ 0.55, 1 ], "title": { "text": "X position" } }, "yaxis": { "anchor": "x", "domain": [ 0, 1 ], "title": { "text": "Y position" } }, "yaxis2": { "anchor": "x2", "domain": [ 0, 1 ], "title": { "text": "Y position" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Compare GNN vs JPDA\n", "fig = make_subplots(rows=1, cols=2, subplot_titles=('GNN Tracking', 'JPDA Tracking'),\n", " horizontal_spacing=0.1)\n", "\n", "tracker_data = [('GNN', gnn_tracks), ('JPDA', jpda_tracks)]\n", "\n", "for col, (tracker_name, tracks) in enumerate(tracker_data, 1):\n", " # True trajectories\n", " for i, track in enumerate(true_tracks):\n", " fig.add_trace(\n", " go.Scatter(x=track[:, 0], y=track[:, 2], mode='lines',\n", " name=f'True {i+1}' if col == 1 else None,\n", " line=dict(color=colors[i], width=2), opacity=0.4,\n", " showlegend=(col == 1)),\n", " row=1, col=col\n", " )\n", " \n", " # Tracker estimates\n", " for i, track in enumerate(tracks):\n", " history = np.array(track.history)\n", " fig.add_trace(\n", " go.Scatter(x=history[:, 0], y=history[:, 2], mode='lines',\n", " name=f'{tracker_name} {i+1}' if col == 1 else None,\n", " line=dict(color=colors[i], width=2, dash='dash'),\n", " showlegend=(col == 1)),\n", " row=1, col=col\n", " )\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " height=450,\n", ")\n", "fig.update_xaxes(title_text='X position', row=1, col=1)\n", "fig.update_xaxes(title_text='X position', row=1, col=2)\n", "fig.update_yaxes(title_text='Y position', row=1, col=1)\n", "fig.update_yaxes(title_text='Y position', row=1, col=2)\n", "\n", "fig.show()" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Position RMSE (m):\n", "Track GNN JPDA\n", "--------------------------------\n", "Target 1 3.181 3.233\n", "Target 2 3.149 2.915\n", "Target 3 2.159 2.192\n", "--------------------------------\n", "Average 2.830 2.780\n" ] } ], "source": [ "# Compute tracking errors\n", "def compute_position_rmse(tracker_tracks, true_tracks):\n", " \"\"\"Compute RMSE for each track.\"\"\"\n", " rmse = []\n", " for i, (tracker, truth) in enumerate(zip(tracker_tracks, true_tracks)):\n", " history = np.array(tracker.history)\n", " # Align lengths\n", " min_len = min(len(history), len(truth))\n", " pos_error = np.sqrt((history[:min_len, 0] - truth[:min_len, 0])**2 + \n", " (history[:min_len, 2] - truth[:min_len, 2])**2)\n", " rmse.append(np.sqrt(np.mean(pos_error**2)))\n", " return rmse\n", "\n", "gnn_rmse = compute_position_rmse(gnn_tracks, true_tracks)\n", "jpda_rmse = compute_position_rmse(jpda_tracks, true_tracks)\n", "\n", "print(\"Position RMSE (m):\")\n", "print(f\"{'Track':<10} {'GNN':>10} {'JPDA':>10}\")\n", "print(\"-\" * 32)\n", "for i in range(n_targets):\n", " print(f\"Target {i+1:<4} {gnn_rmse[i]:>10.3f} {jpda_rmse[i]:>10.3f}\")\n", "print(\"-\" * 32)\n", "print(f\"{'Average':<10} {np.mean(gnn_rmse):>10.3f} {np.mean(jpda_rmse):>10.3f}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 4. Performance Evaluation with OSPA\n", "\n", "The Optimal Subpattern Assignment (OSPA) metric provides a principled way to measure multi-target tracking performance:\n", "\n", "$$d_{OSPA}(X, Y) = \\left( \\frac{1}{n} \\left( \\min_{\\pi} \\sum_{i=1}^m d^p(x_i, y_{\\pi(i)}) + c^p(n-m) \\right) \\right)^{1/p}$$" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Compute OSPA over time\n", "def compute_ospa_sequence(tracker_tracks, true_tracks, c=10, p=2):\n", " \"\"\"Compute OSPA at each time step.\"\"\"\n", " ospa_values = []\n", " \n", " # Get minimum length\n", " min_len = min(\n", " min(len(t.history) for t in tracker_tracks),\n", " min(len(t) for t in true_tracks)\n", " )\n", " \n", " for k in range(min_len):\n", " # Get positions at time k\n", " est_pos = np.array([[t.history[k][0], t.history[k][2]] for t in tracker_tracks])\n", " true_pos = np.array([[t[k, 0], t[k, 2]] for t in true_tracks])\n", " \n", " # Compute OSPA\n", " ospa_val = ospa(est_pos, true_pos, c=c, p=p)\n", " ospa_values.append(ospa_val)\n", " \n", " return np.array(ospa_values)\n", "\n", "gnn_ospa = compute_ospa_sequence(gnn_tracks, true_tracks)\n", "jpda_ospa = compute_ospa_sequence(jpda_tracks, true_tracks)\n", "\n", "fig = go.Figure()\n", "\n", "time = np.arange(len(gnn_ospa)) * dt\n", "fig.add_trace(\n", " go.Scatter(x=time, y=gnn_ospa, mode='lines',\n", " name=f'GNN (mean: {np.mean(gnn_ospa):.2f})',\n", " line=dict(color='#00d4ff', width=2))\n", ")\n", "fig.add_trace(\n", " go.Scatter(x=time, y=jpda_ospa, mode='lines',\n", " name=f'JPDA (mean: {np.mean(jpda_ospa):.2f})',\n", " line=dict(color='#ff4757', width=2))\n", ")\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='OSPA Metric Over Time',\n", " xaxis_title='Time (s)',\n", " yaxis_title='OSPA distance (m)',\n", " height=400,\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Summary & Learning Path\n", "\n", "### Association Methods Comparison\n", "\n", "| Method | Pros | Cons | Use Cases |\n", "|--------|------|------|-----------|\n", "| **GNN** | O(n³) time, simple | Hard decisions, track swaps | Real-time applications, low clutter |\n", "| **JPDA** | Soft associations, ambiguity handling | O(n²^m) exponential, all hypotheses | Medium clutter, medium number targets |\n", "| **MHT** | Optimal, deferred decisions | O(2^k) exponential, hypothesis explosion | Offline, backtracking allowed |\n", "| **Auction** | Distributed, robust | Slower convergence | Network scenarios, decentralized |\n", "\n", "### 4-Week Curriculum\n", "\n", "**Week 1: Fundamentals**\n", "- Day 1-2: Bayesian filtering basics, Kalman filter track propagation\n", "- Day 3-4: Gating, feasible region computation, mahalanobis distance\n", "- Day 5: Single-target tracking vs multi-target, nearest neighbor association\n", "\n", "**Week 2: GNN & JPDA**\n", "- Day 1-2: Global Nearest Neighbor algorithm, Hungarian algorithm complexity\n", "- Day 3-4: Joint Probabilistic Data Association, conditional probabilities\n", "- Day 5: Implementation comparison, performance benchmarking\n", "\n", "**Week 3: Advanced Association**\n", "- Day 1-2: Multiple Hypothesis Tracking (MHT), hypothesis trees\n", "- Day 3-4: Hypothesis management, pruning strategies, N-scan pruning\n", "- Day 5: Auction algorithm, distributed assignment\n", "\n", "**Week 4: Integration & Applications**\n", "- Day 1-2: Track initiation and confirmation, quality gates\n", "- Day 3-4: Track management, merge/split handling\n", "- Day 5: Benchmark datasets, OSPA metric interpretation, real-world tuning\n", "\n", "### Advanced Topics\n", "\n", "**Multiple Hypothesis Tracking (MHT)**\n", "- Maintains multiple hypotheses throughout tracking window\n", "- Each measurement generates competing hypotheses\n", "- Pruning mitigates exponential growth: N-scan pruning, score thresholding\n", "- Optimal but requires memory management\n", "\n", "**IMMH (Interacting Multiple Model Hypotheses)**\n", "- Combines model mixing with hypothesis tree\n", "- Handles maneuvering targets with multiple motion models\n", "- Uses Markov chain model transitions\n", "\n", "**Auction Algorithm for Assignment**\n", "- Distributed alternative to Hungarian algorithm\n", "- Each track \"bids\" for measurements\n", "- Converges to ε-optimal solution\n", "- Robust to communication delays\n", "\n", "**Track Quality Assessment**\n", "- Confirmation gates prevent spurious track initiation\n", "- Quality scores based on measurement-to-track consistency\n", "- Covariance ellipse size monitors filter divergence\n", "- OSPA component breakdown: localization + cardinality error\n", "\n", "## Progressive Exercises\n", "\n", "**Exercise 1: Single Target Baseline** ⭐\n", "- Modify code to track only 1 target (set n_targets=1)\n", "- Observe GNN and JPDA performance without association ambiguity\n", "- Expected: Both methods equivalent, clean sequential association\n", "\n", "**Exercise 2: Track Crossing** ⭐⭐\n", "- Create scenario where 2 targets cross paths (modify initial_states)\n", "- Observe track swap behavior in GNN vs soft decisions in JPDA\n", "- Analyze: Which association method recovers from swap? How?\n", "\n", "**Exercise 3: Clutter Sweep** ⭐⭐\n", "- Parameterize lambda_clutter from [0.5, 1, 2, 5, 10]\n", "- Plot OSPA vs clutter density for GNN and JPDA\n", "- Identify: At what clutter level does JPDA outperform GNN?\n", "\n", "**Exercise 4: MHT Implementation** ⭐⭐⭐\n", "- Start with GNN code, maintain hypothesis tree\n", "- Implement N-scan pruning: keep top 5 hypotheses per scan\n", "- Compare: MHT performance vs GNN/JPDA (should be optimal)\n", "\n", "**Exercise 5: Track Management** ⭐⭐⭐\n", "- Add track initiation logic: create tracks from confirmed measurement clusters\n", "- Implement confirmation threshold: require 3 consecutive detections\n", "- Add deletion: remove tracks with >5 consecutive misses\n", "- Expected: Graceful handling of appearing/disappearing targets\n", "\n", "**Exercise 6: Incomplete Data Association** ⭐⭐⭐⭐\n", "- Simulate measurement origin uncertainty (target vs clutter probability)\n", "- Use likelihood ratios: P(z|target) / P(z|clutter) as soft measurements\n", "- Implement: Soft-gating instead of hard chi-square threshold\n", "- Compare: Likelihood-based JPDA vs traditional gating\n", "\n", "## Core References\n", "\n", "1. **Bar-Shalom, Y., & Li, X. R. (1995).** *Multitarget-Multisensor Tracking: Principles and Techniques*. Artech House. — Foundational text on MTT theory\n", "2. **Blackman, S. S., & Popoli, R. (1999).** *Design and Analysis of Modern Tracking Systems*. Artech House. — Comprehensive implementation guide\n", "3. **Schuhmacher, D., Vo, B. T., & Vo, B. N. (2008).** \"A consistent metric for performance evaluation of multi-object filters.\" *IEEE transactions on signal processing*, 56(8), 3447-3457. — OSPA metric definition\n", "\n", "## Advanced References\n", "\n", "4. **Reid, D. B. (1979).** \"An algorithm for tracking multiple targets.\" *IEEE transactions on Automatic Control*, 24(6), 843-854. — Classical JPDA paper\n", "5. **Kuhn, H. W. (1955).** \"The Hungarian method for the assignment problem.\" *Naval research logistics quarterly*, 2(1-2), 83-97. — Hungarian algorithm foundation\n", "6. **Cox, I. J., & Hingorani, S. L. (1996).** \"An efficient implementation of Reid's multiple hypothesis tracking algorithm and its evaluation for the purpose of visual tracking.\" *IEEE transactions on pattern analysis and machine intelligence*, 18(2), 138-150. — MHT implementation insights\n", "\n", "## PyTCL API Documentation\n", "\n", "- [`gnn_association()`](https://github.com/nrl-ai/nrl-tracker/blob/main/pytcl/assignment_algorithms/data_association.py): Greedy nearest neighbor\n", "- [`jpda()`](https://github.com/nrl-ai/nrl-tracker/blob/main/pytcl/assignment_algorithms/jpda.py): Joint probabilistic association\n", "- [`ospa()`](https://github.com/nrl-ai/nrl-tracker/blob/main/pytcl/performance_evaluation/__init__.py): Optimal subpattern assignment metric\n", "- [`hungarian()`](https://github.com/nrl-ai/nrl-tracker/blob/main/pytcl/assignment_algorithms/two_dimensional/assignment.py): Hungarian algorithm solver" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.0" } }, "nbformat": 4, "nbformat_minor": 4 }