This paper proposes an algorithm for motion planning among dynamic agents using adaptive conformal prediction. We consider a deterministic control system and use trajectory predictors to predict the dynamic agents' future motion, which is assumed to follow an unknown distribution. We then leverage ideas from adaptive conformal prediction to dynamically quantify prediction uncertainty from an online data stream. Particularly, we provide an online algorithm that uses delayed agent observations to obtain uncertainty sets for multistep-ahead predictions with probabilistic coverage. These uncertainty sets are used within a model predictive controller to safely navigate among dynamic agents. While most existing data-driven prediction approaches quantify prediction uncertainty heuristically, we quantify the true prediction uncertainty in a distribution-free, adaptive manner that even allows to capture changes in prediction quality and the agents' motion.  We empirically evaluate  our algorithm on a  case study where a drone avoids a flying frisbee.

MPC, dynamic environments, uncertainty quantification, and conformal prediction.

§ INTRODUCTION

Motion planning of autonomous systems in dynamic environments requires the system to  reason about uncertainty in its environment, e.g., a self-driving car needs to reason about uncertainty in the motion of other vehicles, and a mobile robot navigating a crowded space needs to assess uncertainty of nearby pedestrians. These applications are safety critical, as the agents’ intentions are unknown, and systems must be able to plan reactive behaviors in response to an increase in uncertainty.

Existing works include predictive and reactive approaches, e.g., multi-agent navigation via the dynamic window approach [Fox et al., 1997, Mitsch et al., 2013] or navigation functions [Dimarogonas et al., 2006, Tanner et al., 2003]. Reactive approaches typically consider simplified dynamics and do not optimize performance. Predictive approaches incorporate predictions of the agents' future motion and can optimize performance. Interactive approaches  take inter-agent interaction into account [Kretzschmar et al., 2016, Everett et al., 2021], while non-interactive approaches ignore potential interactions [Trautman and Krause, 2010, Du Toit and Burdick, 2011].

While many prior works assume perfect knowledge of the environment, an important challenge is to account for uncertainty in perception. Existing works address the problem by making simplifying assumptions, such as linear system dynamics and bounded or Gaussian uncertainty distributions [Aoude et al., 2013, Thomas et al., 2021, Renganathan et al., 2020]. However, addressing the problem in its full generality for nonlinear dynamics and arbitrary distributions is an open problem.

In this paper, we use trajectory predictors to predict the agents’ future motion, and quantify prediction uncertainty in an adaptive and online manner from past agent observations of a single trajectory. Particularly, we use tools from the adaptive conformal prediction (ACP) literature [Gibbs and Candes, 2021, Gibbs and Candès, 2022, Zaffran et al., 2022, Bastani et al., 2022] to construct prediction regions that quantify multistep-ahead prediction uncertainty. Based on this quantification, we formulate an uncertainty-informed motion planner. Our contributions are as follows:

* We propose an algorithm that adaptively quantifies uncertainty of trajectory predictors using ACP. Our algorithm is distribution-free and applies to a broad class of trajectory predictors, providing average probabilistic coverage.

* We propose a model predictive controller (MPC) that leverages uncertainty quantifications to plan probabilistically safe paths around dynamic obstacles. Importantly, our adaptive algorithm enables us to capture and react to changes in prediction quality and the agents’ motion.

* We provide empirical evaluations of a drone avoiding a flying frisbee.

§.§ Related Work

Planning in dynamic environments has found broad interest, and non-interactive sampling-based motion planner were presented in [Phillips and Likhachev, 2011, Renganathan et al., 2022, Aoude et al., 2013, Majd et al., 2021, Kalluraya et al., 2022], while [Du Toit and Burdick, 2011, Wei et al., 2022, Wang et al., 2022, Thomas et al., 2021] propose non-interactive receding horizon planning algorithms. However, accounting for uncertainty in the agent motion is challenging.

Intent-driven models for planning among human agents have estimated agent uncertainty using Bayesian inference  [Fisac et al., 2018, Nakamura and Bansal, 2022, Fridovich-Keil et al., 2020, Bansal et al., 2020]. Model predictive control was also used in a stochastic setting to account for uncertainty under the assumption of bounded or Gaussian uncertainty [Fan et al., 2021, Nair et al., 2022, Yoon et al., 2021]. Data-driven trajectory predictors can provide mean and variance information of the predictions, which can be approximated as a Gaussian distribution [Busch et al., 2022] and used within stochastic planning frameworks [Choi et al., 2017, Omainska et al., 2021, Fulgenzi et al., 2008]. These approaches quantify prediction uncertainty in a heuristic manner for real systems as the authors make certain assumptions  on prediction algorithms and agent models and its distribution, e.g., being Gaussian. Distributionally robust approaches such as [Wei et al., 2022] are distribution free and can ensure safety at the cost of conservatism.

Data-driven trajectory predictors, such as RNNs or LSTMs, provide no information about prediction uncertainty which can lead to unsafe decisions. For this reason, prediction monitors were recently presented in [Farid et al., 2022, Luo et al., 2021] to monitor prediction quality. Especially [Luo et al., 2021]  used conformal prediction to obtain guarantees on the predictor's false negative rate. Conformal prediction was further used to obtain estimates on constraint satisfaction via neural network predictors  [Dietterich and Hostetler, 2022, Bortolussi et al., 2019, Qin et al., 2022, Lindemann et al., 2022]. Conceptually closest to our work are [Chen et al., 2020, Lindemann et al., 2022] where prediction uncertainty quantifications are  obtained using conformal prediction, and then utilized to design model predictive controllers. While the algorithm in [Chen et al., 2020] can not provide end-to-end safety guarantees,  [Lindemann et al., 2022] can provide probabilistic safety guarantees for the planner. However, changes in the distribution that describes the agents' motion can not be accounted for, e.g., when the agents' motion changes depending on the motion of the control system. Another distinct difference is that offline trajectory data is needed, while we obtain uncertainty quantifications in an adaptive manner from past agent observations of a single trajectory.

§ PROBLEM FORMULATION AND PRELIMINARIES

The dynamics of our autonomous system are governed by the discrete-time dynamical system,

\begin{align}
\label{eq:system}
x_{t+1}=f(x_t,u_t), \;\;\; x_0:=\zeta
\end{align}

where $x_t\in\mathcal{X}\subseteq\mathbb{R}^n$ and $u_t\in \mathcal{U}\subseteq \mathbb{R}^m$ denote the state and the control input at time $t\in\mathbb{N}\cup \{0\}$, respectively. The sets  $\mathcal{U}$ and $\mathcal{X}$ denote the set of permissible control inputs and the workspace of the system, respectively. The measurable function $f:\mathbb{R}^n\times\mathbb{R}^m\to \mathbb{R}^n$ describes the system dynamics and $\zeta\in\mathbb{R}^n$ is the initial condition of the system. For brevity, let $x:=(x_0,x_1,\hdots)$ denote the trajectory of (<ref>) under a given control sequence $u:=(u_0,u_1,\hdots)$.

The system operates in an environment with $N$  dynamic agents whose trajectories are a priori unknown. Let $\mathcal{D}(x)$ be an unknown distribution over agent trajectories, i.e., let
Y:=(Y_0,Y_1,\hdots)\sim \mathcal{D}(x)
describe a random trajectory where the joint agent state $Y_t:=(Y_{t,1},\hdots,Y_{t,N})$ at times $t\in\mathbb{N}\cup \{0\}$ is drawn from $\mathbb{R}^{Nn}$, i.e., $Y_{t,j}$ is the state of agent $j$ at time $t$. For instance, $Y_t$ can denote the uncertain two-dimensional positions of $N$ pedestrians at time $t$. Modeling dynamic agents by a distribution $\mathcal{D}$ provides great flexibility, and $\mathcal{D}$ can generally describe the motion of Markov decision processes.

We use lowercase letters $y_t$ when referring to a  realization of  $Y_t$, and assume at time $t$ to have access to past observations  $(y_0,\hdots,y_t)$.   We make no other assumptions on the distribution $\mathcal{D}$, and in our proposed algorithm we will predict states $(y_{t+1},\hdots,y_{t+H})$ for a prediction horizon of $H$ from $(y_0,\hdots,y_t)$ and quantify prediction uncertainty using ideas from ACP.

Given the system in (<ref>), the unknown random trajectories $Y\sim\mathcal{D}(x)$, and a failure probability $\delta\in(0,1)$, design the control inputs $u_t$ such that the Lipschitz continuous constraint function $c:\mathbb{R}^n\times\mathbb{R}^{nN}\to \mathbb{R}$ is satisfied[For an obstacle avoidance constraint, like $c(x,y):= \lVert x - y \rVert -0.5 \geq 0 $, the Lipschitz constant is 1. We implicitly assume that the constraint function is initially satisfied, i.e., that $c(x_0,y_0)\ge 0$.] with a probability of at least $1-\delta$ at each time, i.e., that

\begin{align}\label{eq:safety_constr}
\textrm{Prob}\big(c(x_\tau,Y_\tau)\ge 0\big)\ge 1-\delta\;\;\; \text{ for all } \;\;\; \tau\ge 0.
\end{align}

We note that our previous work [Lindemann et al., 2022] considers a similar problem formulation. However, in [Lindemann et al., 2022], we assume that the distribution $\mathcal{D}$ is stationary and it does not depend on the system trajectory $x$ or the environment, i.e., there is no interaction between the control system and the dynamic agents. In reality, however, a pedestrian may come to a halt if a mobile robot comes too close, resulting in a distribution shift in $\mathcal{D}$. This work is a step towards the implementation of a general framework that can adapt to such changes in the agent distribution.

To address Problem <ref>, we use trajectory predictors to predict the motion of the agents $(Y_0,Y_1,\hdots)$  to enforce the constraint (<ref>) within a MPC framework. In [Lindemann et al., 2022], we assumed the availability of validation data from $\mathcal{D}$ to build prediction regions that quantify uncertainty of trajectory predictors. In this setting, we can collect data online to adapt our uncertainty sets based on past performance of our predictor using ACP without any assumptions on the distribution of the uncertainty and exchangeability of the validation and training dataset.

By parameterizing the distribution $\mathcal{D}(x)$ by the trajectory $x$, we model potential interactions between system and  agents. This way, we can adapt to cases where the trajectory predictor (introduced next) is trained without information of $x$, i.e., without taking interactions into account.

Trajectory Predictors: Given observations $(y_0,\hdots,y_t)$ at time $t$, we want to predict future states $(y_{t+1},\hdots,y_{t+H})$ for a prediction horizon of $H$. Assume  that Predict is a function that maps observations $(y_{0},\hdots,y_t)$ to predictions $(\hat{y}_t^1,\hdots,\hat{y}_t^H)$ of $(y_{t+1},\hdots,y_{t+H})$. Note that $t$ in $\hat{y}_t^\tau$ denotes the time at which the prediction is made, while $\tau$ indicates how many steps we predict ahead. In principle, Predict can be a classical auto-regressive model or a  neural network based method.

While our proposed problem solution is compatible with any trajectory predictor Predict, we focus in the case studies on real-time updating strategies like sliding linear predictors with extended Kalman filter. Extracting a dynamics model from data is challenging, especially when the available data is limited, noisy, and partial.
[Takens, 1981] showed that the method of delays can be used to reconstruct qualitative features of the full-state, phase space from delayed partial observations. By building on our previous work using time delay embedding in dynamic obstacle avoidance ([Wei et al., 2022]), we employ a linear predictor based on spatio-temporal factorization of the delayed partial observations as the pairing trajectory predictor (See Appendix <ref>).

Adaptive Conformal Prediction (ACP): Conformal prediction is used to obtain  prediction regions for  predictive models, e.g., neural networks, without making assumptions on the underlying distribution or the predictive model [Vovk et al., 2005, Shafer and Vovk, 2008, Angelopoulos and Bates, 2021]. Let $R_1,\hdots,R_{t+1}$ be $t+1$ independent and identically distributed (i.i.d.) random variables. The goal in conformal prediction is to obtain a prediction region of $R_{t+1}$ based on $R_1,\hdots,R_{t}$. Formally, given a failure probability $\delta\in (0,1)$, we want to obtain a  prediction region $C$ such that

\begin{align*}
\textrm{Prob}(R_{t+1}\le C)\ge 1-\delta.
\end{align*}

We refer to $R_i$ also as the  nonconformity score. For supervised learning, we can select $R_i:=\|Z_i-\mu(X_i)\|$ where $\mu$ is the predictor so that a large nonconformity score indicates a poor predictive model. By a  quantile argument, see <cit.>, we can obtain $C$ to be the $(1-\delta)$th quantile of the empirical distribution of the values $R_1,\hdots,R_{t}$ and $\infty$. Calculating the $(1-\delta)$th quantile can be done by assuming that $\bar{R}_1,\hdots,\bar{R}_{t}$ correspond to the values of $R_1,\hdots,R_{t}$, but instead sorted in non-decreasing order ($\bar{R}$ refers to the order statistic of $R$), i.e., for each $\bar{R}_i$ there exists exactly one $R_j$ such that $\bar{R}_i=R_j$ and $\bar{R}_{i+1}\ge \bar{R}_i$. By setting $q:=\lceil (t+1)(1-\delta)\rceil\le t$, we  obtain the $(1-\delta)$th quantile as $C:=\bar{R}_{q}$, i.e., the $q^{\text{th}}$ smallest nonconformity score.

The underlying assumption in conformal prediction is that $R_1,\hdots,R_{t+1}$ are exchangeable (exchangeability includes i.i.d. data). This is an unreasonable assumption for time-series prediction where $R_t$ may denote the nonconformity score at time $t$. To address this issue, ACP was introduced in [Gibbs and Candes, 2021, Gibbs and Candès, 2022, Zaffran et al., 2022, Bastani et al., 2022]. The idea is now to obtain a prediction region $C_{t+1}$ adaptively so that $\textrm{Prob}(R_{t+1}\le C_{t+1})\ge 1-\delta$ for each time $t$. In fact, the prediction region is now obtained as $C_{t+1}:=\bar{R}_{q_{t+1}}$ where $q_{t+1}:=\lceil (t+1)(1-\delta_{t+1})\rceil$ depends on the variable $\delta_{t+1}$ that is adapted online based on observed data.  In this way, the prediction region $C_{t+1}$ becomes a tuneable parameter by the choice of $\delta_{t+1}$. To adaptively obtain the parameter $\delta_{t+1}$, ideas from online learning are used and we update $\delta_{t+1}$ as

\begin{align}\label{eq:adapt_upd_rule}
\delta_{t+1}:=\delta_{t}+\gamma(\delta-e_{t})
\; \text{ with }\; e_{t}:=\begin{cases}
0 &\text{if }\, r_{t}\le C_{t}\\
1 &\text{otherwise}
\end{cases}
\end{align}

where we denote by $r_{t}$ the observed realization of $R_{t}$ and where $\gamma$ is a learning rate. The idea is to use $\delta_{t+1}$ to adapt to changes in the distribution of $R_1,\hdots,R_{t+1}$ over time by using information on how much the prediction region $C_{t}$ overcovered ($r_{t}\ll C_{t}$) or undercovered ($r_{t}\gg C_{t}$) in the past.

One of the main performance enhancers is the proper choice of $\gamma$. In [Gibbs and Candès, 2022], the authors present fully adaptive conformal prediction (FACP) where a set of learning rates $\{\gamma_i\}_{1\leq i \leq k}$ is used in parallel from which the best $\gamma$ is selected adaptively. Based on past performance (using a reweighting scheme that evaluates which $\gamma_i$ provided the best coverage), the authors maintain a belief $p_t^{(i)}$ at each time step $t$ for each  $\{\delta_t^{(i)}\}_{1\leq i \leq k}$. The new update laws are

\delta^{(i)}_{t+1}:=\delta^{(i)}_{t}+\gamma_i(\delta-e^{(i)}_{t})
\; \text{ with }\; e^{(i)}_{t}:=\begin{cases}
0 &\text{if }\, r_{t}\le C^{(i)}_{t}\\
1 &\text{otherwise}
\end{cases}$$

where the individual prediction regions are $C^{(i)}_{t}:=\bar{R}_{q^{(i)}_{t}}$ with $q^{(i)}_{t}:=\lceil (t+1)(1-\delta^{(i)}_{t})\rceil$, while the best prediction region is  $C_{t}:=\bar{R}_{q_{t}}$ with $q_{t}:=\lceil (t+1)(1-\sum_{i=1}^{k}p_t^{(i)}\delta^{(i)}_{t})\rceil$.

§ ADAPTIVE CONFORMAL PREDICTION REGIONS FOR TRAJECTORY PREDICTIONS

Recall that we can obtain predictions  $(\hat{y}_t^1,\hdots,\hat{y}_t^H)$  at time $t$ of future agent states  $(Y_{t+1},\hdots,Y_{t+H})$ from past observations $(y_{0},\hdots,y_t)$ using the Predict function. Note, however, that these point predictions contain no information about prediction uncertainty and can hence not be used to  reason about the safety constraint (<ref>). To tackle this issue, we aim to construct prediction regions for $(Y_{t+1},\hdots,Y_{t+H})$ using ideas from ACP.

To obtain  prediction regions for $(Y_{t+1},\hdots,Y_{t+H})$,  we could consider the nonconformity score $\|Y_{t+\tau}-\hat{y}_t^\tau\|$ at time $t$ that captures the multistep-ahead prediction error for each $\tau\in\{1,\hdots,H\}$. A large nonconformity score indicates that the prediction $\hat{y}_t^\tau$ of $Y_{t+\tau}$ is not accurate, while a small score indicates an accurate prediction. For each $\tau$, we wish to obtain a prediction region $C_t^\tau$ that is again defined by an update variable $\delta_t^\tau$. Note, however, that we can not evaluate $\|y_{t+\tau}-\hat{y}_t^\tau\|$ at time $t$ as only measurements $(y_0,\hdots,y_t)$ are known, but not $(y_{t+1},\hdots,y_{t+H})$. Consequently, we cannot use the update rule (<ref>) to update $\delta_{t}^\tau$, as the error $e_t^\tau$ would depend on checking if $\|y_{t+\tau}-\hat{y}_{t}^\tau\|\le C_{t}^\tau$. To address this issue, we define the time  lagged nonconformity score

\begin{align*}
\end{align*}

that we can evaluate at time $t$ so that we can use the update rule (<ref>). This nonconformity score $R_t^\tau$ is time lagged in the sense that, at time $t$, we evaluate the $\tau$ step-ahead prediction error that was made $\tau$ time steps ago. We can now update the parameter $\delta_{t+1}^\tau$ that defines $C_{t+1}^\tau$ as

\begin{align}\label{eq:recursion}
\delta_{t+1}^\tau:=\delta_{t}^\tau+\gamma(\delta-e_{t}^\tau)
\; \text{ with }\; e_{t}^\tau:=\begin{cases}
0 &\text{if }\, \|y_{t}-\hat{y}_{t-\tau}^\tau\|\le C_{t}^\tau\\
1 &\text{otherwise.}
\end{cases}
\end{align}

To  compute the prediction region $C_{t+1}^\tau$, note that we can not compute $R_1^\tau,\hdots,R_{\tau-1}^\tau$. Therefore, with minor change, we let $C_{t+1}^\tau$ be the $\lceil(t-\tau+1)(1-\delta_{t+1}^\tau)\rceil^{\text{th}}$ smallest value of $(R_\tau^\tau,\hdots,R_{t}^\tau)$[Instead of keeping track of all  data, we will choose  a sliding window of the $N$ most recent data. For all prediction regions, we will then consider $(R_{t-N}^\tau,\hdots,R_{t}^\tau)$ and compute $C_{t+1}^\tau$ as the $\lceil(N+1)(1-\delta_{t+1}^\tau)\rceil^{\text{th}}$ smallest value.].

By obtaining a prediction region for $R_{t+1}^\tau$ using ACP, we obtain a prediction region for the $\tau$ step-ahead prediction error that was made $\tau-1$ time steps ago, i.e., for $\|Y_{t+1}-\hat{y}_{t+1-\tau}^\tau\|$. Under the assumption that $R_{t+1}^\tau$ and $R_{t+\tau}^\tau$ are independent and identically distributed, $R_{t+1}^\tau$ serves as a prediction region for $\tau$ step-ahead prediction error that was made $0$ time steps ago (now at time $t$), i.e., for $R_{t+\tau}^\tau$ which encodes $\|Y_{t+\tau}-\hat{y}_{t}^\tau\|$. Naturally, in our setting $R_{t+1}^\tau$ and $R_{t+\tau}^\tau$ are not independent and identically distributed, but it still serves as a good measure for the prediction region $R_{t+\tau}^\tau$. We remark that for the theoretical guarantees that we provide in the next section, only the one step-ahead prediction errors are relevant.

Let $\gamma$ be a learning rate, $\delta_0^1\in (0,1)$ be an initial value for the recursion (<ref>), and $T$ be the number of times that we compute the recursion (<ref>). Then, for the onestep-ahead prediction errors, it holds that

\begin{align}\label{eq:thm1}
1-\delta-p_1 \leq \frac{1}{T}\sum_{t=0}^
{T-1} \textrm{Prob}(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1)\leq 1-\delta+p_2
\end{align}

with constants $p_1:=\frac{\delta_0^1+ \gamma}{T\gamma}$, $p_2:=\frac{(1-\delta_0^1)+ \gamma}{T\gamma}$ so that $\lim_{T\rightarrow\infty}p_1 =0$ and $\lim_{T\rightarrow\infty}p_2 =0$.

Since the probability of an event is equivalent to the expected value of the indicator function of that event, it follows by the definition of the error $e_{t+1}^1$ that

\begin{align}\label{eq:proof1}
\textrm{Prob}(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1)= \mathbb{E}[1-e_{t+1}^1] = 1-\mathbb{E}[e_{t+1}^1].
%\mathbb{P}(\|y_{t}-\hat{y}_{t-\tau}^\tau\|\le C_{t-\tau-1}^\tau \, | \, )
\end{align}

For a given initialization $\delta_0^\tau$ and learning rate $\gamma$, we know from <cit.> that the following bound holds (with probability one) for the misclassification errors

\begin{align*}
\;\;\;\frac{-(1-\delta_0^1)+ \gamma}{T\gamma}&\leq \frac{1}{T}\sum_{t=0}^
{T-1} e_{t+1}^1 -\delta \leq \frac{\delta_0^1+ \gamma}{T\gamma}
\implies \Big|\frac{1}{T}\sum_{t=0}^
{T-1} e_{t+1}^1 -&\delta\Big| \leq \frac{\max(\delta_0^1,1-\delta_0^1)+ \gamma}{T\gamma}.
\end{align*}

Hence, taking the expectation of the above two-sided inequality, we get that

\begin{align*}
\frac{-(1-\delta_0^1)+ \gamma}{T\gamma} &\leq \frac{1}{T}\sum_{t=0}^
{T-1} \mathbb{E}[e_{t+1}^1] -\delta \leq \frac{\delta_0^1+ \gamma}{T\gamma},\\
\overset{(a)}{\Leftrightarrow}\;\;\;\frac{-(1-\delta_0^1)+ \gamma}{T\gamma} &\leq\frac{1}{T}\sum_{t=0}^
{T-1} \big(1-\textrm{Prob}(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1)\big)-\delta \leq  \frac{\delta_0^1+ \gamma}{T\gamma},\\
\Leftrightarrow\;\;\;1-\delta + \frac{(1-\delta_0^1)+ \gamma}{T\gamma} &\geq \frac{1}{T}\sum_{t=0}^
{T-1} \textrm{Prob}(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1) \geq 1-\delta - \frac{\delta_0^1+ \gamma}{T\gamma},
\end{align*}

where we used equation (<ref>) for the equivalence in (a).

The above result can be similarly extended to the FACP case with a set of candidate learning rates, $\gamma$, <cit.>.

To illustrate these multistep-ahead prediction regions, consider a planar double pendulum whose dynamics are governed by chaotic, nonlinear dynamics that are sensitive to the initial condition <cit.>.

We study the predictions made by a linear predictor that uses noisy observations of the position of the double pendulum (See Appendix <ref>)

and use ACP to predict the uncertainty in the predictions. Both the trajectory predictor and the uncertainty quantification using ACP use online data from a single trajectory. ACP provides the multi-step errors in the linear predictions with a coverage level of $\delta = 0.1$, and learning rates $\gamma = \begin{pmatrix}
0.0008 & 0.0015 & 0.003 & 0.005& 0.009 & 0.017 &0.03 & 0.05 &0.08
\end{pmatrix}.$

Figure <ref> compares the 1-step and 6-step ahead error prediction regions to the true multi-step errors for two states, the second mass position, $x_2, y_2$. The percentages of one-step errors that are incorrectly predicted, i.e., $e_t^1 = 1$, for the positions of each mass, $x_1, x_2, y_1, y_2$ are $2.36\%, 0.94\%, 1.57 \%, 1.73\%$  respectively. We can see the effects of adaptation as the ACP prediction regions are larger in areas of poor performance of the linear predictor (and consequently higher error in the prediction) and smaller in regions where the linear predictor performs well.

The multi-step prediction errors are shown for two of the six states of a double pendulum ($x_2, y_2$). ACP can correctly predict regions of high and low error ($90\%$ coverage regions) by adjusting the prediction quantile using update law (<ref>). The orange lines are the true multi-step prediction errors and the blue areas are the error regions predicted by ACP.

§ UNCERTAINTY-INFORMED MODEL PREDICTIVE CONTROL

Based on the obtained uncertainty quantification from the previous section, we propose an uncertainty-informed model predictive controller (MPC) that uses predictions $\hat{y}_t^\tau$ and adaptive prediction regions $C_{t+1}^\tau$. The underlying optimization problem that is solved at every time step $t$ is:

\begin{align}
\min_{(u_t,\hdots,u_{t+H-1})}& \sum_{k=t}^{t+H-1}J(x_{k+1},u_k) &\\
\text{s.t.}\qquad & x_{k+1}=f(x_k,u_k), &k\in\{t,\hdots,t+H-1\}\\
& c(x_{t+\tau},\hat{y}_t^\tau)\ge LC_{t+1}^\tau,&\tau\in\{1,\hdots,H\}\label{eq:constC_2}\\
& u_k \in \mathcal{U},x_{k+1} \in \mathcal{X},&k\in\{t,\hdots,t+H-1\}
\end{align}

where $L$ is the Lipschitz constant of the constraint function $c$, $J$ is a step-wise cost function, and  $u_t,\hdots,u_{t+H-1}$ is the control sequence. The optimization problem in (<ref>) is convex if the functions $J$ and $f$ are convex, the function $c$ is convex in its first argument, and the sets $\mathcal{U}$ and $\mathcal{X}$ are convex.

Based on this optimization problem, we propose a receding horizon control strategy in Algorithm <ref>. In line 1 of Algorithm <ref>, we initialize the parameter $\delta_0^t$ simply to $\delta$. Lines 2-11 present the real-time planning loop by: 1) updating the states $x_t$ and $y_t$ and calculating new predictions $\hat{y}_{t}^\tau$ (lines 3-4), 2) computing the adaptive nonconformity scores $C_{t+1}^\tau$ (lines 5-9), and 3) solving the optimization problem in (<ref>) of which we apply only $u_t$ (lines 10-11).

[1]
Input:  Failure probability $\delta$, prediction horizon $H$, learning rate $\gamma$
Output:  Control input $u_t(x_t,y_0,\hdots,y_t)$ at each time $t$
$\delta_0^\tau \gets \delta$ for $\tau\in\{1,\hdots,H\}$
$t$ from $0$ to $\infty$   # real-time motion planning loop
Update $x_t$ and  $y_t$
Obtain predictions $\hat{y}_t^\tau$ for $\tau\in\{1,\hdots,H\}$
$\tau$ from $1$ to $H$   # compute ACP regions
$\delta_{t+1}^\tau \gets \delta_{t}^\tau+\gamma(\delta-e_{t}^\tau)$
$q \gets \big\lceil (t+1)(1-\delta_{t+1}^\tau)\big\rceil$
Set $C_{t+1}^\tau$ as the $q$th smallest value of $(R_\tau^\tau,\hdots,R_t^\tau)$
Calculate controls $u_t,...,u_{t+H-1}$ as the solution of (<ref>)
Apply $u_t$ to (<ref>)

MPC with ACP Regions

While Algorithm <ref> uses a single learning rate, one can similarly extend the above algorithm to be fully adaptive using a candidate set of $\{\gamma_i\}_{1\leq i\leq k}$ without loss of generality.

assume that when $\delta_{t+1} \leq 0$, the prediction region $C_{t+1}\rightarrow \infty$. This means that when the algorithm requires robust behavior, the $\infty$-prediction region ensures that any prediction at the next time-step should be correctly classified. For a physical system, there are limits on how much the dynamic obstacle can accelerate in one time-step which gives us an upper bound $R_{\text{max}}< \infty$ on the worst-case error. In practice, we enforce $0\leq\delta_{t+1}\leq 1$ with $C_{t+1}\leq R_{\text{max}}$.

If the MPC optimization is recursively feasible, Algorithm <ref> will provide a controller that collides with the dynamic obstacle with at most the following average probability. By assumption, the optimization problem (<ref>) is feasible at each time $t\in \{0,1,\hdots\}$. Due to constraint (<ref>) and Lipschitz continuity of $c$, it hence holds that

\begin{align*}
0&\le c(x_{t+1},\hat{y}_{t}^1)- LC_{t+1}^1\\
&\le c(x_{t+1},Y_{t+1})+L\|Y_{t+1}-\hat{y}_{t}^1\|- LC_{t+1}^1=:p(x_{t+1},Y_{t+1})
\end{align*}

at each time $t\in \{0,1, \hdots\}$. If we now know that $P(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1))\ge 1-\delta$, then we know that $P(c(x_{t+1},Y_{t+1})\ge 0)\ge 1-\delta$. In this adaptive setting, we can not guarantee $P(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1))\ge 1-\delta$, but we know from Theorem <ref> that (<ref>) holds, and, consequently, by taking the limit at $t\to\infty$, we know that

\begin{align*}
\lim_{T\xrightarrow[]{}\infty}\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}(\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1)  \geq 1-\delta,
\end{align*}

i.e., on average we have the desired prediction accuracy with a probability greater than $1-\delta$.

If the MPC optimization is recursively feasible, Algorithm <ref> will provide a controller that collides with the dynamic obstacle with atmost the following average probability,

\begin{align}
\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)< LC_{t-\tau}^\tau\big) \leq \delta + \frac{1-\delta_0^\tau+ \gamma}{T\gamma} \qquad \qquad \forall \tau\in\{1, \dotsc, H\}.
\end{align}

Using the Law of Total Probability, we have,

\begin{align*}
\textrm{Prob}&\big(c(x_{t+\tau-1},\hat{y}_t^\tau)\ge LC_{t-\tau}^\tau\big) \\&=
\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)\ge LC_{t-\tau}^\tau \,\big\vert \, \lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert\le C_{t-\tau}^\tau\big)\textrm{Prob}(\lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert\le C_{t-\tau}^\tau) + \\ &\qquad\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)\ge LC_{t-\tau}^\tau \,\big\vert \, \lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert> C_{t-\tau}^\tau\big)\textrm{Prob}(\lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert> C_{t-\tau}^\tau) \\
&\geq \textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)\ge LC_{t-\tau}^\tau  \,\big\vert \, \lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert\le C_{t-\tau}^\tau\big)\textrm{Prob}(\lVert y_{t}-\hat{y}_{t-\tau}^\tau\rVert\le C_{t-\tau}^\tau) \\
&= \textrm{Prob}(\|y_{t}-\hat{y}_{t-\tau}^\tau\|\le C_{t-\tau}^\tau)\\
&= \mathbb{E}(1-e_t^\tau) = 1-\mathbb{E}(e_t^\tau).
%\mathbb{P}(\|y_{t}-\hat{y}_{t-\tau}^\tau\|\le C_{t-\tau-1}^\tau \, | \, )
\end{align*}

We know from [Gibbs and Candes, 2021] that the following bound holds for the misclassification errors, for a given initialization $\delta_0^\tau$ and learning rate $\gamma$,

\begin{align*}
\frac{-\delta_0^\tau + \gamma}{T\gamma} \leq \frac{1}{T}\sum_{t=1}^
{T} e_t^\tau -\delta \leq \frac{1-\delta_0^\tau+ \gamma}{T\gamma} \qquad \qquad \forall \tau\in\{1, \dotsc, H\}.
\end{align*}

Hence, taking the expectation of the above set of inequalities, we get,

\begin{align*}
{T} \mathbb{E}[e_t^\tau] -\delta \leq \frac{1-\delta_0^\tau+ \gamma}{T\gamma},\\
{T} \bigg(1-\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)\ge LC_{t-\tau}^\tau\big)\bigg)-\delta  \leq \frac{1}{T}\sum_{t=1}^
{T} \mathbb{E}[e_t^\tau] -\delta \leq \frac{1-\delta_0^\tau+ \gamma}{T\gamma}, \\
{T}\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)< LC_{t-\tau}^\tau\big) -\delta \leq \frac{1-\delta_0^\tau+ \gamma}{T\gamma} \qquad \qquad \forall \tau\in\{1, \dotsc, H\}.
\end{align*}

This gives us the following asymptotic guarantee on obstacle avoidance,

\begin{align*}
\lim_{T\xrightarrow[]{}\infty}\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}\big(c(x_{t+\tau-1},\hat{y}_t^\tau)< LC_{t-\tau}^\tau\big) \leqas \delta.
\end{align*}

Moreover, it's clear that the above guarantee holds with equality for the prediction regions obtained from ACI, i.e.,

\begin{align*}
\lim_{T\xrightarrow[]{}\infty}\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}(\|y_{t}-\hat{y}_{t-\tau}^\tau\|> C_{t-\tau}^\tau) \equalas \delta \qquad \qquad \forall \tau\in\{1, \dotsc, H\}.
\end{align*}

Let $\gamma$ be a learning rate, $\delta_0^1\in (0,1)$ be an initial value for the recursion (<ref>), and $T$ be the number of times that we compute the recursion (<ref>). If the optimization problem (<ref>) in Algorithm <ref> is recursively feasible, then Algorithm <ref> will lead to

\begin{align}
\frac{1}{T}\sum_{t=0}^
{T-1}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge  0\big) \geq 1-\delta - p_1
\end{align}

with constant $p_1:=\frac{\delta_0^1+ \gamma}{T\gamma}$ so that $\lim_{T\rightarrow\infty}p_1 =0$.

By assumption, the optimization problem in (<ref>) is feasible at each time $t\in \{0,1,\hdots\}$. Due to constraint (<ref>) and Lipschitz continuity of $c$, it hence holds that

\begin{align}\label{eq:proof2}
0&\le c(x_{t+1},\hat{y}_{t}^1)- LC_{t+1}^1\le c(x_{t+1},Y_{t+1})+L\|Y_{t+1}-\hat{y}_{t}^1\|- LC_{t+1}^1
\end{align}

at each time $t\in \{0,1, \hdots\}$. Consequently, note that $\|Y_{t+1}-\hat{y}_{t}^1\|\le C_{t+1}^1$ is a sufficient condition for  $c(x_{t+1},Y_{t+1})\ge 0$. In a next step, we can derive that

\begin{align*}
\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0\big) &\overset{(a)}{=}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0 \,\big\vert \, \lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1\big)\textrm{Prob}(\lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1)  \\ &\qquad \hspace{-0.75cm}+\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0 \,\big\vert \, \lVert Y_{t+1}-\hat{y}_{t}^1\rVert> C_{t}^1\big)\textrm{Prob}(\lVert Y_{t+1}-\hat{y}_{t}^1\rVert> C_{t}^1) \\
&\overset{(b)}{\geq}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0  \,\big\vert \, \lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1\big)\textrm{Prob}(\lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1) \\
&\overset{(c)}{=} \textrm{Prob}(\lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1)
% &= \mathbb{E}[1-e_{t+1}^1] = 1-\mathbb{E}[e_{t+1}^1].
%\mathbb{P}(\|y_{t}-\hat{y}_{t-\tau}^\tau\|\le C_{t-\tau-1}^\tau \, | \, )
\end{align*}

where the equality in (a) follows from the law of total probability, while the inequality in (b)  follows from the nonnegativity of probabilities. The equality in (c) follows as $\textrm{Prob}(c(x_{t+1},Y_{t+1})\ge 0  \,\vert \, \lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1)=1$ since $\lVert Y_{t+1}-\hat{y}_{t}^1\rVert\le C_{t}^1$ implies $c(x_{t+1},Y_{t+1})\ge 0$ according to  (<ref>). We now use the result from Theorem <ref> to complete the proof.

This gives us the following asymptotic guarantee on obstacle avoidance,

\begin{align*}
\lim_{T\xrightarrow[]{}\infty}\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0\big) \geq 1-\delta.
\end{align*}

remark equality of Theorem 3 vs inequality of thm 7

This gives us the following asymptotic guarantee on obstacle avoidance,

\begin{align*}
{T}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})< 0\big) \leq \delta\\
& \lim_{T\xrightarrow[]{}\infty}\frac{1}{T}\sum_{t=1}^
{T}\textrm{Prob}\big(c(x_{t+1},Y_{t+1})\ge 0\big) \geq 1-\delta
\end{align*}

§ CASE STUDIES: MULTIROTOR OPERATING IN SMALL ANGLE REGIME DODGING A FLYING FRISBEE

We compare the performance of the MPC with ACP uncertainty prediction regions with our past work that uses a distributionally robust approach to uncertainty quantification <cit.>. We use the same multirotor operating in the presence of a moving obstacle example with a MPC planner. The multirotor is constrained to operate within the state constraints
$\theta\in [-0.45,0.45]$ radians and $\varphi \in [-0.45,0.45]$  radians. We use the following standard multirotor linear dynamics,

\begin{align} \label{eq:sim_agent_dyn2}
\ddot{x}= -g\theta, \, \,
\ddot{y} = g\varphi,\,\, \ddot{z}=u_1 -g, \,\,
\ddot{\varphi} = \frac{u_2}{I_{xx}},\,\, \ddot{\theta} = \frac{u_3}{I_{yy}},\,\, \ddot{\psi} = \frac{u_4}{I_{zz}},\vspace{-3mm}
\end{align}

where the planner control inputs $u_1, u_2, u_3, u_4$ correspond to the thrust force in the body frame and three moments. The vehicle's moments of inertia are $I_{xx} = 0.0075 kgm^2, I_{yy} = 0.0075 kgm^2, I_{zz} = 0.013kgm^2$. The MPC planner has a horizon length of 10 steps and the planner is updated at 20 Hz. It is implemented through a Sequential Convex Programming approach <cit.>.

Numerical simulations of the proposed MPC planner with ACP regions and dynamics (<ref>) are presented as it avoids a Frisbee that is thrown at the drone from various initial positions, velocities, and rotation speed. The Frisbee is modeled following [Hummel, 2003], and we implement linear predictions of the trajectory arising from its nonlinear dynamics.

We conducted 1000 Monte Carlo simulations per allowed failure probability level $\delta$ to compare the numerical feasibility, percentage of success in obstacle avoidance (if the MPC planner is feasible), and the planner's conservativeness, as measured by the minimum distance between the obstacle and agent centers, i.e., $\bar{d}_{min}$ and  $\sigma({d_{min}})$ describe the average and standard deviation of this minimum distance across simulations, respectively. We compare three uncertainty quantification techniques in Table <ref>, (1) The proposed ACP method (Algorithm <ref>), (2) empirical bootstrap prediction that accounts for the uncertainty in the predictions using the empirical bootstrap variance <cit.>, and (3) the sliding linear predictor with an Extended Kalman Filter (EKF) that approximates the uncertainty in the obstacle predictions as a Gaussian distribution (See Appendix <ref>).

Discussion:  Table <ref> shows that our proposed method can successfully avoid the Frisbee, while using a significantly smaller average divergence distance ($d_{min}, \,\sigma({d_{min}})$) from the Frisbee. I.e., our approach avoids the conservatism of other approaches due to the adaptivity of the uncertainty sets.

Our method can usefully adjust the prediction sets when the underlying uncertainty distribution is shifting (due to discrepancy in the linear dynamic predicted and the true nonlinear obstacle motion). We also note that the feasibility of the MPC optimization is worse for our method compared to [Wei et al., 2022] and the EKF predictor. This issue arises during sudden changes in the size of the uncertainty sets when the learning rate $\gamma$ is chosen too large. We will investigate this issue in future work by considering tools to ensure recursive feasibility <cit.> or by providing backup controllers <cit.> when the MPC is infeasible.

Case    $\delta$         $0.025$          $0.05$

UQ method      Proposed     [Wei et al., 2022]     w/EKF     Proposed      [Wei et al., 2022]     w/EKF

$\%$Feas.                   83.8   87.4      97.1    80.9   90.3   97.6

Frisbee     $\%$Succ.       99.2   100    100    100   100   100

w/drag     $\overline{d}_{min}$    2.91   14.2    5.27    2.74   4.97   4.25
$\sigma(d_{min})$               1.25   2.04    1.28    1.3   1.97   1.11

Summary of results from MC simulations of system (<ref>). We used FACP for predicting uncertainty sets with learning rates $\gamma = \{0.0008,\, 0.0015,\, 0.003,\, 0.005,\, 0.009,\, 0.017,\,0.03,\,0.05,\,0.08,\, 0.13 \} $ and using the last $30$ measurements of the obstacle.

CARLA Simulations for Pedestrian Motion Prediction using LSTMs. We evaluate our MPC and ACP planning framework in the autonomous driving simulator CARLA on an intersection containing four pedestrians with random initial and goal positions. The pedestrians randomly speed up and slow down at a fixed time in the middle of each trial, which is something that our previous work from [Lindemann et al., 2022] would not be able to handle. We used the LSTM trajectory predictor from our previous work [Lindemann et al., 2022]. The simulator runs at 20Hz, while the LSTM and MPC run at 2Hz. The MPC uses standard double integrator dynamics to generate waypoints that get fed to PID controllers that control the car's throttle and steering angle. The LSTM has an observation window of 3 seconds and a prediction horizon of 5 seconds. The MPC uses a planning horizon of 5 seconds.

For the ACP, learning rates $\gamma = \{ 0.0008, 0.0015, 0.003, 0.005, 0.009, 0.017, 0.03, 0.05, 0.08\}$ and a desired coverage of 0.9 were used. At the beginning of each trial, we collect 20 seconds of pedestrian data, which corresponds to 40 data points, before beginning the FACP and MPC. We ran  ... trials of the scenario. One such trial is show in <ref>. For all  ... trials the car reached the goal location while avoiding the pedestrians. The ACP region coverage across all trials for the $10$ look ahead prediction horizons (0.5 seconds to 5 seconds) are given somewhere. Finally, the 1 step look ahead and 8 step look ahead error and prediction region sizes are shown over time for a trial in Figure <ref>. The prediction errors spike when the pedestrians speed up, but for the 0.5 second prediction the ACP is quickly able to react by increasing its prediction region. However, the ACP for the 4 second prediction window takes much longer to increase it's prediction region. That is because there is a 4 second delay between when the prediction get made and the ACP algorithm seeing what the error was. This highlights one potential drawback of the ACP approach, which is that the longer it takes for the algorithm to get real-time feedback about the predictions, the longer it will take to adapt to distribution shifts.

The change of pedestrian speed is not something that the offline conformal prediction from our previous work in [Lindemann et al., 2022] could properly capture, unless it was explicitly encoded in the offline validation data. Even then, note that the LSTM errors for the different speeds are slightly different. This would lead to larger conformal regions even when the pedestrians are travelling at lower speeds. On the other hand, our adaptive approach can alter it's prediction regions to be smaller when the pedestrians are travelling at low speeds and higher when the pedestrians are travelling at high speed.

The car (black dot) navigating an intersection with pedestrians (red stars). The LSTM predictions are shown as green dots and the ACP prediction regions are shown as green circles. The blue line shows the desired MPC path. In between the second and third subfigure, the pedestrians all speed up, which causes the predictions regions to rapidly expand to account for the new prediction errors.

§ CONCLUSION

We presented an algorithm for safe motion planning in an environment with other dynamic agents using ACP. Specifically, we considered a deterministic control system that uses state predictors to estimate the future motion of dynamic agents. We then  leveraged ideas from ACP to dynamically quantify prediction uncertainty from an online data stream, and designed an uncertainty-informed model predictive controller to safely navigate among dynamic agents. In contrast to other data-driven prediction models that quantify prediction uncertainty in a heuristic manner, we quantify the true prediction uncertainty in a distribution-free, adaptive manner that even allows to capture changes in prediction quality and the agents' motion.

Lars Lindemann, Matthew Cleaveland, and George J. Pappas were generously supported by NSF award CPS-2038873. The work of Anushri Dixit and Skylar Wei was supported in part by DARPA, through the LINC program.

[Agarwal et al., 2020]
Anish Agarwal, Abdullah Alomar, and Devavrat Shah.
On multivariate singular spectrum analysis and its variants, 2020.
URL <https://arxiv.org/abs/2006.13448>.

[Angelopoulos and Bates, 2021]
Anastasios N Angelopoulos and Stephen Bates.
A gentle introduction to conformal prediction and distribution-free
uncertainty quantification.
arXiv preprint arXiv:2107.07511, 2021.

[Aoude et al., 2013]
Georges S Aoude, Brandon D Luders, Joshua M Joseph, Nicholas Roy, and
Jonathan P How.
Probabilistically safe motion planning to avoid dynamic obstacles
with uncertain motion patterns.
Autonomous Robots, 350 (1):0 51–76, 2013.

[Bansal et al., 2020]
Somil Bansal, Andrea Bajcsy, Ellis Ratner, Anca D Dragan, and Claire J Tomlin.
A hamilton-jacobi reachability-based framework for predicting and
analyzing human motion for safe planning.
In 2020 IEEE International Conference on Robotics and
Automation (ICRA), pages 7149–7155. IEEE, 2020.

[Bastani et al., 2022]
Osbert Bastani, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam,
and Aaron Roth.
Practical adversarial multivalid conformal prediction.
arXiv preprint arXiv:2206.01067, 2022.

[Bortolussi et al., 2019]
Luca Bortolussi, Francesca Cairoli, Nicola Paoletti, Scott A Smolka, and
Scott D Stoller.
Neural predictive monitoring.
In International Conference on Runtime Verification, pages
129–147. Springer, 2019.

[Busch et al., 2022]
Finn Lukas Busch, Jake Johnson, Edward L. Zhu, and Francesco Borrelli.
A gaussian process model for opponent prediction in autonomous
racing, 2022.
URL <https://arxiv.org/abs/2204.12533>.

[Chen et al., 2020]
Yuxiao Chen, Ugo Rosolia, Chuchu Fan, Aaron D Ames, and Richard Murray.
Reactive motion planning with probabilistic safety guarantees.
arXiv preprint arXiv:2011.03590, 2020.

[Choi et al., 2017]
Sungjoon Choi, Eunwoo Kim, Kyungjae Lee, and Songhwai Oh.
Real-time nonparametric reactive navigation of mobile robots in
dynamic environments.
Robotics and Autonomous Systems, 91:0 11–24, 2017.

[Dietterich and Hostetler, 2022]
Thomas G Dietterich and Jesse Hostetler.
Conformal prediction intervals for markov decision process
arXiv preprint arXiv:2206.04860, 2022.

[Du Toit and Burdick, 2011]
Noel E Du Toit and Joel W Burdick.
Robot motion planning in dynamic, uncertain environments.
IEEE Transactions on Robotics, 280 (1):0
101–115, 2011.

[Everett et al., 2021]
Michael Everett, Yu Fan Chen, and Jonathan P How.
Collision avoidance in pedestrian-rich environments with deep
reinforcement learning.
IEEE Access, 9:0 10357–10377, 2021.

[Fan et al., 2021]
D.D. Fan, K. Otsu, Y. Kubo, A. Dixit, J.W. Burdick, and A.-A. Agha-Mohammadi.
Step: Stochastic traversability evaluation and planning for
risk-aware off-road navigation.
In Robot.: Sci. Syst, 2021.

[Farid et al., 2022]
Alec Farid, Sushant Veer, Boris Ivanovic, Karen Leung, and Marco Pavone.
Task-relevant failure detection for trajectory predictors in
autonomous vehicles.
arXiv preprint arXiv:2207.12380, 2022.

[Fisac et al., 2018]
Jaime F Fisac, Andrea Bajcsy, Sylvia L Herbert, David Fridovich-Keil, Steven
Wang, Claire J Tomlin, and Anca D Dragan.
Probabilistically safe robot planning with confidence-based human
In 14th Robotics: Science and Systems, RSS 2018. MIT Press
Journals, 2018.

[Fox et al., 1997]
Dieter Fox, Wolfram Burgard, and Sebastian Thrun.
The dynamic window approach to collision avoidance.
IEEE Robotics & Automation Magazine, 40 (1):0
23–33, 1997.

[Fridovich-Keil et al., 2020]
David Fridovich-Keil, Andrea Bajcsy, Jaime F Fisac, Sylvia L Herbert, Steven
Wang, Anca D Dragan, and Claire J Tomlin.
Confidence-aware motion prediction for real-time collision
The International Journal of Robotics Research, 390
(2-3):0 250–265, 2020.

[Fulgenzi et al., 2008]
Chiara Fulgenzi, Christopher Tay, Anne Spalanzani, and Christian Laugier.
Probabilistic navigation in dynamic environment using
rapidly-exploring random trees and gaussian processes.
In 2008 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 1056–1062. IEEE, 2008.

[Gavish and Donoho, 2014]
Matan Gavish and David L. Donoho.
The optimal hard threshold for singular values is $4/\sqrt {3}$.
IEEE Transactions on Information Theory, 600
(8):0 5040–5053, 2014.

[Gibbs and Candes, 2021]
Isaac Gibbs and Emmanuel Candes.
Adaptive conformal inference under distribution shift.
Advances in Neural Information Processing Systems,
34:0 1660–1672, 2021.

[Gibbs and Candès, 2022]
Isaac Gibbs and Emmanuel Candès.
Conformal inference for online prediction with arbitrary distribution
arXiv preprint arXiv:2208.08401, 2022.

[Golyandina et al., 2001]
Nina Golyandina, Vladimir Nekrutkin, and Anatoly A Zhigljavsky.
Analysis of time series structure: SSA and related techniques.
CRC press, 2001.

[Hewing et al., 2020]
Lukas Hewing, Kim P. Wabersich, and Melanie N. Zeilinger.
Recursively feasible stochastic model predictive control using
indirect feedback.
Automatica, 119:0 109095, 2020.
ISSN 0005-1098.

[Hummel, 2003]
S.A. Hummel.
Frisbee flight simulation and throw biomechanics.
University of California, Davis, 2003.

[Kalluraya et al., 2022]
Samarth Kalluraya, George J. Pappas, and Yiannis Kantaros.
Multi-robot mission planning in dynamic semantic environments.
arXiv preprint arXiv:2209.06323, 2022.

[Kretzschmar et al., 2016]
Henrik Kretzschmar, Markus Spies, Christoph Sprunk, and Wolfram Burgard.
Socially compliant mobile robot navigation via inverse reinforcement
The International Journal of Robotics Research, 350
(11):0 1289–1307, 2016.

[Lindemann et al., 2022]
Lars Lindemann, Matthew Cleaveland, Gihyun Shim, and George J Pappas.
Safe planning in dynamic environments using conformal prediction.
arXiv preprint arXiv:2210.10254, 2022a.

[Lindemann et al., 2022]
Lars Lindemann, Xin Qin, Jyotirmoy V Deshmukh, and George J Pappas.
Conformal prediction for stl runtime verification.
arXiv preprint arXiv:2211.01539, 2022b.

[Luo et al., 2021]
Rachel Luo, Shengjia Zhao, Jonathan Kuck, Boris Ivanovic, Silvio Savarese,
Edward Schmerling, and Marco Pavone.
Sample-efficient safety assurances using conformal prediction.
arXiv preprint arXiv:2109.14082, 2021.

[Majd et al., 2021]
Keyvan Majd, Shakiba Yaghoubi, Tomoya Yamaguchi, Bardh Hoxha, Danil Prokhorov,
and Georgios Fainekos.
Safe navigation in human occupied environments using sampling and
control barrier functions.
In 2021 IEEE/RSJ International Conference on Intelligent Robots
and Systems (IROS), pages 5794–5800. IEEE, 2021.

[Mitsch et al., 2013]
Stefan Mitsch, Khalil Ghorbal, and André Platzer.
On provably safe obstacle avoidance for autonomous robotic ground
In Robotics: Science and Systems IX, Technische Universität
Berlin, Berlin, Germany, June 24-June 28, 2013, 2013.

[Morgan et al., 2014]
D. Morgan, S.J. Chung, and F. Hadaegh.
Model predictive control of swarms of spacecraft using sequential
convex programming.
Journal of Guidance, Control, and Dynamics, 37:0
1–16, 04 2014.

[Nair et al., 2022]
Siddharth H. Nair, Vijay Govindarajan, Theresa Lin, Chris Meissen, H. Eric
Tseng, and Francesco Borrelli.
Stochastic mpc with multi-modal predictions for traffic
In 2022 IEEE 25th International Conference on Intelligent
Transportation Systems (ITSC), pages 635–640, 2022.

[Nakamura and Bansal, 2022]
Kensuke Nakamura and Somil Bansal.
Online update of safety assurances using confidence-based
arXiv preprint arXiv:2210.01199, 2022.

[Omainska et al., 2021]
Marco Omainska, Junya Yamauchi, Thomas Beckers, Takeshi Hatanaka, Sandra
Hirche, and Masayuki Fujita.
Gaussian process-based visual pursuit control with unknown target
motion learning in three dimensions.
SICE Journal of Control, Measurement, and System Integration,
140 (1):0 116–127, 2021.

[Phillips and Likhachev, 2011]
Mike Phillips and Maxim Likhachev.
Sipp: Safe interval path planning for dynamic environments.
In 2011 IEEE International Conference on Robotics and
Automation, pages 5628–5635. IEEE, 2011.

[Qin et al., 2022]
Xin Qin, Yuan Xian, Aditya Zutshi, Chuchu Fan, and Jyotirmoy V Deshmukh.
Statistical verification of cyber-physical systems using surrogate
models and conformal inference.
In 2022 ACM/IEEE 13th International Conference on
Cyber-Physical Systems (ICCPS), pages 116–126. IEEE, 2022.

[Renganathan et al., 2020]
Venkatraman Renganathan, Iman Shames, and Tyler H Summers.
Towards integrated perception and motion planning with
distributionally robust risk constraints.
IFAC-PapersOnLine, 530 (2):0 15530–15536,

[Renganathan et al., 2022]
Venkatraman Renganathan, Sleiman Safaoui, Aadi Kothari, Benjamin Gravell, Iman
Shames, and Tyler Summers.
Risk bounded nonlinear robot motion planning with integrated
perception & control.
arXiv preprint arXiv:2201.01483, 2022.

[Shafer and Vovk, 2008]
Glenn Shafer and Vladimir Vovk.
A tutorial on conformal prediction.
Journal of Machine Learning Research, 90 (3), 2008.

[Shinbrot et al., 1992]
Troy Shinbrot, Celso A Grebogi, Jack Wisdom, and James A Yorke.
Chaos in a double pendulum.
In American Journal of Physics, American Association of Physics
Teachers. 1992.

[Singletary et al., 2022]
Andrew Singletary, Aiden Swann, Ivan Dario Jimenez Rodriguez, and Aaron D.
Safe drone flight with time-varying backup controllers, 2022.
URL <https://arxiv.org/abs/2207.05220>.

[Takens, 1981]
F. Takens.
Detecting strange attractors in turbulence.
In Dynamical systems and turbulence, pages 366–381. Springer,

[Tanner et al., 2003]
Herbert G Tanner, Savvas G Loizou, and Kostas J Kyriakopoulos.
Nonholonomic navigation and control of cooperating mobile
IEEE Trans. Robotics and Automation, 190 (1):0
53–64, 2003.

[Dimarogonas et al., 2006]
Dimos V. Dimarogonas et al.
A feedback stabilization and collision avoidance scheme for multiple
independent non-point agents.
Automatica, 420 (2):0 229–243, 2006.

[Thomas et al., 2021]
Antony Thomas, Fulvio Mastrogiovanni, and Marco Baglietto.
Probabilistic collision constraint for motion planning in dynamic
In International Conference on Intelligent Autonomous Systems,
pages 141–154. Springer, 2021.

[Tibshirani et al., 2019]
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas.
Conformal prediction under covariate shift.
Advances in neural information processing systems, 32, 2019.

[Tordesillas et al., 2020]
Jesus Tordesillas, Brett T. Lopez, Michael Everett, and Jonathan P. How.
Faster: Fast and safe trajectory planner for navigation in unknown
environments, 2020.
URL <https://arxiv.org/abs/2001.04420>.

[Trautman and Krause, 2010]
Peter Trautman and Andreas Krause.
Unfreezing the robot: Navigation in dense, interacting crowds.
In 2010 IEEE/RSJ International Conference on Intelligent Robots
and Systems, pages 797–803. IEEE, 2010.

[Vovk et al., 2005]
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer.
Algorithmic learning in a random world.
Springer Science & Business Media, 2005.

[Wang et al., 2022]
Allan Wang, Christoforos Mavrogiannis, and Aaron Steinfeld.
Group-based motion prediction for navigation in crowded environments.
In Conference on Robot Learning, pages 871–882. PMLR, 2022.

[Wei et al., 2022]
Skylar X. Wei, Anushri Dixit, Shashank Tomar, and Joel W. Burdick.
Moving obstacle avoidance: A data-driven risk-aware approach.
IEEE Control Systems Letters, 7:0 289–294, 2022.

[Yoon et al., 2021]
Youngmin Yoon, Changhee Kim, Jongmin Lee, and Kyongsu Yi.
Interaction-aware probabilistic trajectory prediction of cut-in
vehicles using gaussian process for proactive control of autonomous vehicles.
IEEE Access, 9:0 63440–63455, 2021.

[Zaffran et al., 2022]
Margaux Zaffran, Olivier Féron, Yannig Goude, Julie Josse, and Aymeric
Adaptive conformal predictions for time series.
In International Conference on Machine Learning, pages
25834–25866. PMLR, 2022.

§ SLIDING LINEAR PREDICTOR WITH EXTENDED KALMAN FILTER

Given observations $\{y\}_{0}^t$ at the current time $t\ge 0$ of a discrete-time multivariate stochastic process, we assume the agent is governed by

\begin{equation}
z_{t+1} = f_d^{agent}(z_{t}),\quad \quad  y_t = h_d(z_{t}) + \xi_t
\end{equation}

where $f_d$ and $h_d$ are smooth (infinitely differentiable) functions that are the unknown states transition function in terms of full agent state $z_t$ and observation function that maps $z_t$ into observables (partial) $\{y\}_{0}^{t}$, respectively. The observables are corrupted by independent identically distributed Gaussian noise $\{\xi\}_{0}^{t}$ where each $\xi_i \in \mathcal{N}(0,\sigma^2)$.

Our goal is to obtain predictions  $(\hat{y}_t^1,\hdots,\hat{y}_t^H)$  at time $t$ of future agent states  $(Y_{t+1},\hdots,Y_{t+H})$ from past observations $(y_{0},\hdots,y_t)$ using the Predict function.

Together, we let the vector $g_{0:L-1}^{(i)}\triangleq[
]^{T} \in \mathbb{R}^{L}$ be the $L$-delay embedding the of $i^{th}$ measurable. As additional observable is acquired as time progresses, we can construct the trajectory matrix of the $i^{th}$ observable $\{y^{(i)}_0,\cdots,y^{(i)}_{N}\}$ or also known as the Hankel matrix:

\begin{align} \label{eq:hankel}
H^{(i)}_{[L,N]} = \begin{bmatrix}
g^{(i)}_{0:L-1} & g^{(i)}_{1:L} &\cdots  & g^{(i)}_{L:N-1}
\end{bmatrix} = U\Sigma V^*
\end{align}

The matrix of left singular vectors $U = \begin{bmatrix}{\mu}_1, \cdots, {\mu}_L \end{bmatrix}$ is orthonormal. The principal components of $H^x_{L\times N}$ are the columns of $V$.
To efficiently separate the noise and the true signal, we follow the work by [Agarwal et al., 2020] introduce the Page matrix representation of observables $\{y_0,\cdots,y_{TL-1}\}$. We construct and denote a $L$-embedding Page matrix as $P^{(i)}_{[L,TL]}$:

\begin{equation}
P^{(i)}_{[L,TL]} = \begin{bmatrix} g^{(i)}_{0:L-1} & g^{(i)}_{L:2L-1} &\cdots  & g^{(i)}_{(T-1)L:TL-1}
\end{bmatrix}=  U_P \sigma_P V_P^*
\end{equation}

Unlike Hankel matrices (<ref>), Page matrices do not have repeated entries which enable us to leverage the result by [Gavish and Donoho, 2014], an optimal hard singular value threshold (optHSVT) algorithm (with respect to the Mean Squared Error) for any unknown $m\times n$ matrix corrupted by noise that is zero mean, identically and independently distributed.

In summary, the optHSVT algorithm provides $\sigma_{HSVT}$ that partitions the Page matrix as,

\begin{equation} \label{eq:page_noise_signal_separation}
P^{(i)}_{[L,TL]} = \underbrace{\sum_{\rho = 1}^{n_{HSVT}} \sigma_\rho \mathbold{\mu}_\rho\mathbold{\nu}_\rho^T}_{\approx\,\, \mbox{signal}} + \underbrace{\sum_{\rho=n_{HSVT}+1}^{\min\{L, T\}}\sigma_\rho \mathbold{\mu}_\rho\mathbold{\nu}_\rho^T}_{\approx\,\, \mbox{noise}}.
\end{equation}

where $n_{HSVT}$ is the index of singular value of the logic statement $\sigma_\rho\left( P^{(i)}_{[L,TL]}\right) \geq \sigma_{HSVT}$.
Since both Hankel and Page construction shares the same rank, allowing us to use the Page matrix to recover the rank of the system and avoid ill-conditioned matrix inversion. As a result, we extract a linear predictor using the pseudo inverse $\Lambda_t = \hat{H}_{[L,2L]}^{(i),2:L} (\hat{H}_{[L,2L]}^{(i),1:L-1})^{\dagger}$ (similar to the minimum linear recurrence result in [Golyandina et al., 2001]). In particular, we denote
$$\hat{H}^{(i),2:L}_{[L,2L]} = \Big[ g^{(i)}_{t-2L:t-L-1},  g^{(i)}_{t-2L+1:t-L}, \cdots,  g^{(i)}_{[t-L:t-1]}\Big],$$

$$\hat{H}^{(i),1:L-1}_{[L,2L]} = \Big[ g^{(i)}_{t-2L+1:t-L}, g^{(i)}_{t-2L+1:t-L+1},\cdots, g^{(i)}_{[t-L+1:t]}\Big],$$
which are both $L\times L$ matrices. The $\hat{\cdot}$ operation is reconstructing the Hankel matrices with the first $n_{HSVT}$ singular eigenvector and eigenvalue pairs.  At each instance, a $H$ step prediction simply extracts the last $H$ elements of the last column of $(\Lambda_t)^{H}\hat{H}^{(i),2:L}_{[L,2L]}$. This linear predictor model will be updated instantly as new measurements are obtained. Further, we employ a standard Extended Kalman Filter (EKF) which allows us the incorporate the new measurements observed over time where the instantaneous $\Lambda_t$ is approximated as the Jacobian of the state transition function of the agent.


On the effect of scalar fields on Hawking radiation and quasinormal modes of
black holes Prof. Narayan Banerjee Doctor of Philosophy Physical Sciences
IISER Kolkata Department of Physical Sciences

Doctoral Thesis

By
Avijit Chowdhury
Roll No.: 13IP001
Department of Physical Sciences
Indian Institute of Science Education and Research Kolkata

_Supervisor:_ Prof. Narayan Banerjee

A thesis submitted in fulfilment of the requirements for the degree of
in the at the
Indian Institute of Science Education and Research Kolkata

May 21, 2021

Date: May 21, 2021

I, Avijit Chowdhury Registration No. 13IP001 dated 25/07/2013, a student of
Department of Physical Sciences of the Integrated PhD Programme of the Indian
Institute of Science Education and Research Kolkata (IISER Kolkata), hereby
declare that this thesis is my own work and, to the best of my knowledge, it
neither contains materials previously published or written by any other
person, nor it has been submitted for any degree/diploma or any other academic
award anywhere before.

I also declare that all copyrighted material incorporated into this thesis is
in compliance with the Indian Copyright (Amendment) Act, 2012 and that I have
received written permission from the copyright owners for my use of their
work.

I hereby grant permission to IISER Kolkata to store the thesis in a database
which can be accessed by others.

———————————–

Avijit Chowdhury
Department of Physical Sciences

Indian Institute of Science Education and Research Kolkata

Mohanpur 741246, West Bengal, India

Certificate from the Supervisor

Date: May 21, 2021

This is to certify that the thesis entitled “On the effect of scalar fields on
Hawking radiation and quasinormal modes of black holes” submitted by
Registration No. 13IP001 dated 25/07/2013, a student of Department of Physical
Sciences of the Integrated PhD Programme of IISER Kolkata, is based upon his
own research work under my supervision. This is also to certify that neither
the thesis nor any part of it has been submitted for any degree/diploma or any
other academic award anywhere before. In my opinion, the thesis fulfils the
requirement for the award of the degree of Doctor of Philosophy.

———————————–

Prof. Narayan Banerjee

Professor

Department of Physical Sciences

Indian Institute of Science Education and Research Kolkata

Mohanpur 741246, West Bengal, India

Abstract

The present thesis attempts to study the effect of scalar fields on Hawking
radiation and quasinormal modes of black holes. We selected a static,
spherically symmetric electrically charged black hole with an additional
scalar ‘hair’ for our analysis. The scalar ‘hair’ is sourced by a scalar
field, conformally coupled to the Einstein-Hilbert action. The scalar field
can survive even in the absence of the black hole’s electric charge and is
characterized as a ‘primary hair’. This scalar field changes the gravitational
constant, and hence modifies the ADM (Arnowitt-Deser-Missner) mass of the
black hole. The scalar field’s strength is determined by a scalar ‘charge’
that manifests itself as an additive correction to the square of the electric
charge in the standard Reissner-Nordström metric. This seemingly simple
modification leads to nontrivial physical implications.

We start with an analysis of the quasinormal modes of the black hole mentioned
above against perturbation by massless and massive, uncharged and charged
scalar and Dirac test fields. The quasinormal modes encode a black hole’s
response to perturbations (either of the metric or that induced by a test
field). The quasinormal modes are characterized by damped oscillations with
complex frequencies called the Quasinormal frequencies. The real part of the
quasinormal frequency gives the actual frequency of the wave motion, whereas
the imaginary part corresponds to the damping rate. We observed that the
presence of the scalar hair affects both the real part and imaginary part of
the quasinormal frequency.

If one relaxes the quasinormal mode boundary conditions of purely ingoing
waves at the event horizon and purely outgoing waves at spatial infinity and
instead considers a charged bosonic wave incident on the black hole from
spatial infinity, then the reflected wave from the event horizon may be
amplified. This superradiant amplification occurs at the cost of the
electrical (or rotational in case of rotating black hole) energy of the black
hole. The superradiantly amplified waves can be confined and made to interact
repeatedly with the black hole by a hypothetical ‘mirror’ surrounding the
black hole. This repeated reflection and superradiance may lead to an
exponentially increasing amplitude and hence instability. Interestingly, the
mass of the incident bosonic wavefield can effectively act as a ‘mirror’ to
reflect the low-frequency modes and lead to superradiant instability. We
studied the effect of the scalar hair on the superradiant stability of the
black hole.

An isolated black hole is also capable of radiating via pair-production in the
form of Hawking radiation. To an asymptotic observer, the Hawking emission
spectrum ‘coarsely resembles’ a black body spectrum with a temperature
inversely proportional to the black hole’s mass. Though detection of Hawking
radiation from astrophysical black holes is a near impossibility due to the
extremely low temperature of the black holes, the study of Hawking radiation
is significant in its own right, particularly in the pursuit to arrive at a
quantum theory of gravity. The Hawking radiation emitted at the event horizon
gets modified as it propagates through the spacetime surrounding the black
hole, which acts as a filter, allowing only a fraction of the emitted
radiation to reach an asymptotic observer. This fraction is referred to as the
Greybody factor and measures the deviation of the Hawking emission spectrum
from perfect blackbody like Planckian distribution. Another critical aspect
that distinguishes Hawking radiation from blackbody radiation is its
‘sparsity’, which measures the number of particles emitted per unit time.
Whereas the sparsity of a blackbody spectrum is extremely low, suggesting an
enormous number of emitted particles per unit time, the sparsity of the
Hawking radiation is exceptionally high. The latter half of the thesis is
devoted to studying the effect of the black hole scalar hair on Hawking
radiation of scalar particles, its sparsity, and greybody factor.

Acknowledgements

First and foremost, I wish to express my deepest gratitude to my supervisor,
Professor Narayan Banerjee, for his patient guidance, continuous support, and
enthusiastic encouragement throughout my Ph.D. He has always guided me with
his immense knowledge, experience, and expertise both academically and
personally. It was a great pleasure to work under his supervision. I could not
have wished for a better mentor.

I am grateful to Dr. Golam Mortuza Hossain, Dr. Rajesh Kumble Nayak, and Dr.
Ananda Dasgupta for their insightful comments and suggestions. I would also
like to extend my sincere gratitude to the office staff of the Department of
Physical Sciences, IISER Kolkata, and Assistant Librarian, IISER-K Library,
Dr. Siladitya Jana, for their help and cooperation.

I want to thank my seniors Nandan Roy, Ankan Mukherjee, Soumya Chakrabarti,
Gopal Sardar, Santanu Tripathi, Nivedita Bhadra, Biswarup Ash, Swati Sen,
Rafiqul Rahman, Subhajit Barman, Chiranjeeb Singha, Anushree Datta, Supriya
Pan and Souvik Pramanik for their help and support. I am thankful to my
friends and colleagues Anurag, Ankit, Sachin, Souraj, Sajal, Sayak, Soumik,
Purba, Tanima, and Shibendu for making my stay at IISER Kolkata a memorable
experience. Special thanks to my dear friend and colleague Srijita Sinha for
her immense help, unswerving support, motivation, and encouragement.

Finally, I want to thank my parents for their unconditional love, support,
encouragement, and inspiration.

List of Publications

## Publications included in this thesis:

  * 2\.

Avijit Chowdhury and Narayan Banerjee, “Quasinormal modes of a charged
spherical black hole with scalar hair for scalar and Dirac perturbations”,
Eur. Phys. J. C 78, 594 (2018); arXiv:1807.09559 [gr-qc].
(Chapter 2)

  * 6\.

Avijit Chowdhury and Narayan Banerjee, “Superradiant stability of mutated
Reissner–Nordström black holes”, Gen. Rel. Grav. 51, 99 (2019);
arXiv:1906.09796 [gr-qc].
(Chapter 3)

  * 10\.

Avijit Chowdhury, “Hawking emission of charged particles from an electrically
charged spherical black hole with scalar hair”, Eur. Phys. J. C  79, 928
(2019); arXiv:1911.00302 [gr-qc].
(Chapter 4)

  * 14\.

Avijit Chowdhury and Narayan Banerjee, “Greybody factor and sparsity of
Hawking radiation from a charged spherical black hole with scalar hair”, Phys.
Lett. B 805, (2020) 135417; arXiv:2002.03630 [gr-qc].
(Chapter 5)

## Publications not included in this thesis:

  * 18\.

Avijit Chowdhury and Narayan Banerjee, “Echoes from a Singularity”, Phys. Rev.
D 102, 124051 (2020); arXiv:2006.16522 [gr-qc]

To my loving parents and teachers …