\section*{Appendix}

\begin{proof}[Proof of Theorem~\ref{thm:V>0}]
We first prove the sufficiency. Suppose that there exist an $\epsilon>0$ and a finite $T>0$ such that for all $\phi\in\Phi$, there is a sequence of control inputs $\mathbf{u}=\{u_t\}_{t=0}^\infty$ with the property $
     \min\{\min_{t=0,\dots,T} \gamma^t c(\xi_x^{\mathbf{u},\phi (\mathbf{u})}(t)), \gamma^T r(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(T))\}>\epsilon,$
which implies that for all $\phi\in\Phi$.
We then have $V(x) \ge \epsilon >0$.

We show the necessity by a contrapositive statement. Suppose that for all $\epsilon>0$, there exists a disturbance strategy $\phi\in\Phi$ such that for all sequences of control inputs $\{u_t\}_{t=0}^\infty$ and all time $T\in\{0,1,\dots\}$, $
\min\{\min_{t=0,\dots, T}\gamma^t c(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(t)),\gamma^T r(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(T))\}\le \epsilon,$
which is equivalent to that for all $\epsilon>0$, there exists a disturbance strategy $\phi$ with the property
\begin{equation*}\small
\begin{aligned}
    \max_{\{u_t\}_{t=0}^\infty} \sup_{t=0,1,\dots}&\min\big\{ \min_{t=0,\dots, T} \gamma^t c(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(t)) , \gamma^T r(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(T))\big\}\le \epsilon.
\end{aligned}
\end{equation*}
In another words, for all $ \epsilon>0$,
\begin{equation*}\small
\begin{aligned}
    V(x_0) = \inf_{\phi} \max_{\{u_t\}_{t=0}^\infty}& \sup_{t=0,1,\dots} \min\big\{ \min_{t=0,\dots, T}\gamma^t c(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(t)), \\&\gamma^T r(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(T)) \big\}\le \epsilon,
\end{aligned}
\end{equation*}
which yields that
\begin{equation*}\small
\begin{aligned}
    V(x_0) = \inf_{\phi} \max_{\{u_t\}_{t=0}^\infty}& \sup_{t=0,1,\dots} \min\big\{ \min_{t=0,\dots, T}\gamma^t c(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(t)), \\ &\gamma^T r(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(T)) \big\}\le0.
\end{aligned}
\end{equation*}

Therefore, $V(x)>0$ if and only if the problem \eqref{eq:inf_horizon_reach_avoid_problem} is finite-time feasible and reachable for the initial state $x$.
\end{proof}
\begin{lemma}\label{lem: max_min_swap} Given a compact set $\mathcal{C}\subseteq \mathbb{R}$ and a function $a(\cdot):\mathbb{R}\to \mathbb{R}$, we have $\max_{c\in \mathcal{C} }  \min (a(c), b) = \min (\max_{c \in \mathcal{C} } a(c), b),\label{eq:max_min_swap_eq} $ and $\min_{c\in \mathcal{C} }  \min (a(c), b) = \min (\min_{c \in \mathcal{C} } a(c), b) $.
\end{lemma}
\begin{proof}[Proof of Theorem~\ref{thm:Bellman}]
We first show that $V(x)$ as defined in \eqref{eq:inf_horizon_reach_avoid_problem} satisfies the Bellman backup equation \eqref{eq:bellman_backup}, and then show that the proposed Bellman backup \eqref{eq:bellman_backup} is a contraction mapping.

By definition, we have
\begin{equation*}\small
\begin{aligned}
V(x_0) =&
\max\Big\{ \min\{ r(x_0), c(x_0) \},  \inf_{\phi}\max_{\{u_t\}_{t=0}^\infty} \sup_{t=1,2,\dots} \min \{ \min\{\\&\gamma^t r(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(t)), \min_{\tau=1,\dots, t} \gamma^{\tau} c(\xi_{x_0}^{\mathbf{u},\phi(\mathbf{u})}(\tau))\}, c(x_0) \}\Big\} .
\end{aligned}
\end{equation*}
By applying Lemma \ref{lem: max_min_swap}, the above equation implies
\begin{equation*}\small
\begin{aligned}
V(x_0
= &\min\Big\{ c(x_0), \max\{ r(x_0) , \gamma \max_{u_0}\min_{d_0} V(f(x_0,u_0,d_0)) \} \Big\}.
\end{aligned}
\end{equation*}
\noindent In what follows, we show that \eqref{eq:bellman_backup} is a contraction mapping.
It suffices to show that for all state $x$, we have $| B[V_1](x) - B[V_2](x) |\le \gamma \left\| V_1 - V_2 \right\|_{\infty}$, where $V_1$ and $V_2$ are two arbitrary bounded functions. One can write \begin{equation}\label{eq:proof_Bellman_backup1}\small
    \begin{aligned}
    &|B[V_1] (x) - B[V_2](x)|\\%& = |\min\{c(x),\max\{r(x),\gamma \max_u\min_d V_k(f(x,u,d))\}\} \\&\ \ -\min\{c(x),\max\{r(x), \gamma \max_u \min_d V_{k-1}(f(x,u,d))\}\}| \\
    &\le | \max\{ r(x), \gamma \max_u\min_d V_1(f(x,u,d)) \}\\&\  \ - \max\{ r(x),\gamma \max_{u}\min_d V_2 (f(x,u,d)) \}|\\
    &\le | \gamma \max_u \min_d V_1(f(x,u,d))  - \gamma \max_u \min_d V_2(f(x,u,d))|
    \end{aligned}
\end{equation}
where the above inequalities follow from the fact that $\|\min\{a,b\} - \min\{a,c\}\|\le b-c, \forall a,b,c\in\mathbb{R}$.
Without loss of generality, we suppose that $\max_u\min_d V_1(f(x,u,d))\ge \max_u\min_d V_2(f(x,u,d))$ and let $u^*:=\argmax_u \min_d V_1(f(x,u,d))$. In addition, let $d^*:=\arg\min_d V_2(f(x,u^*,d))$. We then have
\begin{equation}\label{eq:proof_Bellman_backup2}\small
    \begin{aligned}
    |\gamma &\max_u\min_d V_1(f(x,u,d))-\gamma \max_u\min_d V_2 (f(x,u,d))|\\&\le \gamma |\min_d V_1( f(x,u^*,d) ) - \min_d V_2(f(x,u^*,d))|\\

    & \le \gamma | V_1(f(x,u^*,d^*)) - V_2(f(x,u^*,d^*)) |\\
    & \le \gamma \max_{x} |V_1(x) - V_2(x)|
    \le \gamma \|V_1 - V_2\|_{\infty}.
    \end{aligned}
\end{equation}
Combining \eqref{eq:proof_Bellman_backup1} and \eqref{eq:proof_Bellman_backup2}, we have $|B[V_1](x) - B[V_2](x)|\le \gamma \| V_1 - V_2\|_\infty,\ \textrm{for all }x$.
This yields that
$\| B[V_1] - B[V_2] \|_\infty\le \gamma \| V_1 - V_2 \|_\infty$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{lemma:continuity}]
Define
\begin{align}\small
    P(\mathbf{u},\mathbf{d},t,x) \coloneqq \min\{ \gamma^t r(\xi_x^{\mathbf{u},\mathbf{d}}(t)), \min_{\tau=0,...,t} \gamma^\tau c(\xi_x^{\mathbf{u},\mathbf{d}}(\tau)) \}.
\end{align}

Consider two initial states $x_1,x_2\in\mathbb{R}^n$.
Given $\epsilon>0$, there exists a non-anticipative strategy $\bar{\phi}$ such that
\begin{align}\small
    V(x_1) \geq \sup_\mathbf{u} \sup_t P(\mathbf{u},\bar{\phi}(\mathbf{u}), t,x_1) - \epsilon.
    \label{eq:pf_lma_cont_eq1}
\end{align}
We select a control sequence $\bar{\mathbf{u}}$ and time $\bar{t}$ such that
\begin{align}\small
    V(x_2) \leq  P(\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}}), \bar{t},x_2) + \epsilon.
    \label{eq:pf_lma_cont_eq2}
\end{align}
Moreover, \eqref{eq:pf_lma_cont_eq1} implies that
\begin{align}\small
    V(x_1) \geq  P(\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}}), \bar{t},x_1) - \epsilon.
    \label{eq:pf_lma_cont_eq3}
\end{align}
By combining \eqref{eq:pf_lma_cont_eq2} and \eqref{eq:pf_lma_cont_eq3}, we obtain
\begin{equation}\small
\begin{aligned}
    V(x_1)  - V(x_2 ) + &2\epsilon \geq P(\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}}), \bar{t},x_1) - P(\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}}), \bar{t},x_2) \\

    \geq & \min\{ \gamma^{\bar{t}} (r(\xi_{x_1}^{\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}})}(\bar{t}))-r(\xi_{x_2}^{\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}})}(\bar{t}))),\\
    &\min_{\tau=0,...,\bar{t}} \gamma^\tau (c(\xi_{x_1}^{\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}})}(\bar{t})) - c(\xi_{x_2}^{\bar{\mathbf{u}},\bar{\phi}(\bar{\mathbf{u}})}(\bar{t}))) \}.
\end{aligned}
\label{eq:pf_lma_cont_eq4}
\end{equation}
The last inequality is due to the fact that for any finite values $a_i,b_i\in \mathbb{R}$ ($i=1,...,n$), we have
\begin{align}\small
\begin{split}
    \min\{a_1,...,a_n\}&-\min\{b_1,...,b_n\} \geq \min\{a_1-b_1,...,a_n-b_n\}.
\end{split}
\label{eq:pf_lma_cont_eq5}
\end{align}
According to the Lipscthiz-continuity assumptions,
\begin{align}\small
\begin{split}
    & \|\xi_{x_1}^{\mathbf{u},\mathbf{d}}(t) - \xi_{x_2}^{\mathbf{u},\mathbf{d}}(t)  \| \leq L_f^t\|x_1-x_2\|, \\
    & \|c(\xi_{x_1}^{\mathbf{u},\mathbf{d}}(t)) - c(\xi_{x_2}^{\mathbf{u},\mathbf{d}}(t))  \| \leq L_c L_f^t\|x_1-x_2\|, \\
    & \|r(\xi_{x_1}^{\mathbf{u},\mathbf{d}}(t)) - r(\xi_{x_2}^{\mathbf{u},\mathbf{d}}(t))  \| \leq L_r L_f^t\|x_1-x_2\|.
\end{split}
\end{align}
Thus, it follows from \eqref{eq:pf_lma_cont_eq4} that
\begin{align}\small
\begin{split}
    V&(x_1)  - V(x_2 ) + 2\epsilon  \\
    &\geq-\max\{ L_r \gamma^{\bar{t}}L_f^{\bar{t}}, \max_{\tau=0,...,\bar{t}} L_c \gamma^{\tau}L_f^{\tau } \} \|x_1-x_2\|.
\end{split}
\label{eq:pf_lma_cont_eq55}
\end{align}
The condition $\gamma L_f <1$ implies that the coefficient in the right-hand side in \eqref{eq:pf_lma_cont_eq55} is bounded for all $\bar{t}$. As a result, $   V(x_1)  - V(x_2 ) + 2\epsilon \geq -C \|x_1-x_2\|
$
for some $C>0$. Similarly, we can show that $
    V(x_2)  - V(x_1 ) + 2\epsilon \geq -C \|x_1-x_2\|.
$
Combining these two inequalities, we prove Theorem \ref{lemma:continuity}.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{theorem:pure_safe}]
The non-positivity of $V(x)$ is due to $r(x)=-1$, for all $x$. We then show that $V(x)=0$ if and only if $x\in\Omega (\bar{\mathcal{C}})$.

(Sufficiency) On one hand, suppose that for all $\phi\in\Phi$, there exists a sequence of control inputs $\mathbf{u}=\{u_t\}_{t=0}^\infty$ under which $c(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(t))\ge 0$, $\forall t\in\{0,1,\dots\}$. Then, for all $\phi\in\Phi$,\vspace{-0.15cm}
\begin{equation*}\small
    \begin{aligned}
    V(x)& \ge \max_{\{u_t\}_{t=0}^\infty} \sup_{t=0,1,\dots} \min\big\{ -\gamma^t , \min_{\tau = 0,\dots, t} \gamma^\tau c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(\tau)) \big\}\\
    & \ge \max_{\{u_t\}_{t=0}^\infty} \min\big\{ -\gamma^t, \min_{\tau = 0,\dots,t}\gamma^\tau c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(\tau)) \big\}\big|_{t=\infty}=0.
    \end{aligned}\vspace{-0.15cm}
\end{equation*}
On the other hand, \vspace{-0.15cm}
\begin{equation*}\small
    \begin{aligned}
    V(x)&\le \inf_{ \phi } \max_{\{u_t\}_{t=0}^\infty}\sup_{t=0,1,\dots} \min\big\{ 0, \min_{\tau=0,\dots,t}\gamma ^{\tau}c(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(\tau)) \big\}\\
    & \le \inf_\phi \max_{\{u_t\}_{t=0}^\infty }\sup_{t=0,1,\dots} 0= 0.
    \end{aligned}\vspace{-0.15cm}
\end{equation*}
Thus, $V(x)=0$ if for all $\phi\in\Phi$ there exists a sequence of control inputs $\{u_t\}_{t=0}^\infty$ such that $ c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(t))\ge 0$, $\forall t\in\{0,1,\dots\}$.\\
(Necessity) We approach the proof by a contrapositive statement. Suppose that for every $\phi\in\Phi$ and every sequence of control inputs $\mathbf{u}$, there exists a non-negative integer $t_{\phi,\mathbf{u}}$ such that $c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(t_{\phi,\mathbf{u}}))< 0$. Then, we have\vspace{-0.15cm}
\begin{equation*}\small
    \begin{aligned}
    V(x)
    & \le \max_{\mathbf{u}} \sup_{t=t_{\phi,\mathbf{u}},t_{\phi,\mathbf{u}}+1,\dots} \min\{-\gamma^t , \gamma^{t_{\phi,\mathbf{u}}} c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(t_{\phi,\mathbf{u}}))\}\\
    & = \max_{\mathbf{u}} \gamma^{t_{\phi,\mathbf{u}}} c(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(t_{\phi,\mathbf{u}}))<0.
    \end{aligned}\vspace{-0.15cm}
\end{equation*}
This completes the proof.
\end{proof}
\begin{proof}[Proof of Proposition~\ref{theorem:pure_reach}]
The non-negativity of $V(x)$ is due to $c(x)=1$, for all $x$. Subsequently, it suffices to show that $V(x)>0$ if and only if there exists an $\epsilon>0$ such that, for all $\phi\in\Phi$, there exists a sequence of control inputs that renders $\gamma^t \xi_x^{\mathbf{u},\phi(\mathbf{u})}(t)>\epsilon$ and $\gamma^t>\epsilon$, for some non-negative integer $t$.

(Sufficiency) Suppose that there exists $\epsilon>0$ such that for all $\phi\in\Phi$ there exists a sequence of control inputs $\mathbf{u} = \{u_t\}_{t=0}^\infty$, $\gamma^{T_{\phi,\mathbf{u}}} r(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(T_{\phi,\mathbf{u}}))>\epsilon$, for some $T_{\phi,\mathbf{u}}\in\mathbb{Z}_+$. Then, we have\vspace{-0.15cm}
\begin{equation*}\small
    \begin{aligned}
    V(x)& = \inf_\phi \max_{\{u_t\}_{t=0}^\infty} \sup_{t=0,1,\dots} \min\big\{ \gamma^t r(\xi_x^{\mathbf{u},\phi(\mathbf{u})}(t)),\gamma^t \big\}\\
    & \ge \inf_{\phi} \max_{\{u_t\}_{t=0}^\infty} \epsilon\ge \epsilon.
    \end{aligned}\vspace{-0.15cm}
\end{equation*}
(Necessity) We approach the proof by a contrapositive statement. Suppose that for all $\epsilon>0$ there exist $\hat{\phi}$ such that for every sequence of control inputs $\mathbf{u} = \{u_t\}_{t=0}^\infty$, it holds that $\gamma^t r(\xi_{x}^{\mathbf{u},\hat{\phi}(\mathbf{u})}(t))\le \epsilon$ or $\gamma^t\le \epsilon$, $\forall t\in\mathbb{Z}_+$. Then, we have\vspace{-0.15cm}
\begin{equation*}\small
    \begin{aligned}
    V(x) & \le \max_{\{u_t\}_{t=0}^\infty} \sup_{t=0,1,\dots} \min\big\{ \gamma^t r(\xi_x^{\mathbf{u},\hat{\phi}(\mathbf{u})}(t)),\gamma^t \big\}\\
    & \le \sup_{\{u_t\}_{t=0}^\infty} \sup_{t=0,1,\dots}\epsilon\le \epsilon.
    \end{aligned}\vspace{-0.15cm}
\end{equation*}
Since the above ienquality holds true for all $\epsilon>0$, we have $V(x)\le 0$. This completes the proof.
\end{proof}

\begin{lemma}\label{lem:inequality_minimax}
Consider two functions $g(\cdot):\mathbb{R}\to\mathbb{R}$ and $\bar{g}(\cdot):\mathbb{R}\to\mathbb{R}$. Suppose that $g(a,b)\le \bar{g}(a,b)$, $\forall a,b$. Then, we have $\max_a\min_b g(a,b) \le \max_a \min_b \bar{g}(a,b)$.
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{thm:sandwidch}]
Let $V^{(0)}(\cdot):\mathbb{R}^n\to \mathbb{R}$ be an arbitrary bounded function. Consider the value iteration:
\begin{equation}\small
\begin{aligned}
    V^{(k+1)}(x) = B[V^{(k)}](x),\  \forall k\in\mathbb{Z}_+.
\end{aligned}
\end{equation}
Let $V^{(0)}_{CQL}:\mathbb{R}^n\to \mathbb{R}$, and consider the CQL-based value iteration:
\begin{equation}\small
    V_{CQL}^{(k+1)}(x) = B_{CQL}[V_{CQL}^{(k)}](x),\ \forall k\in\mathbb{Z}_+.
\end{equation}
Suppose that $V_{CQL}^{(0)}(x) =V^{(0)}(x),\forall x\in\mathbb{R}^n$. It suffices to show that\vspace{-0.3cm}
\begin{equation}\small
    V^{(k)}(x)-\sum_{i=1}^k \gamma^i \lambda \le V_{CQL}^{(k)}(x) \le V^{(k)}(x)-\lambda,\ \forall x\in\mathbb{R}^n,
\end{equation}
because by taking the limit $k\to \infty$, we have\vspace{-0.2cm}
\begin{equation}\small
    \lim_{k\to \infty} V(x) - \frac{\lambda}{1-\gamma}\le V_{CQL}(x)\le V(x)-\lambda, \forall x\in\mathbb{R}^n.
\end{equation}
To this end, we first show the upper bound $V_{CQL}^{(k)}(x)\le V^{(k)}(x) - \lambda$ by induction. From \eqref{eq:CQL_Bellman_backup}, we have\vspace{-0.2cm}
\begin{equation}\label{eq:first_induction_cql_proof}\small
    V_{CQL}^{(1)}(x) = B[V^{(0)}](x)-\lambda\le V^{(1)}(x)-\lambda,\forall x\in\mathbb{R}^n.
\end{equation}
Therefore,\vspace{-0.1cm}
\begin{equation*}\small
\begin{aligned}
    V_{CQL}^{(2)}(x) \le &\min\big\{ c(x), \max\{r(x), \gamma \max_u\min_d V^{(1)}(f(x,u,d))\} \big\}-\lambda\\
    \le&V^{(2)}(x)-\lambda,
\end{aligned}
\end{equation*}
where we substitute \eqref{eq:first_induction_cql_proof} into the CQL Bellman backup \eqref{eq:CQL_Bellman_backup} of the $V_{CQL}^{(2)}(x)$ and also use the inequality in Lemma \ref{lem:inequality_minimax}. By induction, we have $V_{CQL}^{(k)}\le V^{(k)}-\lambda,\forall x\in\mathbb{R}^n.$ Similarly, we show the lower bound $V_{CQL}^{(k)}(x)\ge V^{(k)}(x) - \sum_{i=1}^k \gamma^i \lambda$ as follows. Since $V_{CQL}^{(1)}(x) \ge V^{(1)}-\lambda$, we have\vspace{-0.2cm}
\begin{equation*}\small
\begin{aligned}
    V_{CQL}^{(2)}(x)\ge& \min\big\{ c(x),\max\{r(x), \\ &\gamma \max_u \min_d (V^{(1)}(f(x,u,d))-\lambda)\} \big\}-\lambda\\
    \ge & \min\big\{c(x)-\gamma \lambda, \max \{ r(x) - \gamma \lambda, \\ &\gamma \max_u \min_d V^{(1)}(f(x,u,d)) - \gamma \lambda \}\big\}-\lambda\\
    =&V^{(2)}(x)-\gamma \lambda - \lambda.
\end{aligned}
\end{equation*}\vspace{-0.1cm}
By induction, we have $V^{(k)}-\sum_{i=1}^k \gamma^i \lambda \le V_{CQL}^{(k)}(x)$.
\end{proof}

\section{Conclusion}
\label{sec:conclusion}
In this paper, we investigated the infinite-horizon reach-avoid zero-sum game problem, in which the goal is to learn the reach-avoid set in the state space and an associated policy such that each state in the reach-avoid set could be driven towards a given target set while satisfying constraints. We designed a value function that offers several properties: 1) its super-zero level set coincides with the reach-avoid set and the induced Bellman Backup equation is a contraction mapping; 2) the value function is Lipschitz continuous under certain conditions; and 3) the value function can be adapted to compute the viability kernel and backward reachable set.
We proposed to alleviate the curse of dimensionality issue by developing a deep RL algorithm. The provided theoretical and empirical results suggest that our method is able to learn reach-avoid sets reliably even with neural network approximation errors.

\section{Experiments}\label{sec:experiments}
In this section, we present experiments on Algorithm~\ref{alg:DQN} and show that our method could learn a (conservative) approximation to the reach-avoid set reliably even with neural network approximation.

\subsection{2D Experiment for Reach-Avoid Game}\label{sec:2d_experiment}
In this experiment, we compare the reach-avoid set learned by Algorithm~\ref{alg:DQN} with the one learned by tabular Q-learning, where we first grid the continuous state space and then run value iteration \eqref{eq:bellman_backup} over the grid. We treat the reach-avoid set learned by tabular Q-learning as the ground truth solution. We apply Algorithm~\ref{alg:DQN} to learn neural network Q functions with $4$ hidden layers, where each hidden layer has 128 neurons with ReLu activation functions. This neural network architecture is chosen because empirically it provides sufficient model capacity for approximating the true value function.

Let the target set and constraint set be $\mathcal{T}=\{(x,y)\in\mathbb{R}^2: 1-(x^2+y^2)>0\}$ and $\mathcal{C} = \{(x,y)\in\mathbb{R}^2: 1-\frac{(x-2)^2}{1.5^2} - y^2>0 \}$, respectively. We visualize the target set $\mathcal{T}$ and the constraint set $\mathcal{C}$ in Figure \ref{fig:2d_target_constraint}. Consider the following discrete-time double integrator dynamics, with the time constant $\Delta t = 0.02s$:
\begin{figure}[t]
    \centering
    \includegraphics[clip, trim = 5cm 10.5cm 5cm 10.5cm, width =0.3\textwidth]{plots/2d_target_constraint.pdf}
    \caption{The target set and the constraint set in the 2D experiment}
    \label{fig:2d_target_constraint}
\end{figure}

\begin{figure}[t]
\centering
\includegraphics[clip,trim = 0cm 9.8cm 0cm 9.8cm,width=0.5\textwidth]{plots/table_plot.pdf}
\caption{Comparison of the 2D reach-avoid set learned by tabular Q-learning and Algorithm~\ref{alg:DQN}. The yellow area corresponds to the reach-avoid set.}
\label{fig:DI}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[clip, trim = 3cm 7.7cm 2.6cm 7.7cm, width =0.35\textwidth]{plots/6d_target_constraint.pdf}
    \caption{The avoidance area and the target area in the three-cart reach-avoid zero-sum game experiment}
    \label{fig:6d_target_constraint}
\end{figure}

\begin{figure}[h!]
    \centering
    \includegraphics[clip,trim = 1cm 9.2cm 1cm 9cm,width=0.5\textwidth]{plots/DI_3_table_plots.pdf}
    \caption{Visualization of reach-avoid sets under different CQL penalty weights $\lambda$, with $[x_2,v_2,x_3,v_3]=[-1,1,1, -1]$. In the first row, the yellow area represents the reach-avoid set. In the second row, we plot the value of each point in the corresponding plots in the first row.}
    \label{fig:DI_3}
\end{figure}

\begin{figure}[h!]
    \centering
    \includegraphics[clip, trim = 1cm 11.4cm 1cm 11.5cm, width = 0.5\textwidth]{plots/DI_3_policy.pdf}
    \caption{The control and disturbance policies extracted from the neural network value function learned by Algorithm \ref{alg:DQN} with $\lambda = 0.0$. The other four states are $[x_2,v_2,x_3,v_3] = [-1,1,1,-1]$. The yellow and blue areas in the left plot correspond to the control inputs with the values 1 and -1, respectively. The yellow and blue ares in the right plot correspond to the disturbances with the values $0.5$ and $-0.5$, respectively.}
    \label{fig:policy}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[clip, trim = 0cm 11.6cm 0cm 11.6cm, width = 0.5\textwidth]{plots/DI_3_VK_plot.pdf}
    \caption{Visualization of the learned viability kernel, with $[x_2,v_2,x_3,v_3]=[1,1,-1,1]$. In the second subplot, the yellow area is the viability kernel. In the third subplot, the yellow and blue areas correspond to the control inputs $1$ and $-1$, respectively. In the fourth subplot, the yellow and blue areas correspond to the disturbances $0.5$ and $-0.5$, respectively.
    \label{fig:VK}
\end{figure}
\begin{figure}[h!]
    \centering
    \includegraphics[clip, trim = 0cm 11.6cm 0cm 11.6cm, width = 0.5\textwidth]{plots/DI_3_BRS_plot.pdf}
    \caption{Visualization of the learned backward reachable set, with $[x_2,v_2,x_3,v_3]=[0.6,0.0,0.7,0.1]$. In the second subplot, the yellow area is the backward reachable set. In the third subplot, the yellow and blue areas correspond to the control actions $1$ and $-1$, respectively. In the fourth subplot, the yellow and blue areas correspond to the disturbance action $0.5$ and $-0.5$, respectively.
    \label{fig:BRS}
\end{figure}

\begin{equation}\label{eq:2d_dynamics}
    \begin{bmatrix}
    x(t+1)\\    y(t+1)
    \end{bmatrix} = \begin{bmatrix}
    x(t) + \Delta t\cdot y(t)\\ y(t) + \Delta t\cdot (u(t) + d(t))
    \end{bmatrix}
\end{equation}
where $x(t)$ and $y(t)$ are the position and velocity, respectively. The $u(t)\in\{-1,1\}$ and $d(t)\in\{-0.5,0.5\}$ are the control action and disturbance at time $t\in\{0,1,2,\dots\}$, respectively.

We see in Figure~\ref{fig:DI} that the reach-avoid set learned by Algorithm \ref{alg:DQN} is similar to the one computed by tabular Q-learning. An interesting observation is that, under different time-discount factors, the reach-avoid sets computed by tabular Q-learning are somewhat different. This could potentially be due to the numerical difficulty introduced by small values of $\gamma$. To be more specific, from the definition of the value function \eqref{eq:inf_horizon_reach_avoid_problem}, we see that the powers of small constant $\gamma\in[0,1)$ decays to 0 faster than those for a large parameter $\gamma\in[0,1)$, and this makes it difficult to distinguish zero from the product of the power of a small constant $\gamma$ and a bounded function term. Despite this numerical difficulty, it can be observed that both tabular Q-learning and Algorithm \ref{alg:DQN} learn similar reach-avoid sets under different time-discount factors $\gamma\in[0,1)$.

In addition, as we increase the CQL penalty $\lambda$, the reach-avoid set shrinks to a conservative subset of the true reach-avoid set in both tabular Q-learning and Algorithm~\ref{alg:DQN}. For the same $\lambda$, although subject to certain numerical errors, both of these methods yield similar results, which empirically supports Theorem \ref{thm:sandwidch}.

\subsection{6D Experiment for Reach-Avoid Game}\label{sec:6d experiment}
In this experiment, we consider a three-cart dynamical system, where the dynamics of each cart is modeled as a double integrator. The carts move along different axes. The first cart with the position $x_1(t)$ and velocity $v_1(t)$ moves vertically, while the second and the third carts move along the upper and the lower horizontal lines in Figure \ref{fig:6d_target_constraint}, respectively.

The task is to drive the first cart towards the yellow region in Figure~\ref{fig:6d_target_constraint} while keeping the distance between every two cars at least $2$. The target and the constraint sets can then be formulated as $\mathcal{T} = \{x\in\mathbb{R}^6: 2-|x_1|>0 \}$ and $\mathcal{C} = \{x\in\mathbb{R}^6: \min\{(x_1-2)^2+x_2^2, (x_1+2)^2+x_3^2 \}-4>0\}$, respectively. The dynamics is
\begin{equation}\label{eq:experiment 6d dynamics}
    \begin{aligned}
    \begin{bmatrix}
    x_1(t+1)\\v_1(t+1)\\x_2(t+1)\\v_2(t+1)\\x_3(t+1)\\v_3(t+1)
    \end{bmatrix} = \begin{bmatrix}
    x_1(t) + \Delta t\cdot v_1(t)\\v_1(t) + \Delta t \cdot (u_t+d_t)\\x_2(t) + \Delta t\cdot v_2(t)\\ v_2(t) + 0.02\Delta t\\ x_3(t) + \Delta t\cdot v_3(t)\\v_3(t) +0.02 \Delta t
    \end{bmatrix}
    \end{aligned}
\end{equation}
where $u_t\in\{-1,1\}$ and $d_t\in \{-0.5,0.5\}$ are the control input and disturbance, respectively. The time-integration constant $\Delta t $ is equal to $0.02 s$. The time-discount factor $\gamma$ is $0.99$.

Due to the curse of dimensionality, tabular Q learning explained in the previous experiment suffers numerical difficulties in this 6-dimensional experiment. In this subsection, we apply Algorithm~\ref{alg:DQN} with the same neural network architecture as in Section~\ref{sec:2d_experiment}. We plot the learned reach-avoid set by projecting it onto a 2-dimensional plane. In Figure~\ref{fig:DI_3}, we visualize the reach-avoid set as well as the effect of the CQL penalty $\lambda$ on the learned reach-avoid set. As the penalty $\lambda$ increases, the volume of the reach-avoid set shrinks while the empirical success rate improves. This suggests that a larger penalty $\lambda$ induces a more conservative estimation of the reach-avoid set and the policy.

We sample 1000 initial states in each of the three learned reach-avoid set in Figure \ref{fig:DI_3}, and then collect the trajectories with maximum length 1000 time steps, under the control and disturbance policies induced by the learned neural network value function. For the three learned value functions, the portion of those 1000 trajectories under each of the three values of $\lambda$ that successfully reach the target set without violating the constraints are $85.4\%$, $88.4\%$, and $91.3\%$. In addition, we randomly sample 10,000 points in the state space, and observe that the ratios of points lying in the learned reach-avoid sets for $\lambda=0.01$ and $\lambda=0.05$ to those for $\lambda = 0.0$ are $99.7\%$ and $82.5\%$, respectively. However, note that the training epochs taken to learn the three value functions are 1290, 1650, and 1470, respectively

In Figure~\ref{fig:policy}, we visualize the control and disturbance policies extracted from the Q function of the neural network corresponding to $\lambda=0.0$ in Figure~\ref{fig:DI_3}. The two policies are considered as to be reasonable because at most state, the control policy either drives the agent towards the target set or prevent the violation of the constraint.
Notice that there are a few states, e.g., some points at the right lower corner of the disturbance law in Figure \ref{fig:policy}, where they do not complement to each other. One possible reason is that we learn a local optimal neural network Q function by minimizing the non-convex loss function \eqref{eq:cql_loss}.

\subsection{6D Experiments on Learning Viability Kernel and Backward Reachable Set}
In this subsection, we apply Algorithm~\ref{alg:DQN} to learn viability kernel and backward reachable set for the 6-dimensional dynamical system in Subsection \ref{sec:6d experiment}. The results empirically confirm Propositions~\ref{theorem:pure_safe} and \ref{theorem:pure_reach}. In the following two experiments, the same neural network architecture as in Section~\ref{sec:6d experiment} does not yield satisfactory results and we conjecture that this is due to the limited model capacity. As such, in this subsection, we increase the model capacity by adopting 4-layer neural networks with 256 neurons in each layer. We set the CQL penalty parameter to be $\lambda=0.0$.

We first consider learning the viability kernel where the constraint set is the same as the one in Subsection~\ref{sec:6d experiment}. The reward function is set to be $r(x) = -1$, for all $ x\in\mathbb{R}^n$.
In the first subplot of Figure~\ref{fig:VK}, we visualize the learned value function.
The value function is non-positive, which is predicted by Proposition \ref{theorem:pure_reach}.
We visualize the learned viability kernel in the second subplot of Figure \ref{fig:VK}.
We sampled $1000$ initial positions in the learned viability kernel and simulated a trajectory for each of them with $600$ steps. The portion of those sampled points that can be maintained inside the constraint set is~$79.2\%$.

Subsequently, we consider learning a backward reachable set by leveraging Proposition \ref{theorem:pure_reach}, where the constraint function is set to be a constant function with the value $1$.
We consider the target set $\mathcal{T}=\{x\in\mathbb{R}^6:\min(2-|x_1|, 1-|x_2|,1-|x_3|)>0\}$. We visualize the learned value function and backward reachable set in Figure~\ref{fig:BRS}. As shown in Proposition \ref{theorem:pure_reach}, the value function is non-negative.
We sampled $1000$ points in the obtained backward reachable set. The portion of initial states that can be driven towards the target set within 600 simulation steps~is~$70.0\%$.

It is observed that the empirical success rate of viability kernel is higher than backward reachable set. There are multiple reasons behind it. First, the simulation horizon is not long enough for an initial state to be driven towards the backward reachable set. In addition, for backward reachable set, a single failure in control may push the trajectory away from the target set in the future. However, for viability kernel, multiple failures in control are allowed if controls at the boundary of the viability kernel keep the trajectory inside the constraint set.

We remark here that the high-dimensional experiments are challenging because there is a lack of efficient methods to check the sufficiency of neural network model capacity and solve the non-convex optimization problem \eqref{eq:cql_loss}, which are common problems but also active research areas in deep RL \cite{fan2020theoretical}.
\section{Introduction}
\label{sec:introduction}

Ensuring the safety and performance of autonomous systems is essential for safety-critical systems, such as autonomous driving \cite{muhammad2020deep}, surgical robots \cite{thananjeyan2020safety}, and air traffic control \cite{hwang2007protocol}.
Some safe control tasks could be modeled as driving the system's state to a target set in the state space while satisfying certain safety constraints \cite{bansal2017hamilton}. This is referred to as the \emph{reach-avoid} problem \cite{summers2011stochastic}. However, it is challenging to solve this problem under the presence of uncertainty \cite{dorato1987historical}, such as modeling errors and environmental disturbances. One way to accommodate this is to consider the reach-avoid problem under the worst-case scenario, which could be formulated as a zero-sum game between the control inputs and an adversary, accounting for the uncertainty or disturbance, with an objective to compromise the efforts of control inputs\cite{tomlin1998conflict}.

In the general case, this problem is challenging because it requires solving a zero-sum game with nonlinear dynamics, where the objective involves the worst-case performance instead of an average or cumulative performance over time, as in most constrained reinforcement learning (RL) papers \cite{achiam2017constrained,chow2017risk,altman1999constrained}. Moreover, no future constraint violation is considered once the state trajectory enters the target set in the reach-avoid zero-sum game. Since constrained RL aims to learn a policy satisfying constraints at all times, it can only learn a conservative sub-optimal policy for the reach-avoid zero-sum game.

A well-known approach to solving the reach-avoid zero-sum game is the Hamilton-Jacobi (HJ) method \cite{margellos2011hamilton,fisac2015reach}, in which one can design a value function such that the sign of the value function evaluated at a state encodes the safety and performance information of that state. In addition, reach-avoid games with multiple agents \cite{selvakumar2019feedback} and stochastic systems \cite{vidal2002probabilistic} have also been studied.
These methods provide a closed-loop control policy for the continuous-time and finite-horizon zero-sum game setting, where an agent is required to reach a target set safely within a given finite-time horizon.

However, there are two major limitations of existing work on HJ-based methods for finite-horizon reach-avoid games. Firstly, for complex or uncertain dynamical systems, it is difficult to predict a sufficient time horizon to guarantee the feasibility of the finite-time reach-avoid zero-sum game problem. This motivates the formulation of the infinite-horizon reach-avoid zero-sum game, where we remove the requirement of reaching the target set within a pre-specified finite horizon. The infinite-horizon reach-avoid game has been studied in only a few prior works. Among these is \cite{hsusafety}, in which the reach-avoid problem without an adversary player is considered. The authors introduce the time-discount factor, a parameter discounting the impact of future reward and constraints, to the design of a contractive Bellman backup such that by annealing the time-discount factor to 1 they can obtain the reach-avoid set. Empirical results in \cite{hsusafety} suggest the potential of this method in solving the infinite-horizon reach-avoid zero-sum~games.

A second limitation is the computational complexity of classical HJ-based methods, which are exponential in the dimension of the state space \cite{bansal2017safe}. Several approaches have been proposed in the literature to alleviate this. A line of work \cite{mitchell2008flexible,landry2018reach,singh2018robust} formulate the reach-avoid zero-sum games as polynomial optimization problems for which there is no need to grid the entire state space. Another line of work on system decomposition, that is, decomposing a high-dimensional control problem into low-dimensional problems, is also a promising direction \cite{chen2016exact,chen2018decomposition}.
\textcolor{black}{Underapproximation of the reach-avoid set is proposed in \cite{gleason2017underapproximation} and an efficient open-loop policy method is developed in \cite{zhou2012general}. }
Nevertheless, these approaches presume certain structural assumptions about the dynamical systems and costs, which restrict their applications

With the power of neural networks, deep RL has been proven to be a promising technique for high-dimensional optimal control tasks \cite{mnih2013playing,silver2014deterministic,haarnoja2018soft}, where a policy is derived to maximize the accumulated reward at each time step. It has been shown in \cite{munos1999gradient} that neural networks could be leveraged to approximate the value function in high-dimensional optimal control problems and therefore alleviate the curse of dimensionality of Hamilton-Jacobi reachability analysis. For example, sinusoidal neural networks is proven to be a good functional approximator for learning the value function of backward-reachable-tube problem for high-dimensional dynamical systems \cite{bansal2020deepreach}. A deep reinforcement learning-based method is proposed in \cite{fisac2019bridging} to learn a neural network value function for \emph{viability kernel}, the set of initial states from which a state trajectory could be maintained to satisfy pre-specified constraints. In particular, the paper \cite{fisac2019bridging} designs a contractive Bellman backup and learns a conservative approximation to the viability kernel. This method is further extended to solve infinite-horizon reach-avoid problem in \cite{hsusafety}.

In this paper, we propose a new HJ-based method for the infinite-horizon reach-avoid zero-sum game, and we develop a deep reinforcement learning method to alleviate the curse of dimensionality in solving it. Our contributions are threefold. We first propose a new value function for the reach-avoid zero-sum game, where the induced Bellman backup is a contraction mapping and ensures the convergence of value iteration to the unique fixed point. Subsequently, we analyze the designed value function by first proving its Lipschitz continuity, and then show that the new value function could be adapted to compute the viability kernel and the \emph{backward reachable set}, that is, the set of states from which a state trajectory could be controlled to reach the given target set. Finally, we alleviate the curse of dimensionality issue by proposing a deep RL algorithm, where we extend conservative Q-learning \cite{kumar2020conservative} to learn the value function of the infinite-horizon reach-avoid zero-sum game. We obtain upper and lower bounds for the learned value function. Our empirical results suggest that a (conservative) approximation of the reach-avoid set can be learned, even with neural network approximation.

Unlike the previous work \cite{hsusafety} where the value function is discontinuous in general and the reach-avoid set can only be obtained when the time-discount factor is annealing to 1, the proposed value function is Lipschitz continuous under certain conditions and can exactly recover the reach-avoid set without annealing the time-discount factor. The obtained reach-avoid set is agnostic to any time-discount factors in the interval $[0,1)$.
In addition, this new value function could be adapted to compute the viability kernel and backward reachable set, which constitutes a unified theoretical perspective on reachability analysis concepts such as reach-avoid set, viability kernel, and backward reachable set.

The rest of the paper is organized as follows.
In Section \ref{sec:problem_formulation}, we formulate the infinite-horizon reach avoid problem.
We present our main theoretical results in Sections \ref{sec:methods} - \ref{sec:pure_constraint_and_pure_target}, with proofs provided in the Appendix. In Section \ref{sec:experiments}, we illustrate our algorithm in multiple experiments. Finally, we conclude the paper in Section \ref{sec:conclusion}.

\section{A New Value Function for Infinite-horizon Reach-Avoid Games}
In this section, we address Problem~\ref{Reach_avoid_problem} by introducing a new Lipschitz continuous value function such that its sign evaluated at a state indicates whether that state can be driven to the target set without violating constraints. To be more specific, we will show that the \emph{super-zero level set} of the designed value function recovers the reach-avoid set in Problem~\ref{Reach_avoid_problem}. Subsequently, we derive a Bellman backup equation. The fixed-point iteration based on this Bellman backup equation induces a unique fixed point solution, which will be proven to be the designed value function \eqref{eq:inf_horizon_reach_avoid_problem}. Finally, we will show that the designed value function is Lipschitz continuous, which is a favorable property for HJ analysis \cite{basco2019lipschitz}.

Suppose that a state trajectory reaches a target set $\mathcal{T}$ at time $t$, i.e., $\xi_{x}^{\mathbf{u,d}}(t)\in\mathcal{T}$, while being maintained within the constraint set $\mathcal{C}$ for all $\tau \in\{0,1,\dots ,t\}$ under an arbitrary sequence of disturbances $\mathbf{d}=\{d_t\}_{t=0}^\infty$. Let $\gamma\in[0,1)$ be the time-discount factor, which discounts the impact of future reward and constraints. We observe that such a sequence of control inputs $\mathbf{u} = \{u_t\}_{t=0}^\infty$ should satisfy
\begin{equation*}
\begin{aligned}
    \max_{u_0}\min_{d_0}&\max_{u_1}\min_{d_1}\cdots \max_{u_t}\min_{d_t} \min \big\{ \gamma^t r(\xi_{x}^{\mathbf{u,d}}(t)), \\ &\min_{\tau=0,\dots, t} \gamma^{\tau} c(\xi_{x}^{\mathbf{u,d}}(\tau)) \big\}>0.
\end{aligned}
\end{equation*}
Therefore, to verify the existence of a sequence of control inputs driving the state trajectory to the target set safely from an initial state $x_0$, it suffices to check the sign of the following term:
\begin{equation}\label{eq:inf_time_check_finite_time}
    \begin{aligned}
        \max_{u_0}\min_{d_0}\max_{u_1}&\min_{d_1}\dots \sup_{t=0,\dots} \min\big\{ \gamma^t r(\xi_{x}^{\mathbf{u,d}}(t)),\\& \min_{\tau = 0,\dots,t}\gamma^\tau c(\xi_{x}^{\mathbf{u,d}}(\tau)) \big\}.
    \end{aligned}
\end{equation}
\begin{comment}
\textcolor{blue}{Instead of using this strategy, I suggest
\begin{align*}
    \max_{u_0}\min_{d_0}\max_{u_1}\min_{d_1}\dots \max_{t=0,\dots, \infty} \min\big\{ \gamma^t r(\xi_{x}^{\mathbf{u,d}}(t)), \min_{\tau = 0,\dots,t}\gamma^\tau c(\xi_{x}^{\mathbf{u,d}}(\tau)) \big\} \\
    = \left(\prod_{t=0}^\infty \max_{u_t}\min_{d_t}\right) \max_{t=0,\dots, \infty} \min\big\{ \gamma^t r(\xi_{x}^{\mathbf{u,d}}(t)), \min_{\tau = 0,\dots,t}\gamma^\tau c(\xi_{x}^{\mathbf{u,d}}(\tau)) \big\}.
\end{align*}
}
\end{comment}
By using the notion of the non-anticipative strategy $\phi$, we can simplify \eqref{eq:inf_time_check_finite_time} to the term
\begin{equation*}
\begin{aligned}
    \inf_{\phi}\max_{\mathbf{u}}&\sup_{t=0,\dots, } \min \big\{ \gamma^t r(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(t)), \min_{\tau=0,\dots, t} \gamma^{\tau} c(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(\tau)) \big\}.
\end{aligned}
\end{equation*}
This implies that a new value function for Problem~\ref{Reach_avoid_problem} can be defined~as
\begin{equation}\label{eq:inf_horizon_reach_avoid_problem}
\begin{aligned}
    V(x) := \inf_{\phi} &\max_{\mathbf{u}} \sup_{t=0,\dots} \min \big\{ \gamma^t r(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(t)) ,\\& \min_{\tau=0,\dots,t} \gamma^{\tau} c(\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(\tau)) \big\},\ \forall x\in\mathbb{R}^n.
\end{aligned}
\end{equation}
The sign of the value function  encodes some crucial safety information about each state, that is, whether the state could be driven towards the target set while satisfying the given constraints. More precisely, $V(x)>0$ if for every disturbance strategy $\phi$, there exist $\mathbf{u}=\{u_t\}_{t=0}^\infty$ and $T<\infty$ such that $\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(T)\in\mathcal{T}$ and $\xi_{x}^{\mathbf{u},\phi(\mathbf{u})} (t)\in\mathcal{C}$ for all $ t\in[0,T]$. Based on this intuition, we characterize the relationship between the super-zero level set of the value function~\eqref{eq:inf_horizon_reach_avoid_problem} and the reach-avoid set next.

\begin{theorem}\label{thm:V>0}
Consider the value function $V(x)$ defined in \eqref{eq:inf_horizon_reach_avoid_problem}. For every $\gamma\in[0,1)$, it holds that
$\{x\in\mathbb{R}^n:V(x)>0\} = \mathcal{RA(T,C)}$.
\end{theorem}

We propose to compute the value function \eqref{eq:inf_horizon_reach_avoid_problem} using dynamic programming. To this end, a contractive Bellman backup will be derived below.
\label{sec:methods}

\begin{theorem}\label{thm:Bellman}
Let $\gamma\in[0,1)$ be the time-discount factor. Suppose $U:\mathbb{R}^n\to\mathbb{R}$ is a bounded function. Consider the Bellman backup $B[\cdot] $ defined as,
\begin{equation}\label{eq:bellman_backup}
\begin{aligned}
    B[U](x) \coloneqq &\min\big\{ c(x), \max\{ r(x), \gamma \max_u \min_{d} U(f(x,u,d)) \}\big\}.
\end{aligned}
\end{equation}
Then, \eqref{eq:inf_horizon_reach_avoid_problem} is the unique solution to the Bellman backup equation, i.e., $V=B[V]$,
and $    \|B[V_1] - B[V_2]\|_\infty \le \gamma \| V_1-V_2 \|_\infty$, for all bounded functions $V_1$ and $V_2$.
\end{theorem}

With the Bellman backup \eqref{eq:bellman_backup}, we define the \emph{value iteration} as the following recursion, starting from an arbitrary bounded function $V^{(0)}(\cdot):\mathbb{R}^n \to \mathbb{R}$,
\begin{equation}\label{eq:value_iteration}
V^{(k+1)} := B[V^{(k)}],\  \forall k\in\mathbb{Z}_+.
\end{equation}
Since the fixed-point iteration based method using a contraction mapping $B$ will guarantee the convergence to a fixed point within that bounded function space, the Bellman backup \eqref{eq:bellman_backup} ensures the convergence of value iteration to \eqref{eq:inf_horizon_reach_avoid_problem}, i.e., $\lim_{k\to \infty}V^{(k)} = V$.

Once we obtain the value function \eqref{eq:inf_horizon_reach_avoid_problem}, we can calculate the following Q function:
\begin{equation}\label{eq:Q}
    Q(x,u,d) \coloneqq \min\big\{ c(x), \max \{r(x), \gamma V(f(x,u,d))\} \big\},
\end{equation}
where $V(x) = \max_u\min_d Q(x,u,d)$. Given a state $x\in\mathbb{R}^n$, we can find an optimal control input and disturbance by $u^* = \max_u \min _d Q(x,u,d)$ and $d^*=\min_d Q(x,u,d)$, respectively. This provides a way to extract the optimal control and worst-case disturbance for Problem \ref{Reach_avoid_problem}. Therefore, the proposed value function \eqref{eq:inf_horizon_reach_avoid_problem} constitutes a solution to Problem~\ref{Reach_avoid_problem} in the sense that one can find the reach-avoid set, the optimal sequence of control inputs, and the worst-case sequence of disturbances.

In what follows, we characterize the Lipschitz continuity of the proposed value function \eqref{eq:inf_horizon_reach_avoid_problem}. We show that the Lipschitz continuity of the value function \eqref{eq:inf_horizon_reach_avoid_problem} could be ensured under certain conditions on the dynamics and the time-discount factor.

\begin{theorem}[Lipschitz continuity]\color{black}
Suppose that the bounded functions $r(\cdot)$ and $c(\cdot)$ are $L_r$- and $L_c$-Lipschitz continuous, respectively. Assume also that the dynamics $f(x,u,d)$ is $L_f$-Lipschitz continuous in $x$, for all $u\in\mathcal{U}$ and $d\in\mathcal{D}$. Let $L:= \max(L_r,L_c)$. Then, $V(x)$ is $L$-Lipschitz~continuous~if~$L_f \gamma <1$.
\label{lemma:continuity}
\end{theorem}
\begin{remark}
It is known that the sample complexity of neural network approximation could be improved if the function to be approximated is continuous \cite{gouk2021regularisation}. Therefore, the Lipschitz continuity of the value funtion \eqref{eq:inf_horizon_reach_avoid_problem} is a beneficial property yielding reliable empirical performance when we deploy neural networks approximation to handle curse of dimensionality as highlighted in Section~\ref{sec:6d experiment}.
\end{remark}

\section{Computing the Viability Kernel and the Backward Reachable Set}\label{sec:pure_constraint_and_pure_target}
In this section, we show that the designed value function \eqref{eq:inf_horizon_reach_avoid_problem} can be adapted to compute the viability kernel \cite{fisac2019bridging} and the backward reachable set \cite{bansal2020deepreach}. We first present the formal definitions of these notions below.

We adopt the same definition of viability kernel as in \cite{fisac2019bridging}, where the \emph{viability kernel} is defined with respect to a closed set $\bar{\mathcal{C}}=\{x\in\mathbb{R}^n: c (x)\ge 0\}$, i.e., the closure of the constraint set $\mathcal{C}$, as
\begin{equation*}
    \Omega(\mathcal{\bar{C}}):=\{x\in\mathbb{R}^n:\forall \phi\in\Phi , \exists \mathbf{u} , \textrm{s.t., }\xi_{x}^{\mathbf{u},\phi (\mathbf{u})}(t)\in \mathcal{\bar{C}},\forall t\ge 0  \},
\end{equation*}
which contains all states $x$ from which a state trajectory $\xi_x^{\mathbf{u},\phi(\mathbf{u})}$ can be drawn such that $\xi_{x}^{\mathbf{u},\phi(\mathbf
{u})}(t)\in\bar{\mathcal{C}}$, $\forall t>0$. This set is of importance when the control task is to make the system satisfy some safety-critical constraints in real-world applications \cite{fisac2019bridging}.

The \emph{backward-reachable set} \cite{bansal2020deepreach} of a target set $\mathcal{T}=\{x\in\mathbb{R}^n: r(x)>0\}$ is defined as
\begin{equation*}
\begin{aligned}
    \mathcal{R(T)} := \{ x\in\mathbb{R}^n: &\forall \phi\in\Phi,\exists \mathbf{u}, \exists t \ge 0,\textrm{s.t., } \xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(t)\in\mathcal{T}\},
\end{aligned}
\end{equation*}
which includes all states that can be driven towards the target set $\mathcal{T}$ in finite time. The backward reachable set is a useful concept in reachability analysis \cite{bansal2020deepreach} because it specifies the set of states that can be controlled to reach a given target set. For instance, if an airplane is in the backward reachable set of another one, then it indicates that the two planes could collide with each other if they are not properly controlled.

In what follows, we show how the value function \eqref{eq:inf_horizon_reach_avoid_problem} can be adapted to compute the viability kernel and backward-reachable set.

\begin{proposition}\label{theorem:pure_safe}
Assume that $r(x)=-1$ for all $ x\in\mathbb{R}^n$. It holds that $V(x)\le 0$ for all $ x\in\mathbb{R}^n$. In addition, $V(x)=0$ if and only if $x\in\Omega(\mathcal{\bar{C}})$.
\end{proposition}%

\begin{remark}
The value function in Proposition \ref{theorem:pure_safe} could serve as a control barrier function \cite{ames2016control}, from which we can derive a policy keeping the system states within a given set of the state space.
\end{remark}

Similarly, we can compute the backward-reachable set by substituting particular constraint functions into \eqref{eq:inf_horizon_reach_avoid_problem}.

\begin{proposition}\label{theorem:pure_reach}
Assume that $c(x)=1$ for all $x\in\mathbb{R}^n$. It holds that $V(x)\ge 0$ for all $x\in\mathbb{R}^n$. In addition, $V(x) >  0$ if and only if $x\in \mathcal{R(T)}$.
\end{proposition}

Given the above results, our method provides a new theoretical angle to computing the reach-avoid set, viability kernel, and backward reachable set for infinite-horizon games, where a common value function \eqref{eq:inf_horizon_reach_avoid_problem} can be adaptively used to compute multiple important sets for safety-critical analysis.

\section{A Deep Reinforcement Learning Algorithm}
In this section, we develop a deep RL algorithm, which alleviates the curse of dimensionality issue for high dimensional problems. In particular, since the satisfaction of given safety constraints is vital for safety-critical systems, we propose to extend conservative Q-learning (CQL) \cite{kumar2020conservative} to Problem \ref{Reach_avoid_problem} and develop a deep RL algorithm for solving it, where the conservatism is favorable due to the neural network approximation error. More precisely, we learn a value function parameterized by a neural network which in theory is a lower bound of the value function \eqref{eq:inf_horizon_reach_avoid_problem}. The super-zero level set of the converged value function in CQL is a subset of $\mathcal{RA(T,C)}$, i.e., a conservative approximation of $\mathcal{RA(T,C)}$

The reason why CQL manages to learn a value function lower bound \eqref{eq:inf_horizon_reach_avoid_problem} is that CQL minimizes not only the Bellman backup error but also the value function itself at each iteration \cite{kumar2020conservative}.
Since the super-zero level set of the value function \eqref{eq:inf_horizon_reach_avoid_problem} is the reach-avoid set $\mathcal{RA(T,C)}$, the super-zero level set of a function that is a lower bound of \eqref{eq:inf_horizon_reach_avoid_problem} is a subset of $\mathcal{RA(T,C)}$

Similar to prior works on Deep RL \cite{mnih2013playing,silver2014deterministic,kumar2020conservative}, we approximate the Q function \eqref{eq:Q} by a neural network $Q_\theta(x,u,d):\mathbb{R}^n\times \mathcal{U}\times \mathcal{D}\to \mathbb{R} $, where $\theta\in\mathbb{R}^M$ is the vector of parameters of the neural network and $M$ is the total number of parameters. {We define the neural network value function as $V_\theta(x) := \max_u\min_d Q_\theta(x,u,d)$, $\forall x\in\mathbb{R}^n$.} We adopt the CQL framework \cite{kumar2020conservative} to learn the value function \eqref{eq:inf_horizon_reach_avoid_problem} by replacing the Bellman backup therein with \eqref{eq:bellman_backup}. With $\lambda\ge 0$, we extend the loss function in \cite{kumar2020conservative} to the reach-avoid zero-sum game setting and propose the following loss function $L(\theta):\theta\in\mathbb{R}^M \to\mathbb{R} $ for the neural network parameters:
\begin{equation}\label{eq:cql_loss}
	\begin{aligned}
		L(\theta) :=&\mathbb{E}_{x\sim \mu}\big[ \|  V_\theta(x)  - B[ V_\theta](x) \|_2^2 + \lambda V_\theta(x) \big],
	\end{aligned}
\end{equation}
where $\mu$ is the uniform distribution over a compact set $\mathcal{X}\subseteq \mathbb{R}^n$ and the set $\mathcal{X}$ is subject to user's choice.

As suggested in \cite{kumar2020conservative}, given a Bellman backup \eqref{eq:bellman_backup}, its corresponding CQL Bellman backup $B_{CQL}[\cdot]$ can be derived as
\begin{equation}\label{eq:CQL_Bellman_backup}
	B_{CQL}[U](x) := B[U](x) - \lambda,
\end{equation}
where $U:\mathbb{R}^n\to \mathbb{R}$ is a bounded function and $B[\cdot]$ is the Bellman backup \eqref{eq:bellman_backup}. One can show that this Bellman backup is a contraction mapping by a similar reasoning as in the proof of Theorem~\ref{thm:Bellman}.

Given a bounded functional space, the fixed-point theorem \cite{agarwal2001fixed} ensures that the value iteration based on \eqref{eq:CQL_Bellman_backup} will converge to a unique value function, which we refer to as $V_{CQL}(x)$. We characterize the relationship between the nominal value function $V(x)$ in \eqref{eq:inf_horizon_reach_avoid_problem} and its conservative counterpart $V_{CQL}(x)$ below.
\begin{theorem}\label{thm:sandwidch}
	Let $V(x)$ and $V_{CQL}(x)$ be the nominal value function defined in \eqref{eq:inf_horizon_reach_avoid_problem} and CQL value function, respectively. We have
	\begin{equation}
		V(x) - \frac{\lambda}{1-\gamma}\le V_{CQL}(x) \le V(x)-\lambda,\ \forall x \in \mathbb{R}^n.
	\end{equation}
\end{theorem}

Theorem~\ref{thm:sandwidch} implies that the value function learned by CQL would be a lower bound of the true value function \eqref{eq:inf_horizon_reach_avoid_problem}. However, the learned value function from CQL would still be bounded, and it is not too pessimistic, i.e., no state will have a value going to negative infinity. We remark here that the bounds in Theorem~\ref{thm:sandwidch} are specialized for the reach-avoid zero-sum game.

Building on the above results, we propose Algorithm \ref{alg:DQN}, where we substitute the Bellman backup in the algorithm of CQL \cite{kumar2020conservative} with \eqref{eq:bellman_backup}. As in DQN \cite{mnih2013playing}, we adopt \emph{experience replay} in Algorithm~\ref{alg:DQN}, where we store the state transition $\psi_t=(\xi_x^{\mathbf{u},\mathbf{d}}(t),u_t,d_t,\xi_x^{\mathbf{u},\mathbf{d}}(t+1))$ at each time step in a replay memory data-set $\Psi=\{\psi_0,\psi_1,\dots\}$. Subsequently, we apply Q-learning updates to random samples from $\Psi$ in step \ref{alg:update_gradient} of Algorithm \ref{alg:DQN}. It is shown that applying Q-learning to random samples drawn from experience replay could break down the correlation between consecutive transitions and recall rare transitions, which leads to a better convergence performance \cite{mnih2013playing}.

\begin{algorithm}[t]
	\SetAlgoLined
	\caption{Conservative Reach-Avoid Deep Q-learning}\label{alg:DQN}

	Initialize the action-value function $Q_{\theta_0}(x,u,d)$ with random weights $\theta_0$. Select a stepsize $\alpha>0$, the total number of iterations $K$, the batch size $J$, and the rollout horizon $T$\;
	\For{k = 0,\dots , K}{
		Uniformly sample $x\in\mathcal{X}$\;
		Compute $\mathbf{u}$ and $\mathbf{d}$ such that $u_t \gets \arg\max_u \min_d Q_{\theta_k}(\xi_x^{\mathbf{u,d}}(t),u,d)$ and $d_t\gets \arg \min_d Q_{\theta_k}(\xi_x^{\mathbf{u,d}}(t),u_t,d) $\;
		\For{t= 0,\dots, T}{

			Store $\psi_t = (\xi_x^{\mathbf{u,d}}(t),u_t,d_t,\xi_x^{\mathbf{u,d}}(t+1))$ in $\Psi$\;
		}
		\For{j=1,\dots,J}{
			Sample a transition $\psi_j$ in $\Psi$\;
			Set $y_j \gets \min \{c(\xi_x^{\mathbf{u,d}}(j)), \max\{ r(\xi_x^{\mathbf{u,d}}(j)),$ $\gamma \max_u \min_d Q_{\theta_k}(\xi_x^{\mathbf{u,d}}(j),u,d) \} \}$\;\label{alg:bellman}
		}
		$\theta_{k+1} \gets\theta_{k} - \alpha \nabla_\theta \Big( \sum_{j=1}^J \big((y_j - Q_{\theta} (\xi_x^{\mathbf{u,d}}(j),u_j,d_j))^2+\lambda Q_{\theta}(\xi_x^{\mathbf{u,d}}(j),u_j,d_j)\big)\Big)$\;\label{alg:update_gradient}
	}
\end{algorithm}

\begin{comment}
	\section{Reach-avoid Problem with Future Safety Guarantee}\label{sec:reach_and_stay}
	Naively applying the Reach-avoid DQN may result in violation of the constraints or departure from the target set in future. In this section, we propose a pure-DQN solution to the problem where we hope to first reach the target set and then stay thereafter.

	Problem~\ref{Reach_avoid_problem} considers the existence of a policy driving the state to the target set safely. However, its formulation ignores the possibility of the state going out the target set or violating the constraint after reaching the target set, which could lead to unsafe operation of robotic arm or collisions of autonomous vehicles. We formalize the problem as follows.

	\begin{problem}[Reach-avoid Problem with Future Safety Guarantee]\label{prob:reach_and_stay}
		Let $\mathcal{T}:=\{s\in\mathcal{S}: r(s)>0\}$ and $\mathcal{C}:=\{s\in\mathcal{S}:c(s)>0\}$ be the target and the constraint set, respectively. Find a set of states $\mathbb{R}^n$ and a policy $\pi$ such that for any $s\in\mathbb{R}^n$, the trajectory $\xi_{s}^\pi (\tau)\in\mathcal{C}$, $\forall \tau\ge 0$ and $\xi_{s}^\pi (\tau')\in\mathcal{T}$, $\forall \tau'\ge t$, for some $t\ge 0$.
	\end{problem}

	\begin{definition}[Forward-invariant Set]
		A set $\mathcal{S}$ is \emph{forward invariant} if for $\forall s_0\in\mathcal{S}$, $s_t\in \mathcal{S}$ under the dynamics $s_{t+1} = f(s_t,\pi(s_t))$, where $\pi(\cdot)$ is a feedback control policy.
	\end{definition}

	We first learn a forward-invariant set $\mathcal{T}'$ inside the intersection of target set $\mathcal{T}$ and constraint set $\mathcal{C}$. Then, we treat this forward-invariant set as the new target set and learn a reach-avoid set $\mathcal{RA(T',C)}$ and the corresponding policy $\pi$. We can show that for any $s_0\in\mathcal{RA(T',C)}$, there exists a finite time $t\ge 0$ such that $\xi_{s_0}^\pi(t)\in\mathcal{T'}$ and $\xi_{s_0}^\pi(\tau)\in\mathcal{C}$, $\forall \tau\in[0,t]$.

	\begin{proposition}

		Consider a target set $\mathcal{T}=\{s\in\mathcal{S}:r(s)>0\}$ and a constraint set $\mathcal{C} = \{s\in\mathcal{S}: c(s)>0\}$. Let $\mathcal{\hat{V}}_0$ be the zero-level set of the function
		\begin{equation}
			\begin{aligned}
				\hat{V}(s_0)=\max_{\pi}&\max_{t=0,\dots,\infty} \min\{-\gamma^t,\\ & \min_{t'=0,\dots,t}\gamma^{t'} (\min\{r(s_{t'}),c(s_{t'})\}-\epsilon)\}.
			\end{aligned}
		\end{equation}
		Let $\hat{\mathcal{T}}\subseteq \hat{\mathcal{V}}_0$. Let $s\in \mathcal{RA}(\hat{\mathcal{T}}, \mathcal{C})$. Then, there exists a policy $\pi$ such that $\xi_{s}^\pi(\tau)\in\mathcal{C}$, $\forall \tau\ge 0$ and $\xi_{s}^\pi(\tau')\in\mathcal{T}$, $\forall \tau'\ge t$, for some $t\ge 0$.
	\end{proposition}
	\begin{proof}
		The $\hat{\mathcal{V}}_0$ is the set of initial states $s_0$ from which there exists a policy $\hat{\pi}$ such that $\xi_{s_0}^{\hat{\pi}}(t)\in\mathcal{T\cap C}$, $\forall t\ge 0$. Let $\pi$ be the policy associated with $\mathcal{RA(\hat{T},C)}$.

		To be added...
	\end{proof}
	\begin{algorithm}[t]\color{red}
		\SetAlgoLined
		\caption{Conservative Reach-Avoid Deep Q-learning}\label{alg:DQN}

		Initialize the action-value function $Q_{\theta_0}(x,u,d)$ with random weights $\theta_0$\;
		\For{k = 0,\dots , K}{
			Uniformly sample $x\in\mathbb{R}^n$\;
			\For{t= 0,\dots, T}{
				With probability $\epsilon$ randomly pick $(u_t,d_t)\in \mathcal{U\times D}$, and otherwise $u_t \gets \arg\max_u \min_d Q_{\theta_k}(x,u,d)$ and $d_t\gets \arg \min_d Q_{\theta_k}(x_t,u_t,d) $\;}
			Store $\psi_t = (x_t,u_t,d_t,x_{t+1})$ in $\Psi$\;
			\For{j=1,\dots,J}{
				Sample random transitions $\psi_j$ in $\Psi$\;
				Set $y_j \gets \min \{c(x_j), \max\{ r(x_j),\gamma \max_u \min_d Q_{\theta_k}(x_j,u,d) \} \}$\label{alg:bellman}
				$\theta_{kT+t+1} \gets\theta_{kT+t} - \alpha \nabla_\theta \big( \sum_{j=1}^J (y_j - Q_{\theta_{kT+t}} (x_t,u_t,d_t))^2+\lambda Q_{\theta_{kT+t}}(x_t,u_t,d_t)\big)$\;\label{alg:update_gradient}
			}
		}
	\end{algorithm}
\end{comment}

\section{Problem Formulation}
\label{sec:problem_formulation}
We denote the state of a system by $x\in \mathbb{R}^n$. Define $\mathbf{u}:=\{u_0,u_1,\dots\}$ and $\mathbf{d} := \{d_0,d_1,\dots\}$, where $u_t\in\mathcal{U}\subseteq \mathbb{R}^m$ and $d_t\in \mathcal{D}\subseteq \mathbb{R}^\ell$ are a sequence of control inputs and a sequence of disturbances, respectively. We assume $\mathcal{U}$ and $\mathcal{D}$ to be compact sets. Let $\xi_{x}^{\mathbf{u},\mathbf{d}}(t)$ be the state trajectory evaluated at time $t$, which evolves according to the update rule
\begin{equation}
\begin{aligned}
    \xi_x^{\mathbf{u},\mathbf{d}}(0) & = x,\\
    \xi_x^{\mathbf{u},\mathbf{d}}(t+1) &= f(\xi_x^{\mathbf{u},\mathbf{d}}(t), u_t,d_t),\ t\in\mathbb{Z}_+,
\end{aligned}
\end{equation}
where $\mathbb{Z}_+$ is the set of all non-negative integers and the system dynamics $f(\cdot,\cdot,\cdot ):\mathbb{R}^n\times \mathcal{U}\times \mathcal{D}\to \mathbb{R}^n$ is assumed to be Lipschitz continuous in the state.

Many control problems involving safety-critical systems can be interpreted as driving the system's state to a specific region while satisfying certain safety constraints. This intuition can be formalized by introducing the concept of \emph{target set} as the set of desirable states to reach as well as the concept of \emph{constraint set} as the set of all the states complying with the given constraints. The task is to design control inputs such that even under the worst-case disturbance the system state trajectory hits the target set while staying in the constraint set all times. We represent the target set and constraint set by $\mathcal{T}=\{x\in\mathbb{R}^n: r(x)>0\}$ and $\mathcal{C}=\{x\in\mathbb{R}^n: c(x)>0 \}$, respectively, for some Lipschitz continuous and bounded functions $r(\cdot): \mathbb{R}^n \to \mathbb{R}$ and $c(\cdot):\mathbb{R}^n\to \mathbb{R}$.

At each time instance $t\in\mathbb{Z}_+$, the control input $u_t$ aims to move the state towards the target set while staying inside the constraint set, whereas the disturbance $d_t$ attempts to drive the state away from the target set and the constraint set. In this work, we consider a conservative setting, where at each time instance the control input plays before the disturbance.
We propose to account for this playing order by adopting the notion of \emph{non-anticipative strategy}
\begin{definition}[Non-anticipative strategy]
A map $\phi: \{u_t\}_{t=0}^\infty\to \{d_t\}_{t=0}^\infty$, where $u_t\in\mathcal{U}$ and $d_t\in\mathcal{D}$, $\forall t\in\mathbb{Z}_+$, is a non-anticipative strategy if it satisfies the following condition: Let $\{u_t\}_{t=0}^\infty$ and $\{\bar{u}_t\}_{t=0}^\infty$ be two sequences of control inputs. Let $\{d_t\}_{t=0}^\infty=\phi(\{u_t\}_{t=0}^\infty)$ and $\{\bar{d}_t\}_{t=0}^\infty = \phi(\{\bar{u}_t\}_{t=0}^\infty)$. For all $T\ge 0$, if $u_t=\bar{u}_t$, $\forall t\in\{0,1,\dots,T\}$, then $d_t = \bar{d}_t$, $\forall t\in \{0,1,\dots, T\}$.
\end{definition}
The intuition behind this non-anticipative strategy is that, given two sequences of control inputs sharing the same values for the first $T$ entries, the corresponding entries of the two sequences of disturbance must also be the same, meaning the disturbance cannot use any information about the future control inputs when taking its own action. We denote by $\Phi$ the set of all non-anticipative strategies. Building upon the previous discussion on reach-avoid zero-sum games, we are now ready to define the definition the \emph{reach-avoid set}:
\begin{equation*}
    \begin{aligned}
    \mathcal{RA(T,C)} := &\{x\in\mathbb{R}^n: \forall \phi\in\Phi, \exists \{u_t\}_{t=0}^\infty \textrm{ and } T\ge 0,\\ &\textrm{s.t., } \forall t\in[0,T],\xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(T) \in\mathcal{T}\wedge   \xi_{x}^{\mathbf{u},\phi(\mathbf{u})}(t)\in \mathcal{C}\},
    \end{aligned}
\end{equation*}
where 's.t.' is the abbreviation of the phrase 'such that'. As such, we formalize the problem to be studied in this paper below.
\begin{problem}[Infinite-horizon reach-avoid game]\label{Reach_avoid_problem}
 Let $\mathcal{T}:=\{x\in\mathbb{}{R}^n: r(x)>0\}$ and $\mathcal{C}:=\{x\in\mathbb{R}^n:c(x)>0\}$ be the target and the constraint set, respectively. Find the reach-aviod set $\mathcal{RA(T,C)}$ and an optimal sequence of control inputs $\{u_t\}_{t=0}^\infty$ for each state in $\mathcal{RA(T,C)}$ such that under the worst-case disturbance $\{d_t\}_{t=0}^\infty$ the state trajectory will reach the target set without violating the constraints.
\end{problem}

\section{Convergence analysis}
\label{sec:results}


\section{Related Work}\label{sec:related}
\PAR{Multi-view Depth Estimation.}
The most related line of research is \textit{real-time methods} for multi-view depth estimation.
Before the age of deep learning, many renowned works in monocular 3D reconstruction \cite{vogiatzisVideobasedRealtimeMultiview2011,kolevTurningMobilePhones2014,schops3DModelingGo2015,pizzoliREMODEProbabilisticMonocular2014} have achieved good performance with plane-sweeping stereo and depth filters under the assumption of photo-consistency.
\cite{valentinDepthMotionSmartphone2019,yang2020Mobile3DReconRM} optimize this line of research towards low power consumption on mobile platforms.
Learning-based methods on real-time multi-view depth estimation try to alleviate the photo-consistency assumption with a data-driven approach.
Notably, MVDepthNet \cite{wangMVDepthNetRealtimeMultiview2018} and Neural RGB-$>$D \cite{liuNeuralRGBSensing2019} use 2D CNNs to process the 2D depth cost volume constructed from multi-view image features.
CNMNet \cite{longOcclusionAwareDepthEstimation2020} further leverages the planar structure in indoor scenes to constrain the surface normals calculated from the predicted depth maps to obtain smooth depth estimation.
These learning-based methods use 2D CNNs to process the depth cost volume to maintain a low computational cost for near real-time performance. %

When the input images are high-resolution and offline computation is allowed, multi-view depth estimation is also known as the \textit{Multiple View Stereo (MVS)} problem.
PatchMatch-based methods \cite{zhengPatchMatchBasedJoint2014,schonbergerPixelwiseViewSelection2016} have achieved impressive accuracy
and are still the most popular methods applicable to high-resolution images.
Learning-based approaches in MVS have recently dominated several benchmarks \cite{aanaesLargeScaleDataMultipleView2016,knapitschTanksTemplesBenchmarking2017} in terms of accuracy,
but are only limited to processing mid-resolution images due to the GPU memory constraint.
Different from the real-time methods, 3D cost volumes are constructed and 3D CNNs are used to process the cost volume as proposed in MVSNet \cite{yaoMVSNetDepthInference2018}.
Some recent works \cite{guCascadeCostVolume2019,chengDeepStereoUsing2019} improve this pipeline with a coarse-to-fine approach.
Similar design can also be found in many learning-based SLAM systems
 \cite{ummenhoferDeMoNDepthMotion2017,zhouDeepTAMDeepTracking2018,tangBANetDenseBundle2018,teedDeepV2DVideoDepth2018}.

All the above-mentioned works adopt single-view depth maps as intermediate representations.
SurfaceNet \cite{jiSurfaceNetEndtoend3D2017,jiSurfaceNetEndtoend3D2020} takes a different approach and uses a unified \textit{volumetric representation} to predict the volume occupancy.
Recently, Atlas \cite{murezAtlasEndtoEnd3D2020} also proposes a volumetric design and direct predicts TSDF and semantic labels with 3D CNN.
As an offline method, Atlas aggregates the image features of the entire sequence and then predicts the global TSDF volume only once with a decoder module.
We further elaborate the relationship between the proposed method and Atlas in the supplementary material.
The proposed method is also related to \cite{choy3DR2N2UnifiedApproach2016,karLearningMultiViewStereo} in terms of using recurrent networks for multi-view feature fusion.
However, their recurrent fusion is applied to only the global features and their focus is to reconstruct single objects.

\input{figures/sys-arch.tex}
\PAR{3D Surface Reconstruction.}
After depth maps are estimated and converted to point clouds, the remaining task for 3D reconstruction is to estimate the 3D surface position and produce the reconstructed mesh.
In an offline MVS pipeline \cite{schonbergerPixelwiseViewSelection2016}, Poisson reconstruction \cite{kazhdanScreenedPoissonSurface2013} and Delaunay triagulation \cite{labatutRobustEfficientSurface2009} are often used to fulfill this purpose.
Proposed by the seminal work KinectFusion \cite{newcombeKinectFusionRealTimeDense2011},
incremental volumetric TSDF fusion \cite{curlessVolumetricMethodBuilding1996} gets widely adopted in real-time reconstruction scenarios due to its simplicity and parallelization capability.
\cite{niessnerRealtime3DReconstruction2013,daiBundleFusionRealtimeGlobally2016} improve KinectFusion by making it more scalable and robust.
RoutedFusion~\cite{wederRoutedFusionLearningRealtime2020,weder2020neuralfusion} changes the fusion operation from a simple linear addition into a data-dependent process.

\PAR{Neural Implicit Representations.}
Recently, neural implicit representations~\cite{meschederOccupancyNetworksLearning2018,parkDeepSDFLearningContinuous2019,saitoPIFuPixelAlignedImplicit2019,jiangLocalImplicitGrid2020,yarivMultiviewNeuralSurface2020,liu2020neural} have gained significant advances.
Our work also learns a neural implicit representation by predicting SDF with the neural network from the encoded image features similar to PIFu~\cite{saitoPIFuPixelAlignedImplicit2019}.
The key difference is that we are using sparse 3D convolution to predict a discrete TSDF volume, instead of querying the MLP network with image features and 3D coordinates.

\section{Introduction}\label{sec:intro}
3D scene reconstruction is one of the central tasks in 3D computer vision with many applications.
In augmented reality (AR) for example, to enable realistic and immersive interactions between AR effects and the surrounding physical scene,
3D reconstruction needs to be accurate, coherent and performed in real-time.
While camera motion can be tracked accurately with state-of-the-art visual-inertial SLAM systems \cite{camposORBSLAM3AccurateOpenSource2020,qinGeneralOptimizationbasedFramework2019a, AugmentedRealityApple},
real-time image-based dense reconstruction remains to be a challenging problem due to low reconstruction quality and high computation demands.
\begin{figure}[tb]
    \centering
    \includegraphics[width=1\linewidth]{figures/comparison.pdf}
    \caption{
        \textbf{Comparison between depth-based 3D reconstruction methods and the proposed method.}
        In depth-based methods, key-frame depths are estimated separately from each key frame, and later fused into a TSDF volume.
        In the proposed method, the TSDF volume is directly predicted with all the key frames in a local window.
        This design leads to a much more coherent reconstruction and real-time speed.
    }
    \label{fig:teaser}
\end{figure}

Most image-based real-time 3D reconstruction pipelines \cite{schops3DModelingGo2015,yangRealtimeMonocularDense2017} adopt the depth map fusion approach, which resemble RGB-D reconstruction methods like KinectFusion \cite{newcombeKinectFusionRealTimeDense2011}.
Single-view depth maps from each key frame are first estimated with real-time multi-view depth estimation methods like \cite{wangMVDepthNetRealtimeMultiview2018,liuNeuralRGBSensing2019,houMultiViewStereoTemporal2019,valentinDepthMotionSmartphone2019}.
The estimated depth maps are later filtered with criteria like multi-view consistency and temporal smoothness, and fused into a Truncated Signed Distance Function (TSDF) volume.
The reconstructed mesh can be extracted from the fused TSDF volume with the Marching Cubes algorithm \cite{lorensenMarchingCubesHigh1987}.
This depth-based pipeline has two major drawbacks.
First, since single-view depth maps are estimated individually on each key frame,
each depth estimation is from scratch instead of conditioned on the previous estimations even the view-overlapping is substantial.
As a result, the scale-factor may vary even with the correct camera ego-motion.
Due to depth inconsistencies between different views, the reconstruction result is prone to be either layered or scattered.
One example is shown in the red boxes in Fig. \ref{fig:teaser}, where the depth-based method struggles to produce coherent depth estimations on the chairs and wall.
Second, since key-frame depth maps need to be estimated separately in overlapped local windows,
geometry of the same 3D surface is estimated multiple times in different key frames, causing redundant computation.

In this paper, we propose a novel framework for real-time monocular reconstruction named NeuralRecon\xspace that jointly reconstructs and fuses the 3D geometry directly in the volumetric TSDF representation.
Given a sequence of monocular images and their corresponding camera poses estimated by a SLAM system,
NeuralRecon\xspace incrementally reconstructs local geometry in a view-independent 3D volume instead of view-dependent depth maps.
Specifically, it unprojects the image features to form a 3D feature volume and then uses sparse convolutions to process the feature volume to output a sparse TSDF volume.
With a coarse-to-fine design, the predicted TSDF is gradually refined at each level.
By directly reconstructing the implicit surface (TSDF), the network is able to
learn the local smoothness and global shape  prior  of natural 3D surfaces.
Different from depth-based methods that predict depth maps for each key frame separately, the surface geometry within a local fragment window is jointly predicted in NeuralRecon\xspace,
and thus \textit{locally} coherent geometry estimation can be produced.
To make the current-fragment reconstruction to be \textit{globally} consistent with the previously reconstructed fragments,
a learning-based TSDF fusion module using the Gated Recurrent Unit (GRU) is proposed.
The GRU fusion makes the current-fragment reconstruction conditioned on the previously reconstructed global volume,
yielding a joint reconstruction and fusion approach.
As a result, the reconstructed mesh is dense, accurate and globally coherent in scale.
Furthermore, predicting the volumetric representation also removes the redundant computation in depth-based methods,
which allows us to use a larger 3D CNN while maintaining the real-time performance.

We validate our system on the ScanNet and 7-Scenes datasets.
The experimental results show that
NeuralRecon\xspace outperforms multiple state-of-the-art multi-view depth estimation methods and the volume-based reconstruction method Atlas~\cite{murezAtlasEndtoEnd3D2020} by a large margin, %
while achieving a real-time performance at 33 key frames per second, ${\sim}10\times$ faster compared to Atlas.
As shown in the supplementary video, our method is able to reconstruct large-scale 3D scenes from a video stream on a laptop GPU in real-time.
To the best of our knowledge, this is the first learning-based system that is able to reconstruct dense and coherent 3D scene geometry in real-time.

\section{Experiments}\label{sec:exp}
In this section, we conduct a series of experiments to evaluate the reconstruction quality and different design considerations of NeuralRecon\xspace.

\subsection{Datasets, Metrics, Baselines and Protocols.}\label{sec:dmb}
\PAR{Datasets.} We perform the experiments on two indoor datasets, ScanNet (V2)~\cite{daiScanNetRichlyannotated3D2017} and 7-Scenes~\cite{shottonSceneCoordinateRegression2013}.
The ScanNet dataset contains 1613 indoor scenes with ground-truth camera poses, surface reconstructions, and semantic segmentation labels.
There are two training/validation splits commonly used in previous works (defined in \cite{murezAtlasEndtoEnd3D2020} and \cite{tangBANetDenseBundle2018}) for the ScanNet dataset.
We use the same training and validation data with the corresponding baseline methods to make a fair comparison.
The 7-Scenes dataset is another challenging RGB-D dataset captured in indoor scenes.
Following the baseline method~\cite{longOcclusionAwareDepthEstimation2020}, we use the model trained on ScanNet to perform the validation on 7-Scenes.

\PAR{Metrics.} The 3D reconstruction quality is evaluated using 3D geometry metrics presented in \cite{murezAtlasEndtoEnd3D2020}, as well as standard 2D depth metrics defined in \cite{eigenDepthMapPrediction2014}.
The definitions of these metrics are detailed in the supplementary material.
Among these 3D and 2D metrics, we consider \textit{F-score} as the most suitable metrics to measure 3D reconstruction quality since both the accuracy and completeness of the reconstruction are considered.

\PAR{Baselines.} We compare our method with the following baseline methods in three categories:
1) \textit{Real-time methods} for multi-view depth estimation \cite{wangMVDepthNetRealtimeMultiview2018,houMultiViewStereoTemporal2019,liuNeuralRGBSensing2019,longOcclusionAwareDepthEstimation2020}.
Due to the efficiency constraints, the estimated depth accuracy by these methods is rather limited.
We compare with these methods to demonstrate the better reconstruction accuracy of NeuralRecon\xspace given the same efficiency.
2) \textit{Multiple View Stereo} methods \cite{schonbergerPixelwiseViewSelection2016,imDPSNetEndtoendDeep2019,yaoMVSNetDepthInference2018,murezAtlasEndtoEnd3D2020,luoConsistentVideoDepth2020}.
These offline methods have much higher accuracy compared to real-time methods.
These baselines are used to demonstrate that NeuralRecon\xspace achieves a reconstruction quality on-par with offline methods but runs in real-time.
3) \textit{Learning-based SLAM} methods \cite{ummenhoferDeMoNDepthMotion2017,tangBANetDenseBundle2018,teedDeepV2DVideoDepth2018}.
These monocular SLAM methods estimate camera poses and perform reconstruction simultaneously, thus the scale factor of pose and depth is usually not accurately estimated.
For a fair comparison, we use ground-truth camera poses for these methods and apply a scaling factor to the predicted depth map using ground-truth depth.
Among all these baseline methods, \textit{GPMVS}~\cite{houMultiViewStereoTemporal2019} and \textit{Atlas}~\cite{murezAtlasEndtoEnd3D2020} are the most relevant real-time and offline methods, respectively.

\PAR{Evaluation Protocols.} Since our method does not estimate depth maps explicitly, we render the reconstructed mesh to the image plane and obtain depth map estimations \cite{murezAtlasEndtoEnd3D2020}.
Key frames used for evaluation are sampled from the video sequence with an interval of 10 frames for both depth-based methods and Atlas.
Following \cite{murezAtlasEndtoEnd3D2020,longOcclusionAwareDepthEstimation2020}, \cite{yaoMVSNetDepthInference2018,wangMVDepthNetRealtimeMultiview2018,imDPSNetEndtoendDeep2019,houMultiViewStereoTemporal2019} are fine-tuned on ScanNet.
To evaluate depth-based methods \cite{schonbergerPixelwiseViewSelection2016, wangMVDepthNetRealtimeMultiview2018, houMultiViewStereoTemporal2019, imDPSNetEndtoendDeep2019} in 3D,
we use the point cloud fusion to obtain the 3D reconstruction following Atlas.
For other depth-based methods, we use the standard TSDF fusion proposed in~\cite{newcombeKinectFusionRealTimeDense2011,curlessVolumetricMethodBuilding1996}.
For the reasons we detailed in the supplementary material, in order to make a fair comparison with Atlas, we also report the evaluation results using the double-layered mesh (same as Atlas).
The evaluation of 3D geometry on 7-Scenes uses the single-layered mesh.
We also evaluate the depth filtering operation with multi-view consistency check, which will be elaborated in the supplementary material.
\input{tables/ScanNet3d.tex}
\input{tables/ScanNet2d.tex}

\subsection{Evaluation Results}\label{sec:eval_results}

\PAR{ScanNet.}
2D depth metrics and 3D geometry metrics are used on the ScanNet dataset.
The 3D geometry evaluation results are shown in Tab. \ref{tab:scannet-3d}.
Our method produces much better performance than recent learning-based methods and achieves slightly better results than COLMAP.
We believe that the improvements come from the joint reconstruction and fusion design achieved by the GRU Fusion module.
Compared to depth-based methods, NeuralRecon\xspace can produce coherent reconstructions both locally and globally.
Our method also surpasses the volumetric baseline method Atlas \cite{murezAtlasEndtoEnd3D2020} on the accuracy, precision, and F-score.
The improvements potentially come from the design of local fragment separation in our method,
which can act as a view-selection mechanism that avoids irrelevant image features to be fused into the 3D volume.
In terms of completeness and recall, the proposed method has an inferior performance compared to both depth-based methods and Atlas.
Since depth-based methods predict pixel-wise depth maps on each view, the coverage of their predictions is high by nature, but with the cost of accuracy.
Being an offline approach, Atlas has the advantage of having a global context from the entire sequence before predicting the geometry.
As a result, Atlas sometimes achieves even better completeness compared to the ground-truth due to its TSDF completion capability.
However, Atlas tends to predict over-smoothed geometries, and the completed regions may be inaccurate.
As for 2D depth metrics, NeuralRecon\xspace also outperforms previous state-of-the-art methods for almost all 2D depth metrics, as shown in Tab. \ref{tab:scannet-2d}. %

\PAR{7-Scenes.}
2D depth metrics and 3D geometry metrics are evaluated on the 7-Scenes dataset.
As shown in Tab. \ref{tab:7scenes-2d}, our method achieves comparable performance to the state-of-the-art method CNMNet \cite{longOcclusionAwareDepthEstimation2020} and outperforms all other methods.
We believe that the accuracy of the proposed method can be further improved by leveraging the planar structure information as in CNMNet.
Since the model used here is only trained on ScanNet, the results also demonstrate that NeuralRecon\xspace can generalize well beyond the domain of the training data.

\PAR{Efficiency.}
We also report the average running time of the baselines and our method in Tab. \ref{tab:scannet-3d}.
Only the inference time on key frames is computed.
A detailed timing analysis for each module of NeuralRecon\xspace is presented in Table \ref{tab:time}.
For volumetric methods (Atlas and ours), the running time is obtained by dividing the time of reconstructing the TSDF volume of a local fragment by the number of key frames in the local fragment.
Notice that the time for TSDF fusion is not included for depth-based methods.
The running time for \cite{teedDeepV2DVideoDepth2018,luoConsistentVideoDepth2020,liuNeuralRGBSensing2019,longOcclusionAwareDepthEstimation2020, ummenhoferDeMoNDepthMotion2017} and NeuralRecon\xspace is measured on an NVIDIA RTX 2080Ti GPU.
We use running time reported in \cite{murezAtlasEndtoEnd3D2020} and \cite{yu2020fast} for \cite{wangMVDepthNetRealtimeMultiview2018,imDPSNetEndtoendDeep2019,schonbergerPixelwiseViewSelection2016,houMultiViewStereoTemporal2019,murezAtlasEndtoEnd3D2020} and \cite{yaoMVSNetDepthInference2018}, respectively.
\input{tables/sevenscenes_all.tex}

As shown in Tab. \ref{tab:scannet-3d}, our time cost is 30ms per key frame,  achieving real-time speed at 33 key frames per second and outperforming all previous methods.
Specifically, our method runs $\sim$\textbf{10$\times$ faster} than Atlas, and \textbf{77$\times$ faster} than Consistent Depth.
Predicting the volumetric representation removes the redundant computation in depth-based methods, which contributes to the fast running speed of our method.
Compared to Atlas, incrementally reconstructing geometry in local fragment avoids processing a huge 3D volume, leading to a faster speed than Atlas.
The use of sparse convolution also contributes to the superior efficiency of NeuralRecon\xspace.

\vspace{-0.1cm}
\subsection{Ablation Study}\label{sec:ablation}
In this section, we conduct several ablation experiments on the ScanNet dataset to discuss the effectiveness of components in our method.

\PAR{GRU Fusion.}
We validate the GRU Fusion design by comparing rows from (i) to (iv) in Tab. \ref{tab:ablation}.

To validate the benefit of feature fusion, we compare row (i) and row (ii) in Tab. \ref{tab:ablation}. Using feature fusion with the average operation obtains nearly 5\% improvement for the precision metric than conventional linear TSDF fusion.
Visualization in Fig. \ref{fig:ablation} shows that feature fusion with the average operation can reconstruct smoother geometry.
These results demonstrate that feature fusion can be more effective than TSDF fusion using the same average operation.

Comparing row (ii) and row (iii) in Tab. \ref{tab:ablation} shows that replacing average operation with GRU gives 4\% improvement in terms of recall.
The mesh in Fig. \ref{fig:ablation} (iii) is also more complete than that in Fig. \ref{fig:ablation} (ii).
These results demonstrate that the GRU is more effective to
selectively integrate \textit{only} the consistent information from the current-fragment to the hidden state.

The recalls in row (iii) and row (iv) in Tab. \ref{tab:ablation} show that fusion in the fragment bounding volume can produce much more complete results.
Visualization results in Fig. \ref{fig:ablation} (iii) and (iv) show that, with fusion in the fragment bounding volume, our method produces fewer artifacts on the ground.
Fusion in the fragment bounding volume can leverage the context information in boundaries and produce more consistent and complete surface estimation.

\input{tables/time-single-column.tex}
\input{tables/ablation.tex}
\PAR{Number of views.}
We set 5, 7, 9 and 11 views as the length of a fragment respectively.
As shown in row (v) in Tab. \ref{tab:ablation}, the F-score has over 2\% improvement when 9 views are used as a fragment.
As shown in visualization results in Fig. \ref{fig:ablation} (v), with more views in a fragment, the geometry can be reconstructed more accurately compared to Fig. \ref{fig:ablation} (iv).

\PAR{Qualitative Results.}\label{sec:qualitative_results}
We provide the qualitative results and the corresponding analysis in Fig. \ref{fig:qualitative}.

\section{Methods}\label{sec:method}
Given a sequence of monocular images $\{\mathbf{I}_t\}$ and camera pose trajectory $\{\xi_{t}\} \in \mathbb{SE}(3)$ provided by a SLAM system,
the goal is to reconstruct dense 3D scene geometry accurately in real-time.
We denote the global TSDF volume to reconstruct as $\mathbf{S}_t^g$, where $t$ represents the current time step.
The system architecture is illustrated in Fig. \ref{fig:arch}.

\subsection{Key Frame Selection}\label{sec:keyframe}
To achieve real-time 3D reconstruction that is suitable for interactive applications,
the reconstruction process needs to be incremental and the input images should be processed sequentially in local fragments \cite{choiRobustReconstructionIndoor}.
We seek to find a set of suitable key frames from the incoming image stream as input for the networks.
To provide enough motion parallax while keeping multi-view co-visibility for reconstruction, the selected key frames should be neither too close nor far from each other.
Following \cite{houMultiViewStereoTemporal2019}, a new incoming frame is selected as a key frame if its relative translation is greater than $t_{max}$ and the relative rotation angle is greater $R_{max}$.
A window with $N$ key frames is defined as a local fragment.
After key frames are selected, a cubic-shaped fragment bounding volume (FBV) that encloses all the key frame view-frustums is computed with a fixed max depth range $d_{max}$ in each view.
Only the region within the FBV is considered during the reconstruction of each fragment.

\input{figures/toy_example.tex}
\subsection{Joint Fragment Reconstruction and Fusion}
We propose to simultaneously reconstruct the TSDF volume of a local fragment $\mathbf{S}_t^l$ and fuse it with global TSDF volume $\mathbf{S}_t^g$ with a learning-based approach.
The joint reconstruction and fusion is carried out in the local coordinate system.
The definition of the local and global coordinate systems as well as the construction of FBV are illustrated in Fig. 1 of the supplementary material.

\PAR{Image Feature Volume Construction.}
The $N$ images in the local fragment are first passed through the image backbone to extract the multi-level features.
Similar to previous works on volumetric reconstruction \cite{karLearningMultiViewStereo,jiSurfaceNetEndtoend3D2017,murezAtlasEndtoEnd3D2020},
the extracted features are back-projected along each ray into the 3D feature volume.
The image feature volume $\mathbf{F}_t^l$ is obtained by averaging the features from different views according to the visibility weight of each voxel.
The visibility weight is defined as the number of views from which a voxel can be observed in the local fragment.
A visualization of this unprojection process can be found in Fig.\ref{fig:toy_examples} i.

\PAR{Coarse-to-fine TSDF Reconstruction.}
We adopt a coarse-to-fine approach to gradually refine the predicted TSDF volume at each level.
We use 3D sparse convolution to efficiently process the feature volume $\mathbf{F}_t^l$.
The sparse volumetric representation also naturally integrates with the coarse-to-fine design.
Specifically, each voxel in the TSDF volume $\mathbf{S}_t^l$ contains two values, the occupancy score $o$ and the SDF value $x$.
At each level, both $o$ and $x$ are predicted by the MLP.
The occupancy score represents the confidence of a voxel being within the TSDF truncation distance $\lambda$.
The voxel whose occupancy score is lower than the sparsification threshold $\theta$ is defined as void space and will be sparsified.
This representation of sparse TSDF volume is visually illustrated in Fig.\ref{fig:toy_examples} iii.
After the sparsification,
$\mathbf{S}_t^{l}$ is upsampled by $2\times$ and concatenated with the $\mathbf{F}_t^{l+1}$ as the input for the GRU Fusion module (introduced later) in the next level.

Instead of estimating single-view depth maps for each key frame, NeuralRecon\xspace jointly reconstructs the implicit surface within the bounding volume of the local fragment window.
This design guides the network to learn the natural surface prior directly from the training data.
As a result, the reconstructed surface is locally smooth and coherent in scale.
Notably, this design also leads to less redundant computation compared to depth-based methods since each area on the 3D surface is estimated only once during the fragment reconstruction.

\PAR{GRU Fusion.}
To make the reconstruction consistent between fragments,
we propose to make the current-fragment reconstruction to be conditioned on the reconstructions in previous fragments.
We use a 3D convolutional variant of Gated Recurrent Unit (GRU)~\cite{chungEmpiricalEvaluationGated2014} module for this purpose.
As illustrated in Fig.\ref{fig:toy_examples} ii,
at each level the image feature volume $\mathbf{F}_t^l$ is first passed through the 3D sparse convolution layers to extract 3D geometric features $\mathbf{G}_t^l$.
The hidden state $\mathbf{H}_{t-1}^l$ is extracted from the global hidden state $\mathbf{H}_{t-1}^g$ within the fragment bounding volume.
GRU fuses $\mathbf{G}_t^l$ with hidden state $\mathbf{H}_{t-1}^l$ and produces the updated hidden state $\mathbf{H}_t^l$,
which will be passed through the MLP layers to predict the TSDF volume $\mathbf{S}_t^l$ at this level.
The hidden state $\mathbf{H}_{t}^l$ will also be updated to global hidden state $\mathbf{H}_{t}^g$ by directly replacing the corresponding voxels.
Formally, denoting $z_t$ as the update gate, $r_t$ as the reset gate, $\sigma$ as the sigmoid function and $W_{*}$ as the weight for sparse convolution,
GRU fuses $\mathbf{G}_t^l$ with hidden state $\mathbf{H}_{t-1}^l$ with the following operations:
\begin{align*}
    &z_t = \sigma(\text{SparseConv}([\mathbf{H}^l_{t-1}, \mathbf{G}_t^l], W_z)) \\
    &r_t = \sigma(\text{SparseConv}([\mathbf{H}^l_{t-1}, \mathbf{G}_t^l], W_r)) \\
    &\tilde{\mathbf{H}^l_{t}} = \tanh(\text{SparseConv}([r_t \odot \mathbf{H}^l_{t-1}, \mathbf{G}_t^l], W_h)) \\
    & \mathbf{H}^l_{t} = (1 - z_t) \odot \mathbf{H}^l_{t-1} + z_t \odot \tilde{\mathbf{H}^l_{t}}
\end{align*}

Intuitively, in the context of joint reconstruction and fusion of TSDF,
the update gate $z_t$ and forget gate $r_t$ in the GRU determine how much information from the previous reconstructions (i.e. hidden state $\mathbf{H}^l_{t-1}$) is fused to the current-fragment geometric feature $\mathbf{G}_t^l$,
as well as how much information from the current-fragment will be fused into the hidden state $\mathbf{H}^l_{t}$.
As a data-driven approach, the GRU serves as a selective attention mechanism that replaces the linear running-average operation in conventional TSDF fusion~\cite{newcombeKinectFusionRealTimeDense2011}.
By predicting $\mathbf{S}_t^l$ after the GRU,
the MLP network can leverage the context information accumulated from history fragments to produce consistent surface geometry across local fragments.
This is also conceptually analogous to the depth filter in a non-learning-based 3D reconstruction pipeline~\cite{schops3DModelingGo2015,pizzoliREMODEProbabilisticMonocular2014},
where the current observation and the temporally-fused depths are fused with the Bayesian filter.
The effectiveness of joint reconstruction and fusion is validated in the ablation study.

\PAR{Integration to the Global TSDF Volume.}
At the last coarse-to-fine level, $\mathbf{S}_t^3$ is predicted and further sparsified to $\mathbf{S}_t^l$.
Since the fusion between $\mathbf{S}_t^l$ and $\mathbf{S}_t^g$ has been done in GRU Fusion, $\mathbf{S}_t^l$ is integrated into $\mathbf{S}_t^g$ by directly replacing the corresponding voxels after being transformed into the global coordinate.
At each time step $t$, Marching Cubes is performed on $\mathbf{S}_t^g$ to reconstruct the mesh.

\PAR{Supervision.}
Following \cite{daiSGNNSparseGenerative2019}, two loss functions are used to supervise the network.
The occupancy loss is defined as the binary cross-entropy (BCE) between the predicted occupancy values and the ground-truth occupancy values.
The SDF loss is defined as the $\ell_1$ distance between the predicted SDF values and the ground-truth SDF values.
We log-transform the SDF values of predictions and ground-truth before applying the $\ell_1$ loss.
The supervision is applied to all the coarse-to-fine levels.

\subsection{Implementation Details}
We use \texttt{torchsparse} \cite{tangSearchingEfficient3D2020} as the implementation of 3D sparse convolution.
The image backbone is a variant of MnasNet \cite{tan2019mnasnet} and is initialized with the weights pretrained from ImageNet.
Feature Pyramid Network \cite{linFeaturePyramidNetworks2017} is used in the backbone to extract more representative multi-level features.
The entire network is trained end-to-end with randomly initialized weights except for the image backbone.
The occupancy score $o$ is predicted with a Sigmoid layer.
The voxel size of the last level is $4cm$ and the TSDF truncation distance $\lambda$ is set to $12cm$.
$d_{max}$ is set to $3m$.
$R_{max}$ and $t_{max}$ are set to 15\degree and $0.1m$ respectively.
$\theta$ is set to $0.5$.
Nearest-neighbor interpolation is used in the upsampling between coarse-to-fine levels.

\section{Conclusion}
In this paper, we introduced a novel system NeuralRecon\xspace for real-time 3D reconstruction with monocular video.
The key idea is to jointly reconstruct and fuse sparse TSDF volumes for each video fragment incrementally by 3D sparse convolutions and GRU.
This design enables NeuralRecon\xspace to output accurate and coherent reconstruction in real-time.
Experiments show that NeuralRecon\xspace outperforms state-of-the-art methods in both reconstruction quality and running speed.
The sparse TSDF volume reconstructed by NeuralRecon\xspace can be directly used in downstream tasks like 3D object detection, 3D semantic segmentation and neural rendering.
We believe that, by jointly training with the downstream tasks end-to-end, NeuralRecon\xspace enables new possibilities in learning-based multi-view perception and recognition systems.

\input{figures/qualitative.tex}
\PAR{Acknowledgement.}
The authors would like to acknowledge the support from the National Key Research and Development Program of China (No. 2020AAA0108901), NSFC (No. 61806176), and ZJU-SenseTime Joint Lab of 3D Vision.

\input{figures/ablation.tex}