if $\tau_{1}=\epsilon\cdot(\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot N)$,
then
$\delta_{F}(\pi_{F^{\prime}}(v_{1}),\sigma_{F^{\prime}}(v_{2})+\tau)\leq\delta$

  2. (ii)

if
$\delta_{F}(\pi_{F^{\prime}}(v_{1}),\sigma_{F^{\prime}}(v_{2})+\tau)\leq\delta$,
then $\left|\epsilon\cdot(\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)-\tau_{1}\right|\leq\frac{1}{3}\epsilon$

######  Lemma 5.5.

Given curves $\pi_{G}(v_{3}),\sigma_{G}(v_{4})$ for some $v_{3}\in V_{3}$ and
$v_{4}\in V_{4}$, and given a translation $\tau\in\mathcal{T}$, the following
properties hold:

  1. (i)

if $\tau_{2}=\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot N)$,
then $\delta_{F}(\pi_{G}(v_{3}),\sigma_{G}(v_{4})+\tau)\leq\delta$

  2. (ii)

if $\delta_{F}(\pi_{G}(v_{3}),\sigma_{G}(v_{4})+\tau)\leq\delta$, then
$\left|\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)-\tau_{2}\right|\leq\frac{1}{3}\epsilon$

######  Lemma 5.6.

Given curves $\pi_{G^{\prime}}(v_{3}),\sigma_{G^{\prime}}(v_{4})$ for some
$v_{3}\in V_{3}$ and $v_{4}\in V_{4}$, and given a translation
$\tau\in\mathcal{T}$, the following properties hold:

  1. (i)

if $\tau_{2}=\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot N)$,
then
$\delta_{F}(\pi_{G^{\prime}}(v_{3}),\sigma_{G^{\prime}}(v_{4})+\tau)\leq\delta$

  2. (ii)

if
$\delta_{F}(\pi_{G^{\prime}}(v_{3}),\sigma_{G^{\prime}}(v_{4})+\tau)\leq\delta$,
then $\left|\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)-\tau_{2}\right|\leq\frac{1}{3}\epsilon$

We now show that all subcurves of different equality gadgets are pairwise
further apart than $\delta$.

######  Lemma 5.7.

For any vectors $v_{1}\in V_{1},\dots,v_{4}\in V_{4}$ and any translation
$\tau\in\mathcal{T}$, each $\pi$-subcurve from any of
$F(v_{1},v_{2}),F^{\prime}(v_{1},v_{2}),G(v_{3},v_{4}),G^{\prime}(v_{3},v_{4})$
is in discrete Fréchet distance greater than $\delta$ from each
$\sigma$-subcurve of any equality gadget of different type.

###### Proof.

We first show that this holds for $F$ and $F^{\prime}$. Consider the first
point of $\sigma_{F(\cdot,\cdot)}$ which we call $q$. This point is further
than $2+N^{2}\epsilon$ from both points of $\pi_{F^{\prime}(\cdot,\cdot)}$.
When translating $\sigma$ with $\tau$, the distance is still greater than
$2+\tfrac{3}{4}\epsilon$. Thus, $\sigma_{F(\cdot,\cdot)}$ and
$\pi_{F^{\prime}(\cdot,\cdot)}$ are in discrete Fréchet distance greater than
$\delta$ for any valid $\tau$. Now let $p$ be the second point of
$\pi_{F(\cdot,\cdot)}$. The point $p$ has distance greater than $2+\epsilon$
from $\sigma_{F^{\prime}(\cdot,\cdot)}$. With translation $\tau$ this distance
is still greater than $2+\tfrac{3}{4}\epsilon$ and thus $\pi_{F(\cdot,\cdot)}$
and $\sigma_{F^{\prime}(\cdot,\cdot)}$ are in discrete Fréchet distance
greater than $\delta$ for any valid $\tau$. The proof for $G$ and $G^{\prime}$
is symmetric.

Now we prove the lemma for $F$ and $G,G^{\prime}$. First note that every point
of $F$ is in distance $1+\eta$ of the first coordinate axis and every point of
$G,G^{\prime}$ is in distance $1+\eta$ of the second coordinate axis.
Additionally, no point of $F$ is closer than $1-2N^{2}\epsilon$ to the second
coordinate axis while no point of $G,G^{\prime}$ is closer than
$1-2N^{2}\epsilon$ to the first coordinate axis. This means that every point
of a $\pi$-curve of $F$ is in distance at least
$2+\eta-2N^{2}\epsilon=2+N^{2}\epsilon$ of any point of a $\sigma$-curve of
$G$ or $G^{\prime}$. Even with translation this distance is at least
$2+\tfrac{3}{4}\epsilon\geq\delta$. Thus, also the discrete Fréchet distance
is greater than $\delta$. The proof for $F^{\prime}$ is similar and the proofs
for $G$ and $G^{\prime}$ are symmetric. ∎

We moreover observe that our equality gadgets lie in very restricted regions.
Specifically, we call a curve _diagonal_ if all of its vertices are contained
in

$[-1-2\eta,-1+2\eta]^{2}\;\cup\;[1-2\eta,1+2\eta]^{2},$

and we call it _anti-diagonal_ if all of its vertices are contained in

$[-1-2\eta,-1+2\eta]\times[1-2\eta,1+2\eta]\;\cup\;[1-2\eta,1+2\eta]\times[-1-2\eta,-1+2\eta].$

######  Observation 5.8.

For all gadgets
$F(v_{1},v_{2}),F^{\prime}(v_{1},v_{2}),G(v_{3},v_{4}),G^{\prime}(v_{3},v_{4})$
the $\sigma$-parts are diagonal while the $\pi$-parts are anti-diagonal.

We are now ready to describe the last gadget. For proving its correctness, we
will essentially only use the diagonal and anti-diagonal property of the
curves above.

##### OR Gadget.

We construct an OR gadget over diagonal and anti-diagonal curves which we will
later apply to equality gadgets. Before introducing the gadget itself, we
define various auxiliary points whose meaning will become clear later. Here we
keep notation close to [Bri14], although the details of our construction are
quite different.

$\begin{split}&s_{1}\coloneqq\left(-\tfrac{1}{4},-\tfrac{1}{4}\right),\;t_{1}\coloneqq\left(\tfrac{1}{4},\tfrac{1}{4}\right),\;r_{1}\coloneqq\left(\tfrac{99}{100},-\tfrac{5}{4}\right),\;r_{1}^{\prime}\coloneqq\left(-\tfrac{99}{100},\tfrac{5}{4}\right),\\\
&s_{2}\coloneqq(0,0),\;s_{2}^{*}\coloneqq\left(-\tfrac{3}{2},-\tfrac{3}{2}\right),\;t_{2}^{*}\coloneqq\left(\tfrac{3}{2},\tfrac{3}{2}\right),\;t_{2}\coloneqq(0,0),\;r_{2}\coloneqq\left(-\tfrac{99}{100},-\tfrac{5}{4}\right),\;r_{2}^{\prime}\coloneqq\left(\tfrac{99}{100},\tfrac{5}{4}\right).\end{split}$

Figure 13: The OR gadget for general diagonal and anti-diagonal curves. The
gray square is the centered square with diameter 2.

Now, given diagonal curves $\hat{\sigma}^{1},\dots,\hat{\sigma}^{\ell}$ and
anti-diagonal curves $\hat{\pi}^{1},\dots,\hat{\pi}^{k}$, we define the two
curves of the OR gadget as

$\begin{split}\pi_{\mathrm{OR}}&\coloneqq\mathop{\bigcirc}\limits_{i\in[k]}s_{1}\circ
r_{1}\circ\hat{\pi}^{i}\circ r_{1}^{\prime}\circ t_{1},\\\
\sigma_{\mathrm{OR}}&\coloneqq s_{2}\circ
s_{2}^{*}\circ(\mathop{\bigcirc}_{j\in[\ell]}r_{2}\circ\hat{\sigma}^{j}\circ
r_{2}^{\prime})\circ t_{2}^{*}\circ t_{2}.\end{split}$

See Figure 13 for a visualization. Now let us prove correctness of the gadget.

######  Lemma 5.9.

Given an OR gadget over diagonal curves
$\hat{\sigma}^{1},\dots,\hat{\sigma}^{\ell}$ and anti-diagonal curves
$\hat{\pi}^{1},\dots,\hat{\pi}^{k}$, for any translation $\tau\in\mathcal{T}$
we have $\delta_{F}(\pi_{\mathrm{OR}},\sigma_{\mathrm{OR}}+\tau)\leq\delta$ if
and only if $\delta_{F}(\hat{\pi}^{i},\hat{\sigma}^{j}+\tau)\leq\delta$ for
some $i,j$.

###### Proof.

First observe that no two auxiliary points have distance close to $2$ and thus
the translation $\tau$ does not change whether auxiliary points are closer
than $\delta=2+\frac{1}{4}\epsilon$ or not. Thus, we can ignore the
translation for distances between auxiliary points in this proof.

We first show that if
$\delta_{F}(\hat{\pi}^{i},\hat{\sigma}^{j}+\tau)\leq\delta$ for some $i,j$,
then $\delta_{F}(\pi_{\mathrm{OR}},\sigma_{\mathrm{OR}}+\tau)\leq\delta$ by
giving a valid traversal. We start in $s_{1},s_{2}$. Then we traverse
$\pi_{\mathrm{OR}}$ until the copy of $s_{1}$ which comes before the subcurve
$\hat{\pi}^{i}$. While staying in $s_{1}$, we traverse $\sigma_{\mathrm{OR}}$
until we reach the copy of $r_{2}$ right before the subcurve
$\hat{\sigma}^{j}$. We then do one step on $\pi_{\mathrm{OR}}$ to $r_{1}$. Now
we step to the first nodes of $\hat{\pi}^{i}$ and $\hat{\sigma}^{j}$
simultaneously, and then traverse these two subcurves in distance $\delta$,
which is possible due to
$\delta_{F}(\hat{\pi}^{i},\hat{\sigma}^{j}+\tau)\leq\delta$. We then step to
the copies of $r_{1}^{\prime}$ and $r_{2}^{\prime}$ simultaneously. We then
step to $t_{1}$ on $\pi_{\mathrm{OR}}$, while staying at $r_{2}^{\prime}$ at
$\sigma_{\mathrm{OR}}$. Subsequently, while staying in $t_{1}$, we traverse
$\sigma_{\mathrm{OR}}$ until we reach its last point, namely $t_{2}$. Now we
can traverse the remainder of $\pi_{\mathrm{OR}}$. One can check that this
traversal stays within distance $\delta$.

We now show that if
$\delta_{F}(\pi_{\mathrm{OR}},\sigma_{\mathrm{OR}}+\tau)\leq\delta$, then
there exist $i,j$ such that
$\delta_{F}(\hat{\pi}^{i},\hat{\sigma}^{j}+\tau)\leq\delta$. We prove this by
reconstructing how a valid traversal, which exists due to
$\delta_{F}(\pi_{\mathrm{OR}},\sigma_{\mathrm{OR}}+\tau)\leq\delta$, must have
passed through $\pi_{\mathrm{OR}}$ and $\sigma_{\mathrm{OR}}$. Consider the
point when $s_{2}^{*}$ is reached. At that point, we have to be in some copy
of $s_{1}$ as this is the only type of node of $\pi_{\mathrm{OR}}$ which is in
distance at most $\delta$ from $s_{2}^{*}$. Let $\hat{\pi}^{i}$ be the
subcurve right after this copy of $s_{1}$. When we step to the copy of $r_{1}$
right after this $s_{1}$, there are only three types of nodes from
$\sigma_{\mathrm{OR}}$ in distance $\delta$: $s_{2},t_{2},r_{2}$. Note that we
already passed $s_{2}$, and we cannot have reached $t_{2}$ yet, as $t_{2}^{*}$
is neither in reach of $s_{1}$ nor $r_{1}$. Thus, we are in $r_{2}$. Let the
curve right after $r_{2}$ be $\hat{\sigma}^{j}$. The only option now is to do
a simultaneous step to the first nodes of $\hat{\pi}^{i}$ and
$\hat{\sigma}^{j}$. Now, consider the point when either $r_{1}^{\prime}$ or
$r_{2}^{\prime}$ is first reached. All points of $\hat{\pi}^{i}$ are far from
$r_{2}^{\prime}$ and all points of $\hat{\sigma}^{j}$ are far from
$r_{1}^{\prime}$ and thus we have to be in $r_{1}^{\prime}$ and
$r_{2}^{\prime}$ at the same time. This implies that we traversed
$\hat{\pi}^{i}$ and $\hat{\sigma}^{j}$ from the start to the end nodes in
distance $\delta$ and therefore
$\delta_{F}(\hat{\pi}^{i},\hat{\sigma}^{j}+\tau)\leq\delta$. ∎

##### Assembling $\pi^{(j)}$ and $\sigma^{(j)}$.

Now we can apply the OR gadget to the equality gadgets in the following way.
For each of the $D$ dimensions we construct an OR gadget. The OR gadget for
dimension $j\in[D]$ contains as anti-diagonal curves all $\pi_{F}(v_{1})$ with
$v_{1}[j]=0$, all $\pi_{F^{\prime}}(v_{1})$, all $\pi_{G}(v_{3})$ with
$v_{3}[j]=0$, and all $\pi_{G^{\prime}}(v_{3})$; and as diagonal curves it
contains all $\sigma_{F}(v_{2})$, all $\sigma_{F^{\prime}}(v_{2})$ with
$v_{2}[j]=0$, all $\sigma_{G}(v_{4})$, and all $\sigma_{G^{\prime}}(v_{4})$
with $v_{4}[j]=0$. By Observation 5.8 these curves are suited to be used in
the OR gadget. We denote the resulting curves by $\pi^{(j)}$ and
$\sigma^{(j)}$, and we write $H(j)=(\pi^{(j)},\sigma^{(j)})$. This yields the
following lemma.

######  Lemma 5.10.

Given a $4$-OV instance $V_{1},\dots,V_{4}$, and consider the corresponding OR
gadget $H(j)=(\pi^{(j)},\sigma^{(j)})$ for some $j\in[D]$. It holds that:

  1. (i)

For any vectors $v_{1}\in V_{1},\dots,v_{4}\in V_{4}$ with $v_{1}[j]\cdot
v_{2}[j]\cdot v_{3}[j]\cdot v_{4}[j]=0$ we have
$\delta_{F}(\pi^{(j)},\sigma^{(j)}+\tau)\leq\delta$ for
$\tau=((\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)\cdot\epsilon,(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)\cdot\epsilon)$.

  2. (ii)

If $\delta_{F}(\pi^{(j)},\sigma^{(j)}+\tau)\leq\delta$ for some
$\tau\in\mathcal{T}$, then

     * •

$\exists v_{1}\in V_{1},v_{2}\in V_{2}:v_{1}[j]\cdot
v_{2}[j]=0\enspace\text{and}\enspace\left|\epsilon\cdot(\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)-\tau_{1}\right|\leq\frac{1}{3}\epsilon$

     * or

     * •

$\exists v_{3}\in V_{3},v_{4}\in V_{4}:v_{3}[j]\cdot
v_{4}[j]=0\enspace\text{and}\enspace\left|\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)-\tau_{2}\right|\leq\frac{1}{3}\epsilon$

###### Proof.

For (i), from $v_{1}[j]\cdot v_{2}[j]\cdot v_{3}[j]\cdot v_{4}[j]=0$ it
follows that at least one gadget of $F(v_{1},v_{2})$,
$F^{\prime}(v_{1},v_{2})$, $G(v_{3},v_{4})$, $G^{\prime}(v_{3},v_{4})$ is
contained in $H(j)$. By Lemmas 5.3 to 5.6, we know that the discrete Fréchet
distance of this gadget is small. By Lemma 5.9 it then follows that
$\delta_{F}(\pi^{(j)},\sigma^{(j)}+\tau)\leq\delta$.

For (ii), from $\delta_{F}(\pi^{(j)},\sigma^{(j)}+\tau)\leq\delta$ it follows
by Lemmas 5.9 and 5.7 that there exists a gadget $\Gamma$ for which the
discrete Fréchet distance is at most $\delta$. From Lemmas 5.3 to 5.6 it then
follows that

$\left|\epsilon\cdot(\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)-\tau_{1}\right|\leq\frac{1}{3}\epsilon\quad\text{or}\quad\left|\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)-\tau_{2}\right|\leq\frac{1}{3}\epsilon.$

for some vectors $v_{1}\in V_{1},\dots,v_{4}\in V_{4}$. As $\Gamma$ is
contained in the OR gadget, we additionally have that $v_{1}[j]\cdot
v_{2}[j]=0$ or $v_{3}[j]\cdot v_{4}[j]=0$, respectively. ∎

##### Final Curves.

The final curves $\pi$ and $\sigma$ are now defined as follows. We start with
the translation gadget $\pi^{(0)}$ ($\sigma^{(0)}$). Then the curves
$\pi^{(j)}$ ($\sigma^{(j)}$) follow for $j\in[D]$. Note that we have to
translate these curves to fulfill the requirements of Lemmas 5.1 and 5.2,
thus, we translate $\pi^{(j)}$ ($\sigma^{(j)}$) by $(100\cdot j,0)$.

We are now ready to prove Theorem 1.1. Recall its statement: *

Also recall that it suffices to prove a lower bound under the $4$-OV
hypothesis. For clarity of structure, we split the proof into Lemma 5.11 and
Lemma 5.12 which together imply Theorem 1.1.

######  Lemma 5.11.

Given a YES-instance of $4$-OV, the curves $\pi$ and $\sigma$ constructed in
our reduction have discrete Fréchet distance under translation at most
$\delta$, i.e. $\min_{\tau}\delta_{F}(\pi,\sigma+\tau)\leq\delta$.

###### Proof.

Let $v_{1}\in V_{1},\dots,v_{4}\in V_{4}$ be orthogonal vectors and let
$\tau=((\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)\cdot\epsilon,(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)\cdot\epsilon)$ be the corresponding translation to those vectors. From
Lemma 5.1 we know that $\delta_{F}(\pi^{(0)},\sigma^{(0)}+\tau)\leq\delta$,
and thus there is a valid traversal to the endpoints of the translation
gadget. Then we simultaneously step to the start of $\pi^{(1)}$ and
$\sigma^{(1)}$. From Lemma 5.10 we know that there also exist traversals of
$\pi^{(1)},\dots,\pi^{(D)}$ and $\sigma^{(1)}+\tau,\dots,\sigma^{(D)}+\tau$ of
distance at most $\delta$. It follows from Lemma 5.2 that we can also traverse
those gadgets sequentially in distance $\delta$ and thus
$\delta_{F}(\pi,\sigma+\tau)\leq\delta$. ∎

######  Lemma 5.12.

If the curves $\pi$ and $\sigma$ constructed in our reduction have discrete
Fréchet distance under translation at most $\delta$, then the given $4$-OV
instance is a YES-instance.

###### Proof.

Let $\tau$ be a translation such that $\delta_{F}(\pi,\sigma+\tau)\leq\delta$.
We know from Lemma 5.1 that $\tau\in\mathcal{T}$. Furthermore, from Lemma 5.2
we know that for all $j\in[D]$ it holds that
$\delta_{F}(\pi^{(j)},\sigma^{(j)}+\tau)\leq\delta$. It follows from Lemma
5.10 that for every $j\in[D]$ there exist $v_{1}\in V_{1},v_{2}\in V_{2}$ such
that $v_{1}[j]\cdot v_{2}[j]=0$ and
$\left|\epsilon\cdot(\mathrm{ind}(v_{1})+\mathrm{ind}(v_{2})\cdot
N)-\tau_{1}\right|\leq\frac{1}{3}\epsilon$ or there exist $v_{3}\in
V_{3},v_{4}\in V_{4}$ such that $v_{3}[j]\cdot v_{4}[j]=0$ and
$\left|\epsilon\cdot(\mathrm{ind}(v_{3})+\mathrm{ind}(v_{4})\cdot
N)-\tau_{2}\right|\leq\frac{1}{3}\epsilon$. Therefore, every dimension
$j\in[D]$ gives us constraints on either $v_{1},v_{2}$ or $v_{3},v_{4}$. Note
that those constraints have to be consistent. If in total this gives us
constraints for $v_{1},\dots,v_{4}$, then we are done. Otherwise, if this only
gives us constraints for $v_{1},v_{2}$, then we already found $v_{1},v_{2}$
which are orthogonal and thus we can pick arbitrary $v_{3}\in V_{3},v_{4}\in
V_{4}$ to obtain an orthogonal set of vectors. The case of only $v_{3},v_{4}$
being constrained is symmetric. ∎

###### Proof of Theorem 1.1..

The Strong Exponential Time Hypothesis implies the $k$-OV hypothesis. The
reduction above from a $4$-OV instance of size $N$ over $\\{0,1\\}^{D}$ to an
instance of the discrete Fréchet distance under translation in
$\mathbb{R}^{2}$ results in two curves of length $\mathcal{O}(D\cdot N)$.
Lemmas 5.11 and 5.12 show correctness of this reduction. Hence, any
$\mathcal{O}(n^{4-\epsilon})$-time algorithm for the discrete Fréchet distance
under translation would imply an algorithm for $4$-OV in time
$\mathcal{O}((D\cdot N)^{4-\epsilon})=\mathcal{O}(\text{poly}(D)\cdot
N^{4-\epsilon})$, refuting the $k$-OV hypothesis. ∎

##  6 Conclusion

In this work, we designed an improved algorithm for the discrete Fréchet
distance under translation running in time $\tilde{\cal
O}(n^{14/3})=\tilde{\cal O}(n^{4.66...})$. As a crucial subroutine, we
developed an improved algorithm for offline dynamic grid reachability.
Additionally, we presented a conditional lower bound of $n^{4-o(1)}$ based on
the Strong Exponential Time Hypothesis, which, despite not yet matching our
upper bound, strongly separates the discrete Fréchet distance under
translation from the standard discrete Fréchet distance.

Our use of offline dynamic grid reachability yields further motivation for
studying the offline setting of dynamic algorithms, for potential use as
subroutines in static algorithms. Problems left open by this paper include:
(1) Closing the gap between our upper and conditional lower bound. This might
require a solution to offline dynamic grid reachability with polylogarithmic
amortized update time. (2) Generalizing our bounds to higher dimensions, as in
this paper we only considered curves in the plane. (3) Considering different
transformations such as scaling, rotation, or affine transformations in
general; here we only treated translations. Significantly new ideas seem
necessary to obtain meaningful lower bounds for other transformations.

## References

  * [AB10] Helmut Alt and Maike Buchin.  Can we compute the similarity between surfaces?  Discrete & Computational Geometry, 43(1):78–99, 2010.
  * [AB18] Amir Abboud and Karl Bringmann.  Tighter connections between Formula-SAT and shaving logs.  In Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP’18), 2018.  To appear.
  * [ABAKS13] P. Agarwal, R. Ben Avraham, H. Kaplan, and M. Sharir.  Computing the discrete Fréchet distance in subquadratic time.  In Proc. 24th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA’13), pages 156–167, 2013.
  * [ACG12] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In Proc. 44th Annual ACM Symposium on Theory of Computing (STOC’12), pages 1199–1218, 2012.
  * [AD16] Amir Abboud and Søren Dahlgaard.  Popular conjectures as a barrier for dynamic planar graph algorithms.  In Proc. IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS’16), pages 477–486, 2016.
  * [AG95] Helmut Alt and Michael Godau.  Computing the Fréchet distance between two polygonal curves.  Internat. J. Comput. Geom. Appl., 5(1–2):78–99, 1995.
  * [AKNW14] Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe.  $\widetilde{O}(\sqrt{n})$-space and polynomial-time algorithm for planar directed graph reachability.  In Proc. 39th International Symposium on Mathematical Foundations of Computer Science (MFCS’14), pages 45–56, 2014.
  * [AKW01] Helmut Alt, Christian Knauer, and Carola Wenk.  Matching polygonal curves with respect to the Fréchet distance.  In Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS’01), pages 63–74, 2001.
  * [AN18] Ryo Ashida and Kotaro Nakagawa.  $\widetilde{O}(n^{1/3})$-space algorithm for the grid graph reachability problem.  In Proc. 34th International Symposium on Computational Geometry (SoCG’18), pages 5:1–5:13, 2018.
  * [BAFK+15] Rinat Ben Avraham, Omrit Filtser, Haim Kaplan, Matthew J. Katz, and Micha Sharir.  The discrete and semicontinuous Fréchet distance with shortcuts via approximate distance counting and selection.  ACM Transactions on Algorithms, 11(4):29, 2015.
  * [BAKS15] Rinat Ben Avraham, Haim Kaplan, and Micha Sharir.  A faster algorithm for the discrete Fréchet distance under translation.  ArXiv preprint http://arxiv.org/abs/1501.03724, 2015.
  * [BBG+11] Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo.  Detecting commuting patterns by clustering subtrajectories.  Internat. J. Comput. Geom. Appl., 21(3):253–282, 2011.
  * [BBMM14] Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer.  Four soviets walk the dog - with an application to Alt’s conjecture.  In Proc. 25th Annu. ACM-SIAM Sympos. Discrete Algorithms (SODA’14), pages 1399–1413, 2014.
  * [BBW09] Kevin Buchin, Maike Buchin, and Yusu Wang.  Exact algorithms for partial curve matching via the Fréchet distance.  In Proc. 20th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA’09), pages 645–654, 2009.
  * [BPSW05] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk.  On map-matching vehicle tracking data.  In Proc. 31st International Conf. Very Large Data Bases (VLDB’05), pages 853–864, 2005.
  * [Bri14] Karl Bringmann.  Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails.  In Proc. 55th Ann. IEEE Symposium on Foundations of Computer Science (FOCS’14), pages 661–670, 2014.
  * [CCdVE+10] Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite.  Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time.  Computational Geometry, 43(3):295–311, 2010.
  * [Cha88] Bernard Chazelle.  A functional approach to data structures and its use in multidimensional searching.  SIAM J. Comput., 17(3):427–462, 1988.
  * [Col87] Richard Cole.  Slowing down sorting networks to obtain faster sorting algorithms.  Journal of the ACM, 34(1):200–208, 1987.
  * [CT17] Timothy M. Chan and Konstantinos Tsakalidis.  Dynamic orthogonal range searching on the ram, revisited.  In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia, pages 28:1–28:13, 2017.
  * [CW10] A. F. Cook and Carola Wenk.  Geodesic Fréchet distance inside a simple polygon.  ACM Transactions on Algorithms, 7(1):193–204, 2010.
  * [DHP13] Anne Driemel and Sariel Har-Peled.  Jaywalking your dog: computing the Fréchet distance with shortcuts.  SIAM Journal on Computing, 42(5):1830–1866, 2013.
  * [DS07] Krzysztof Diks and Piotr Sankowski.  Dynamic plane transitive closure.  In Proc. 15th European Symposium on Algorithms (ESA’07), pages 594–604, 2007.
  * [EIV01] Alon Efrat, Piotr Indyk, and Suresh Venkatasubramanian.  Pattern matching for sets of segments.  In Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’01), pages 295–304, 2001.
  * [EM94] Thomas Eiter and Heikki Mannila.  Computing discrete Fréchet distance.  Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994.
  * [FK15] Omrit Filtser and Matthew J. Katz.  The discrete Fréchet gap.  ArXiv preprint http://arxiv.org/abs/1506.04861, 2015.
  * [FK18] Omrit Filtser and Matthew J. Katz.  Algorithms for the Discrete Fréchet Distance Under Translation.  In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [FR17] Chenglin Fan and Benjamin Raichel.  Computing the Fréchet Gap Distance.  In Proc. 33rd International Symposium on Computational Geometry (SoCG’17), volume 77, pages 42:1–42:16, 2017.
  * [GBT84] Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan.  Scaling and related techniques for geometry problems.  In Proc. 16th Annual ACM Symposium on Theory of Computing (STOC’84), pages 135–143, 1984.
  * [IKŁS17] Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, and Piotr Sankowski.  Decremental single-source reachability in planar digraphs.  In Proc. 49th Annual ACM Symposium on Theory of Computing, pages 1108–1121, 2017.
  * [Ind02] Piotr Indyk.  Approximate nearest neighbor algorithms for Fréchet distance via product metrics.  In Proc. 18th Annu. Symp. Comp. Geometry (SoCG’02), pages 102–106, 2002.
  * [INSWN11] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In Proc. 43rd Annual ACM Symposium on Theory of Computing (STOC’11), pages 313–322, 2011.
  * [IP01] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-SAT.  Journal of Computer and System Sciences, 62:367–375, 2001.
  * [JXZ08] Minghui Jiang, Ying Xu, and Binhai Zhu.  Protein structure–structure alignment with discrete Fréchet distance.  J. Bioinformatics and Computational Biology, 6(01):51–64, 2008\.
  * [KS98] Philip N. Klein and Sairam Subramanian.  A fully dynamic approximation scheme for shortest paths in planar graphs.  Algorithmica, 22(3):235–249, 1998.
  * [MC05] Axel Mosig and Michael Clausen.  Approximately matching polygonal curves with respect to the Fréchet distance.  Computational Geometry: Theory and Applications, 30(2):113–127, 2005.
  * [Meg83] Nimrod Megiddo.  Applying parallel computation algorithms in the design of serial algorithms.  Journal of the ACM, 30(4):852–865, 1983.
  * [Mor06] Christian Worm Mortensen.  Fully dynamic orthogonal range reporting on RAM.  SIAM J. Comput., 35(6):1494–1525, 2006.
  * [MP99] Mario E. Munich and Pietro Perona.  Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification.  In Proc. 7th Intl. Conf. Comp. Vision (ICCV’99), pages 108–115, 1999.
  * [MSSZZ11] Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, and Hamid Zarrabi-Zadeh.  Fréchet distance with speed limits.  Computational Geometry, 44(2):110–120, 2011.
  * [Sub93] Sairam Subramanian.  A fully dynamic data structure for reachability in planar digraphs.  In Proc. 1st European Symposium on Algorithms (ESA’93), pages 372–383, 1993.
  * [Wen02] Carola Wenk.  Shape matching in higher dimensions.  PhD thesis, Freie Universität Berlin, 2002.  PhD Thesis.
  * [Wil05] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.


# Learning When to Quit: Meta-Reasoning for Motion Planning

Yoonchang Sung, Leslie Pack Kaelbling, and Tomás Lozano-Pérez The authors are
with the Computer Science and Artificial Intelligence Laboratory,
Massachusetts Institute of Technology, Cambridge, MA 02139 USA {yooncs8,
<EMAIL_ADDRESS>
###### Abstract

Anytime motion planners are widely used in robotics. However, the relationship
between their solution quality and computation time is not well understood,
and thus, determining when to quit planning and start execution is unclear. In
this paper, we address the problem of deciding when to stop deliberation under
bounded computational capacity, so called _meta-reasoning_ , for anytime
motion planning. We propose data-driven learning methods, model-based and
model-free meta-reasoning, that are applicable to different environment
distributions and agnostic to the choice of anytime motion planners. As a part
of the framework, we design a convolutional neural network-based optimal
solution predictor that predicts the optimal path length from a given 2D
workspace image. We empirically evaluate the performance of the proposed
methods in simulation in comparison with baselines.

##  I Introduction

Anytime algorithms [1] are a class of algorithms that improve solution quality
over time and output an answer even if interrupted during computation. Such
algorithms occur frequently in time-critical robotic applications and they
raise decision-theoretic problems whose objective is to determine when to stop
the computation, that is, stop improving the solution, and take action. In
this work, we specifically focus on a class of anytime _motion planning_
algorithms [2, 3, 4]. The goal of motion planning (in Figure 1) is to find a
collision-free path from the initial configuration to the goal configuration
such that the robot does not collide with any obstacles. Anytime motion
planning algorithms typically improve the total length of the path when
allowed additional computation time, although one could instead improve
another objective, such as obstacle clearance or energy consumption.

Anytime motion planning consist of two phases: (1) finding a feasible path
that reaches the goal configuration, and then (2) monotonically improving the
path over time. We focus on the second phase in this work: we consider the
problem of determining when to stop deliberation after finding a first
feasible path. For anytime motion planning, we do not typically have a well-
characterized relationship between the solution quality and computation time.
Even for asymptotically optimal sampling-based motion planners there does not
yet exist a theoretical understanding of their convergence rate to optimality
[5]. Therefore, we will have to rely on data-driven methods to decide when to
terminate the computation.

Figure 1: Examples of environment distributions and the robot shape used in
simulation.

Meta-reasoning [6, 7, 8] (also known as meta-level control) is reasoning about
reasoning, to address decision-theoretic deliberation under bounded
computational capacity. Meta-reasoning can be used to determine when to stop
deliberation by monitoring the progress of reasoning and regulating the
computation time [9]. Our objective is to design a meta-reasoning framework
for anytime motion planning that applies to any anytime motion planner without
modification and generalizes to different environment distributions.

Our meta-reasoning methods make decisions based on the observed profile of the
quality of the current best solution over time (called the _performance
profile_). If this profile is fairly smooth, meta-reasoning can be solved by
online prediction without the necessity of data from previous runs; one can
extrapolate the future solution quality from a model regressed from the
history of solution qualities over the profile at hand [10]. This is, however,
infeasible in anytime motion planning because performance profiles are
generally highly non-smooth due to homotopy-class changes occurring
stochastically (see Figure 2). Therefore, we will pursue data-driven learning
methods to leverage meta-reasoning based data from related planning problems.

We assume the existence of a distribution of problems of interest, which share
some similarity in their performance profiles, and assume examples from this
distribution are available for training a model that can be used for efficient
execution on new instances from that distribution. We generate training data
by running a given anytime motion planner on the training problems and
extracting the resulting performance profiles. From this data, we learn a
decision policy by either model-based or model-free strategies. At execution
time, we apply the learned policy to the evolving performance profile of a new
problem, assuming that the given problem is drawn from the same distribution
as the training problems. Our methods can exploit aspects of the history of
solution qualities to determine whether to stop deliberation or keep executing
at every decision-making time.

Our model-based approach follows [11], using a discretization of planning time
and solution quality to frame the decision problem as a Markov decision
process (MDP). We learn a transition model for this discrete state and action
MDP based on the historical performance profiles in the dataset. We can then
compute an optimal stopping policy for this MDP using value iteration. This
simple strategy is effective for small state spaces but does not scale well
(in computation and data requirements) as the size of the state space
increases, for example, when extending states to include additional features
of the history besides the current quality and time.

We also investigate model-free approaches that use the function-approximation
capabilities of neural networks to mitigate the curse of dimensionality. As
meta-reasoning is a control problem, approximate dynamic programming or
reinforcement learning (RL) can be adopted to learn a policy [12]. However, we
observe that in our problem, we have access to an oracle for the optimal
decision policy for each performance profile in the dataset, simply by letting
the motion planner run long enough so that we get diminishing returns and
determining, post hoc, the optimal stopping time for each training example.
Therefore, model-free meta-reasoning can be formulated as _imitation learning_
[13], where the optimal decision policy is treated as an expert demonstration.
By exploiting this property, we can take a supervised learning approach, which
is generally more robust and has lower sample complexity than RL. We propose
two supervised learning-based methods: (1) neural network-based classification
with hand-designed features and (2) recurrent neural network (RNN) sequence-
to-sequence mapping on the raw performance profile.

In order to generalize over problem instances of different difficulty, the
performance profiles need to be normalized so that the states, including
quality and time, are comparable across problems. A critical requirement for
this normalization is an estimate of the optimal path length for the current
problem. We have designed a predictor for the optimal solution using a
convolutional neural network (CNN) to predict a shortest path length for a
given 2D workspace image. We use the predicted optimal solution as a
normalizer. Although this approach could potentially be extended to 3D
workspaces using voxel grids or point clouds as input, it currently limits the
applicability of our methods to problems with planar workspaces.

Our contributions include:

  * •

the application of machine-learning methods for general-purpose meta-reasoning
to the problem of trading off planning and execution time for anytime motion
planning;

  * •

the formulation, implementation, and comparison of model-based and model-free
strategies for this problem; and

  * •

the use of CNNs to predict optimal solution quality from 2D images. We develop
a solution predictor that predicts an optimal path length from a 2D workspace
image.

We present experimental results demonstrating the effectiveness of these
techniques in comparison to a set of baseline strategies.

##  II Problem Description

Given an anytime motion planning algorithm and a dataset of performance
profiles from previous motion planning problems, we want to find a policy
$\pi$ that can be used to decide when computation should be halted on a new
problem. The goal is to receive the maximal expected utility, defined as a
function of path quality and computation time. In this paper, we assume that
we have a geometric and kinematic description of the robot and that the robot
is operating in a 2D workspace, but that the dimension of the configuration
space of the robot is unconstrained.

The anytime motion planner, after having found an initial path, can be thought
of as a function that produces a path quality value as a function of running
time; this function is monotonically non-decreasing. We will normalize this
function, as described later, so that the running time $t$ is in the range
$[0,1]$ and the quality $q$ is also in the range $[0,1]$. We are also given a
normalized utility $U(q,t)$ that is a function of the normalized quality $q$
and normalized running time $t$. We will assume that there are $T+1$ evenly
spaced decision steps, $i\in[0,T]$. At every time step $i$, the performance
history $H_{i}$ is a vector of all the normalized utility values up to that
time step. The robot picks an action $a_{i}=\pi(H_{i})$ at each decision time
step $i$ in the current, unseen, workspace. If the robot chooses $a_{i}$ to be
continue, the deliberation continues to the $(i+1)$-th time step and repeats
the same process at time $t_{i+1}$. The meta-reasoning process terminates if
$a_{i}=$ stop or $i=T$.

We seek a utility-maximizing stopping policy $\pi(H_{i})$. An ideal policy
with oracular information would output $a_{i}=$ stop for
$i=\operatorname*{arg\,max}_{j\in[0,T]}U(q_{j},t_{j})$. We can at best seek a
policy that is optimal in expectation given the performance profile so far,
which is to stop if we do not expect any future time to have a higher utility
than the current one:

$\pi(H_{i})=\text{{continue}\;\; iff}\\\
\exists{j\in[i+1,T]},\;\mathbb{E}\big{[}U(q_{j},t_{j})\mid
H_{i}\big{]}>U(q_{i},t_{i})\;\;.$

Let the time at which the first feasible solution is found be, without loss of
generality, $0$. The running time is the maximal allowed time for attempting
to improve the solution, at which time meta-reasoning always terminates the
algorithm. We define a normalized time $t$ as:

$~{}t=\frac{{\rm current\ time}}{{\rm running\ time}}\in[0,1].$ (1)

We discretize the normalized time range into $T+1$ values.

The solution quality, denoted by $q$, will also be normalized. We use the
optimal (i.e., shortest) path length for this problem and the worst (i.e.,
longest) path length for this problem for normalization, so that the
normalized solution quality $q$ is:

$~{}q=\frac{{\rm worst\ path\ length}-{\rm current\ path\ length}}{{\rm worst\
path\ length}-{\rm optimal\ path\ length}}\in[0,1]\;\;.$ (2)

We discretize the range of normalized solution qualities $q$ into $Q+1$
values.

The purpose of the normalization is to make performance histories across
different problems comparable and thus enhance our ability to learn a stopping
policy that generalizes across problems. Note that the worst path length is
known and corresponds to the length of the first feasible path. The optimal
path length, however, is unknown in a previously unseen problem and therefore
must be predicted. We describe a CNN-based predictor for the optimal path
length in Section V.

The history of normalized solution qualities $H_{i}$ is the performance
profile, represented by a vector of real values: $(q_{0},\ldots,q_{i})$. Note
that the solution quality in a performance profile cannot decrease as the
deliberation time increases and so $q_{i}\leq q_{i+1}$.

The utility function $U$ encodes the user’s trade-off between solution quality
and computation time. The utility function $U(q,t)$ takes as input a
normalized solution quality $q$ and normalized time $t$ and outputs a real-
valued utility value. Although other functional forms for $U$ are possible, we
focus on a linear functional form, i.e., $U(q,t)=wq-(1-w)t$ where $w\in[0,1]$
is a user-defined parameter. Thus, $U(q,t)\in[-1,1]$ due to normalization.
This linear functional form has been widely used in the meta-reasoning
literature [8, 11]. Note that, although $q$ always increases, utility may
become negative as the computation time becomes large; this is the main
motivation for meta-reasoning.

##  III Motivating Example

Figure 2 illustrates a motivating example, in which we are using the anytime
motion-planning algorithm RRT∗ [14] in a simple workspace that could occur as
part of a larger domain. Due to the narrow passage located in the middle of
the wall (i.e., well-known challenge in sampling-based motion planning [15]),
the algorithm tends to first find a longer path going through the wide passage
and then later find a shorter path that passes through the narrow passage.
Therefore, we expect that typical performance profiles would have a single
jump when switching from the wide-passage path to the narrow-passage path
(i.e., when the homotopy class changes). However, other performance profiles
are also possible because of the stochastic nature of the algorithm. For
example, some paths may find the narrow passage first and some may not find
the narrow passage within the allotted time. Even the length of the paths that
pass through the same passage may also vary and the jump between the same two
passages may occur at different times.

A sampling of 20 executions of the algorithm with the same start and goal
configurations illustrates that the performance profiles are highly varying
even in this simple example. Our goal is to design a predictable meta-
reasoning framework that learns from such a distribution of performance
profiles to find a utility-maximizing stopping policy.

(a) Example problem.

(b) Plot of performance profiles.

Figure 2: Motivating example where there are two passages in the 2D workspace:
the narrow passage in the middle and the wide passage on the top that makes
the robot detour around the wall. A rigid L-shaped robot is used here that can
translate in the XY plane and rotate around the Z axis. Twenty performance
profiles are obtained from twenty randomly generated paths by running the RRT∗
algorithm [14].

##  IV Meta-Reasoning Frameworks

In both the model-based and model-free meta-reasoning frameworks, we assume we
are given a dataset of representative problems. For model-based meta-
reasoning, during training, we learn an MDP transition model over a state
space that represents aspects of the performance profile so far. Then, we can
compute a stopping policy via value iteration. This model-based learning and
decision process is described in Sections IV-B. For model-free meta-reasoning,
we directly learn a stopping policy, either in the form of a fully-connected
neural network classifier operating on features of the performance profile or
in the form of an RNN on the full performance profile; this process is
described in Section IV-C. As we mentioned earlier, we also need a predictor
during training and testing to estimate an optimal solution quality to be used
as a normalizer; the predictor is described in Section V. Figure 3 shows the
overall framework used for meta-reasoning. We first show how to generate a
dataset of performance profiles before we present model-based and model-free
meta-reasoning methods.

Figure 3: Overall meta-reasoning framework.

###  IV-A Dataset Generation

For each of the training problems, we run the given anytime motion planner for
long enough to obtain (with high probability) the optimal quality solution. We
use this optimal solution to train the optimal solution predictor (Section V).
We also run the planner multiple times in each problem to gather a set of
performance profiles, each of which consists of a temporal sequence of
solution qualities $(q_{0},\ldots,q_{T})$. A set of performance profiles forms
a training dataset of the model-based approach. For model-free meta-reasoning,
however, we additionally need oracular decisions.

For each performance profile and a predetermined utility trade-off $w$ that
determines a functional form of the utility function, $wq_{i}-(1-w)t_{i}$, we
can compute a temporal sequence of optimal actions represented by
$(a^{*}_{0},\ldots,a^{*}_{T})$, where $a^{*}_{i}=$ stop for
$i=\operatorname*{arg\,max}_{j\in[0,T]}U(q_{j},t_{j})$. Optimal actions before
the time step $i$, $(a^{*}_{0},\ldots,a^{*}_{i-1})$, are continue, and those
after the time step $i$, $(a^{*}_{i+1},\ldots,a^{*}_{T})$, are stop. The
training dataset of the model-free approach consists of these paired
performance profiles and optimal action sequences, and the parameter $w$, with
multiple examples constructed from each training problem.

###  IV-B Model-Based Meta-Reasoning

We can formulate the model-based meta-reasoning problem as an MDP,
$(\mathcal{S},\mathcal{A},T,R)$, with: state space $\mathcal{S}$; action space
$\mathcal{A}$; transition model
$T(s_{i},a_{i},s_{i+1})=P(S_{i+1}=s_{i+1}|S_{i}=s_{i},A_{i}=a_{i})$ where
$s_{i},s_{i+1}\in\mathcal{S},a_{i}\in\mathcal{A}$, and $S_{i},A_{i}$ are
random variables denoting the state and action taken at time step $i$; and
reward function $R(s_{i},a_{i})=r_{i}\in\mathbb{R}$.

In our setting, the state at time step $i$ is typically defined to be a tuple
of a normalized solution quality and normalized time, $(q_{i},t_{i})$. We will
also explore including additional features of the history in the state. The
set of actions is $\\{$continue, stop$\\}$. The reward function provides a
terminal reward based on the utility when the reasoning is stopped, so
$R((q_{i},t_{i}),a_{i})=wq_{i}-(1-w)t_{i}$ if $a_{i}=\texttt{stop}$ and $0$
otherwise.

We first learn the transition model from the dataset of performance profiles.
We then compute an optimal policy using this learned transition model.

Transition model When the state consists of $(q,t)$ pairs, then, because time
increments deterministically and sequentially, we only need to explicitly
build a transition model of the form $P(q_{i+1}\mid q_{i},t_{i})$, where we
arbitrarily set $q_{0}$ to be 0.

We note that, due to monotonicity in solution quality, $q_{i+1}\geq q_{i}$,
and so we can model the distribution on the next quality value given that the
solution quality at time step $i$ is $q_{i}$, $P(q_{i+1}\mid q_{i},t_{i})$, as
having a categorical or “multinoulli” distribution with parameter vector
$\theta_{t,q}$ in the $(Q+1-Qq_{i})$-simplex: that is, with $Q+1-Qq_{i}$
positive real parameters that sum to 1, so that $P(q_{i+1}\mid
q_{i},t_{i})=\theta_{t,q}(Qq_{i+1}-Qq_{i})$. Maximum likelihood estimates of
the $\theta_{t,q}$ parameters can be computed by counting the number of the
corresponding events in the data, and made more robust to sparse data by
applying Laplace smoothing.

In general, the $(q,t)$ values are not a sufficient representation of the
latent state of the underlying planning process, and prediction accuracy for
the next quality value can be improved by conditioning on additional features
of the performance profile so far or, indeed, on the whole history
$(q_{0},\ldots,q_{i-1})$. However, increasing the number of conditioning
variables substantially increases the number of parameters in the model and
therefore the amount of data required to obtain accurate parameter estimates
increases drastically.

Ultimately, the effectiveness of an estimated transition model is borne out in
how well the decisions it induces perform at execution time. However, it is
useful to be able to measure its accuracy as an independent component of the
overall system. We use the negative log likelihood assigned by our estimated
distribution $\widehat{\theta}$ to a set of held-out test data:

${\cal L}(\widehat{\theta})=\sum_{d\in{\cal
D}_{\text{test}}}-\log(\widehat{\theta}_{d})\;\;.$ (3)

Model-based decision-making A policy $\pi$ is a function that maps from state
$s$ to action $a$. We compute the policy that is optimal for the estimated
transition model, $\pi^{*}$, by maximizing the expected discounted sum of the
utility values over our decision horizon:
$\pi^{*}=\operatorname*{arg\,max}_{\pi}\mathop{\mathbb{E}}\big{[}\sum_{i=0}^{T}R(s_{i},a_{i})\big{]}$.
We solve this MDP using value iteration.

###  IV-C Model-Free Meta-Reasoning

In contrast with model-based meta-reasoning, learning a transition model is
not required in the model-free approach. Moreover, the Markovian property
assumed in an MDP may not hold for motion planning with non-smooth performance
profiles. Thus, we investigate the applicability of the model-free approach
that learns a policy directly. In general, learning a policy requires
reinforcement-learning methods, but we are able to take advantage of a special
property of this meta-reasoning problem to reduce the policy learning to
supervised learning.

We observe that if, on a training example problem, we run the anytime
algorithm and compute the utility of stopping at each time step, we can find
the optimal stopping time, $t^{*}$ and therefore determine, for each time step
$i$, that the optimal action $a_{i}^{*}$ is continue if $t_{i}<t^{*}$ and stop
otherwise. These labels constitute a “demonstration” of the optimal policy and
so allow us to use them as targets for supervised learning. We explore two
supervised learning methods: (1) a feed-forward neural-network classifier and
(2) an RNN sequence-to-sequence model. The important distinction is that the
RNN model does not require manual feature design.

Neural network-based classification From a training dataset consisting of
paired performance profiles and optimal action sequences for a predetermined
$w$, we design features that can be informative for predicting the optimal
decision. Similar to model-based meta-reasoning, besides $q$ and $t$,
additional features of the history such as derivatives can be computed. We
then learn a classifier to predict the optimal action at time $t_{i+1}$ given
features of the performance profile up through time $t_{i}$ based on a set of
labeled examples.

RNN sequence-to-sequence model Since our decision whether or not to stop
deliberation depends on a sequence of previous observations, it is natural to
frame the problem as one of mapping the performance profile so far, as a
sequence of utility values to the sequence of actions. We can use an RNN model
to learn this sequence-to-sequence mapping, which relieves us from having to
hand-craft temporal features, as we did for the feed-forward network. The
training data is a set of input-output pairs, where each pair consists of a
temporal sequence of utility values, $U(q_{i},t_{i})\;\forall i\in[0,T]$,
which can be obtained from performance profiles, as input and the
corresponding temporal sequence of optimal actions, $a^{*}_{i}\;\forall
i\in[0,T]$, as output for all performance profiles.

Because the input and output are low-dimensional, we use a simple RNN with
ReLU nonlinearities and cross-entropy loss; we tune the number of hidden
dimensions and learning rate using cross-validation. Although it might be
better to use an LSTM, we get very good performance with this very simple
model.

##  V Optimal Solution Predictor

One difficulty with this meta-reasoning framework is that performance profiles
from problems of different underlying difficulties are pooled together in the
training data. In order to learn anything from that data and apply it to new
problems, we would like to normalize any measured solution length in a problem
by the actual shortest path length (length of the optimal solution) for that
problem. Unfortunately, of course, we do not know that optimal path length, so
we take the approach of learning to predict it from a description of the
problem which, in our case, is a top-down 2D map of the environment.

From a known distribution of problems, we can sample a set of 2D workspace
images. For each workspace we run the anytime motion planner for a long term
and consider the resulting path length to be the optimum. The set of paired
workspace images and optimal path lengths forms a dataset for a supervised
regression problem. We train a CNN model to learn this mapping. We use squared
loss and select the learning rate, the number of hidden units and batch size
through cross-validation.

##  VI Simulation Results

We perform three evaluation studies, measuring: (1) the effect of the CNN-
based solution quality predictor; (2) the accuracy and computational
requirements of transition-model estimation; and (3) the value of our
approaches for meta-reasoning for anytime motion planning compared to several
baselines. In all simulations, the robot (Figure 1) had three degrees of
freedom in motion, that is, 2D translation and rotation. We defined the
normalized quality $q$ to be 30 discrete values (i.e., $Q=30$) and normalized
running time $t$ to be 200 discrete values (i.e., $T=200$). We set the utility
trade-off $w$ to be 0.8 unless stated otherwise. All simulations were
implemented based on OMPL [16].

###  VI-A Solution Quality Predictor

We analyzed the performance of the CNN-based predictor both in terms of
accuracy in predicting optimal path length and in terms of its effect on the
overall quality of the meta-reasoning system. We trained a CNN model composed
of two convolutional layers with $(5\times 5)$ kernels interleaved with two
$(2\times 2)$ max-pooling layers, followed by fully-connected layers at the
end.

####  VI-A1 Prediction Accuracy

We defined the prediction accuracy to be the percent similarity of the
predicted path length to the optimal path length. To verify the accuracy of
the predictor, we constructed an environment distribution by allowing the
partial 2D workspace to randomly vary while the start and goal configurations
are fixed. We then generated three different distributions having entirely
different 2D workspaces. From each environment distribution, we sampled 1000
images (800 images are training data and 200 images are test data) whose
resolution is $500\times 500$. We ran RRT∗ on 800 images for long enough to
obtain the shortest path lengths and used them as labels. The accuracy results
in Table I were computed after applying a learned CNN model to 200 images that
were held out. Figure 4 presents the longest and shortest paths from 200
images in each distribution. The results show that larger difference between
the longest and shortest path lengths, the lower prediction accuracy.
Nevertheless, the CNN-based predictor performed reliably with the amount of
variation shown in Figure 4.

Figure 4: The shortest (first row) and longest (second row) paths in three environment distributions (three columns). The lengths of the shortest and longest paths in meters are: 440.49 and 599.32 in the first column distribution, 641.37 and 757.61 in the second column distribution, and 622.91 and 832.13 in the third column distribution.  Environment type | Env. I | Env. II | Env. III
---|---|---|---
Accuracy | 88.21% | 96.23% | 94.25%
TABLE I: Image resolution of environment images and accuracy results of the
optimal solution predictor.

####  VI-A2 Effect of Prediction

We validated the importance of having a reasonable predictor in meta-
reasoning. To do that, we analyzed the consequence of using different
normalizers when finding a stoppinging policy over the same environments
above. We considered model-based meta-reasoning and RRT∗. We learned a model
from 800 workspaces and applied the model to compute the utility values on 200
held-out workspaces. We compared the CNN-based predictor with two other
methods: a ground-truth method where the optimal solution was known; and a
straight line connecting the start configuration to the goal configuration in
2D workspace which represents a coarse normalizer.

Table II presents the average predicted optimal path length and utility values
computed over 200 workspaces for three normalizers. The results imply that
poor prediction would decrease the performance of meta-reasoning drastically.
The straight-line normalizer produced a comparable performance in the third
environment because its prediction was close to the ground truth.

Environment type | Average path length | Utility
---|---|---
Ground truth |  CNN | Straight line | Ground truth |  CNN | Straight line
Environment I | 592.42 | 542.86 | 440.00 | 0.63$\pm$0.09 | 0.58$\pm$0.08 | 0.39$\pm$0.08
Environment II | 701.67 | 716.72 | 622.25 | 0.70$\pm$0.00 | 0.65$\pm$0.11 | 0.40$\pm$0.00
Environment III | 694.68 | 683.66 | 622.25 | 0.67$\pm$0.00 | 0.66$\pm$0.01 | 0.60$\pm$0.09
TABLE II: Average optimal path length predicted by three normalizers and
utility values obtained by applying the normalizers to meta-reasoning. Utility
values are represented by mean and 95% confidence interval. Three environments
are the same as used in Table I.

###  VI-B Transition Model Estimation

We evaluated the accuracy and efficiency of estimating the transition model,
using 4500 trajectories as training data and 500 trajectories as test data
obtained from five environment distributions ($500\times 500$ square meters)
in Figure 1.

As using all possible features summarizing the entire history is infeasible,
we introduce conditioning on two more features besides $q$ and $t$ providing a
summary of the performance history: _slope_ and _flatness_. The slope is just
a one-step empirical derivative $(q_{i}-q_{i-1})/(t_{i}-t_{i-1})$ and flatness
is the number of previous time steps for which the quality value has been
equal to $q_{i}$.

Table III reports the results of estimating the quality transition model
conditioned on different feature sets. The first row reports the data-
likelihood loss (3) on the held-out data. Adding the slope and flatness
features substantially improved the model’s predictions. Unfortunately, as
indicated in the second row, which reports the time required to estimate the
model parameters, the improvements in accuracy come at a huge computational
cost. This is the curse of dimensionality arising from estimating a large
discrete model.

Features | No features | $t_{i}$ | $t_{i},q_{i}$ | $t_{i},q_{i},q_{i-1}$ | $t_{i},q_{i},{\rm slope}$ | $t_{i},q_{i},{\rm slope,flatness}$ | $t_{i},{\rm slope,flatness}$
---|---|---|---|---|---|---|---
Loss | 1.84 | 1.79 | 0.22 | 0.19 | 0.10 | 0.03 | 1.79
Time (s) | 0.41 | 2.53 | 10.64 | 2858.63 | 11933.72 | – | –
TABLE III: Data-likelihood loss, accuracy, and computation time of estimated
transition model for different feature sets. The symbol “–” implies the time
taken more than a day.

###  VI-C The Value of Model-Based Meta-Reasoning for Anytime Motion Planning

We applied the proposed model-based and model-free meta-reasoning frameworks
to three anytime motion planners: RRT∗, PRM∗ [17, 14] and Lazy PRM∗ [18]. We
evaluated their effectiveness in five different environment distributions from
which we can sample 2D workspaces whose area is $500\times 500$ square meters
(Figure 1). We generated a dataset from these distributions and extracted 2D
workspace images to learn a CNN-based predictor. All training was based on
datasets consisting of 4500 training performance profiles and 500 test
performance profiles. We ran the planners 20 times on every held-out workspace
to measure the performance of the meta-reasoning methods. In RRT∗, we set the
range parameter to be large (i.e., 100) so that the planner found a first
feasible path quickly but its initial quality was poor. Examples of the
profile of the utility values are shown in Figure 5.

Figure 5: Profiles of utility values obtained by running RRT∗ over five
different environment distributions. Different colors represent different
environment distributions.

We compared the performance of the proposed methods with other baselines in
terms of the mean and 95% confidence interval of utility values from held-out
workspaces while varying the value of $w$. The oracle outputs the optimal
actions from all test performance profiles, giving an upper bound on the mean
utility value.

We additionally designed two simple meta-reasoning approaches as baselines:
the _fixed-time strategy_ and the _fixed-quality strategy_. The fixed-time
strategy finds a single time step $i\in[0,T]$ by averaging the time steps at
which the optimal stop action is taken from all training performance profiles,
where each optimal time step can be computed by:
$\operatorname*{arg\,max}_{j\in[0,T]}U(q_{j},t_{j})$. Then, in test
performance profiles, the fixed-time strategy stops at the chosen time step
$i$. Likewise, the fixed-quality strategy finds an unnormalized quality value
$Qq\in[0,Q]$ by averaging the unnormalized quality values at which the optimal
stop action is taken from all training performance profiles. The fixed-quality
strategy stops when the performance profile reaches the unnormalized value of
$Qq$ in all test performance profiles.

Although we demonstrated that adding features to the model-based method can
substantially improve its accuracy, the computational requirements of doing so
were impossible for our larger experimental domains. For this reason, we used
$(q_{i},q_{i-1},t)$ as features for the model-based method. However,
$(q_{i},q_{i-1},t,{\rm slope},{\rm flatness})$ were used for classification.
For the classification, we trained a neural network composed of three layers
(128, 64, 32 neurons per each layer) and the ReLU activation functions. For
the RNN model, we used 300 neurons in the hidden layer, 0.0001 as a learning
rate, and 40000 epochs.

The results are shown in table IV. In general, the model-based meta-reasoning
methods provide a substantial advantage over the baselines. The most reliably
good results come from the RNN-based predictor, which is able to discover its
own temporal features for prediction and does not suffer from estimation
problems due to model size, which cause difficulty for the model-based
methods, particularly when increased emphasis is placed on time cost by
decreasing $w$.

Anytime planner | Utility | Meta-reasoning method
---|---|---
trade-off | Oracle | Model-based | Classification | RNN | Fixed time | Fixed quality
(i.e., w) | Mean | CI | Mean | CI | Mean | CI | Mean | CI | Mean | CI | Mean | CI
RRT∗ | 0.8 | 0.677 | 0.008 | 0.663 | 0.010 | 0.658 | 0.014 | 0.670∗ | 0.006∗ | 0.575 | 0.016 | 0.634 | 0.011
0.6 | 0.442 | 0.008 | 0.414∗ | 0.012∗ | 0.399 | 0.013 | 0.401 | 0.013 | 0.341 | 0.014 | 0.337 | 0.016
0.4 | 0.244 | 0.006 | 0.168 | 0.015 | 0.195∗ | 0.008∗ | 0.191 | 0.010 | 0.176 | 0.008 | 0.010 | 0.019
0.2 | 0.096 | 0.004 | 0.031 | 0.016 | 0.079∗ | 0.004∗ | 0.074 | 0.004 | 0.072 | 0.004 | -0.283 | 0.031
PRM∗ | 0.8 | 0.718 | 0.002 | 0.702∗ | 0.003∗ | 0.697 | 0.003 | 0.698 | 0.003 | 0.662 | 0.004 | 0.674 | 0.004
0.6 | 0.507 | 0.002 | 0.490∗ | 0.004∗ | 0.489 | 0.003 | 0.485 | 0.004 | 0.451 | 0.004 | 0.396 | 0.008
0.4 | 0.314 | 0.002 | 0.297∗ | 0.004∗ | 0.292 | 0.003 | 0.294 | 0.003 | 0.271 | 0.003 | 0.118 | 0.011
0.2 | 0.140 | 0.001 | 0.120 | 0.004 | 0.125 | 0.002 | 0.125∗ | 0.002∗ | 0.120 | 0.002 | -0.344 | 0.016
Lazy PRM∗ | 0.8 | 0.643 | 0.006 | 0.591 | 0.009 | 0.593∗ | 0.008∗ | 0.589 | 0.008 | 0.559 | 0.007 | 0.588 | 0.009
0.6 | 0.441 | 0.005 | 0.376 | 0.010 | 0.387 | 0.006 | 0.393∗ | 0.007∗ | 0.361 | 0.006 | 0.302 | 0.010
0.4 | 0.266 | 0.003 | 0.201 | 0.009 | 0.224∗ | 0.004∗ | 0.221 | 0.005 | 0.216 | 0.003 | 0.0157 | 0.012
0.2 | 0.117 | 0.002 | 0.053 | 0.009 | 0.100 | 0.002 | 0.100∗ | 0.001∗ | 0.100 | 0.002 | -0.367 | 0.016
TABLE IV: Comparison with baselines for three different anytime motion
planners. In each row, we mark with $*$ the method whose performance is
closest to the oracle. CI implies the 95% confidence interval. Bolded numbers
represent the methods whose performance is not statistically significantly
different from the method with $*$.

##  VII Related Work

The study of meta-reasoning has its roots in the late 80’s in the problem of
building intelligent decision-making agents under bounded rationality [8] in
terms of two equivalent models: anytime algorithms [6] and flexible
computation [7]. Here we will focus on meta-reasoning in the context of
planning. For more complete surveys, see [19, 20, 9], and [21].

Meta-reasoning has been extensively employed for online planning to decide
when to switch to execution during concurrent planning and execution. In
online planning, the agent must plan ahead for a bounded time before taking
action. The longer the agent spends planning, the higher performance it can
achieve but the higher cost it pays, such as wasting energy. Hay et al. [22]
applied meta-reasoning as a part of the selection process in Monte-Carlo tree
search and compared that with the bandit setting. Lin et al. [23] proved the
hardness of solving the meta-reasoning version of MDPs and instead proposed an
approximation algorithm. Other planning domains have also adopted meta-
reasoning, including algorithm selection in sorting [24] and belief space
meta-reasoning in autonomous driving applications [25].

In this work, our interest lies in anytime motion planning in continuous
configuration spaces, but there exist previous works on meta-reasoning for
path planning in discrete domains. O’Ceallaigh and Ruml [26] designed a meta-
reasoning-based search algorithm that dynamically switches between greedy
hill-climbing for committing to actions and $A^{*}$ for deliberation. Cserna
et al. [27] considered durative actions and showed that taking a slower action
can lead to a better outcome by allowing a longer time for planning. In their
subsequent work [28], they presented several backup methods to estimate
heuristic values in order to decide which node to expand in tree search.

The most related work to ours is by Hansen and Zilberstein [11], where they
proposed a dynamic-programming approach to solve the model-based variant of
meta-reasoning. They later developed online approaches, such as online
performance prediction [10] and RL-based model-free meta-reasoning [12] in an
attempt to remove the necessity of preprocessing and gathering data. They
particularly considered the solution quality to be safety, yielding smooth
performance profiles. However, we deal with non-smooth performance profiles
due to our definition of path length-based solution quality in this work. As a
consequence, a learning framework is necessary for anytime motion planning.

While algorithmic properties like feasibility and completeness have drawn much
attention in anytime motion planning work [5], bounded rationality has
generally been overlooked. However, recent work by Sudhakar et al. [29]
formulated an energy-minimization problem that trades off actuation energy and
computing energy in anytime motion planners for low-power robotic platforms.
Their approach exhibits meta-reasoning in terms of energy consumption although
learning from data to help decision-making was not considered.

##  VIII Conclusion

In this work, we introduce a general-purpose meta-reasoning framework for
anytime motion planning. Several data-driven learning methods are proposed,
namely model-based and model-free meta-reasoning. We show that learning-based
meta-reasoning approaches can improve the utility of anytime motion-planning
in embedded settings where computation time must be traded off against
execution time.

## References

  * [1] S. Zilberstein, “Using anytime algorithms in intelligent systems,” _AI magazine_ , vol. 17, no. 3, pp. 73–73, 1996.
  * [2] S. Karaman, M. R. Walter, A. Perez, E. Frazzoli, and S. Teller, “Anytime motion planning using the rrt,” in _2011 IEEE International Conference on Robotics and Automation_. IEEE, 2011, pp. 1478–1483.
  * [3] R. Shome and K. E. Bekris, “Anytime multi-arm task and motion planning for pick-and-place of individual objects via handoffs,” in _2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)_. IEEE, 2019, pp. 37–43.
  * [4] N. Shah, D. K. Vasudevan, K. Kumar, P. Kamojjhala, and S. Srivastava, “Anytime integrated task and motion policies for stochastic environments,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 9285–9291.
  * [5] J. D. Gammell and M. P. Strub, “Asymptotically optimal sampling-based motion planning methods,” _Annual Review of Control, Robotics, and Autonomous Systems_ , vol. 4.
  * [6] T. L. Dean and M. S. Boddy, “An analysis of time-dependent planning.” in _AAAI_ , vol. 88, 1988, pp. 49–54.
  * [7] E. J. Horvitz, “Computation and action under bounded resources,” Ph.D. dissertation, Citeseer, 1990.
  * [8] S. J. Russell and E. Wefald, _Do the right thing: studies in limited rationality_. MIT press, 1991.
  * [9] R. Ackerman and V. A. Thompson, “Meta-reasoning: Monitoring and control of thinking and reasoning,” _Trends in Cognitive Sciences_ , vol. 21, no. 8, pp. 607–617, 2017.
  * [10] J. Svegliato, K. H. Wray, and S. Zilberstein, “Meta-level control of anytime algorithms with online performance prediction,” in _Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence_ , 2018\.
  * [11] E. A. Hansen and S. Zilberstein, “Monitoring and control of anytime algorithms: A dynamic programming approach,” _Artificial Intelligence_ , vol. 126, no. 1-2, pp. 139–157, 2001.
  * [12] J. Svegliato, P. Sharma, and S. Zilberstein, “A model-free approach to meta-level control of anytime algorithms,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 11 436–11 442.
  * [13] A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne, “Imitation learning: A survey of learning methods,” _ACM Computing Surveys (CSUR)_ , vol. 50, no. 2, pp. 1–35, 2017.
  * [14] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The international journal of robotics research_ , vol. 30, no. 7, pp. 846–894, 2011.
  * [15] D. Hsu, L. E. Kavraki, J.-C. Latombe, R. Motwani, S. Sorkin _et al._ , “On finding narrow passages with probabilistic roadmap planners,” in _Robotics: the algorithmic perspective: 1998 workshop on the algorithmic foundations of robotics_ , 1998, pp. 141–154.
  * [16] I. A. Sucan, M. Moll, and L. E. Kavraki, “The open motion planning library,” _IEEE Robotics & Automation Magazine_, vol. 19, no. 4, pp. 72–82, 2012\.
  * [17] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [18] K. Hauser, “Lazy collision checking in asymptotically-optimal motion planning,” in _2015 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2015, pp. 2951–2957.
  * [19] M. T. Cox, “Metacognition in computation: A selected research review,” _Artificial intelligence_ , vol. 169, no. 2, pp. 104–141, 2005.
  * [20] M. L. Anderson and T. Oates, “A review of recent research in metareasoning and metalearning,” _AI Magazine_ , vol. 28, no. 1, pp. 12–12, 2007.
  * [21] T. L. Griffiths, F. Callaway, M. B. Chang, E. Grant, P. M. Krueger, and F. Lieder, “Doing more with less: meta-reasoning and meta-learning in humans and machines,” _Current Opinion in Behavioral Sciences_ , vol. 29, pp. 24–30, 2019.
  * [22] N. Hay, S. Russell, D. Tolpin, and S. E. Shimony, “Selecting computations: theory and applications,” in _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence_ , 2012, pp. 346–355.
  * [23] C. H. Lin, A. Kolobov, E. Kamar, and E. Horvitz, “Metareasoning for planning under uncertainty,” in _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * [24] F. Lieder, D. Plunkett, J. B. Hamrick, S. J. Russell, N. Hay, and T. Griffiths, “Algorithm selection by rational metareasoning as a model of human strategy selection,” in _Advances in neural information processing systems_ , 2014, pp. 2870–2878.
  * [25] J. Svegliato, K. H. Wray, S. J. Witwicki, J. Biswas, and S. Zilberstein, “Belief space metareasoning for exception recovery,” in _IROS_ , 2019.
  * [26] D. O’Ceallaigh and W. Ruml, “Metareasoning in real-time heuristic search,” in _Eighth Annual Symposium on Combinatorial Search_ , 2015.
  * [27] B. Cserna, W. Ruml, and J. Frank, “Planning time to think: Metareasoning for on-line planning with durative actions,” in _Twenty-Seventh International Conference on Automated Planning and Scheduling_ , 2017.
  * [28] A. Mitchell, W. Ruml, F. Spaniol, J. Hoffmann, and M. Petrik, “Real-time planning as decision-making under uncertainty,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, 2019, pp. 2338–2345.
  * [29] S. Sudhakar, S. Karaman, and V. Sze, “Balancing actuation and computing energy in motion planning,” in _2020 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2020, pp. 4259–4265.