$ \DeclareMathOperator{\DOT}{.} \DeclareMathOperator{\nondet}{|} \newcommand\conc{\parallel} \newcommand\m[1]{\mathit{#1}} \newcommand\D{\mathcal{D}} \newcommand\E{\mathcal{E}} \newcommand\F{\mathcal{F}} \newcommand\I{\mathfrak{I}} \newcommand\ntg{\m{ntg}} \newcommand\ttc{\m{ttc}} \newcommand\tntg{\m{tntg}} \newcommand\tttc{\m{tttc}} \newcommand\antg{\m{antg}} \newcommand\attc{\m{attc}} \newcommand\NTG{\m{NTG}} \newcommand\TTC{\m{TTC}} \newcommand\TNTG{\m{TNTG}} \newcommand\TTTC{\m{TTTC}} \newcommand\nonzero{\eta} \newcommand\defined{\kappa} \newcommand{\defeq}{\stackrel{\mathsf{def}}{=}} \newcommand{\qqquad}{\quad\qquad} \newcommand\b{\color{blue}b} \newcommand\c{\color{red}c} \newcommand\d{\color{green}d} $

Spatio-Temporal Reasoning about Traffic Scenarios

Knowledge-Based Systems Group

RWTH Aachen University

Commonsense 2013

Introduction

Longitudinal traffic model
- Continuous values
- Relative perspective
- Complete view of traffic
Based on temporal distance measures
- Net Time Gap (NTG)
- Time To Collision (TTC)
Application in plan recognition

Net Time Gap (NTG)

Net Time Gap: ntg(b, c) =

$\ntg(\b,\c) = \frac{x(\c) - x(\b)}{v(\b)}$

Time To Collision (TTC)

Time To Collision: ttc(b, c) =

$\ttc(\b,\c) = \frac{x(\c) - x(\b)}{v(\b) - v(\c)}$

What NTG + TTC tell us

ntg(b, c) 0 ntg(c, b) 0 ttc(b, c) 0

NTG + TTC tell us how two cars interrelate

Symmetry and Transitivity

$\ntg(\c, \b) = \frac{-1}{1 - \frac{\ntg(\b, \c)}{\ttc(\b, \c)}} \cdot \ntg(\b, \c)$

$\ntg(\b, \d) = \ntg(\b, \c) + \big(1 - \tfrac{\ntg(\b, \c)}{\ttc(\b, \c)}\big) \cdot \ntg(\c, \d)$

$\ttc(\c, \b) = \ttc(\b, \c)$

$\ttc(\b, \d) = \lambda_1 \cdot \ttc(\b, \c) + \lambda_2 \cdot \ttc(\c, \d)$

$\small \lambda_1 \defeq \tfrac{\ttc(\c, \d) \cdot \ntg(\b, \c)} {\ntg(\c, \d) \cdot \ttc(\b, \c) + \ttc(\c, \d) \cdot \ntg(\b, \c) - \ntg(\c, \d) \cdot \ntg(\b, \c)}$

$\small \lambda_2 \defeq \tfrac{\ttc(\b, \c) \cdot \ntg(\c, \d) - \ntg(\b, \c) \cdot \ntg(\c, \d)} {\ntg(\b, \c) \cdot \ttc(\c, \d) + \ttc(\b, \c) \cdot \ntg(\c, \d) - \ntg(\b, \c) \cdot \ntg(\c, \d)}$

Time and Acceleration

Time: 0 s

Acceleration = discontinuous change of velocity by a relative factor

$\tntg(\b,\c,t) = \ntg(\b,\c) - t \cdot \tfrac{\ntg(\b,\c)}{\ttc(\b,\c)}$

$\antg_1(\b, \c, q) = \tfrac{1}{q} \cdot \ntg(\b, \c)$

$\tttc(\b,\c,t) = \ttc(\b,\c) - t$

$\attc_1(\b, \c, q) = \frac{1}{(q - 1) \cdot \frac{\ttc(\b, \c)}{\ntg(\b, \c)} + 1} \cdot \ttc(\b, \c)$

Similarly $\small \antg_2(\b,\c,q)$, $\small \attc_2(\b,\c,q)$ for $\small \c$ accelerating.

Situation Calculus

Reiter's Situation Calculus:

Basic Action Theory: FOL sentences about
- fluent values in initial situation $S_0$
- how actions affect fluent values in situations $\m{do}(a,s)$
- action preconditions $\m{Poss}(a, s)$
Action language Golog
- program execution builds up a situation term
- nondeterminism

Situation Calculus Theory

Fluents: $\NTG(b,c,r,s)$, $\TTC(b,c,r,s)$, $\m{lane}(b, s) = \ell$
- Represent partial functions $\ntg(b,c,s) = r$, $\ttc(b,c,s) = r$
- Situation parameter $s$ encodes time and acceleration
Actions: $\m{accel}(b, q)$, $\m{wait}(t)$, $\m{lc}(b, \ell)$
Initial situation: contains chain of measured values
- Complete knowledge
- Symmetry and transitivity are state constraints

Situation Calculus Theory

If $t_i$ contains $\ntg(b,c,s)$ then $t_1 = t_2$ expands to
$\exists r \, \big(\NTG(b,c,r,s) \wedge (t_1)^{\ntg(b,c,s)}_r = (t_2)^{\ntg(b,c,s)}_r\big)$.
Analogously for $\ttc(b,c,s)$ and $\frac{x}{y}$.

Successor State Axiom for NTG:

\begin{align*} & \NTG(b, c, r, \m{do}(a, s)) \equiv{}\\ & \quad \exists t \, \left( a = \m{wait}(t) \wedge %\ttc(b, c, s) \neq 0 \wedge{} r = \ntg(b, c, s) - t \cdot \tfrac{\ntg(b, c, s)}{\ttc(b, c, s)} \right) \; \vee{}\\ & \quad \exists q \, \left( a = \m{accel}(b, q) \wedge %q \neq 0 \wedge{} r = \tfrac{1}{q} \cdot \ntg(b, c, s) \right) \; \vee{}\\ & \quad \NTG(b, c, r, s) \wedge \forall t \, a \neq \m{wait}(t) \wedge{} \forall q \, a \neq \m{accel}(b, q) \end{align*}

$\TTC$ analogously.

The Model in Action

Time: 0 s

S₀

Application: Plan Recognition

Our approach:

Domain specification = Basic Action Theory
Plan library = (nondeterministic) Golog programs
Simulate program execution, try to match with observations

Plan Recognition System

Driving Simulator:

Adapted racing game TORCS
Complete knowledge
Two observations per second

Plan Recognition System:

Golog interpreter (written in Haskell)
Executes concurrently
- One program for each car
- Exogenous actions for observations
Decision-theoretically searches for the best execution

Plan Recognition Example

green passes blue on the left lane and
red passes blue with lane changes

Observed scenario:

Reconstructed scenario:

S₀

Plan Recognition Example

Goal: execute program in a way that matches observed NTG + TTC with model NTG + TTC

Conclusion

Conclusion:

Temporal distances (NTG, TTC)
No global information needed (no absolute velocities, no GPS)
Few NTG + TTC measurements give complete view of traffic
Integrated time and simplified acceleration
Used for on-line plan recognition

Future work:

Sensing and incomplete knowledge
Inaccurate measurements
Larger-scale experiments
Prediction of traffic situations