Abstracting road traffic via topological braids: Applications to traffic flow analysis and distributed control

Abstract

Despite the structure of road environments, imposed via geometry and rules, traffic flows exhibit complex multiagent dynamics. Reasoning about such dynamics is challenging due to the high dimensionality of possible behavior, the heterogeneity of agents, and the stochasticity of their decision-making. Modeling approaches learning associations in Euclidean spaces are often limited by their high sample complexity and the sparseness of available datasets. Our key insight is that the structure of traffic behavior could be effectively captured by lower-dimensional abstractions that emphasize critical interaction relationships. In this article, we abstract the space of behavior in traffic scenes into a discrete set of interaction modes, described in interpretable, symbolic form using topological braids. First, through a case study across real-world datasets, we show that braids can describe a wide range of complex behavior and uncover insights about the interactivity of vehicles. For instance, we find that high vehicle density does not always map to rich mixing patterns among them. Further, we show that our representation can effectively guide decision-making in traffic scenes. We describe a mechanism that probabilistically maps vehicles’ past behavior to modes of future interaction. We integrate this mechanism into a control algorithm that treats navigation as minimization of uncertainty over interaction modes, and investigate its performance on the task of traversing uncontrolled intersections in simulation. We show that our algorithm enables agents to coordinate significantly safer traversals for similar efficiency compared to baselines explicitly reasoning in the space of trajectories across a series of challenging scenarios.