https://ieeexplore.ieee.org/abstract/document/9653809
Learning an Explainable Trajectory Generator Using the Automaton Generative Network (AGN)
Symbolic reasoning is a key component for enabling practical use of data-driven planners in autonomous driving. In that context, deterministic finite state automata (DFA) are often used to formalize the underlying high-level decision-making process. Manual
ieeexplore.ieee.org
Introduction
본 논문에서는 주어진 data로부터 explainable structure를 추출해낼 수 있는 differentiable architecture를 설계했다. 즉, 모델이 trajectory를 생성할 뿐만 아니라, 내부에 analyzable한 구조를 갖는 AGN architecture를 제안하고 있다. (2022 RA-L)
Contribution은 다음과 같다.
- Automaton의 정의를 encode하고, driving data로부터 high-level planning을 학습할 수 있는 Automaton Generative Network (AGN) 구조를 제안함.
- 기존에 존재하는 data-driven trajectory planner와 AGN을 결합시켜서 explainability, sample efficiency, generalization을 향상시킴.
- 시뮬레이션 환경 뿐만 아니라, 실차 dataset을 통해 성능을 검증함.
Backgrounds
Definition
논문에서 계속 사용되는 "Deterministic Finite State Automaton (FSA)"에 대해 알아보자. DFA는 state machine의 graphical transition model 버전이라고 생각하면 되며, 주로 CS 분야의 lexical analysis나 pattern matching과 같은 task에 사용되는 개념이다. 기본적인 정의는 다음과 같다.
DFA is a tuple (( \mathcal{A} = (Q, q_{init}, \Sigma, \delta, F) )), where :
- ((Q)) : finite set of states
- ((q_{init} \in Q)) : initial state
- ((\Sigma)) : input alphabet
- ((\delta : Q \times \Sigma \to Q)) : transition function
- ((F \subseteq Q)) : set of accepting states
Finite sequence of symbols (word) : ((\sigma = \sigma_0 \sigma_1 ... \sigma_{N-1})), ((\sigma_k \in \Sigma))에 의해 생성된 ((\mathcal{A}))의 trajectory : ((q_0 q_1 ... q_N))을 생각해보자. 이 때, ((q_0 = q_{init}))이고, ((q_{k+1}=\delta(q_k, \sigma_k) \; \forall k \geq 0)) 이다.
또한, input alphabet ((\Sigma))는 주어진 set of propositions ((\Pi)) (binary value로 이루어진 variables)의 powerset으로 이루어져 있다. 즉, ((\Sigma=2^{\Pi})) 이다.
만약 finite input word ((\sigma \in \Sigma))가 "acceptable terminal state" (i.e. ((q_N \in F))) 를 갖는 ((\mathcal{A}))의 trajectory ((q))를 생성한다면, "((\sigma)) is acceptable"이라고 표현한다.
Guard of the transition : ((g(q, q') = \left\{ \sigma \vert q' = \delta(q, \sigma) \right\} \subseteq \Sigma)) 은 state ((q)) 에서 ((q'))로 transition되는 모든 input symbol들의 set을 의미한다.
그리고, 다음의 boolean operator도 사용된다. ((\wedge))(and), ((\vee))(or), ((\neg))(not).
Example
Fig. 2-(a)와 같이 ego vehicle이 비신호 교차로에 진입한 상황을 고려해보자. 여기서, 다음과 같이 총 4개의 propositions ((\Pi)) 를 정의한다.
(( \Pi : \; \left\{ cii, cs, F, S \right\} ))
- ((cci)) : whether there's a car in the intersection
- ((cs)) : whether that car has stopped (가끔 교차로에 진입해 있는 차량이 ego vehicle을 위해 멈춰주기도 한다!)
- ((F)) : Faster ; ego vehicle is speeding up
- ((S)) : Slower ; ego vehicle is slowing down
그러면, input alphabet ((\Sigma)) 는 다음과 같이 정의되며, 총 ((\left| \Sigma \right| = 2^4)) 개의 원소를 갖는다.
(( \Sigma = \left\{ cci \wedge cs \wedge F \wedge S, \neg cci \wedge cs \wedge F \wedge S, ... , \neg cci \wedge \neg cs \wedge \neg F \wedge \neg S \right\} ))
Fig. 2-(b)는 교차로 내에 "STOP" 또는 "YIELD" 표지판이 없고, 기본적으로 ego vehicle은 이미 교차로에 진입해있는 차량을 대상으로 양보한다는 high-level policy에 의해 정해진 DFA를 나타낸다. (이해를 돕기 위해, 간단하게 ((q_0))는 initial state이고, ((q_1))은 "Move forward", ((q_2))는 "Stop/Slow down"이라고 생각하면 된다. 예를 들어, i.c.에서 교차로 내에 차가 없거나 교차로 내의 차가 멈춰있다면 "Move forward"를 선택한다. "Move forward"에서 교차로 내에 차가 멈추지 않고 내 차량은 가속하고 있었다면 "Stop/Slow down"을 선택한다.)
[추가 설명] ((\sigma \in \Sigma)) 중에는 당연히 말이 안되는 것들도 있다. 예를 들어, (( \cdot \wedge \cdot \wedge F \wedge S)) 는 사실 존재할 수 없다. 즉, 이 경우 추후 설명될 ((L)) 값은 모든 state pair의 transition들에 대해 항상 0이다. 결국, ((cii \wedge \neg cs \wedge \neg F \wedge S)) 은 간단히 ((cii \wedge \neg cs \wedge S)) 로 표현하고 있다.
Automaton Generative Network (AGN)
앞서 설명한 DFA는 propositions (binary variables) 로 구성되어 있기 때문에 gradient 기반의 방법들에는 적용하기 어렵다. 따라서, transition function (edges와 guards) 을 학습함으로써 DFA를 미분 가능한 형태로 encode하는 AGN에 대해 소개하고 있다.
Predicate DFA (( (\mathcal{A}_p) ))
Modify the definition
우선, atomic binary value로 구성된 DFA를 AGN이 다루기 위해 DFA의 정의를 약간 수정하여 다음과 같이 continuous data로 구성된 predicate 형태로 만든다.
$$ p(s) : f^p(s) < c $$
이 때, ((s))는 continuous state, ((c))는 constant, 그리고 ((f^p(s)))는 ((s))에 대한 real-valued function이다. 이렇게 정의된 predicate가 "True"일 필요충분조건은 (( c - f^p(s) > 0 ))이다.
앞선 Fig. 2의 예시에서, ((cs))에 대한 predicate는 (( \left| v \right| < \epsilon )) 로 정의될 수 있고, 여기서 state ((s=v)) 는 교차로 내 차량의 속도, ((c=\epsilon)) 은 constant threshold, 그리고 ((f^p(\cdot) = \left| \cdot \right|)) 이다.
Modify the guard formula
기존 정의에 따르면, 두 개의 automaton state 간 transition은 edge의 조건 (i.e. guard formula)이 참일 때만 이루어진다. 예를 들어, Fig. 2-(b)에서 ((q_0))와 ((q_1)) 간 transition은 (( \neg cii \vee cs))가 참일 때 이루어진다.
하지만, continuous system의 state에 대해 transition이 이루어지려면 DFA의 transition function ((\delta))도 수정되어야 한다. 이에 guard formula를 변형시켜서 boolean operator로 구성된 predicate Boolean formula를 구성한다. 즉, ((q_i))에서 ((q_j))로의 transition에 대한 predicate guard는 ((b(q_i,q_j)))로 표현된다.
Modify the transition function
이제 Signal Temporal Logic (STL) 에서 고안된 개념인 robustness of predicated guard에 대해 정의하고자 한다. 쉽게 말하면, 현재 정의된 명제들은 시간에 따라 참과 거짓이 변화하기 때문에 이에 대한 강건성을 정의한 것이라고 생각하면 된다.
주어진 두 개의 predicates ((p_1(s) : f^{p_1}(s) < c_1)), ((p_2(s) : f^{p_2}(s) < c_2)) 에 대해 robustness degree of predicate guard는 다음과 같이 recursive하게 정의된다.
$$ \begin{align*}
r(s, p) &= c - f^p(s) \\
r(s, \neg p) &= -r(s, p(s)) \\
r(s, p_1 \wedge p_2) &= \min(r(s, p_1), r(s, p_2)) \\
r(s, p_1 \vee p_2) &= \max(r(s, p_1), r(s, p_2))
\end{align*} \tag{1} $$
이 정의를 이용하면, predicate guard가 state ((s))에 대해 "True"일 필요충분 조건은 robustness degree가 ((s))에서 0보다 클 때로 표현된다. 즉, predicate transition function ((\delta_p))의 정의는 다음과 같다.
((\delta_p)) ((s.t.)) ((q_i)) transitions to ((q_j)) at ((s)) ((\text{iff})) (( r( s, b(q_i, q_j) ) > 0))
Contructing an AGN
Predicate DFA에 대한 표현은 다음과 같이 정리된다.
- (( P = \left\{ p_i \vert i \in [0,n) \right\} )) : given set of predicates
- (( \Sigma = 2^P )) : constructed alphabet of automation as powerset of P
- (( \sigma \in \Sigma )) : conjunctive predicate Boolean formula over the predicates in ((P))
- (( L : Q \times \Sigma \times Q \to \left\{ 0, 1 \right\} )) : labeling function
여기서, ((L))은 두 state 사이의 transition이 어떤 input alphabet에 의해 관리되는지를 나타내며, (( L(q_i, \sigma_k, q_j) = 1 )) 은 ((\sigma_k))가 ((q_i))에서 ((q_j))로의 transition에 대한 guarding 성분으로 구성되어 있음을 의미한다. (( (q_i, q_j) ))의 guard에 대한 Boolean formula는 다음과 같이 표현된다.
$$ b(q_i, q_j) = \bigvee_{k\in[0,n)} L(q_i, \sigma_k, q_j)\sigma_k \tag{2} $$
Fig. 3의 예시는 주어진 predicate set ((P = \left\{ cii, cs \right\}))을 가지고 automation을 생성하는 과정이다. 여기서, (( \neg cii \vee cs = (cii \wedge cs) \vee (\neg cii \wedge cs) \vee (\neg cii \wedge \neg cs) )) 로 줄여서 쓰고 있다.
- Alphabet 정의 : (( \Sigma = \left\{cii \wedge \neg cs, cii \wedge cs, \neg cii \wedge cs, \neg cii \wedge \neg cs \right\} ))
- 각 ((\sigma \in \Sigma))에 대해, ((\sigma))가 영향을 미친 edge들을 포함한 sub-automation을 만든다.
- 구한 sub-automata들에 대해 Eqn. (2)를 적용하여 final automaton을 구한다.
각 sub-automata를 나타내는 행렬의 column과 raw는 각각 source, target automaton state를 표현하고 있으며, transition matrix로 해석할 수 있다. 앞서 설명한 바와 같이, ((\mathcal{A}_p)) 안에 정의된 nodes ((q_i)) 와 ((q_j)) 간 transition은 robustness (( r( s, b(q_i, q_j) ) ))에 따라 결정되며, Eqn. (1)과 (2)로부터 다음과 같이 정리된다.
$$ r(s, b(q_i, q_j)) = \max_{k \in [0, n)} L(q_i, \sigma_k, q_j) r(s, \sigma_k) \tag{3} $$
이제 AGN을 본격적으로 설계해보자. 주어진 predicates set ((P))와 ((N))개의 automaton nodes로부터 현재 automaton state ((\mathbf{q}_t \in \mathbb{R}^N)) 를 ((N)) 차원의 vector로 표현할 수 있으며, 이때 ((i))번째 성분은 해당 state가 ((q_i))에 속할 확률을 의미한다.
Alphabet vector ((\mathbf{v}^\Sigma))는 각 성분으로 (( v^sigma = r(s, \sigma) )), ((\sigma \in \Sigma))를 가지며, 이 때 ((r))은 Eqn. (1)에서 정의한 robustness degree를 의미한다. 또한, 아래의 weight도 정의한다.
$$ \mathbf{W}^\Sigma = \text{sigmoid}(\mathbf{W}^{\mathcal{L}}) \tag{4} $$
여기서, (( \mathbf{W}^{\mathcal{L}} ))은 learnable weight로 (( \left| \Sigma \right| \times N \times N )) 차원의 행렬이다. 각 성분 ((\sigma_{k, i, j}^\sigma))는 state ((q_i))에서 ((q_j))로의 transition에 대해 ((\sigma_k))가 얼마나 많은 영향을 주었는지를 의미한다.
Robustness martix ((\mathbf{R}))도 정의되며, ((N \times N)) 차원의 행렬로 각 성분 ((r_{ij}))는 다음과 같이 정의된다.
$$ r_{ij} = \max_{k \in [0, n)} w_{k,i,j}^\sigma v_k^\sigma = \max_{k \in [0, n)} w_{k,i,j}^\sigma r(s, \sigma_k) \tag{5} $$
Eqn. (3)의 scaled version이라고 생각하면 되며, robustness가 0보다 큰 edge들만 고려하면 되기 때문에 ((\mathbf{R}))에 ReLU activation을 적용한다. 최종적으로, ((\mathbf{q}_t))에서 ((\mathbf{q}_{t+1}))로의 transition은 다음과 같이 표현할 수 있다.
$$ \mathbf{q}_{t+1} = \text{softmax} (ReLU( \mathbf{R} ) \cdot \mathbf{q}_t ) \tag{6} $$
여기서, AGN이 gradient를 정의할 수 있도록 ((\max(\cdot))) 함수가 (( \text{softmax}(\cdot) ))으로 대체되었다. 결국 AGN 함수는 input vector ((\mathbf{v}^\Sigma))를 받아 transition system (state machine) 처럼 동작하고, 시간에 따라 반복되며 학습이 진행되는 RNN과 유사한 구조를 갖는다.
Fig. 5는 AGN과 trajectory generation module (TGM)이 적용된 decoder를 model의 개략도이다.
- AGN input : ((\mathbf{v}^\Sigma)) using high-level features (agents' position, velocity, lane representation, goal pose, etc.)
- AGN output : Automaton state distribution
- TGM input : AGN output + BEV feature from CNN feature extractor
- TGM output : Predicted trajectory
이 논문에서 제안하는 장점 중 하나로, TGM은 다양한 종류의 네트워크가 될 수 있다. 여기서는 LSTM 계열의 모델을 사용했으며, 다음은 AGN decoder를 학습하는 알고리즘이다.
이 때, (( \theta^{AGN} = \mathbf{W}^{\mathcal{L}} ))이며, data sample의 구성 요소는 (( \mathbf{x}_0 )) - inputs at current time step (i.e. BEV image, agent poses, velocities, etc.); (( \mathbf{y}_0 )) - ego vehicle's currnet positions; (( \mathbf{y}_{1:T} )) - ego vehicle's target future trajectory 이다.
Predicate DFA Corresponding to Learned AGN
학습된 ((\mathbf{W}^\Sigma)) 로부터 대응되는 (( \mathcal{A}_p ))를 도출해낼 수 있다. Fig. 4-(a)는 학습된 weight 예시이고, (b)는 이로부터 생성한 (( \mathcal{A}_p ))이다.
각 edge에는 transition 여부를 결정하는 robustness term이 표기되어 있고, predicate guard를 계산하기 위해 threshold ((\eta))를 설정한다. 즉, ((w_{k,i,j}^\Sigma > \eta))일 때 (( (q_i, q_j) ))에 해당하는 edge 상에 ((\sigma_k))가 존재하게 된다. Fig. 4-(b)에서는 (( \eta=0.15 ))로 설정되어 있으며, 이는 hyper-parameter이다.
Experiments
Setup
두 가지 방법으로 실험을 진행함.
- Simulated Intersection : Highway-env [19] for synthetic data generation.
- Ego vehicle은 Fig. 2-(b)에 나타낸 GT automaton을 따라 제어됨.
- Goal : Synthetic dataset을 사용하여 GT automaton을 학습하는 것이 가능한지 확인하고, 학습된 automaton의 특성을 분석하는 것.
- Using NuScenes dataset : 1000 scenes of 20s videos.
- 이 경우, GT automaton이 없음.
- Goal : Ego vehicle을 guide할 수 있는 explainable representation을 AGN이 학습할 수 있는지 확인하는 것.
- Evaluation metrics :
- Average displacement error (ADE)
- Safety distance - minimum distance to other agents along the generated trajectory
- Goal distance - caculates how close the generated trajectory is able to reach its goal
[19] E. Leurent, “An environment for autonomous driving decision-making,” 2018. [Online]. Available: https://github.com/eleurent/highway-env
Results
Simulated Intersection
Fig. 6-(a)에서 AGN의 edge 굵기는 연결 강도, 즉 transition이 일어날 확률을 의미한다. 처음에는 비슷한 값으로 random하게 초기화되어 있다가, 학습이 진행됨에 따라 ((q_0))와 연결된 edge들의 연결은 약해지고, ((q_1)) 및 ((q_2)) 간 (자기 자신 포함) 연결된 edge들의 연결은 강해졌다. 100번때 epoch에서는 ((q_0))가 initial state 역할을 하게 되고, 대부분의 transition 결과, ((q_1)) 또는 ((q_2))에 머무르게 된다. 하지만 GT와는 조금 다르게 ((q_0))로 가는 모든 edge가 사라지지는 않았다.
Fig. 6-(b)는 비보호 좌회전 시나리오이다. State ((\mathbf{q}))는 3차원의 vector이며, 각 성분은 각각의 state에 속할 확률을 의미한다. 왼쪽 아래 automaton의 배경 투명도는 그 확률을 의미하며, 진할수록 큰 값을 가진다.
주목할만한 점은 각 state가 암시적으로 특정 maneuver를 나타내고, 그 maneuver들은 서로 확실하게 구분된다는 것이다. ((\mathbf{q}))는 (([1,0,0]))으로 초기화된 후, Fig. 7에서 나타낸 바와 같이 생성된 trajectory를 관찰해보면 ((q_1))은 "fast moving mode"를, 그리고 ((q_2))는 "slow moving (yielding) mode"를 나타낸다는 것을 확인할 수 있다. (초기화 시, 속도는 (([5, 10]))에서 random하게 sampling 하도록 설정되어 있다.)
Nuscenes dataset
이번에는 Nuscenes dataset을 사용하여 학습했으며, Fig. 8은 evaluation 결과이다. 연두색이 ego vehicle이고 right-turn 시나리오에서 앞 차 대상으로 "slow down"하고 있는 상황이라는데... 그림을 봐서는 이해하기 어렵다. (좌측통행 도로이고, ego vehicle은 left-turn 하고 있다고 이해했다. 그리고 그 경로와 인접해있는 차량은 역주행 차량으로 보자...)
차량이 좌회전을 시작하는 11초 정도부터 ((q_0))에서 ((q_1))으로 distribution shift가 일어났고, 끝날 때 다시 ((q_0))로 돌아갔다. 또한, 차량이 "slow down"하고 있었기 때문에 ((q_2))에는 낮은 확률이 부여되었다. 즉, 이번에는 ((q_0))에 "Driving straight"가 부여되었고, ((q_1))과 ((q_2))에는 각각 회전 과정에서 "Slow down"과 "Move fast"가 암시적으로 부여되었다고 생각할 수 있다. (AGN이 steering mode에 따라 q-state들을 mapping하도록 학습한 것이다!)
Table 1은 9개의 node들을 가진 AGN을 학습시킨 결과이다. 여기서 safety distance 항목이 SOTA를 달성하지 못했는데, 그 이유는 이 metric이 goal distance와 trade-off 관계에 있기 때문이다. 실제 사람의 운전 데이터를 기반으로 학습했기 때문에, 보수적인 안전거리 확보보다는 목적지에 더 가까운 trajectory planning이 수행되었고, 그 성향을 반영한 것이다.
Remarks
Summary
- State input을 받아 trajectory output을 출력하는 딥러닝 모델 중간에 AGN을 도입하여 explainable한 구조를 제시함.
- High-level policy를 나타내는 DFA를 reconstruct 했을 때, 각 state가 explicit한 의미를 가짐.
- Trajectory generator에 LSTM 구조를 사용하여 temporal 정보를 활용함.
- 시뮬레이션 및 실제 사람의 운전 데이터를 사용하여 성능을 검증함.
Limitations
- 횡방향으로는 사전 지정된 경로를 추종하며, 종방향 planning만 진행함.
- 각 state의 explicit한 의미가 heuristic manner로 부여됨.
- HVs의 behavior가 고정된 채로 training 및 evaluation이 진행되었으며, behavior 추정이 이루어지지 않음.
