Abstract
This study presents a rigorous statistical validation of the Markov property—the assumption that a system's future state depends solely on its current state—within the context of vehicle trajectories. By comparing autonomous vehicles (AVs) and human-driven vehicles (HVs), the researchers demonstrate that while AVs generally follow a memoryless (first-order Markov) process, human drivers exhibit high-order Markov behavior, integrating several seconds of historical context into their decision-making.
Introduction
In traffic engineering and robotics, car-following models often rely on the Markov assumption. This simplification posits that the current state (e.g., position, speed, and gap) contains all necessary information to predict the next state. However, human driving is a complex cognitive task involving anticipation and reaction to past patterns. If the Markov assumption is flawed for humans, current simulators and AV controllers may fail to capture the nuanced, history-dependent nature of real-world traffic. This paper addresses this gap by applying conditional independence tests to real-world trajectory data.
Methodology
The researchers developed a statistical framework to distinguish between a standard Markov Process (MP) and a High-Order Markov Process (HOMP).
A standard MP assumes the action $A_t$ depends only on the current state $X_t$. In contrast, a HOMP considers a history of states $I_t = \{X_t, X_{t-1}, X_{t-2}, ...\}$. The study utilizes the following notations for the car-following state:
The core of the analysis involves:
- Conditional Independence (CI) Testing: Using Conditional Characteristic Functions (CCF) to determine if a trajectory satisfies the Markov property.
- Markov Order Estimation: Identifying the minimum number of past states ($k$) required to explain current decisions.
- Comparative Analysis: Employing $t$-tests and $F$-tests to compare the mean and variance of Markov orders between AVs and HVs.
Data and Results
The study analyzed two major datasets: the Lyft Level-5 Dataset (70,000+ real-world AV car-following pairs) and the CATS Lab ACC Dataset (controlled experiments with AVs and HVs in cruising and stop-and-go scenarios).
Adherence to the Markov Property
In the Lyft dataset, 80.95% of AV trajectories conformed to the first-order Markov property, compared to 67.16% of HV trajectories. This confirms that AVs, typically programmed with reactive controllers, are more "memoryless" than humans.
Markov Order and Heterogeneity
In the CATS Lab dataset, the average Markov order for HVs was significantly higher (3.18s) than for AVs (1.74s). Furthermore, $F$-test results ($F = 12.6774$) highlighted that human behavior is much more heterogeneous; different drivers utilize varying lengths of history in their decision-making logic.
Discussion and Key Insights
The findings suggest that context significantly influences the Markov property. Both AVs and humans show stronger adherence to the Markov property during "oscillation" (stop-and-go) scenarios than during steady cruising. In high-uncertainty, erratic traffic, drivers prioritize immediate feedback to avoid collisions, effectively reducing their reliance on long-term history.
However, for general trajectory prediction, the results indicate that human-centric models should incorporate at least 3-4 seconds of history to achieve high accuracy. While first-order models may suffice for current AV controllers, capturing human-like behavior requires accounting for the high-order dependencies identified in this research.
Conclusion
This work provides empirical evidence that human driving is fundamentally a high-order Markov process. Future research should extend this analysis to lateral maneuvers like lane-changing and investigate which specific historical features most heavily influence human decisions. Integrating these insights is crucial for developing more predictable and human-like autonomous driving systems.
Summary updated