#  Aliphatics and Aromatics in the Universe: The Pre-JWST Era
DRAFT:

X.J. Yang11affiliation: Department of Physics, Xiangtan University, 411105
Xiangtan, Hunan Province, China<EMAIL_ADDRESS>22affiliation: Department
of Physics and Astronomy, University of Missouri, Columbia, MO 65211, USA;
<EMAIL_ADDRESS>and Aigen Li22affiliation: Department of Physics and
Astronomy, University of Missouri, Columbia, MO 65211, USA<EMAIL_ADDRESS>
###### Abstract

The so-called “unidentified infrared emission” (UIE) features at 3.3, 6.2,
7.7, 8.6, and 11.3$\,{\rm\mu m}$ ubiquitously seen in a wide variety of
astrophysical regions are generally attributed to polycyclic aromatic
hydrocarbon (PAH) molecules. Astronomical PAHs often have an aliphatic
component (e.g., aliphatic sidegroups like methyl –CH3 may be attached as
functional groups to PAHs) as revealed by the detection in many UIE sources of
the aliphatic C–H stretching feature at 3.4$\,{\rm\mu m}$. With its
unprecedented sensitivity, unprecedented spatial resolution and high spectral
resolution, the James Webb Space Telescope (JWST) holds great promise for
revolutionizing the studies of aliphatics and aromatics in the universe. To
facilitate analyzing JWST observations, we present a theoretical framework for
determining the aliphatic fractions ($\eta_{\rm ali}$) of PAHs, the fractions
of C atoms in aliphatic units, from the emission intensity ratios of the
3.4$\,{\rm\mu m}$ aliphatic C–H feature to the 3.3$\,{\rm\mu m}$ aromatic C–H
feature. To demonstrate the effectiveness of this framework, we compile the
3.3 and 3.4$\,{\rm\mu m}$ UIE data obtained in the pre-JWST era for an as
complete as possible sample, and then apply the framework to these pre-JWST
data. We derive a median aliphatic fraction of $\langle\eta_{\rm
ali}\rangle\approx 5.4\%$, and find that the aliphatic fractions are the
highest in protoplanetary nebulae illuminated by cool stars lacking
ultraviolet radiation. Nevertheless, the “hardness” of stellar photons is not
the only factor affecting the PAH aliphaticity, other factors such as the
starlight intensity may also play an important role.

dust, extinction — ISM: lines and bands — ISM: molecules

##  1 Introduction

Polycyclic aromatic hydrocarbon (PAH) molecules, composed of fused benzene
rings, have long been thought to be ubiquitous in the interstellar medium
(ISM), as evidenced by a series of emission bands observed at wavelengths 3.3,
6.2, 7.7, 8.6 and 11.3$\,{\rm\mu m}$, which are coincident with the
vibrational transitions of PAHs (Léger & Puget 1984, Allamandola et al. 1985).
These emission bands are often also known as the “unidentified infrared (IR)
emission” (UIE) bands. Of all interstellar carbon, $\sim\,$15% is thought to
be incorporated into PAHs (Li & Draine 2001). Their emission accounts for up
to 20% of the total IR power of the Milky Way and star-forming galaxies (see
Li 2020).

It has been generally held that astronomical PAHs are not really pure aromatic
compounds (see Kwok 2022). They may include ring defects, substituents,
partial dehydrogenation and sometimes superhydrogenation or deuteration (see
Yang et al. 2017a and references therein). Astronomical PAHs often also
include an aliphatic component (e.g., aliphatic sidegroups like methyl –CH3
may be attached as functional groups to PAHs), as revealed by the detection in
many UIE sources of a weak satellite emission feature at 3.4$\,{\rm\mu m}$
which always accompanies the 3.3$\,{\rm\mu m}$ emission feature (see Yang et
al. 2017b and references therein). While the 3.3$\,{\rm\mu m}$ feature arises
from aromatic C–H stretch, the 3.4$\,{\rm\mu m}$ feature is generally thought
to arise from aliphatic C–H stretch, although it could also be due to
anharmonicity (Barker et al. 1987) and superhydrogenation (Bernstein et al.
1996, Yang et al. 2020). In addition, some UIE sources also exhibit two
aliphatic C–H deformation bands at 6.85 and 7.25$\,{\rm\mu m}$ (see Yang et
al. 2016a and references therein). Typically, for those sources with prominent
6.85 and 7.25$\,{\rm\mu m}$ bands, the 3.4$\,{\rm\mu m}$ band is often
pronounced.

Let $\eta_{\rm ali}\equiv N_{\rm C,ali}/\left(N_{\rm C,aro}+N_{\rm
C,ali}\right)$ be the aliphatic fraction of PAHs, i.e., the ratio of the
number of C atoms in aliphatic units ($N_{\rm C,ali}$) to that in aromatic
rings ($N_{\rm C,aro}$) plus that in aliphatic units. In recent years, the PAH
aliphatic fraction has received increasing attention (e.g., see Kwok & Zhang
2011; Li & Draine 2012; Rouillé et al. 2012; Steglich et al. 2013; Pilleri et
al. 2015; Bernstein et al. 2017; Buragohain et al. 2015, 2016, 2020;
Allamandola et al. 2021; Yang et al. 2013, 2016a,b, 2017a,b). Despite the
widespread acceptance and extreme popularity of the PAH model, the exact
nature of the UIE carriers remains unknown and many candidate materials have
been proposed. All these hypotheses generally agree that the UIE bands arise
from some sort of aromatic hydrocarbon material. The major debate lies in the
exact structure of the UIE carriers: are they (i) free-flying, predominantly
aromatic gas-phase molecules like PAHs, or (ii) amorphous solids (either bulk
or nano-sized) with a mixed aromatic/aliphatic structure (e.g., see Sakata et
al. 1987, Papoular et al. 1993, Kwok & Zhang 2011, Jones et al. 2013)? One way
to address this is to examine the aliphatic fraction of the UIE carriers:
while PAHs, by definition, are predominantly aromatic, all other (proposed)
carriers are considerably aliphatic (see Yang et al. 2017b).

Prior to the launch of the James Webb Space Telescope (JWST), the
3.4$\,{\rm\mu m}$ feature, together with the 3.3$\,{\rm\mu m}$ feature, has
already been seen in a wide variety of Galactic and extragalactic regions,
including reflection nebulae, Hii regions, photodissociated regions (PDRs),
protoplanetary nebulae, planetary nebulae, protoplanetary disks around Herbig
Ae/Be stars and T Tauri stars, and external galaxies (see Yang et al. 2017b).
Undoubtedly, the high spectral resolution and unprecedented sensitivity of
JWST will bring the studies on aliphatics and aromatics to a new height.
Indeed, as illustrated in Figure 1, the 3.3 and (tentatively) 3.4$\,{\rm\mu
m}$ features were very recently seen in the mid-IR spectrum of SPT0418-47, a
galaxy at a redshift of $z\approx 4.22$, obtained with the Mid-IR Instrument
(MIRI) on board JWST (Spilker et al. 2023). The 3.3 and 3.4$\,{\rm\mu m}$
emission features have also been detected by JWST, through its Near Infrared
Camera (NIRCam), in dozens of moderately distant galaxies at redshifts $z$
$\sim$ 0.2–0.5 in the Great Observatories Origins Deep Survey–South (GOODS-S;
see Lyu et al. 2023). It is expected that JWST will accumulate a rich set of
such spectra for a wide range of astrophysical regions, particularly in the
distant universe.

We have initiated a program to explore the aliphatic and aromatic contents of
PAHs in the universe, both in the Milky Way and external galaxies, both near
and far. In this work, we focus on the 3.3 and 3.4$\,{\rm\mu m}$ emission
features detected in the pre-JWST era. This paper is organized as follows. In
§2 we present a theoretical framework for relating the aliphatic fractions of
PAHs to the emission intensity ratios of the 3.4$\,{\rm\mu m}$ feature to the
3.3$\,{\rm\mu m}$ feature. This theoretical framework will not only be used in
later sections but in the very near future also serve the JWST community as an
effective tool for quantitatively determining the aliphatic fractions of PAHs.
The 3.3 and 3.4$\,{\rm\mu m}$ emission features of various astrophysical
regions detected in the pre-JWST era will be summarized and analyzed in §3. We
will quantitatively determine the aliphatic fractions of PAHs and discuss the
results in §4. Finally, we summarize our major results in §5.

##  2 IR Emission Spectra of PAHs with Aliphatic Sidegroups: Theoretical
Framework

To facilitate the analysis of the 3.3 and 3.4$\,{\rm\mu m}$ emission detected
in the pre-JWST era, we first set up a theoretical framework to model the IR
emission of PAHs containing aliphatic sidegroups and relate the emission
intensities of the 3.3 and 3.4$\,{\rm\mu m}$ features to the PAH aliphatic
fraction. In the JWST era, this theoretical framework will also be used to
analyze JWST observations to quantitatively determine the aliphatic fractions
of PAHs.

Due to their small heat contents, PAHs are transiently heated in the ISM by
single stellar photons (see Li 2004). They will not attain an equilibrium
temperature, instead, they will experience temperature spikes and undergo
temperature fluctuations. For PAHs containing aliphatic contents (which we
call “aliphatic” PAHs), we consider PAHs attached with aliphatic sidegroups
like methylene and methyl. Following Draine & Li (2001), we will calculate the
temperature probability distribution functions and emission spectra of
aliphatic PAHs of $N_{\rm C,aro}$ aromatic C atoms, $N_{\rm H,aro}$ aromatic H
atoms, $N_{\rm C,ali}$ aliphatic C atoms, and $N_{\rm H,ali}$ aliphatic H
atoms. For such molecules, we approximate their absorption cross sections by
adding three Drude functions to that of PAHs of $N_{\rm C,aro}$ C atoms and
$N_{\rm H,aro}$ H atoms These Drude functions represent the 3.4$\,{\rm\mu m}$
aliphatic C–H stretch, and the 6.85 and 7.25$\,{\rm\mu m}$ aliphatic C–H
deformations. The absorption cross section of an aliphatic PAH molecule of
$N_{\rm C,aro}$ aromatic C atoms, $N_{\rm H,aro}$ aromatic H atoms, $N_{\rm
C,ali}$ aliphatic C atoms, and $N_{\rm H,ali}$ aliphatic H atoms becomes

$\displaystyle C_{\rm abs}(N_{\rm C},\lambda)$ $\displaystyle=$ $\displaystyle
C^{\scriptscriptstyle\rm PAH}_{\rm abs}(N_{\rm C,aro},N_{\rm H,aro},\lambda)$
(1) $\displaystyle+$ $\displaystyle N_{\rm
H,ali}\frac{2}{\pi}\frac{\gamma_{3.4}\lambda_{3.4}\sigma_{\rm
int,3.3}\left(A_{3.4}/A_{3.3}\right)}{(\lambda/\lambda_{3.4}-\lambda_{3.4}/\lambda)^{2}+\gamma_{3.4}^{2}}$
(2) $\displaystyle+$ $\displaystyle N_{\rm
H,ali}\frac{2}{\pi}\frac{\gamma_{6.85}\lambda_{6.85}\sigma_{\rm
int,6.2}\left(A_{6.85}/A_{6.2}\right)}{(\lambda/\lambda_{6.85}-\lambda_{6.85}/\lambda)^{2}+\gamma_{6.85}^{2}}$
(3) $\displaystyle+$ $\displaystyle N_{\rm
H,ali}\frac{2}{\pi}\frac{\gamma_{7.25}\lambda_{7.25}\sigma_{\rm
int,6.2}\left(A_{7.25}/A_{6.2}\right)}{(\lambda/\lambda_{7.25}-\lambda_{7.25}/\lambda)^{2}+\gamma_{7.25}^{2}}~{}~{},$
(4)

where $N_{\rm C}=N_{\rm C,aro}+N_{\rm C,ali}$ is the number of C atoms
contained in an aliphatic PAH molecule; $\lambda_{3.4}=3.4\,{\rm\mu m}$,
$\lambda_{6.85}=6.85\,{\rm\mu m}$, and $\lambda_{7.25}=7.25\,{\rm\mu m}$ are
respectively the central wavelengths of the 3.4, 6.85 and 7.25$\,{\rm\mu m}$
aliphatic C–H features; $\gamma_{3.4}\lambda_{3.4}$,
$\gamma_{6.85}\lambda_{6.85}$, and $\gamma_{7.25}\lambda_{7.25}$ are
respectively the FWHMs of the 3.4, 6.85 and 7.25$\,{\rm\mu m}$ features
($\gamma_{3.4}$, $\gamma_{6.85}$, and $\gamma_{7.25}$ are dimentionless
parameters; see Draine & Li 2007); $A_{3.3}$ and $A_{3.4}$ are the intensities
of the aromatic and aliphatic C–H stretches, respectively; $A_{6.2}$ and
$A_{7.7}$ are the intensities of the C–C stretches; $A_{6.85}$ and $A_{7.25}$
are the intensities of the aliphatic C–H deformation bands; and $\sigma_{{\rm
int},3.3}$ and $\sigma_{{\rm int},6.2}$ are respectively the integrated
strengths per (aromatic) C atom of the 3.3$\,{\rm\mu m}$ aromatic C–H stretch
and 6.2$\,{\rm\mu m}$ aromatic C–C stretch (see Draine & Li 2007). We take
$A_{3.4}/A_{3.3}=1.76$ for neutrals and $A_{3.4}/A_{3.3}=3.80$ for cations as
computed by Yang et al. (2013). We take the lower limits of
$A_{6.85}/A_{6.2}\approx 5.0$ and $A_{7.25}/A_{6.2}\approx 0.5$ for neutrals,
$A_{6.85}/A_{6.2}\approx 0.5$ and $A_{7.25}/A_{6.2}\approx 0.25$ for cations
as derived in Yang et al. (2016a). We note that, with $N_{\rm C,ali}\approx
3N_{\rm H,ali}$ (suitable for methyl sidegroups), the absorption cross
sections given in eqs.1–4 are the same as that of Yang et al. (2016a).

Let $dP$ be the probability that the temperature of the aliphatic PAH molecule
will be in $[T,T+dT]$. The emissivity (in unit of $\,{\rm erg}\,{\rm
s}^{-1}\,{\rm cm}^{-1}$) of this molecule becomes

$j_{\lambda}(N_{\rm C})=\int C_{\rm abs}(N_{\rm C},\lambda)\,4\pi
B_{\lambda}(T)\,\frac{dP}{dT}\,dT~{}.$ (5)

The 3–4$\,{\rm\mu m}$ interstellar UIE emitters are in the size range of
$N_{\rm C}$ $\sim\,$20–30 C atoms, as shown in Figures 6, 7 of Draine & Li
(2007). For illustrative purpose, we consider $N_{\rm C,aro}=24$ (like
coronene). For a coronene-like molecule, up to 12 methylene or methyl
sidegroups can be attached, we thus consider $N_{\rm C,ali}=0,1,2,...12$
aliphatic C atoms and $N_{\rm H,ali}=0,1,2,...36$ aliphatic H atoms. For all
molecules, $N_{\rm C,aro}=24$ is fixed. Yang et al. (2016a) have shown that
the model IR emission spectra (scaled by starlight intensity) are essentially
independent of the absolute values of the starlight intensities. Therefore, we
only consider $U=1$, with $U$ defined as

$U\equiv\frac{\int_{1\mu{\rm m}}^{912{\rm\,{\rm\AA}}}4\pi
J_{\star}(\lambda)\,d\lambda}{\int_{1\mu{\rm m}}^{912{\rm\,{\rm\AA}}}4\pi
J_{\rm ISRF}(\lambda)\,d\lambda}~{}~{},$ (6)

where $J_{\star}(\lambda)$ is the intensity of starlight, and $J_{\rm
ISRF}(\lambda)$ is the starlight intensity of the solar neighbourhood
interstellar radiation field (ISRF) of Mathis, Mezger & Panagia (1983; MMP83).
In addition to the MMP83 ISRF, we consider five types of radiation fields,
approximated by the stellar model atmospheric spectra of Kurucz (1979) of
effective temperatures of $T_{\rm eff}=3,500,6,000,10,000,22,000,30,000\,{\rm
K}$, like that of M2V stars, the Sun, A2V stars, B1.5V stars and B0V stars,
respectively. The reflection nebula NGC 2023 is illuminated by HD 37903, an
B1.5V star with $T_{\rm eff}=22,000\,{\rm K}$, while IRAS 03035+5819 is
illuminated by an B0V star of $T_{\rm eff}=30,000\,{\rm K}$.

We adopt the “thermal-discrete” method of Draine & Li (2001) to compute the
temperature probability distribution functions and the IR emission spectra of
both neutral and ionized aliphatic PAHs excited by starlight of different
spectra. In Figures 2 and 3 we show the model emission spectra in
3–15$\,{\rm\mu m}$ respectively for neutral and ionized aliphatic PAHs of
$N_{\rm H,ali}=0,2,6,10$ illuminated by stars of different $T_{\rm eff}$. It
is apparent that the 3.4 and 6.85$\,{\rm\mu m}$ aliphatic C–H features are
clearly visible and become stronger as $N_{\rm H,ali}$ increases. The
7.25$\,{\rm\mu m}$ aliphatic C–H feature, however, remains hardly noticeable
even for $N_{\rm H,ali}=10$. This is because the intrinsic strength of the
7.25$\,{\rm\mu m}$ feature ($A_{7.25}$) is much weaker compared to that of the
3.4 and 6.85$\,{\rm\mu m}$ features ($A_{3.4}$, $A_{6.85}$; see Yang et al.
2016a).

In the following, we will focus on the 3.3 and 3.4$\,{\rm\mu m}$ features.
Figure 4 highlights the spectra in the wavelength range of 3.2–3.6$\,{\rm\mu
m}$ for both neutral and ionized aliphatic PAHs with $N_{\rm H,ali}=0,2,6,10$.
The 3.4$\,{\rm\mu m}$ aliphatic C–H band becomes pronounced even at $N_{\rm
H,ali}=2$. At $N_{\rm H,ali}=10$, the 3.4$\,{\rm\mu m}$ feature becomes
comparable to or even stronger than the 3.3$\,{\rm\mu m}$ aromatic C–H
feature. For the same $N_{\rm H,ali}$, PAH cations emit less at 3.3 and
3.4$\,{\rm\mu m}$ than their neutral counterparts.

For a given $N_{\rm H,ali}$, we derive $\left(I_{3.4}/I_{3.3}\right)_{\rm
mod}$, the model emission intensity ratio of the 3.4$\,{\rm\mu m}$ band to the
3.3$\,{\rm\mu m}$ band, from

$\left(\frac{I_{3.4}}{I_{3.3}}\right)_{\rm mod}=\frac{\int_{3.4}\Delta
j_{\lambda}(N_{\rm C})\,d\lambda}{\int_{3.3}\Delta j_{\lambda}(N_{\rm
C})\,d\lambda}~{}~{},$ (7)

where $I_{3.4}$ and $I_{3.3}$ are respectively the calculated intensities of
the 3.4$\,{\rm\mu m}$ and 3.3$\,{\rm\mu m}$ emission features; and
$\int_{3.3}\Delta j_{\lambda}(N_{\rm C})\,d\lambda$ and $\int_{3.4}\Delta
j_{\lambda}(N_{\rm C})\,d\lambda$ are respectively the feature-integrated
excess emission of the 3.3 and 3.4$\,{\rm\mu m}$ features of aliphatic PAHs.

In Figures 5 and 6 we show the model intensity ratios
$\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ as a function of $N_{\rm
H,ali}/N_{\rm H,aro}$ for neutral and ionized PAHs, respectively. Basically,
the model band ratios $\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ are linearly
correlated with $N_{\rm H,ali}/N_{\rm H,aro}$ for both neutrals and cations.
The correlation slope, defined as $d\left(I_{3.4}/I_{3.3}\right)_{\rm
mod}/d\left(N_{\rm H,ali}/N_{\rm H,aro}\right)$, is a weak function of $T_{\rm
eff}$ and listed in Table 1. On average, $\langle
d\left(I_{3.4}/I_{3.3}\right)_{\rm mod}/d\left(N_{\rm H,ali}/N_{\rm
H,aro}\right)\rangle\approx 1.92\pm 0.09$ for neutrals and $\approx 4.13\pm
0.16$ for cations. Therefore, to first order, we obtain
$\left(I_{3.4}/I_{3.3}\right)_{\rm mod}\approx 1.92\times\left(N_{\rm
H,ali}/N_{\rm H,aro}\right)$ for neutrals and
$\left(I_{3.4}/I_{3.3}\right)_{\rm mod}\approx 4.13\times\left(N_{\rm
H,ali}/N_{\rm H,aro}\right)$ for cations. With the temperature dependence of
the correlation slope taken into account, the model band ratio
$\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ can be expressed as

$\left(\frac{I_{3.4}}{I_{3.3}}\right)_{\rm
mod}=\left(\frac{A_{3.4}}{A_{3.3}}\right)\times\left(\frac{N_{\rm
H,ali}}{N_{\rm H,aro}}\right)\times k(T_{\rm eff})~{}~{},$ (8)

where $k(T_{\rm eff})$, the correlation slope, is

$k(T_{\rm eff})\approx\begin{cases}1.20-0.122\times\left(T_{\rm
eff}/10,000\,{\rm K}\right)+0.022\times\left(T_{\rm eff}/10,000\,{\rm
K}\right)^{2}&{\rm for~{}neutrals}~{}~{},\\\ 1.18-0.113\times\left(T_{\rm
eff}/10,000\,{\rm K}\right)+0.023\times\left(T_{\rm eff}/10,000\,{\rm
K}\right)^{2}&{\rm for~{}cations}~{}~{}.\\\ \end{cases}$ (9)

The correlation slope $k(T_{\rm eff})$ somewhat decreases as $T_{\rm eff}$
increases. This is because, in regions illuminated by hot stars (of higher
$T_{\rm eff}$), the stellar photons are more energetic. Upon absorption of
such an energetic photon emitted from hotter stars, PAHs are excited to higher
temperatures and emit more effectively at shorter wavelengths (e.g.,
3.3$\,{\rm\mu m}$) than at longer wavelengths (e.g., 3.4$\,{\rm\mu m}$).
Therefore, for a given $N_{\rm H,ali}/N_{\rm H,aro}$, a smaller
$\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ is expected for regions illuminated
by stars of higher $T_{\rm eff}$.

To relate $N_{\rm C,ali}/N_{\rm C,aro}$ through $N_{\rm H,ali}/N_{\rm H,aro}$,
we assume that one aliphatic C atom corresponds to 2.5 aliphatic C–H bonds
(intermediate between methylene –CH2 and methyl –CH3) and one aromatic C atom
corresponds to 0.75 aromatic C–H bond (intermediate between benzene C6H6 and
coronene C24H12). Therefore, the ratio of the number of C atoms in aliphatic
units to that in aromatic rings is $N_{\rm C,ali}/N_{\rm
C,aro}\approx\left(0.75/2.5\right)\,\times\,N_{\rm H,ali}/N_{\rm H,aro}$. As
the 3.3 and 3.4$\,{\rm\mu m}$ C–H stretches are predominantly emitted by
neutral PAHs, we therefore recommend the following relation to estimate
$N_{\rm C,ali}/N_{\rm C,aro}$ from the observed band ratios
$\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$:

$\frac{N_{\rm C,ali}}{N_{\rm
C,aro}}\approx\frac{1}{5.87}\left(\frac{I_{3.4}}{I_{3.3}}\right)_{\rm
obs}\times\left\\{1.20-0.122\times\left(T_{\rm eff}/10,000\,{\rm
K}\right)+0.022\times\left(T_{\rm eff}/10,000\,{\rm
K}\right)^{2}\right\\}^{-1}~{}~{}.$ (10)

In case there is no information on $T_{\rm eff}$ (e.g., the MMP83 ISRF), we
recommend

$\frac{N_{\rm C,ali}}{N_{\rm
C,aro}}\approx\frac{1}{6.40}\left(\frac{I_{3.4}}{I_{3.3}}\right)_{\rm
obs}~{}~{}.$ (11)

The aliphatic fraction of PAHs is determined from

$\eta_{\rm ali}=\left(1+N_{\rm C,aro}/N_{\rm C,ali}\right)^{-1}~{}~{}.$ (12)

There is no need to compute the temperature probability distribution functions
and the IR emission spectra of aliphatic PAHs as long as one is only
interested in the aliphatic fraction of the UIE carrier.

##  3 Aliphatic and Aromatic Observations in the Pre-JWST Era

A wealth of observational spectra for the aliphatic and aromatic C–H stretches
are available in archive or literature. This allows an in-depth study of the
aliphatics and aromatics in the universe. We compile the aliphatic and
aromatic C–H emission data, as complete as possible, from observations made
with space-borne satellites such as the Infrared Space Observatory (ISO) and
AKARI, airborne telescopes such as the Kuiper Airborne Observatory (KAO), and
ground-based telescopes such as the Infrared Telescope Facilities (IRTF) and
the United Kingdom Infrared Telescope (UKIRT).

To this end, we find 28 sources which show both the 3.3 and 3.4$\,{\rm\mu m}$
features. These sources include Galactic PDRs, protoplanetary nebulae (PPNe),
planetary nebulae (PNe), reflection nebulae (RNe), young stellar objects
(YSOs), and HII regions, as well as external galaxies.

For each source, we fit the observed spectrum in terms of two or more Drude
profiles combined with an underlying linear continuum:

$F_{\lambda}=a_{0}+a_{1}\lambda+\sum_{j}\frac{P_{j}\,\times\,\left(2\gamma_{j}/\pi\right)}{\left(\lambda-\lambda_{{\rm
o},j}^{2}/\lambda\right)^{2}+\gamma_{j}^{2}},$ (13)

where $a_{0}$ and $a_{1}$ are the coefficients of the linear continuum;
$\lambda_{{\rm o},j}$ and $\gamma_{j}$ are the central wavelength and width of
the $j$-th Drude profile; $P_{j}$, the power emitted from $j$-th Drude profile
(in unit of $\,{\rm erg}\,{\rm s}^{-1}\,{\rm cm}^{-2}$), is obtained by
integrating the emission feature over wavelength:

$P_{j}=\int_{\lambda_{j}}\Delta F_{\lambda}\,d\lambda~{}~{}.$ (14)

For the Drude profiles, the 3.3 and 3.4$\,{\rm\mu m}$ features are always
included for consideration. In some objects (e.g., IRAS 21282+5050), one or
more additional weak features at 3.43, 3.47, 3.51, and 3.56$\,{\rm\mu m}$ are
also present and each of these features is also approximated as a Drude
profile. We sum up the power emitted from all these sub-features and attribute
them to the aliphatic C–H stretches. Therefore, for the ratio of the power
emitted from the aliphatic C–H stretches to that from the aromatic C–H
stretches, we take $\left(I_{3.4}/I_{3.3}\right)_{\rm
obs}=\left(P_{3.4}+P_{3.43}+P_{3.47}+P_{3.51}+P_{3.56}\right)/P_{3.3}$
provided that these subfeatures are detected. If only the 3.3 and
3.4$\,{\rm\mu m}$ features show up, we take $\left(I_{3.4}/I_{3.3}\right)_{\rm
obs}=P_{3.4}/P_{3.3}$. We note that in the literature the band ratios
$\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ have been reported for some sources.
We prefer to derive by ourselves because in the literature there is a certain
arbitrarity in defining the underlying continuum for the features and the
strengths of the features were calculated in different ways. When taking data
from different publications, these differences may actually play a role. We
therefore decide to derive $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ in a
coherent way for all sources.

For each source, we follow the above procedure to fit the observed spectrum to
derive $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$. We then derive the aliphatic
fraction $\eta_{\rm ali}$ from $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ (see
eqs. 10–12). The spectral fits are illustrated in Figures 7–11 and the derived
aliphatic fractions $\eta_{\rm ali}$ are tabulated in Table 2.

##  4 Results and Discussion

Figure 7 shows the aliphatic and aromatic C–H stretches seen in emission in
PDRs excited by B0V or earlier-type stars with $T_{\rm eff}\gtrsim
30,000\,{\rm K}$. The aliphatic C–H stretches are relatively weak and the
aliphatic fractions of PAHs are all smaller than 3%. This is understandable
since PDRs are rich in energetic photons so that the aliphatic sidegroups
attached to PAHs could easily be stripped off.

Figure 8 shows the near-IR spectra of four PNe. NGC 7027, excited by an B2.5V
star of $T_{\rm eff}\approx 20,000\,{\rm K}$, exhibits the strongest aliphatic
C–H stretches among these four PNe. As the illuminating star becomes hotter,
$\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ decreases, so does the PAH aliphatic
fraction. With $T_{\rm eff}\approx 37,000\,{\rm K}$, IC 418 does not show any
noticeable aliphatic C–H emission. In contrast, excited by an B0V star of
$T_{\rm eff}\approx 30,000\,{\rm K}$, BD+303639 shows a broad, shallow feature
around 3.4–3.5$\,{\rm\mu m}$. By attributing this feature to aliphatic C–H
stretches, we estimate an aliphatic fraction of $\sim\,$5.3% for PAHs in
BD+303639.

The aliphatic and aromatic C–H stretches of two reflection nebulae are shown
in Figure 9. IRAS 03035+5819 exhibits a series of weak aliphatic C–H
stretching features. NGC 1333 and IRAS 03035+5819 are both excited by an B0V
star of $T_{\rm eff}\approx 30,000\,{\rm K}$ and their PAH aliphatic fractions
are comparable to that of BD+303639 (PN), but appreciably higher than that of
S106 (PDR). Both BD+303639 and S106 are illuminated by stars with $T_{\rm
eff}\approx 30,000\,{\rm K}$, just like NGC 1333 and IRAS 03035+5819.

Figure 10 shows the near-IR spectra of four YSOs. All four objects show
several sub-features at $\sim\,$3.4–3.6$\,{\rm\mu m}$ attributed to aliphatic
C–H stretches. The PAH aliphatic fraction does not show any strong dependence
on $T_{\rm eff}$.

We show in Figure 11 the aliphatic and aromatic C–H stretching features of
four PPNe. Except the Red Rectangle illuminated by HD 44179 of $T_{\rm
eff}\approx 7,750\,{\rm K}$, PAHs in these PPNe are rich in aliphatic contents
and their aliphatic fractions are high, with $\eta_{\rm ali}\approx 25\%$ for
IRAS 04296+3429, $\eta_{\rm ali}\approx 35\%$ for IRAS 05341+0852, and
$\eta_{\rm ali}\approx 8.6\%$ for CRL 2688. All these three aliphatic-rich
PPNe are excited by cool stars which lack UV photons ($T_{\rm eff}\approx
6,500\,{\rm K}$ for IRAS 04296+3429 and IRAS 03541+0852, and $T_{\rm
eff}\approx 7,000\,{\rm K}$ for CRL 2688). This suggests that, in UV-poor
regions, once attained, PAHs are capable of maintaining their aliphatic
sidegroups without being stripped off. Nevertheless, the Red Rectangle, also
illuminated by a cool star with little UV radiation, shows very weak emission
at 3.4$\,{\rm\mu m}$ and the PAH aliphatic fraction is only $\sim\,$0.3%. This
indicates that, in addition to the “hardness” of the exciting stellar photons,
some other factors (e.g., the starlight intensity) are also at play in
affecting the PAH aliphatic fractions.

Among our 24 Galactic sources, six objects lack information about their
illuminating stars. Their near-IR spectra are shown in Figure 12 and the
intensity of the aliphatic C–H stretching feature (relative to the aromatic
C–H feature) varies substantially, from essentially no 3.4$\,{\rm\mu m}$
emission in IRAS 16362-4845 to highly aliphatic in IRAS 12063-6259 ($\eta_{\rm
ali}\approx 20.4\%$) and in IRAS 06572-0742 ($\eta_{\rm ali}\approx 6.0\%$).
IRAS 16362-4845 exhibits a smooth, flat continuum at $\sim\,$3.4–3.6$\,{\rm\mu
m}$. The PAH aliphatic fractions of IRAS 09296+1159 ($\eta_{\rm ali}\approx
3.5\%$), IRAS 17199-3446 ($\eta_{\rm ali}\approx 4.8\%$), and IRAS 19097+0847
($\eta_{\rm ali}\approx 4.6\%$) are moderate.

Figure 13 shows the aliphatic and aromatic C–H stretches of four nearby
galaxies. They all show considerable emission at 3.4$\,{\rm\mu m}$ and their
PAH aliphatic fractions all exceed 7%. The Large Magellanic Cloud (LMC) and
NGC 253, a dusty starburst galaxy, also show a weak sub-feature at $\sim\,$3.5
and 3.6$\,{\rm\mu m}$, respectively. It is not clear if (and how) the galaxy
metallicity affects the PAH aliphatic fraction. It has long been known that,
since the ISO time, the PAH abundance decreases as the metallicity drops (see
Li 2020 and references therein). It is unclear if the presence and the
intensity of the 3.4$\,{\rm\mu m}$ feature (relative to the 3.3$\,{\rm\mu m}$
feature) are related to the metallicity. In this respect, JWST, with its
unprecedented sensitivity and spatial resolution, will allow an in-depth
study. In principle, in low-metallicity regions, PAHs are less likely to
attain aliphatic sidegroups because of the low C/H ratio (and therefore low
–CH3 abundance) and more likely to attain extra H atoms to be
superhydrogenated. As the intrinsic strength of the 3.4$\,{\rm\mu m}$
aliphatic C–H stretch of superhydrogenated PAHs is close to that of PAHs with
aliphatic sidegroups (see Yang et al. 2020), observationally, it is difficult
to distinguish whether the 3.4$\,{\rm\mu m}$ feature arises from
superhydrogenated PAHs or from PAHs with aliphatic sidegroups. Also, it is not
clear if (and how) the 3.4$\,{\rm\mu m}$ feature is affected by the star
formation rate. We await JWST for quantitative investigations.

In Figure 14 we show the PAH aliphatic fraction distribution of our sample of
28 sources. It can be seen that the majority (24/28) of these sources has
$\eta_{\rm ali}<10\%$. The median of the PAH aliphatic fraction is
$\langle\eta_{\rm ali}\rangle\approx 5.4\%$. Two PPNe—IRAS 04296+3429
($\eta_{\rm ali}\approx 24.8\%$) IRAS 05341+0852 ($\eta_{\rm ali}\approx
34.9\%$)—are unusually rich in aliphatics. Another object—IRAS 12063-6259
($\eta_{\rm ali}\approx 20.4\%$) of which the exact nature is unknown—also has
a large aliphatic content.

We explore whether (and how) the PAH aliphatic fraction varies with
astrophysical environments (e.g., hardness of the exciting starlight photons).
As shown in Figure 15, $\eta_{\rm ali}$ appears higher in regions illuminated
by stars with lower $T_{\rm eff}$. Indeed, as discussed above, it is generally
true that in UV-poor PPNe the 3.4$\,{\rm\mu m}$ emission feature (relative to
the 3.3$\,{\rm\mu m}$ feature) is much stronger than that of PNe, RNe, and
PDRs (see Figure 11). Nevertheless, the Red Rectangle, a PPN illuminated by HD
44179 of $T_{\rm eff}\approx 7,750\,{\rm K}$, has a rather low $\eta_{\rm
ali}$, much lower than that of PDR and RNs illuminated by stars of much higher
$T_{\rm eff}$. This implies that, not only the hardness but also the intensity
of the starlight may affect the accumulation and survival of aliphatic
sidegroups attached to PAHs. This can be studied in more detail by future
JWST/NIRSpec observations of spatially-resolved PAH spectra. Previously, the
spatial variations of $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ with the
exciting UV starlight intensities have been investigated (e.g., see Joblin et
al. 1996, Sloan et al. 1997, Goto et al. 2003). Again, with its unprecedented
sensitivity and spatial resolution, JWST will allow us to explore the spatial
variations of the PAH aliphatic fractions and their relations to the physical
and chemical conditions in an unprecedented depth.

While the 3.4$\,{\rm\mu m}$ aliphatic C–H emission is widely seen in various
astrophysical environments, prior to JWST, the detection of the 6.85 and
7.25$\,{\rm\mu m}$ aliphatic C–H deformation bands is rare and has so far been
reported only in a couple dozen objects, mostly based on the observations made
with the Infrared Spectrograph (IRS) on board the Spitzer Space Telescope and
the Shorter Wavelength Spectrometer (SWS) on board ISO (see Sloan et al. 2014,
Yang et al. 2016a). This will change with the launch of JWST: due to its
unprecedented sensitivity, the MIRI spectrometer is well suited for detecting
the 6.85 and 7.25$\,{\rm\mu m}$ bands (while the NIRSpec spectrograph is ideal
for detecting the 3.4$\,{\rm\mu m}$ band). A combination of the 3.4, 6.85 and
7.25$\,{\rm\mu m}$ bands would allow us to probe the aliphatic contents of
large PAHs (e.g., see Li & Draine 2012). It is interesting to note that, in
some planetary nebulae, where the 3.4$\,{\rm\mu m}$ emission is observed, an
5.25$\,{\rm\mu m}$ band is often also seen. The 5.25$\,{\rm\mu m}$ band is
thought to be coming from large compact PAHs (see Boersma et al. 2009). Larger
compact PAHs with aliphatic side groups should be more eligible to survive in
environments illuminated by cool stars. It would be interesting to consider,
in the JWST era, large aliphatic PAHs in a theoretical framework similar to
that presented in §2 and see if any correlations exist between these bands.

Finally, we note that the 3.4$\,{\rm\mu m}$ band could also arise from
superhydrogenated PAHs whose edges contain excess H atoms (Bernstein et al.
1996, Sandford et al. 2013, Yang et al. 2020). The addition of excess H atoms
to PAHs converts the flat sp2 aromatic bonding of their asscoiated C atoms
into tetrahedral sp3 aliphatic bonding, resulting in the creation of aliphatic
C–H stretching bands. Compared with methylated PAHs in which one aliphatic C
atom corresponds to three aliphatic C–H bonds, for superhydrogenated PAHs, one
“superhydrogenated” C atom corresponds to two aliphatic C–H bonds. For
superhydrogenated PAHs, the ratio of the intensity of the 3.4$\,{\rm\mu m}$
aliphatic C–H stretch to that of the 3.3$\,{\rm\mu m}$ aromatic C–H stretch
$\langle A_{3.4}/A_{3.3}\rangle\approx 1.98$ (Yang et al. 2020) is similar to
that of methylated PAHs ($\langle A_{3.4}/A_{3.3}\rangle\approx 1.76$; Yang et
al. 2013, 2017b). Therefore, the aliphatic fraction as defined in eq.12 would
be higher by a factor of
$\approx\left(3/2\right)\times\left(1.76/1.98\right)\approx 1.33$, if the
observed 3.4$\,{\rm\mu m}$ emission is attributed to superhydrogenated PAHs.

##  5 Summary

To facilitate a quantitative analysis of the aliphatic and aromatic contents
of PAHs in the JWST era, we have proposed a theoretical framework for
determining the aliphatic fractions ($\eta_{\rm ali}$) of PAHs and have
applied the framework to pre-JWST UIE data. Our major results are as follows:

  1. 1.

An analytical formula for relating the PAH aliphatic fraction ($\eta_{\rm
ali}$) to the emission intensity ratio of the 3.4$\,{\rm\mu m}$ feature to the
3.3$\,{\rm\mu m}$ feature ($I_{3.4}/I_{3.3}$) is presented. This relation is
somewhat dependent on the “hardness” of the exciting stellar photons measured
by the stellar effective temperature ($T_{\rm eff}$).

  2. 2.

To demonstrate the effectiveness of this framework (of deriving $\eta_{\rm
ali}$ from $I_{3.4}/I_{3.3}$), we have compiled the 3.3 and 3.4$\,{\rm\mu m}$
UIE data obtained in the pre-JWST era for an as complete as possible sample of
28 Galactic and extragalactic sources. We have then applied the $\eta_{\rm
ali}$–$I_{3.4}/I_{3.3}$ relation to these pre-JWST data.

  3. 3.

We have derived the PAH aliphatic fraction $\eta_{\rm ali}$ for each source
from the observed band ratio $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ and
found a median aliphatic fraction of $\langle\eta_{\rm ali}\rangle\approx
5.4\%$. Generally, the aliphatic fractions are the highest in protoplanetary
nebulae illuminated by cool stars lacking UV radiation. However, the hardness
of stellar photons is not the only factor affecting the PAH aliphaticity,
other factors such as the starlight intensity may also play an important role.

We thank B.T. Draine, R. Glaser, A.N. Witt and the anonymous referee for
valuable suggestions. We thank J.S. Spilker for providing us the JWST data of
SPT0418-47. XJY is supported in part by NSFC 12122302 and 11873041. AL is
supported in part by NASA grants 80NSSC19K0572 and 80NSSC19K0701.

## References

  * (1) Allamandola, L.J., Tielens, A.G.G.M., & Barker, J.R. 1985, ApJ, 290, L25
  * (2) Allamandola, L. J., Boersma, C., Lee, T. J., et al. 2021, ApJL, 917, L35
  * (3) Barker, J. R., Allamandola, L. J., & Tielens, A.G.G.M. 1987, ApJ, 315, L61
  * (4) Bernstein, L. S., Shroll, R. M., Lynch, D. K., & Clark, F. O. 2017, ApJ, 836, 229
  * (5) Bernstein, M.P., Sandford, S.A., & Allamandola, L.J. 1996, ApJ, 472, L127
  * (6) Boersma, C., Mattioda, A. L., Bauschlicher, C. W., et al. 2009, ApJ, 690, 1208
  * (7) Buragohain, M., Pathak, A., Sarre, P., Onaka, T., & Sakon, I. 2015, MNRAS, 454, 193
  * (8) Buragohain, M., Pathak, A., Sarre, P., Onaka, T., & Sakon, I. 2016, Planet. Space Sci., 133, 97
  * (9) Buragohain, M., Pathak, A., Sakon, I., & Onaka, T. 2020, ApJ, 892, 11
  * (10) Draine, B.T., & Li, A. 2001, ApJ, 551, 807
  * (11) Draine, B.T., & Li, A. 2007, ApJ, 657, 810
  * (12) Geballe, T.R., Lacy, J.H., Persson, S.E., McGregor, P. J., & Soifer, B.T. 1985, ApJ, 292, 500
  * (13) Geballe, T. R. & van der Veen, W. E. C. J. 1990, A&A, 235, L9
  * (14) Geballe, T. R., Tielens, A. G. G. M., Kwok, S., & Hrivnak, B. J. 1992, ApJL, 387, L89
  * (15) Goto, M., Gaessler, W., Hayano, Y., et al. 2003, ApJ, 589, 419
  * (16) Joblin, C., Tielens, A.G.G.M., Allamandola, L.J., & Geballe, T.R. 1996, ApJ, 458, 610
  * (17) Jones, A. P., Fanciullo, L., Köhler, M., et al. 2013, A&A, 558, A62
  * (18) Jourdain de Muizon, M., Geballe, T.R., d’Hendecourt, L.B., & Baas, F. 1986, ApJ, 306, L105
  * (19) Jourdain de Muizon, M., d’Hendecourt, L. B., & Geballe, T. R. 1990, A&A,, 227, 526
  * (20) Kondo, T., Kaneda, H., Oyabu, S., et al. 2012, ApJ, 751, L18
  * (21) Kurucz, R.L. 1979, ApJS, 40, 1
  * (22) Kwok, S. 2022, Ap&SS, 367, 16
  * (23) Kwok, S., & Zhang, Y. 2011, Nature, 479, 80
  * (24) Léger, A., & Puget, J.L. 1984, A&A, 137, L5
  * (25) Li, A., 2004, in Astrophysics of Dust, Witt, A.N., Clayton, G.C., & Draine, B.T. (eds.), ASP Conf. Ser., 309, 417
  * (26) Li, A. 2020, Nature Astronomy, 4, 339
  * (27) Li, A., & Draine, B.T. 2001, ApJ, 554, 778
  * (28) Li, A., & Draine, B.T. 2012, ApJ, 760, L35
  * (29) Lyu, J.W., Yang, X.J., Li, A., et al. 2023, in preparation
  * (30) Mathis, J.S., Mezger, P.G., & Panagia, N. 1983, A&A, 128, 212
  * (31) Mori, T. I., Onaka, T., Sakon, I., et al. 2014, ApJ, 784, 53
  * (32) Onaka, T., Nakamura, T., Sakon, I., et al. 2018, ApJ, 853, 31
  * (33) Pilleri, P., Joblin, C., Boulanger, F., et al. 2015, A&A, 577, A16
  * (34) Papoular, R., Breton, J., Gensterblum, G., Nenner, I., Papoular, R. J., & Pireaux, J.-J. 1993, A&A, 270, L5
  * (35) Rouillé, G., Steglich, M., Carpentier, Y., et al. 2012, ApJ, 752, 25.
  * (36) Sakata, A., Wada, S., Onaka, T., & Tokunaga, A.T. 1987, ApJ, 320. L63
  * (37) Sandford, S.A., Bernstein, M. P., & Materese, C.K. 2013, ApJS, 205, 8
  * (38) Sloan, G.C., Bregman, J.D., Geballe, T.R., Allamandola, L.J., & Woodward, C.E. 1997, ApJ, 474, 735
  * (39) Sloan, G. C., Jura, M., Duley, W. W., et al. 2007, ApJ, 664, 1144
  * (40) Sloan, G. C., Lagadec, E., Zijlstra, A. A., et al. 2014, ApJ, 791, 28
  * (41) Spilker, J. S., Phadke, K. A., Aravena, M., et al. 2023, Nature, 618, 708
  * (42) Steglich, M., Jäger, C., Huisken, F., et al. 2013, ApJS, 208, 26
  * (43) Yamagishi, M., Kaneda, H., Ishihara, D., et al. 2012, A&A, 541, A10
  * (44) Yang, X. J., Glaser, R., Li, A., & Zhong, J. X. 2013, ApJ, 776, 110
  * (45) Yang, X. J., Glaser, R., Li, A., & Zhong, J. X. 2016a, MNRAS, 462, 1551
  * (46) Yang, X. J., Li, A., Glaser, R., & Zhong, J. X. 2016b, ApJ, 825, 22
  * (47) Yang, X. J., Li, A., Glaser, R., & Zhong, J. X. 2017a, ApJ, 837, 171
  * (48) Yang, X. J., Glaser, R., Li, A., & Zhong, J. X. 2017b, New Astron. Rev., 77, 1
  * (49) Yang, X. J., Li, A., & Glaser, R. 2020, ApJS, 247, 1

Figure 1:  The aromatic and aliphatic C–H stretches respectively at
$\sim\,$3.3 and 3.4$\,{\rm\mu m}$ from SPT0418-47, a galaxy at $z\approx
4.22$, detected by JWST/MIRI (Spilker et al. 2023). The MIRI spectrum has been
smoothed to a resolution of $R\approx 600$. Also shown is the JWST/NIRCam
spectrum of GOODS-S 9883, a moderately distant galaxy at $z$ $\sim$ 0.36 (Lyu
et al. 2023). To facilitate comparison, the JWST/NIRCam spectrum has been
multiplied by a factor of three.  Figure 2:  Model IR emission spectra of
neutral aliphatic PAHs of $N_{\rm H,ali}=0,2,6,10$ aliphatic H atoms and
$N_{\rm C,aro}=24$ aromatic C atoms illuminated by an M2V star of $T_{\rm
eff}=3,500\,{\rm K}$ (orange lines), a solar-type star of $T_{\rm
eff}=6,000\,{\rm K}$ (purple lines), an A2V star of $T_{\rm eff}=10,000\,{\rm
K}$ (mangeta lines), an B1.5V star of $T_{\rm eff}=22,000\,{\rm K}$ (blue
lines), an B0V star of $T_{\rm eff}=30,000\,{\rm K}$ (cyan lines), and the
MMP83 ISRF (black lines). The starlight intensities are all set to be $U=1$.
The 3.4 and 6.85$\,{\rm\mu m}$ aliphatic C–H features are clearly seen in the
spectra of aliphatic PAHs with $N_{\rm H,ali}=2,6,10$, while the
7.25$\,{\rm\mu m}$ aliphatic C–H feature is less prominent. For clarity, their
spectra are vertically shifted.  Figure 3:  Same as Figure 2 but for aliphatic
PAH cations.  Figure 4:  Same as Figures 2,3 but highlighting the aromatic and
aliphatic C–H bands in the 3.2–3.6$\,{\rm\mu m}$ wavelength range.  Figure 5:
Model-calculated intensity ratios $\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ as
a function of $N_{\rm H,ali}/N_{\rm H,aro}$ for neutral aliphatic PAHs of
$N_{\rm C,aro}=24$. These molecules are illuminated by an M2V star of $T_{\rm
eff}=3,500\,{\rm K}$ (orange lines), a solar-type star of $T_{\rm
eff}=6,000\,{\rm K}$ (purple lines), an A2V star of $T_{\rm eff}=10,000\,{\rm
K}$ (magenta lines), an B1.5V star of $T_{\rm eff}=22,000\,{\rm K}$ (blue
lines), an B0V star of $T_{\rm eff}=30,000\,{\rm K}$ (cyan lines), and the
MMP83 ISRF (black lines). The starlight intensities are all set to be $U=1$.
Figure 6:  Same as Figure 5 but for aliphatic PAH cations.

Figure 7:  Aliphatic and aromatic C–H stretching features of four PDRs (IRAS
18416-0420, Jourdain de Muizon et al. 1990; Orion Bar, Sloan et al. 1997; IRAS
19442+2427, Jourdain de Muizon et al. 1990; S106, Geballe et al. 1985). The
observed spectra are shown as black diamonds. The fitted spectra (solid red
lines) are a combination of two or more Drude profiles and a linear,
underlying continuum.

Figure 8:  Same as Figure 7 but for four planetary nebulae (IC 418, Geballe et
al. 1985; BD+303639, Geballe et al. 1985; IRAS 21282+5050, Jourdain de Muizon
et al. 1986; NGC 7027, Geballe et al. 1985).

Figure 9:  Same as Figure 7 but for reflection nebulae NGC 1333 (Joblin et al.
1996) and IRAS 03035+5819 (Jourdain de Muizon et al. 1986).

Figure 10:  Same as Figure 7 but for four YSOs (IRAS 20293+3952, IRAS
20319+3958, IRAS 19213+1723, and IRAS 03260+3111; Jourdain de Muizon et al.
1990).

Figure 11:  Same as Figure 7 but for four PPNe: the Red Rectangle illuminated
by HD 44179 (Geballe et al. 1985); CRL 2688 (Geballe et al. 1992); IRAS
04296+3429 (Geballe et al. 1992); and IRAS 05341+0852 (Geballe et al. 1990).

Figure 12:  Same as Figure 7 but for six sources of which the effective
temperatures of the illuminating stars are unknown: IRAS 16362-4845 (Jourdain
de Muizon et al. 1990); IRAS 06572-0742 (Jourdain de Muizon et al. 1990); IRAS
09296+1159 (Geballe et al. 1990); IRAS 12063-6259 (Jourdain de Muizon et al.
1990); IRAS 17199-3446 (Jourdain de Muizon et al. 1990); and IRAS 19097+0847
(Jourdain de Muizon et al. 1990).

Figure 13:  Same as Figure 7 but for four external galaxies: M82 (Yamagishi et
al. 2012); NGC 253 (Yamagishi et al. 2012); NGC 2782 (Onaka et al. 2018); and
LMC (Mori et al. 2012).

Figure 14:  Histogram of the aliphatic fractions of PAHs for 28 UIE sources.
The median aliphatic fraction is $\langle\eta_{\rm ali}\rangle\approx 5.4\%$.
Figure 15:  PAH aliphatic fraction ($\eta_{\rm ali}$) vs. stellar effective
temperature ($T_{\rm eff}$). PPN: protoplanetary nebula; PN: planetary nebula;
RN: reflection nebula; MC: molecular cloud; PDR: photodissociated region; YSO:
young stellar object.

Table 1: Slopes for the Correlation between the Model Band Ratio $\left(I_{3.4}/I_{3.3}\right)_{\rm mod}$ versus $N_{\rm C,ali}/N_{\rm C,aro}$ for Neutrals and Cations as a Function of Stellar Effective Temperatures.  $T_{\rm eff}$ (K) | Neutral PAHs | Cationic PAHs
---|---|---
3500 | 2.06 | 4.38
6000 | 1.98 | 4.20
10000 | 1.93 | 4.14
22000 | 1.84 | 3.97
30000 | 1.81 | 3.96
Average | 1.92 | 4.13
Stdev | 0.09 | 0.16

Table 2: Observed Band Ratios $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ of Astronomical Sources Exhibiting Both the 3.3 and 3.4$\,{\rm\mu m}$ Emission, and PAH Aliphatic Fractions $\eta_{\rm ali}$ Derived from $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ Based on Eqs. 10–12.  Object | Type | $T_{\rm eff}$ | Correlation | $\left(I_{3.4}/I_{3.3}\right)_{\rm obs}$ | $\eta_{\rm ali}$
---|---|---|---|---|---
|  | (K) | Slope |  | (%)
IRAS 18416-0420 | PDR | 40000 | 1.87 | 0.15 | 2.33
Orion Bar | PDR | 39000 | 1.86 | 0.11 | 1.74
IRAS 19442+2427 | PDR | 36000 | 1.84 | 0.17 | 2.67
S106 | PDR | 30000 | 1.81 | 0.08 | 1.28
IC418 | PN | 36700 | 1.84 | 0.01 | 0.08
BD+303639 | PN | 30000 | 1.81 | 0.34 | 5.30
IRAS 21282+5050 | PN | 28000 | 1.81 | 0.35 | 5.42
NGC7027 | PN | 20000 | 1.84 | 0.53 | 7.94
IRAS 03035+5819 | RN | 30000 | 1.81 | 0.43 | 6.67
NGC 1333 | RN | 30000 | 1.81 | 0.36 | 5.58
IRAS 20293+3952 | YSO | 20500 | 1.83 | 0.49 | 7.47
IRAS 20319+3958 | YSO | 20500 | 1.83 | 0.44 | 6.78
IRAS 19213+1723 | YSO | 15000 | 1.87 | 0.26 | 3.93
IRAS 03260+3111 | YSO | 13000 | 1.90 | 0.34 | 5.15
HD44179 | PPN | 7750 | 1.97 | 0.02 | 0.32
CRL2688 | PPN | 7000 | 1.98 | 0.62 | 8.56
IRAS 04296+3429 | PPN | 6500 | 1.99 | 2.18 | 24.79
IRAS 05341+0852 | PPN | 6500 | 1.99 | 3.56 | 34.94
IRAS 16362-4845 | MC | 5700 | 2.00 | 0.54 | 7.54
IRAS 06572-0742 | … | 18000 | 1.85 | 0.39 | 6.00
IRAS 09296+1159 | … | … | 1.92 | 0.24 | 3.54
IRAS 12063-6259 | … | … | 1.92 | 1.64 | 20.37
IRAS 17199-3446 | … | … | 1.92 | 0.32 | 4.82
IRAS 19097+0847 | … | … | 1.92 | 0.31 | 4.59
M82 | starburst galaxy | … | 1.92 | 0.58 | 8.35
NGC253 | starburst galaxy | … | 1.92 | 0.52 | 7.48
NGC2782 | spiral galaxy | … | 1.92 | 0.81 | 11.26
LMC | irregular galaxy | … | 1.92 | 0.72 | 10.06


# Improving Reliable Navigation under Uncertainty via Predictions Informed by
Non-Local Information

Raihan Islam Arnob and Gregory J. Stein R. Arnob and G. Stein are with the
Department of Computer Science, George Mason University, USA, {rarnob,
<EMAIL_ADDRESS>
###### Abstract

We improve reliable, long-horizon, goal-directed navigation in partially-
mapped environments by using non-locally available information to predict the
goodness of temporally-extended actions that enter unseen space. Making
predictions about where to navigate in general requires non-local information:
any observations the robot has seen so far may provide information about the
goodness of a particular direction of travel. Building on recent work in
learning-augmented model-based planning under uncertainty, we present an
approach that can both rely on non-local information to make predictions (via
a graph neural network) and is reliable by design: it will always reach its
goal, even when learning does not provide accurate predictions. We conduct
experiments in three simulated environments in which non-local information is
needed to perform well. In our large scale university building environment,
generated from real-world floorplans to the scale, we demonstrate a 9.3%
reduction in cost-to-go compared to a non-learned baseline and a 14.9%
reduction compared to a learning-informed planner that can only use local
information to inform its predictions.

##  I Introduction

We focus on the task of goal-directed navigation in a partially-mapped
environment, in which a robot is expected to reach an unseen goal in minimum
expected time. Often modeled as a Partially Observable Markov Decision Process
(POMDP) [1], long-horizon navigation under uncertainty is computationally
demanding, and so many strategies turn to learning to make predictions about
unseen space and thereby inform good behavior. To perform well, a robot must
understand how parts of the environment the robot cannot currently see (i.e.,
non-locally available information) inform where it should go next, a
challenging problem for many existing planning strategies that rely on
learning.

Consider the simple scenario from our _J-Intersection_ environment shown in
Fig. 1: information at the center of the map (the color of that region)
informs whether the robot should travel left or right; optimal behavior
involves following the hallway whose color matches that of the center of the
map. As this color is not visible from the intersection, a robot must remember
what the space looked like around the corner to perform well and learn how
that information relates to its decision. More generally, many real-world
environments require such understanding, a particularly challenging task for
building-scale environments. In this work, we aim to allow a robot to retain
non-local knowledge and learn to use it to make predictions that inform where
it should travel next.

Recently, learning-driven approaches—including many model-free approaches
trained via deep reinforcement learning [2, 3]—have demonstrated the capacity
to perform well in this domain. However, in the absence of an explicit map for
the robot to use to keep track of where it has yet to go, many such approaches
are unreliable, lacking guarantees that they will reach the goal [4].
Moreover, these approaches struggle to reason far enough into the future to
understand the impact of their actions and thus perform poorly and can be
brittle and unreliable for long-horizon planning.

The recent Learning over Subgoals planning approach (LSP) [5] introduces a
high-level abstraction for planning in a partial map that allows for both
state-of-the-art performance and reliability-by-design. In LSP, actions
correspond to exploration of a particular region of unseen space. Learning
(via a fully-connected neural network) is used to estimate the goodness of
exploratory actions, including the likelihood an exploration will reveal the
unseen goal. These predictions inform model-based planning and are thus used
to compute expected cost. LSP overcomes two problems: (1) its state and action
abstraction allows for learning-informed reasoning far into the future and (2)
it is guaranteed to reach the goal if there exists a viable path. However, LSP
is limited: its ability to make predictions about unseen space only makes use
of locally observable information, limiting its performance.

Figure 1:  Overview: non-local information is often essential for good
navigation in a partial map. Our LSP-GNN approach uses a graph neural network
to make predictions about unseen space via both local and non-local
information and integrates these into the Learning over Subgoals model-based
planning abstraction [5, 6] to improve reliable navigation.

In this paper, we extend the Learning over Subgoals Planner (LSP-Local),
replacing its learning backend with a Graph Neural Network (LSP-GNN),
affording reliable learning-informed planning capable of using both local and
non-local information to make predictions about unseen space and thus improve
performance in complex navigation scenarios in building-scale environments.
Using a graph representation of the partial map—constructed via a map skeleton
[7] so as to preserve topological structure—we demonstrate that our GNN allows
for accurate predictions of unseen space using non-local information.
Additionally, we demonstrate that our LSP-GNN planner improves performance
over the original LSP-Local planner while retaining guarantees on reliability:
i.e., the robot always reaches the goal. We show the effectiveness of our
approach in our simulated _J-Intersection_ , _Parallel Hallway_ , and
_University Building_ environments, in the latter yielding improvements of
9.3% and 14.9% (respectively) over non-learned and learned baselines.

##  II Related Works

Planning under Uncertainty POMDPs [1, 8, 9, 10] have been used to represent
navigation and exploration tasks under uncertainty, yet direct solution of the
model implicit in the POMDP is often computationally infeasible. To mitigate
this limitation, many approaches to planning rely on learning to inform
behavior [4, 11, 12], yet only plan a few time steps into the future and so
are not well-suited to long-horizon planning problems. Some reinforcement
learning approaches that deal with partially observed environments [13, 14,
15, 16, 17, 18] are also limited to fairly small-scale environments. The
MERLIN agent [2] uses a differentiable neural computer to recall information
over much longer time horizons than is typically possible for end-to-end-
trained model-free deep reinforcement learning systems. However, the
reinforcement learning approaches [2, 19, 20] can be difficult to train and
lacks plan completeness, making it somewhat brittle in practice. Our proposed
work improves long-horizon planning under uncertainty learning the relational
properties from the non-local observation of the environment with the
guarantee of completeness.

Graph Neural Networks and Planning Battaglia et al. [21] present a survey of
GNN approaches, demonstrating how GNNs can be used for relational reasoning
and exhibit combinatorial generalization, opening numerous opportunities for
learning over structured and relational data. Zhou et al. [22] show how GNNs
have been used in the field of modeling physics systems, learning molecular
fingerprints, predicting protein interface, classifying diseases, and many
others. GNNs are fast to evaluate on sparse graphs and have shown capacity to
generalize effectively in multiple domains [21, 23, 24]. Moreover, GNNs have
recently been used to accelerate task and motion planning [25, 26] and to
inform other problems of interest to robotics: joint mapping and navigation
[27], object search in previously-seen environments [28], and modeling
physical interaction [29]. In particular, Chen et al. [30] propose a framework
that uses GNN in conjunction with deep reinforcement learning to address the
problem of autonomous exploration under localization uncertainty for a mobile
robot with 3D range sensing.

##  III Problem Formulation

Our robot is tasked to reach an unseen goal in a partially-mapped environment
in minimum expected cost (distance). The synthetic robot is equipped with a
semantically-aware planar laser scanner, which it can use to both localize and
update its partial semantic-occupancy-grid map of its local surroundings,
limited by range and obstacle occlusion. As the robot navigates the partially-
mapped environment, it updates its belief state $b_{t}$ to include newly-
revealed space and its semantic class.

Formally, we represent this problem as a Partially Observable Markov Decision
Process [1, 8] (POMDP). The expected cost $Q$ under this model can be written
via a belief space variant of the Bellman equation [31]:

$\split
Q(b_{t},a_{t})=\sum_{b_{t+1}}P(b_{t+1}|b_{t},a_{t})\Big{[}R(b_{t+1},b_{t},a_{t})\\\
+\min_{a_{t+1}\in\mathcal{A}(b_{t}+1)}Q(b_{t+1},a_{t+1})\Big{]},$ (1)

where $R(b_{t+1},b_{t},a_{t})$ is the cost of reaching belief state $b_{t+1}$
from $b_{t}$ by taking action $a_{t}$ and $P(b_{t+1}|b_{t},a_{t})$ is the
transition probability.

Figure 2:  Our robot’s actions correspond to boundaries between free and
unseen space. The robot can leave observed space through either boundary: via
subgoal $s_{1}$ or $s_{2}$. Upon selecting action $a_{2}$, the robot reaches
the goal with probability $P_{S}$ and incurs an expected cost $R_{S}$, or is
turned back (probability $1-P_{S}$), accumulates cost $R_{E}$ and selects
another action.

##  IV Preliminaries: Model-based Planning under Uncertainty via Learning over
Subgoals

As Eq. eq:POMDP cannot be solved directly, our robot instead relies on the
recent Learning over Subgoals Planning (LSP) approach [5] to determine the
robot’s behavior. LSP introduces a model-based planning abstraction that
alleviates the computational requirements of POMDP planning, affording both
reliability and good performance informed by predictions about unseen space
from learning.

For LSP planning, actions available to the robot correspond to navigation to
_subgoals_ —each associated with a boundary between free and unknown space—and
then exploration beyond in an effort to reach the unseen goal. Consistent with
this action abstraction, planning under the LSP model is done over an abstract
belief state: a tuple $b_{t}=\\{m_{t},q_{t}\\}$, where $m_{t}$ is the current
map of the environment, and $q_{t}$ is the robot pose. Each high-level action
$a_{t}\in\mathcal{A}(\\{m_{t},q_{t}\\})$ has a binary outcome: with
probability $P_{S}(a_{t})$, the robot _succeeds_ in reaching the goal or (with
the inverse probability $1-P_{S}(a_{t})$) fails to reach the goal. Upon
selecting an action $a_{t}$, the robot must first move through known space to
the boundary, accumulating a cost $D(m_{t},q_{t},a_{t})$. If the robot
succeeds in reaching the goal, it accumulates a _success cost_ $R_{S}(a_{t})$,
the expected cost for the robot to reach the goal, and no further navigation
is necessary. Otherwise, the robot accumulates an _exploration cost_
$R_{E}(a_{t})$, the expected cost of exploring the region beyond the subgoal
of interest and needing to turn back, and must subsequently choose another
action $a_{t+1}\in
A_{t+1}\equiv\mathcal{A}(\\{m_{t},q(a_{t})\\})\setminus\\{a_{t}\\}$.

Under this LSP planning model, the expected cost of taking an action $a_{t}$
from belief state $b_{t}=\\{m_{t},q_{t}\\}$ is

$\split
Q(&\\{m_{t},q_{t}\\},a_{t}\in\mathcal{A})=D(m_{t},q_{t},a_{t})+P_{S}(a_{t})R_{S}(a_{t})\\\
+(1-P_{S}(a_{t}))\left[R_{E}(a_{t})+\min_{a_{t+1}}Q(\\{m_{t},q(a_{t})\\},a_{t+1})\right]$
(2)

While the known-space distance $D(m_{t},q_{t},a_{t})$ can be calculated
directly from the observed map using A${}^{\\!*}$ or RRT∗, the _subgoal
properties_ $P_{S}(a_{t})$, $R_{S}(a_{t})$, and $R_{E}(a_{t})$ for each
subgoal are estimated via learning from information collected during
navigation.111The terms $P_{S}$, $R_{S}$, and $R_{E}$ are implicitly functions
of the belief, but shown here only as functions of the chosen action for
notational simplicity.

In the LSP approach [5] and in other LSP-derived planners so far [32, 6],
learning has relied only on _local_ information—e.g., semantic information,
images, or local structure. However, locally-accessible information alone
cannot inform effective predictions about unseen space in general; information
revealed elsewhere in the environment may determine where a robot should
navigate next. As such, the learned models upon which existing LSP approaches
rely perform poorly in even simple environments where non-locally available
information is required. We show one example of this limitation in Sec. V and
discuss how we use Graph Neural Networks to overcome it in Sec. VI.

##  V Motivating Example: A Memory Test for Navigation

Figure 3:  Low cost navigation in our J-Intersection environment requires non-
local information. When the goal is either on left or right from the
intersection, we need the non-local information from the start position to
decide correctly at the intersection. Choosing always left or right or even
choosing one color over another will not reliably succeed.

Fig. 3 shows an example scenario motivating the necessity of using non-locally
observable information to make good predictions about the environment while
trying to reach the goal under uncertainty. Our _J-Intersection_ environment
has either a red or blue square region inside of it and around the corner
occluded from that square region far away at the intersection that colored
region leads to the goal (bottom).

Maps in this environment are structured so that the color of the hallway the
robot should follow matches the color of the center region of the map. We
randomize the color of the center map region and mirror the environment
randomly so that no systematic policy (e.g., _follow the blue hallway_ or
_turn left at the fork_) will efficiently reach the goal.

Since the LSP approach is limited to making predictions for the subgoal using
only locally observable information, it cannot to learn the (simple) defining
structural characteristic of the environment: if the inside square region is
red then the path to the goal is red and if the inside square is blue then
blue is the path to the goal. Instead, we will augment the LSP approach to
rely on a _graph neural network_ [21] to estimate the subgoal properties,
allowing it to use both local and non-local information to make predictions
about the goodness of actions that enter unseen space and thus perform well
across a variety of complex environments.

##  VI Approach: Making Predictions about Unseen Space using Non-Local
Information

We aim to improve navigation under uncertainty by estimating task-relevant
properties of unseen space via non-locally observable information. Consistent
with our discussion in Sec. IV for modelling uncertainty via POMDP, our robot
relies on the LSP model-based planning abstraction of Stein et al. [5] for
high-level navigation through partially-revealed environments, for which
learning is used to estimate the _subgoal properties_ ($P_{S}$, $R_{S}$, and
$R_{E}$) used to determine expected cost via Eq. eq:lsp-planning.

We will use a Graph Neural Network (GNN) to overcome the limitations of making
predictions using only local information (as discussed in Sec. V) and thus
improve both predictive power and planning performance. A graph-based
representation of the environment captures both topological structure and also
allows information to be retained and communicated over long distances [33,
34]. A GNN is a deep-learning approach that allows predictions over graph
data; to plan, we require estimates of the properties ($P_{S}$, $R_{S}$, and
$R_{E}$) for each subgoal node and so our graph neural network will output
estimates of these properties for each. In the following sections, we detail
how we convert the environment into a graph representation (Sec. VI-A), how
training data is generated (Sec. VI-C), and the network and training
parameters (Sec. VI-B).

###  VI-A Computing a High-level Graph Representation

While the occupancy grid of the observed region can be used as a graph
representation of the environment, it has too many nodes for learning to be
practical. Instead, we want to generate a simplified (few-node) graph of the
environment that preserves high-level topological structure, so that nodes
exist at (i) intersections, (ii) dead-ends, and (iii) subgoals.

Graph Generation: We create this graph via a process shown in Fig. 4. We first
generate a skeleton [7, 35] over a modified version of the map in which
unknown space is marked as free yet where frontiers are masked as obstacles
except for a single point near their center. We eliminate the skeleton outside
known space and add nodes at all intersections and skeleton endpoints and
finally use the skeleton to define the edges between them. We additionally add
nodes corresponding to each subgoal and connect each new node to its nearest
structural neighbor in the graph generated from the skeletonization process.
Finally, we add a _goal node_ at the location of the goal that has an edge
connection to every other node; this _global node_ [21] allows for the
propagation of information across the entire environment.

Figure 4: Graph representations of the environment for our graph neural net
are computed from the partial map. We use an image skeleton [7] to generate a
graph from the partial occupancy grid. See Sec. VI-A for details.

Neural Network Input Features: Structure alone is often insufficient to inform
good predictions of unseen space. As such, we seek to not only compute a
topometric graph of the environment, but also associate semantic information
with each node. Each graph node is given a local observation—a _node feature_
—from which the subgoal properties ($P_{S}$, $R_{S}$, and $R_{E}$ in Eq.
eq:lsp-planning) will be estimated via the graph neural network. Node features
are 6-element vectors: (i) a 3-element one-hot semantic class (or color) at
the location of the node, (ii) the number of neighbors of that node, (iii) a
binary indicator of whether or not the node is a subgoal, and (iv) a binary
indictor of whether the node is the goal node. We additionally include a
single edge feature, associated with each edge in the graph: the geodesic
distance between the nodes it connects. Owing to the presence of a goal node
connected to every other node, the edge features provides each node its
distance to the goal. To ensure a fair comparison with the LSP-Local planner,
our learned baseline that does not consider edge information, the node
features for LSP-Local are augmented to include the geodesic distance to the
goal. Conditioned upon, correctly building the map the input is enough to
ensure safety during navigation. Safety during navigation with the
aforementioned inputs is ensured conditioned upon correctly building the maps.

###  VI-B Graph Neural Network Structure and Training

We use the PyTorch [36] neural network framework and Torch Geometric [37] to
define and train our graph neural network. The neural network begins with 3
locally-fully-connected layers, which are fully-connected layers that
processes the features for each node in isolation, without considering the
edges or passing information to neighbors; all three have hidden layer
dimension of 8. Next, the network has 4 GATv2Conv [38] layers, each with
hidden layer dimension of 8. Finally, a locally-fully-connected layer takes in
the 8-dimensional node features as input and produces a three dimensional
output: a logit corresponding to $P_{S}$ and the two cost terms $R_{S}$ and
$R_{E}$. For the LSP-Local learned-baseline planner, we replace the GATv2Conv
graph neural network layers with locally-fully-connected layers, eliminating
sharing of information between nodes and thus its ability to use non-locally-
available information to make predictions about unseen space.

Loss Function: Our loss function matches the original LSP approach of Stein et
al. [5] adapted for our graph input data. For each subgoal node, we accumulate
error according to a weighted cross-entropy loss (a classification objective)
for $P_{S}$ and an L1-loss (a regression objective) for $R_{S}$ and $R_{E}$.
Since only the properties of the subgoal nodes are needed, we mask the loss
for non-subgoal nodes and only consider the subgoal nodes’ contribution to the
loss.

Training Parameters: We train a separate network (with identical parameters)
for each environment. Training proceeds for 50k steps. The learning rate
begins at $10^{-3}$ and decays by a factor of 0.6 every 10k steps.

###  VI-C Generating Training Data

To train our graph neural network, we require training data collected via
offline navigation trials from which we can learn to estimate the subgoal
properties ($P_{S}$, $R_{S}$, and $R_{E}$) for each subgoal node in the graph.
During an offline training phase, we conduct trials in which the robot
navigates from start to goal and generates labeled data at each time step.
Training data consists of environment graphs $G$—with input features
consistent with our discussion in Sec. VI-A—and labels associated with each
subgoal node.

To compute the labels for our training data, we use the underlying known map
to determine whether or not a path to the goal exists through a subgoal. Using
this information, we record a label for each subgoal that corresponds to a
sample of the probability of success $P_{S}$ and from which we can learn to
estimate $P_{S}$ using cross-entropy loss. Labels for the other subgoal
properties are computed similarly: labels for the success cost $R_{S}$
correspond to the travel distance through unknown space to reach the goal, for
when the goal can be reached, and the exploration cost $R_{E}$ is a heuristic
cost corresponding to how long it will take a robot to realize a region is a
dead end, approximated as the round-trip travel time to reach the farthest
reachable point in unseen space beyond the chosen frontier. This data and
collection process mirrors that of LSP [5]; readers are referred to their
paper for additional details.

We repeat the data collection process for each step over hundreds of trials
for each training environment. So as to generate more diverse data, we switch
between the known-space planner and an optimistic (non-learned) planner to
guide navigation during data generation. The details of each environment can
be found in Sec. VII.

##  VII Experimental Results

We conduct simulated experiments in three environments—our _J-Intersection_
(Sec. VII-A), _Parallel Hallway_ (Sec. VII-B), and _University Building_ (Sec.
VII-C)—in which a robot must navigate to a point goal in unseen space. For
each trial, we evaluate performance of 4 planners:

Optimistically assumes the unseen space to be free and plans via grid-based
A${}^{\\!*}$ search.

Plans via Eq. eq:lsp-planning, estimating subgoal properties via only local
features, as in [5].

Plans via Eq. eq:lsp-planning, yet uses our graph neural network learning
backend to estimate subgoal properties using both local and non-local
features.

The robot uses the fully-known map to navigate; a lower bound on cost. For
each planner, we compute average navigation cost across many (at least 100)
random maps from each environment.

TABLE I: Avg. Cost over 100 Trials in the J-Intersection Environment Planner | Avg. Cost (grid cell units)
---|---
Non-Learned Baseline | $303.03$
LSP-Local (learned baseline) | $323.46$
LSP-GNN (ours) | 204.85
Fully-Known Planner | $204.85$

###  VII-A J-Intersection Environment

Figure 5: Planned trajectories of the bench-marked planner approaches.
J-intersection environment where the goal is on the right. The left column
shows the optimal trajectory (planned using the underlying known map). The
middle column shows the same trajectory of both the non-learned baseline and
LSP-Local where they make a systematic choice. The right column shows the
trajectory planned by LSP-GNN that is similar to the optimal one.

We first show results in the J-Intersection environment, described in Sec. V
to motivate the importance of non-local information for good performance for
navigation under uncertainty. In this environment, the robot must choose where
to travel at a fork in the road, yet non-locally observable information is
needed to reliably make the correct choice—a blue-colored starting region
indicates that the goal can be reached by turning towards the blue hallway at
the intersection, and the same for the red-colored regions. We randomly mirror
the environment so that the robot cannot learn a systematic policy that
quickly reaches the goal without understanding.

We conduct 100 trials for each planner in this environment to evaluate their
performance and show the average cost planning strategy in Table I. Across all
trials, our proposed LSP-GNN planner _always_ correctly decides where to go at
the intersection and achieves near-perfect performance. By contrast, both the
LSP-Local and Non-Learned Baseline planners lack the knowledge to determine
which is the correct way to go and perform poorly overall, resulting in poor
performance in roughly half of the trials. We highlight two example trials in
Fig. 5. We do not report the prediction accuracy empirically, because the
prediction accuracy does not reflect the actual gain in performance for our
work.

###  VII-B The Parallel Hallway Environment

Figure 6: Two sample maps from our procedurally-generated Parallel Hallway
environment. A robot is tasked to navigate from start to goal in these maps
without having access to the underlying map. The left image shows a sample map
where the red rooms connect the hallways and the right image shows where the
blue rooms connect the hallways.

Our _Parallel Hallway_ environment (Fig. 6) consists of parallel hallways
connected by rooms. We procedurally generate maps in this environment with
three hallways and two room types: (i) _dead-end_ rooms and (ii) _passage_
rooms that provide connections between neighboring parallel hallways. Only one
passage room exists between a pair of hallways, and so the robot must identify
this room if it is to travel to another hallway. Environments are generated
such that the dead-end rooms all have the same color (red or blue) distinct
from the color of the passage rooms, which are thus blue or red, respectively.
We are making the environment such that the relational information, such as
recognizing that if a room with certain color is explored as a dead-end, then
the other colored room serves as a pass-through room can be learned. If the
colors were entirely random, there would be no way to make predictions about
the unseen space. Both room types contain obstructions and are otherwise
identical, so that it is not possible to tell whether or not a room will
connect to a parallel hallway without trial-and-error or by utilizing semantic
color information from elsewhere in the map. Rooms are placed far enough apart
that the robot cannot determine from the local observations if a room will
lead to the next hallway or will be a dead end. The start and goal locations
are placed in separate hallways, so as to force the robot to understand its
surroundings to reach the goal quickly. Thus, to navigate well in this
challenging procedurally-generated environment, the robot must first explore,
trying nearby rooms to determine which color belongs to which room type, and
then retain this information to inform navigation through the rest of the
environment.

TABLE II: Avg. Cost over 500 Trials in the Parallel Hallway Environment Planner | Avg. Cost (grid cell units)
---|---
Non-Learned Baseline | $205.93$
LSP-Local (learned baseline) | $236.47$
LSP-GNN (ours) | 141.37
Fully-Known Planner | $108.37$
Figure 7: Parallel Hallway Results: average cost over 500 trials decreases
using LSP-GNN. Our learning-informed planner outperforms both the non-learned
baseline (left) and the LSP-Local (right) planners.

We train the simulated robot on data from 2,000 distinct procedurally
generated maps and evaluate in a separate set of 500 distinct procedurally
generated maps. We show the average performance of each planning strategy in
Table II and include scatterplots of the relative performance of different
planners for each trial in Fig. 7. The robot planning with our LSP-GNN
approach is able to utilize non-local local information to improve its
predictions about how best to reach the goal, achieving a 31.3% improvement in
average cost versus the optimistic Non-Learned Baseline planner and a 40.2%
improvement over the LSP-Local planner. In addition, our approach is
_reliable_ : owing to the LSP planning abstraction, our robot is able to
successfully reach the goal in all maps.

We highlight one trial in Fig. 8, in which the robot is tasked to navigate
from the top hallway to the bottom hallway, which contains the goal. After a
brief period of trial-and-error exploration in the first (top) hallway, the
robot discovers the passage to the neighboring hall and uses the knowledge of
the semantic color to quickly locate the passage to the next hallway and reach
the goal. By contrast, the Non-Learned Baseline optimistically assumes unseen
space to be free and enters every room in the direction of the goal. The LSP-
Local planner makes predictions using only local information and, unable to
use important navigation-relevant information, cannot determine how to reach
the goal; its poor predictions result in frequent turning-back behavior as it
seeks alternate routes to the goal, reducing performance.

Figure 8: Navigation trajectories of the tested planners in one of the testing
maps from the parallel hallway environment. Using non-local information
enables LSP-GNN to perform better than both the learned (LSP-Local) and non-
learned (Dijkstra) baselines.

###  VII-C University Building Floorplans

Figure 9: Three large-scale training maps from our university floorplan
environment, each generated from a real-world floor plan. The inset in the
center map shows an instance of a graph (as used to define our graph neural
network) for a partial map during a navigation trial. Plot axes are in units
of meters.

Finally, we evaluate in large-scale maps generated from real-world floorplans
of buildings from the Massachusetts Institute of Technology, including
buildings of over 100 meters in extent along either side; see Fig. 9 for
examples. We generate data from 2,000 trials across 56 training floorplans and
evaluate in 250 trials from 9 held-out test floorplans, each augmented by
procedurally generated clutter to add furniture-like obstacles to rooms. In
addition to occupancy information, _rooms_ in the map have a distinct semantic
class from _hallways_ (and other large or accessible spaces); this semantic
information is provided as input node features to the neural networks to
inform their predictions.

We show the average performance of each planning strategy in Table III and
include scatterplots of the relative performance of different planners for
each trial in Fig. 10. The robot planning with our LSP-GNN approach achieves
improvements in average cost of 9.3% versus the optimistic Non-Learned
Baseline planner and of 14.9% improvement over the LSP-Local Learned Baseline
planner. Unlike the LSP-Local planner, which does not have enough information
to make good predictions about unseen space, our LSP-GNN approach can make use
of non-local information to inform its predictions and thus performs well
despite the complexity inherent in these large-scale testing environments.

TABLE III: Avg. Cost over 250 Trials in the University Building Floorplans Planner | Avg. Cost (meter)
---|---
Non-Learned Baseline | $44.98$
LSP-Local (learned baseline) | $47.93$
LSP-GNN (ours) | 40.80
Fully-Known Planner | $31.77$
Figure 10: University Building Floorplan Results: average cost (meter) over
250 trials decreases using LSP-GNN. Our learning-informed planner outperforms
both the non-learned baseline (left) and the LSP-Local (right) planners.
Figure 11: Navigation trajectories of all tested planners in one of the large-
scale testing maps from the university building environment. LSP-GNN performs
better than both the learned (LSP-Local) and non-learned (Dijkstra) baselines
deviating very few times from the hallway to reach faraway goal.  Figure 12:
Two comparison between the navigational trajectories of our LSP-GNN against
LSP-Local. LSP-GNN exhibits the capacity to recover quickly than LSP-Local
when both planner cannot immediately find the correct path.

Fig. 11 shows a typical navigation example in one of our test environments. In
this scenario, the shortest possible trajectory involves knowing to follow
hallways until near to the goal. Both learned planners generally exhibit
hallway-following behavior—often useful in building-like environments such as
these—and improve upon the non-learned (optimistic) baseline. However, our
LSP-GNN planner, able to make use of non-local information, can more reliably
determine which is the more productive route and more quickly reaches the
faraway goal. Fig. 12 shows two additional examples that highlight the
improvements of our LSP-GNN planner made possible by non-locally-available
information. In Fig. 12A, we highlight an example in which both learned
planners cannot immediately find the correct path, yet LSP-GNN is able to
improve its predictions about where is most likely to lead to the unseen goal
and recover more quickly than does LSP-Local. Fig. 12B shows a more extreme
example, in which the LSP-Local planner fails to quickly turn back to seek a
promising alternate route immediately identified by LSP-GNN.

##  VIII Conclusion and Future Work

We present a reliable model-based planning approach that uses a graph neural
network to estimate the goodness of goal-directed high-level actions from both
local and non-local information, improving navigation under uncertainty. Our
planning approach takes advantage of non-local information to make informed
decisions about how to more quickly reach the goal. We rely on a graph neural
network (GNN) to make these predictions. The GNN consumes a graph
representation of the partial map and makes predictions about the goodness of
potential routes to the goal. We demonstrate improved performance on two
simulated environments in which non-local information is required to plan
well, demonstrating the efficacy of our approach.

In future work, we envision passing more complex sensory input to the robot,
allowing it to estimate the goodness of its actions using information
collected from image sensors or semantically-segmented images.

## References

  * [1] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra, “Planning and acting in partially observable stochastic domains,” _Artif. Intell._ , vol. 101, no. 1–2, p. 99–134, 1998.
  * [2] G. Wayne, C. Hung, D. Amos, M. Mirza, A. Ahuja, A. Grabska-Barwinska, J. W. Rae, P. Mirowski, J. Z. Leibo, A. Santoro, M. Gemici, M. Reynolds, T. Harley, J. Abramson, S. Mohamed, D. J. Rezende, D. Saxton, A. Cain, C. Hillier, D. Silver, K. Kavukcuoglu, M. M. Botvinick, D. Hassabis, and T. P. Lillicrap, “Unsupervised predictive memory in a goal-directed agent,” _CoRR_ , vol. abs/1803.10760, 2018.
  * [3] P. Mirowski, M. K. Grimes, M. Malinowski, K. M. Hermann, K. Anderson, D. Teplyashin, K. Simonyan, K. Kavukcuoglu, A. Zisserman, and R. Hadsell, “Learning to navigate in cities without a map,” _CoRR_ , vol. abs/1804.00168, 2018.
  * [4] M. Pfeiffer, M. Schaeuble, J. I. Nieto, R. Siegwart, and C. Cadena, “From perception to decision: A data-driven approach to end-to-end motion planning for autonomous ground robots,” _CoRR_ , vol. abs/1609.07910, 2016\.
  * [5] G. J. Stein, C. Bradley, and N. Roy, “Learning over subgoals for efficient navigation of structured, unknown environments,” in _Proceedings of The 2nd Conference on Robot Learning_ , ser. Proceedings of Machine Learning Research, A. Billard, A. Dragan, J. Peters, and J. Morimoto, Eds., vol. 87. PMLR, 29–31 Oct 2018, pp. 213–222.
  * [6] C. Bradley, A. Pacheck, G. J. Stein, S. Castro, H. Kress-Gazit, and N. Roy, “Learning and planning for temporally extended tasks in unknown environments,” in _2021 IEEE International Conference on Robotics and Automation (ICRA)_ , 2021, pp. 4830–4836.
  * [7] T. Y. Zhang and C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” _Commun. ACM_ , vol. 27, no. 3, p. 236–239, 1984.
  * [8] M. L. Littman, A. R. Cassandra, and L. P. Kaelbling, _Learning Policies for Partially Observable Environments: Scaling Up_. Morgan Kaufmann Publishers Inc., 1997.
  * [9] S. Thrun, W. Burgard, and D. Fox, _Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)_. The MIT Press, 2005.
  * [10] G. Parascandolo, L. Buesing, J. Merel, L. Hasenclever, J. Aslanides, J. B. Hamrick, N. Heess, A. Neitz, and T. Weber, “Divide-and-conquer monte carlo tree search for goal-directed planning,” 2020.
  * [11] C. Richter, J. Ware, and N. Roy, “High-speed autonomous navigation of unknown environments using learned probabilities of collision,” in _2014 IEEE International Conference on Robotics and Automation (ICRA)_ , 2014, pp. 6114–6121.
  * [12] S. Ross, N. Melik-Barkhudarov, K. S. Shankar, A. Wendel, D. Dey, J. A. Bagnell, and M. Hebert, “Learning monocular reactive UAV control in cluttered natural environments,” _CoRR_ , vol. abs/1211.1690, 2012.
  * [13] Y. Duan, J. Schulman, X. Chen, P. L. Bartlett, I. Sutskever, and P. Abbeel, “RL2: Fast reinforcement learning via slow reinforcement learning,” _CoRR_ , vol. abs/1611.02779, 2016.
  * [14] Y. Yang, J. P. Inala, O. Bastani, Y. Pu, A. Solar-Lezama, and M. C. Rinard, “Program synthesis guided reinforcement learning,” _CoRR_ , vol. abs/2102.11137, 2021.
  * [15] S. Gupta, J. Davidson, S. Levine, R. Sukthankar, and J. Malik, “Cognitive mapping and planning for visual navigation,” _CoRR_ , vol. abs/1702.03920, 2017.
  * [16] J. Zhang, J. T. Springenberg, J. Boedecker, and W. Burgard, “Deep reinforcement learning with successor features for navigation across similar environments,” _CoRR_ , vol. abs/1612.05533, 2016.
  * [17] L. Tai, G. Paolo, and M. Liu, “Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation,” _CoRR_ , vol. abs/1703.00420, 2017.
  * [18] P. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. J. Ballard, A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell, “Learning to navigate in complex environments,” _CoRR_ , vol. abs/1611.03673, 2016.
  * [19] J. Kober and J. Peters, _Reinforcement Learning in Robotics: A Survey_. Cham: Springer International Publishing, 2014, pp. 9–67.
  * [20] P. Henderson, R. Islam, P. Bachman, J. Pineau, D. Precup, and D. Meger, “Deep reinforcement learning that matters,” _CoRR_ , vol. abs/1709.06560, 2017\.
  * [21] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. F. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, Ç. Gülçehre, H. F. Song, A. J. Ballard, J. Gilmer, G. E. Dahl, A. Vaswani, K. R. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu, “Relational inductive biases, deep learning, and graph networks,” _CoRR_ , vol. abs/1806.01261, 2018.
  * [22] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, and M. Sun, “Graph neural networks: A review of methods and applications,” _CoRR_ , vol. abs/1812.08434, 2018.
  * [23] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 28, 2015.
  * [24] F. Monti, D. Boscaini, J. Masci, E. Rodola, J. Svoboda, and M. M. Bronstein, “Geometric deep learning on graphs and manifolds using mixture model CNNs,” in _Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 5115–5124.
  * [25] B. Kim and L. Shimanuki, “Learning value functions with relational state representations for guiding task-and-motion planning,” in _Conference on Robot Learning (CoRL)_ , 2019.
  * [26] B. Kim, L. Shimanuki, L. P. Kaelbling, and T. Lozano-Pérez, “Representation, learning, and planning algorithms for geometric task and motion planning,” _The International Journal of Robotics Research_ , 2021\.
  * [27] F. Chen, J. D. Martin, Y. Huang, J. Wang, and B. Englot, “Autonomous exploration under uncertainty via deep reinforcement learning on graphs,” in _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020.
  * [28] A. Kurenkov, R. Martín-Martín, J. Ichnowski, K. Goldberg, and S. Savarese, “Semantic and geometric modeling with neural message passing in 3D scene graphs for hierarchical mechanical search,” in _International Conference on Robotics and Automation (ICRA)_ , 2021.
  * [29] J. Kossen, K. Stelzner, M. Hussing, C. Voelcker, and K. Kersting, “Structured object-aware physics prediction for video modeling and planning,” in _International Conference on Learning Representations (ICLR)_ , 2020.
  * [30] F. Chen, P. Szenher, Y. Huang, J. Wang, T. Shan, S. Bai, and B. J. Englot, “Zero-shot reinforcement learning on graphs for autonomous exploration under uncertainty,” _CoRR_ , vol. abs/2105.04758, 2021.
  * [31] J. Pineau and S. Thrun, “An integrated approach to hierarchy and abstraction for POMDPs,” Carnegie Mellon University, Tech. Rep. CMU-RI-TR-02-21, 2002.
  * [32] G. Stein, “Generating high-quality explanations for navigation in partially-revealed environments,” in _Advances in Neural Information Processing Systems_ , vol. 34. Curran Associates, Inc., 2021, pp. 17 493–17 506.
  * [33] F. Zhu, X. Liang, Y. Zhu, X. Chang, and X. Liang, “SOON: scenario oriented object navigation with graph-based exploration,” _CoRR_ , vol. abs/2103.17138, 2021.
  * [34] V. Azizi, M. Usman, H. Zhou, P. Faloutsos, and M. Kapadia, “Graph-based generative representation learning of semantically and behaviorally augmented floorplans,” _The Visual Computer_ , vol. 38, no. 8, pp. 2785–2800, may 2021\.
  * [35] A. S. Krishna, K. Gangadhar, N. Neelima, and K. Sahithi, “Topology preserving skeletonization techniques for grayscale images,” in _Computation and Communication Technologies_ , 2016.
  * [36] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, “Pytorch: An imperative style, high-performance deep learning library,” in _Advances in Neural Information Processing Systems 32_. Curran Associates, Inc., 2019, pp. 8024–8035.
  * [37] M. Fey and J. E. Lenssen, “Fast graph representation learning with PyTorch Geometric,” in _ICLR Workshop on Representation Learning on Graphs and Manifolds_ , 2019.
  * [38] S. Brody, U. Alon, and E. Yahav, “How attentive are graph attention networks?” 2021.