$\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) =
s

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

# Time To Collision (TTC)

Time To Collision:     ttc(b, c) =
s

$\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(b, c) 0     ntg(c, b) 0     ttc(b, c) 0

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

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

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

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

# 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$
• 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) (\NTG(b,c,r,s) \wedge (t_1)^{\ntg(b,c,s)}_r = (t_2)^{\ntg(b,c,s)}_r)$.
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) \DOT 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)} \; \vee{}\\ & \quad (\exists q) \DOT a = \m{accel}(b, q) \wedge %q \neq 0 \wedge{} r = \tfrac{1}{q} \cdot \ntg(b, c, s) \; \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.

Time: 0 s
S0

# 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:

• Complete knowledge
• Two observations per second

Plan Recognition System:

# Plan Recognition Example

• green passes blue on the left lane and
• red passes blue with lane changes
Observed scenario:
Reconstructed scenario:
S0

# Plan Recognition Example

Goal: find program execution s.t. observed NTG + TTC and model NTG + TTC coincide

# 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