{ "cells": [ { "cell_type": "markdown", "id": "cell-0", "metadata": {}, "source": [ "# Network Flow for Assignment Problems\n", "\n", "This notebook demonstrates network flow techniques for solving assignment problems in tracking applications. We cover:\n", "\n", "1. **Assignment Problem Basics** - Matching measurements to tracks\n", "2. **Network Flow Formulation** - Converting assignments to flow networks\n", "3. **Successive Shortest Paths** - Finding optimal flow\n", "4. **Dijkstra-Optimized Algorithm** - High-performance implementation\n", "5. **Comparison with Hungarian Algorithm** - Performance trade-offs\n", "\n", "## Prerequisites\n", "\n", "```bash\n", "pip install nrl-tracker plotly numpy scipy networkx\n", "```" ] }, { "cell_type": "code", "execution_count": 1, "id": "cell-1", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import plotly.graph_objects as go\n", "from plotly.subplots import make_subplots\n", "import networkx as nx\n", "import time\n", "\n", "from pytcl.assignment_algorithms.network_flow import (\n", " FlowEdge, FlowStatus,\n", " assignment_to_flow_network,\n", " min_cost_flow_successive_shortest_paths,\n", " min_cost_flow_simplex,\n", " assignment_from_flow_solution,\n", " min_cost_assignment_via_flow,\n", ")\n", "from pytcl.assignment_algorithms import hungarian\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", "id": "cell-2", "metadata": {}, "source": [ "## 1. The Assignment Problem in Tracking\n", "\n", "In multi-target tracking, each time step requires associating:\n", "- **Tracks**: Existing estimates of target states\n", "- **Measurements**: New sensor observations\n", "\n", "The assignment problem finds the optimal one-to-one matching that minimizes total cost.\n", "\n", "### Problem Formulation\n", "\n", "Given:\n", "- $m$ tracks and $n$ measurements\n", "- Cost matrix $C$ where $C_{ij}$ is cost of assigning track $i$ to measurement $j$\n", "\n", "Find: Assignment matrix $X$ where $X_{ij} \\in \\{0, 1\\}$ minimizing:\n", "\n", "$$\\min \\sum_{i,j} C_{ij} X_{ij}$$\n", "\n", "Subject to:\n", "$$\\sum_j X_{ij} \\leq 1 \\quad \\forall i \\quad \\text{(each track assigned at most once)}$$\n", "$$\\sum_i X_{ij} \\leq 1 \\quad \\forall j \\quad \\text{(each measurement assigned at most once)}$$" ] }, { "cell_type": "code", "execution_count": 2, "id": "cell-3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cost Matrix (squared distance):\n", " Meas 0 Meas 1 Meas 2 Meas 3 \n", "Track 0 0.05 23.05 23.57 200.00 \n", "Track 1 24.05 0.05 22.57 125.00 \n", "Track 2 20.20 22.10 0.02 92.25 \n" ] } ], "source": [ "# Example: 3 tracks, 4 measurements\n", "# Cost based on distance/likelihood\n", "\n", "# Track positions\n", "tracks = np.array([\n", " [0, 0], # Track 0 at origin\n", " [5, 0], # Track 1 at (5, 0)\n", " [2.5, 4], # Track 2 at (2.5, 4)\n", "])\n", "\n", "# Measurement positions\n", "measurements = np.array([\n", " [0.1, 0.2], # Measurement 0 near Track 0\n", " [4.8, -0.1], # Measurement 1 near Track 1\n", " [2.6, 4.1], # Measurement 2 near Track 2\n", " [10, 10], # Measurement 3 (spurious/clutter)\n", "])\n", "\n", "# Compute cost matrix (squared distance)\n", "n_tracks = len(tracks)\n", "n_meas = len(measurements)\n", "\n", "cost_matrix = np.zeros((n_tracks, n_meas))\n", "for i in range(n_tracks):\n", " for j in range(n_meas):\n", " cost_matrix[i, j] = np.sum((tracks[i] - measurements[j])**2)\n", "\n", "print(\"Cost Matrix (squared distance):\")\n", "print(f\"{'':10s}\", end='')\n", "for j in range(n_meas):\n", " print(f\"Meas {j:2d} \", end='')\n", "print()\n", "\n", "for i in range(n_tracks):\n", " print(f\"Track {i:2d} \", end='')\n", " for j in range(n_meas):\n", " print(f\"{cost_matrix[i, j]:7.2f} \", end='')\n", " print()" ] }, { "cell_type": "code", "execution_count": 3, "id": "cell-4", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "marker": { "color": "#00d4ff", "size": 16, "symbol": "square" }, "mode": "markers+text", "name": "Tracks", "text": [ "T0", "T1", "T2" ], "textfont": { "color": "#00d4ff" }, "textposition": "top right", "type": "scatter", "x": { "bdata": "AAAAAAAAAAAAAAAAAAAUQAAAAAAAAARA", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAAAAAAAAAAAAAAAAAAAAAABBA", "dtype": "f8" } }, { "marker": { "color": "#ff4757", "size": 16, "symbol": "circle" }, "mode": "markers+text", "name": "Measurements", "text": [ "M0", "M1", "M2", "M3" ], "textfont": { "color": "#ff4757" }, "textposition": "bottom right", "type": "scatter", "x": { "bdata": "mpmZmZmZuT8zMzMzMzMTQM3MzMzMzARAAAAAAAAAJEA=", "dtype": "f8" }, "y": { "bdata": "mpmZmZmZyT+amZmZmZm5v2ZmZmZmZhBAAAAAAAAAJEA=", "dtype": "f8" } }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 0, 0.1 ], "y": [ 0, 0.2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 0, 4.8 ], "y": [ 0, -0.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 0, 2.6 ], "y": [ 0, 4.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 0, 10 ], "y": [ 0, 10 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 5, 0.1 ], "y": [ 0, 0.2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 5, 4.8 ], "y": [ 0, -0.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 5, 2.6 ], "y": [ 0, 4.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 5, 10 ], "y": [ 0, 10 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 2.5, 0.1 ], "y": [ 4, 0.2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 2.5, 4.8 ], "y": [ 4, -0.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 2.5, 2.6 ], "y": [ 4, 4.1 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 0.5 }, "mode": "lines", "opacity": 0.2, "showlegend": false, "type": "scatter", "x": [ 2.5, 10 ], "y": [ 4, 10 ] } ], "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": "Track-to-Measurement Assignment Problem" }, "xaxis": { "scaleanchor": "y", "scaleratio": 1, "title": { "text": "X" } }, "yaxis": { "title": { "text": "Y" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize tracks and measurements\n", "fig = go.Figure()\n", "\n", "# Plot tracks\n", "fig.add_trace(\n", " go.Scatter(x=tracks[:, 0], y=tracks[:, 1], mode='markers+text',\n", " marker=dict(size=16, color='#00d4ff', symbol='square'),\n", " text=[f'T{i}' for i in range(len(tracks))],\n", " textposition='top right', textfont=dict(color='#00d4ff'),\n", " name='Tracks')\n", ")\n", "\n", "# Plot measurements\n", "fig.add_trace(\n", " go.Scatter(x=measurements[:, 0], y=measurements[:, 1], mode='markers+text',\n", " marker=dict(size=16, color='#ff4757', symbol='circle'),\n", " text=[f'M{j}' for j in range(len(measurements))],\n", " textposition='bottom right', textfont=dict(color='#ff4757'),\n", " name='Measurements')\n", ")\n", "\n", "# Draw all possible associations (faint lines)\n", "for i in range(n_tracks):\n", " for j in range(n_meas):\n", " fig.add_trace(\n", " go.Scatter(x=[tracks[i, 0], measurements[j, 0]], \n", " y=[tracks[i, 1], measurements[j, 1]],\n", " mode='lines', line=dict(color='gray', width=0.5),\n", " opacity=0.2, showlegend=False, hoverinfo='skip')\n", " )\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='Track-to-Measurement Assignment Problem',\n", " xaxis_title='X',\n", " yaxis_title='Y',\n", " height=500,\n", " xaxis=dict(scaleanchor='y', scaleratio=1),\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "id": "cell-5", "metadata": {}, "source": [ "## 2. Network Flow Formulation\n", "\n", "The assignment problem can be converted to a min-cost max-flow network:\n", "\n", "```\n", " c[0,0] c[0,1] c[0,2] c[0,3]\n", " Worker 0 ─────> Task 0 ──> Task 1 ──> Task 2 ──> Task 3\n", " / \\ /\n", " / c[1,0] c[1,1] c[1,2] / c[1,3]\n", "Source ─> W1 ─────────────────────────────────────────────\n", " \\ c[2,0] c[2,1] c[2,2] c[2,3]\n", " \\ Worker 2 ────────────────────────────────────> Sink\n", "```\n", "\n", "### Network Structure\n", "\n", "- **Source**: Supplies $m$ units of flow (one per track)\n", "- **Worker nodes**: One per track, connected to source with capacity 1\n", "- **Task nodes**: One per measurement, connected to all workers with capacity 1\n", "- **Sink**: Demands $m$ units of flow\n", "- **Edge costs**: Assignment costs $C_{ij}$" ] }, { "cell_type": "code", "execution_count": 4, "id": "cell-6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Network Structure\n", "============================================================\n", "Number of nodes: 9\n", "Number of edges: 19\n", "\n", "Nodes: [np.str_('source'), np.str_('worker_0'), np.str_('worker_1'), np.str_('worker_2'), np.str_('task_0'), np.str_('task_1'), np.str_('task_2'), np.str_('task_3'), np.str_('sink')]\n", "\n", "Supplies/Demands:\n", " source: supplies 3\n", " sink: demands 3\n", "\n", "Edges with costs:\n", " source -> worker_0: capacity=1, cost=0.00\n", " source -> worker_1: capacity=1, cost=0.00\n", " source -> worker_2: capacity=1, cost=0.00\n", " worker_0 -> task_0: capacity=1, cost=0.05\n", " worker_0 -> task_1: capacity=1, cost=23.05\n", " worker_0 -> task_2: capacity=1, cost=23.57\n", " worker_0 -> task_3: capacity=1, cost=200.00\n", " worker_1 -> task_0: capacity=1, cost=24.05\n", " ... (11 more edges)\n" ] } ], "source": [ "# Convert to flow network\n", "edges, supplies, node_names = assignment_to_flow_network(cost_matrix)\n", "\n", "print(\"Network Structure\")\n", "print(\"=\" * 60)\n", "print(f\"Number of nodes: {len(supplies)}\")\n", "print(f\"Number of edges: {len(edges)}\")\n", "print(f\"\\nNodes: {list(node_names)}\")\n", "\n", "print(f\"\\nSupplies/Demands:\")\n", "for i, (name, supply) in enumerate(zip(node_names, supplies)):\n", " if supply > 0:\n", " print(f\" {name}: supplies {supply:.0f}\")\n", " elif supply < 0:\n", " print(f\" {name}: demands {-supply:.0f}\")\n", "\n", "print(f\"\\nEdges with costs:\")\n", "for edge in edges[:8]: # Show first 8 edges\n", " from_name = node_names[edge.from_node]\n", " to_name = node_names[edge.to_node]\n", " print(f\" {from_name} -> {to_name}: capacity={edge.capacity:.0f}, cost={edge.cost:.2f}\")\n", "print(f\" ... ({len(edges) - 8} more edges)\")" ] }, { "cell_type": "code", "execution_count": 5, "id": "cell-7", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ -2, 0 ], "y": [ 2, 4 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ -2, 0 ], "y": [ 2, 2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ -2, 0 ], "y": [ 2, 0 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 4, 4.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 4, 3 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 4, 1.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 4, 0 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 2, 4.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 2, 3 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 2, 1.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 2, 0 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 0, 4.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 0, 3 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 0, 1.5 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 0, 6 ], "y": [ 0, 0 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 6, 8 ], "y": [ 4.5, 2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 6, 8 ], "y": [ 3, 2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 6, 8 ], "y": [ 1.5, 2 ] }, { "hoverinfo": "skip", "line": { "color": "gray", "width": 1 }, "mode": "lines", "opacity": 0.5, "showlegend": false, "type": "scatter", "x": [ 6, 8 ], "y": [ 0, 2 ] }, { "marker": { "color": "#00ff88", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "source", "showlegend": false, "text": [ "source" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ -2 ], "y": [ 2 ] }, { "marker": { "color": "#00d4ff", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "worker_0", "showlegend": false, "text": [ "W0" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 0 ], "y": [ 4 ] }, { "marker": { "color": "#00d4ff", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "worker_1", "showlegend": false, "text": [ "W1" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 0 ], "y": [ 2 ] }, { "marker": { "color": "#00d4ff", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "worker_2", "showlegend": false, "text": [ "W2" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 0 ], "y": [ 0 ] }, { "marker": { "color": "#ff4757", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "task_0", "showlegend": false, "text": [ "T0" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 6 ], "y": [ 4.5 ] }, { "marker": { "color": "#ff4757", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "task_1", "showlegend": false, "text": [ "T1" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 6 ], "y": [ 3 ] }, { "marker": { "color": "#ff4757", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "task_2", "showlegend": false, "text": [ "T2" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 6 ], "y": [ 1.5 ] }, { "marker": { "color": "#ff4757", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "task_3", "showlegend": false, "text": [ "T3" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 6 ], "y": [ 0 ] }, { "marker": { "color": "#ffb800", "line": { "color": "white", "width": 2 }, "size": 30 }, "mode": "markers+text", "name": "sink", "showlegend": false, "text": [ "sink" ], "textfont": { "color": "white", "size": 10 }, "textposition": "middle center", "type": "scatter", "x": [ 8 ], "y": [ 2 ] } ], "layout": { "annotations": [ { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "0.1", "x": 3, "y": 4.25 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "23.1", "x": 3, "y": 3.5 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "23.6", "x": 3, "y": 2.75 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "200.0", "x": 3, "y": 2 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "24.1", "x": 3, "y": 3.25 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "0.1", "x": 3, "y": 2.5 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "22.6", "x": 3, "y": 1.75 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "125.0", "x": 3, "y": 1 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "20.2", "x": 3, "y": 2.25 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "22.1", "x": 3, "y": 1.5 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "0.0", "x": 3, "y": 0.75 }, { "font": { "color": "#00d4ff", "size": 8 }, "showarrow": false, "text": "92.2", "x": 3, "y": 0 }, { "font": { "color": "#00ff88", "size": 12 }, "showarrow": false, "text": "Supply=3", "x": -2.5, "y": 5 }, { "font": { "color": "#ffb800", "size": 12 }, "showarrow": false, "text": "Demand=3", "x": 8, "y": 5 } ], "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": "Min-Cost Flow Network for Assignment" }, "xaxis": { "range": [ -3.5, 10 ], "showgrid": false, "showticklabels": false, "zeroline": false }, "yaxis": { "range": [ -1, 6 ], "showgrid": false, "showticklabels": false, "zeroline": false } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize the flow network\n", "fig = go.Figure()\n", "\n", "# Node positions\n", "pos = {}\n", "pos['source'] = (-2, 2)\n", "pos['sink'] = (8, 2)\n", "\n", "# Worker nodes on left\n", "for i in range(n_tracks):\n", " pos[f'worker_{i}'] = (0, 4 - i * 2)\n", "\n", "# Task nodes on right\n", "for j in range(n_meas):\n", " pos[f'task_{j}'] = (6, 4.5 - j * 1.5)\n", "\n", "# Draw edges first (so nodes appear on top)\n", "for edge in edges:\n", " from_name = node_names[edge.from_node]\n", " to_name = node_names[edge.to_node]\n", " x1, y1 = pos[from_name]\n", " x2, y2 = pos[to_name]\n", " \n", " fig.add_trace(\n", " go.Scatter(x=[x1, x2], y=[y1, y2], mode='lines',\n", " line=dict(color='gray', width=1), opacity=0.5,\n", " showlegend=False, hoverinfo='skip')\n", " )\n", " \n", " # Add cost label for worker->task edges\n", " if 'worker' in from_name and 'task' in to_name:\n", " mid_x, mid_y = (x1 + x2) / 2, (y1 + y2) / 2\n", " fig.add_annotation(x=mid_x, y=mid_y, text=f'{edge.cost:.1f}',\n", " showarrow=False, font=dict(size=8, color='#00d4ff'))\n", "\n", "# Draw nodes\n", "node_colors = {'source': '#00ff88', 'sink': '#ffb800'}\n", "for name in node_names:\n", " x, y = pos[name]\n", " color = node_colors.get(name, '#00d4ff' if 'worker' in name else '#ff4757')\n", " display_name = name.replace('worker_', 'W').replace('task_', 'T')\n", " \n", " fig.add_trace(\n", " go.Scatter(x=[x], y=[y], mode='markers+text',\n", " marker=dict(size=30, color=color, line=dict(color='white', width=2)),\n", " text=[display_name], textposition='middle center',\n", " textfont=dict(size=10, color='white'),\n", " name=name, showlegend=False)\n", " )\n", "\n", "# Add annotations\n", "fig.add_annotation(x=-2.5, y=5, text='Supply=3', showarrow=False, \n", " font=dict(color='#00ff88', size=12))\n", "fig.add_annotation(x=8, y=5, text='Demand=3', showarrow=False,\n", " font=dict(color='#ffb800', size=12))\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='Min-Cost Flow Network for Assignment',\n", " xaxis=dict(range=[-3.5, 10], showgrid=False, zeroline=False, showticklabels=False),\n", " yaxis=dict(range=[-1, 6], showgrid=False, zeroline=False, showticklabels=False),\n", " height=500,\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "id": "cell-8", "metadata": {}, "source": [ "## 3. Successive Shortest Paths Algorithm\n", "\n", "The successive shortest paths algorithm finds the minimum cost flow:\n", "\n", "### Algorithm\n", "```\n", "while supply nodes have remaining supply:\n", " 1. Find shortest path from supply to demand node\n", " 2. Compute maximum flow that can be pushed\n", " 3. Push flow and update residual capacities\n", " 4. Update node supplies/demands\n", "```\n", "\n", "### Complexity\n", "- **Bellman-Ford**: $O(k \\cdot V \\cdot E)$ where $k$ = number of paths\n", "- **Dijkstra with potentials**: $O(k \\cdot E \\log V)$" ] }, { "cell_type": "code", "execution_count": 6, "id": "cell-9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Bellman-Ford Based Solution\n", "==================================================\n", "Status: OPTIMAL\n", "Total Cost: -272.98\n", "Iterations: 3\n", "\n", "Optimal Assignment:\n", " Track 0 -> Measurement 0 (cost: 0.05)\n", " Track 0 -> Measurement 1 (cost: 23.05)\n", " Track 0 -> Measurement 2 (cost: 23.57)\n", " Track 1 -> Measurement 3 (cost: 125.00)\n", " Track 2 -> Measurement 2 (cost: 0.02)\n" ] } ], "source": [ "# Solve using successive shortest paths\n", "result_bf = min_cost_flow_successive_shortest_paths(edges, supplies)\n", "\n", "print(\"Bellman-Ford Based Solution\")\n", "print(\"=\" * 50)\n", "print(f\"Status: {result_bf.status.name}\")\n", "print(f\"Total Cost: {result_bf.cost:.2f}\")\n", "print(f\"Iterations: {result_bf.iterations}\")\n", "\n", "# Extract assignment\n", "assignment_bf, cost_bf = assignment_from_flow_solution(\n", " result_bf.flow, edges, cost_matrix.shape\n", ")\n", "\n", "print(f\"\\nOptimal Assignment:\")\n", "for row_idx, col_idx in assignment_bf:\n", " print(f\" Track {row_idx} -> Measurement {col_idx} (cost: {cost_matrix[row_idx, col_idx]:.2f})\")" ] }, { "cell_type": "code", "execution_count": 7, "id": "cell-10", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Dijkstra-Optimized Solution\n", "==================================================\n", "Status: OPTIMAL\n", "Total Cost: 0.12\n", "Iterations: 4\n", "\n", "Optimal Assignment:\n", " Track 0 -> Measurement 0 (cost: 0.05)\n", " Track 1 -> Measurement 1 (cost: 0.05)\n", " Track 2 -> Measurement 2 (cost: 0.02)\n" ] } ], "source": [ "# Solve using Dijkstra-optimized algorithm\n", "result_dijkstra = min_cost_flow_simplex(edges, supplies)\n", "\n", "print(\"Dijkstra-Optimized Solution\")\n", "print(\"=\" * 50)\n", "print(f\"Status: {result_dijkstra.status.name}\")\n", "print(f\"Total Cost: {result_dijkstra.cost:.2f}\")\n", "print(f\"Iterations: {result_dijkstra.iterations}\")\n", "\n", "# Extract assignment\n", "assignment_dij, cost_dij = assignment_from_flow_solution(\n", " result_dijkstra.flow, edges, cost_matrix.shape\n", ")\n", "\n", "print(f\"\\nOptimal Assignment:\")\n", "for row_idx, col_idx in assignment_dij:\n", " print(f\" Track {row_idx} -> Measurement {col_idx} (cost: {cost_matrix[row_idx, col_idx]:.2f})\")" ] }, { "cell_type": "code", "execution_count": 8, "id": "cell-11", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "marker": { "color": "#00d4ff", "size": 16, "symbol": "square" }, "mode": "markers+text", "name": "Tracks", "text": [ "T0", "T1", "T2" ], "textfont": { "color": "#00d4ff" }, "textposition": "top right", "type": "scatter", "x": { "bdata": "AAAAAAAAAAAAAAAAAAAUQAAAAAAAAARA", "dtype": "f8" }, "y": { "bdata": "AAAAAAAAAAAAAAAAAAAAAAAAAAAAABBA", "dtype": "f8" } }, { "marker": { "color": "#ff4757", "size": 16, "symbol": "circle" }, "mode": "markers+text", "name": "Measurements", "text": [ "M0", "M1", "M2", "M3" ], "textfont": { "color": "#ff4757" }, "textposition": "bottom right", "type": "scatter", "x": { "bdata": "mpmZmZmZuT8zMzMzMzMTQM3MzMzMzARAAAAAAAAAJEA=", "dtype": "f8" }, "y": { "bdata": "mpmZmZmZyT+amZmZmZm5v2ZmZmZmZhBAAAAAAAAAJEA=", "dtype": "f8" } }, { "line": { "color": "#00ff88", "width": 4 }, "mode": "lines", "name": "Assignment", "showlegend": true, "type": "scatter", "x": [ 0, 0.1 ], "y": [ 0, 0.2 ] }, { "line": { "color": "#00ff88", "width": 4 }, "mode": "lines", "showlegend": false, "type": "scatter", "x": [ 5, 4.8 ], "y": [ 0, -0.1 ] }, { "line": { "color": "#00ff88", "width": 4 }, "mode": "lines", "showlegend": false, "type": "scatter", "x": [ 2.5, 2.6 ], "y": [ 4, 4.1 ] }, { "marker": { "color": "rgba(0,0,0,0)", "line": { "color": "#a855f7", "width": 3 }, "size": 25 }, "mode": "markers", "name": "Unassigned", "type": "scatter", "x": [ 10 ], "y": [ 10 ] } ], "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": "Optimal Assignment (Total Cost: 0.12)" }, "xaxis": { "scaleanchor": "y", "scaleratio": 1, "title": { "text": "X" } }, "yaxis": { "title": { "text": "Y" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize the optimal assignment\n", "fig = go.Figure()\n", "\n", "# Plot tracks\n", "fig.add_trace(\n", " go.Scatter(x=tracks[:, 0], y=tracks[:, 1], mode='markers+text',\n", " marker=dict(size=16, color='#00d4ff', symbol='square'),\n", " text=[f'T{i}' for i in range(len(tracks))],\n", " textposition='top right', textfont=dict(color='#00d4ff'),\n", " name='Tracks')\n", ")\n", "\n", "# Plot measurements\n", "fig.add_trace(\n", " go.Scatter(x=measurements[:, 0], y=measurements[:, 1], mode='markers+text',\n", " marker=dict(size=16, color='#ff4757', symbol='circle'),\n", " text=[f'M{j}' for j in range(len(measurements))],\n", " textposition='bottom right', textfont=dict(color='#ff4757'),\n", " name='Measurements')\n", ")\n", "\n", "# Draw optimal assignments with thick green lines\n", "for row_idx, col_idx in assignment_dij:\n", " fig.add_trace(\n", " go.Scatter(x=[tracks[row_idx, 0], measurements[col_idx, 0]], \n", " y=[tracks[row_idx, 1], measurements[col_idx, 1]],\n", " mode='lines', line=dict(color='#00ff88', width=4),\n", " name='Assignment' if row_idx == assignment_dij[0, 0] else None,\n", " showlegend=bool(row_idx == assignment_dij[0, 0]))\n", " )\n", "\n", "# Highlight unassigned measurement\n", "assigned_meas = set(assignment_dij[:, 1])\n", "for j in range(n_meas):\n", " if j not in assigned_meas:\n", " fig.add_trace(\n", " go.Scatter(x=[measurements[j, 0]], y=[measurements[j, 1]],\n", " mode='markers',\n", " marker=dict(size=25, color='rgba(0,0,0,0)', \n", " line=dict(color='#a855f7', width=3)),\n", " name='Unassigned')\n", " )\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title=f'Optimal Assignment (Total Cost: {cost_dij:.2f})',\n", " xaxis_title='X',\n", " yaxis_title='Y',\n", " height=500,\n", " xaxis=dict(scaleanchor='y', scaleratio=1),\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "id": "cell-12", "metadata": {}, "source": [ "## 4. Performance Comparison\n", "\n", "Let's compare the performance of different algorithms:\n", "1. Network flow (Bellman-Ford)\n", "2. Network flow (Dijkstra-optimized)\n", "3. Hungarian algorithm" ] }, { "cell_type": "code", "execution_count": 9, "id": "cell-13", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Size 10x 10: BF= 1.40ms, Dijkstra= 0.95ms, Hungarian= 0.03ms\n", "Size 20x 20: BF= 8.95ms, Dijkstra= 5.37ms, Hungarian= 0.04ms\n", "Size 50x 50: BF= 119.24ms, Dijkstra= 68.82ms, Hungarian= 0.03ms\n", "Size 100x100: BF= nanms, Dijkstra= 529.98ms, Hungarian= 0.10ms\n", "Size 200x200: BF= nanms, Dijkstra=4025.68ms, Hungarian= 0.96ms\n" ] } ], "source": [ "# Performance benchmark\n", "sizes = [10, 20, 50, 100, 200]\n", "\n", "bf_times = []\n", "dijkstra_times = []\n", "hungarian_times = []\n", "\n", "n_trials = 5\n", "\n", "for size in sizes:\n", " # Generate random cost matrix\n", " cost = np.random.rand(size, size) * 100\n", " \n", " # Bellman-Ford based (limit to smaller sizes)\n", " if size <= 50:\n", " edges_tmp, supplies_tmp, _ = assignment_to_flow_network(cost)\n", " times = []\n", " for _ in range(n_trials):\n", " start = time.time()\n", " result = min_cost_flow_successive_shortest_paths(edges_tmp, supplies_tmp)\n", " times.append(time.time() - start)\n", " bf_times.append(np.mean(times))\n", " else:\n", " bf_times.append(np.nan)\n", " \n", " # Dijkstra-optimized\n", " edges_tmp, supplies_tmp, _ = assignment_to_flow_network(cost)\n", " times = []\n", " for _ in range(n_trials):\n", " start = time.time()\n", " result = min_cost_flow_simplex(edges_tmp, supplies_tmp)\n", " times.append(time.time() - start)\n", " dijkstra_times.append(np.mean(times))\n", " \n", " # Hungarian algorithm\n", " times = []\n", " for _ in range(n_trials):\n", " start = time.time()\n", " row_ind, col_ind, total_cost = hungarian(cost)\n", " times.append(time.time() - start)\n", " hungarian_times.append(np.mean(times))\n", " \n", " print(f\"Size {size:3d}x{size:3d}: BF={bf_times[-1]*1e3:7.2f}ms, \"\n", " f\"Dijkstra={dijkstra_times[-1]*1e3:7.2f}ms, \"\n", " f\"Hungarian={hungarian_times[-1]*1e3:7.2f}ms\")" ] }, { "cell_type": "code", "execution_count": 10, "id": "cell-14", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "line": { "color": "#ff4757", "width": 2 }, "marker": { "size": 8 }, "mode": "lines+markers", "name": "Bellman-Ford", "type": "scatter", "x": [ 10, 20, 50, 100, 200 ], "y": { "bdata": "AAAAAKhz9j8AAAAAX+QhQAAAABiHz11AAAAAAAAA+H8AAAAAAAD4fw==", "dtype": "f8" } }, { "line": { "color": "#00ff88", "width": 2 }, "marker": { "size": 8, "symbol": "square" }, "mode": "lines+markers", "name": "Dijkstra-optimized", "type": "scatter", "x": [ 10, 20, 50, 100, 200 ], "y": { "bdata": "AAAAANBN7j8AAAAA/3cVQAAAAFBgNFFAAAAA39CPgEABAEA4XnOvQA==", "dtype": "f8" } }, { "line": { "color": "#00d4ff", "width": 2 }, "marker": { "size": 8, "symbol": "triangle-up" }, "mode": "lines+markers", "name": "Hungarian", "type": "scatter", "x": [ 10, 20, 50, 100, 200 ], "y": { "bdata": "AAAAAIAAmz8AAAAAAJukPwAAAACAAJs/AAAAAGAJuT8AAAAApLDuPw==", "dtype": "f8" } } ], "layout": { "height": 450, "template": { "layout": { "font": { "color": "#e6edf3" }, "paper_bgcolor": "#0d1117", "plot_bgcolor": "#0d1117", "xaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" }, "yaxis": { "gridcolor": "#30363d", "zerolinecolor": "#30363d" } } }, "title": { "text": "Assignment Algorithm Performance Comparison" }, "xaxis": { "title": { "text": "Problem Size (n x n)" } }, "yaxis": { "title": { "text": "Time (ms)" }, "type": "log" } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize performance comparison\n", "fig = go.Figure()\n", "\n", "fig.add_trace(\n", " go.Scatter(x=sizes, y=np.array(bf_times)*1e3, mode='lines+markers',\n", " name='Bellman-Ford', line=dict(color='#ff4757', width=2),\n", " marker=dict(size=8))\n", ")\n", "fig.add_trace(\n", " go.Scatter(x=sizes, y=np.array(dijkstra_times)*1e3, mode='lines+markers',\n", " name='Dijkstra-optimized', line=dict(color='#00ff88', width=2),\n", " marker=dict(size=8, symbol='square'))\n", ")\n", "fig.add_trace(\n", " go.Scatter(x=sizes, y=np.array(hungarian_times)*1e3, mode='lines+markers',\n", " name='Hungarian', line=dict(color='#00d4ff', width=2),\n", " marker=dict(size=8, symbol='triangle-up'))\n", ")\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title='Assignment Algorithm Performance Comparison',\n", " xaxis_title='Problem Size (n x n)',\n", " yaxis_title='Time (ms)',\n", " yaxis_type='log',\n", " height=450,\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "id": "cell-15", "metadata": {}, "source": [ "## 5. Application: Multi-Target Tracking\n", "\n", "Let's demonstrate using network flow for a complete tracking scenario with:\n", "- Gate-based cost computation\n", "- Missed detection handling\n", "- New track initiation" ] }, { "cell_type": "code", "execution_count": 11, "id": "cell-16", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Generated 10 frames with 5 targets\n", " Frame 0: 5 detections, 2 clutter\n", " Frame 1: 5 detections, 4 clutter\n", " Frame 2: 5 detections, 2 clutter\n" ] } ], "source": [ "# Simulate tracking scenario\n", "n_timesteps = 10\n", "n_tracks = 5\n", "\n", "# True target trajectories\n", "np.random.seed(42)\n", "true_positions = []\n", "positions = np.random.randn(n_tracks, 2) * 5 + 10\n", "velocities = np.random.randn(n_tracks, 2) * 0.5\n", "\n", "for t in range(n_timesteps):\n", " true_positions.append(positions.copy())\n", " positions += velocities + np.random.randn(n_tracks, 2) * 0.1\n", "\n", "# Generate measurements with noise and clutter\n", "detection_prob = 0.9\n", "clutter_rate = 2 # average clutter per frame\n", "measurement_noise = 0.3\n", "\n", "all_measurements = []\n", "all_truth_associations = []\n", "\n", "for t in range(n_timesteps):\n", " frame_meas = []\n", " frame_assoc = []\n", " \n", " # Target detections\n", " for i in range(n_tracks):\n", " if np.random.rand() < detection_prob:\n", " meas = true_positions[t][i] + np.random.randn(2) * measurement_noise\n", " frame_meas.append(meas)\n", " frame_assoc.append(i)\n", " \n", " # Clutter\n", " n_clutter = np.random.poisson(clutter_rate)\n", " for _ in range(n_clutter):\n", " clutter = np.random.rand(2) * 30 # Uniform in surveillance region\n", " frame_meas.append(clutter)\n", " frame_assoc.append(-1) # -1 indicates clutter\n", " \n", " all_measurements.append(np.array(frame_meas))\n", " all_truth_associations.append(np.array(frame_assoc))\n", "\n", "print(f\"Generated {n_timesteps} frames with {n_tracks} targets\")\n", "for t in range(3):\n", " n_det = np.sum(all_truth_associations[t] >= 0)\n", " n_clut = np.sum(all_truth_associations[t] < 0)\n", " print(f\" Frame {t}: {n_det} detections, {n_clut} clutter\")" ] }, { "cell_type": "code", "execution_count": 12, "id": "cell-17", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "Tracking Results:\n", " Total assignments: 32\n", " Correct associations: 32\n", " Accuracy: 100.0%\n" ] } ], "source": [ "def compute_gated_cost_matrix(track_positions, measurements, gate_threshold=10.0):\n", " \"\"\"\n", " Compute cost matrix with gating.\n", " \n", " Parameters\n", " ----------\n", " track_positions : ndarray\n", " Track predicted positions [n_tracks, 2].\n", " measurements : ndarray\n", " Measurement positions [n_meas, 2].\n", " gate_threshold : float\n", " Maximum squared distance for valid association.\n", " \n", " Returns\n", " -------\n", " cost_matrix : ndarray\n", " Cost matrix with inf for gated-out associations.\n", " \"\"\"\n", " n_tracks = len(track_positions)\n", " n_meas = len(measurements)\n", " \n", " cost_matrix = np.full((n_tracks, n_meas), np.inf)\n", " \n", " for i in range(n_tracks):\n", " for j in range(n_meas):\n", " dist_sq = np.sum((track_positions[i] - measurements[j])**2)\n", " if dist_sq < gate_threshold:\n", " cost_matrix[i, j] = dist_sq\n", " \n", " return cost_matrix\n", "\n", "\n", "# Run tracking with network flow assignment\n", "# Initialize tracks at frame 0\n", "track_estimates = true_positions[0].copy()\n", "\n", "assignment_results = []\n", "total_correct = 0\n", "total_assignments = 0\n", "\n", "for t in range(1, n_timesteps):\n", " meas = all_measurements[t]\n", " truth_assoc = all_truth_associations[t]\n", " \n", " if len(meas) == 0:\n", " continue\n", " \n", " # Compute gated cost matrix\n", " cost = compute_gated_cost_matrix(track_estimates, meas, gate_threshold=4.0)\n", " \n", " # Replace inf with large value for network flow\n", " max_cost = 1e6\n", " cost_finite = np.where(np.isinf(cost), max_cost, cost)\n", " \n", " # Solve assignment\n", " assignment, total_cost = min_cost_assignment_via_flow(cost_finite)\n", " \n", " # Evaluate accuracy\n", " for row_idx, col_idx in assignment:\n", " if cost[row_idx, col_idx] < max_cost: # Valid assignment\n", " total_assignments += 1\n", " if truth_assoc[col_idx] == row_idx: # Correct assignment\n", " total_correct += 1\n", " \n", " # Update track estimates with assigned measurements\n", " for row_idx, col_idx in assignment:\n", " if cost[row_idx, col_idx] < max_cost:\n", " track_estimates[row_idx] = meas[col_idx]\n", " \n", " assignment_results.append((t, assignment, cost))\n", "\n", "accuracy = total_correct / total_assignments if total_assignments > 0 else 0\n", "print(f\"\\nTracking Results:\")\n", "print(f\" Total assignments: {total_assignments}\")\n", "print(f\" Correct associations: {total_correct}\")\n", "print(f\" Accuracy: {accuracy*100:.1f}%\")" ] }, { "cell_type": "code", "execution_count": 13, "id": "cell-18", "metadata": {}, "outputs": [ { "data": { "application/vnd.plotly.v1+json": { "config": { "plotlyServerURL": "https://plot.ly" }, "data": [ { "line": { "color": "#00d4ff", "width": 2 }, "mode": "lines", "name": "Target 0", "opacity": 0.7, "showlegend": true, "type": "scatter", "x": { "bdata": "lG9alpb3KEAdaNGY/ssoQIAgul2NNihA2ympDbrlJ0CBFkhYr38nQMHxnCuE8CZADj5Pg2KMJkAOZwmwgAomQHZPgo/WmCVAW4eleLzZJEA=", "dtype": "f8" }, "y": { "bdata": "maeKGwueIkCc71C/QRsiQIqw4dzdAiJA3fy99GmUIUB4f1mKeAkhQCaLhgG9iCBANMowS0JgIEDFHe/yofYfQG21FEReax9A4zHCK9dRHkA=", "dtype": "f8" } }, { "marker": { "color": "#00d4ff", "size": 10, "symbol": "circle" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 12.483570765056164 ], "y": [ 9.308678494144077 ] }, { "marker": { "color": "#00d4ff", "size": 10, "symbol": "square" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 10.425266046720642 ], "y": [ 7.57992237446567 ] }, { "line": { "color": "#ff4757", "width": 2 }, "mode": "lines", "name": "Target 1", "opacity": 0.7, "showlegend": true, "type": "scatter", "x": { "bdata": "gF0LKRV6KkDkvmSBe7sqQG04hNW7+CpAvFKRP8EwK0Dt6YnvCUwrQObMqjhWUStAI8e44XGNK0Dt14ksDhcsQAZvjXYNMSxANpvArHJdLEA=", "dtype": "f8" }, "y": { "bdata": "LoVgbHqdMUAOmJrTGoQwQDKaVEpB6C5AfakM7gnvLEA2CSmPjiQrQPo12OeC/ShAT6XTRNJjJ0CTKZ12fF8lQPWE9f7oZCNAsOc3pwhSIUA=", "dtype": "f8" } }, { "marker": { "color": "#ff4757", "size": 10, "symbol": "circle" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 13.238442690503462 ], "y": [ 17.61514928204013 ] }, { "marker": { "color": "#ff4757", "size": 10, "symbol": "square" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 14.182515524398337 ], "y": [ 8.66022226865229 ] }, { "line": { "color": "#00ff88", "width": 2 }, "mode": "lines", "name": "Target 2", "opacity": 0.7, "showlegend": true, "type": "scatter", "x": { "bdata": "AyeNPpGoIUAwG11kO6YfQNsItntNhxxAvyd6fL58GECP0QgXKXMVQFKxaIk0UxJA4+wAH5KnC0ADcVLprBsEQKm4FpUcyvk/W2qIqNV25z8=", "dtype": "f8" }, "y": { "bdata": "3y7/AJyoIUDKLh3QVx4hQPocQuXjTyBATdckWy02H0B6xZAnpnUeQEH9qQWj4B1A/aBWjegUHUBVdScko8EbQHWb7dLhCxpA3Oepn10VGUA=", "dtype": "f8" } }, { "marker": { "color": "#00ff88", "size": 10, "symbol": "circle" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 8.82923312638332 ], "y": [ 8.829315215254097 ] }, { "marker": { "color": "#00ff88", "size": 10, "symbol": "square" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 0.7332561771066354 ], "y": [ 6.270864958520146 ] }, { "line": { "color": "#ffb800", "width": 2 }, "mode": "lines", "opacity": 0.7, "showlegend": false, "type": "scatter", "x": { "bdata": "QiSUdGTlMUCUvo3aSEYxQLegRzb9yTBAst5s6408MED3PKQl20ovQNiYSmXiQy5AFqZOcA5FLUDWFaTlo3AsQEsD702EfCtA1MccBc7ZKkA=", "dtype": "f8" }, "y": { "bdata": "fEMrBqKsK0BGAujiUBAsQCnCfZxt/CtA4wF0CQCDLEDa/0OkncMsQI27R6lxRy1AGsh5BpWILUA3CYeL3OktQB2uCsOsRy5ARWBagA+hLkA=", "dtype": "f8" } }, { "marker": { "color": "#ffb800", "size": 10, "symbol": "circle" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 17.896064077536955 ], "y": [ 13.837173645764544 ] }, { "marker": { "color": "#ffb800", "size": 10, "symbol": "square" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 13.42539993263555 ], "y": [ 15.314571391136392 ] }, { "line": { "color": "#a855f7", "width": 2 }, "mode": "lines", "opacity": 0.7, "showlegend": false, "type": "scatter", "x": { "bdata": "dP5piEqcHkAOV02e4I0cQFVxg3z2NBpA5Se5sz2HGEC5KeIKQdgWQIC6EZVgLBVAEcAegd1kE0DiGXqgtV0RQHsQakimGg9AVN4MR5StC0A=", "dtype": "f8" }, "y": { "bdata": "Ny5xJvRsKUCFw2AgePQnQJN90bD/lCZA33h2by7RJEDikXhdlJkjQGG1her/DiJALhqrt68/IECjbEP21OAdQB6NJu619RpAg6CO5/waGEA=", "dtype": "f8" } }, { "marker": { "color": "#a855f7", "size": 10, "symbol": "circle" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 7.652628070325239 ], "y": [ 12.712800217929823 ] }, { "marker": { "color": "#a855f7", "size": 10, "symbol": "square" }, "mode": "markers", "showlegend": false, "type": "scatter", "x": [ 3.4597554732134004 ], "y": [ 6.026355379181157 ] }, { "marker": { "color": "white", "opacity": 0.4, "size": 4 }, "mode": "markers", "name": "Detections", "type": "scatter", "x": [ 12.243022412051257, 13.414499818643543, 8.681203381722321, 17.92595948706325, 7.65537137404728, 12.29140328781163, 13.43441462713651, 7.814988650325617, 17.35251399790204, 7.528371207852099, 12.421351505609177, 13.193403558996298, 7.363124720607326, 17.035638006959122, 6.140760203907415, 11.526763519351762, 13.273956618190352, 5.108423317907386, 15.368389223444666, 5.763139895253651, 11.786985432507429, 13.983776314696106, 4.8527916872977785, 15.287100942774677, 5.692601580634079, 11.132609534256495, 14.244373515955408, 3.237711683130179, 15.351586570757206, 4.240958446138116, 10.66042413668661, 14.140360123603848, 2.1352482097989713, 4.9781600231018786, 10.727294378969916, 13.123425638247275, 1.0133551930624578, 13.611183556672612, 3.9055651425937827, 14.658320569241942, 0.9393107309364266, 13.50969749295606, 3.7252526133694 ], "y": [ 9.72388320982388, 18.272285969783123, 9.106263997756683, 13.686130949529684, 12.60313842888006, 9.220072526870485, 16.908177167374614, 8.497503694475945, 14.266413975429941, 11.717335145467983, 9.40313062743032, 15.689748506988131, 8.53655243670818, 14.562061662602591, 11.059479040354137, 8.779511983481486, 14.611614358550524, 7.160437474412425, 14.228172490147765, 9.915555274961436, 8.28247525887555, 12.81127997140626, 7.288200568309422, 15.795358488721707, 9.325757018065861, 8.514690959983339, 11.733528899069615, 7.335355942746409, 15.3197861002725, 8.18032378721772, 7.89050179050689, 10.20282826273967, 7.21445748100931, 7.779301963595925, 8.416453487669026, 9.389773825503065, 6.121545784981147, 15.179212116741398, 7.444350899960517, 8.288877619004236, 6.29215668321207, 15.127761535190213, 5.886996454587667 ] }, { "marker": { "color": "gray", "opacity": 0.5, "size": 4, "symbol": "x" }, "mode": "markers", "name": "Clutter", "type": "scatter", "x": [ 20.728132143073978, 28.101899662102035, 4.848861422838413, 18.1928717897877, 3.044146285980963, 0.1518475153865606, 26.761396655313398, 23.844339106249453, 27.849556877631763, 18.45021680097509, 2.81945819522607, 1.0782682139022626, 16.2793390412273, 2.353691440267979, 28.87945244033775, 10.679180359537847, 2.1170624220128955, 0.7953393162486544 ], "y": [ 11.602060389016122, 4.1256283243797975, 26.956625655812378, 0.27591154849888944, 19.905053073241675, 4.82424154252496, 18.934158779917887, 15.079112793155764, 12.84552444951943, 29.701615503127897, 17.34840422988522, 13.967940543973805, 8.596237563848533, 0.7605223024637253, 25.079403615366175, 22.735383313931074, 19.27257834618947, 17.5732674382039 ] } ], "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": "Multi-Target Tracking with Network Flow Assignment (Accuracy: 100.0%)" }, "xaxis": { "title": { "text": "X" } }, "yaxis": { "title": { "text": "Y" } } } } }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Visualize tracking results\n", "fig = go.Figure()\n", "\n", "colors = ['#00d4ff', '#ff4757', '#00ff88', '#ffb800', '#a855f7']\n", "\n", "# Plot true trajectories\n", "for i in range(n_tracks):\n", " traj = np.array([true_positions[t][i] for t in range(n_timesteps)])\n", " fig.add_trace(\n", " go.Scatter(x=traj[:, 0], y=traj[:, 1], mode='lines',\n", " line=dict(color=colors[i % len(colors)], width=2),\n", " name=f'Target {i}' if i < 3 else None,\n", " showlegend=(i < 3), opacity=0.7)\n", " )\n", " # Start and end markers\n", " fig.add_trace(\n", " go.Scatter(x=[traj[0, 0]], y=[traj[0, 1]], mode='markers',\n", " marker=dict(size=10, color=colors[i % len(colors)], symbol='circle'),\n", " showlegend=False)\n", " )\n", " fig.add_trace(\n", " go.Scatter(x=[traj[-1, 0]], y=[traj[-1, 1]], mode='markers',\n", " marker=dict(size=10, color=colors[i % len(colors)], symbol='square'),\n", " showlegend=False)\n", " )\n", "\n", "# Plot measurements (detections and clutter)\n", "all_det_x, all_det_y = [], []\n", "all_clut_x, all_clut_y = [], []\n", "\n", "for t in range(n_timesteps):\n", " meas = all_measurements[t]\n", " truth = all_truth_associations[t]\n", " \n", " for j in range(len(meas)):\n", " if truth[j] >= 0:\n", " all_det_x.append(meas[j, 0])\n", " all_det_y.append(meas[j, 1])\n", " else:\n", " all_clut_x.append(meas[j, 0])\n", " all_clut_y.append(meas[j, 1])\n", "\n", "fig.add_trace(\n", " go.Scatter(x=all_det_x, y=all_det_y, mode='markers',\n", " marker=dict(size=4, color='white', opacity=0.4),\n", " name='Detections')\n", ")\n", "fig.add_trace(\n", " go.Scatter(x=all_clut_x, y=all_clut_y, mode='markers',\n", " marker=dict(size=4, color='gray', symbol='x', opacity=0.5),\n", " name='Clutter')\n", ")\n", "\n", "fig.update_layout(\n", " template=dark_template,\n", " title=f'Multi-Target Tracking with Network Flow Assignment (Accuracy: {accuracy*100:.1f}%)',\n", " xaxis_title='X',\n", " yaxis_title='Y',\n", " height=550,\n", ")\n", "fig.show()" ] }, { "cell_type": "markdown", "id": "cell-19", "metadata": {}, "source": [ "## Summary & Learning Path\n", "\n", "### Key Concepts\n", "\n", "Key takeaways:\n", "\n", "1. **Network flow formulation** converts assignment to min-cost flow\n", "2. **Successive shortest paths** finds optimal solution iteratively\n", "3. **Dijkstra optimization** provides O(k*E log V) vs O(k*V*E) \n", "4. **Hungarian algorithm** is often faster for dense problems\n", "5. **Network flow** scales better for sparse/gated problems\n", "\n", "### When to Use Each Algorithm\n", "\n", "| Scenario | Recommended Algorithm | Complexity | Trade-off |\n", "|----------|----------------------|-----------|-----------|\n", "| Small dense (n < 100) | Hungarian | O(n³) | Simple, proven optimal |\n", "| Large dense (n > 500) | Dijkstra-flow | O(k·E log V) | Better scaling |\n", "| Sparse/gated | Flow network | O(k·V·E) | Flexible constraints |\n", "| Rectangular | Network flow | O(min(V,E)³) | Handles non-square |\n", "| Dynamic/streaming | Auction | O(n·m·ε⁻¹) | Parallelizable |\n", "\n", "### 4-Week Learning Curriculum\n", "\n", "**Week 1: Foundations**\n", "- Day 1-2: Bipartite matching and assignment problem formulation\n", "- Day 3-4: Min-cost flow network structure (source, sink, workers, tasks)\n", "- Day 5: Edge costs, capacities, and supply/demand balance\n", "\n", "**Week 2: Classic Algorithms**\n", "- Day 6-7: Hungarian algorithm derivation and complexity analysis\n", "- Day 8-9: Auction algorithm iterative price updates\n", "- Day 10: Comparative benchmarking for small problems\n", "\n", "**Week 3: Network Flow Methods**\n", "- Day 11-12: Successive shortest paths with Bellman-Ford\n", "- Day 13-14: Dijkstra-optimized with potentials (O(k·E log V))\n", "- Day 15: Simplex method visualization and convergence\n", "\n", "**Week 4: Advanced Applications**\n", "- Day 16-17: Sparse and gated network formulations\n", "- Day 18-19: 3D assignment reduction to flow networks\n", "- Day 20: Dynamic networks and streaming applications\n", "\n", "### Advanced Topics\n", "\n", "**1. Auction Algorithm for Assignment**\n", "- Distributed algorithm suitable for parallel computation\n", "- Each \"bidder\" competes for \"objects\" through price mechanism\n", "- Convergence: O(n·m·ε⁻¹ log(nC)) iterations\n", "- Often faster than Hungarian for sparse problems\n", "\n", "**2. Successive Shortest Paths (SSP)**\n", "- Iteratively finds augmenting paths with min-cost\n", "- Uses Bellman-Ford (handles negative costs): O(k·V·E)\n", "- Or uses Dijkstra with potentials: O(k·E log V)\n", "- Better for dynamic networks (tracks appear/disappear)\n", "\n", "**3. Network Simplex**\n", "- Primal simplex method specialized for networks\n", "- Highly efficient in practice despite O(V²·E) worst-case\n", "- Used in production tracking systems\n", "- Handles rectangular, sparse, gated problems naturally\n", "\n", "**4. Min-Cost Max-Flow Relaxations**\n", "- 3D/4D assignment reduced to min-cost max-flow\n", "- Achieved by decomposing high-order tensor into constraints\n", "- Often better than Lagrangian relaxation for small instances\n", "\n", "**5. Dynamic/Streaming Networks**\n", "- Networks where tracks/measurements appear and disappear\n", "- Incremental Hungarian using basis updates\n", "- Real-time tracking: reuse previous solution, update diffs only\n", "- Complexity: O(n²) update instead of O(n³) from scratch\n", "\n", "### 6 Progressive Exercises\n", "\n", "**⭐ Beginner: Cost Matrix to Flow Network**\n", "```python\n", "# Implement assignment_to_flow_network from scratch\n", "# 1. Create nodes: source, workers, tasks, sink\n", "# 2. Add edges with costs and capacities\n", "# 3. Set supplies/demands correctly\n", "```\n", "\n", "**⭐⭐ Intermediate: Implement Successive Shortest Paths**\n", "```python\n", "# Implement min_cost_flow_successive_shortest_paths using Bellman-Ford\n", "# 1. Initialize residual graph\n", "# 2. While supply remains: find shortest path\n", "# 3. Push flow and update supplies\n", "# Compare timing with Hungarian algorithm\n", "```\n", "\n", "**⭐⭐ Intermediate: Gating Integration**\n", "```python\n", "# Extend network flow to include gating constraints\n", "# 1. Remove edges where cost > gate_threshold\n", "# 2. Compare results: full network vs gated vs Hungarian + gating\n", "# 3. Measure performance and optimality gap\n", "```\n", "\n", "**⭐⭐⭐ Advanced: 3D Assignment via Network Flow**\n", "```python\n", "# Reduce 3D assignment (measurements × tracks × hypotheses) to min-cost flow\n", "# 1. Create additional constraint nodes for 3rd dimension\n", "# 2. Set supply/demand to enforce exactly-once selection\n", "# 3. Compare with Lagrangian relaxation optimization\n", "```\n", "\n", "**⭐⭐⭐ Advanced: Dynamic Networks**\n", "```python\n", "# Implement incremental assignment updates\n", "# 1. Reuse previous solution basis\n", "# 2. Add/remove nodes (new tracks or measurements)\n", "# 3. Measure speedup vs cold start (target: 10-100x faster)\n", "```\n", "\n", "**⭐⭐⭐⭐ Expert: Streaming Auction Algorithm**\n", "```python\n", "# Implement parallel auction algorithm for large-scale tracking\n", "# 1. Multiple workers bid simultaneously for objects\n", "# 2. Price update rules ensure convergence\n", "# 3. Benchmark vs network simplex for 1000+ tracks\n", "# 4. Analyze scaling and parallelism efficiency\n", "```\n", "\n", "### Complete References\n", "\n", "**Core References:**\n", "1. **Ahuja, R.K., Magnanti, T.L., & Orlin, J.B.** (1993). *Network Flows: Theory, Algorithms, and Applications*. Prentice Hall.\n", " - Comprehensive treatment of min-cost flow algorithms\n", " - Successive shortest paths and simplex methods\n", " - Foundation for understanding flow networks in tracking\n", "\n", "2. **Blackman, S., & Popoli, R.** (1999). *Design and Analysis of Modern Tracking Systems*. Artech House.\n", " - Applies network flow concepts to target tracking\n", " - Best practices for gating and assignment\n", " - Performance analysis of different algorithms\n", "\n", "3. **Bar-Shalom, Y., & Li, X.R.** (1995). *Multitarget-Multisensor Tracking: Principles and Techniques*. Artech House.\n", " - Foundational MHT framework\n", " - Assignment problem formulation in tracking context\n", " - Connection between network flow and data association\n", "\n", "**Advanced References:**\n", "4. **Bertsekas, D.P.** (1988). \"The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem\". *Annals of Operations Research*, 14(1), 105-123.\n", " - Original auction algorithm paper\n", " - Distributed and parallel variants\n", " - Complexity analysis and convergence proofs\n", "\n", "5. **Kuhn, H.W.** (1955). \"The Hungarian Method for the Assignment Problem\". *Naval Research Logistics Quarterly*, 2(1-2), 83-97.\n", " - Classic Hungarian algorithm (provides baseline for comparison)\n", " - Historical context for modern approaches\n", " - Fundamental pruning techniques still used today\n", "\n", "6. **Castañón, D.A.** (1997). \"Efficient Algorithms for Nonlinear Smoothing\". *IEEE Transactions on Signal Processing*, 45(10), 2425-2438.\n", " - Advanced filtering techniques compatible with flow networks\n", " - Extension to nonlinear systems\n", " - Connection between smoothing and assignment\n", "\n", "### PyTCL API Reference\n", "\n", "Key functions and their integration:\n", "\n", "```python\n", "# Main network flow functions\n", "from pytcl.assignment_algorithms.network_flow import (\n", " FlowEdge, FlowStatus,\n", " assignment_to_flow_network, # Convert assignment → flow network\n", " min_cost_flow_successive_shortest_paths, # SSP with Bellman-Ford\n", " min_cost_flow_simplex, # Dijkstra-optimized\n", " assignment_from_flow_solution, # Extract assignment from flow\n", " min_cost_assignment_via_flow, # End-to-end flow assignment\n", ")\n", "\n", "# Supporting algorithms for comparison\n", "from pytcl.assignment_algorithms import (\n", " hungarian, # Baseline algorithm\n", " assign2d, # Generalized 2D assignment\n", " auction, # Auction algorithm\n", " gnn_association, # GNN for association\n", " jpda, # JPDA with flow networks\n", ")\n", "```" ] } ], "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": 5 }