# Unveiling Multi-Quantum Excitonic Correlations in Push-Pull Polymer
Semiconductors

Yulong Zheng  [  Esteban Rojas-Gatjens  [  Myeongyeon Lee  [  Elsa Reichmanis
[  Carlos Silva-Acuña<EMAIL_ADDRESS>[

###### Abstract

Bound and unbound Frenkel-exciton pairs are essential transient precursors for
a variety of photophysical and biochemical processes. In this work, we
identify bound and unbound Frenkel-exciton complexes in an electron push-pull
polymer semiconductor using coherent two-dimensional spectroscopy. We find
that the dominant $A_{0-1}$ peak of the absorption vibronic progression is
accompanied by a sub-peak, each dressed by distinct vibrational modes. By
considering the Liouville pathways within a two-exciton model, the imbalanced
cross peaks in one-quantum rephasing and non-rephasing spectra can be
accounted for by the presence of pure biexcitons. The two-quantum non-
rephasing spectra, on the other hand, provide direct evidence for unbound
exciton pairs and biexcitons with dominantly attractive force. In addition,
the spectral features of unbound exciton pairs show mixed absorptive and
dispersive character, implying many-body interactions within the correlated
Frenkel-exciton pairs. Our work offers novel perspectives on the rich
photophysical processes in semiconductor polymers with the presence of Frenkel
exciton complexes.

GT-chem] School of Chemistry and Biochemistry, Georgia Institute of
Technology, 901 Atlantic Drive, Atlanta GA 30332, United States GT-chem]
School of Chemistry and Biochemistry, Georgia Institute of Technology, 901
Atlantic Drive, Atlanta GA 30332, United States Leigh] Department of Chemical
& Biomolecular Engineering, Lehigh University, 124 E. Morton Street, Bethlehem
PA 18015, United States Leigh] Department of Chemical & Biomolecular
Engineering, Lehigh University, 124 E. Morton Street, Bethlehem PA 18015,
United States UdeM] Institut Courtois & Département de physique, Université de
Montréal, 1375 Avenue Thérèse-Lavoie-Roux, Montréal, Québec H2V 0B3, Canada
[GT-chem] School of Chemistry and Biochemistry, Georgia Institute of
Technology, 901 Atlantic Drive, Atlanta GA 30332, United States

Frenkel excitons are a collective of local excitations coupled through
resonant Coulomb interactions within chromophores.1 Despite the fact that the
extent of the delocalization can theoretically span the entirety of the
aggregate structure, no realistic molecular aggregates are disorder-free,
especially in conjugated polymers, where both static disorder (e.g.
conformational disorder from site to site) and environmental fluctuations
(e.g. low-frequency torsional modes) significantly constrain the effective
delocalization length.2, 3, 4, 5 As a consequence, at sufficiently high
excitation densities, multiple excitons can coexist in close proximity,
leading to distinguishable exciton-exciton interactions and correlations.6
Electron push-pull polymers are known to form disordered polymeric
aggregates,7, 8 which could host two-dimensional hybrid HJ excitons.9, 2, 3,
10, 11 In this work, we show direct evidence of two distinct excitons dressed
by different vibrational modes, each with its own vibronic progression.
Furthermore, we demonstrate the presence of Frenkel biexcitons and correlated
exciton pairs revealed in one-quantum (1Q) and two-quantum (2Q) two-
dimensional coherent spectra (2DCS). By tracing the Liouville pathways
qualitatively in a two-exciton basis, we show that the spectral overlap
between the biexcitons and the dominant feature of single excitons gives rise
to asymmetric cross peaks in the 1Q spectra.

Under a two-level molecular picture, Frenkel exciton-exciton interactions
(EEI) can be categorized into two types: the first type, termed kinematic
exciton-exciton interactions, originates from the hard-core-like scattering
between Frenkel excitons due to the Pauli exclusion principle.12 Naturally,
the kinematic interaction gives rise to an effective repulsive two-exction
state, which is observed as a blue-shifted positive absorption feature (in
differential absorption) relative to the ground-state bleach for J-aggregates
in pump-probe experiments.13, 14, 15. The second type is the dynamic exciton-
exciton interaction originating from the differences in the permanent static
dipoles of the ground and excited states.16 For the latter case, experimental
reports on the existence of dynamic Frenkel biexcitons in molecular aggregates
are fairly limited, with sporadic evidence provided by fluence-dependent
intensity and spectral lineshape analysis by transient absorption
measurements.17, 18, 19 Recently, more direct evidence is presented through
the use of multi-quantum coherent spectroscopy.20, 21, 22, 23 Dostál et al.
ascribed the growing two-exciton features in a small-molecule aggregated
system to exciton-exciton interactions through diffusion.20 Malý et al. probed
exciton transport transitioning from wavelike to sub-diffusive behavior
through EEI in a conjugated copolymer with varying chain lengths.21 Gutiérrez-
Meza et al. investigated the correlation between the biexcitonic binding
energy and hybrid H and J aggregate characteristics in a liquid-crystalline-
like conjugated polymer.23, 24 Despite the incremental new discoveries of
Frenkel-exciton properties, the biexciton resonances and many-body
correlations (e.g. excitaion-induced dephasing) in Frenkel-exciton systems are
not well developed as in their Wanner-Mott counterparts.25, 26, 27, 28, 29,
30, 31, 32 In addition, although the biexcitons are observed explicitly in the
2Q spectra, their contributions to the 1Q spectra are often neglected.

In this Letter, we address these issues by probing the conjugated electron
push-pull polymer,
poly[N,N’-bis(2-octyldodecyl)naphthalene-1,4,5,8-bis(dicarboximide)-2,6-diyl]-alt-5,5’-
(2,2’-bithiophene) (or N2200 and its associated chemical structure is shown in
Figure 1a) by means of two-dimensional coherent spectroscopic measurements.
The thin-film preparation of N2200 is described in the Supporting Information
(SI). Compared to conjugated homopolymers, the strong charge-transfer
character in the electron push-pull polymers leads to a large permanent static
dipole moment,33 which determines the strength of dynamic EEI.6 Another
difference lies in the fact that the electronic transitions in conjugated
copolymers are coupled to more vibrational modes, resulting in synergistic
intermode effects, where the weakly-coupled mode could borrow intensities from
the strongly-coupled vibrational mode.34 These, along with polymorphism and
static disorder, lead to significantly congested spectral features in electron
push-pull polymers.

Figure 1: (a) Chemical structure of N2200. (b) Absorption spectra of the low-
energy band of N2200 (blue solid line) and the femtosecond pulse spectrum of
the local oscillator used in the 2DCS measurements reported in this manuscript
(black dashed line shaded in grey).

Implementing 2DCS, we directly resolve (i) electronic correlations between
different excited states and (ii) inhomogeneous and homogeneous broadening
contributions into the optical linewidths.35 We employ a coherent optical
laser beam recombination technique (COLBERT) designed in the research group of
Keith Nelson,36, 37 which adopts a four-wave-mixing (FWM) signal acquisition
scheme based on phase matching imposed by the incident beam geometry and on
time ordering of the femtosecond pulse sequence. This spectroscopy generates a
third-order macroscopic coherent polarization by interacting a pulse train of
three sequential beams with an optically active material resonantly. The
coherent emission propagates in the well-defined direction for one-quantum
rephasing scheme with wavevector
$\vv{k_{s}}=-\vv{k_{a}}+\vv{k_{b}}+\vv{k_{c}}$ and nonrephasing scheme with
wavevector $\vv{k_{s}}=\vv{k_{a}}-\vv{k_{b}}+\vv{k_{c}}$, where the difference
lies on the relative pulse arrival within the two first phase-conjugate
pulses. Eventually, the coherent signal is detected through spectral
interferometry by an attenuated fourth beam (i.e. the local oscillator or LO).
Fourier-transforming along the first and third time duration variable gives
rise to correlated ‘absorption’ and ‘emission’ axes, where the different
electronic transitions lie on the diagonal axis but any correlations between
the electronic states show up as cross peaks.38 The experimental method is
further explained in SI. In this work, we performed a series of fluence-
dependent measurements with the pulse fluence varied from 12.8 to 121
$\mu$J/cm2at an initial population waiting time of 20 fs (to avoid
contamination from coherent artefacts at shorter delays). Here, we display a
case measured at an intermediate fluence in (Figure 2), with the rest shown in
Figure S2 in SI, where we observed no drastic fluence dependence of the
spectral lineshape. We overlap the pulse spectrum with the $A_{0-1}$ vibronic
transition (Figure 2a) in the N2200 thin film. The real, imaginary and
absolute part of the 1Q rephasing diagrams are shown in Figure 2b, c and d,
respectively. The real part is absorptive while the imaginary part is
dispersive along the diagonal axis, as expected in a transmission experiment.
Interestingly, the absorptive feature in Figure 2b appears to be elongated
along the diagonal axis, with a slight tail that extends along the absorption
energy axis, which is enhanced in the absolute diagram in Figure 2d. In
addition, the cross peaks in Figure 2b seems to be negative even though they
are more attenuated compared to the dominant peaks. We will discuss their
implications when considering all possible Liouville pathways later. As the
dephasing rate determines the homogeneous linewidth, we also took the
antidiagonal cuts of the absolute-valued spectra as shown in Figure S3.
Despite the distinct pumping fluences, we observed no drastic differences
between the antidiagonal linewidths, as opposed to what was previously
observed in inorganic and perovskite semiconductors, which was attributed to
excitation-induced dephasing.25, 27, 29 Such difference might be due to the
strongly-bound nature of Frenkel excitons in comparison to Wannier-Mott
excitons, where Frenkel excitons are less susceptible to long-range Coulombic
screening, at least in this type of push-pull conjugated polymer. In contrast
to rephasing spectra, the real (Figure 2f) and imaginary part (Figure 2g) of
the nonrephasing spectrum demonstrate absorptive and dispersive characteristic
across the diagonal axis, respectively. A small side peak is observed above
the dominant $A_{0-1}$ peak, which might be due to the interstate coherence
with $A_{0-2}$ that is out of the spectral range. Since the phase twist is now
perpendicular to the diagonal axis, the shoulder at 1.664 eV along the
diagonal axis and cross peak at (1.736, 1.664) eV emerge more clearly. The
same character is also observed in the absolute-valued diagram for
nonrephasing in Figure 2h.

Figure 2: (a) and (e) absorption spectra of $A_{0-1}$ in blue solid curve with
the pulse spectra shown in dashed black line shaded in grey. (b)-(d) real,
imaginary and absolute spectrum of the rephasing diagram, measured with a
fluence of 25.6 $\mu$J/cm2. (f)-(h) real, imaginary and absolute spectrum of
the nonrephasing diagram. All measurements are conducted with the samples
positioned in a high-vacuum chamber at ambient temperature.

A common practice to eliminate the phase twist issue is to sum the real part
of rephasing and nonrephasing diagram, in which the linewidth is purely
absorptive.39 By doing so, the small shoulder becomes more prevalent besides
the dominant $A_{0-1}$ transition as shown in Figure 3a-d. It is worth noting
that the peak amplitude is weighted by the product of the absorption spectrum
and the pulse intensity. As the intensity of the beam is much more attenuated
on the low-energy part, this feature should be much stronger than it appears.
The cross peak at (1.736, 1.656) eV indicates the two excitons share a common
ground state, which excludes the possibility of the side peak originating from
a different polymer phase. In addition, we also want to highlight that the
sub-peak cannot be the tail of $A_{0-0}$ as its energy difference from the
$A_{0-1}$ is less than 80 meV, greatly smaller than the energy of the dominant
vinyl-stretching mode (170 meV), characteristic of various conjugated
polymers.40 Another important feature is the asymmetric cross peaks in the
upper and lower quadrants of the 2D spectrum, also seen in the nonrephasing
diagram. Such signature was explained previously for a cancellation of the
Liouville pathways for the interstate coherence and excited state absorption
(of mixed biexciton states, see below).41 The cross peak amplitude would then
scale as the coupling strength between the two excitons in the weak-coupling
limit. In the upper quadrant, the cross peak shown in the red dashed square
has a positive sign as opposed to the dominant features. Since they are
overlapped with the dominant feature, their real intensities might be
underestimated.

Figure 3: (a)-(d) 1Q total-correlation spectroscopy of 12.8, 25.6, 51.2, and
121 $\mu$J/cm2, respectively. The black dash lines indicate the position of
the dominant $A_{0-1}$ feature. The red dash squares highlight positive
features indicating the contribution from biexcitons. (e) Level scheme for
both local and normal mode system of two heterogeneous vibronic excitons and
their associated biexcitons. The relative energies between the normal modes
depend upon the sign and magnitude of exciton-exciton coupling strengths.

By identifying the two one-exciton transitions, we can apply the level scheme
of a pair of heterogeneous vibronic excitons with their associated biexciton
states as shown in Figure 3e.39 $|n_{\nu_{1}}m_{\nu_{2}}\rangle$ denotes a
state that has $m$ excitons, each coupled to the dominant vinyl-stretching
vibrational mode, $\nu_{2}$, and $n$ excitons coupled to the satellite
vibrational mode, $\nu_{1}$. As the relative position of $|n\rangle$ and
$|m\rangle$ can encode the two vibration modes directly, we discard the
subscription in the following discussion for simplicity. For FWM experiments,
only a conserved two-exciton space needs to be considered. Specifically, we
only take account of the pure biexciton states, $|20\rangle$ and $|02\rangle$,
and mixed biexciton states, $|11\rangle$. Transitions are ignored when
multiple transition dipoles are required. For example, a direct transition,
$|10\rangle\rightarrow|02\rangle$ is considered forbidden since it involves
multiple photons in one step. The associated normal mode is given
schematically on the right panel in Figure 3e. The exact energy shift depends
on the magnitude and sign of the exciton-exciton coupling operators.

Figure 4: Liouville pathways for rephasing (a) and nonrephasing (b) diagrams.
Schematic of purely absorptive 1Q spectra for rephasing (c) and nonrephasing
(d) phase matching conditions. The negative and positive features are denoted
in red and blue, respectively. Reproduced based on Ref.39.

The Liouville pathways considering all allowed transitions are demonstrated in
Figure 4. Despite the fact that the linewidths in conjugated polymers are
broadened, qualitative features can be observed immediately. The positive
features that originate from transitions to the mixed biexciton
($|f_{m}\rangle$) and pure biexciton ($|f_{1}\rangle,|f_{2}\rangle$) states,
concentrate on the left regime to the diagonal axis, while the right side of
the diagonal axis has an overlapped feature from the excited state absorption
of the mixed biexciton and interstate coherence as mentioned earlier in both
rephasing and nonrephasing spectra. The overall imbalanced 1Q total
correlation spectra are indeed observed as shown in Figure 3a-d. However, here
we considered all three biexciton states, where the pure biexciton features
also give rise to positive features even though they could have larger energy
shift. Therefore, the overall imbalanced spectral features could be caused by,
1) the overlap between the mixed biexciton absorption and interstate coherence
on both sides of the diagonal axis with their amplitude determined by the EEI
strength and their relative transition dipole moments, 2) pure biexciton
absorption on the left regime, leaving the right regime in negative sign due
to the interstate coherence solely or 3) a combination of both contributions.
To address this issue, we resort to the 2Q nonrephasing scheme in the phase-
matching direction $\vv{k_{s}}=\vv{k_{a}}+\vv{k_{b}}-\vv{k_{c}}$.42 In
contrast to the 1Q, now the first two pulses interacting with the material
share the same phase. The sequential excitation could generate biexciton and
unbound exciton pairs, which can be resolved in more detail along the two-
quantum axis.43, 28

Figure 5: (a) real, (b) imaginary and (c) absolute spectrum of the 1Q
nonrephasing spectra. (a) real, (b) imaginary and (c) absolute spectrum of the
2Q nonrephasing diagram. The black dash line indicate the peak position at the
dominant $A_{0-1}$. The red dash line locates at the side peak position.

To more easily compare the 2Q spectral features with their 1Q counterparts,
the 1Q and 2Q nonrephasing measurements are presented in Figure 5 under
pumping fluence of each pulse being 121 $\mu$J/cm2. The spectral features do
not significantly depend on the fluences, although low fluence measurements
seem to present more artefacts as shown in Figure S4 in SI. A close match of
the energies of the two heterogeneous vibronic excitons in 1Q and 2Q spectra
can be found by the red and black dashed lines. Two prominent features can be
observed and explained in Figure 5d-f. First, the two dominant peaks, $\beta$
and $\alpha$ reside on the diagonal axis, each accompanied by a red-shifted
side peak, $\beta^{\prime}$ and $\alpha^{\prime}$ respectively, along the two-
quantum axis. Therefore, the binding energies, experimentally determined as
($E_{2Q}-2E_{1Q}$), for $|f_{1}\rangle$ and $|f_{2}\rangle$ are estimated to
be -76 and -64 meV as shown in Figure S6, respectively, where the negative
sign indicates their attractive nature. The exciton binding energies are
comparable since the two vibronic excitons have the same electronic origins,
while the slight difference might originate from the perturbation of the two
distinct vibrational modes. Interestingly, a blue-shifted shoulder around
(1.736, 3.502),eV can also be observed extending out of $\alpha$. Therefore,
the repulsive binding energy can be estimated to be around 39 meV. One
possible origin of such positive feature could be the kinematic exciton-
exciton scattering mentioned above. Second, unlike the real and imaginary part
of the 1Q nonrephasing spectrum in Figure 5a and b, which show distinct
absorptive and dispersive features, respectively, the real and imaginary part
of the 2Q nonrephasing spectrum show mixed features. Such features are
previously observed in gallium-arsenide quantum wells, which are ascribed to
many-body interactions.28 Thirdly, a small side peak $\sigma$ at (1.736,
3.312) eV, is observed in the absolute diagram, while the real and imaginary
part of the spectra show stronger signals. As the $\sigma$ peak absorbs
approximately twice the $|e_{1}\rangle$ energy and emits at the
$|e_{2}\rangle$, it suggests that the coherence originates between the
$|e_{1}\rangle$ exciton complexes (i.e. unbound exciton pair $2|e_{1}\rangle$
or the bound exciton, $|f_{1}\rangle$) and the single exciton,
$|e_{2}\rangle$. In contrast, we did not observe the coherences between the
$|e_{2}\rangle$ exciton complexes and $|e_{1}\rangle$, although a slight
elongation on top of the $\beta$ peak in Figure 5e suggests its weak presence.
Although the 2Q nonrephasing spectra provided rich information in the multi-
exciton correlations, certain concerns still remain. One of which is the non-
negligible spectral overlap between $\beta$ and $\sigma$ in Figure 5d and e,
leading to ambiguities in deciphering the many-body effects on their presence.

It is worth mentioning that the biexciton states observed here do not
originate from the higher-lying excited state. Previous transient absorption
measurements on N2200 show that the excited-state absorption lies around 400
meV above the ground-state absorption, which is outside the spectral window
here.44 In addition, Denti et al. previously conducted Raman and infrared
spectroscopy on the doped N2200 system, showing that the polaron formation is
strongly localized on the NDI units, in great contrast to other conjugated
homopolymers.45 Despite the fact that the 2D 1Q measurements performed here
look at exciton dynamics at initial population time ($T=20$ fs), it is not
unreasonable to hypothesize that the biexcitons observed in this work might be
attributed to interactions between localized excitons on stacked NDI unit and
its neighboring unit. Although we only probed one sample under specific
processing conditions, further studies incorporating samples processed under
different conditions will be valuable to correlate exciton dynamics with
solid-state microstructure which will be essential to understand multi-exciton
properties in semiconductor polymers. Previously, the short- and long-range
aggregation in N2200 have been demonstrated to be tuned by varied molecular
weights46, solvent quality47, film annealing48, blending49 and etc, which give
handles to observe exciton pair and biexciton generations by different
preparation processes. Furthermore, to assign the satellite vibrational mode,
$\alpha$, both the energy separation between $\alpha$ and $\beta$ and Huang-
Rhys (HR) factors are needed. Figure 5 suggests that the energy difference
between the two vibronic excitons should be larger than 72 meV (580 cm-1) as
the side peak is limited by the spectral window. The accurate assignment of
the vibrational mode other than the dominant ring-stretching mode is still
elusive due to their unknown HR factors. Nonetheless, if we assume the HR
factors of both modes are comparable, the first vibrational mode might land
below 1000 cm-1, which is in wavenumber range of the low-energy stretching and
torsional modes of the chain backbone, since the dominant Raman modes are
already around 1500 cm-1 in N2200 thin film. Last but not the least, the mixed
biexciton state does not seems to contribute significantly in either 1Q or 2Q
spectra. As shown by Yang and Mukamel, spectral features from both mixed
biexciton states should reside off-diagonally with equal two-quantum energy.26
However, the two biexcitons observed in this work do not show coherences from
a mixed biexciton state. Only a small interstate coherence peak from pure
$|e_{1}\rangle$ exciton complexes and the single exciton $|e_{2}\rangle$ is
observed. Although the electronic transition from $|e_{1}\rangle$ or
$|e_{2}\rangle$ to $|f_{m}\rangle$ is allowed, the vibrational transition from
$|v_{1}\rangle$ to $|v_{2},v_{1}\rangle$ could be partly forbidden due to the
orthogonality of the two normal vibrational modes as indicated in Equation 1,
where the equality holds true under Born-Oppenheimer (BO) approximation,
leading to the weak and even no appearance of the coherences from the mixed
biexciton.

$\langle f_{m};v_{1},v_{2}|\vv{\mu}|e_{1};v_{1}\rangle=\langle
f_{m}|\vv{\mu}|e_{1}\rangle\langle v_{1},v_{2}|v_{1}\rangle$ (1)

Previous work by De Sio et al has demonstrated the presence of conical
intersections of multiple potential wells addressed by both symmetric and
asymmetric vibrational modes in molecular aggregates.50 Close to the conical
intersection does the BO approximation break down since the non-adiabatic
transition is enabled by the vibronic coupling. However, as all measurements
performed here are at early population time, the BO approximation should still
hold considering that the coherent exciton motion does not initiate yet.
Nevertheless, the 2Q spectral features at long population times are of great
interest to investigate, as the conical intersection will allow transitions to
dark states which are not visible under direct optical excitation.

Finally, we highlight that the pump fluences employed in this work range from
10-100 $\mu$J/cm2, in which sufficient exciton-exciton annihilation (EEA) is
expected in electron push-pull polymers on picoseconds time scale.51, 52 Our
work shows direct evidence of both correlated exciton pairs and bounded
biexcitons even at initial population time, which might be precursors for EEA
process in N2200. Dostál et al. directly monitored the change of two-quantum
peak intensities for a molecular aggregate in five-wave-mixing experiments
with time evolving into the nanosecond range.20 By fitting the temporal
evolution with the derived theoretical result considering the direct
population of biexciton states, they were able to acquire an associated
diffusion constant in good consistency with previous literature.

In addition to the method of direct monitoring through EEI, we suggest that
the lineshape at initial population time and the diffusion constant might have
a deterministic correlation. Moix et al. studied the quantum transport
behavior theoretically at short and long times in a one-dimensional
J-aggregate chain, when both static disorder and environmental fluctuations
exist. Of particular relevance, they treated either analytical solutions for
master equations for the exciton dynamics, which correlate the exciton
diffusion constants to the Coulombic coupling constant, static disorder and
dephasing rates. In conjugated polymers, the first two parameters can
theoretically be acquired by fitting the linear absorption spectra the with
the Spano model.53 Meanwhile, the dephasing rates could be determined by
analyzing the full coherent line shape properly in 2DCS measurements by
utilizing a microscopic theory of dephasing.

The microscopic dephasing theory points out that the exciton dynamics
generated by the impulsive excitation are not only determined by population
decay, which are in turn determined by the radiative and nonradiative rates,
but that there is also a contribution to decoherence due to system-bath
interactions e.g. exciton-phonon and exciton-exciton scattering.27, 31 The
combination of both gives rise to the homogeneous linewidth in frequency
domain, which can be determined by fitting the antidiagonal cut with a
Lorentzian function in a purely homogeneously broadened limit. However, in
addition to the homogeneous line broadening contributions, the inhomogeneous
broadening arising from static disorder (e.g. each molecular segments adopts a
slightly different conformation, resulting in different transition energies)
will broaden the diagonal line shape, which has an impact on the antidiagonal
linewidth concurrently.54 Therefore, alongside the Coulomb coupling constant
and the static disorder, the remaining parameter, homogeneous dephasing rate,
could be obtained through the lineshape analysis, thus, an effective diffusion
constant can be determined. The comparison between this and the one determined
from traditional ultrafast measurements could lead to new physical insights
into the evolution of exciton transport and diffusion behavior.

In conclusion, we perform 1Q and 2Q coherent optical spectroscopic
measurements on an electron push-pull conjugated polymer, where clear features
originating from two heterogeneous vibronic excitons alongside their exciton
complexes are observed. 1Q measurements display spectral features due to the
advantageous attractive bound biexcitons, leading to asymmetric cross peaks.
The resultant 2D spectra can be explained qualitatively by tracing the
Liouville pathways using a two-exciton model. The 2Q nonrephasing diagram
provides further unambiguous evidence on both bound biexcitons and unbound
exciton pairs. Specifically, unbound exciton pairs are found to be the
dominant feature with a strong attractive biexciton subpeak, the binding
energy of which is approximately 70 meV. A weak repulsive biexciton is also
observed from the shoulder of the unbound exciton pairs. The unbound exciton
pairs show mixed absorptive and dispersive lineshape in contrast to that of
the attractive biexciton, indicating the many-body effects in the unbound but
correlated exciton pairs.

CSA acknowledges funding from the Government of Canada (Canada Excellence
Research Chair CERC-2022-00055) and from the Courtois Institute, Faculté des
arts et des sciences, Université de Montréal (Chaire de Recherche de
l’Institut Courtois) for support during the redaction of the manuscript. CSA,
ER, and ERG acknowledge support from National Science Foundation (NSF) Grant
number DMR-2019444 (IMOD) for support for the data acquisition and analysis;
YZ and ML acknowledge NSF-DMREF funding through grant number 1922111 for
support for sample preparation and characterization. ER also appreciates
support associated with the Carl Robert Anderson Chair funds at Lehigh
University.

See the Supplementary Information for the experimental methods including
sample preparation, the technique of 2DCS and the XFROG results. Additional
fluence-dependent 1Q and 2Q measurements are also provided for comparison.

## References

  * Frenkel 1931 Frenkel, J. On the transformation of light into heat in solids. I. _Phys. Rev._ 1931, _37_ , 17
  * Paquin et al. 2013 Paquin, F.; Yamagata, H.; Hestand, N. J.; Sakowicz, M.; Bérubé, N.; Côté, M.; Reynolds, L. X.; Haque, S. A.; Stingelin, N.; Spano, F. C. et al. Two-dimensional spatial coherence of excitons in semicrystalline polymeric semiconductors: Effect of molecular weight. _Phys. Rev.B_ 2013, _88_ , 155202
  * Spano and Silva 2014 Spano, F. C.; Silva, C. H-and J-aggregate behavior in polymeric semiconductors. _Ann. Rev. Phys. Chem._ 2014, _65_ , 477–500
  * Moix et al. 2013 Moix, J. M.; Khasin, M.; Cao, J. Coherent quantum transport in disordered systems: I. The influence of dephasing on the transport properties and absorption spectra on one-dimensional systems. _New J. Phys._ 2013, _15_ , 085010
  * Zheng et al. 2023 Zheng, Y.; Venkatesh, R.; Callaway, C. P.; Viersen, C.; Fagbohungbe, K. H.; Liu, A. L.; Risko, C.; Reichmanis, E.; Silva-Acuña, C. Chain conformation and exciton delocalization in a push-pull conjugated polymer. _Chem. Mater._ 2023, _35_ , 10258–10267
  * Knoester and Agranovich 2003 Knoester, J.; Agranovich, V. M. Frenkel and charge-transfer excitons in organic solids. _Thin Films Nanostr._ 2003, _31_ , 1–96
  * Noriega et al. 2013 Noriega, R.; Rivnay, J.; Vandewal, K.; Koch, F. P.; Stingelin, N.; Smith, P.; Toney, M. F.; Salleo, A. A general relationship between disorder, aggregation and charge transport in conjugated polymers. _Nat. Mater._ 2013, _12_ , 1038–1044
  * Zheng et al. 2017 Zheng, Y.-Q.; Yao, Z.-F.; Lei, T.; Dou, J.-H.; Yang, C.-Y.; Zou, L.; Meng, X.; Ma, W.; Wang, J.-Y.; Pei, J. Unraveling the solution-state supramolecular structures of donor–acceptor polymers and their Influence on solid-state morphology and charge-transport properties. _Adv. Mater._ 2017, _29_ , 1701072
  * Yamagata and Spano 2012 Yamagata, H.; Spano, F. C. Interplay between intrachain and interchain interactions in semiconducting polymer assemblies: The HJ-aggregate model. _J. Chem. Phys._ 2012, _136_ , 184901
  * Zhong et al. 2020 Zhong, C.; Bialas, D.; Spano, F. C. Unusual non-kasha photophysical behavior of aggregates of push–pull donor–acceptor chromophores. _J. Phys. Chem. C_ 2020, _124_ , 2146–2159
  * Chang et al. 2021 Chang, X.; Balooch Qarai, M.; Spano, F. C. HJ-aggregates of donor–acceptor–donor oligomers and polymers. _J. Chem. Phys._ 2021, _155_ , 034905
  * Agranovich et al. 2000 Agranovich, V.; Dubovsky, O.; Basko, D.; La Rocca, G.; Bassani, F. Kinematic frenkel biexcitons. _J. Lumin._ 2000, _85_ , 221–232
  * Fidder et al. 1993 Fidder, H.; Knoester, J.; Wiersma, D. A. Observation of the one-exciton to two-exciton transition in a J aggregate. _J. Chem. Phys._ 1993, _98_ , 6564–6566
  * Bakalis and Knoester 1999 Bakalis, L. D.; Knoester, J. Pump-probe spectroscopy and the exciton delocalization length in molecular aggregates. _J. Phys. Chem. B_ 1999, _103_ , 6620–6628
  * Jumbo-Nogales et al. 2022 Jumbo-Nogales, A.; Krivenkov, V.; Rusakov, K.; Urban, A. S.; Grzelczak, M.; Rakovich, Y. P. Cross determination of exciton coherence length in J-aggregates. _The Journal of Physical Chemistry Letters_ 2022, _13_ , 10198–10206
  * Spano et al. 1991 Spano, F. C.; Agranovich, V.; Mukamel, S. Biexciton states and two-photon absorption in molecular monolayers. _J. Chem. Phys._ 1991, _95_ , 1400–1409
  * Klimov et al. 1998 Klimov, V.; McBranch, D.; Barashkov, N.; Ferraris, J. Biexcitons in $\pi$-conjugated oligomers: Intensity-dependent femtosecond transient-absorption study. _Phys. Rev.B_ 1998, _58_ , 7654
  * Chakrabarti et al. 1998 Chakrabarti, A.; Schmidt, A.; Valencia, V.; Fluegel, B.; Mazumdar, S.; Armstrong, N.; Peyghambarian, N. Evidence for exciton-exciton binding in a molecular aggregate. _Phys. Rev.B_ 1998, _57_ , R4206
  * Cunningham et al. 2020 Cunningham, P. D.; Díaz, S. A.; Yurke, B.; Medintz, I. L.; Melinger, J. S. Delocalized two-exciton states in DNA scaffolded cyanine dimers. _J. Phys. Chem. B_ 2020, _124_ , 8042–8049
  * Dostál et al. 2018 Dostál, J.; Fennel, F.; Koch, F.; Herbst, S.; Würthner, F.; Brixner, T. Direct observation of exciton–exciton interactions. _Nat. Comm._ 2018, _9_ , 2466
  * Malỳ et al. 2020 Malỳ, P.; Lüttig, J.; Turkin, A.; Dostál, J.; Lambert, C.; Brixner, T. From wavelike to sub-diffusive motion: exciton dynamics and interaction in squaraine copolymers of varying length. _Chem. Sci._ 2020, _11_ , 456–466
  * Malỳ et al. 2020 Malỳ, P.; Mueller, S.; Lüttig, J.; Lambert, C.; Brixner, T. Signatures of exciton dynamics and interaction in coherently and fluorescence-detected four-and six-wave-mixing two-dimensional electronic spectroscopy. _J. Chem. Phys._ 2020, _153_
  * Gutiérrez-Meza et al. 2021 Gutiérrez-Meza, E.; Malatesta, R.; Li, H.; Bargigia, I.; Srimath Kandada, A. R.; Valverde-Chávez, D. A.; Kim, S.-M.; Li, H.; Stingelin, N.; Tretiak, S. et al. Frenkel biexcitons in hybrid HJ photophysical aggregates. _Science advances_ 2021, _7_ , eabi5197
  * Bittner and Silva 2022 Bittner, E. R.; Silva, C. Concerning the stability of biexcitons in hybrid HJ aggregates of $\pi$-conjugated polymers. _J. Chem. Phys._ 2022, _156_
  * Li et al. 2006 Li, X.; Zhang, T.; Borca, C. N.; Cundiff, S. T. Many-body interactions in semiconductors probed by optical two-dimensional Fourier transform spectroscopy. _Phys. Rev. Lett._ 2006, _96_ , 057406
  * Yang and Mukamel 2008 Yang, L.; Mukamel, S. Revealing exciton-exciton couplings in semiconductors using multidimensional four-wave mixing signals. _Phys. Rev. B_ 2008, _77_ , 075335
  * Moody et al. 2015 Moody, G.; Kavir Dass, C.; Hao, K.; Chen, C.-H.; Li, L.-J.; Singh, A.; Tran, K.; Clark, G.; Xu, X.; Berghäuser, G. et al. Intrinsic homogeneous linewidth and broadening mechanisms of excitons in monolayer transition metal dichalcogenides. _Nat. Comm._ 2015, _6_ , 8315
  * Karaiskaj et al. 2010 Karaiskaj, D.; Bristow, A. D.; Yang, L.; Dai, X.; Mirin, R. P.; Mukamel, S.; Cundiff, S. T. Two-quantum many-body coherences in two-dimensional Fourier-transform spectra of exciton resonances in semiconductor quantum wells. _Phys. Rev. Lett._ 2010, _104_ , 117401
  * Thouin et al. 2019 Thouin, F.; Cortecchia, D.; Petrozza, A.; Kandada, A. R. S.; Silva, C. Enhanced screening and spectral diversity in many-body elastic scattering of excitons in two-dimensional hybrid metal-halide perovskites. _Phys. Rev. Res._ 2019, _1_ , 032032
  * Srimath Kandada et al. 2020 Srimath Kandada, A. R.; Li, H.; Thouin, F.; Bittner, E. R.; Silva, C. Stochastic scattering theory for excitation-induced dephasing: Time-dependent nonlinear coherent exciton lineshapes. _The Journal of Chemical Physics_ 2020, _153_
  * Li et al. 2023 Li, H.; Shah, S.; Kandada, A. R. S.; Silva, C.; Piryatinski, A.; Bittner, E. R. The optical signatures of stochastic processes in many-body exciton scattering. _Annual Review of Physical Chemistry_ 2023, _74_ , 467–492
  * Rojas-Gatjens et al. 2023 Rojas-Gatjens, E.; Li, H.; Vega-Flick, A.; Cortecchia, D.; Petrozza, A.; Bittner, E. R.; Srimath Kandada, A. R.; Silva-Acuña, C. Many-Exciton Quantum Dynamics in a Ruddlesden–Popper Tin Iodide. _J. Phys. Chem. C_ 2023, _127_ , 21194–21203
  * Grisanti et al. 2009 Grisanti, L.; D’Avino, G.; Painelli, A.; Guasch, J.; Ratera, I.; Veciana, J. Essential state models for solvatochromism in donor- acceptor molecules: The role of the bridge. _J. Phys. Chem. B_ 2009, _113_ , 4718–4725
  * Zhao and Spano 2007 Zhao, Z.; Spano, F. C. Multiple mode exciton-phonon coupling: Applications to photoluminescence in oligothiophene thin films. _J. Phys. Chem. C_ 2007, _111_ , 6113–6123
  * Mukamel 1995 Mukamel, S. _Principles of nonlinear optical spectroscopy_ ; Oxford University Press, 1995
  * Vaughan et al. 2005 Vaughan, J. C.; Hornung, T.; Feurer, T.; Nelson, K. A. Diffraction-based femtosecond pulse shaping with a two-dimensional spatial light modulator. _Opt. Lett._ 2005, _30_ , 323–325
  * Turner et al. 2011 Turner, D. B.; Stone, K. W.; Gundogdu, K.; Nelson, K. A. Invited Article: The coherent optical laser beam recombination technique (COLBERT) spectrometer: Coherent multidimensional spectroscopy made easier. _Rev. Sci. Instrum._ 2011, _82_
  * Fresch et al. 2023 Fresch, E.; Camargo, F. V.; Shen, Q.; Bellora, C. C.; Pullerits, T.; Engel, G. S.; Cerullo, G.; Collini, E. Two-dimensional electronic spectroscopy. _Nat. Rev. Methods Primers_ 2023, _3_ , 84
  * Hamm and Zanni 2011 Hamm, P.; Zanni, M. _Concepts and methods of 2D infrared spectroscopy_ ; Cambridge University Press, 2011
  * Chang et al. 2022 Chang, X.; Balooch Qarai, M.; Spano, F. C. Intermolecular charge transfer in H-and J-aggregates of donor–acceptor–donor chromophores: The curious case of bithiophene-DPP. _J. of Phys. Chem. C_ 2022, _126_ , 18784–18795
  * Malỳ and Mančal 2018 Malỳ, P.; Mančal, T. Signatures of exciton delocalization and exciton–exciton annihilation in fluorescence-detected two-dimensional coherent spectroscopy. _J. Phys. Chem. Lett._ 2018, _9_ , 5654–5659
  * Kim et al. 2009 Kim, J.; Mukamel, S.; Scholes, G. D. Two-dimensional electronic double-quantum coherence spectroscopy. _Accounts of chemical research_ 2009, _42_ , 1375–1384
  * Yang and Mukamel 2008 Yang, L.; Mukamel, S. Two-dimensional correlation spectroscopy of two-exciton resonances in semiconductor quantum wells. _Phys. Rev. Lett._ 2008, _100_ , 057402
  * Jin et al. 2017 Jin, F.; Ding, G.; Wang, Y.; Yuan, J.; Guo, W.; Yuan, H.; Sheng, C.; Ma, W.; Zhao, H. Thermal annealing effect on ultrafast charge transfer in all-polymer solar cells with a non-fullerene acceptor N2200. _J. Phys. Chem. C_ 2017, _121_ , 8804–8811
  * Denti et al. 2019 Denti, I.; Cimo, S.; Brambilla, L.; Milani, A.; Bertarelli, C.; Tommasini, M.; Castiglioni, C. Polaron confinement in n-doped P (NDI2OD-T2) unveiled by vibrational spectroscopy. _Chem. Mater._ 2019, _31_ , 6726–6739
  * Nahid et al. 2017 Nahid, M. M.; Matsidik, R.; Welford, A.; Gann, E.; Thomsen, L.; Sommer, M.; McNeill, C. R. Unconventional Molecular Weight Dependence of Charge Transport in the High Mobility n-type Semiconducting Polymer P (NDI2OD-T2). _Advanced Functional Materials_ 2017, _27_ , 1604744
  * Nahid et al. 2018 Nahid, M. M.; Welford, A.; Gann, E.; Thomsen, L.; Sharma, K. P.; McNeill, C. R. Nature and Extent of Solution Aggregation Determines the Performance of P (NDI2OD-T2) Thin-Film Transistors. _Advanced Electronic Materials_ 2018, _4_ , 1700559
  * Trefz et al. 2018 Trefz, D.; Gross, Y. M.; Dingler, C.; Tkachov, R.; Hamidi-Sakr, A.; Kiriy, A.; McNeill, C. R.; Brinkmann, M.; Ludwigs, S. Tuning orientational order of highly aggregating P (NDI2OD-T2) by solvent vapor annealing and blade coating. _Macromolecules_ 2018, _52_ , 43–54
  * Tang et al. 2021 Tang, L.; Watts, B.; Thomsen, L.; McNeill, C. R. Morphology and charge transport properties of P(NDI2OD-T2)/polystyrene blends. _Macromolecules_ 2021, _54_ , 11134–11146
  * De Sio et al. 2021 De Sio, A.; Sommer, E.; Nguyen, X. T.; Groß, L.; Popović, D.; Nebgen, B. T.; Fernandez-Alberti, S.; Pittalis, S.; Rozzi, C. A.; Molinari, E. et al. Intermolecular conical intersections in molecular aggregates. _Nature Nanotechnology_ 2021, _16_ , 63–68
  * Zheng et al. 2024 Zheng, Y.; Venkatesh, R.; Rojas-Gatjens, E.; Reichmanis, E.; Silva-Acuña, C. Exciton bimolecular annihilation dynamics in push–pull semiconductor polymers. _J. Phys. Chem. Lett._ 2024, _15_ , 272–280
  * Wang et al. 2021 Wang, K.; Chen, H.; Zhang, J.; Zou, Y.; Yang, Y. Intrachain and interchain exciton–exciton annihilation in donor–acceptor copolymers. _J. Phys. Chem. Lett._ 2021, _12_ , 3928–3933
  * Clark et al. 2009 Clark, J.; Chang, J.-F.; Spano, F. C.; Friend, R. H.; Silva, C. Determining exciton bandwidth and film microstructure in polythiophene films using linear absorption spectroscopy. _Applied Physics Letters_ 2009, _94_ , 117
  * Siemens et al. 2010 Siemens, M. E.; Moody, G.; Li, H.; Bristow, A. D.; Cundiff, S. T. Resonance lineshapes in two-dimensional Fourier transform spectroscopy. _Opt. Exp._ 2010, _18_ , 17699–17708

See pages 1-9 of SI_v2.pdf


# Evaluating Guiding Spaces for Motion Planning

Amnon Attali1 Stav Ashur1 Isaac Burton Love1 Courtney McBeth1 James Motes1
Diane Uwacu2
Marco Morales1 Nancy M. Amato1 1Department of Computer Science, University of
Illinois, 201 N. Goodwin Avenue, Urbana, IL 61801, USA2Department of Computer
Science and Engineering, Texas A&M University, College Station, Texas,
77843-3112, USA

(September 2022)

###### Abstract

Randomized sampling based algorithms are widely used in robot motion planning
due to the problem’s intractability, and are experimentally effective on a
wide range of problem instances. Most variants do not sample uniformly at
random, and instead bias their sampling using various heuristics for
determining which samples will provide more information, or are more likely to
participate in the final solution. In this work, we define the _motion
planning guiding space_ , which encapsulates many seemingly distinct prior
works under the same framework. In addition, we suggest an information
theoretic method to evaluate guided planning which places the focus on the
quality of the resulting biased sampling. Finally, we analyze several motion
planning algorithms in order to demonstrate the applicability of our
definition and its evaluation.

##  I Introduction

An instance of a motion planning problem involves computing a collision-free
path between configurations of a robot in a continuous space. The family of
sampling based motion planning (SBMP) algorithms uses random sampling of
configuration space, and local attempts to connect valid configurations, in
order to find such a path [12, 11]. SBMP is a powerfully general approach,
which assumes very little prior knowledge of the underlying space. On the
other hand, real world robotics problems contain much underlying structure. In
particular, realistic configuration spaces are not arbitrary topological
spaces, but rather arise from the interaction of a known robot geometry with a
known set of obstacles in the 2/3D world (workspace\environment).

In this paper we discuss SBMP works which attempt to replace the uniform
sampling of configuration space with biased sampling, which takes advantage of
some of this underlying structure. In section II we formalize the definition
of a _motion planning guiding space_ , a phrase which has been used informally
by many researchers in seemingly distinct contexts. Next, in section III, we
provide a categorization of some these past works, and indicate how they are
indeed guiding spaces. Finally, in section IV, we describe an information
theoretic metric which provides a more nuanced evaluation of biased sampling
methods, and then demonstrate this metric on a set of algorithms in Section V.

We note that we are not the first to suggest alternative metrics for
evaluating motion planning, for example in [15], the authors describe a metric
that can be used to evaluate probabilistic roadmaps (PRM), by classifying new
samples based on their effect on the graph structure. Moreover prior work has
used information theoretic concepts in motion planning. For example in [6],
the algorithm adds configurations that maximize the expected information gain,
and [1] attempts to compute an information preserving space based on state
aggregation. In this work, our focus is on applying such ideas to guiding
spaces, and as such we focus our discussion of related work in section III on
algorithms that employ guiding spaces.

##  II Definition of Guiding Space

(a) A 2D workspace with a stationary 2-joint manipulator, and 2 obstacles.
Three intermediates from the path found in guiding space (b) are shown in
dashed gray, where the last is the target configuration. We observe that one
intermediate is invalid.

(b) The lazy planning guiding space for the environment (a) without obstacle
$o_{2}$. A red curve shows a path between the current and target
configurations shown in (a), and a blue wedge shows the resulted sampling
bias.

Figure 1: An illustration of guiding space usage.

######  Definition 1 (Guiding Space)

Let $r$ be a robot, and $E$ be an environment. Denote the implicit
configuration space given by $r$ and $E$ as $\mathcal{C}$. A Guiding Space is
a reduction from a motion planning instance in $\mathcal{C}$ to a motion
planning instance in another space $\mathcal{S}$. It consists of a pair

$(f:\mathcal{C}\longrightarrow\mathcal{S},h:\mathcal{S}\times\mathcal{S}\longrightarrow\Delta(\mathcal{C})).$

We refer to $\mathcal{S}$ as the Guiding Space, $f$ as the _projection_ which
maps instances of motion planning problems in $\mathcal{C}$ to $\mathcal{S}$,
and $h$ as the _heuristic_ which provides guidance (e.g., biased samples) via
a distribution $\Delta(C)$ over the continuous $\mathcal{C}$.

This definition gives rise to a natural motion planning algorithm. Given a
motion planning instance composed of start and goal configurations $(s,t)$ in
$\mathcal{C}$, and a guiding space $(f,h)$, guided planning produces a motion
planning instance $(u,v)=(f(s),f(t))$ in $\mathcal{S}$, and then new samples
in configuration space, $x\sim h(u,v),x\in\mathcal{C}$.

Note that the algorithm can create a set $\\{\mathcal{S}_{i}\\}$ of spaces,
combining the guidance they provide. Alternatively it can create a sequence of
such spaces, and use each guiding space $\mathcal{S}_{i}$ to provide a single
new sample in $\mathcal{C}$, which informs the construction of the next space
$\mathcal{S}_{i+1}$. The definition is general, for example we do not restrict
the structure of $f$ and $h$, intentionally not limiting the set of algorithms
that can be interpreted as using guiding spaces, and rather identifying the
components of guidance which can be individually analyzed.

Finally we observe that the definition inherently lends itself to a recursive
hierarchy, in which a guiding space $(f,h)$ can itself have a guiding space
which informs how $h$ solves motion planning instances in $\mathcal{S}$.
Similarly, we can consider the trivial guiding spaces:
$\mathcal{S}=\mathcal{C}$ and $\mathcal{S}=\\{0\\}$. When
$\mathcal{S}=\mathcal{C}$ we have $f(s)=s$, the identity function, and
$h(s,t)$ is a constant distribution which produces an $(s,t)$ path $P_{s,t}$.
This represents perfect guidance along a solution to the motion planning
instance. When $\mathcal{S}=\\{0\\}$ we have $f(x)=0$ and
$h(f(s),f(t))=Q_{\mathcal{C}}$, where $Q_{\mathcal{C}}$ is some distribution
over $\mathcal{C}$. This case represents sampling bias without a guiding
space. In the next section we describe a set of categories of more interesting
guiding spaces, and how past works fit into these categories.

##  III Analysis of previous work

We separate guiding space methods into three main categories: robot
modification, environment modification and experience based guidance. We find
these subcategories natural and comprehensive, as the entire motion planning
problem is encapsulated in the structure of the configuration space, which can
be learned from experience, or is induced by its robot and environment
constraints.

###  III-A Robot Modification

Recalling that a configuration space is the product of a robot $r$ and
environment $E$, $\mathcal{C}=(E,r)$, we define robot modification as
producing a guiding space $\mathcal{S}=(E,r^{\prime})$ for some new robot
$r^{\prime}$. In this paradigm, the projection function $f$ describes the
relationship between robot configurations, mapping configurations in the first
robot’s configuration space to configurations in the second.

Given such a mapping $f$, $h$ must compute (in a possibly implicit manner)
paths between configurations in $\mathcal{S}$, and then use those paths to
describe a sampling distribution in $\mathcal{C}$. Note that the translation
of a path back into $\mathcal{C}$ is often costly and may be one-to-many
(e.g., inverse-kinematics).

There are many natural ways one might modify a robot description to obtain a
closely related configuration space. One of the most natural projections is to
define $\mathcal{S}$ as workspace itself, ignoring the robot entirely and
treating it as a fully controllable point robot in the environment [10, 7].
Some prior works ignore kinodynamic constraints on the robot [16], thereby
simplifying the complexity of paths in the guiding space where the robot is
locally controllable. For chain-link robots, such as manipulators, a common
guiding space involves focusing on a subset of the degrees of freedom [13].
Such methods often use heuristics in deciding which subsets to consider, e.g.
focus on the first joints of a manipulator. Finally, some works attempt to
learn a subspace of the robot’s degrees of freedom, e.g. using statistical
projections such as PCA [14].

###  III-B Environment Modification

Environment modification refers to guiding spaces which map
$\mathcal{C}=(E,r)$ to $\mathcal{S}=(E^{\prime},r)$. Unlike in robot
modification, the associated projection $f$ is often simpler to compute, and
translation of paths in $\mathcal{S}$ back to $\mathcal{C}$ requires
relatively little work. In fact, in all of the papers cited below, $f$ is
nothing but the identity function, which only changes the validity of some
points in $\mathcal{C}$ to produce $\mathcal{S}$.

Narrow passages are a known bottleneck for randomized sampling algorithms, as
such, some works modify obstacles in an attempt to widen passages [2, 17].
Lazy planning methods [5, 9] also perform a type of environment modification
by ignoring constraints during initial planning, and incorporating them later
as needed. When removing constraints, paths in $\mathcal{S}$ are not
necessarily valid in $\mathcal{C}$, and thus often such works iteratively or
hierarchically compute a guiding space, use $h$ to produce samples near the
unvalidated path, and then repeat with a new guiding space informed by the
recently acquired samples.

Unlike the above works which remove environment constraints, adding
constraints to the environment is less common, but can be done to simplify
geometries and therefore collision detection [8]. Moreover adding constraints
ensures that any path in $\mathcal{S}$ is also valid in $\mathcal{C}$,
simplifying the translation of paths found in guiding space.

###  III-C Experience Based Guidance

Experience based guidance methods are characterized by their use of a dataset
of solved motion planning problems in a diverse set of environments and/or
robots. Each element of the dataset represents a guiding space, and $f$
performs a database lookup. The resulting solution must then be translated
(i.e., “fixed”) by $h$ into the current configuration space. Often such
methods assume some repetitive structure, such as a known distribution of
obstacles, and hope to capture this structure through appropriate feature
selection to determine how $f$ queries the dataset.

The most common version of experience based guidance assumes the dataset
contains a variety of environments all for the same robot. Consequently,
database queries often consist of evaluating the degree to which paths in the
dataset violate discovered constraints in the current motion planning instance
[3]. Some methods perform multiple queries, where the guiding space
effectively becomes the composite space of multiple independent motion
planning problems from the dataset. At the extreme end we have learning based
methods, which train a neural network from a dataset of experience to provide
guidance, effectively combining all past solutions through the weights of the
neurons of a neural network [4].

##  IV Evaluation metric

Often we evaluate sampling based motion planning methods using algorithm level
holistic metrics such as running time or number of samples. Minimizing such
metrics is a reasonable goal, but they can be sensitive to implementation
details, and focusing on them can obscure which aspect of a proposed
contribution is responsible for results. In the context of guided motion
planning, we now present a new method to evaluate quality of the guidance.

A guiding space biases sampling, and in doing so it provides the algorithm
with some information, reducing uncertainty with regards to where one should
explore to connect two points in the environment. The quality of this
information is exactly what we wish to capture when evaluating a guiding
space. In particular, a good guiding space should contain little extra
information that isn’t in some desirable target distribution.

######  Definition 2 (Sampling efficiency)

Given a target sampling distribution $T$ and empirical sampling distribution
$Q$, the sampling efficiency of $Q$ is defined as the information gain of
using $T$ instead of $Q$, equivalently described as the Kullback-Liebler
divergence between the two distributions,

$SE_{T}(Q)=D_{KL}(T||Q).$

The lower this quantity, the more similar the two distributions, and therefore
the more samples from $Q$ are informative about $T$. We emphasize that the
choice of target distribution is application dependent. If $h$ is used to
narrow down a set of possible steering options in a kinodynamic RRT, then $T$
may refer to the subset of steering options which take the agent closer to the
goal. If the task is not only $(s,t)$-connectivity, but also to find an
optimal path, then $T$ might refer to the set of samples on boundedly optimal
paths. In the next section we describe one possible general definition of $T$
for problems in which the task is to find any path from $s$ to $t$.

##  V Experiments

(a) DR-RRT on Simple Passage. As expected, baseline RRT struggles to find the
narrow passages whereas DR-RRT (with the help of workspace skeleton guidance)
finds it without exploring the entire region.

(b) IRC on Trap environment. In this environment, shrinking the robot makes
impassable passages seem traversable, and therefore the guidance does a poor
job by biasing sampling towards those regions.

(c) LazyPRM on Cup environment. Notice that in this environment there are
multiple homotopy classes of solutions, and that LazyPRM, while it does
oversample near the obstacles, is heavily biased along paths to the goal.

Figure 2: We show sampling distributions for our three environments and three
guiding space algorithms - (a) Simple Passage and DR-RRT, (b) Trap and IRC,
(c) Cup and LazyPRM. The sampling distributions in each figure correspond to
an average over 15 random seeds, and are displayed as a discretized grid for
visual clarity, where the size of each circle corresponds to the number of
samples in that grid cell. In red we show the approximate distribution of the
target path $T_{P}^{\delta}$. In blue are the set of samples on the tree
resulting from guided samples. In purple are the set of expansion samples,
i.e., the samples in the environment towards which the tree is steered.
Finally, in green are the samples of a baseline RRT.

Given a path $P$ we define a target distribution $T_{P}^{\delta}$ as a uniform
distribution over points at most a distance $\delta$ from the path,
$T_{P}^{\delta}=U(\\{x\mid d(x,P)<\delta\\})$. This represents the optimal
sampling distribution for discovering the path $P$. Let $Q$ be the sampling
distribution induced by a guiding space, then the guiding space sampling
efficiency is
$SE_{T_{P}^{\delta}}(Q)=D_{KL}(T_{P}^{\delta}||Q)=\mathbb{E}_{T_{P}^{\delta}}(\frac{\log
T_{P}^{\delta}}{\log Q})$.

We evaluate the sampling efficiency of four methods on three environments,
designed to highlight the strengths and weaknesses of the guidance provided by
each. Dynamic Region-biased RRT (DR-RRT) [7] grows an RRT while constraining
sampling around a topological skeleton of the workspace environment. LazyPRM
[5] does not perform collision detection while extending the edges of the
tree, and rather discards invalid edges when later evaluating paths. Iterative
Relaxation of Constraints (IRC) [2] finds a path for a shrunken version of the
robot, effectively widening narrow passages, then uses this path as guidance
for the full-size robot. RRT [12] is used as a baseline which uses no
guidance. All methods were implemented in C++ using the Parasol Planning
Library.

All scenarios consider a 3 degree of freedom (2 translational, one rotational)
robot with dimensions 0.2x0.6 in a 10x10 2D environment. Simple Passage (Fig.
2(a)) is composed of a narrow passage (width 0.5) that the robot must pass
through in a lengthwise orientation to reach the goal. Trap (Fig. 2(b))
includes several false passages that the robot may attempt to pass through
before finding the feasible passage to the goal. Cup (Fig. 2(c)) features a
large obstacle obstructing a direct path to the goal. In all cases we set
$\delta=0.5$, corresponding to the RRT maximum steering distance, meaning the
maximum distance a new sample is extended from the tree. We make this choice
of $\delta$ because it relates to the natural density of samples in the
environment, though we note there are other reasonable choices, such as the
maximum clearance of $P$.

We report results in Table I, where for each combination of algorithm and
environment we report the KL-divergence derived sampling efficiency of the
algorithm relative to the target distribution $T_{P}^{\delta}$ for the
resulting $(s,t)$-path $P$. Notice that guidance is not always beneficial: the
environment Trap was designed as an adversarial example for methods like DR-
RRT and IRC, and indeed they perform similarly or worse than baseline RRT in
this environment. While Cup was designed to hinder LazyPRM, it seems that lazy
planning does quite well under our metric.

| Simple Passage | Trap | Cup
---|---|---|---
RRT |  | 32.147
---
18.671
| 9.589
---
7.547
| 8.539
---
5.246
LazyPRM |  | 11.395
---
NA
| 14.869
---
NA
| 6.992
---
NA
DR-RRT |  | 6.115
---
19.845
| 38.759
---
57.244
| 5.834
---
18.176
IRC |  | 13.797
---
19.447
| 4.845
---
21.612
| 3.829
---
9.443
TABLE I: We report the KL-divergence values $SE_{T}(Q)$, where
$T=T_{P}^{\delta}$, for final path $P$ found by the algorithm, and $Q$ is the
distribution produced by the algorithm in the same row. In each cell the upper
value represents the samples on the final RRT tree, and the lower value
represents the samples used to guide the expansion of nodes in the tree.

##  VI Discussion

In this work we introduced the concept of a guiding space for motion planning.
This definition captures the common paradigm in which one solves “simpler”
versions of motion planning instances in order to get guidance in the form of
biased planning for an original motion planning problem.

Our characterization is useful because it immediately follows that one can
evaluate quality of guidance separately from implementation dependent metrics
such as overall algorithm running time. Similarly, the metric we propose for
evaluating a guiding space isolates the _information_ contained within it
regarding the underlying exploration task, rather than how that information is
used. A better understanding of what information is captured by a guiding
space can consequently inform how and when we use it.

As the complexity of motion planning algorithms increases, and as black-box
experience based methods become ubiquitous, it is especially important to have
evaluation metrics that are informative regardless of lower level details.
Simultaneously, it is crucial to recognize which methods are indeed
comparable. The framework of guiding spaces demonstrates that a large class of
motion planning algorithms are more similar than they first appear.

## References

  * [1] Jérome Barraquand and Pierre Ferbach.  Motion planning with uncertainty: The information space approach.  In Proceedings of 1995 IEEE International Conference on Robotics and Automation, volume 2, pages 1341–1348. IEEE, 1995.
  * [2] O. Burçhan Bayazit, Dawen Xie, and Nancy M. Amato.  Iterative relaxation of constraints: a framework for improving automated motion planning.  In 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2005, pages 3433–3440. IEEE, 2005.  doi:10.1109/IROS.2005.1545045.
  * [3] Dmitry Berenson, Pieter Abbeel, and Ken Goldberg.  A robot path planning framework that learns from experience.  In 2012 IEEE International Conference on Robotics and Automation, pages 3671–3678. IEEE, 2012.
  * [4] Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer.  Learning heuristic search via imitation.  In Conference on Robot Learning, pages 271–280. PMLR, 2017.
  * [5] Robert Bohlin and Lydia E. Kavraki.  Path planning using lazy PRM.  In International Conference on Robotics and Automation, ICRA, pages 521–528. IEEE, 2000.  doi:10.1109/ROBOT.2000.844107.
  * [6] Brendan Burns and Oliver Brock.  Information theoretic construction of probabilistic roadmaps.  In Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003)(Cat. No. 03CH37453), volume 1, pages 650–655. IEEE, 2003.
  * [7] Jory Denny, Read Sandström, Andrew Bregger, and Nancy M. Amato.  Dynamic region-biased rapidly-exploring random trees.  In Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics, WAFR 2016,, volume 13 of Springer Proceedings in Advanced Robotics, pages 640–655. Springer, 2016.  doi:10.1007/978-3-030-43089-4\\_41.
  * [8] Mukulika Ghosh, Shawna L. Thomas, Marco Morales, Samuel Rodríguez, and Nancy M. Amato.  Motion planning using hierarchical aggregation of workspace obstacles.  In 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5716–5721. IEEE, 2016.  doi:10.1109/IROS.2016.7759841.
  * [9] Kris Hauser.  Lazy collision checking in asymptotically-optimal motion planning.  In IEEE International Conference on Robotics and Automation, ICRA 2015, Seattle, WA, USA, 26-30 May, 2015, pages 2951–2957. IEEE, 2015\.  doi:10.1109/ICRA.2015.7139603.
  * [10] Christopher Holleman and Lydia E Kavraki.  A framework for using the workspace medial axis in prm planners.  In IEEE International Conference on Robotics and Automation, volume 2, pages 1408–1413. IEEE, 2000.
  * [11] Lydia E. Kavraki, Petr Svestka, Jean-Claude Latombe, and Mark H. Overmars.  Probabilistic roadmaps for path planning in high-dimensional configuration spaces.  IEEE Trans. Robotics Autom., 12(4):566–580, 1996.  doi:10.1109/70.508439.
  * [12] Steven M LaValle et al.  Rapidly-exploring random trees: A new tool for path planning.  1998\.
  * [13] Tomas Lozano-Perez.  A simple motion-planning algorithm for general robot manipulators.  IEEE Journal on Robotics and Automation, 3(3):224–238, 1987.
  * [14] Arthur Mahoney, Joshua Bross, and David Johnson.  Deformable robot motion planning in a reduced-dimension configuration space.  In IEEE International Conference on Robotics and Automation, ICRA 2010, pages 5133–5138. IEEE, 2010.  doi:10.1109/ROBOT.2010.5509649.
  * [15] Pearce Morales and Amato.  Metrics for analyzing the evolution of c-space models.  In IEEE International Conference on Robotics and Automation, 2006, pages 1268–1273. IEEE, 2006.
  * [16] Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi.  Discrete search leading continuous exploration for kinodynamic motion planning.  In Robotics: Science and Systems III, 2007. The MIT Press, 2007\.  URL: http://www.roboticsproceedings.org/rss03/p40.html, doi:10.15607/RSS.2007.III.040.
  * [17] Vojtech Vonásek, Robert Penicka, and Barbora Kozlíková.  Computing multiple guiding paths for sampling-based motion planning.  In 19th International Conference on Advanced Robotics, ICAR 2019, pages 374–381. IEEE, 2019.  doi:10.1109/ICAR46387.2019.8981589.