Papers for

urban infrastructure teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Improved efficient network design on planar graphs with small length slack

A Little Length Slack Goes a Long Way in Planar Length-Constrained Network Design

Abstract: Problems in length-constrained network design ask for min-cost subgraphs connecting $k$ input vertex pairs by paths of length at most $h$. Algorithms that instead connect these pairs by paths of length at most $βh$ are said to have length slack $β$. Recent work has shown that poly-time polylogarithmic approximations with polylogarithmic length slack are possible for a broad class of both directed and multicommodity length-constrained network design problems on planar graphs. We give the first poly-time polylogarithmic approximations with $O(1)$ length slack for these problems on planar graphs. In particular, for the length-constrained setting, we give LP-competitive algorithms for planar graphs with length slack $1+ε$ and approximation ratios of $O(\log^2 k/ε)$ for directed Steiner tree and $O(\log^5 k/ε^2)$ for (undirected) Steiner forest. Similarly, for length-constrained directed Steiner forest, we give an $O(\log^6 k/ε)$ approximation on planar graphs with length slack $6+ε$. Our approach is based on a novel charging argument that charges the cost of our solution to the length of the LP and the length of our solution to the cost of the LP. We complement these algorithms with hardness results that separate planar and general graphs for both forest problems: under standard complexity assumptions, we rule out polylogarithmic approximations on general graphs with length slack below $3$.

Thu 12 NovData Structures and Algorithms
The gist
Designing networks that connect points with short paths can be very hard. The authors show that on flat (planar) layouts, allowing just a tiny bit of extra path length makes it much easier to find good network designs quickly. They created algorithms that nearly match the best possible solutions while only slightly increasing path lengths. They also prove it’s much harder to do this well on non-flat networks when the allowed path length increase is very small.
Open → 2611.17201v1

Traffic signal system restores reliable data after sensor attacks and failures

MDRC: A Deployable State-Recovery Defense for Traffic Signal Control under Sensor Corruption

Abstract: Traffic Signal Control (TSC) is a safety-critical cyber-physical system that relies on real-time sensing. Corrupted observations caused by adversarial perturbations or sensor failures can propagate from the sensing layer into the controller and degrade traffic efficiency. Existing robust Reinforcement Learning (RL)-based TSC methods often suffer from limited cross-city generalization, high inference latency, and weak recovery under partial observability. We present MDRC (Meta-Diffusion-based framework for Resilient traffic signal Control against adversarial attacks and sensor failures), a post-detection state-recovery defense inserted between sensing and control. MDRC reconstructs trustworthy traffic states before they are consumed by the controller. It combines Denoising Diffusion Implicit Models (DDIM) for efficient state recovery with Reptile meta-learning for a transferable initialization across cities. We provide an optimization-based view of the DDIM recovery dynamics and establish a recovery-error bound that separates score approximation, numerical discretization, and initialization mismatch. Across seven real-world-derived CityFlow benchmarks, MDRC reduces Average Travel Time by 6.77% under stochastic and policy-aware attacks and by 12.75% under structured sensor loss, while improving state-recovery fidelity. We further evaluate 3,600 seconds of real roadside measurements with 50% of detector channels disabled and integrate MDRC into a hardware-in-the-loop traffic-signal stack. Over a 9.16-hour run with 32,389 sensing/control cycles, the system achieves 99.79% decision availability, produces no out-of-plan recommendations, and requires approximately 38 ms of component-wise processing per one-second control interval.

Wed 23 SeptCryptography and Security
The gist
Traffic lights rely on sensors to control traffic flow safely and efficiently, but corrupt or faulty sensor data can cause delays or unsafe signals. The authors created a recovery method called MDRC that fixes bad data before it reaches the traffic controller, using a smart combination of AI techniques. This method works across different cities and conditions, improving traffic times even when some sensors fail or are attacked. They tested MDRC in simulations and real-world traffic systems, showing it runs quickly and keeps traffic signals reliable for long periods.
Open → 2609.27528v1

Benchmark reveals challenges in describing long term image changes

Spot-the-shift: Evaluating Grounded Image Difference Captioning of Long-term Changes

Abstract: Long-term change understanding from images of the same place revisited over time is a challenging task with applications in map maintenance and urban infrastructure monitoring. Prior work addresses it either through pixel-level prediction or difference captioning, neither of which is sufficient to reliably measure how well models detect and describe such changes. We introduce SPOT-THE-SHIFT, a human-verified benchmark for grounded image difference captioning of long-term changes in real-world driving scenes. Our benchmark provides natural language captions and spatial masks for structural changes across each image pair. We further propose an evaluation protocol that reliably assesses models' captioning ability, validated through human studies. Benchmarking state-of-the-art MLLMs, we find that models struggle with the fine-grained multi-image spatial capability required for this task. Finally, we develop a synthetic data generation pipeline that improves an off-the-shelf MLLM without sacrificing general capabilities.

Wed 9 SeptComputer Vision and Pattern Recognition
The gist
Understanding changes in images taken from the same place over time is tricky but important for things like keeping maps updated. The authors created SPOT-THE-SHIFT, a test dataset with image pairs, descriptions in everyday language, and marked areas that show changes. They also made a way to check how well computer models can notice and explain these changes. Testing current models showed they find it hard to describe detailed changes over multiple images. The authors improved a model by generating synthetic training data that helps it learn better without losing other skills.
Open → 2609.10356v1