[논문 리뷰] ASPIRe: An Informative Trajectory Planner with Mutual InformationApproximation for Target Search and Tracking [2024]

 

---

1. Abstract

여기서는 STE를 SAT[search and tracking]이라고 표현한다. MCTS의 non-myopic[멀리 내다볼 수 있는] 방식을 채택하여 planning을 하려고 하지만, MCTS의 많은 계산량으로 인한 문제점이 존재한다. 이로 인해 MCTS는 제한된 particle filter를 사용한다. 이를 해결하기 위해 이 사람들은 Sigma Point-based mutual information reward pproximation[ASPIRe]를 제시한다. 이는 SP-based인 MI[mutual information]으로, 훨씬 우월한 real-time 계산시간을 보여주고, search에 대한 효율성을 지닌다.

---

2. Main[System Formulation]

• Sensor models
  discrete-time kinematic model을 다음과 같이 표현하자.
  $$x^r_{k+1} = f^r(x^r_k, u^r_k)$$
  이 때, f는 kinematic model이고, x, u는 robot의 state와 control이다. r은 로봇을 의미한다. k는 time step이다. 이 때, noise로 인해서 위 공식은 현실에서는 다음과 같이 표현된다.
  $$x^r_{k+1} = f^r(x^r_k, u^r_k) + η_k,η_k ~ N(0, Q)$$
  η은 gaussian noise다. 이 곳에서 $z_k$[sensor measurement]에 대해서 다음과 같이 표현한다.
  $$\begin{equation*} z_k = \begin{cases} \mathbf{h}(x_k^r, x_k^t) + \epsilon_k, \quad \epsilon_k \sim \mathcal{N}(0, \Sigma) & \gamma_k = 1 \\ \emptyset & \gamma_k = 0 \end{cases} \end{equation*}$$
  즉, $z_k$는 FOV안에 있을 때 값을 지닌다. h는 observation function, epsilon은 gaussian noise다. 

---

• Belief MDP Formulation
  SAT문제에 대해서 MDP[Markov decision process]를 이용해서 해결한다. 변수로는 h, B, A, τ, R, γ을 가지고, B : belief state space, A : action space, τ : belief transition model, h: planning horizon, γ : discount factor, R : Reward function. 그리고, particle filter에 대한 가중치에 대해서 설명한다.
  $$P(x_k^t | q) \sim \sum_{j=1}^{N} w_{j,k} \delta(x_k^t - \tilde{x}_{k}^{t,j})$$
  이는 추정되는 위치는 particle들의 가중치에 대한 합산을 통해서 나타난다는 것이다. 그리고 가중치는 다음과 같다.
  $$\begin{align*}\tilde{x}{k+1}^{t,j} &\sim \mathcal{N}(f^t(\tilde{x}k^{t,j}, u_k^t), \mathbf{Q}), \quad j = 1, \ldots, N, \\w{k+1}^j &= \frac{P(z{k+1} \mid \tilde{x}{k+1}^{t,j})}{\sum{j=1}^{N} P(z_{k+1} \mid \tilde{x}_{k+1}^{t,j})} w_k^j, \quad j = 1, \ldots, N,\end{align*}$$
  가중치는 x의 point에 따라서 업데이트 된다.

---

• Sigma Point-Based Mutual Information
  기존 Reward Function SP에서의 보상함수는 다음과 같다.
  $$R(B_k,a_k)=I(x_{k+1};z_{k+1})=H(z_{k+1})−H(z_{k+1}∣x_{k+1})$$
  즉, target의 위치 예상과 현재 내 위치에서의 target 정보간 차이가 보상 함수가 된다.
  여기까지는 기존의 GMM(Gaussian Mixture Model)과 같다. 여기까지 진행했을 때, GMM의 문제점을 제시한다.
  1. GMM은 정확하게 평가할 수 없고, MC 적분을 사용하여 수치적으로 평가할 수 있지만, 정확한 근사를 하는 과정에 계산량이 너무 많다.
  2. 이 문제를 해결하기 위해 사용하는 Taylor 전개법은 GMM의 엔트로피를 근사하기 위해 사용되었으나 이는 큰 오류값을 지닌다.
  이러한 문제점을 해결하기 위해 Sigma Point를 도입한다.
  • Sigma Point-Based Entropy
    entropy H[zk+1]은 다음과 같이 표현가능하다.
    $$H(z_{k+1})=−∫P(z_{k+1})logP(z_{k+1})dz_{k+1}≈−∑^N_{j=1}w^k_kp_j$$
    이전에, 정말 어려운 개념 하나를 들고 가자.
    UKF : 함수를 선형화 하지 않고 여러 샘플을 통해 가우시안의 근사분포를 얻어내는 것이 목표. point들의 새로운 mean값과 covariance를 계산하여 새로운 가우시안 분포를 만드는 것이 목표이다.
    
    샘플로 사용할 점을 먼저 정한다. 이 때, 샘플로 정하는 point를 Sigma Point, 우리가 이 논문에서 제시한 점이다. 또한 weight $w$를 구하게 된다.
    $$\begin{align*} \sum_i w^{[i]} &= 1 \\ \mu &= \sum_i w^{[i]} \chi^{[i]} \\ \Sigma &= \sum_i w^{[i]} (\chi^{[i]} - \mu)(\chi^{[i]} - \mu)^T \end{align*}$$
    Choosing Sigma Points
    $$\begin{align*} \chi^{[0]} &= \mu \\ \chi^{[i]} &= \mu + \left(\sqrt{(n + \lambda) \Sigma}\right)i \quad \text{for } i = 1, \ldots, n \\ \chi^{[i]} &= \mu - \left(\sqrt{(n + \lambda) \Sigma}\right){i-n} \quad \text{for } i = n+1, \ldots, 2n \end{align*}$$
    μ를 중심으로 샘플을 뽑는다고 생각하면 된다. 이 때, 𝜆는 𝜇에서부터 샘플을 얼마나 먼 지점에서 뽑느냐를 결정한다.
    Choosing Sigma Point weights
    $$\begin{align*} w_m^{[0]} &= \frac{\lambda}{n + \lambda} \\ w_m^{[i]} = w_c^{[i]} &= \frac{1}{2(n + \lambda)} \end{align*}$$
    마지막으로 Gaussian Approximation을 다음과 같이 표현한다.
    $$\begin{align*} \mu' &= \sum_{i=0}^{2n} w_m^{[i]} g(\chi^{[i]}) \\ \Sigma' &= \sum_{i=0}^{2n} w_c^{[i]} \left( g(\chi^{[i]}) - \mu' \right) \left( g(\chi^{[i]}) - \mu' \right)^T \end{align*}$$
    다시 논문으로 돌아와서, μ는 Point P들의 평균값이 된다.
    그리고, 논문에서는 P에 대해서 다음과 같이 approximated 한다.
    $$\begin{align*} P(z_{k+1} | \tilde{x}{k+1}^{t,j}) &\approx \sum{l=0}^{2m} w_s^{j,l} \delta(z_{k+1} - \tilde{z}_{k+1}^{j,l}) \end{align*}$$
    
    여기까지가 이 논문에서 제시한 방식이다.

---

3. Algorithm

알고리즘은 다음과 같다.

ASPIRe Algorithm

이는 기존의 MCTS 방법과 비슷하다. 보상에 따라 UCB[경계]를 통해 반복하며, 새로운 노드와 환경에 대해서 탐색하고 업데이트 하는 방식이다.

기존의 MCTS와 다른 점은, Tree가 계속해서 뻗어나가지 않아도[정해진 길이 만큼] 그 이전의 임계값을 초과한다면 최대 깊이에 도달하기 이전에 종료한다. 이를 통해서 target를 넘어가는 일이 발생하지 않는다.

---

4. Conclusion

Conclusion

결과적으로, 기존의 MC, Taylor 방식보다 더 나은 성능이 나타났다. 

Simulation

 

또한, Simulation하는 과정에 대해서도 다음과 같이 제공을 해 주었다. 제공한 모습을 통해서, Target이 관측이 되지 않았을 때는 무작위의 행동을 하는 모습을 보이지만, 관측이 되고 나서 Tracking 할 때에는 정확히 수행하는 것을 볼 수 있다.

---

5. Summery

이 논문에서는 기존 Gaussian 방식에 대해서 많은 계산량으로 인해 생기는 실시간적 적용이 이루어지지 않는 것에 대해서 문제점을 제기하였다. 그리고, UKF의 Sigma Point를 사용하여 이 문제를 해결하려고 하고 있다. 하지만, Sigma Point 를 사용하며 오차가 생기는 것과, 모든 Particle에 대해서 계산하는 것이 아니라는 것에 대해서 문제가 생길 수 있을 것 같다.