# Quasi-isomorphism of grid chain complexes for a connected sum of knots

Hajime Kubota  Department of Mathematics, Graduate School of Science, Kyoto
University, Kitashirakawa-Oiwakecho, Sakyo-ku, Kyoto 606-8502, Japan
<EMAIL_ADDRESS>
###### Abstract.

We give a purely combinatorial proof of the Künneth formula for the knot Floer
homology of connected sums by constructing a quasi-isomorphism of grid chain
complexes. This proof is complete within the framework of the knot grid
homology. The construction of the quasi-isomorphism naturally deduces that the
Legendrian and transverse invariants behave functorially with respect to the
connected sum operation.

###### Key words and phrases:

grid homology; knot Floer homology; Künneth formula; spatial graph

###### 1991 Mathematics Subject Classification:

57K18

##  1\. Introduction

Grid homology is a combinatorial reconstruction of knot Floer homology
developed by Manolescu, Ozsváth, Szabó, and Thurston [10]. Because grid
homology is a purely combinatorial theory without holomorphic theory, it is an
interesting problem whether the known results of knot Floer homology can be
shown in the framework of grid homology. For example, there are combinatorial
reformulations of the knot Floer invariants such as the tau, epsilon, and
Upsilon invariant [14, 6, 4]. Furthermore, the tau and Upsilon invariants were
combinatorially proved to be concordance invariants in [15, 7], respectively.

In this paper, we only consider knots in $S^{3}$ and discuss the hat version
of grid homology and knot Floer homology. There is the Künneth formula for the
knot Floer homology of connected sums

(1.1)
$\widehat{HFK}(K_{1})\otimes\widehat{HFK}(K_{2})\cong\widehat{HFK}(K_{1}\\#K_{2}).$

In [8], the author proved (1.1) by applying the grid homology for spatial
graphs. However, we proved the existence of the isomorphism of the homologies
without the concrete isomorphism. We verified this by observing the tilde
chain complexes that are reduced complexes of the hat complexes depending on
grid diagrams. In addition, the proof needs the extended grid homology for
spatial graphs and is not completed within the framework of the knot grid
homology.

The former result of the present paper is a refinement of the work in [8]. We
explore the hat version of grid chain complexes to give quasi-isomorphism of
the formula.

######  Theorem 1.1.

Let $g_{1}$ and $g_{2}$ be two good (Definition 4.1) grid diagrams
representing two knots $K_{1}$ and $K_{2}$ respectively. Let $g_{\\#}$ be the
grid diagram representing $K_{1}\\#K_{2}$ obtained by $g_{1}$ and $g_{2}$.
Then there is a quasi-isomorphism

$\widehat{GC}(g_{1})\otimes\widehat{GC}(g_{2})\to\widehat{GC}(g_{\\#}).$

######  Remark 1.2.

Every knot is represented by a good grid diagram. The proof of this theorem is
complete within the framework of the knot grid homology.

Grid homology gives effective invariants for Legendrian and transverse knots
in $(\mathrm{R}^{3},\xi_{\mathrm{std}})$ [12]. For example, two Legendrian
knots with the topological type $5_{2}$ and the same classical invariants are
distinguished by the grid Legendrian invariant [2, 12]. This invariant is
known to provide obstructions to decomposable Lagrangian cobordisms, certain
good cobordisms between two Legendrian knots [1, Theorem 1.2]. The grid
transverse invariant is applied to study the transverse simplicity of
topological knots [11]. These invariants are extended to null-homologous
Legendrian and transverse knots in general closed contact three-manifolds [9].

The grid Legendrian invariants are defined to be the homology classes
determined by the canonical generators of the chain complex. By the
construction of the quasi-isomorphism of the above theorem, we can easily
trace the generators, so we can quickly show the following$\colon$

######  Theorem 1.3.

Let $g_{1}$ and $g_{2}$ be two good (Definition 4.1) grid diagrams
representing two Legendrian knots $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$
respectively. Let $g_{\\#}$ be the grid diagram representing
$\mathcal{K}_{1}\\#\mathcal{K}_{2}$ obtained by $g_{1}$ and $g_{2}$. Then
there is a quasi-isomorphism

$\widehat{GC}(g_{1})\otimes\widehat{GC}(g_{2})\to\widehat{GC}(g_{\\#})$

which maps
$\widehat{\lambda}_{+}(\mathcal{K}_{1})\otimes\widehat{\lambda}_{+}(\mathcal{K}_{2})$
to $\widehat{\lambda}_{+}(\mathcal{K}_{1}\\#\mathcal{K}_{2})$ and
$\widehat{\lambda}_{-}(\mathcal{K}_{1})\otimes\widehat{\lambda}_{-}(\mathcal{K}_{2})$
to $\widehat{\lambda}_{-}(\mathcal{K}_{1}\\#\mathcal{K}_{2})$.

The grid transverse invariant is defined to be the homology class
$\widehat{\lambda}_{+}\in\widehat{GH}(g)$, so the following corollary is
proved immediately.

######  Corollary 1.4.

Let $g_{1}$ and $g_{2}$ be two good grid diagrams representing the transverse
knots $\mathcal{T}_{1}$ and $\mathcal{T}_{2}$ respectively. Let $g_{\\#}$ be
the grid diagram representing $\mathcal{T}_{1}\\#\mathcal{T}_{2}$ obtained by
$g_{1}$ and $g_{2}$. Then there is a quasi-isomorphism

$\widehat{GC}(g_{1})\otimes\widehat{GC}(g_{2})\to\widehat{GC}(g_{\\#})$

which maps
$\widehat{\theta}(\mathcal{T}_{1})\otimes\widehat{\theta}(\mathcal{T}_{2})$ to
$\widehat{\theta}(\mathcal{T}_{1}\\#\mathcal{T}_{2})$.

These are purely combinatorial proofs of Vétesi’s results [16, Corollaries 1.2
and 1.3].

###  1.1. Outline of the paper.

In Section 2, we review the knot grid homology. In Section 3, we briefly
describe Legendrian and transverse knots and the relation between them to grid
homology. In Section 4, we prepare some notations and define useful chain
complexes to prove the main theorem. In section 5, we give the construction of
a quasi-isomorphism and prove the main theorem.

##  2\. The definition of grid homology for knots

This section quickly provides an overview of grid homology for knots and
links. Referring to [13, Remark 4.6.13], we will introduce the hat version
without using the minus version. See [13] for details.

A planar grid diagram $g$ (Figure 1) is an $n\times n$ grid of squares some of
which is decorated with an $X$\- or $O$\- marking such that it satisfies the
following conditions.

  1. (i)

There is exactly one $O$ and $X$ on each row and column.

  2. (ii)

$O$’s and $X$’s do not share the same square.

We denote the set of $O$\- by $\mathbb{O}$ and the set of $X$-markings by
$\mathbb{X}$. We often use the labeling of markings as $\\{O_{i}\\}_{i=1}^{n}$
and $\\{X_{j}\\}_{j=1}^{m}$.

A grid diagram determines a link in $S^{3}$. Drawing oriented segments from
the $O$-markings to the $X$-markings in each row and oriented segments from
the $X$-markings to the $O$-marking in each column. Assume that the vertical
segments always cross above the horizontal segments. Then we can recover the
link diagram. In this paper, we only consider grid diagrams representing
knots.

It is known that any two grid diagrams for the same knot can be connected by a
finite sequence of moves on grid diagrams called grid moves; see [3, 10].

A toroidal grid diagram is a grid diagram that is regarded as a diagram on the
torus obtained by identifying edges in a natural way. We assume that every
toroidal diagram is oriented in a natural way. We write the horizontal circles
and vertical circles which divide the torus into squares as
$\boldsymbol{\alpha}=\\{\alpha_{i}\\}_{i=1}^{n}$ and
$\boldsymbol{\beta}=\\{\beta_{j}\\}_{j=1}^{n}$ respectively. A state
$\mathbf{x}$ of a toroidal diagram $g$ is a bijection
$\boldsymbol{\alpha}\rightarrow\boldsymbol{\beta}$. We denote by
$\mathbf{S}(g)$ the set of states of $g$. We describe a state as $n$ points on
a toroidal grid diagram (figure 1).

Figure 1. an example of states and a rectangle

There are $n\times n$ squares on $g$ that is separated by
$\boldsymbol{\alpha}\cup\boldsymbol{\beta}$. Fix $\mathbf{x,y}\in S$(g), a
domain $p$ from $\mathbf{x}$ to $\mathbf{y}$ is a formal sum of the closure of
squares satisfying $\partial(\partial_{\alpha}p)=\mathbf{y}-\mathbf{x}$ and
$\partial(\partial_{\beta}p)=\mathbf{x}-\mathbf{y}$, where
$\partial_{\alpha}p$ is the portion of the boundary of $p$ in the horizontal
circles $\alpha_{1}\cup\dots\cup\alpha_{n}$ and $\partial_{\beta}p$ is the
portion of the boundary of $p$ in the vertical ones. A domain $p$ is positive
if the coefficient of any square is non-negative. Let $\pi(\mathbf{x,y})$
denote the set of domains from $\mathbf{x}$ to $\mathbf{y}$. Throughout the
paper, we always assume that a domain is positive. For two domains
$p_{1}\in\pi(\mathbf{x,y})$ and $p_{2}\in\pi(\mathbf{y,z})$, the composite
domain $p_{1}*p_{2}$ is the domain from $\mathbf{x}$ to $\mathbf{z}$ such that
the coefficient of each square is the sum of the coefficient of the square of
$p_{1}$ and $p_{2}$. Consider $\mathbf{x,y\in S}(g)$ that coincide with $n-2$
points. An rectangle $r$ from $\mathbf{x}$ to $\mathbf{y}$ is a domain such
that $\partial r$ is the union of four segments. A rectangle $r$ is empty if
$\mathbf{x}\cap\mathrm{Int}(r)=\mathbf{y}\cap\mathrm{Int}(r)=\emptyset$. Let
$\mathrm{Rect}^{\circ}(\mathbf{x,y})$ be the set of empty rectangles from
$\mathbf{x}$ to $\mathbf{y}$ if $\mathbf{x}$ and $\mathbf{y}$ coincide with
$n-2$ points and $\mathrm{Rect}^{\circ}(\mathbf{x,y})=\emptyset$ otherwise.

######  Definition 2.1.

The (hat version of) grid chain complex $(\widehat{GC}(g),\widehat{\partial})$
is the $\mathbb{F}$-vector space with basis $\\{U_{1}^{k_{1}}\cdots
U_{n-1}^{k_{n-1}}\cdot\mathbf{x}|k_{1},\dots,k_{n-1}\geqq
0,\mathbf{x}\in\mathbf{S}(g)\\}$, where $\mathbb{F}=\mathbb{Z}/2\mathbb{Z}$
and the $U_{i}$’s are the formal variables corresponding to the $O_{i}$’s in
$g$. The differential $\widehat{\partial}$ is the linear map satisfying
$U_{i}\circ\widehat{\partial}=\widehat{\partial}\circ U_{i}$ and for
$\mathbf{x}\in\mathbf{S}(g)$,

$\widehat{\partial}(\mathbf{x})=\sum_{\mathbf{y}\in\mathbf{S}(g)}\left(\sum_{\\{r\in\mathrm{Rect}^{\circ}(\mathbf{x,y})|r\cap\mathbb{X}=\emptyset,O_{n}\notin
r\\}}U_{1}^{O_{1}(r)}\cdots U_{n-1}^{O_{n-1}(r)}\right)\mathbf{y},$

where $O_{i}(r)=1$ if $r$ contains $O_{i}$ and $O_{i}(r)=0$ otherwise for
$i=1,\dots,n-1$ and $U_{i}\circ\widehat{\partial}=\widehat{\partial}\circ
U_{i}$.

There are two gradings for $\widehat{GC}(g)$, the Maslov grading and the
Alexander grading. A planar realization of a toroidal diagram $g$ is a planar
figure obtained by cutting toroidal diagram $g$ along $\alpha_{i}$ and
$\beta_{j}$ for some $i$ and $j$, and putting on
$[0,n)\times[0,n)\in\mathbb{R}^{2}$ in a natural way. For two points
$(a_{1},a_{2}),(b_{1},b_{2})\subset\mathbb{R}^{2}$, let
$(a_{1},a_{2})<(b_{1},b_{2})$ if $a_{1}<b_{1}$ and $a_{2}<b_{2}$. For two sets
of finitely many points $A,B\subset\mathbb{R}^{2}$, let $\mathcal{I}(A,B)$ be
the number of pairs $a\in A,b\in B$ with $a<b$ and let
$\mathcal{J}(A,B)=(\mathcal{I}(A,B)+\mathcal{I}(B,A))/2$.

Then for $\mathbf{x\in S}(g)$, the Maslov grading $M(\mathbf{x})$ and the
Alexander grading $A(\mathbf{x})$ are defined by

(2.1) $\displaystyle M(\mathbf{x})$
$\displaystyle=\mathcal{J}(\mathbf{x}-\mathbb{O},\mathbf{x}-\mathbb{O})+1,$
(2.2) $\displaystyle A(\mathbf{x})$
$\displaystyle=\mathcal{J}(\mathbf{x},\mathbb{X}-\mathbb{O})+\frac{1}{2}(\mathcal{J}(\mathbb{O}+\mathbb{X},\mathbb{O}-\mathbb{X}))-\frac{n-1}{2}.$

These two gradings are extended to the whole $\widehat{GC}(g)$ by

(2.3) $\displaystyle M(U_{i})=-2,\ A(U_{i})=-1\ (i=1,\dots,n-1).$

It is known that these two gradings are independent of the choice of the
planar realization and that the differential $\widehat{\partial}$ drops the
Maslov grading by 1 and preserves or drops the Alexander grading. So
$(\widehat{CF}(g),\widehat{\partial})$ is an absolute Maslov graded, Alexander
graded chain complex [13, Sections 4.3 and 4.6].

######  Definition 2.2.

The (hat version of) grid homology of $g$, denoted $\widehat{GH}(g)$, is the
homology of $(\widehat{CF}(g),\widehat{\partial})$, thought of as a bigraded
vector space.

The grid chain complex $(\widehat{CF}(g),\widehat{\partial})$ depends on which
$O$-marking is labeled as $O_{n}$ (Definition 2.1). However, the homology
$\widehat{GH}(g)$ up to isomorphism is independent of the choice of $O_{n}$
[13, Corollary 4.6.16]. Moreover, $\widehat{GH}(g)$ is an invariant for knots.

######  Theorem 2.3 ([13, Theorem 5.3.1]).

Let $g_{1}$ and $g_{2}$ be two grid diagrams representing the same knot $K$.
Then $\widehat{GH}(g_{1})\cong\widehat{GH}(g_{2})$ as bigraded vector spaces.

We will denote by $\widehat{GH}(K)$ if there is no confusion.

##  3\. Legendrian and transverse knots with grid diagram

###  3.1. Legendrian and transverse knots

We briefly review the Legendrian knot and the Legendrian and transverse
invariants with grid homology. See [5, 12] for details.

A Legendrian knot is a smooth knot $\mathcal{K}\in\mathbb{R}^{3}$ whose
tangent vectors are contained in the contact planes of
$\mathrm{Ker}\,\xi_{\mathrm{std}}$, where $\xi_{\mathrm{std}}=dz-y\,dx$. Two
knots are Legendrian isotopic if they are connected by a smooth one-parameter
family of Legendrian knots. There are two classical invariants of a Legendrian
knot $\mathcal{K}$; the Thurston-Bennequin number $\mathrm{tb}(\mathcal{K})$
and the rotation number $\mathrm{r}(\mathcal{K})$. Consider a framing of
$\mathcal{K}$ obtained by restricting $\xi_{\mathrm{std}}$ to $\mathcal{K}$
and let $\mathcal{K}^{\prime}$ be the push-off of $\mathcal{K}$ with the
framing. Then $\mathrm{tb}(\mathcal{K})$ is defined to be $\ell
k(\mathcal{K},\mathcal{K}^{\prime})$. Fix a Seifert surface $F$ for
$\mathcal{K}$. The restriction of $\xi_{\mathrm{std}}$ to $F$ gives an
oriented two-plane bundle over $F$, which has a trivialization along the
$\partial F$ induced by tangent vectors to $\mathcal{K}$. Then
$\mathrm{r}(\mathcal{K})$ is the relative Euler number of the two-plane field
$\xi_{\mathrm{std}}$ over $F$, relative to the trivialization over $\partial
F$. Legendrian knots are studied via their front projections to the $xz$-plane
by the projection map $(x,y,z)\mapsto(x,z)$. The front projection of a
Legendrian knot has no vertical tangencies and in the generic case, its
singularities are double points and cusps. Let $\mathcal{D}$ be the front
projection of $\mathcal{K}$. Then we have

$\displaystyle\mathrm{tb}(\mathcal{K})$
$\displaystyle=\mathrm{wr}(\mathcal{D})-\frac{1}{2}\\#\\{\mathrm{cusps\ in}\
\mathcal{D}\\},$ $\displaystyle\mathrm{r}(\mathcal{K})$
$\displaystyle=\frac{1}{2}(\\#\\{\mathrm{downward-oriented\
cusps}\\}-\\#\\{upward-oriented\ cusps\\}).$

Legendrian knots can be locally changed by adding two new cusps, called
Legendrian stabilization. Legendrian stabilization preserves the topological
knot type, but it changes the Legendrian knot type. Legendrian stabilization
drops the Thurston-Bennequin number by one and changes the rotation number by
$\pm 1$. The stabilization increasing the rotation number by $1$ is called a
positive stabilization and the stabilization drops the rotation number by $1$
is called a negative stabilization.

A transverse knot $\mathcal{T}$ is a knot whose tangent vectors are transverse
to the contact planes of $\mathrm{Ker}\,\xi_{\mathrm{std}}$. Two transverse
knots are transverse isotopic if they are connected by a smooth one-parameter
family of transverse knots. There is a classical invariant for transverse
knots $\mathcal{T}$ called self-linking number $\mathrm{sl}(\mathcal{T})$. See
[5, Section 2.6.3] for the definition. Given a Legendrian knot $\mathcal{K}$,
there are transverse knots $\mathcal{T}$ that are arbitrarily close to
$\mathcal{K}$ (in $C^{1}$ topology). Furthermore, there is a neighborhood of
$\mathcal{K}$ such that any two transverse knots in this neighborhood are
transverse isotopic. The transverse push-off $\mathcal{T}(\mathcal{K})$ of
$\mathcal{K}$ is the transverse knot type which can be represented by a
transverse knot arbitrarily close to $\mathcal{K}$. Any transverse knot
$\mathcal{T}$ is transversely isotopic to the transverse push-off of some
Legendrian knot $\mathcal{K}$. Then $\mathcal{K}$ is called Legendrian
approximation of $\mathcal{T}$.

###  3.2. Legendrian knots and grid diagram

Figure 2. The Legendrian knot determined by a grid diagram

We quickly review the Legendrian knot and the Legendrian and transverse
invariants with grid homology. There is an algorithm for giving the front
projection of a Legendrian knot from a (planar) grid diagram (Figure 2. See
[12, Section 4] and [13, Section 12.2] for details). Let $g$ be a planar grid
diagram for a knot $K$. Connect each marking of $g$ by horizontal and vertical
segments to obtain a diagram of $K$ on $g$. Rotate $g$ by $45^{\circ}$
clockwise. Turn each corner of the diagram of $K$ on $g$ into cusps or smooth
arcs. Switch all crossings of the diagram. Then we get the front projection of
the Legendrian knot whose topological type is $m(K)$. We say that a grid
diagram $g$ represents the Legendrian knot $\mathcal{K}$ if $\mathcal{K}$ is
obtained from $g$ by the above procedure. Furthermore, considering the
transverse push-off of $\mathcal{K}$, a grid diagram uniquely specified a
transverse knot. Any transverse knot is represented by grid diagrams by taking
its Legendrian approximation.

In [12], Ozsváth, Szabó, and Thurston defined Legendrian and transverse
invariants using grid homology. For a grid diagram $g$, let
$\mathbf{x}^{+}(g)$ be the canonical state consisting of the northeast corner
of each square decorated by $X$. Similarly, let $\mathbf{x}^{-}(g)$ be the
canonical state consisting of the southwest corner of each square decorated by
$X$.

######  Theorem 3.1 ([12, Theorem 1.1]).

Let $\mathcal{K}$ be a Legendrian knot represented by a grid diagram $g$. The
homology classes in $\widehat{GH}(g)$ represented by $\mathbf{x}^{+}(g)$ and
$\mathbf{x}^{-}(g)$, denoted by $\widehat{\lambda}_{+}(g)$ and
$\widehat{\lambda}_{-}(g)$ respectively, are invariants of Legendrian knots;
i.e., if $g$ and $g^{\prime}$ represent Legendrian isotopic knots, then there
is a quasi-isomorphism

$\Phi\colon\widehat{GC}(g)\to\widehat{GC}(g^{\prime})$

such that $\Phi(\widehat{\lambda}_{+}(g))=\widehat{\lambda}_{+}(g^{\prime})$
and $\Phi(\widehat{\lambda}_{-}(g))=\widehat{\lambda}_{-}(g^{\prime})$.

######  Theorem 3.2 ([12, Corollary 1.4]).

Let $\mathcal{K}$ be a Legendrian knot represented by a grid diagram $g$, and
$\mathcal{T}$ be its transverse push-off. The homology class
$\widehat{\lambda}(g)\in\widehat{GH}(g)$, denoted by
$\widehat{\theta}(\mathcal{T})$, is an invariant of transverse knot; i.e., if
$g$ and $g^{\prime}$ represent two Legendrian approximations to $\mathcal{T}$,
then there is a quasi-isomorphism

$\Psi\colon\widehat{GC}(g)\to\widehat{GC}(g^{\prime})$

such that
$\Psi(\widehat{\theta}(\mathcal{T}))=\widehat{\theta}(\mathcal{T^{\prime}})$.

We remark that the Legendrian invariant $\widehat{\lambda}_{\pm}$ provides
obstructions to decomposable Lagrangian cobordisms, certain good cobordisms
between two Legendrian knots [1, Theorem 1.2].

##  4\. The preparation of the proof of main theorem

###  4.1. The construction of grid diagram $g_{\\#}$

First, we construct $g_{\\#}$ from $g_{1}$ and $g_{2}$.

######  Definition 4.1.

A grid diagram is called good if it has an $O$-marking in the leftmost square
of the top row and in the rightmost square of the bottom row and an
$X$-marking in the rightmost square of the top row.

We remark that every knot is represented by a good grid diagram.

Let $g_{\\#}$ be the $2n\times 2n$ toroidal diagram so that the four $n\times
n$ blocks obtained by cutting it along the horizontal circles
$\alpha_{1}\cup\alpha_{n+1}$ and the vertical circles
$\beta_{1}\cup\beta_{n+1}$, denoted by $g_{11}$, $g_{12}$, $g_{21}$, and
$g_{22}$ respectively (see Figure 3), satisfy the following conditions:

  * •

$g_{11}$ and $g_{1}$ coincide except for the rightmost square of the bottom
row.

  * •

$g_{22}$ and $g_{2}$ coincide except for the leftmost square of the top row.

  * •

$g_{12}$ and $g_{21}$ have exactly one $O$-marking.

Figure 3.  A $2n\times 2n$ grid diagram $g_{\\#}$.

Let $O_{i}$ be the $O$-marking in the $i$-th column of $g_{\\#}$
$(i=1,\dots,2n)$. Choose $O_{n+1}$ as the special $O$-marking. Then
$\widehat{GC}(g)$ is the chain complex of $\mathbb{F}$-vector space with basis
$\\{U_{1}^{k_{1}}\cdots U_{n}^{k_{n}}\cdot U_{n+2}^{k_{n+2}}\cdots
U_{2n}^{k_{2n}}\cdot\mathbf{x}|k_{1},\dots,k_{2n}\geqq
0,\mathbf{x}\in\mathbf{S}(g)\\}$.

###  4.2. The classification of the states $\mathbf{S}(g_{\\#})$

The basic idea is the same as [8, Section 5.1]. Let
$\mathbf{g}_{11}=(\alpha_{1}\cup\dots\cup\alpha_{n})\cap(\beta_{1}\cup\dots\cup\beta_{n})$
be the $n^{2}$ points in $g_{11}$. Define $\mathbf{g}_{12}$,
$\mathbf{g}_{21}$, and $\mathbf{g}_{22}$ similarly. For a state
$\mathbf{x}\in\mathbf{S}(g_{\\#})$ and $i,j\in\\{1,2\\}$, let
$\mathbf{x}_{ij}=\mathbf{x}\cap\mathbf{g}_{ij}$. We will represent each state
$\mathbf{x\in S}(g_{\\#})$ uniquely as

$\mathbf{x}=\begin{pmatrix}\mathbf{x}_{11}&\mathbf{x}_{12}\\\
\mathbf{x}_{21}&\mathbf{x}_{22}\\\ \end{pmatrix},$

where $\mathbf{x}_{11}$ and $\mathbf{x}_{22}$ are the $n-k$ points of
$\mathbf{x}$ contained in $g_{11}$ and $g_{22}$ respectively, and
$\mathbf{x}_{12}$ and $\mathbf{x}_{21}$ is the $k$ points of $\mathbf{x}$
contained in $g_{12}$ and $g_{21}$ respectively.

Take a point $c$ as the intersection point $\alpha_{n+1}\cap\beta_{n+1}$. Let
$\mathbf{I}(g_{\\#})$ be the set of states that containing $c$ and
$\mathbf{N}(g_{\\#})=\mathbf{S}(g_{\\#})\setminus\mathbf{I}(g_{\\#})$. Then,
we will classify the states of $\mathbf{I}(g_{\\#})$ and $\mathbf{N}(g_{\\#})$
as

$\displaystyle\mathbf{I}_{k}(g_{\\#})$
$\displaystyle=\\{\mathbf{x}\in\mathbf{I}(g_{\\#})|\\#(\mathbf{x}\cap\mathbf{g}_{12})=\\#(\mathbf{x}\cap\mathbf{g}_{21})=k\\},$
$\displaystyle\mathbf{N}_{k}(g_{\\#})$
$\displaystyle=\\{\mathbf{x}\in\mathbf{N}(g_{\\#})|\\#(\mathbf{x}\cap\mathbf{g}_{12})=\\#(\mathbf{x}\cap\mathbf{g}_{21})=k\\},$

for $k=0,\dots,n$. Note that since the point $c$ is contained in
$\mathbf{g}_{12}$, we have $\mathbf{I}_{0}(g_{\\#})=\emptyset$.

##  5\. The proof of the main theorems

###  5.1. The construction of
$f\colon\widehat{GC}(g_{1})\otimes\widehat{GC}(g_{1})\to\widehat{GC}(g_{\\#})$

For $i=1,\dots,n$ and $j=1,2$, let $O_{i}^{j}$ be the $O$-marking in the
$i$-th column of $g_{j}$. We choose $O_{n}^{1}$ and $O_{1}^{2}$ as the special
markings. Then we regard $\widehat{GC}(g_{1})$ as the chain complex of
$\mathbb{F}$-vector space with the basis $\\{V_{1}^{k_{1}}\cdots
V_{n-1}^{k_{n-1}}\cdot\mathbf{x}_{1}|k_{1},\dots,k_{n-1}\geqq
0,\mathbf{x_{1}}\in\mathbf{S}(g_{1})\\}$ and $\widehat{GC}(g_{2})$ as the
chain complex of $\mathbb{F}$-vector space with the basis
$\\{W_{2}^{l_{2}}\cdots
W_{n}^{l_{n}}\cdot\mathbf{x}_{2}|l_{2},\dots,l_{n}\geqq
0,\mathbf{x_{2}}\in\mathbf{S}(g_{2})\\}$, where the indices of the formal
variables correspond to the indices of $O$-markings.

For
$(\mathbf{x}_{1},\mathbf{x}_{2})\in\mathbf{S}(g_{1})\times\mathbf{S}(g_{2})$,
let $\mathbf{x}_{\\#}(\mathbf{x}_{1},\mathbf{x}_{2})$ be the state of
$\mathbf{N}_{0}(g_{\\#})$ naturally obtained by putting $\mathbf{x}_{1}$ and
$\mathbf{x}_{2}$ on the $n\times n$ blocks $g_{11}$ and $g_{22}$ respectively.

######  Definition 5.1.

Let
$f\colon\widehat{GC}(g_{1})\otimes\widehat{GC}(g_{2})\to\widehat{GC}(g_{\\#})$
be the linear map defined by for
$(\mathbf{x}_{1},\mathbf{x}_{2})\in\mathbf{S}(g_{1})\times\mathbf{S}(g_{2})$,

$f(\mathbf{x}_{1},\mathbf{x}_{2})=\mathbf{x}_{\\#}(\mathbf{x}_{1},\mathbf{x}_{2}),$

and

$f(V_{i}^{k_{i}})=U_{i}^{k_{i}},\ f(W_{j}^{l_{i}})=U_{n+j}^{l_{i}}.$

Because $g_{\\#}$ is obtained by two good grid diagrams, for a state of
$\mathbf{N}_{0}(g_{\\#})$, the rectangles counted by the differential of
$\widehat{GC}(g_{\\#})$ must change either two points in $g_{11}$ or two
points in $g_{22}$. In addition, direct computations show that
$M(\mathbf{x}_{1})+M(\mathbf{x}_{2})=M(\mathbf{x}_{\\#}(\mathbf{x}_{1},\mathbf{x}_{2}))$
and
$A(\mathbf{x}_{1})+A(\mathbf{x}_{2})=A(\mathbf{x}_{\\#}(\mathbf{x}_{1},\mathbf{x}_{2}))$.
Therefore $f$ is a chain map preserving the bigrading.

###  5.2. Simplification of the chain complex $\widehat{GC}(g_{\\#})$

We will observe the tilde-like chain complex of the quotient complex
$\widehat{GC}(g_{\\#})/\mathrm{Im}f$. In general, there is the simplest
version of grid homology called the tilde version which is the chain complex
of finite-dimensional vector space. The tilde chain complex is obtained from
the hat complex by letting every variable be zero. The homology of the tilde
complex and the size of the grid diagram deduce the homology of the hat
complex. In order to see that the quotient complex
$\widehat{GC}(g_{\\#})/\mathrm{Im}f$ is acyclic, we will observe the tilde-
like complex of $\widehat{GC}(g_{\\#})/\mathrm{Im}f$.

First, we check that multiplication by $U_{i}$ is chain homotopic to
multiplication by $U_{n+1}$ if $i\neq n$. Let $X_{i}$ be the $X$-marking of
$g_{\\#}$ in the $i$-th column of $g_{\\#}$ The marking $X_{i}$ is said to be
adjacent to $O_{j}$ if these two markings are in the same row or column. For
$i\neq n$, let
$\widetilde{\mathcal{H}}_{X_{i}}\colon\widehat{GC}(g_{\\#})/\mathrm{Im}f\to\widehat{GC}(g_{\\#})/\mathrm{Im}f$
be a homotopy operator

$\widetilde{\mathcal{H}}_{X_{i}}(\mathbf{x})=\sum_{\mathbf{y}\in\mathbf{S}(g_{\\#})}\left(\sum_{\\{r\in\mathrm{Rect}^{\circ}(\mathbf{x,y})|r\cap\mathbb{X}=\\{X_{i}\\},O_{n+1}\notin
r\\}}U_{1}^{O_{1}(r)}\cdots U_{n}^{O_{n}(r)}\cdot U_{n+2}^{O_{n+2}(r)}\cdots
U_{2n}^{O_{2n}(r)}\right)\mathbf{y}.$

This is the induced map of the homotopy operator for the minus chain complex
discussed in [13, Lemma 4.6.8].

######  Lemma 5.2.

Suppose that $X_{i}$ is adjacent to $O_{i}$ and $O_{j}$. If $i,j\neq n$, then

(5.1)
$\widetilde{\partial}\circ\widetilde{\mathcal{H}}_{X_{i}}+\widetilde{\mathcal{H}}_{X_{i}}\circ\widetilde{\partial}=U_{i}-U_{j},$

assuming that $U_{n+1}=0$.

###### Proof.

We refer to the notation in [13, Lemmas 4.6.7 and 4.6.9]. For the cases (R-1)
and (R-2), the same consequences as in the [13] follow in the same way as
[13]. For the case (R-3), we consider the states that give rise to a thin
annulus containing $X_{i}$. Let $\mathbf{y}$ be the state that appear in the
terms of $\widetilde{\mathcal{H}}_{X_{i}}(\mathbf{x})$. Suppose that there are
two rectangles $r_{1}\in\mathrm{Rect}^{\circ}(\mathbf{x,y})$ and
$r_{2}\in\mathrm{Rect}^{\circ}(\mathbf{y,x})$ such that $r_{1}*r_{2}$ is the
annulus of height or width $1$ and appear in
$\widetilde{\partial}\circ\widetilde{\mathcal{H}}_{X_{i}}+\widetilde{\mathcal{H}}_{X_{i}}\circ\widetilde{\partial}$.
Because the $X_{i}$ is not in the top row or $n+1$-th row and the annulus
$r_{1}*r_{2}$ contains $X_{i}$, both $\mathbf{x,y}$ are either in
$\mathbf{N}_{0}(g_{\\#})$ or
$\mathbf{S}(g_{\\#})\setminus\mathbf{N}_{0}(g_{\\#})$. Therefore two annuli of
height $1$ and width $1$ appear in
$\widetilde{\partial}\circ\widetilde{\mathcal{H}}_{X_{i}}+\widetilde{\mathcal{H}}_{X_{i}}\circ\widetilde{\partial}$,
so (5.1) holds for $i,j\neq n$. ∎

######  Proposition 5.3.

Let
$C=\frac{\widehat{GC}(g_{\\#})/\mathrm{Im}f}{U_{1}=\dots=U_{n-1}=U_{n+2}=\dots=U_{2n}=0}$.
Let $W=\mathbb{F}_{0,0}\oplus\mathbb{F}_{-1,-1}$ be the two-dimensional
bigraded vector space. Then, there is an isomorphism

$H(C)\cong H(\widehat{GC}(g_{\\#})/\mathrm{Im}f)\otimes W^{\otimes(2n-2)}$

of bigraded vector spaces.

###### Proof.

The proof is the same as [13, Proposition 4.6.15]. We remark that by Lemma
5.2, if $i\neq n$, we have $U_{i}\simeq U_{n+1}=0$ in
$\widehat{GC}(g_{\\#})/\mathrm{Im}f$. ∎

###  5.3. The proof of Theorem 1.1

###### proof of Theorem 1.1.

We will see that $\widehat{GC}(g_{\\#})/\mathrm{Im}f$ is acyclic. By
Proposition 5.3, it is sufficient to prove that $C$ is acyclic.

For $k=1,\dots,n$, let $I_{k}$ and $N_{k}$ be the spans of
$\mathbf{I}_{k}(g_{\\#})$ and $\mathbf{N}_{k}(g_{\\#})$ respectively. Then
$\widehat{GC}(g_{\\#})$ is a direct sum of infinitely many subspaces, where
each summand is written as $U_{1}^{k_{1}}\cdots U_{n}^{k_{n}}\cdot
U_{n+2}^{k_{n+2}}\cdots U_{2n}^{k_{2n}}\cdot I_{k}$ or $U_{1}^{k_{1}}\cdots
U_{n}^{k_{n}}\cdot U_{n+2}^{k_{n+2}}\cdots U_{2n}^{k_{2n}}\cdot N_{k}$ for
non-negative integers $k_{1},\dots,k_{2n}$. By the construction of the chain
map $f$ (Section 5.1), as the vector space,
$\mathrm{Im}f\cong\bigoplus_{k_{1},\dots,k_{n-1},k_{n+2},\dots,k_{2n}\geqq
0}(U_{1}^{k_{1}}\cdots U_{n-1}^{k_{n-1}}\cdot U_{n+2}^{k_{n+2}}\cdots
U_{2n}^{k_{2n}}\cdot N_{0}).$ We remark that $k_{n}=0$ in the above equation.
Therefore
$C=\frac{\widehat{GC}(g_{\\#})/\mathrm{Im}f)}{U_{1}=\dots=U_{n-1}=U_{n+2}=\dots=U_{2n}=0}$
is written as directed sums of infinitely many vector spaces

$\displaystyle C$ $\displaystyle\cong(N_{1}\oplus\dots\oplus N_{n}\oplus
I_{1}\oplus\dots\oplus I_{n})$ $\displaystyle\oplus
U_{n}\cdot(N_{0}\oplus\dots\oplus N_{n}\oplus I_{1}\oplus\dots\oplus I_{n})$
$\displaystyle\oplus U_{n}^{2}\cdot(N_{0}\oplus\dots\oplus N_{n}\oplus
I_{1}\oplus\dots\oplus I_{n})$ $\displaystyle\oplus\dots$

Because of the markings on $g_{\\#}$, the induced differential $\partial$ of
$C$ satisfies that for $j\geqq 1$ and $k\geqq 0$,

$\displaystyle\partial(U_{n}^{k}N_{j})$ $\displaystyle\subset
U_{n}^{k}N_{j-1}\oplus U_{n}^{k}N_{j}\oplus U_{n}^{k}I_{j}\oplus
U_{n}^{k+1}N_{j-1},$ $\displaystyle\partial(U_{n}^{k}I_{j})$
$\displaystyle\subset U_{n}^{k}I_{j-1}\oplus U_{n}^{k}I_{j}\oplus
U_{n}^{k+1}N_{j-1},$ $\displaystyle\partial(U_{n}^{k}N_{0})$
$\displaystyle\subset U_{n}^{k}N_{0},$

where $I_{0}$ is the trivial vector space. We will represent these relations
with the following schematic picture:

$\textstyle{N_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{N_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{N_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{I_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{I_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{I_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}N_{0}}$$\textstyle{U_{n}N_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}N_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}N_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}I_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}I_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}I_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}N_{0}}$$\textstyle{U_{n}^{2}N_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}N_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}N_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}I_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}I_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\cdots\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{U_{n}^{2}I_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\vdots}}$$\textstyle{{\vdots}}$$\textstyle{{\vdots}}$$\textstyle{{\vdots}}$$\textstyle{{\vdots}}$

Then this picture deduces that $U_{n}^{i}I_{1}\oplus U_{n}^{i+1}N_{0}$ forms
the subcomplex of $C$ for $i\geqq 0$.

The proof that $C$ is acyclic goes in two steps. First, we will prove that
each subcomplex $U_{n}^{i}I_{1}\oplus U_{n}^{i+1}N_{0}$ is acyclic. Then we
will check that the quotient complex $C/\bigoplus_{i\geqq
0}(U_{n}^{i}I_{1}\oplus U_{n}^{i+1}N_{0})$ is also acyclic.

  1. (STEP 1)

As each subcomplex $U_{n}^{i}I_{1}\oplus U_{n}^{i+1}N_{0}$ is isomorphic to
$I_{1}\oplus U_{n}N_{0}$, it is sufficient to consider $I_{1}\oplus
U_{n}N_{0}$. For each state $\mathbf{x}\in\mathbf{I}_{1}(g_{\\#})$, the part
of $\partial(\mathbf{x})$ into $U_{n}N_{0}$ counts exactly one rectangle.
Direct computations show that
$\\#\mathbf{N}_{0}(g_{\\#})=\\#\mathbf{I}_{1}(g_{\\#})=n!\times n!$. The part
of the differential $I_{1}\to U_{n}N_{0}$ is naturally a chain map (Figure 4).
Therefore $I_{1}\oplus U_{n}N_{0}$ is acyclic because it forms a mapping cone
of an isomorphism.

  2. (STEP 2)

The quotient complex $C/\bigoplus_{i\geqq 0}(U_{n}^{i}I_{1}\oplus
U_{n}^{i+1}N_{0})$ is the directed sum of infinitely many copies of
$N_{1},\dots,N_{n},I_{2},\dots,I_{n}$ as vector space. Using the following
lemma repeatedly, combining [8, Lemmas 5.1 and 5.3], we conclude that the
quotient complex $C/\bigoplus_{i\geqq 0}(U_{n}^{i}I_{1}\oplus
U_{n}^{i+1}N_{0})$ is acyclic.

######  Lemma 5.4.

Let $C^{\prime}$ be the subcomplex of $C$. If $C^{\prime}$ and $C/C^{\prime}$
are acyclic, then $C$ is acyclic.

∎

###  5.4. The proof of Theorem 1.3

######  Lemma 5.5.

Let $g_{1}$ and $g_{2}$ be good grid diagrams representing Legendrian knots
$\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ respectively. Let $g_{\\#}$ be the
grid diagram from $g_{1}$ and $g_{2}$ (described in Section 4.1). Then
$g_{\\#}$ represents the connected sum of Legendrian knots
$\mathcal{K}_{1}\\#\mathcal{K}_{2}$.

###### Proof.

The front projection determined by $g_{\\#}$ naturally represents the
connected sum of $K_{1}$ and $K_{2}$, either Legendrian Reidemeister move $1$
(Figure 4).

Figure 4. Left$\colon$A front projection of $K_{1}\sqcup K_{2}$.
Right$\colon$The front projection determined by $g_{\\#}$

∎

###### proof of Theorem 1.3.

By the construction of $g_{\\#}$ and $f$, $f$ sends
$\mathbf{x}^{+}(g_{1})\otimes\mathbf{x}^{+}(g_{2})$ to
$\mathbf{x}^{+}(g_{\\#})$ and
$\mathbf{x}^{-}(g_{1})\otimes\mathbf{x}^{-}(g_{2})$ to
$\mathbf{x}^{-}(g_{\\#})$. Then Lemma 5.5 and Theorem 3.1 complete the proof.
∎

## References

  * [1] John A. Baldwin, Tye Lidman, and C.-M. Michael Wong, _Lagrangian cobordisms and Legendrian invariants in knot Floer homology_ , Michigan Math. J. 71 (2022), no. 1, 145–175. MR 4389674
  * [2] Yuri Chekanov, _Differential algebra of Legendrian links_ , Invent. Math. 150 (2002), no. 3, 441–483. MR 1946550
  * [3] Peter R. Cromwell and Ian J. Nutt, _Embedding knots and links in an open book. II. Bounds on arc index_ , Math. Proc. Cambridge Philos. Soc. 119 (1996), no. 2, 309–319. MR 1357047
  * [4] Subhankar Dey and Hakan Doğa, _A combinatorial description of the knot concordance invariant epsilon_ , J. Knot Theory Ramifications 30 (2021), no. 6, Paper No. 2150036, 26. MR 4305516
  * [5] John B. Etnyre, _Legendrian and transversal knots_ , Handbook of knot theory, Elsevier B. V., Amsterdam, 2005, pp. 105–185. MR 2179261
  * [6] Viktória Földvári, _The knot invariant $\Upsilon$ using grid homologies_, J. Knot Theory Ramifications 30 (2021), no. 7, Paper No. 2150051, 26. MR 4321933
  * [7] Hajime Kubota, _Concordance invariant $\Upsilon$ for balanced spatial graphs using grid homology_, arXiv:2206.15048v2, 2022.
  * [8] Hajime Kubota, _Grid homology for spatial graphs and a künneth formula of connected sum_ , 2023.
  * [9] Paolo Lisca, Peter Ozsváth, András I. Stipsicz, and Zoltán Szabó, _Heegaard Floer invariants of Legendrian knots in contact three-manifolds_ , J. Eur. Math. Soc. (JEMS) 11 (2009), no. 6, 1307–1363. MR 2557137
  * [10] Ciprian Manolescu, Peter Ozsváth, Zoltán Szabó, and Dylan Thurston, _On combinatorial link Floer homology_ , Geom. Topol. 11 (2007), 2339–2412. MR 2372850
  * [11] Lenhard Ng, Peter Ozsváth, and Dylan Thurston, _Transverse knots distinguished by knot Floer homology_ , J. Symplectic Geom. 6 (2008), no. 4, 461–490. MR 2471100
  * [12] Peter Ozsváth, Zoltán Szabó, and Dylan Thurston, _Legendrian knots, transverse knots and combinatorial Floer homology_ , Geom. Topol. 12 (2008), no. 2, 941–980. MR 2403802
  * [13] Peter S. Ozsváth, András I. Stipsicz, and Zoltán Szabó, _Grid homology for knots and links_ , Mathematical Surveys and Monographs, vol. 208, American Mathematical Society, Providence, RI, 2015. MR 3381987
  * [14] Sucharit Sarkar, _Grid diagrams and the Ozsváth-Szabó tau-invariant_ , Math. Res. Lett. 18 (2011), no. 6, 1239–1257. MR 2915478
  * [15] by same author, _Grid diagrams and the Ozsváth-Szabó tau-invariant_ , Math. Res. Lett. 18 (2011), no. 6, 1239–1257. MR 2915478
  * [16] Vera Vértesi, _Transversely nonsimple knots_ , Algebr. Geom. Topol. 8 (2008), no. 3, 1481–1498. MR 2443251


# Hierarchical Constrained Stochastic Shortest Path Planning via Cost Budget
Allocation

Sungkweon Hong1 and Brian C. Williams1 1Computer Science and Artificial
Intelligence Lab, Massachusetts Institute of Technology, Cambridge, MA 01239,
USA, {sk5050<EMAIL_ADDRESS>The work was supported by the Boeing
Corporation.

###### Abstract

Stochastic sequential decision making often requires hierarchical structure in
the problem where each high-level action should be further planned with
primitive states and actions. In addition, many real-world applications
require a plan that satisfies constraints on the secondary costs such as risk
measure or fuel consumption. In this paper, we propose a hierarchical
constrained stochastic shortest path problem (HC-SSP) that meets those two
crucial requirements in a single framework. Although HC-SSP provides a useful
framework to model such planning requirements in many real-world applications,
the resulting problem has high complexity and makes it difficult to find an
optimal solution fast which prevents user from applying it to real-time and
risk-sensitive applications. To address this problem, we present an algorithm
that iteratively allocates cost budget to lower level planning problems based
on branch-and-bound scheme to find a feasible solution fast and incrementally
update the incumbent solution. We demonstrate the proposed algorithm in an
evacuation scenario and prove the advantage over a state-of-the-art
mathematical programming based approach.

##  I Introduction

As human beings, making decisions is one of the daily tasks to improve our
lives, where many, if not most, decisions are sequential. Sequential decision
making has been one of the core topics in Artificial Intelligence (AI) to
support those pervasive tasks [ernst2004power, silver2017mastering,
cassandra1998survey]. The major role of sequential decision making is
generating a course of actions that achieves the goals of an agent. Actions
are defined from the domain of the problem and describe the states where they
can be executed and how the states are changed by executing them. In
commercial aircraft operation, for example, nominal unit operations are based
on air route segments and standard departure/arrival procedures, and hence
those can be reasonable choices of actions sets.

In sequential decision making problems, a crucial assumption is that the
actions are well defined and an agent is capable of executing those actions.
For many real-world problems, however, such assumption is too strong to hold,
especially for online applications. Again, in aircraft operations, even though
each air route segment is well established and can be flown as a routine
procedure, there might be a novel circumstance that prohibits an aircraft from
flying the segment as published, such as convective weather conditions. In
such situation, travelling the air route segment forms another planning
problem, which makes the problem hierarchical.

In fact, hierarchical structure in the planning problem has been widely
studied in stochastic sequential decision making problems [sutton1999between,
theocharous2004approximate, lim2011monte, omidshafiei2017decentralized,
amato2014planning]. In those works, options, also known as macro actions or
skills, were introduced to abstract the underlying problem space into a
higher-level space to scale both learning and planning processes. However,
most of the works in hierarchical planning focus on minimizing the expected
cost (or maximizing the expected reward). In many of the real-world
applications, however, naively minimizing the expected cost might not be
desirable. For example, when we want an aircraft to navigate to the
destination as fast as possible, it is also important to ensure the aircraft
can complete the mission with the onboard fuel or stays outside of the unsafe
region for safety.

Despite being non-hierarchical, stochastic sequential decision making problems
have been widely extended to include constraints. One of the most well-known
frameworks is constrained stochastic shortest path problems (C-SSPs)
[altman1999constrained], which optimize the primary cost function while
constraining the secondary cost functions. In this paper, we propose a new
framework, hierarchical constrained stochastic shortest path problem (HC-SSP),
that extends C-SSP to hierarchical problem structure. To the authors’
knowledge, this extension has been little attempted, yet there is some work on
this direction [feyzabadi2015hcmdp]. However, the previous work focuses on
abstracting the existing state space to find an approximated solution to the
original problem. In our approach, on the other hand, we focus on finding
(near-)optimal solution given the hierarchical structure of the problem.

Although the extension from C-SSP to HC-SSP looks straightforward, this
extension poses a unique challenge that has not been present in the previous
works. A hierarchical approach has its advantage based on decoupled high-level
actions that can be learned individually. However, with a constraint, they are
no longer decoupled due to shared cost budget given by the constraint. To
address this problem, we propose a cost budget allocation approach based on
the well-known branch-and-bound scheme.

This paper makes two main contributions. First, we propose a hierarchical
constrained stochastic shortest path problem (HC-SSP) that extends C-SSP with
hierarchical structure. Second, we propose a budget-allocation-based algorithm
that finds a deterministic hierarchical policy to a HC-SSP in an anytime
fashion. The algorithm is shown to be theoretically optimal given a specific
condition and can be approximated based on the user-defined approximation
level. The experimental results show that the algorithm can find near-optimal
solutions in most cases even with high approximation level.

The remainder of this paper is organized as follows. Section II summarizes the
most relevant backgrounds to our work. Section III presents the proposed HC-
SSP problem definition with an intuitive example. Section IV elaborates our
proposed algorithm, followed by evaluation results in Section
LABEL:sec_experiments. Finally, we conclude and present future work in Section
LABEL:sec_conclusion.

##  II Preliminaries

###  II-A Constrained Stochastic Shortest Path Problem

A constrained stochastic shortest path problem (C-SSP) is a tuple
$\langle\mathcal{S},\bar{s},\mathcal{G},\mathcal{A},T,\vec{C},\vec{\Delta}\rangle$
in which $\mathcal{S}$ is a set of discrete states; $\bar{s}\in\mathcal{S}$ is
the initial state; $\mathcal{G}\subset\mathcal{S}$ is a set of goal states;
$\mathcal{A}$ is a set of discrete actions;
$T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is the state
transition function, where $T(s,a,s^{\prime})=Pr(s^{\prime}|s,a)$ is the
probability of being in state $s^{\prime}$ after executing action $a$ in state
$s$; $\vec{C}$ is the indexed set of cost functions $\\{C_{0},...,C_{N}\\}$,
where each
$C_{i}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}_{+}$
is the cost function and $C_{i}(s,a,s^{\prime})$ is the $i$-th cost of
executing action $a$ in the state $s$ and resulting in the state $s^{\prime}$;
and $\vec{\Delta}$ is the indexed set of bounds
$\\{\Delta_{1},\dots,\Delta_{N}\\}$, where $\Delta_{i}$ is the bound for
$i$-th cost function for $i=1,\dots,N$ [altman1999constrained,
trevizan2016heuristic].

A solution to a C-SSP is a policy
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ which maps states to a
probability distribution over actions. If a policy maps every state to a
probability distribution with a single outcome, the policy is called
“deterministic,” and is called “stochastic” otherwise. In the former case, we
denote $\pi(s)$ as the action selected by the policy $\pi$ for the state $s$.

An optimal solution to a C-SSP is a policy $\pi^{*}$ which minimizes the total
expected cost, but in addition, the expected cost of the secondary cost
function $C_{i}$ should be upper bounded by $\Delta_{i}$ for $i=1,\dots,N$. In
other words, an optimal policy $\pi^{*}$ for a C-SSP is defined as follows:

$\displaystyle\underset{\pi\in\Pi}{\text{argmin}}\qquad$ $\displaystyle
f(\pi)$ s.t. $\displaystyle g_{i}(\pi)\leq 0\quad\text{for $i=1,\dots,N$},$

where $\Pi$ is the set of all policies and

$\displaystyle f(\pi)$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=0}^{\infty}C_{0}(s_{t},a_{t},s_{t+1})\bigg{|}s_{0}=\bar{s},\pi\Bigg{]}$
$\displaystyle g_{i}(\pi)$
$\displaystyle=\mathbb{E}\Bigg{[}\sum_{t=0}^{\infty}C_{i}(s_{t},a_{t},s_{t+1})\bigg{|}s_{0}=\bar{s},\pi\Bigg{]}-\Delta_{i}.$

Note that every optimal policy for a C-SSP might be stochastic
[altman1999constrained]. In this paper, however, we limit the policy space to
deterministic ones which are preferred due to explainability and reliability
in the safety-critical applications such as aircraft operations. Note that it
is known that limiting the policy space to deterministic ones significantly
increases the complexity of the problem [feinberg2000constrained].

###  II-B Anytime Algorithm for C-SSPs

In this section, we introduce a recently developed anytime algorithm for
C-SSPs in [hong2021anytime] which we use as a subroutine in our proposed
method. The algorithm has two stages where the first stage finds a Lagrangian
dual solution of a C-SSP and then the second stage incrementally closes a
duality gap, if there is any. In the first stage, the Lagrangian function is
defined as follows:

$\displaystyle L(\lambda,\pi)=f(\pi)+\lambda\cdot g(\pi),$ (1)

where $\lambda=[\lambda_{1},\dots,\lambda_{N}]\in\mathbb{R}_{+}^{N}$ and
$g=[g_{1},\dots,g_{N}]^{\top}$. Then the Lagrangian dual problem is defined as
follows:

$\displaystyle L^{*}=L(\lambda^{*})=\max_{\lambda\geq 0}L(\lambda),$ (2)

where

$\displaystyle L(\lambda)=\min_{\pi\in\Pi}L(\lambda,\pi).$ (3)

Note that the following statement holds, according to the weak duality
[boyd2004convex]:

$\displaystyle L(\lambda)\leq f^{*},\quad\forall\lambda\geq 0,$ (4)

where $f^{*}$ is the primal optimal cost. If $L(\lambda)=f^{*}$, where the
strong duality holds, the dual solution coincides with a true optimal
solution. However, strong duality usually does not hold in our problem and a
duality gap exists. The purpose of the second stage is to reduce such gap and
find a primal optimal solution.

Figure 1: Visualization of the second stage of the anytime algorithm.

Conceptually, the way the algorithm obtains a primal optimal policy is quite
simple. From the dual optimal policy, we can find a primal optimal solution by
iteratively finding the next best solutions, with respect to the Lagrangian
function value $L(\lambda^{*},\pi)$. This procedure is illustrated in Fig. 1
with an intuitive example which only includes a single secondary cost
function. The figure shows all the deterministic policies in $(\lambda,L)$
space, including feasible ones ($g_{1}(\pi)\leq 0$) and infeasible ones
($g_{1}(\pi)>0$), in green solid lines and red dotted lines, respectively.
Note that the true primal optimal policy $\pi^{*}$ is indicated with a bold
line. Fig. 1 also shows the Lagrangian function value $L(\lambda^{*},\pi)$ for
each policy as an intersection of the policy with the dotted vertical line at
$\lambda^{*}$. Similarly, a $y$-intercept of a policy $\pi$ is the primal cost
$f(\pi)$. In addition, $\pi^{1}$ is the solution associated with $\lambda^{*}$
which can be obtained from the first stage, where $\pi^{k}$ denotes $k$-th
best policy with respect to the Lagrangian function value
$L(\lambda^{*},\pi)$. Starting from $\pi^{1}$, we find the next best policies
in terms of $L(\lambda^{*},\pi)$, in a non-decreasing manner, until we obtain
a primal optimal policy $\pi^{*}$, and update the incumbent policy whenever we
obtain a better feasible policy. Note that the Lagrangian function value and
incumbent cost at any time set lower and upper bounds on the optimal cost of
the C-SSP, respectively. We refer to [hong2021anytime] for the details of the
anytime algorithm.

##  III Hierarchical Constrained Stochastic Shortest Path Problem

In this section, we define a hierarchical constrained stochastic shortest path
problem (HC-SSP). We begin this section with an intuitive example of a HC-SSP
followed by a formal definition.

###  III-A HC-SSP in a Nutshell

Consider a grounded example shown in Fig. 2, in which a robot is evacuating
from a building with six rooms in a hazardous environment. In this example, a
robot should make a series of decisions about which hallway or door to
approach to get to the exit point. At a quick glance, using door 1 and door 2
seems to let the robot evacuate faster than the other options. However, the
decision should be made carefully since the robot has only partial information
on the building: the robot knows that the hallways are always clear, but also
knows that the doors are locked with a 0.1 probability, in which case the
robot should take a roundabout way. By assuming that a set of activities that
move a robot from a specific landmark to another is well defined, the problem
can be formulated as a conditional procedural planning problem, which is shown
in Fig. 3 graphically. Note that, each circle and oval represents a notable
event and activities, respectively. Also note that, double circle and dotted
double circle represent controllable and uncontrollable choices, respectively.

Figure 2: Illustration of the robot evacuation scenario. Figure 3: Graphical
representation of the procedural planning problem for the evacuation scenario
in Fig. 2. An example of planning problem for go-to-door1 activity is also
shown, where red shaded states are hazardous states and blue and green states
are initial and goal states, respectively.

One of the keys to our approach is noting that each activity (e.g., go-to-
door1) is not necessarily predefined. Rather, each of the activities can be
defined as an another planning problem with its own state and action space.
For example, each activity can be considered as a stochastic shortest path
problem in a grid world as shown in Fig. 3.

Another key to our approach is constraints on secondary costs defined over a
set of activities. Consider a global constraint for the evacuation scenario is
defined verbally as follows: “The damage caused by fire must be less than or
equal to $\Delta$ until evacuation.” With such constraint, the planning
problem for go-to-door1 in Fig. 3 is now a constrained stochastic shortest
path problem.

There is another yet more important implication of having such global
constraint. Due to the global constraint, activities are no longer
independent. Suppose we are planning for an activity go-to-door1 as a sub-
problem for our evacuation planning problem. Then, how much of the cost out of
the global damage budget $\Delta$ should be allocated for this activity? For
example, using budget parsimoniously in planning go-to-door1 might result in a
conservative and sub-optimal plan if optimal solutions for other activities
cause negligible damage. On the other hand, using too much of the budget in
planning go-to-door1 might result in sub-optimality as well, since other
activities could reduce global cost by using more budget. This motivates us to
allocate the budget systematically for different activities to obtain global
optimality which will be discussed in more detail in Section IV.

Finally, a solution to HC-SSP is a hierarchical policy that consists of both
procedural policy and policies for every associated activity. There are two
desirable properties for a solution. First, the solution should be feasible,
which means that the solution should not violate any constraint. In the
evacuation scenario, we only have one global constraint that requires the
damage caused by fire to be less than or equal to $\Delta$. Therefore, the
weighted sum of the damage cost for every activity that is selected by a
procedural policy should be less than or equal to $\Delta$, where a weight for
an activity is the likelihood of executing that activity. Second, the solution
should minimize the expected cost. It is not always possible, however, to
obtain an optimal solution, especially when the planning time is limited.
Therefore, we want to develop a solution method with an anytime property which
can output an incumbent feasible solution at timeout while the solution
eventually converges to a true optimal solution with sufficient planning time.

###  III-B Problem Definition

A HC-SSP is a tuple
$\langle\mathcal{S},\mathcal{I},\mathcal{T},\mathcal{V},\mathcal{E},\mathcal{P},\\{\mathcal{C}_{j}\\}_{j\in
J}\rangle$, where

  * •

$\mathcal{S}$ is a set of discrete states.

  * •

$\mathcal{I}:\mathcal{S}\rightarrow[0,1]$ is the initial distribution.

  * •

$\mathcal{T}$ is a set of notable events. Note that $t^{s}$ and $t^{e}$ are
two special events, where $t^{s}$ is the start event and $t^{e}$ is the end
event.

  * •

$\mathcal{V}$ is a set of choice variables, each $v\in\mathcal{V}$ being a
discrete, finite domain variable. Note that each $v\in\mathcal{V}$ is
associated with an event $t\in\mathcal{T}$, where we denote
$\mathcal{V}(t)=v$.

  * •

$\mathcal{E}$ is a set of activities. An activity $E\in\mathcal{E}$ is
activated if both start and end events of the activity are activated.

  * •

$\mathcal{P}:\mathcal{T}\times\bigcup_{t\in\mathcal{T}}\text{Dom}\\{\mathcal{V}(t)\\}\times\mathcal{T}\rightarrow[0,1]$
is a probabilistic transition function between events based on the assignments
of choice variables, where $\mathcal{P}(t,a,t^{\prime})=Pr(t^{\prime}|t,a)$ is
the probability of being in event $t^{\prime}$ after executing choice $a$ in
event $t$.

  * •

$\\{\mathcal{C}_{j}\\}_{j\in J}$ is an indexed set of constraints, where
$J=\\{1,\dots,M\\}$ and $M$ is the number of constraints. Each
$\mathcal{C}_{j}$ is a tuple $\langle\Psi_{j},I_{j},\Delta_{j}\rangle$, where
$\Psi_{j}\subset\mathcal{E}$ is a set of activities associated with the
constraint $\mathcal{C}_{j}$, $\Delta_{j}$ is an upper bound and
$I_{j}:\Psi_{j}\rightarrow\mathbb{N}$ is an index function for each
$E\in\Psi_{j}$ that indicates which secondary cost function is used for
$\mathcal{C}_{j}$. Note that in this paper we assume that a secondary cost
function of an activity is included in at most one constraint for simplicity.
This assumption, however, can be easily generalized with little modification.

A HC-SSP abstracts the underlying state-action space and dynamics based on
events and activities, where the activities are selected by choice variables
and the transitions between events are governed by transition function
$\mathcal{P}$. Then each activity is defined over a subset of underlying state
space and has its own action space and dynamics with its sub-goal. Formally,
an activity $E\in\mathcal{E}$ is a tuple $\langle
t_{E}^{s},t_{E}^{e},\mathcal{S}_{E},\mathcal{A}_{E},T_{E},\vec{C}_{E},\mathcal{G}_{E}\rangle$,
where

  * •

$t_{E}^{s},t_{E}^{e}\in\mathcal{T}$ are the start and end events of the
activity, respectively.

  * •

$\mathcal{S}_{E}\subset\mathcal{S}$ is a set of discrete states.

  * •

$\mathcal{A}_{E}$ is a set of discrete actions.

  * •

$T_{E}:\mathcal{S}_{E}\times\mathcal{A}_{E}\times\mathcal{S}_{E}\rightarrow[0,1]$
is the state transition function, where
$T_{E}(s,a,s^{\prime})=Pr(s^{\prime}|s,a)$ is the probability of being in
state $s^{\prime}$ after executing action $a$ in state $s$.

  * •

$\vec{C}_{E}=\\{C_{E}^{0},...,C_{E}^{N_{E}}\\}$ is an indexed set of cost
functions, where each
$C_{E}^{i}:\mathcal{S}_{E}\times\mathcal{A}_{E}\times\mathcal{S}_{E}\rightarrow\mathbb{R}_{+}$
is the $i$-th cost function that defines the $i$-th cost of executing action
$a$ in state $s$ and resulting in state $s^{\prime}$ and $N_{E}$ is the number
of secondary cost functions for the activity $E$.

  * •

$\mathcal{G}_{E}\subset\mathcal{S}_{E}$ is the set of goal state.

In this paper, we refer to the planning problem over the events and activities
as procedural planning and the planning problem for each activity as activity
planning, which will be discussed in more detail in Section IV-B.

###  III-C Solution to HC-SSP

A solution to a HC-SSP problem is a tuple $\langle\rho,\Gamma\rangle$, where

  * •

$\rho$ is a procedural policy which fully assigns every choice variable
$\mathcal{V}$.

  * •

$\Gamma$ is a set of policies for every activated activity by $\rho$, where a
policy $\Gamma_{E}:\mathcal{S}_{E}\rightarrow\mathcal{A}_{E}$ is a mapping
from states to actions for an activity $E$.

Note that, abusing the notation, $E\in\rho$ if an activity $E\in\mathcal{E}$
is activated by $\rho$, and $E\not\in\rho$ otherwise. Then, an optimal
solution to a HC-SSP is defined as follows:

$\displaystyle\underset{\rho,\Gamma}{\text{argmin}}\quad$
$\displaystyle\mathbb{E}_{E\sim\rho}\Big{[}f^{E}\big{(}\Gamma_{E}\big{)}\Big{]}$
(5) s.t. $\displaystyle\mathcal{I}=\Gamma_{E}^{I}\text{ for }E\in\rho\text{
such that }t_{E}^{s}=t^{s},$ (6)
$\displaystyle\Gamma_{E}^{T}=\Gamma_{E^{\prime}}^{I}\text{ for
}E,E^{\prime}\in\rho\text{ such that }t_{E}^{e}=t_{E^{\prime}}^{s},$ (7)
$\displaystyle\sum_{E\in\Psi_{j}}L(E|\rho)\cdot
g_{I_{j}(E)}^{E}\big{(}\Gamma_{E}\big{)}\leq\Delta_{j}\text{ for }j\in J,$ (8)

where $\Gamma_{E}^{I}$ and $\Gamma_{E}^{T}$ are initial and termination
distributions of the policy $\Gamma_{E}$ for an activity $E$, respectively,
$L(E|\rho)$ is a likelihood of executing an activity $E$ given procedural
policy $\rho$, and $f^{E}(\Gamma_{E})$ is the expected primary cost for an
activity $E$ which is defined as follows:

$\displaystyle
f^{E}(\Gamma_{E})=\mathbb{E}\Bigg{[}\sum_{t=0}^{\infty}C_{E}^{0}(s_{t},a_{t},s_{t+1})\bigg{|}\Gamma_{E}^{I},\Gamma_{E}\Bigg{]},$

and $g_{i}^{E}(\Gamma_{E})$ is the expected $i$-th secondary cost for an
activity $E$ which is defined as follows:

$\displaystyle
g_{i}^{E}(\Gamma_{E})=\mathbb{E}\Bigg{[}\sum_{t=0}^{\infty}C_{E}^{i}(s_{t},a_{t},s_{t+1})\bigg{|}\Gamma_{E}^{I},\Gamma_{E}\Bigg{]}.$

##  IV Approach

In this section, we present our proposed approach for a HC-SSP. We begin with
an intuitive introduction of the approach and then present algorithms and
formal analysis.

###  IV-A Overview

For the purpose of illustration, let us consider a simple problem shown in
Fig. 4a which has two activities and a single constraint including both
activities. Our approach is based on the fact that we can decouple the
procedural and each activity planning problems if the constraint budget
$\Delta$ is allocated properly to each of the activities.

Fig. 4b shows the constraint budget allocation space for the example problem,
where $x-$ and $y-$axes are the allocated budget for activities $E_{1}$ and
$E_{2}$, respectively, and the green shaded region conceptually shows the
region where a feasible solution to HC-SSP exists. Then if we allocate a
specific budget to $E_{1}$ and $E_{2}$, respectively, then we can find
policies for each activity based on the allocation, which in turn allows us to
find procedural policy based on $f$ and $g$ values of each activity. However,
since the allocation space is continuous, it is computationally intractable to
check every possible budget allocation to find an optimal solution. Instead,
we frame the allocation problem based on the branch-and-bound scheme
[balakrishnan1991branch, horst2013global].

(a) Example procedural planning problem with two activities.

(b) Budget allocation space where $x-$ and $y-$ axes are allocated cost budget
for $E_{1}$ and $E_{2}$.

Figure 4: Illustration of budget allocation for an example with only two
activities and a single global constraint.

Let $M^{-}_{E,I_{j}(E)}$ and $M^{+}_{E,I_{j}(E)}$ be lower and upper limits of
budget allocation for a constraint $\mathcal{C}_{j}$ and an activity
$E\in\Psi_{j}$. Then the allocation space that we are interested in, which we
denote as $\mathcal{Q}_{\text{init}}$, is defined as follows:

$\displaystyle\mathcal{Q}_{\text{init}}=\prod_{j\in
J}\prod_{E\in\Psi_{j}}\Big{[}M^{-}_{E,I_{j}(E)},M^{+}_{E,I_{j}(E)}\Big{]}.$

Note that a simple choice of such lower and upper limits for $E\in\Psi_{j}$ is
$0$ and $\frac{1}{L(E)}\cdot\Delta_{j}$, where $L(E)$ is the minimum
likelihood of activity $E$, although a more sophisticated bound can be found
based on pre-processing. Then the branch-and-bound algorithm keeps splitting
$\mathcal{Q}_{\text{init}}$ into smaller partitions and computes upper
($\alpha$) and lower bounds ($\beta$) for the newly generated partitions,
which can be used not only to guide the search toward an optimal solution but
also to determine the quality of the current incumbent solution.

Algorithm 1 shows the branch-and-bound algorithm for a HC-SSP, where
$\alpha(\mathcal{Q})$ and $\beta(\mathcal{Q})$ denote upper and lower bounds
for a partition $\mathcal{Q}$, respectively, and $\alpha_{k}$ and $\beta_{k}$
denotes global upper and lower bounds at the $k$-th iteration, respectively.
After initialization (lines 1–9), the algorithm splits a partition with the
lowest lower bound into two partitions along its longest edge to form a new
partition (lines 11–13). Then it computes lower and upper bounds for newly
generated partitions (lines 14–19) and updates the global lower and upper
bounds (lines 20–21). In addition, whenever a better feasible solution is
found, it updates the incumbent solution (lines 4–6 and 16–18).

The core parts of Algorithm 1 are Compute-LB and Compute-UB subroutines which
highly affect the performance of the algorithm. Before presenting the proposed
Compute-LB and Compute-UB subroutines, let us begin with introducing
procedural and activity planning in more detail, which has been briefly
introduced in Section III-B.

Input: HC-SSP instance $\mathcal{H}$, initial budget allocation space
$\mathcal{Q}_{\text{init}}$, approximation parameter $l$, optimality tolerance
$\epsilon$

1 $k=0$

2 $\mathcal{M}_{0}=\\{\mathcal{Q}_{\text{init}}\\}$

3 $\alpha(\mathcal{Q}_{\text{init}}),\langle\rho_{0},\Pi_{0}\rangle\leftarrow$
Compute-UB($\mathcal{H}$, $\mathcal{Q}_{\text{init}}$, $l$)

4 if  _$\langle\rho_{0},\Pi_{0}\rangle$ is not None_ then

5
$\langle\rho_{\text{inc}},\Pi_{\text{inc}}\rangle\leftarrow\langle\rho_{0},\Pi_{0}\rangle$

6 $\alpha_{\text{inc}}\leftarrow\alpha(\mathcal{Q}_{\text{init}})$

7$\beta(\mathcal{Q}_{\text{init}})\leftarrow$ Compute-LB($\mathcal{H}$,
$\mathcal{Q}_{\text{init}}$, $l$)

8 $\alpha_{0}\leftarrow\alpha(\mathcal{Q}_{\text{init}})$

9 $\beta_{0}\leftarrow\beta(\mathcal{Q}_{\text{init}})$

10 while  _$\alpha_{k}-\beta_{k} >\epsilon$_ do

11
$\mathcal{Q}_{k}\leftarrow\text{argmin}_{\mathcal{Q}\in\mathcal{M}_{k}}\beta(\mathcal{Q})$

12 split $\mathcal{Q}_{k}$ along one of its longest edges into
$\mathcal{Q}^{\prime}_{k}$ and $\mathcal{Q}^{\prime\prime}_{k}$

13
$\mathcal{M}_{k+1}\leftarrow\big{(}\mathcal{M}_{k}\backslash\\{\mathcal{Q}_{k}\\}\big{)}\cup\big{(}\mathcal{Q}^{\prime}_{k}\cup\mathcal{Q}^{\prime\prime}_{k}\big{)}$

14 for
_$\mathcal{Q}\in\\{\mathcal{Q}^{\prime}_{k},\mathcal{Q}^{\prime\prime}_{k}\\}$_
do

15 $\alpha(\mathcal{Q}),\langle\rho^{\prime},\Pi^{\prime}\rangle\leftarrow$
Compute-UB($\mathcal{H}$, $\mathcal{Q}$, $l$)

16 if  _$\alpha(\mathcal{Q}) <\alpha_{\text{inc}}$_ then

17
$\langle\rho_{\text{inc}},\Pi_{\text{inc}}\rangle\leftarrow\langle\rho^{\prime},\Pi^{\prime}\rangle$

18 $\alpha_{\text{inc}}\leftarrow\alpha(\mathcal{Q})$

19 $\beta(\mathcal{Q})\leftarrow$ Compute-LB($\mathcal{H}$, $\mathcal{Q}$,
$l$)

20
$\alpha_{k}\leftarrow\min_{\mathcal{Q}\in\mathcal{M}_{k}}\alpha(\mathcal{Q})$

21 $\beta_{k}\leftarrow\min_{\mathcal{Q}\in\mathcal{M}_{k}}\beta(\mathcal{Q})$

22 $k\leftarrow k+1$

23

return $\langle\rho_{\text{inc}},\Pi_{\text{inc}}\rangle$

Algorithm 1 Branch-and-Bound

###  IV-B Procedural and Activity Planning

In this section, we define procedural planning and activity planning, and then
show that both of the planning problems can be reduced to an instance of
C-SSP. Let us begin with the definition of procedural planning.

######  Definition 1.

(Procedural Planning) Suppose estimates for the primary and $i$-th secondary
cost functions for every activity $E\in\mathcal{E}$ and
$i\in\\{1,\dots,N_{E}\\}$ are given, where the former and the latter are
denoted as $\bar{f}^{E}$ and $\bar{g}_{i}^{E}$, respectively. Then we define
planning for a procedural plan $\rho$ based on the given estimates as
procedural planning.

Similarly, we define activity planning as follows.