R Pflieger
email: rachel.pflieger@cea.fr

E Fayard

C Noel

S I Nikitenko

T Belmonte

Molecular emissions in sonoluminescence spectra of water sonicated under Ar-based gas mixtures

Keywords:

Sonoluminescence (SL) spectroscopy is one of the very few ways to study the plasma formed in solutions submitted to ultrasound. Unfortunately, up to now only very limited emission bands were reported in SL spectra of aqueous solutions, moreover broad and badly resolved. It is shown here that by adding some N 2 and/or CO 2 in Ar, new molecular emissions (CN, N 2 and CO) can be observed and that for some of them rovibronic temperatures can be derived. The paramount importance of Stark broadening in these emissions is underlined, together with the need for data on Stark parameters for molecular emissions.

Introduction

When a liquid is irradiated by ultrasounds (US) emitted at a frequency set in the range 20 kHz-1 MHz, a particular chemical activity is observed, called sonochemistry. Its origin is acoustic cavitation: nucleation, growth and violent collapse of microbubbles containing dissolved gases and vapour of the bulk liquid. The formation of a plasma in cavitation bubbles at collapse is now widely admitted [1] even though the underlying mechanism remains unclear. Moreover characterization of this plasma is not straightforward due to its small size (< 1 µm), its short lifespan (< 1 ns) and the stochastic (non-predictable) nature of its apparition. Two main directions can be followed to study it: monitoring of its chemical activity and emission spectroscopy of its sonoluminescence (SL, the light emitted by the sonochemical plasma). Yet, and despite the obvious qualities of water as a solvent, relatively few atomic and molecular emissions have been reported in SL spectra of aqueous solutions and limited information about the plasma characteristics could be derived from them.

Reported molecular emissions are those from OH [2], C 2 [3] and NH [4] radicals and from non-volatile solutes such as alkali metals [5], lanthanide Ln(III) ions [6] and uranyl UO 2 2+ ions [7]. Different excitation mechanisms do exist: excitation by the photons of sonoluminescence (sonophotoluminescence) of ions in solution (e.g. Ce 3+ [8] or UO 2 2+ [7]), collisional excitation at the bubble interface [7] or formation in the intra-bubble plasma [9]. The latter case being common, these emissions have been used to characterize the formed plasma or more generally the conditions reached at collapse.

For instance, emissions from alkali were the focus of various studies aiming at determining the maximum pressure reached in cavitation bubbles. The made assumption was that pressure (or more exactly the intra-bubble density) was the main parameter affecting the line shift and broadening of the emissions. measured Rb resonance line shifts in sonoluminescence of RbCl aqueous solutions sonicated at 20 kHz under Ar or Kr, compared them with tabulated ones vs. relative density and deduced a relative density of 18 ± 2. Similar results were obtained in silicon oil with the same approach [10]. On the other hand, relative densities derived from line broadening were much higher: 36-50 at 460 kHz under Ar [11], 59.5 at 138 kHz under Ar [12], corresponding to 885 bar if a temperature of 4300 K is considered or 800-1200 bar at 22 and 44 kHz under Ar [13]. The discrepancy in the values obtained with these two approaches was attributed to the nonnegligible contribution of Stark effects in both broadening and shift [4b].

Rovibronic temperatures of excited species, obtained from simulation of the SL spectra, were also used to estimate the peak temperature reached at collapse. In early works, unicity of the temperature was assumed. Didenko et al. [3a] fitted C 2 Swan (d 3 Π ga 3 Π u ) bands in the SL spectra of an aqueous 10 -3 M benzene solution sonicated at 20 kHz under Ar and obtained a temperature of 4300 ± 200 K. More recently, a study [3b] at different ultrasonic frequencies of Swan bands in SL spectra of aqueous tert-butanol solutions under Ar showed the necessity of considering the non-equality of the vibrational T v and rotational T r temperatures (T v > T r ). Temperatures ( ± 1000 K) estimated in the tert-butanol concentration range where the intensity of Swan bands was highest were e.g. T v = 6300 K and T r = 4800 K at 20 kHz and T v = 8000 K and T r = 4000 K at 362 kHz. Similar temperatures and the same trend of an increase in vibrational temperatures at high US frequency were obtained from fits of OH (A 2 Σ + -X 2 Π) and NH (A 3 Π -X 3 Σ -) emissions in SL spectra of 0.1 M ammonia solutions under Ar: for OH T v = 9000 ± 1000 K and T r = 5000 ± 500 K at 20 kHz, and T v = 13000 ± 2000 K and T r = 6000 ± 1000 K at 359 kHz, for NH T v = 7000 ± 1000 K and T r = 4000 ± 500 K at 20 kHz, and T v = 10000 ± 1000 K and T r = 2200 ± 500 K at 359 kHz.

The comparison of these values shows a large variation. Thus, the need for information on the plasma formed in cavitation bubbles remains essential and it is important to gain a better understanding of mechanisms controlling molecular emissions produced in known conditions and in systems as simple as possible. The present work focuses on high-frequency (362 kHz) SL spectra of water saturated with gas mixtures in Ar. The added gases and their concentrations were beforehand optimised to allow the observation of some new molecular emissions (CN, CO) in SL without decreasing much the SL intensity, and of already reported ones (OH, NH, C 2 ). Rovibronic temperatures and broadening parameter are determined and compared.

Experimental methods

For all experiments, 250 mL of deionized water (Milli-Q 18.2 MΩ cm) were placed in a thermostated glass reactor equipped with a 362-kHz transducer (ELAC Nautik, 25 cm 2 ) at its bottom. The absorbed acoustic power was determined calorimetrically (P ac = 43 W). The solution was submitted to a continuous gas flow (82 mL/min) of Ar or mixtures of N 2 (5%) and/or CO 2 (0.5%) in Ar (all gases with a purity > 99.999%, and provided by Air Liquide), starting half an hour before the experiment and maintained during the ultrasonic treatment.

Emission spectra of sonoluminescence were collected through a flat quartz window mounted on the sonoreactor and recorded in the spectral range 250-650 nm by means of SP 2356i Roper Scientific spectrometer (gratings 150blz500, 600blz300 and 1200blz300; 50 µm slit) coupled with a CCD camera that is equipped with UV coating (SPEC10-100BR Roper Scientific) cooled by liquid nitrogen. Spectral calibration was performed using a Hg(Ar) pen-ray lamp (LSP035, LOT-Oriel). The spectra acquisition was started after reaching a steady-state temperature. For each experiment, at least ten 300-s (150blz500 grating), respectively 600-s (600blz300 and 1200blz300 gratings), spectra were averaged and corrected for the background noise and for the quantum efficiencies of gratings and CCD.

Molecular emissions were fitted using Specair [14] software after removal of a linear baseline. Computation parameters were the vibrational and rotational temperatures (T v and T r ) of the considered species, the gas temperature, taken equal to T r , and the pressure p. Instrumental broadening was taken into account by convoluting calculated spectra with an experimental slit function. Due to the relatively high signal scattering, the low spectral resolution and the strong broadening of the emissions, an automatic fitting was not possible and the computation parameters were fitted manually in a row to reproduce the relative intensities of the different rovibronic transitions (T v , T r ) and the width of the peaks (p).

Gases formed during the sonolysis were measured online by mass spectrometry (Prima BT, Thermo Fischer Scientific). Monitored masses are given in Table 1. The fragment N (m/z = 14) was recorded to discriminate CO from N 2 (m/z = 28). MS analysis was started at the same time as pre-saturation of the solution, i.e. at least half an hour before the beginning of sonication, to record a baseline for each monitored species. In the particular case of CO, this baseline includes the ion intensities of N 2 and of the fragment CO of CO 2 . The increase in ion intensity of m/z = 28 during the sonolysis is due to CO gas and comparison of the ion intensities during sonolysis and of the baseline allows to quantify its amount.

Results & discussion

Formed gaseous products

Table 2 summarizes the chemical yields of the observed gaseous products of the sonolysis for the various gas mixtures. Hydrogen arises from the dissociation of water molecules in cavitation bubbles at collapse and subsequent recombination of radicals (where))) stands for a reaction induced by ultrasound):

H 2 O → ))) → H + %OH (1)
H + H → H 2 (2)

%OH + %OH → H 2 O 2 (3) H + %OH → H 2 O (4)
As soon as some amount of molecular gas is added in Ar, the H 2 yield decreases. This effect can be partly attributed to the less efficient energy concentration at collapse [START_REF] Young | Sonoluminescence[END_REF] and the additional losses in energy due to higher thermal conductivity of molecules, vibrational and rotational excitations and chemical reactions, translating into a less energetic plasma, but also to additional reactions consuming H radicals and/or H 2 molecules. It is known [4a,16] that the following reactions involving nitrogen and hydrogen take place in cavitation bubbles during the high-frequency sonolysis of water saturated with Ar-N 2 , leading to a decrease in H 2 formation yield:

N 2 → ))) → 2 N (5) N + H → NH (6) N + H 2 → NH + H (7)
The reduction in H 2 yield in the presence of CO 2 may be attributed to the reactions of CO 2 with H atoms [17]:

CO 2 + H → ))) → CO + %OH (8) CO 2 + H → ))) → %COOH (9)
The subsequent reaction of this latter radical with H atoms leads to the formation of formic acid, as previously reported by Henglein [17b] who showed that the main product of the 300-kHz sonolysis of water presaturated with Ar-CO 2 mixtures was carbon monoxide, with some amount of formic acid. Reaction (8) would also explain the observed formation of CO in the sonolysis of water saturated with Ar-0.5%CO 2 and the concomitant similar decrease in CO 2 ion intensity (of 1.4 ± 0.6 µmol/kJ). A second reaction can also lead to CO formation [17b]:

CO 2 → ))) → CO + O (10)
Adding conjointly 0.5% CO 2 and 5% N 2 in Ar leads to the disappearance of CO in the outlet gas, which can be traced back to the reaction [17a] of CO with N 2 :

N 2 + CO → ))) → CN + NO (11)
Reaction (11) would also account for the lesser decrease in H 2 yield with this ternary gas mixture compared to the binary ones Ar-5%N 2 and Ar-0.5%CO 2 , less CO 2 and N 2 molecules being available for quenching H atoms.

Observed molecular emissions in sonoluminescence emission spectra

Fig. 1 presents the UV parts of SL spectra of water sonicated at 362 kHz under Ar-5%N 2 , Ar-0.5%CO 2 and Ar-0.5%CO 2 -5%N 2 gas flows, and Fig. 2 their visible parts.

Like the usually reported SL spectra of water under Ar, they show an intense continuum spanning from the UV to the near IR and the emission from excited OH radicals (OH (A-X)). The latter arise from the dissociation of water molecules in cavitation bubbles at collapse (reaction ( 1)). When the saturating gas is Ar-5%N 2 , a molecular emission is present around 337 nm that is assigned to NH (A-X) [4a]. A probable mechanism of formation of this excited species is given by reactions ( 5)-( 7).

The sonolysis of water in the presence of Ar-0.5%CO 2 gas mixture leads to a complex SL spectrum. A tiny peak appears near 386 nm and is attributed to CN violet [START_REF] Pearse | The Identification of Molecular Spectra[END_REF]; indeed, CN can be formed in the presence of air traces by reaction (11) [17a].

Besides, the maxima of C 2 Swan bands are recognizable but superimpose with a broad not-well-defined emission, or a sum of emissions, likely from CO (possibly CO (X-X) [START_REF] Pearse | The Identification of Molecular Spectra[END_REF] (Fig. 1SI), CO (C-A) and CO (da) [START_REF] Pearse | The Identification of Molecular Spectra[END_REF]). This hypothesis on the nature of this emission is supported by the presence of CO in the outlet gas (Table 2). The ultrasonically driven formation of C 2 excited species in the presence of CO gas was recently [START_REF] Navarro | [END_REF] reported and explained by CO disproportionation followed by the recombination of carbon atoms and/or formation and subsequent dis-

sociation of C 2 O molecules [20]: CO → ))) → CO 2 + C (12) C + C + M → ))) → C 2 + M (13) C + CO + M → ))) → C 2 O + M (14) C 2 O + C → ))) → C 2 + CO (15)
Adding conjointly 0.5% CO 2 and 5% N 2 in Ar leads to the observation of OH (A-X), NH (A-X), CN violet (confirming the nature of the emission at 386 nm) and C 2 Swan bands. In this gas mixture, CN formation can also be attributed to following reaction [21]:

C 2 + N 2 → 2 CN ( 16
)
The absence of CO emission in the SL spectra of water saturated with Ar-0.5%CO 2 -5%N 2 correlates with the absence of CO in the outlet gas (Table 2).

Derived rovibronic temperatures

Fig. 3 compares the OH (A-X) emissions observed with the different gas mixtures in Ar (after subtraction of a baseline due to the SL continuum). They are very similar, except for two zones (indicated by arrows) where the intensity is higher when N 2 is present in the gas: Fig. 1. UV part of SL spectra of water under Ar-5%N 2 , Ar-0.5%CO 2 and Ar-0.5%CO 2 -5%N 2 (362 kHz, 43 W, 14 °C, 600blz300 grating). Fig. 2. Visible part of SL spectra of water under Ar-5%N 2 , Ar-0.5%CO 2 and Ar-0.5%CO 2 -5%N 2 (362 kHz, 43 W, 14 °C, 150blz500 grating). around 308 nm and around 315 nm. The former may be due to NH (c-a) and/or to N 2 (C-B) and the latter to N 2 (C-B) emissions (Fig. 2SI in Supporting Information), superimposed on that of OH. Thus simulation was performed (using Specair software [14]) on OH (A-X) emission under Ar (Fig. 3SI in Supporting Information). It can be reasonably fitted with T v = 9000 K ( ± 1000 K), T r = 6500 K ( ± 1000 K) and an effective pressure of 1000 bar ( ± 300 bar).

The simulation of NH (A-X) in the presence of Ar-5%N 2 (Fig. 4SI in Supporting Information) leads to T v = 10000 K ( ± 1000 K), T r = 10000 K ( ± 1000 K) and an effective pressure of 4000 bar ( ± 500 bar). The bulge around 340-345 nm is of unknown origin. Interestingly, when N 2 content in Ar is increased, NH (A-X) emission cannot be fitted anymore, which is attributed to the presence of a nonnegligible N 2 (C-B) emission (Fig. 2SI in Supporting Information).

Due to the presence of a strong CO emission in the SL spectra of water saturated with Ar-0.5%CO 2 , the simulation of C 2 Swan bands could be performed only for the gas mixture Ar-5%N 2 -0.5%CO 2 for which no CO emission was noted. It was done focusing on the Δν = 0 and Δν = 1 bands (Fig. 5SI in Supporting Information). Derived rovibronic temperatures are T v = 22000 K ( ± 1000 K), T r = 5000 K ( ± 1000 K) and an effective pressure of 6000 bar ( ± 1000 bar).

In the presence of the gas mixture Ar-5%N 2 -0.5%CO 2 an intense CN (B-X) molecular emission is also observed that can be simulated with T v = 12500 K ( ± 2500 K), T r = 10000 K ( ± 1000 K) and an effective pressure of the order of 10000 bar (Fig. 6SI in Supporting Information).

Table 3 summarizes all derived rovibronic temperatures and effective pressures in the form vibrational temperature T v /rotational temperature T r /effective pressure.

The very large effective pressure values obtained, in particular from CN emission, and the fact that they considerably differ depending on which emitting species is considered, undoubtedly confirm that pressure cannot be considered as the main broadening parameter, as previously discussed [4b] and that Stark broadening should be taken into account. Unfortunately however, data on Stark broadening of molecular emissions are particularly scarce, which considerably limits the information that can be derived from the measured broadenings.

Comparison of the present OH rovibronic temperatures with previously [2d] reported ones for the sonication of water at 362 kHz under Ar shows a good agreement for both T v (9000 vs. 8000 K) and T r (6500 vs. 5250 K), whereby the difference may be due to the uncertainty in the baseline definition. Similarly, a difference in the continuum shape in the wavelength range of OH emission may also account for the higher T v reported for OH in a 0.1 M ammonia solution [4b] (13000 K).

In the presence of Ar -5% N 2 two molecular emissions are observed, the vibrational temperatures of which are fairly close, while NH rotational temperature is higher than that of OH. Interestingly, it is also much higher than the rotational temperature derived from NH emission in the sonolysis of an ammonia solution [4b] (2200 K). Considering the different reaction pathways leading to NH formation in both cases (sonolysis of NH 3 molecule vs. reactions ( 1) & ( 5)-( 7)) it is conceivable that the formation of NH from H and N radicals necessitates several steps compared to the direct sonolysis of NH 3 or H 2 O molecules. Then, the chemical pathway leading to emission likely affects the rotational distribution of the emitting states, leading to the observed discrepancy between measurements.

A similar disagreement is observed between the derived rovibronic temperatures for the gas mixture Ar -0.5% CO 2 -5% N 2 . The several steps leading to CN formation may also lead to specific rotational populations and rotational temperature that do not match with the gas temperature, due to the extremely short lifetime of the formed plasma.

For the same reason, vibrational temperatures might be different as well.

Conclusion

Although it was long considered that SL spectra of aqueous solutions were relatively featureless compared to those of exotic liquids (e.g. concentrated sulfuric acid), thus strongly limiting the possibility to study the formed plasma, this study shows that besides usual OH and C 2 emissions and the recently reported NH one, at least three more molecular emissions can be observed in high-frequency SL spectra of aqueous solutions, namely CN, N 2 and CO. This finding enriches the "toolbox" available to characterize the sonochemical plasma, the conditions reached at collapse of cavitation bubbles and the chemical reactions taking place in bubble cores.

Unfortunately, not all these emissions can be fitted yet: CO blends into the continuum and N 2 superimposes over the strong OH emission. Moreover, their presence perturbs the fitting of the other better-defined emissions, like C 2 or OH.

To go further in the exploitation of these emissions, there is a strong need for tabulated data on Stark parameters for molecular emissions. Once available, the present data might allow estimation of the reached pressure and of plasma characteristics such as electron density and temperature. The optimised three-component gas mixture is in this purpose of particular interest since the corresponding SL spectra present three different usable molecular emissions.

Fig. 3 .

 3 Fig. 3. Comparison of OH emission in SL spectra of water sparged with gas mixtures in Ar.

Table 1

 1 Masses (amu) of the gases monitored by mass spectrometry.

	m/z, amu	Species
	40	Ar
	2	H 2
	28	N 2 and/or CO
	32	O 2
	44	CO 2
	14	N

Table 2

 2 Chemical yields of the formed gaseous products, H 2 and CO.

	Saturating gas	H 2 yield, µmol/kJ ( ± 0.02)	CO yield, µmol/kJ ( ± 0.6)
	Ar	0.36	-
	Ar-5%N 2	0.27	-
	Ar-0.5%CO 2	0.09	1.7
	Ar-0.5%CO 2 -5%N 2	0.12	-

Table 3

 3 Estimated rovibronic temperatures ( ± 1000 K unless otherwise specified) and effective pressures ( ± 300 bar) by simulations with Specair software.

	Gas	OH	NH	C 2	CN
	Ar	9000 K/6500 K/1000 bar
	Ar -5% N 2		10000 K/10000 K/4000 bar
	Ar -0.5% CO 2
	Ar -0.5% CO 2 -5% N 2			22000 K/5000 K/6000 bar	10000-15000 K/10000 K/10000 bar

Acknowledgements

CNRS and in particular its Réseau des Plasmas Froids are acknowledged for supporting this work with an IPMC.

Appendix A. Supplementary data

Supplementary data to this article can be found online at https:// doi.org/10.1016/j.ultsonch.2019.104637.


Arthur Bit-Monnot
email: afbit@uniss.it

A Constraint-based Encoding for Domain-Independent Temporal Planning

We present a general constraint-based encoding for domainindependent task planning. Task planning is characterized by causal relationships expressed as conditions and effects of optional actions. Possible actions are typically represented by templates, where each template can be instantiated into a number of primitive actions. While most previous work for domain-independent task planning has focused on primitive actions in a state-oriented view, our encoding uses a fully lifted representation at the level of action templates. It follows a time-oriented view in the spirit of previous work in constraint-based scheduling. As a result, the proposed encoding is simple and compact as it grows with the number of actions in a solution plan rather than the number of possible primitive actions. When solved with an SMT solver, we show that the proposed encoding is slightly more efficient than state-of-the-art methods on temporally constrained planning benchmarks while clearly outperforming other fully constraint-based approaches.

Introduction

Task planning is a field of Artificial Intelligence concerned with finding a set of actions that would result in desirable state. Its key difficulty lies in the handling of causal relationships between a large number of potential actions. Research in the field has focused primarily on the definition of relaxations of the classical planning problem in order to define accurate heuristic functions to guide tree search algorithms. Those heuristics have proved to be highly effective for reasoning on the causal relationships that occur in task planning and have driven most research to focus on state-based heuristic search.

Despite their success in classical planning, they have proved to be difficult to extend to more expressive models including time, resources or continuous changes. This led to a renewal of interest into constraint-based models and search as a way to increase the expressiveness of domain-independent task planners [START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF][START_REF] Dvorák | Planning and Acting with Temporal and Hierarchical Decomposition Models[END_REF][START_REF] Scala | Numeric Planning with Disjunctive Global Constraints via SMT[END_REF].

In this paper, we propose an encoding for the causal relationships that are at the core of domain-independent planning. Unlike the most recent work proposing compilations of domain-independent temporal planning to Constraint Satisfaction Problems (CSPs) which follow a state-oriented view [START_REF] Bryce | SMT-based Nonlinear PDDL+ Planning[END_REF][START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF], we use a timeoriented view inspired by the work in the field of constraint-based planning and scheduling [START_REF] Cesta | Developing an End-to-End Planning Application from a Timeline Representation Framework[END_REF][START_REF] Frank | Constraint-Based Attribute and Interval Planning[END_REF][START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF][START_REF] Laborie | Reasoning with Conditional Time-Intervals[END_REF]. The key benefit of this encoding is its simplicity and its good fit for integration into more general constraint satisfaction problems, going one step closer to bridging the gap between planning and scheduling.

We start by giving a background on task planning and the representation of temporal planning problems as chronicles. We then show how such planning problems can be concisely encoded into CSPs, using a fully lifted representation based on chronicles. The resulting encoding is leveraged in a domain-independent planner for ANML, an expressive language for the specification of planning problems [START_REF] Smith | The ANML Language[END_REF]. Using an off-the-shelf SMT solver as a backend, the planner is shown to outperform state-of-the-art temporal planners on temporally constrained planning benchmarks. Last, we discuss the related work in constraint-based planning and scheduling, especially analyzing other domain-independent planners that rely on SMT.

Background

A Distilled Planning Problem

In its simplest formulation, a planning problem is composed of (i) an initial state, (ii) a goal state and (iii) a set of primitive actions.

A state is an assignment to a set of state variables, each denoting one particular feature of the environment (e.g. the location of a truck). We denote as S the set of possible states.

A primitive action a is composed of:

a set of conditions over state variables. It characterizes the set of states S app a ⊆ S in which the action is applicable. a set of effects from which one can construct a state transition function f a : S app a → S

Given an initial state s 0 ∈ S, a goal state s g ∈ S and a set of primitive actions, a plan is a sequence of primitive actions a 1 , . . . , a n . For a given plan, one can build the resulting sequence of states s 1 , . . . , s n such that s i = f ai (s i-1 ). A plan is a solution to a planning problem if all actions are applicable in the previous state (∀ i∈ [1,n] s i-1 ∈ S app ai ) and the final state is the goal state (s n = s g ). This formulation of planning as a state transition system has been at the core of domain-independent planning research, and of PDDL, the de-facto standard language for describing planning problems [START_REF] Mcdermott | PDDL: the Planning Domain Definition Language[END_REF]. Several extensions have been devised for extending the expressiveness of PDDL, most notably to handle a limited form of temporal constructs and numeric variables [START_REF] Edelkamp | PDDL2.2: The Language for the Classical Part of the 4th International Planning Competition[END_REF][START_REF] Fox | PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains[END_REF]. Nevertheless, the focus of the language and the benchmarks of the International Planning Competition remains heavily focused on handling the causal relationships derived from the conditions and effects of primitive actions.

Temporal Planning as Chronicles

An other notable representation for planning follows a time-oriented view as opposed to the state-oriented view above. We here detail the representation of planning problems as chronicles [START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF], which was first introduced in the IxTeT planner [START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF]. This representation avoids direct references to states and instead describes the evolution of the environment through temporally qualified assertions over the state variables.

A type is defined by a set of values. A type is either (i) a set of domain constants (e.g. the type Truck = { R 1 , R 2 } defines two truck objects R 1 and R 2 in the planning problem), (ii) a discrete or continuous set of numeric values, or (iii) a representation of temporal instants, for which we typically consider the set of natural numbers. 1A (decision) variable is associated with a type that defines its initial domain. We denote as timepoints the subset of variables that represent a temporal instant.

A state variable denotes the evolution of a particular state feature over time. A state variable is typically parameterized by one or multiple domain objects to represent the state of a particular object in a planning problem. For instance loc(R 1 ) denotes the evolution of the location of the truck R 1 over time. A state variable expression can be parameterized by decision variables, in which case the actual state variable it refers to depends on the value taken by its parameters, e.g., loc(r) will refer to loc(R 1 ) or loc(R 2 ) depending on the value taken by the variable r of type Truck .

Chronicle In line with previous work in temporal planning, we represent the core constructs of a planning problem with chronicles [START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF]. A chronicle is a tuple (V, X, C, E) where: it has an undefined value and cannot be further constrained.

-V is a set of variables. -X is a set of constraints over the variables in V . -C is a set of conditions
A chronicle is thus a constraint satisfaction problem (V, X) extended with additional constructs to represent the conditions and effects that are at the core of planning problems. 2Action Chronicle A planning problem defines a set of action templates T where each action template can be instantiated into chronicles. We denote as C i a a chronicle instantiated from an action template a ∈ T , where i distinguishes chronicles instantiated from the same template.

Considering an action template Go ∈ T that moves a truck r from a location s to a location e , its instantiation as a chronicle C Go could have the following components:

-V = { r, s , e ,

Initial Chronicle

We distinguish action chronicles from the initial chronicle C 0 that represents the initial state and the planning objectives. In addition, the initial chronicle might provide a partial view of the expected state evolution, e.g., that a cargo ship (outside the control of the planner) will arrive at 5pm. Specifying a problem where the truck R 1 is initially in location L 0 and must be in location L 2 or L 3 before time 100 is encoded with the chronicle C 0 = (V 0 , X 0 , C 0 , E 0 ) where:

-V 0 = { t, } -X 0 = { t < 100, = L 2 ∨ = L 3 }, constraints restricting the solution set. -C 0 = { [t, t] loc(R 1 ) = }, condition specifying the goal. -E 0 = { [0, 0] loc(R 1 ) ← L 0 }, effect defining the initial state: the truck R 1 is
in L 0 at the initial time.

A planning problem can be represented as a pair (C 0 , T ) where C 0 defines the initial state and objectives and T is a set of action templates that can be instantiated into action chronicles.

Planning as a Constraint Satisfaction Problem

One of the difficulty that arises in planning is that the number of actions is not known beforehand nor can it be given tight bounds. As a first step, we consider a bounded planning problem composed of an initial chronicle C 0 and finite set of optional action chronicles AC. An optional action chronicle C i a ∈ AC is a action chronicle associated to a boolean variable o i a that is true ( ) if C i a is part of the solution plan and false (⊥) otherwise.

Consider the planning problem of moving the truck R to either L2 or L3 from the previous section. Considering a set of optional action chronicles { C 1 Go , C 2 Go }, we can represent all the plans composed of 0, 1 or 2 instances of the Go action. The actual plan depends on the instantiation of the decision variables. One could build a satisfying solution from the partial assignment

{ o 1 Go ← , r 1 ← R 1 , 1 s ← L 0 , 1 e ← L 2 , o 2
Go ← ⊥ } where r 1 , 1 s and 2 e are the eponymous variables in C 1

Go . Such an assignment states that only the first action would be present and would move the truck R 1 from L 0 to L 2 . Note that this only partially defines the solution plan and other assignments would need to be made, notably to the action timepoints and to the variables of C 0 .

A bounded planning problem Π is the set of chronicles {C 0 }∪AC where each

C ∈ Π is associated to a boolean variable present(C) that is: o i a if C is an action chronicle C i a ∈ AC; or if C = C 0 .
This planning problem is called bounded as there is an upper limit on the number of actions in a solution plan defined by the number of action chronicles.

Building Blocks

Given a bounded planning problem Π, we now describe the core structures for compiling it to a constraint satisfaction problem.

Condition Token

Given

a chronicle C ∈ Π, each condition [s, e] sv (p 1 , . . . , p n ) = v in C is associated to a condition token: present(C) : [s, e] sv (p 1 , . . . , p n ) = v This token represents that, if C is part of the solution (present(C) = ), then the state variable sv (p 1 , . . . , p n ) must have the value v over the temporal interval [s, e].
We denote as C Π the set of condition tokens in Π.

Effect Token Given a chronicle C ∈ Π, we associate to each effect [s, e] sv (p 1 , . . . , p n ) ← v in C an effect token:

present(C) : [s, e, t] sv (p 1 , . . . , p n ) ← v
where t is a new timepoint variable. This token states that, if C is part of the solution (present(C) = ), then the state variable sv (p 1 , . . . , p n ) is undefined over the temporal interval ]s, e[ and has the value v over the temporal interval [e, t]. The introduction of the new decision variable t allows us to encode a minimal time for which the effect will persist. We denote as E Π the set of effect tokens in Π.

Characteristics of Tokens Effect tokens here represent the evolution of state variables over time. Each (present) effect token imposes a new value to its state variable. This value is constrained to be maintained on a given temporal interval. Effect tokens thus encode the state evolution. On the other hand, condition tokens place constraints on the state evolution by requesting a given state variable to have a given value over a temporal interval. Intuitively, such a condition is achieved if there is a corresponding effect token that imposes the appropriate value.

For a given token, the variables involved allow four degrees of freedom on which a solver might play to build a consistent plan:

the presence of the token (variable present(•)).

the temporal interval on which it applies, (variables s, e and t).

the state variable on which it applies (variables p 1 , . . . , p n ).

the value taken by the state variable (variable v).

Those variables are typically shared with other tokens from the same action chronicle. These interdependencies between tokens are at the core of the hardness of planning as having an effect token to establish a condition requires the presence of all other tokens from the same chronicle. This in turn requires new conditions to be established as well as new effect tokens that might interact with the existing ones.

Constraints for Plan Consistency

Given a bounded planning problem Π, we define a set of constraints that encode the requirements for a plan to be consistent.

Coherence Constraint State variables are similar to unary resources in that they can only take a single value at a given time. Any two distinct effect tokens α and α in E Π must be coherent: they may not concurrently impose a value to the same state variable.

Given α = o : [s, e, t] sv (p 1 , . . . , p n ) ← v ∈ E Π α = o : [s , e , t ] sv (p 1 , . . . , p n ) ← v ∈ E Π then the constraint coherent(α, α ) is defined as: o ∧ ∧ ∧ ∧ o =⇒ t ≤ s ∨ ∨ ∨ ∨ t ≤ s ∨ ∨ ∨ ∨ p 1 = p 1 ∨ ∨ ∨ ∨ • • • ∨ ∨ ∨ ∨ p n = p n
The coherence constraint enforces that a given state variable has at most one value at any point in time. It is done by forcing two effect tokens to be non overlapping which can be enforced along three axes: presence (o), time (]s, t]) and state variable (sv (p 1 , . . . , p n )).

Support Constraint

We say that a condition token β ∈ C Π , is supported by an effect token α ∈ E Π if α establishes the value required by β and that this value persists for the duration of β.

Given β = o : [s, e] sv (p 1 , . . . , p n ) = v ∈ C Π α = o : [s , e , t ] sv (p 1 , . . . , p n ) ← v ∈ E Π then supported-by(β, α ) is defined as: o ∧ ∧ ∧ ∧ e ≤ s ∧ ∧ ∧ ∧ e ≤ t ∧ ∧ ∧ ∧ p 1 = p 1 ∧ ∧ ∧ ∧ • • • ∧ ∧ ∧ ∧ p n = p n ∧ ∧ ∧ ∧ v = v Less formally, it means that β is supported by α if (i) α is present, (ii) β is contained in the interval [e , t ]
V Π = { V | | | | (V, X, C, E) ∈ Π } ∪ { present(C) | | | | C ∈ Π } X Π = { coherent(α, α ) | | | | α, α ∈ E Π , α = α } ∪ { supported(β) | | | | β ∈ C Π } ∪ { consistent(C) | | | | C ∈ Π }

Symmetry Breaking Constraints

A given bounded planning problem Π might contain several action chronicles of the same action template, e.g., several chronicles being instantiations of the Go action template. In the current formulation, nothing distinguishes two action chronicles of the same template and any satisfying assignment can be made into a new one by exchanging the variables of the two chronicles.

Given the set of action templates T , for any action template a ∈ T , we refer to all action chronicles of the template a in Π as C 1 a , . . . , C n a , in an arbitrary order.

From this ordering, we define two symmetry breaking constraints. The first one requires that, if a given chronicle is present, then all its predecessors in the ordering are present as well:

a∈T i∈[1,n-1] present(C i+1 a ) =⇒ present(C i a )
The second one requires the ordering on chronicles to match the ordering of actions in the solution plan:

a∈T i∈[1,n-1] start(C i+1 a ) ≥ start(C i a )
where start(C) is the start timepoint of the action chronicle C.

Instantiation in a Domain-Independent Planner

We now describe how the presented encoding can be leveraged in a fully domainindependent temporal planner. We present LCP (Lifted Constraint Planner), a planner that solves ANML planning problems using an SMT solver as a backend.

Rather than providing a fully fledged temporal planner, LCP aims at validating the effectiveness of our encoding on standard temporal planning benchmarks.

The ANML Language

The Action Notation Modeling Language (ANML) is a proposal by NASA Ames Research Center to represent rich temporal planning and scheduling problems [START_REF] Smith | The ANML Language[END_REF]. ANML features a clear notion of actions with conditions and effects integrated with a rich representation of time.

Compared to the temporal variants of PDDL, the ANML language has two important features. The support of multi-valued states variables, as opposed to the boolean state variables of PDDL, allows for a more compact representation of the state. In addition, ANML supports referencing timepoints other than the start and end of an action, thus increasing the capabilities to model complex temporal actions. Temporal PDDL planning problems are usually easy to express in ANML, with some recent work to provide an automated translation [START_REF] Bernardini | Extracting Lifted Mutual Exclusion Invariants from Temporal Planning Domains[END_REF][START_REF] Bernardini | Automatic Synthesis of Temporal Invariants[END_REF].

Translation of ANML planning problems into chronicles is straightforward as all constructs we are interested in have a one to one mapping [START_REF] Bit-Monnot | Temporal and Hierarchical Models for Planning and Acting in Robotics[END_REF]. 3 We parse an ANML problem file into the initial chronicle C 0 and a set of action templates T that can be instantiated into action chronicles.

Solving with SMT

Our solving procedure works by incrementally generating bounded planning problems Π k with an increasing number of optional actions. For each problem, an SMT solver is used to either prove the consistency of Π k or the absence of a satisfying assignment. If Π k is consistent, the solution plan is extracted from the found satisfying assignment. Otherwise the process continues with the next bounded problem Π k+1 .

The overall procedure is given in Algorithm 1. The planner iteratively generates bounded planning problems of increasing depth k until a solution is found or a depth k max is reached. Given an input planning problem (C 0 , T ), we generate a bounded problem Π k using the procedure GenProblem(C 0 , T , k) as follows:

Π k = { C 0 } ∪ a∈T { C i a | | | | i ∈ [1, k] }
For a problem Π k , this formulation allows the presence of k instances of each action template a ∈ T . The CheckSMT(Π k ) function encodes Π k as a CSP using the encoding we presented. The consistency of the resulting CSP is checked with the Z3 SMT solver [START_REF] De Moura | Z3: An efficient SMT Solver[END_REF].

Algorithm 1 Planning procedure of LCP (Lifted Constraint Planner) for an input problem (C 0 , T ) and maximum depth k max .

function LCP(C0, T , kmax) k ← 0 while k ≤ kmax do Π k ← GenProblem(C0, T , k) model ← CheckSMT(Π k ) if model is a consistent model then return ExtractSolution(model ) end if k ← k + 1 end while return failure end function

Limitations

As it stands, LCP is a rather naïve instantiation of the proposed encoding into a domain-independent planner. One of the limitation is the absence of reuse of the inconsistent models of previous steps when generating a new bounded planning problem. At the very least, one could analyze the unsatisfiable core provided by SMT solvers to infer which actions must be added to the next bounded planning problem.

More importantly, the use of SMT is certainly suboptimal given the progress made in constraint-based scheduling solvers in tackling closely related problems. Indeed, solvers such as CP Optimizer provide constructs for optional temporal intervals and state functions that closely relate to the building blocks of our encoding [START_REF] Laborie | Reasoning with Conditional Time-Intervals[END_REF][START_REF] Laborie | Reasoning with Conditional Time-Intervals. Part II: An Algebraical Model for Resources[END_REF]. However, as we further discuss in section 6, there is still a mismatch between the available global constraints and the needs for domainindependent planning. In the absence of global constraints for CP solvers, SMT solvers provide a good backup solution for our encoding that features many disjunctive constraints.

LCP here simply aims at a preliminary evaluation of the proposed encoding against existing planners.

Experiments

Comparison with State of the Art Temporal Planners

We evaluate our approach against several state of the art temporal planners on benchmarks from the International Planning Competition (IPC). We focus on problems where time plays an important role in the solution: planning problems that have deadlines or time windows that constrain the occurrence time of actions in the plan. The rationale for doing so is that planning problems without such features can be solved without any explicit handling of time (with the exception of some problem with required concurrency [START_REF] Cushing | When is Temporal Planning Really Temporal?[END_REF]).

We compare ourselves to Temporal Fast Downward (TFD) [START_REF] Eyerich | Using the Context-Enhanced Additive Heuristic for Temporal and Numeric Planning[END_REF], OPTIC [START_REF] Benton | Temporal Planning with Preferences and Time-Dependent Continuous Costs[END_REF], FAPE [START_REF] Bit-Monnot | Temporal and Hierarchical Models for Planning and Acting in Robotics[END_REF][START_REF] Dvorák | Planning and Acting with Temporal and Hierarchical Decomposition Models[END_REF] and SMTPlan+ [START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF]. TFD is a forward-search state-space planner that ranked second in the last temporal track of the IPC [START_REF] Vallati | The 2014 International Planning Competition: Progress and Trends[END_REF]. Its search is based on the addition of new primitives actions at the end of an existing plan and heavily relies on heuristics for guidance. OPTIC is similar in its use of forwardsearch but uses a different heuristic and a lifted temporal representation handled in an STN. It is an improved version of POPF [START_REF] Coles | Forward-Chaining Partial-Order Planning[END_REF], runner up in the temporal track of the penultimate IPC. FAPE represents another line of temporal planners that uses a constraintbased representation. FAPE plans in the space of lifted partial plans, where each plan is composed of a set of partially instantiated actions whose variables are embedded in a CSP. Search proceeds by either imposing values on variables or extending the partial plan with additional actions, thus extending the CSP with new constraints, variables and values in previous domains. FAPE is the first planner in this line of work to show good performance in a domain-independent setting [START_REF] Bit-Monnot | Temporal and Hierarchical Models for Planning and Acting in Robotics[END_REF].

SMTPlan+ [START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF] is a recent planner that supports the full range of PDDL+ [START_REF] Fox | Modelling Mixed Discrete-Continuous Domains for Planning[END_REF] through a compilation to SMT. Unlike LCP, its encoding is state-oriented with additional constructs to support non-linear continuous change. Given SMT-Plan+'s usage of SMT to solve a constraint-based encoding, an additional, more detailed, comparison will be made in the next subsection.

We use the airport-timewindows, satellite-timewindows and pipesworlddeadlines domains from IPC4 which feature durative actions and temporal constraints on the plan in the form of deadlines and time-windows in which actions can be performed. The airport-timewindows domain focuses on planning the takeoff and landing of several planes in an airport, the movement of planes being temporally constrained by the arrival of other planes. The satellite-timewindows domain plans observations and data transmission of a fleet of satellites subject to visibility windows. The pipesworld-deadlines domain focuses on planning the transportation of products through pipes, subject to delivery deadlines. TFD, OPTIC and SMTPlan+ use the original PDDL domains while LCP and FAPE use their translation to ANML from FAPE's benchmark problems. 4As standard in the IPC, we evaluate the planners on the number of problems solved with a 30 minutes timeout. Benchmarks are run on an Intel i5-7200U @ 2.50GHz CPU with 8Gb of RAM. LCP and SMTPlan+ use Z3 [START_REF] De Moura | Z3: An efficient SMT Solver[END_REF] in version 4.6.3 as a black-box SMT solver.

Results are given in Table 1. It can be seen that, on temporally constrained problems, LCP is slightly ahead of both FAPE and OPTIC in terms of number of problems solved. TFD performs poorly on such problems while SMTPlan+ fails to solve any problem.

LCP performs best in the pipesworld-deadlines domain which is characterized by much interference between the available actions, reducing the ability to reason independently on goals. Its worst performance is on the satellite-timewindows domain whose difficulty lies in the number of mostly independent goals requiring a large number of actions. In this setting, LCP fails to prove the absence of solution before reaching the subproblem that actually contains one. The airporttimewindows domain is an intermediate between those two domains making LCP performs only slightly better than other planners. Note on expressiveness Unlike PDDL temporal planners, LCP supports rich temporal constructs, including actions with conditions and effects besides the start and end timepoints of actions. It leverages ANML's multi-valued state variables (as opposed to the boolean state variables of PDDL) to provide a more compact representation. Note that FAPE, which also uses the ANML language as input, has the same characteristics.

In addition, LCP readily supports numeric variables both as action parameters and state variables. State of the art temporal planners do not support numeric parameters due to their need to ground the problem to derive heuristics, even though some recent work was done in this direction for forward-search planners [START_REF] Savas | Planning Using Actions with Control Parameters[END_REF].

Note on performance in non-temporal domains We also tested the performance of LCP on non-temporal domains, i.e., domains where time is either absent or limited to the duration of actions and can soundly be omitted [START_REF] Cushing | When is Temporal Planning Really Temporal?[END_REF]. On the domains tested (blocks, logistics and rovers from the IPC), LCP solved around two thirds of the problems solved by FAPE, OPTIC and TFD who all had similar performance. As could be expected, LCP does not reach the performance of state of the art planners on non-temporal problems. It nevertheless showed consistent performance in its handling of causal relationships.

Comparison with SMTPlan+

Our work was motivated by the recent developments in the planning community to extend the expressiveness of task planners. Research in domain-independent planning has been mostly focused on ground state-based heuristic search. Such planners deliberately choose to cope with very large search spaces because it enables the definition of very effective heuristic functions to guide their exploration.

The will to support more realistic problems through extensions to PDDL is however problematic. Indeed extensions affect the performance of heuristics that become less informative, with dramatic effects on search performance. This state of affairs has motivated the introduction of new planners that rely on SMT solvers to deal with the most expressive extensions of PDDL. Most notably, the most effective approaches for planning with PDDL+ rely on compilations to SMT [START_REF] Bryce | SMT-based Nonlinear PDDL+ Planning[END_REF][START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF].

SMTPlan+ [START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF] appears to be the most effective of those planners. It supports planning with continuous non-linear change and processes and the authors showed that those can be efficiently accounted for in an SMT representation.

Of all the planning benchmarks we tested it on, SMTPlan+ was only able to solve the two simplest instances of the (non-temporal) blocks domain. Its performance on domain-independent temporal or non-temporal planning is thus largely below the ones of LCP and state-of-the-art planners.

SMTPlan+ uses a state-oriented representation where each state is associated to a given happening that alters the state (corresponding to the start or end of an action). Each state is represented by a set of boolean variables. To each happening is associated the choice of a primitive action that implies constraints on the happening's state variables.

To understand the implication of this representation, we compare the encoding of both LCP and SMTPlan+ on two problems of the rovers domains. The two problems mainly differ by the number of objects in the domain, with a direct impact on the number of primitive actions. The first instance (p01) has only 63 primitive actions while the second instance considered (p10) has 382. Note that these numbers are low compared to standard planning benchmarks (e.g. the most difficult problem of the rovers domain has 32,437 reachable primitive actions).

The number of disjunctive constraints (i.e. clauses in the SMT formula) as well as the number of variables is given in Table 2 for both LCP and SMT-Plan+. It can be seen that the size of the SMT formula at a given depth in SMTPlan+ is directly impacted by the number of primitive actions, making it quickly untractable even on problems of modest size. The size of the encoding grows linearly with the number of happenings (depth). On the other hand, LCP is mostly unaffected by the growth in problem size thanks to its use of partially instantiated actions. On the down side, the encoding of LCP grows quadratically with the depth. Note that, in the case of LCP, a depth of 4 means that each action template might be duplicated 4 times (in the rovers domain, which has 9 action templates, the plan at depth 4 might contain up to 36 actions). On the other hand, a durative action requires two happenings in SMTPlan+'s representation, i.e., a depth of 4 would only allow two sequenced actions.

Related Work

Encodings for Graph-Plan A historical application of CP solvers to planning has been based on the graph-plan framework [START_REF] Blum | Fast Planning through Planning Graph Analysis[END_REF]. Such planners build a synthetic data structure that captures causal relationships between primitive actions up to a given plan length. While building such a data structure can be done in polynomial time, extracting a solution (or proving its absence) is combinatorial. CP solvers have been leveraged to perform the plan extraction step in planners such as GP-CSP [START_REF] Do | Solving planning-graph by compiling it into CSP[END_REF] and CSP-PLAN [START_REF] Lopez | Generalizing graphplan by formulating planning as a CSP[END_REF]. Both planners use a grounded state-based encoding where the value of variables in each state is related to the previous state and primitive actions through a set of constraints. Despite work on improving the encoding of the CSP with table constraints [START_REF] Barták | Reformulating Constraint Models for Classical Planning[END_REF], the performance of such planners has been superseded by forward search planners.

Plan-Space and Timeline-based Planners Another line of research is the work on timeline-based planners [START_REF] Cesta | Developing an End-to-End Planning Application from a Timeline Representation Framework[END_REF][START_REF] Chien | ASPEN: Automated Planning and Scheduling for Space Mission Operations[END_REF][START_REF] Frank | Constraint-Based Attribute and Interval Planning[END_REF] and lifted plan-space planners [START_REF] Bit-Monnot | Temporal and Hierarchical Models for Planning and Acting in Robotics[END_REF][START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF]. Both kind of planners use a time-oriented representation, and the chronicle model that we use originated in lifted plan-space planners [START_REF] Ghallab | Representation and Control in IxTeT, a Temporal Planner[END_REF]. Those planners search in the space of partial plans where the current partial plan is extended with new actions during search. Key aspects of the partial plan are represented in a CSP, including the actions' parameters and timepoints. One difficulty is that the CSP is constructed online -both constraints and variables are added to the CSP -limiting the ability to use existing constraint solvers. More problematic is that the set of effects that can be used to support a given condition is not fixed a priori as new actions can be inserted in the partial plan. As a result, the equivalent of our supported-by constraints are often implemented in an ad hoc way, outside of the main constraint engine.

The internal representation of those planners is however closely related to the encoding proposed in this paper. One important difference is that plan-space planners use threats to encode the consistency between support decisions. We avoid the explicit handling of threats by the introduction of a new timepoint in effect tokens to represent the minimal persistence of an effect which is accounted for directly in the coherence constraint. This is important to limit the size of the CSP, as an explicit encoding of threats would be cubic in the number of possible actions.

The proximity with those planners might make it possible to adapt the relaxations, heuristics and propagators developed into global constraints to our setting, such as the one tailored to reason on causal relationships in EUROPA and FAPE [START_REF] Bernardini | Developing Domain-Independent Search Control for EUROPA2[END_REF][START_REF] Bit-Monnot | Delete-free Reachability Analysis for Temporal and Hierarchical Planning[END_REF].

SMT-based Planners

The development of SMT encodings for task planning in the last years has been motivated by the need to support richer planning problems, notably involving continuous change on numeric state variables in planners such as dReach [START_REF] Bryce | SMT-based Nonlinear PDDL+ Planning[END_REF] and SMTPlan+ [START_REF] Cashmore | A Compilation of the Full PDDL+ Language into SMT[END_REF]. As highlighted in subsection 5.2, it is our feeling that the support of more complex problems has been done at the detriment of those planners scalability. Our objective with this paper is precisely to propose an alternative encoding that can (i) be used to efficiently represent planning problems and (ii) does not prevent its extension to problems with continuous change. Our encoding already supports continuous state variables andunlike dReach and SMTPlan+ -action parameters with continuous domains. As for SMTPlan+ and dReach, our use of an SMT solver with non-linear arithmetic theories opens up the possibility of reasoning with non-linear continuous changes and processes.

Constraint-based Scheduling

The consideration of optional activities in constraint solvers slowly narrows the gap that existed between planning and scheduling. Our formulation of a bounded planning problem is indeed very close to a scheduling problem with optional activities over given temporal intervals, in the spirit of those in CP Optimizer [START_REF] Laborie | Reasoning with Conditional Time-Intervals[END_REF].

Achieving good, domain-independent, performance in a such a setting would certainly require specialized global constraints. This is a promising direction to tackle the current quadratic growth in the number of constraints of our representation.

Our coherence constraints are closely related to scheduling optional activities on unary resources and state-functions for which existing techniques could be easily adapted [START_REF] Laborie | Reasoning with Conditional Time-Intervals[END_REF][START_REF] Laborie | Reasoning with Conditional Time-Intervals. Part II: An Algebraical Model for Resources[END_REF][START_REF] Vilím | Extension of O(n log n) filtering algorithms for the unary resource constraint to optional activities[END_REF]. The main difference here being the implicit choice of the state variable that is governed by several variables. Support constraints are more challenging and to our knowledge have no straightforward mapping to global constraints in scheduling. Indeed, the closest equivalent (state-functions in CP Optimizer) lack the notions of conditions and effects. While plan-space planners do provide propagators for such support constraints [START_REF] Bit-Monnot | Delete-free Reachability Analysis for Temporal and Hierarchical Planning[END_REF][START_REF] Vidal | Branching and Pruning: An Optimal Temporal POCL Planner based on Constraint Programming[END_REF], those are highly tailored to their search mechanism and adapting them would require more work.

Conclusion

In this paper, we presented a constraint-based encoding for temporal planning. The encoding is focused on handling the conditions and effects appearing in typical planning problems. It leverages a fully lifted representation and allows the addition of arbitrary constraints. These characteristics make it a good fit for a usage at the core of more general constraint-based planners or for embedding planning subproblems in CSPs.

Its usage in a simple planner, using an off-the-shelf SMT solver, shows improved performance with respect to state of the art temporal planners on planning problems with deadlines and time-windows. The resulting planner largely outperforms existing SMT-based temporal planners on planning benchmarks.

One important contribution is the identification the small discrepancies that remain between the available global constraints in constraint-based scheduling and the requirements for efficiently handling task planning problems; going one step closer to closing the long standing gap between planning and scheduling.

  α∈E Π supported-by(β, α) Internal Chronicle Consistency Given an optional chronicle C = (V, X, C, E), if it is part of the solution then all its internal constraints must hold, which is represented by the constraint consistent(C): present(C) =⇒ c∈X c Formulation as a CSP A bounded planning problem Π is encoded as a Constraint Satisfaction Problem (V Π , X Π ) where:

  . A condition states that the state variable sv(p 1 , . . . , p n ) must have the value v over the temporal interval [s, e]. -E is a set of effects. Each effect is of the form [s, e] sv (p 1 , . . . , p n ) ← v where s and e are timepoints, sv (p 1 , . . . , p n ) is a parameterized state variable (with each p i ∈ V ) and v ∈ V is a variable. Such an effect states that the state variable sv(p 1 , . . . , p n ) will take the value v at time e. Over the temporal interval ]s, e[ the state variable is transitioning from its previous value to v:

. Each condition is of the form [s, e] sv (p 1 , . . . , p n ) = v where s and e are timepoints in V , sv (p 1 , . . . , p n ) is a parameterized state variable (with each p i ∈ V ) and v ∈ V is a variable

  t s , t e } where r, s , e are variables representing the parameters of the action (truck, start location and end location) and t s and t e are timepoints representing the start and end times of the action.-X = { t e = t s + 10, s = e }, constraints stating that the action takes 10 time units and that the origin s and destination e must be different. -C = { [t s , t s ] loc(r) = s }, i.e., the truck r must be in location s at the action' start t s . -E = {[t s , t e ] loc(r) ← e }, i.e., the truck r will be in location e at the action's end t e . Its location is undefined for the duration of the action ]t s , t e [.

	Such a chronicle is called an action chronicle.

  over which the effect of α persists, and (iii) α establishes the right value on the right state variable.The fact that a condition token β ∈ C Π must be supported by at least one effect token if it is present is encoded by the constraint supported(β):

	present(β) =⇒

Table 1 .

 1 Number of problems solved by the considered planners within 30 minutes. Best result is given in boldface.

		LCP	FAPE	OPTIC	TFD	SMTPlan+
	airport-timewindows	8	7	7	1	0
	satellite-timewindows	4	10	4	0	0
	pipesworld-deadlines	17	6	13	2	0
	Total	29	23	24	3	0

Table 2 .

 2 Number of disjunctive constraints (left) and variables (right) in the SMT formulas of LCP and SMTPlan+ at various depths. Depth is the number k of duplicated actions in LCP and the number of happenings in SMTPlan+.

		Rovers p01	Rovers p10
	Depth	LCP	SMTPlan+	LCP	SMTPlan+
	1	109 / 115	1 987 / 332	165 / 132	28 760 / 1 828
	2	295 / 218	3 987 / 664	399 / 235	59 293 / 3 656
	3	561 / 321	6 161 / 996	713 / 338	89 196 / 5 484
	4	907 / 424	8 248 / 1 328	1 107 / 441	119 099 / 7 312

Note that this integer based representation of time is no less expressive than a real-valued representation when forbidding instantaneous changes, as common in temporal planning[START_REF] Cushing | When is Temporal Planning Really Temporal?[END_REF].

The original chronicle model used transitions instead of effects. We use effects to more closely match the classical definition of planning problems and simplify the presentation. Note that transitions can still be straightforwardly encoded by combining a condition and an effect.

Omitted in our translations are the hierarchical and resource constructs of ANML that are beyond the scope of this paper.

https://github.com/laas/fape/tree/master/planning/domains


Md Antje Kutz

Taibur Rahman

Ville Haapasilta

Chiara Venturini

Ralf Bechstein

André Gourdon

Adam S Foster

Angelika Kühnle

‡ Md

André Gordon

Impact of the reaction pathway on the final product in on-surface synthesis

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

On-surface synthesis has emerged as a promising approach for the fabrication of functional molecular structures on surfaces. [1][2][3][4] Performed in ultrahigh vacuum (UHV), on-surface synthesis provides the option to create products that might not be accessible in classical solution synthesis due to, e.g., the poor solubility 5 or high reactivity of the product. 4 An impressive example for the latter is the synthesis of long acenes, 6 which are instable under ambient conditions. While nonacene is the largest acene that has been synthesized so far, 7 the synthesis of decacene has been shown by on-surface reduction on a Au(111) surface. 8 In another work, triangulene has been synthesized, 9 a molecule which was predicted in 1953, 10 but never isolated in its unsubstituted form due to its reactivity.

On-surface polymerization 11 of conductive chains is of particular interest for molecular electronics applications as it offers the possibility to create electrical contacts for linking mesoscopic objects with nanoscopic functional units. [12][13][14][15][16][17] In this context, an elegant example has been presented already in 2001, where the tip of a scanning tunneling microscope has been used to initiate a diacetylene polymerization on a graphite surface. 18,19 However, molecular electronics applications require electrically insulating substrates to decouple the electronic structure of the molecules from the underlying support surface. Recently, we have shown that a diacetylene polymerization can also be induced on the (10.4) surface of calcite, which is a bulk insulator. 20 In the latter study, the dimer formed by homo-coupling of a terminal alkyne has been used as a precursor. Upon deposition onto the surface, the precursors adopt a specific adsorption geometry with a spatially well-defined arrangement. Such geometrical constraints provide the key when aiming for controlling the reaction by surface templating. 21 Given that a specific relative orientation and distance is required for initiating the reaction, 22,23 the arrangement of the precursors on the surface offers a handle for controlling the reaction pathway. Ideally, different reaction pathways should be selectable depending on the specific adsorption configuration. So far, a clear demonstration for reaction selectivity based on surface templating is, however, lacking.

In the present work, we use a terminal alkyne precursor, namely 3-ethynylbenzoic acid (3-EBA, see Fig. 1a), for on-surface synthesis on calcite (10.4) (Fig. 1b). Terminal alkynes are known to undergo Glaser coupling, 24 and the corresponding reaction has been proven to be possible also on metal surfaces. [25][26][27][28][29] We have recently presented the proof of principle that this reaction can also be performed on calcite (10.4). 30 Besides homo-coupling, the precursor used here also has the potential to undergo an acetylene polymerization. 15,[31][32][33][34][35][START_REF] Natta | Stereoregular Polymers and Stereospecific Polymerizations[END_REF][START_REF] Riss | [END_REF] On-surface acetylene polymerization has been shown on Au(111), [START_REF] Riss | [END_REF] however, not on a bulk insulator as yet. Here, we provide experimental evidence for on-surface acetylene polymerization using 3-EBA as a precursor. Upon annealing to 550 K, we obtain acetylene polymer chains with lengths of up to 80 nm as deduced from our dynamic atomic force microscopy (AFM) images. Interestingly, although the dimer forms as well, we find no evidence for diacetylene polymerization. This is surprising as diacetylene polymerization is induced when annealing the directly deposited dimer on the surface. The specificity of this reaction pathway can be understood by the different arrangement of the dimers in the two cases: when formed in an on-surface reaction, the dimers form stripes along the [-4-21] direction. When directly deposited, the dimers form stripes along the [010] direction. In these different arrangements, the alignment of the dimers with respect to each other is different, explaining why diacetylene polymerization is possible in one but not the other arrangement.

Methods

Experimental Part

The calcite crystals used in these experiments were purchased from Korth Kristalle GmbH (Altenholz, Germany). The samples were degassed in situ at 700 K for 2 hours prior to cleavage to remove air-borne contaminations. Afterwards, the cleaved crystals were annealed at 650 K for 1 hour to reduce surface charges. The 3-EBA molecules were purchased from Sigma Aldrich (Germany) or synthesized by us following established procedures [38][39][40][41][42][43] Further information on the molecule synthesis can be found in the ESI. The 3-EBA molecules were sublimated in situ from a home-built Knudsen cell. For sublimation, the maximum temperature of the cell was about 310 K. During deposition, the chamber pressure remained below 2•10 -10 mbar. The molecules were deposited onto a sample kept at room temperature.

All experiments were carried out with a VT AFM 25 atomic force microscope (ScientaOmicron, Taunusstein, Germany) under UHV conditions (base pressure typically better than 4•10 -11 mbar).

All AFM images presented in this work were captured at room temperature. Therefore, all annealed samples were cooled down to room temperature prior to imaging. The system is equipped with an external lock-in amplifier HF2LI (Zurich Instruments AG, Switzerland) to control the phase shift, amplitude and excitation of the oscillation. We used n-doped silicon cantilevers purchased from NanoWorld (Neuchâtel, Switzerland) with an eigen frequency of around 300 kHz (type PPP-NCH). Prior to the measurements, all cantilevers were treated by sputtering with Ar + at 2 keV for 10 minutes to remove possible oxide layers as well as other contaminations.

All images shown here are either topography (zp) or excitation frequency (𝜈𝜈 𝑒𝑒𝑒𝑒𝑒𝑒 ) images. The fast and slow scan directions are indicated in the upper right corner in each image. The images are displayed such that under normal imaging conditions (i.e., without contrast inversion 44 ) bright colors corresponds to high attractive interactions while dark colors correspond to less attractive or repulsive interactions.

Simulations

All the density functional theory (DFT) computations were performed using the CP2k program suite. 42 We used the PBE functional 43 augmented with the D3 dispersion correction scheme 44 in all computations, both in the structural optimization calculations (T = 0 K) and in the firstprinciples molecular dynamics (FPMD) simulations. The electronic structure was solved using the Gaussian Plane Wave Method. 45 The valence electrons were expanded in terms of molecularly optimized double-zeta basis functions, 47 whereas the core electronic states were approximated with GTH pseudopotentials. 46 The electronic density was modelled using a plane wave basis with an energy cutoff of 500 Ry. The FPMD simulations were used to explore suitable bonding patterns and to test the stability of the found structures after optimization calculations. The FPMD simulations were run for few thousand steps with a 0.5 fs timestep using velocity rescaling thermostat 45 set to a target temperature of 560 K.

Results and Discussion

At first, we investigated the adsorption of 3-ethynylbenzoic acid (3-EBA) on calcite (10.4).

More specifically, we performed density-functional theory (DFT) calculations to study the binding geometry of 3-EBA on calcite (10.4). A top and side view of the adsorption geometry is given in Figs. 2a andb The image indicates that the molecules are highly mobile at room temperature, forming a twodimensional gas of moving molecules. These are promising conditions for an on-surface reaction.

Next, we present the results of a heating series performed with the sample discussed previously. After heating the molecule-covered sample at 400 K for 1 hour, dot-like bright structures emerged (see Fig. 3a). The streaky features observed on the as-deposited sample were still present, indicative of mobile molecules. When increasing the heating temperature to 450 K for 1 hour, the streaky features nearly vanished. Most importantly, stripe-like structures were formed along the [-4-21] direction (see Fig 3b). Upon heating at 550 K for 1 hour, these stripeliked structures appeared longer in length (more than 20 nm in Fig. 3c). We could increase the stripe length up to 80 nm upon dosing more monomers and annealing for longer times (see ESI Fig. S1). The streaky features have completely vanished and only few dot-like clusters remained after heating at 550 K. To investigate the inner structure of the emerging stripes, we performed high-resolution imaging of a stripe-covered area. As can be seen in Fig. 4a, two different stripe-like structures exist, which are both aligned along the [-4-21] direction. As will be argued in the following, these two structures are assigned to (1) polyacetylene chains and (2) side-by-side aligned dimers.

The majority of the stripes (marked by the red box in Fig. 4) show a periodicity of 0.4 nm along the [-4-21] direction, corresponding to the calcium-calcium distance in this direction (see Fig. 4bc). Terminal alkynes are known to react via an acetylene polymerization. 31 To investigate whether the stripes formed here indeed constitute acetylene polymers, we again performed DFT calculations. We compared the formation energy of the polymer on the surface with the equivalent number of monomers, i.e., isolated 3-EBA molecules, maintaining compatible atom numbers in both energy evaluations. We found that the acetylene polymer chain has a formation energy, which is 1.1 eV per molecule lower than the energy of isolated 3-EBA molecules on calcite (10.4). This calculation suggests that an acetylene polymer on the surface should be more favorable than the unreacted monomers. Moreover, the calculated cis-transoidal polymer structure fits excellently to the observed stripe structure, as demonstrated in Fig. 4d. With these results, we conclude that an acetylene polymerization can be achieved via the deposition of the monomer precursor, 3-EBA, onto calcite (10.4). 47 In principle, the 3-EBA monomer used here also has the possibility to undergo dimerization. 25 When depositing this dimer directly onto calcite (10.4), we have previously shown that it undergoes diacetylene polymerization. 20 This leads to the interesting question as to why there is no indication of diacetylene polymerization upon deposition of the 3-EBA monomer. Does no dimer form? For this, we return to the second structure formed, which is marked by the blue box in Fig. 4a.

In these stripes, dark dots at the periphery of the stripes are observed, which exhibit a periodicity of 0.8 nm along the [-4-21] direction, which corresponds to the unit cell dimension in this direction (see Fig. 5(a-b)). To obtain further insights into this structure, we compare these stripes with the previously reported arrangement of the dimer molecules when directly deposited onto calcite (10.4). 20 When directly deposited onto calcite (10.4), the dimers form islands composed of rows running along the [010] direction. However, a second island structure is found that was reported in our previous work, 20 composed of rows oriented along the [-4-21] direction (see Fig. 5c). These rows exhibit a periodicity of 0.8 nm along the row direction and do, indeed, resemble the second stripes observed here. When an image of the second stripe structure is superimposed onto the island, the excellent fit in dimensions becomes evident (see Fig. 5d), indicating that the second stripe structure found here is composed of side-by-side arranged dimers resulting in rows oriented in the [-4-21] direction. In summary, the two different reaction products observed here are assigned to (1) polyacetylene chains and (2) side-by-side aligned dimers. The latter finding is surprising because it shows that the monomer indeed undergoes homo-coupling and forms dimers, however, no further reaction towards diacetylene polymers is observed (see Fig. 6). This result demonstrates that a different pathway is taken when the monomer is deposited and only forms dimers on the surface as compared to depositing the dimer directly. In both cases, dimers are present on the surface and arrange side-by-side to form stripes, however, when depositing the dimers directly, the stripes are predominantly aligned along the [010] direction with a periodicity of 0.5 nm along the stripe. 20 In this arrangement, the dimer spacing is in the reported range required for diacetylene polymerization of 0.47 to 0.52 nm and also the angle of the molecular axis with respect to stripe matches the angle of 45°, which has been mentioned in literature. 23 In contrast to the situation observed after depositing the dimers directly, when the dimers are only formed on the surface, the stripes are aligned along the [-4-21] direction. Here, the periodicity along the stripe is 0.8 nm, which is significantly larger than what has been reported for diacetylene polymerization. 23 In this case, the dimers do not further react to diacetylene polymers. This comparison demonstrates that, even that the same molecule is present on the surface in both cases, the specific reaction conditions governs the reaction pathway that is taken.

Conclusion

In conclusion, by the interplay of dynamic AFM experiments and DFT computations we present evidence for an acetylene polymerization carried out on a bulk insulator surface. The terminal alkyne precursor molecule, 3-EBA, used in this work forms a two-dimensional gas of mobile molecules on the surface when deposited at room temperature on calcite (10.4). Heating the sample at 550 K results in the formation of stripes along the [-4-21] direction, which match excellently match with cis-transoidal acetylene polymer chains. This assignment is further corroborated by the DFT calculations, revealing that the acetylene polymerization is associated with an energy gain of 1.1 eV per acetylene unit formed. Moreover, another type of stripe oriented along the [-4-21] direction can be found that is identical to a structure formed upon direct deposition of the dimer.

Therefore, we assign these stripes to an arrangement of side-by-side aligned dimers.

Most interestingly, we find no evidence for a further reaction of the latter dimers to form a diacetylene polymer. This is in sharp contrast to what has been found previously when directly depositing the dimers. Thus, our result demonstrates that the constraint given by the specific reaction pathway can effectively control the final product: When the dimer is deposited directly, the diacetylene polymerization is induced. In sharp contrast, when the dimer is only formed in an on-surface reaction from the monomer precursor, the diacetylene polymerization is effectively prohibited. Our work provides a clear example of how the specific reaction pathway in on-surface synthesis affects the final product. See the ESI for a detailed discussion of other reasonable reaction pathways, in which we provide arguments for discarding all other obvious reaction products.

Synthesis of methyl 3-iodobenzoate

1 I O M e O a c
To a round-bottomed flask were added 3-iodobenzoic acid (2 g, 8.06 mmol), some drops of conc.

H2SO4 and MeOH (50 mL). The solution was heated under reflux overnight, then it was diluted with diethyl ether and washed with H2O, a saturated solution of NaHCO3 and brine. The organic phase was dried over MgSO4 and evaporated under vacuum. The product 7 (1.473 g) is a white solid and was obtained with a yield of 69. 71 %. 7.55*10 -1 mmol) were dissolved in degassed THF(10 mL) in a Schlenk flask. Then trimethylsilylacetylene (0.81 mL), NEt3 (1.06 mL) were added and degassed again for some minutes. The solution was stirred at room temperature under argon atmosphere. After 3h (when the entire starting compound had reacted) were added TBAF in THF solution (7.65 mL) and some molecular sieves (3Å). The reaction was stirred under air atmosphere and at room temperature overnight. The mixture was then filtered on Celite, washing with Et2O. The residue was then purified by column chromatography (SiO2, EtOAc/ hex 0.5 : 9.5) to afford the product (0.392 g, 64.13 %).

Discussion of Reasonable other Reaction Products

To elucidate the nature of the majority stripes formed after annealing, we here discuss the possible reaction pathways the precursor 3-EBA can undergo (Fig. S2). Firstly, the 3-EBA monomers can form straight dimers (Fig. S2a), which are known to subsequently undergo a diacetylene polymerization reaction (Fig. S2b). Secondly, the 3-EBA monomers can undergo a cyclo-trimerization reaction (Fig. S2c) or dimerization reactions that would result in non-straight dimers (Fig. S2d). Finally, terminal alkynes are known to react via an acetylene polymerization (Fig. S2e). Next, we discuss the nature of the majority stripes observed here upon annealing of 3-EBA on the basis of these reaction pathways. As detailed in the main text, the majority stripes are oriented along the [-4-21] direction and show a periodicity of 0.4 nm along this direction.

We discard option S2a, as we can directly compare with the outcome of our previous study: 8 Previously reported AFM images of the straight dimer molecules direction (see Fig. 5c in the main text). These rows, however, exhibit a periodicity of 0.8 nm along the row direction, which does not match the 0.4 nm periodicity found here for the stripes. From these experimental evidences, we conclude that the stripes are not composed of the straight dimers (ruling out the option shown in Fig. S2a). Moreover, we performed DFT calculations to further corroborate this experimental conclusion. To this end, we investigated whether the stripes could be formed 3-BBA molecules arranged side-by-side. Our DFT calculations revealed that it is energetically unfavorable for 3-BBA to be arranged side-by-side along the [-4-21] direction with a periodicity of 0.4 nm, giving further evidence for the conclusion that the stripes are not formed by side-by-side arranged molecular dimers.

As has been shown previously, the dimers can further react via a diacetylene polymerization (Fig. S2b). 8 The diacetylene polymer chain revealed a periodicity of 0.5 nm along the [010] direction on the calcite (10.4) surface. The comparison of the stripes observed here with this diacetylene polymer chain discards the option of the type A stripes being formed from diacetylene polymers, as these two structures do not agree in orientation nor in periodicity.

Moreover, all non-straight and cyclic structures can be excluded, as the stripes observed here are linear. Thus, we additionally discard the options shown in Figs. S2c andS2d.

Figure 1 .

 1 Figure 1. Model of (a) the 3-ethynylbenzoic acid (3-EBA) molecule and (b) the calcite (10.4) surface. The scale bar applies to both models. The calcite (10.4) surface has a rectangular unit cell with dimensions of (0.50 × 0.81) nm 2 , consisting of two carbonate ions and two calcium ions.

  , showing a flat-lying molecule. The main axis of the molecule is oriented along the [-4-21] direction with the ring being positioned on a calcium row. The carboxylic acid group binds to the surface via a characteristic binding motif: 46 the negatively charged carbonyl oxygen is on top of the positively charged surface calcium, while the hydrogen points to the protruding oxygen atom of the surface carbonate group. The adsorbed molecule exhibits a formation energy of -1.5 eV (with a negative energy being favorable to formation), indicating that the molecule should stick on the surface at room temperature. While this is the most stable configuration we found, there are several other possibilities involving the rotation of the molecule's OH-group within 0.4 eV of the ground state. This flexibility likely explains the high mobility of the monomers on the surface despite the strong adsorption, as at room temperature the molecule will rapidly sample through all these configurations offering paths to translational motion.

Figure 2 .

 2 Figure 2. Optimized geometry of an isolated 3-EBA molecule on the calcite (10.4) surface in (a) top view and (b) side view. (c) AFM topography image of an as-deposited calcite (10.4) sample. Two step edges are seen in the image. The terraces are covered by streaky features, indicating mobile species on the surface at room temperature.

Figure 3 .

 3 Figure 3. Examples from a heating series of a molecule-covered sample. Each annealing step lasted for 1 hour. (a) Heating to 400 K led to the formation of some bright dots, while (b) heating to 450 K resulted in a reduction of the streaky features and the appearance of stripe-like structures, oriented in the [-4-21] direction. Further heating to (c) 550 K yielded in longer stripes and the disappearance of the streaky features.

Figure 4 .

 4 Figure 4. Molecular structure obtained upon heating the sample for 1 h to 550 K. (a) Two different kind of stripes can be seen along the [-4-21] direction, marked by red and blue boxes, respectively. (b) The stripe marked by the red box in (a) is shown in a frequency shift image, revealing the periodicity of 0.4 nm. (c) Sketch illustrating the inner structure of the stripes. (d) Acetylene polymer structure as obtained from DFT, including the calcite (10.4) surface to illustrate the excellent match in size and pattern.

Figure 5 .

 5 Figure 5. (a) Zoom-in AFM image of second structure formed upon heating the 3-EBA monomer deposited on calcite (10.4) surface, exhibiting the periodicity of 0.8 nm. (b) Sketch illustrating the inner structure of the stripes. (c) Structure observed after direct deposition of the dimer. The yellow box highlights an island composed of stripes oriented along the [-4-21] direction. (d) An area from (a) is superimposed onto the island shown in image (c).

Figure 6 .

 6 Figure 6. Overview of the reaction pathways of the 3-EBA monomer (a) on calcite (10.4). Upon annealing, acetylene polymerization can be induced (b). The monomer can also form homo-coupled dimers. These dimers align side-by-side and form rows along the [-4-21] direction (c). Interestingly, in this arrangement, the dimers do not react further. When directly depositing the dimers, rows arranged in the [010] direction form (d). Only in this arrangement, the dimers undergo diacetylene polymerization (e).

  46 D. M. Duffy and J. H. Harding, Langmuir, 2004, 20, 7630-7636. 47

Figure S2 .

 S2 Figure S2. (a) Overview of reaction pathways based on terminal alkynes, namely (a) homocoupling of terminal alkynes with possible subsequent (b) diacetylene polymerization, (c) alkyne cyclotrimerization, (d) alkyne dimerization and (e) acetylene polymerization.

( 3 ,

 3 3´-(1,3-butadiyne-1,4diyl)bisbenzoic acid, 3-BBA) directly deposited onto calcite (10.4) revealed islands composed of rows running along the [010] direction. As our stripes are aligned perpendicular to the [010]direction, we discard this structure. However, in the previous work, we have observed that 3-BBA molecules can form a second island structure that is composed of rows oriented along the[-4-21]

  The reaction was stirred overnight. Then the solvent was removed in vacuum, then HCl 3M was added drop by drop until precipitate at pH 8; then adjusted at pH 2~3 and extracted with EtOAc. The organic phase was washed with brine and dried over an. MgSO4; removing of the solvent in vacuum afforded the target compound (0.045 g, 54.20 %).

	Synthesis of 3-ethynylbenzoic acid 5, 6,7
	HO	c
	O	a
	Methyl 3-ethynylbenzoate (91 mg, 5.68*10 -1 mmol) was dissolved in MeOH (1.5 mL) under
	stirring and then a solution of LiOH (16 mg, 6.68*10 -1 mmol) in H2O (1.5 mL) was added to the
	mixture.
	1 H NMR (300 MHz, CDCl3) δH 8.16 (1H, s, Ar-Ha), 8.03-8.00 (1H, m, Ar-H), 7.68-7.64 (1H, m,

Ar-H) , 7.41 (1H, t, J = 7.8 Hz, Ar-Hc), 3.92 (3H, s, ˗OCH3), 3.12 (1H, s, ˗CH). 1 H-NMR (300 MHz, CDCl3) δH 8.23 (1H, s, Ar-Ha), 8.10-8.06 (1H, m, Ar-H), 7.74-7.71 (1H, m, Ar-H), 7.46 (1H, t, J = 7.8 Hz, Ar-Hc), 3.14 (1H, s, ˗CH).

ACKNOWLEDGMENT

We gratefully acknowledge financial support from the EU through grant PAMS (seventh framework program GA 610446). Computing resources from the Aalto Science-IT project and CSC IT Center for Science, Finland, are gratefully acknowledged. This work was furthermore supported by the Academy of Finland through its Centres of Excellence Programme 2015-2017 under project number 284621, as well as project 314877. A.S.F. was supported by the World Premier International Research Center Initiative (WPI), MEXT, Japan.

AUTHOR INFORMATION

Corresponding Author

*kuehnle@uni-bielefeld.de

Conflicts of interest

The authors declare no conflicts of interest.

Additional Image of Reaction Product

We have done the mentioned experiment more than 10 times and investigated a total area of more than 50,000 nm 2 on several calcite (10.4) surfaces. A further representative image is given below.