PaperlayerView exact revision on arXiv

Source-linked AI summary

The path inference filter: model-based low-latency map matching of probe vehicle data

Timothy Hunter, Pieter Abbeel, Alexandre Bayen

arXiv:1109.1966v2cs.AI

TL;DR

Sparse GPS observations make reconstructing urban vehicle trajectories difficult because measurements are noisy and the path between widely spaced points is ambiguous. The paper introduces the path inference filter, a probabilistic framework that jointly maps observations to road states and links them into trajectories in real time. On San Francisco taxi data, it reports robust performance across sampling rates, improved state-of-the-art accuracy in its most accurate settings, and industrial-scale throughput.

  • Problem

    Noisy, low-frequency GPS data leaves vehicle road positions and connecting paths ambiguous, complicating accurate urban trajectory reconstruction.

  • Method

    The path inference filter projects GPS points to candidate road states, builds candidate trajectories, and scores them with observation and driver models in a Conditional Random Field.

  • Results

    The filter is competitive from 1 second to 2 minutes, greatly outperforms intuitive deterministic algorithms, and extends the state of the art in its most accurate settings.

  • Takeaways & Limitations

    The filter supports tunable accuracy, timeliness, and computing trade-offs and has been deployed at industrial scale in Mobile Millennium.

Abstract

from arXiv · show

We consider the problem of reconstructing vehicle trajectories from sparse sequences of GPS points, for which the sampling interval is between 10 seconds and 2 minutes. We introduce a new class of algorithms, called altogether path inference filter (PIF), that maps GPS data in real time, for a variety of trade-offs and scenarios, and with a high throughput. Numerous prior approaches in map-matching can be shown to be special cases of the path inference filter presented in this article. We present an efficient procedure for automatically training the filter on new data, with or without ground truth observations. The framework is evaluated on a large San Francisco taxi dataset and is shown to improve upon the current state of the art. This filter also provides insights about driving patterns of drivers. The path inference filter has been deployed at an industrial scale inside the Mobile Millennium traffic information system, and is used to map fleets of data in San Francisco, Sacramento, Stockholm and Porto.

I. INTRODUCTION

Sparse, noisy urban GPS data makes it difficult to identify both vehicle locations on the road network and the paths connecting successive observations. The path inference filter addresses this by jointly modeling candidate states, paths, and probabilities for real-time, computationally efficient trajectory reconstruction.

  • Motivation: 1 to 2 minutes is the typical sampling interval for large-scale commercial fleet data, during which a vehicle can traverse several city blocks.Lower temporal resolution reduces power and communication costs but loses precise trajectory information.
  • Motivation: Greedy closest-link matching and shortest-path reconstruction can select incorrect turns, links, or states because of GPS noise and network ambiguity.The paper motivates a principled approach that considers map matching and trajectory reconstruction jointly.
  • Motivation: Low-frequency urban GPS observations leave both the vehicle’s exact road position and the path between observations uncertain.These uncertainties are correlated, and lower sampling rates allow many possible paths between successive points.
  • Path inference filter: The path inference filter is a probabilistic framework for recovering road positions and trajectories in real time with computationally efficient trade-offs across scenarios.Its performance is intended to degrade gracefully as sampling frequency decreases, while supporting limited-computing real-time and higher-accuracy offline settings.
  • Path inference filter: The framework projects GPS measurements to candidate road states, computes admissible paths between candidates, and assigns probabilities using vehicle dynamics and learned driver preferences.It is grounded in a Bayesian noisy-channel perspective and can be expressed within Conditional Random Fields.
  • Contributions: The filter unifies path, point, and network-topology information and treats many geometric, topological, and probabilistic map-matching methods as special cases.The paper contrasts this unified trajectory representation with Dynamic Bayesian approaches that can suffer from selection bias at lower frequencies.

B. From discrete vehicle states to trajectories

The filter represents each GPS observation with candidate states and connects successive states through acceptable network paths to form trajectories. It also addresses observation noise, computational trade-offs, and map inaccuracies when enforcing physical consistency.

  • State and path representation: Each GPS point is mapped to multiple candidate states, and trajectories are formed by successive states linked by candidate paths.Candidate paths connect projection states across consecutive observations, while a trajectory is the succession of states and paths.
  • State and path representation: A path discovery algorithm computes acceptable paths between candidate projections, with speed limits making the number of feasible paths finite.Standard graph search can enumerate paths within the maximum distance reachable at speed vmax during the observation interval.
  • Path computation: A* search uses expected link travel time as its cost and scaled shortest geographical distance as an admissible heuristic.The search depth is bounded by the maximum distance a vehicle can travel at speed vmax between observations.
  • Backward paths: GPS noise can make a stationary vehicle appear to move backward on a link, so forbidding backward paths may produce incorrect transitions or implausible loops.The paper discusses alternative treatments that trade physical consistency, state density, connectedness, and computational cost.
  • Practical trade-offs: The implementation’s max-offset heuristic preserves connected states, while different backward-path strategies suit density estimation, travel-time estimation, or expensive high-frequency offline filtering.The heuristic returns x = (l, max(obefore, o∗)); map inaccuracies and out-of-network driving are handled separately.

III. DISCRETE FILTERING USING A CONDITIONAL RANDOM FIELD

The section formulates trajectory reconstruction as probabilistic inference over candidate states and paths using a Conditional Random Field. This formulation addresses selection bias in directed models while retaining efficient inference under Markov assumptions.

  • Probabilistic formulation: The framework selects candidate projections and interleaved paths to infer a reconstructed trajectory or posterior distributions over states and paths.Additional independence assumptions make inference tractable instead of requiring enumeration of exponentially many trajectories.
  • Model components: The observation model scores GPS measurements conditioned on vehicle states, while the transition model represents driver preferences over possible paths.These models are combined into a single trajectory potential.
  • Conditional Random Field: The Conditional Random Field combines observation and transition factors into an unnormalized distribution over trajectories.Its partition function is needed during training and can be computed efficiently with dynamic programming.
  • Limitations of HMMs: Hidden Markov Models suffer from selection bias because independently normalized transitions favor states with fewer path expansions.In road networks, this can assign excessive weight to highly disconnected highways and insufficient weight to other roads.
  • Conditional Random Field: CRFs avoid this problem by renormalizing once over complete paths from start to end rather than independently at every state transition.This changes the normalization scope that produces the HMM bias.

B. Finding the most likely path

The most likely trajectory is found by maximizing its potential over valid combinations of candidate states and paths. Dynamic programming computes this optimum efficiently and traces back the realizing trajectory.

  • Candidate trajectories: Valid trajectories combine candidate states for each observation with paths connecting consecutive candidate states.A path must begin at one candidate state and end at the next.
  • Complexity: O(TI*J*) computations suffice to find the most likely trajectory, where I*=max_t I_t and J*=max_t J_t.This avoids enumerating the at most product-over-time combinations of candidate states and paths.
  • Maximum-potential inference: The most likely trajectory maximizes the potential over all trajectories compatible with the observations.The partition function is unnecessary because it is common to all candidate trajectories.
  • Dynamic programming: Dynamic programming uses inductive partial-potentials identities to compute the maximum and backpointers to recover the corresponding complete trajectory.Only the partial trajectory realizing each intermediate maximum must be retained for traceback.
  • Application: Lagged smoothing can disambiguate an exit-ramp decision by incorporating subsequent trajectory points before returning an estimate.The later observations help decide whether a vehicle left the highway.

C. Trajectory filtering and smoothing

The CRF supports posterior marginal inference through forward and backward recursions over candidate states and paths. Filtering, smoothing, and lagged smoothing provide different latency–accuracy trade-offs.

  • Posterior marginals: State and path marginals represent posterior probabilities over candidate trajectory elements given all observations.The state marginal gives the probability of occupying a candidate state among the alternatives at that time.
  • Forward–backward inference: The chain structure factorizes each marginal into past-and-present and future-observation terms that are computed by forward and backward recursions.This replaces an exponentially large trajectory summation with two more efficient computations.
  • Filtering modes: Smoothing uses all observations, whereas online filtering updates the current estimate as each new observation arrives.Forward recursion supports online estimation, while the complete smoothing procedure combines forward and backward results.
  • Filtering modes: Online filtering minimizes latency and computation by retaining only the previous forward distribution, at the expense of accuracy.Earlier forward distributions can be discarded when only the latest estimate is needed.
  • Filtering modes: Lagged smoothing stores several points and trades additional latency for accuracy by using future observations to update an earlier state estimate.Even a small lag can improve accuracy while keeping latency reasonable.

D. Observation model

The observation model assigns likelihoods to GPS measurements based only on their distance from candidate road states. It uses a constant network-wide noise scale, with an estimated value of 10–15 meters for the studied data.

  • Observation likelihood: The observation probability depends only on the distance between a candidate road point and the GPS coordinates.The model uses an isoradial observation assumption and a distance function over geocoordinates.
  • Algorithmic context: Lagged smoothing processes queued observations with forward and backward filters before returning the delayed state and path estimates.For lag k, the algorithm returns the estimate corresponding to the first queued observation after processing later points.
  • Noise assumptions: The standard deviation σ is assumed constant across the road network, although urban canyoning and satellite occlusions violate this assumption in practice.The model can instead be adapted geographically through clustering.
  • Noise assumptions: 10–15 meters is the estimated GPS-noise standard deviation for the data studied in the article.This estimate is obtained using the paper’s later estimation procedures.

E. Driver model

The driver behavior model assigns probabilities to acceptable paths using a feature-based exponential-family distribution. Its parameters encode preferences such as shorter paths, speed, travel time, stops, signals, and turns.

  • The model assigns a weight to each acceptable road-network path using selected path features.Features can include path length, stop signs, and road speed limits.
  • The path distribution is parameterized by a behavioral vector that forms a weighted combination of path features.The feature function maps each path to a K-dimensional feature vector.
  • A length-only model interprets the inverse parameter as a characteristic length measuring preference for shorter paths.The parameter indicates how aggressively a driver follows the shortest path.
  • The driver models also consider mean speed, travel times, stop signs and signals, and turns.
  • In Mobile Millennium, the feature function excludes current travel time because the filter feeds a travel-time learning model.Current travel time could be added as a feature if that information were available.

IV. TRAINING PROCEDURE

The training procedure calibrates the observation and path-selection models by maximizing observation likelihood and evaluating the learned parameters on held-out trajectories.

  • Training estimates the observation-model and path-selection parameters, including the weight vector µ and standard deviation σ.
  • The parameters are learned by maximizing the likelihood of the observations using standard machine-learning techniques.Likelihood computation requires evaluating the partition function.
  • The trained model is evaluated against held-out trajectories using several metrics described in Section VI.

A. Learning within the exponential family and sparse trajectories

The exponential-family formulation represents trajectory choices with non-negative potentials over sequences of discrete variables and learns parameters by maximizing their likelihood. Multiple GPS trajectories are handled as separate indexed sequences whose likelihoods sum.

  • Path and state variables can be treated uniformly as sequential choices among finitely many pairwise-compatible possibilities.Compatibility is encoded by the functions δ and ¯δ.
  • A trajectory is represented as a sequence of discrete multinomial variables with a non-negative potential controlled by parameter vector θ.The potential defines a probability distribution after normalization.
  • The parameterized potential uses θ as a model parameter rather than a random variable, and the partition function normalizes the potential.
  • The function h is parameter-independent, while feature vectors map each variable realization to a vector used by the exponential-family potential.
  • Multiple trajectories are indexed separately because each GPS sequence can have a different road-network state space.The total log-likelihood sums the likelihood contributions of the individual trajectories.
  • The log-likelihood is linear in θ minus the concave log partition function, yielding a unique solution under non-singular parameterization.Superlinear optimization algorithms can solve the resulting objective using derivatives of log Z(θ).

1) Efficient estimation of the partition function:

The partition function is computed without enumerating all paths by exploiting factorization and dynamic programming. Pairwise compatibility structure supports polynomial-time computation and sparse-data savings.

  • Naively computing the partition function considers exponentially many paths, but dynamic programming factors most of these computations.
  • The compatibility function h decomposes into binary indicators over consecutive variable pairs.These indicators generalize the δ and ¯δ functions for state and path choices.
  • Partial summations Z_l^i collect all partial paths ending at variable value z_l = i and can be computed recursively.
  • The complete partition function is obtained by summing auxiliary partial values.
  • Dynamic programming computes the partition function in polynomial time, with additional savings available through sparse data structures.The implementation should perform relevant calculations in the log domain because of floating-point precision limits.
  • The computation is a specific application of the junction-tree algorithm.

2) Estimation of the gradient:

The learning formulation converts path-and-state assignments into a unified conditional-random-field problem and estimates parameters using supervised or expectation-maximization procedures. With incomplete observations, EM alternates posterior inference over hidden assignments with parameter updates until convergence.

  • Gradient and learning formulation: The formulation transforms path and state variables into a single abstract variable set for conditional-random-field learning.The path and state variables correspond directly to the unified z variables and alternating feature vectors.
  • Supervised learning: With complete trajectories, parameter learning maximizes the likelihood of GPS observations using known path and state assignments.The observed paths and states determine the matching indexes used to solve the supervised optimization problem.
  • Incomplete observations: With only GPS observations, the path and state assignments are hidden, so learning maximizes expected likelihood under their assignment distribution.The expected likelihood is difficult because the distribution used for the expectation also depends on the parameters being learned.
  • Expectation-Maximization: Expectation maximization resolves this dependency by alternating posterior-distribution computation with parameter optimization using fixed expected feature values.The procedure first computes a distribution for the hidden assignments, then updates parameters by solving the resulting simpler optimization problem.
  • Expectation-Maximization: The implementation repeatedly computes path and state posteriors, updates expected feature values, and resolves the parameter-learning problem until convergence.The algorithm uses posterior values as plug-in distributions for the hidden assignments.

V. RESULTS FROM FIELD OPERATIONAL TEST

The field evaluation uses high-frequency San Francisco taxi trajectories as ground truth, downsamples them, and compares models, metrics, and computing strategies across sampling rates. The study evaluates path and state reconstruction, likelihood, entropy, and route miscoverage against several deterministic and probabilistic baselines.

  • Datasets and evaluation: About 700,000 one-second GPS measurements from ten San Francisco taxis provided high-accuracy ground-truth trajectories for evaluation.The experiment ran during two days in October 2010; a larger one-minute dataset was also used for unsupervised learning.
  • Datasets and evaluation: The evaluation decimated high-frequency trajectories to sampling intervals of 1 second, 10 seconds, 30 seconds, 1 minute, 1.5 minutes, and 2 minutes.Models were trained on separated subsets and tested under Viterbi, online, offline, and lagged-smoothing strategies.
  • Models and strategies: The tested models range from greedy closest-point and shortest-path baselines to supervised or unsupervised simple and complex probabilistic models.The complex model uses features including path length, stop signs, signals, turns, travel time, speed, and lane count.
  • Model relationships: The framework represents shortest-path, closest-point, and hard-closest-point approaches as special cases obtained by restricting features or changing model parameters.This common implementation allows the models to be compared by changing feature sets, parameters, and computing strategies.
  • Evaluation metrics: The study measures path misses, state misses, true-point and true-path log-likelihoods, point and path entropy, and relative route miscoverage.Entropy measures confidence in the filter's distribution, while miscoverage measures the fraction of the true path length not covered by the inferred path.
  • Evaluation metrics: Relative route miscoverage compares the length of the true path shared with an inferred path, with 0 indicating perfect coverage.For about 0.06% of point pairs, the true path was manually added because A* did not discover it.

B. Results

The results show strong reconstruction accuracy across sparse sampling, resilient probability assignments, and improved route recovery with backward information. Fixed-lag smoothing offers a practical accuracy–computation–timeliness trade-off, while large unsupervised datasets approach supervised performance.

  • Resilience: True-path likelihood remains relatively stable as sampling intervals grow, indicating that the filter continues assigning high probability to true projections amid increasing path ambiguity.The simple and complex models improve substantially when backward filtering steps are added.
  • Route recovery: A complex model improves route coverage by about 15% with smoothing, while 2-lag and offline strategies achieve lower relative miscoverage than online and 1-lag strategies.At high sampling resolution, inferred paths are close to the true trajectory even when they are not exactly identical.
  • Driver behavior: At 120-second sampling, learned weights show no preference between stop signs and signals but indicate a preference for right turns over left turns.The reported weights are w3 = −0.24±0.07 for stop signs and w4 = −0.21±0.11 for signals.
  • Computational trade-offs: Full smoothing can substantially improve filtering for roughly comparable computational effort, while fixed-lag smoothing approaches full smoothing with slightly greater cost.The authors recommend fixed-lag smoothing as a balance among computation, accuracy, and result timeliness.
  • Sampling rate: Errors increase until the 30-second interval and then plateau across most metrics, while performance remains decent as observations become farther apart.The authors note potential battery-life improvements of up to an order of magnitude for suitable GPS tracking devices.
  • Unsupervised learning: On the two-orders-of-magnitude-larger Dataset 2, unsupervised models reach performance on par with supervised models.The authors caution that unsupervised learning can reinforce a bad local minimum during the E step.

D. Key findings

The path inference filter reconstructs urban vehicle trajectories across sampling rates and configurable filtering strategies, with trained models improving path accuracy and computational trade-offs supporting deployment. Unsupervised training can match supervised performance under supported data conditions, while complex models also reveal driver behavior.

  • Trained models identify 80% to 95% of paths correctly for sampling intervals from 10 to 90 seconds.
  • Complex trained models improve incorrect-path results by 13-20% across all metrics compared with simpler trained or untrained alternatives.
  • Two-lagged smoothing and offline filtering outperform online filtering and 1-lagged smoothing, with two-lagged smoothing nearly matching offline performance.
  • Unsupervised training achieves accuracy comparable to supervised training within limits and with enough data, although EM-Simple may be overconfident.
  • The filter combines candidate road projections, candidate trajectories, observation and driver models, and a Conditional Random Field to select the most probable trajectory.
  • 400 points per second on one core and several thousand points per second on multicore systems demonstrate industrial-scale throughput, while extensions remain relevant for data sparser than two minutes.
Loading 1109.1966v2…