Fabien Sénéchal
email: fabien.senechal@u-picardie.fr

Sarah Robinson

Evert Van Schaik

Martine Trévisan

Prashant Saxena

Didier Reinhardt

Christian Fankhauser

James Watt

Pectin methylesterification modulates cell wall properties to promote neighbour proximityinduced hypocotyl growth

Keywords: CF, DR, FS, SR, EVS. Formal analysis: FS, SR, EVS, MT, PS

research documents, whether they are published or not. The documents may come

Pectin methylesterification modulates cell wall properties to promote neighbour proximity-induced hypocotyl growth

Introduction

Plants growing in dense populations compete for light required for photosynthesis [START_REF] Fiorucci | Plant Strategies for Enhancing Access to Sunlight[END_REF]. Proximity of competitors and shade are perceived as a change in light intensity and quality, resulting in various developmental adaptations [START_REF] Galvão | Sensing the light environment in plants: Photoreceptors and early signaling steps[END_REF]. Depending on their response to shade, plants are classified into shadetolerant and shade-avoiding species [START_REF] Gommers | Shade tolerance: When growing tall is not an option[END_REF]. The latter react to shade with characteristic growth responses in order to reach full sunlight for photosynthesis. This phenomenon, known as Shade-Avoidance Syndrome (SAS) can be observed in most aerial organs and involves a range of developmental changes (Pierik and De Wit, 2014). For example, SAS entails early flowering and inhibition of branching, leaves adopt an upright position (hyponasty), and petioles, stems and hypocotyls elongate (de Wit et al., 2016). These changes accelerate the life cycle of plants and warrant survival and propagation under limited light availability.

The phytochrome (phy) type photoreceptors have a central role in SAS with phyB playing a predominant role in Arabidopsis thaliana (Legris et al., 2019). Under high R:FR conditions, corresponding to full sunlight, active phyB moves into the nucleus, where it interacts with transcription factors known as Phytochrome Interacting Factors (PIFs) to inhibit their activities. Low R:FR conditions, on the other hand, cause inactivation of phyB and derepression of the PIFs, which modulate genes required for shade-induced growth (de Wit et al., 2016). A central mechanism in shade-induced growth is auxin biosynthesis in cotyledons and young leaves followed by polar transport and distribution in hypocotyls and stems, which elongate in response to shade (de Wit et al., 2014). phyB and PIFs also act localy in the hypocotyl to promote growth through mechanisms that are less clearly established [START_REF] Fiorucci | Plant Strategies for Enhancing Access to Sunlight[END_REF]Pucciariello et al., 2018). For example PIFs regulate the expression of genes required for plasma-membrane lipid biogenesis in the hypocotyl [START_REF] Ince | A combination of plasma membrane sterol biosynthesis and autophagy is required for shade-induced hypocotyl elongation[END_REF].

Moreover, numerous genes encoding cell wall-modifying proteins are induced by shade and targeted by PIFs (Kohnen et al., 2016;Pedmale et al., 2016), suggesting role for cell wall metabolism in the establishment of the shade-regulated growth.

The primary cell wall of growing plant organs has seemingly contradictory functions.

On the one hand, it provides mechanical strength to maintain cell shape and plant stature, on the other hand, it has to remain elastic and plastic to allow cell expansion and plant growth [START_REF] Bashline | Cell wall, cytoskeleton, and cell expansion in higher plants[END_REF]. In dicotyledonous species such as Arabidopsis, the primary cell wall consists of interconnected networks of polysaccharides and structural proteins/glycoproteins [START_REF] Cosgrove | Growth of the plant cell wall[END_REF]Wolf et al., 2012a;Nguema-Ona et al., 2014). A first network of cellulose microfibrils cross-linked by hemicelluloses (network 1) is embedded in a second network made by pectins that have gelling properties (network 2). Pectins are intimately associated with a third network (network 3), consisting mainly of glycoproteins such as extensins (EXTs) and arabinogalactan proteins (AGPs) [START_REF] Hijazi | An update on post-translational modifications of hydroxyprolinerich glycoproteins: toward a model highlighting their contribution to plant cell wall architecture[END_REF]. This complex threedimensional mesh resists to internal turgor pressure, and at the same time yields to allow cell growth. Dynamic adjustment of physical cell wall properties (e.g. stiffness, elasticity, plasticity) involves cell wall-synthesizing and modifying enzymes that usually belong to multigenic families and constantly modulate cell walls to allow growth [START_REF] Atmodjo | Evolving Views of Pectin Biosynthesis[END_REF]Sénéchal et al., 2014b;Pauly and Keegstra, 2016;Showalter and Basu, 2016).

Cell wall remodeling plays a central role in the control of seedling development, however, its contribution to adaptive growth phenomena in response to environmental cues such as SAS remains poorly understood. Although transcriptomic analyses suggested that cell wall remodeling may play a central role in adaptive growth processes (Kohnen et al., 2016), direct functional evidence is scarce. A role for xyloglucans in SAS has been established for petiole elongation in Arabidopsis (Sasidharan et al., 2010;Sasidharan and Pierik, 2010), and for shade-induced growth in Stellaria longipes (Sasidharan et al., 2008). Here, we took a systematic approach to explore the contribution of cell wall remodeling in SAS of the Arabidopsis hypocotyl. By combining Fourier-transformed infrared (FTIR) analyses of cell wall constituents with measurements of cell wall biophysics, we show that cell wall remodeling is triggered at early stages of the growth response induced by low R:FR, indicative of neighbour proximity that is a form of SAS. Employing systematic transcriptomic and genetic analysis with mutants affected in various aspects of cell wall biosynthesis and modification, we establish pectin methylesterification status as a central determinant of cell wall extensibility in the neighbour proximity-induced hypocotyl growth.

Results

Low R:FR induces cell elongation mainly in the middle part of the hypocotyl

In order to simulate the proximity of competing neighbours, we subjected Arabidopsis seedlings to white light supplemented with far red (low R:FR ratio). Within one day, this led to increased hypocotyl growth compared to control seedlings kept in white light (high R:FR ratio) (Fig. 1A). In order to determine the site of growth, we used the borders of epidermal cells as marks, since hypocotyl elongation proceeds almost exclusively by cell elongation without cell division. In order te assess cell dimensions, confocal images of seedlings were segmented in MorphoGraphX (de Reuille et al., 2015), followed by semiautomated cell size measurements. Cell length along the length of the hypocotyl was increased by low R:FR primarily in the middle part of the hypocotyl (Fig. 1B).

Low R:FR changes mechanical properties of hypocotyl cell walls

To assess the mechanical properties of the hypocotyl during growth induced by low R:FR, we used an automated confocal micro-extensometer (Robinson et al., 2017). This approach enabled in vivo quantification of the elastic properties of cell walls. Hypocotyls of intact seedlings were abraded by freezing and thawing and subjected to repeated cycles of application and removal of 5 mN of force . Our analysis revealed increased strain under low R:FR after one day of treatment, and decreased strain after three days (Fig. 2A). Interestingly this effect was specific to low R:FR conditions, since no such changes were observed under high R:FR (Fig. 2A).

To relate growth and mechanical changes induced by low R:FR to cell wall properties, we applied Fourier-transformed infrared (FTIR) microspectroscopy to cells located in the middle part of the hypocotyl. The relative absorbance intensities for wavelengths related to the cell wall (from 830 to 1800 cm -1 ) were selected to assess the composition and status of various cell wall polysaccharides. FTIR analysis revealed significantly different patterns of relative absorption induced by low R:FR ratio after three days of treatment (Fig. 2B and Fig. S1). The main differences were observed between 1530 and 1200 cm -1 and between 1180 and 1030 cm -1 (Fig. 2B). A relative decrease (at 1740 and between 1530-1200 cm -1 ) indicates lower levels of pectins and xyloglucans, as well as cellulose and lignin. On the other hand, an increase between 1180 and 1030 cm -1 indicates enrichement of pectins, xyloglucans, cellulose and arabinogalactan that can relate both to AGPs and rhamnogalacturonan I-type pectins (Fig. 2B). These results indicate major cell wall remodeling in response to low R:FR ratio. In order to obtain further insight into the changed cell wall components, we performed hierarchical clustering for the wavelengths that have previously been assigned to certain cell wall components [START_REF] Kakuráková | FT-IR study of plant cell wall model compounds : pectic polysaccharides and hemicelluloses[END_REF]Wilson et al., 2000;Mouille et al., 2003;[START_REF] Alonso-Simón | The use of FTIR spectroscopy to monitor modifications in plant cell wall architecture caused by cellulose biosynthesis inhibitors The use of FTIR spectroscopy to monitor modifications in plant cell wall architecture caused by cellulose biosynthesis inhibi[END_REF]Szymanska-Chargot and Zdunek, 2013;Largo-Gosens et al., 2014) (Fig. 2C).

This revealed an overall enrichment for pectins with a low degree of methylesterification (deesterified pectins), in addition to other pectins, arabinogalactan proteins, cellulose, and xyloglucans in response to low R:FR, while other wavelengths assigned to pectins, cellulose and xyloglucans showed opposite trends. Depending on the chemical bonds revealed by the wavelengths, different structural part of the polysaccharides are assessed such as backbone and side chains. This could explain opposite trends for wavelengths related to the same polysaccharide, which can be more abundant with reduced side chains for instance. Taken together, these results revealed major changes in cell wall biosynthesis and remodeling in response to low R:FR.

Low R:FR impinges on expression of cell wall-related genes

In order to investigate transcriptional regulation of cell wall properties under low R:FR, we considered 40 gene families that are thought to be involved in synthesis and/or remodeling of cell wall components. The expression of a total of 824 genes was analyzed using an RNA sequencing dataset from a time course experiment under low R:FR conditions (Kohnen et al., 2016). In this set of genes, 544 were found to be expressed in seedlings grown under control conditions, among which 224 were regulated by low R:FR in hypocotyls (Fig. 3A). Only few genes were regulated in cotyledons or in both organs (26 and 16 genes, respectively) (Fig. 3A). Most genes were regulated at later stages (90 or 180 min after onset of light stimulus), and they were mostly up-regulated, in particular in hypocotyls (Fig. 3A).

Modulated genes comprised functions related to (hemi)cellulose (network 1), pectin (network 2), and structural proteins (network 3) (Fig. 3B). The few genes that were induced at the early time points (15 or 45 min. after onset of the light stimulus) in hypocotyls are involved in cell wall remodelling (At1g49490:EXT, At5g47500:PME, At1g62760:PMEI, At5g02260:EXP, At5g57560:XTH, At1g02405:EXT, At3g10710:PME, Tables S1A andS1B). Considering the global influence of FR light on cell biosynthetic genes, the highest percentage related to pectins (network 2) with 96% of the genes expressed in seedlings, and 52% affected by low R:FR conditions. Taken together, these results indicate that cell wall remodelling is initiated within the first 15 minutes of low R:FR treatment, followed by general cell wall modifications involving both synthesis and remodeling of all cell wall constituents, in particular of pectin.

SAS is controlled by PIFs, hence, we interrogated previously published ChIP sequencing data (Kohnen et al., 2016) for interactions of PIF4 and PIF5 with the 224 genes regulated in the hypocotyl under low R:FR conditions. Indeed, 59 genes showed a direct interaction with PIF4 and/or PIF5 (Fig. S2 and Table S1C), including genes related to all three polymer networks, as well as to all processes including cell wall synthesis, remodelling, and signalling.

Cell wall-related mutants reveal the role of cell wall components in low R:FR-induced growth

In order to gain insight into the mechanisms involved in low R:FR-induced growth, loss-of-function mutants defective in the three networks (cellulose, pectin, glycoproteins) were investigated for growth phenotypes under low R:FR treatment. We selected xxt mutants impaired in xyloglucan biosynthesis (network 1), mutants affected in pectin biosynthesis (gaut, gatl and cgr) and pectin remodeling (pme and pmei; network 2), and mutants affected in AGP biosynthesis (galt, agp10c, and fla9; network 3). All of these mutants were subjected to low R:FR treatment for three days and their hypocotyl growth response was normalized to the wild type. None of the single mutants in network 1 had a growth phenotype (Fig. 4A), possibly because of genetic redundancy, but the double mutants xxt1xxt2 and xxt2xxt5 showed significantly reduced hypocotyl elongation in response to low R:FR. In network 2 mutants, only cgr2, had a growth defect, which was exacerbated in the cgr2cgr3 double mutant.

Unexpectedely, mutants affected in network 3 generally grew longer than the wild type (Fig. 4A). Taken together, these results highlight the importance of xyloglucan and pectin in SAS, while some proteinaceous component of the cell walls appear to restricts hypocotyl elongation in the wild type.

Based on the induction of several homogalacturonan methyltransferases (HGMT), including the previously characterized HGMT genes CGR2 and CGR3 (Kim et al., 2015) (Fig. S3), and on the strong growth phenotype of the cgr2cgr3 double mutant, (Fig. 4A), we investigated cell wall constituents in cgr2cgr3 by FTIR analyses using wavelengths assigned to methylesterified (1740 cm -1 ) and demethylesterified (1630 cm -1 ) pectins (Fig. S4). Using these wavelengths we estimated the degree of methylesterification (DM), which was decreased by approximately 40% in cgr2cgr3 compared to the wild type. In a time course experiment, cgr2cgr3 was not affected in hypocotyl growth under control conditions (high R:FR), however, under low R:FR conditions, growth was reduced (Fig. 4B). Notably, cgr2cgr3 reacted slower (4d+1d) and weaker (4d+3d) than the wild type (Fig. 4B). The growth defect of cgr2cgr3 was particularly pronounced in the middle part of the hypocotyl that normally shows the strongest growth response (Fig. S5). This indicates that cgr2cgr3 mutants have a defect in low R:FR-induced epidermal cell elongation.

We next assessed the mechanical properties of cgr2cgr3 hypocotyls in response to low R:FR (Fig. 4C). Wild type hypocotyls had shown an increase in cell wall strain after 1d, and a decrease after 3d of FR treatment (Fig. 2A). In contrast, cgr2cgr3 did not show a change in strain at either time point, indicating that cell wall remodeling is defective in the double mutant. To further address this aspect, we investigated cell wall composition of cgr2cgr3 by FTIR microspectroscopy as in the wild type (Fig. 2B,C), in the range of wavelengths from 830 to 1800 cm -1 to obtain a cell wall fingerprint. This analysis was performed in the middle part of hypocotyls which shows the strongest growth increment under low R:FR (Fig. 1B, Fig. S6). Relative absorbances for Col-0 and cgr2cgr3 did not show significant changes in response to low R:FR after the first day (Fig. 5A; Figs. S6A,B upper panels). However, 3 days after transfer, both wild type and cgr2cgr3 showed significant changes of relative absorbances in response to low R:FR conditions (Fig. 5A; Figs. S6A,B, lower panels).

Overall, the pattern of the significantly affected wavelengths were similar for both genotypes, but the differences were more pronounced in the wild type than cgr2cgr3 (Fig. 5B).

The main differences beween the genotypes were observed in the range of wavelengths from 1630 to 1500 cm -1 with a decrease in the wild type but not in cgr2cgr3 (Fig. 5B), and between 1180 to 1030 cm -1 , where the wild type showed a stronger increase than the double mutant. These results suggest that a change in pectin methylesterification in 251 cgr2cgr3 results in secondary changes in cell wall composition (Fig. 5B).

252

Discussion

While growth is simple to quantify, in particular in an organ like the hypocotyl that grows essentially in only one dimension, the underlying molecular mechanisms are extremely complex because they involve multiple regulatory levels such as hormonal and metabolic regulation, transcriptional activation of growth-related genes, and ultimately remodeling of the complex three-dimensional cell wall polymer network. Thanks to the ease of mutational analysis of growth, many of the upstream regulatory components in SAS have been identified (Procko et al., 2014;[START_REF] Ballaré | The shade-avoidance syndrome: Multiple signals and ecological consequences[END_REF][START_REF] Fiorucci | Plant Strategies for Enhancing Access to Sunlight[END_REF]. A reduced R:FR indicative of neighbour proximity is primarily perceived by phyB in cotyledons and young leaves [START_REF] Ballaré | The shade-avoidance syndrome: Multiple signals and ecological consequences[END_REF][START_REF] Fiorucci | Plant Strategies for Enhancing Access to Sunlight[END_REF]. This leads to PIFmediated induction of auxin production, which following transport to the hypocotyl promotes elongation (Procko et al., 2014;[START_REF] Ballaré | The shade-avoidance syndrome: Multiple signals and ecological consequences[END_REF][START_REF] Fiorucci | Plant Strategies for Enhancing Access to Sunlight[END_REF].

PIFs can also directly regulate expression of hypocotyl specific genes as shown for genes encoding enzymes involved in plasma-membrane biogenesis [START_REF] Ince | A combination of plasma membrane sterol biosynthesis and autophagy is required for shade-induced hypocotyl elongation[END_REF]. Our data suggests low R:FR induces extensive hypocotyl-specific regulation of genes encoding enzymes involved in cell wall biosynthesis and remodeling (Fig. 3), that ultimately results in in alteration of cell wall properties and induction of growth. However, due to the interdependency of cell wall components, it has been difficult to disentangle the role of individual cell wall components in growth. Here, we identified and characterized pectin methylesterification status as a central element in the growth phenomenon of Arabidopsis seedlings in the shade avoidance response.

Pectin consists mainly of homogalacturonan (HG) which represents a linear polymer of galacturonic acid (GalA) synthesized by galacturonosyltransferases (GAUTs) and GAUTlike (GATL) enzymes in the Golgi apparatus [START_REF] Atmodjo | Evolving Views of Pectin Biosynthesis[END_REF]. HG is subsequently methylesterified by HGMTs before secretion into the cell wall, where it can be selectively demethylesterified by pectin methylesterases (PMEs) (Sénéchal et al., 2014b). Thus, PME activity adjusts the degree of methylesterification (DM), which in turn modulates cell wall mechanical properties (Peaucelle et al., 2011;Wang et al., 2020). Furthermore, PMEmediated demethylesterification can expose HG to pectin-degrading enzymes such as polygalacturonases (PGs) and pectate lyases-like (PLLs) (Sénéchal et al., 2014b). Pectin degradation by these enzymes can contribute to cell wall loosening. There is evidence for a functional role of pectin metabolism in the regulation of growth [START_REF] Bouton | QUASIMODO1 Encodes a Putative Membrane-Bound Glycosyltransferase Required for Normal Pectin Synthesis and Cell Adhesion in Arabidopsis[END_REF]Mouille et al., 2007) (Pelletier et al., 2010;[START_REF] Guénin | Identification of pectin methylesterase 3 as a basic pectin methylesterase isoform involved in adventitious rooting in Arabidopsis thaliana[END_REF]Wolf et al., 2012b;Sénéchal et al., 2014a) (Wang et al., 2010;Xiao et al., 2014;Rui et al., 2017), however, the high degree of redundancy in cell-wall remodeling enzymes has complicated the analysis. For example, there are 66 and 76 genes, respectively, that encode PMEs and PME inhibitors (PMEIs), allowing for extensive compensatory responses upon genetic or pharmacological interference.

A mechanistic understanding of growth phenomena requires the combined use of genetic, analytic, and biomechanical methods to identify the causal elements in cell growth.

Using FTIR analysis, we document changes in cell wall composition in response to changes in the R:FR ratio, which correlate with accelerated growth. We identified two homogalacturonan-methyltransferase (HGMT) genes (CGR2 and CGR3) that are required for neighbour proximity-induced growth. Biomechanical assays showed that CGR2 and CGR3 contribute to cell wall extensibility at the onset of growth. Previous studies used atomic force microscopy to analyze cell walls, which meausures properties perpendicular to the direction of growth, to detect differences in mechanical properties in plants with modified pectin that correlated with growth (Peaucelle et al., 2008;Peaucelle et al., 2011;[START_REF] Braybrook | Mechano-Chemical Aspects of Organ Formation in Arabidopsis thaliana: The Relationship between Auxin and Pectin[END_REF]Peaucelle et al., 2015). In this study we were able to measure differences in mechanical properties using an extensometer which measures properties in the direction of growth. Both approaches show a correlation between modifying pectin chemistry, changes in cell wall mechanical properties and growth, supporting a role of pectin in growth regulation.

Further work is required to understand the nature of this regulation and how it relates to the other cell wall components [START_REF] Coen | The mechanics of plant morphogenesis[END_REF].

Materials and Methods

307

Information on the biological material and methods is available in the supplemental data 308 t-value

Figure 1 .

 1 Figure 1. Low R:FR induces fast growth in the middle part of the hypocotyl. (A) Length of the hypocotyls in response to high and low R:FR treatments. Col-0 seedlings were grown for 4 days in high R:FR before being transferred under low R:FR (blue bars) or kept in high R:FR (yellow bars) for 3 additional days. The bars show means in mm ± confidence intervals measured at 4 (4d), 5 (4d+1d) and 7 (4d+3d) days. Significant differences (indicated with letters) were determined according to one-way Anova followed by a multiple comparisons with Tukey's test. (B) Length of the hypocotyl epidermis cells in response to high and low R:FR treatments. After 4 days under high R:FR (blue curve), Col-0 seedlings were grown for 1 day under high R:FR (red curve) or low R:FR (green curve). The length of the epidermis cells were plotted from the top to the bottom part of the hypocotyl. The curves show means in µm ± confidence intervals (shaded areas).

Figure 2 .

 2 Figure 2. Low R:FR induces changes in mechanical and cell wall properties of the hypocotyl. (A) Elastic properties of hypocotyl assessed under high and low R:FR treatment. Hypocotyls were frozen and thawed then subjected to cycles of application and removal of 5 mN of force using an automated confocal micro extensometer (see methods). The average magnitude of strain incurred by seedlings grown in a high R:FR (yellow bars) or low R:FR (blue bars) light regime after 1 (4d+1d) and 3 days (4d+3d) is shown. Bright-field images were collected every 645 ms and strain was computed from regions that were tracked in the images using the ACME tracker software. The bars show means in % ± SD (n>10 independent seedlings, at least five oscillations were made). Pairwise comparisons were made using Welch t-test brackets indicated statistical tests that were made with significance p<0.1*, p<0.05** and p<0.01***. (B,C) Cell wall properties in the middle part of the hypocotyl under high and low R:FR treatments. Cell wall chemical bounds were analyzed by Fourrier-Transformed InfraRed (FTIR) microspectroscopy. For each hypocotyl, 6 spectra were collected in the middle part, avoiding the central cylinder, for at least 5 independent hypocotyls per condition. Baseline correction and data normalization were made for the absorbances between 1810 and 830 cm -1 (corresponding to the cell wall fingerprint, see Supplemental Figure S1). Pairwise comparison between high and low R:FR was made after 1 and 3 days treatments and significant differences were identified using Student's t-test for each wavelength. (B) All Student's t-values were plotted against wavelengths with horizontal lines referring to significant threshold for p<0.05. Student's t-values above +2 or below -2 indicate respectively an enrichment or an impoverishment of cell wall components in low compared to high R:FR. (C) Student's t-values for wavelengths assigned to cell wall components were used to build the heatmap with negative and positive t-values respectively represented by a range of colors from blue to orange.

Figure 3 .

 3 Figure 3. Low R:FR triggers changes in the expression of cell wall-related genes. (A)Number of cell wall-related genes identified as expressed in seedling and regulated by low R:FR in hypocotyl, cotyledon or both. From cell wall-selected genes and RNA sequencing data(Kohnen et al. 2016), Venn diagrams highlight cell wall-related genes expressed in seedling and that are regulated by low R:FR in hypocotyl, cotyledon or both. For each, number of up and down-regulated genes are shown along the kinetic of low R:FR treatment.

Figure 4 .

 4 Figure 4. Analysis of mutants impaired in cell wall metabolism reveals importance of CGR2 and CGR3 in the regulation of the hypocotyl growth and the elastic properties under low R:FR. (A) Length of the hypocotyls in response to low R:FR treatment. Seedlings were grown for 4 days in high R:FR and then for 3 additional days in low R:FR. Data of growth induced by low R:FR during the 3 days were normalized against the wild-type and expressed in log2FC. Significant differences (p<0.05*, p<0.001***) were determined according to Student's t-test. (B) Length of the hypocotyls in response to high and low R:FR treatments in Col-0 and cgr2cgr3. Seedlings were grown for 4 days in high R:FR before being transferred under low R:FR (blue bars) or kept in high R:FR (yellow bars) for 3 additional days. The bars show means in mm ± confidence intervals measured at 4 (4d), 5 (4d+1d) and 7 (4d+3d) days. Significant differences (indicated with letters) were determined according to one-way Anova followed by a multiple comparisons with Tukey's test. (C) Elastic properties of hypocotyl assessed under high and low R:FR treatment for Col-0 and cgr2cgr3.Hypocotyls were frozen and thawed then subjected to cyclic loading at 5 mN of force and the strain compared to the data obtained for the wild-type seedlings in Figure2. The average magnitude of strain incurred by seedlings grown in a high R:FR or low R:FR light regime after one (4d+1d) and three days (4d+3d) is shown. The bars show means in % ± SD (n>10 independent seedlings for Col-0 and n>5 independent seedlings for cgr2cgr3, at least five oscillations were made per seedling). Pairwise comparisons were made between the mutant and the wild-type using Welch t-test brackets indicated statistical tests that were made with significance p<0.1*, p<0.05** and p<0.01***.

Figure 5 .

 5 Figure 5. Changes of cell wall properties that occur in response to low R:FR are reduced in cgr2cgr3 (A,B) Cell wall properties in the middle part of the hypocotyl under high and low R:FR treatments for Col-0 and cgr2cgr3. Cell wall chemical bounds were analyzed by Fourrier-Transformed InfraRed (FTIR) microspectroscopy. For each hypocotyl, 6 spectra were collected in the middle part, avoiding the central cylinder, for at least 5 independent hypocotyls per condition. Baseline correction and data normalization were made for the absorbances between 1810 and 830 cm -1 (corresponding to the cell wall fingerprint, see Supplemental Figure S6). Pairwise comparison between high and low R:FR was made after 1 and 3 days treatments for Col-0 and cgr2cgr3 and significant differences were identified using Student's t-test for each wavelength. (A) All Student's t-values were plotted against wavelengths with horizontal lines referring to significant threshold for p<0.05 for Col-0 (left panel) and cgr2cgr3 (right panel). Student's t-values above +2 or below -2 indicate respectively an enrichment or an impoverishment of cell wall components in low compared to

  Figure1

Google Scholar: Author Only Title Only Author and Title

Acknowledgement

The authors wish to gratefully thank Prof. Kenneth Keegstra, Prof. Debra Mohnen, Prof.

Frederica Brandizzi and Prof. Jérôme Pelloux respectively for sharing seeds of the xxt, gaut, cgr and pme/pmei mutants used in this study. We also thank Dr. Christiane Nawrath, Dr.

Sylvester Mazurek and Dr. Gregory Mouille for their help in the analysis of the FTIR microspectroscopy. We thank the Swiss initiative in systems biology (SystemX.ch) and the University of Lausanne for the funding support. We nicely thank Prof. Cris Kuhlemeier for contributing to the funding acquisition and the co-supervising of the "Plant Growth 2 in a Changing Environment" project funded by the Swiss initiative in systems biology (SystemX.ch). We also thank him for his help in the project handing and for hosting Sarah Robinson, postdoc in his lab during the project.

FS, SR, EVS. Writing -Review & Editing: FS, SR, DR, CF

Funding information

This work was supported by grant "Plant Growth 2 in a Changing Environment" funded by the Swiss initiative in systems biology (SystemX.ch) to Cris Kuhlemeier (Bern), Didier Reinhardt (Fribourg) and Christian Fankhauser (Lausanne). Work in the Fankhauser lab was supported by the University of Lausanne.

Literature cited

Alonso-simón A, García-angulo P, Mélida H, Encina A, Álvarez JM, Acebes JL (2011) The use of FTIR spectroscopy to monitor modifications in plant cell wall architecture


Adam B Johnson
email: adambjohnson@uvic.ca

William Thompson

Kris Caputa

Frédéric Grandmont

Christian Marois

Tim Hardy

Joeleff Fitzsimmons

Olivier Lardière

Colin Bradley

Exoplanet Detection and Characterization: Development and Results of a New Generation Imaging Fourier Transform Spectrometer

Keywords: Imaging Fourier transform spectrometer, Michelson interferometer, fringe quadrature, closed-loop voice coil control, exoplanet imaging and characterization, adaptive optics

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

INTRODUCTION

The NEW EARTH laboratory team at the National Research Council Canada (NRC) Herzberg Astronomy & Astrophysics (HAA) observatory in Victoria BC Canada have been working on new high-contrast imaging technologies and ideas [START_REF] Lardière | Optical design and preliminary results of New Earth, first Canadian high-Contrast Imaging Laboratory Test Bench[END_REF]. The current project, the Subaru Pathfinder Instrument for Detecting Exoplanets & Retrieving Spectra (SPIDERS) [START_REF] Lardière | Design, Integration and Tests of SPIDERS: a Subaru Pathfinder Instrument for Detecting Exoplanets & Retrieving Spectra[END_REF] deploys many new technologies designed specifically for the detection and characterization of exoplanets using the 8.2m Subaru telescope on Maunakea, in Hawaii [START_REF]Overview of The Subaru Telescope[END_REF].

In addition to the identification of molecules in the atmospheres of exoplanets using mid to high spectral resolution, an imaging spectrograph can use low spectral resolution to optimize SDI post-processing and planet finding in a large field-of-view (FOV) with approaches like the fast atmospheric self-coherent camera technique (FAST) [START_REF] Gerard | Exoplanet Imaging Speckle Subtraction: Current Limitations and a Path Forward[END_REF] and new self-coherent camera (SCC) algorithms [START_REF] Thompson | Performance of the FAST Self Coherent Camera at the NEW-EARTH Lab and Simplified SCC Measurement Algorithm[END_REF]. Higher spectral resolution imaging around key bands, such as CH4 or CO, could also be used to search for planets hidden in the star speckle noise. Furthermore, at very high spectral resolution the IFTS can be used to do velocity mapping of emission lines. With its low to high dynamic resolution capability, the IFTS is positioned to be a powerful tool to perform cutting-edge exoplanet science.

OPERATIONAL PRINCIPALS

Before its use in exoplanet imaging, Fourier transform spectroscopy was and still is a commonly used process in industries that require the precision measurement and analysis of a material, compound, or light source. Commercially available devices like ABB's Fourier Transform Near-Infrared Process Analyzer FTPA2000-300 [START_REF]FTPA2000-300 FT-NIR Process Analyzer[END_REF] use a bright internal source to create a strong signal for spectral analysis of any sample that light can transmit through. Using this device on SPIDERS, we instead use an exoplanet system as the input signal to perform spectral analysis of the star and its companions.

THE MICHELSON INTERFEROMETER DESIGN

At the heart of the IFTS is a Michelson interferometer with two retroreflector mirrors attached to an arm on a flexural hinge that facilitates interference of an image along a changing optical path difference (OPD), figure 1. The interferometer scans continuously over an OPD window using a voice coil motor to position the arm in space, a helium-neon (HeNe) laser to provide positional feedback, and an internal white light to find the scan center (zero-OPD, or ZPD). An incoming chromatic (broadband) image is interfered with itself to produce an interferogram on the detector of a monochromatic camera. The interferogram recorded at each pixel is then Fourier transformed (FT) to recover the spectrum of the image for each pixel. The resulting wavelength specific images represent the spectral components (slices) of the input image and make up the data cube. Stacking and assigning colour to the data cube images can provide an insightful visualization of the original chromatic image.

CLOSED-LOOP VELOCITY CONTROL

Using the HeNe laser fringe signals, a quadrature algorithm was developed with the help of ABB to recover the OPD of the IFTS [START_REF] Zumberge | Resolving quadrature fringes in real time[END_REF][START_REF] Mark A Zumberge | Resolving quadrature fringes of interferometer signals in real time[END_REF], similar to the method used on SITELLE [START_REF] Drissen | SITELLE: a wide-field imaging Fourier transform spectrometer for the Canada-France-Hawaii Telescope[END_REF]. With a robust method to recover the position of the IFTS along its scan, a closed-loop controller was designed to ensure scan stability and repeatability over long-term operation. Without closed-loop control, external disturbances such as mechanical vibration or turbulent air pushing on the IFTS arm will cause the system to deviate from the commanded trajectory and significantly deteriorate the IFTS scan performance. Keeping the velocity constant over the duration of the scan is critical to ensuring each camera image gets an equal exposure time and are captured at near-equidistant OPD. Because the voice coil is driven through discrete position commands proportional to the current it is drawing, the regulated velocity command must be changed into a position command before it is used. Ultimately, the constant-speed motion during a scan is achieved by providing small linearly increasing position commands to the voice coil while taking advantage of the heavy IFTS arm that increases inertia and filters the discrete step motion. The controller block diagram is shown in figure 4 below. Various controllers were explored in simulation and on the bench including position-velocity cascade and pole-placement, but in the end, the velocity-current cascade controller shown in figure 4 was the simplest to tune and optimize on the bench with a constant positive or negative velocity input. The inner current controller loop is implemented via hardware and does not require any tuning. Although some FTS devices operate in step-scan mode to increase integration time at specific OPD, this system is designed to work at a constant speed only, also referred to as the continuous-scanning mode.

IMPLEMENTATION, PERFORMANCE, AND EARLY RESULTS

To acquire the position feedback, drive the voice coil, and implement closed-loop control for the IFTS system, custom electronics and software were developed. A printed circuit board (PCB) was designed to mount off-the-shelf analog-to-digital converters (ADC) to measure the fringe signals, a digital-to-analog (DAC) converter to command the voice coil current controller, and support for a microcontroller unit (MCU) to control the system. Every 10µs (or at a rate of 100kHz) the 16-bit ADCs measure and sends the analog fringe signals to the MCU, the MCU determines the current position, a new command is sent to the 16-bit DAC, and the current controller provides a new position command to the voice coil. A sheet metal enclosure was designed to house a power supply, fan, and PCB assembly while fitting comfortably on a 1U server rack shelf (< 1.75in tall). BNC connectors on the front allow the input or output of 3.3V triggers while a USB can be connected to set the scan speed and window serially from any PC, figure 5 (left). A custom cable connects the IFTS controller to the ABB FTS voice coil and fringe signal detectors, mitigating any addition of heat or vibration from the controller by housing it away from the system. The closed-loop controller was developed first in the NEW EARTH lab before being optimized on the SPIDERS bench for speeds between 0.36mm/s and 1.2mm/s, scanning back and forth indefinitely over ZPD. An OPD window from -10mm to 10mm or as small as 100µm anywhere within that range can be utilized for double-sided or single-sided scans. Using a scan speed of 0.36mm/s in an OPD window from -3mm to +3mm, the IFTS position and velocity response are shown in figure 6 below from left to right, respectively, for the system in open and closed-loop control. When the speed setpoint changes sign (the system reaches the edge of a scan window), the open-loop system takes over 2 seconds to settle and never fully settles due to external vibrations combined with its highly underdamped response. Furthermore, the open-loop control suffers from steady-state error and on average does not reach the scan speed setpoint, leading to longer than expected scan times. In contrast, the closed-loop system settles in about 35ms (or under 15µm of OPD) and minimized the benchtop vibrations seen in open-loop.

Linking the camera images to the OPD, the IFTS controller can either output a 3.3V trigger at equidistant OPD intervals with non-uniformly triggered camera exposures, or a non-equidistant OPD can be output in Angstroms over serial communication with uniformly triggered camera exposures. In either the equidistant OPD or non-equidistant OPD case, the camera images from a complete scan produce the raw interferogram. The interferogram at equidistant OPD intervals can utilize a standard fast Fourier transform (FFT) to recover the spectrum, while the uniform triggering at non-equidistant OPD intervals require a non-uniform FFT (NUFFT) to interpolate the interferogram and resample to use the standard FFT. Details on these operations are not discussed in this paper but can found in publications such as [START_REF] Christopher | Optical astronomical spectroscopy. Ch8.7 Fourier Transform Spectroscope (Michelson Interferometer[END_REF] and [START_REF] Houlihan | In: Application of the non-uniform fourier transform to nonuniformly sampled Fourier transform spectrometers[END_REF].

To evaluate the spectroscopic performance of the IFTS system, a SuperK COMPACT supercontinuum white light laser [START_REF] Superk | [END_REF] was used as a source on the SPIDERS bench with a C-RED 2 infrared camera [START_REF]VERY HIGH SPEED ULTRA LOW DARK SCIENTIFIC InGaAs INFRARED CAMERA, First Light[END_REF]. The camera took images at equidistant OPD locations every 400nm along a -3mm to +3mm window at a constant speed of 0.36mm/s, requiring an average frame rate of 900Hz. The 15, 000 images recorded by the monochromatic camera produce the interferogram -a subset of black and white images around the ZPD shown in figure 7 on the left -where each pixel is Fourier transformed (FT) to produce a wavenumber spectrum at each pixel in the FOV. The data cube of wavenumber (or wavelength) specific images can be stacked and coloured to produce the original chromatic input image (figure 7, right), with wavelength from red (long) to blue (short). Using the adaptive optics (AO) system within SPIDERS, speckle suppression methods like Thompson 2023 [START_REF] Thompson | High-Spectral Resolution Dark Holes: Concept, Results, and Promise[END_REF] can be used to remove the bright light directly surrounding the star (or benchtop light source in this case) to see potentially hidden planets that might exist. The coloured image in figure 7 illustrates how a deformable mirror (DM) can statically correct the image and allow us to see closer to a bright source, discussed in Thompson 2023 along with an approach to dynamically corrected atmospheric effects during a real observation. Analysing the bright regions in the FOV surrounding the core of the image (to negate chromatic effects caused by the coronagraph removing the central core light, currently installed on SPIDERS), an average 2D interferogram and wavelength spectrum of the light source can be acquired, shown in figure 8 above, respectively. The obtained spectrum confirms that the C-RED 2 camera is only sensitive between 0.9 and 1.7µm, with a peak intensity around 1.06µm. The spectral resolution of this 3mm scan is around R6, 000, where a possible 10mm scan could produce an R20, 000 spectrum, or R100 for a 100µm scan. The interferogram can always be trimmed in post processing to reduce the resolution, but a longer scan must be performed to increase it. During this initial test on the SPIDERS bench, it was discovered that the final folding mirror was not optimal for the infrared waveband we were imaging in and resulted in the strange and lumpy spectrum we see in figure 8, rather than the unique spectrum published by the laser manufacturer [START_REF] Superk | [END_REF]. Verifying the measured peak intensity and confirming the camera sensitivity range shows that the IFTS controller and system are working as expected.

CONCLUSIONS AND FUTURE WORK

Initial results of the IFTS system on SPIDERS indicate that we are able to recover high-resolution spectra over a large FOV on the bench. Tests using a supercontinuum white light source and equidistant OPD intervals proved the success of the new IFTS system and its ability to provide highly-stable motion for long-term continuous-scanning operation. With the ability to reprogram the scan speed and window for use with different triggering modes (equidistant or non-uniform OPD), the system is able to provide unique capabilities for current state-of-the-art and future high-contrast imaging instruments to use for exoplanet imaging and characterization. Current development with non-equidistant OPD serial output and uniform triggering is proving to be easier to integrate with cameras and the rest of the system, while adding some complexity to the post processing. With the planned commissioning of SPIDERS in 2024, we are refining the data cube processing algorithm and system for use over long observing nights and more detailed performance and analysis publications.

Figure 1 .

 1 Figure 1. A scanning Michelson interferometer receives an image and outputs its interferogram.

Figure 2 .

 2 Figure 2. A closed-loop velocity-current cascade controller to regulate the voice coil motor scan speed.

Figure 3 .

 3 Figure 3. The custom IFTS controller system (left) and early experimental setup in the NEW EARTH lab (right).

Figure 4 .

 4 Figure 4. The open and closed-loop response in position and velocity for a 0.36mm/s continuous-scan.

Figure 5 .

 5 Figure 5. The interferogram produced and recorded by the IFTS (left) and the processed broadband image (right).

Figure 6 .

 6 Figure 6. The 2D interferogram (left) and wavelength spectrum (right) of a benchtop supercontinuum white light source.


Nicolas Cavrel
email: nicolas.cavrel@univ-grenoble-alpes.fr

Damien Pellier
email: damien.pellier@univ-grenoble-alpes.fr

Humbert Fiorino
email: humbert.fiorino@univ-grenoble-alpes.fr

Efficient HTN to STRIPS Encodings for Concurrent Planning

Keywords: Automated Planning, Hierarchical Plannning, Concurrent Planning, STRIPS Planning

The Hierarchical Task Network (HTN) formalism is used to express a wide variety of planning problems and many techniques have been proposed to solve them. A particular technique is to encode hierarchical planning problems as classical STRIPS planning problems. One advantage of this technique is to benefit directly from the constant improvements made by STRIPS planners. However, there are still few effective and expressive encodings. In this paper, we present the first HTN to STRIPS encodings allowing to generate concurrent plans. We show experimentally that these encodings not only outperform previous approaches on hierarchical IPC benchmarks but also produce more expressive solution plans.

I. INTRODUCTION

The Hierarchical Task Network (HTN) formalism [START_REF] Erol | Complexity Results for HTN Planning[END_REF], [START_REF] Bercher | A Survey on Hierarchical Planning -One Abstract Idea, Many Concrete Realizations[END_REF] is used to express a wide variety of planning problems in terms of decompositions of tasks into subtasks. HTN planning is used in many applications as, for instance, in task allocation for robot fleets [START_REF] Milot | Solving Hierarchical Auctions with HTN Planning[END_REF], video games [START_REF] Menif | SHPE: HTN Planning for Video Games[END_REF] or industrial contexts such as software deployment [START_REF] Georgievski | Cloud Ready Applications Composed via HTN Planning[END_REF]. One possible explanation for this popularity is that HTN formalism usually fits better for realworld applications and domain experts' mindset: a HTN planning problem is expressed as a set of tasks to achieve rather than an objective state to reach, and the "processes" achieving these tasks as methods, that is to say task decompositions into "simpler" subtasks.

Many techniques are used to solve hierarchical planning problems. The first technique is to develop ad-hoc HTN planners, e.g., [START_REF] Bercher | Hybrid Planning Heuristics Based on Task Decomposition Graphs[END_REF], [START_REF] Nau | SHOP2: An HTN planning system[END_REF]. The second technique consists in encoding HTN problems into other classical formalisms such as SAT problems, e.g., [START_REF] Schreiber | Tree-REX: SAT-Based Tree Exploration for Efficient and High-Quality HTN Planning[END_REF]- [START_REF] Schreiber | Lilotane: A Lifted SAT-based Approach to Hierarchical Planning[END_REF], constraint programming problems, e.g., [START_REF] Vidal | Branching and pruning: An optimal temporal POCL planner based on constraint programming[END_REF] or simply as STRIPS planning problems that can be solved by classical STRIPS planners. This last technique has the advantage to benefit directly from the constant improvements of STRIPS planners. To our best knowledge, only three HTN to STRIPS encodings have been published so far [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF]- [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF]). These translations aims at solving HTN problems by producing a sequential plan, meaning that the resulting plan is a sequence of singular actions performed one at the time. However, in the general case and in particular in multi-agents planning problems, having a concurrent plan where several actions can be performed simultaneously or whose order of execution can be determined at the time of the plan execution is much more efficient and flexible, if not required.

In the literature, there are two approaches producing concurrent plans. The first one is to use plan-space planning. This approach refines an initial task network into a solution one by resolving the flaws of the initial task network, e.g, [START_REF] Bercher | Hybrid Planning Heuristics Based on Task Decomposition Graphs[END_REF]. The resulting plan is a set of actions partially ordered by either causal relationships or precedence constraints inherited from the HTN decomposition. This approach produces very flexible plans, however it can quickly become intractable.

The second approach is to first produce a sequential plan and to de-order it into a partially ordered plan [START_REF] Waters | Plan Relaxation via Action Debinding and Deordering[END_REF], [START_REF] Bäckström | Computational Aspects of Reordering Plans[END_REF]. This approach benefits from the efficiency of sequential planners and can then de-order the plan in polynomial time. The main disbenefit of this method is the quality of the resulting plan: while in a sequential context the optimal plan is the one containing the fewer number of actions, the optimal plan in a concurrent context could contain more actions but performed simultaneously. Hence, a sequential planner returning the sequentially optimal solutions first would not necessarily obtain the optimal concurrent solutions by de-ordering. The second issue with de-ordering approaches is that they are not directly applicable to HTN problems as they only de-order the plan while only maintaining the plan executability, but do not maintain the hierarchical constraints inherited from task decomposition.

To deal with this issue, we propose in this paper two contributions: (1) a search procedure called CPFD (Concurrent Partial Forward Decomposition) that produces and guarantees concurrently optimal plans, and (2) two HTN to STRIPS encodings of the CPFD procedure based on the translations proposed in [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF], [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF]. The translated problems can be solved by any classical sequential planner and produce concurrently optimal plans. The rest of this paper is organized as follows. Section 1 defines the problem statement. Section 2 presents the Concurrent Partial Forward Decomposition procedure (CPFD). Section 3 introduces the key concepts used in the encodings, and Section 4 the two concrete STRIPS encodings of CPFD, called sCTHD (Static Concurrent Task Holders Decomposition encoding) and pCTHD (Push Concurrent Task Holders Decomposition). Finally, in the last section, we compare both CTHD and pCTHD with the translations proposed in [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF], [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF], which are the current state-of-the-art of HTN to STRIPS translations.

A. STRIPS Planning Problems

A STRIPS planning problem is a tuple P = (L, A, I, G) where L is a finite set of logical propositions, A is a finite set of actions, I ⊆ L is the initial state, and G ⊆ L is the goal.

An A state s is a set of logical propositions. The result of applying an action a to state s is a state s ′ defined by the transition function s ′ = γ(s, a) = (s -del(a)) ∪ add(a) if pre(a) ⊆ s, and undefined otherwise. Let an action layer π be a set of pairwise independent actions, and pre(π) = a∈π pre(a). add(π) and del(π) are defined in the same way. By extension s ′ = γ(s, π) = (s -del(π)) ∪ add(π) if pre(π) ⊆ s, and undefined otherwise. Note that the actions of π can be executed concurrently or in any sequential permutation and still yield exactly the same state s ′ .

A layered plan Π is a sequence of action layers ⟨π 1 , . . . , π n ⟩. Let γ(s, Π) = γ(γ(s, π 1 ), ⟨π 2 , . . . , π n ⟩). π i precedes π j if i < j. Likewise a i ≺ a j if a i ∈ π i , a j ∈ π j , and π i precedes π j . A layered plan Π is a solution to a STRIPS planning problem P = (L, A, I, G) iff G ⊆ γ(s, Π) (see Fig. 1).

B. HTN Planning Problems

We build on STRIPS planning problem definition to define a HTN planning problem as a tuple P = (L, T , A, M, I, tn) where L is a finite set of logical propositions, T is a finite set of tasks, A is a finite set of actions, M is a finite set of methods, I ⊆ L is the initial state and tn the initial task network. There are two kinds of tasks: primitive tasks that can be resolved by a STRIPS action a = (name(a), pre(a), add(a), del(a)) ∈ A , and compound tasks, which can be recursively decomposed into either primitive or compound tasks by a method m ∈ M .

A task network is a tuple tn = (T, ≺, α) such that T is a finite set of task symbols, α : T → T maps task symbols to tasks in T , and ≺ is a partial order over T representing precedence constraints:

t precedes t ′ if t ≺ t ′ , or equivalently (t, t ′ ) ∈≺. ≺ is transitive. A task α(t), t ∈ T is trailing if ∀t ′ ∈ T , (t ′ , t) /
∈≺ (t has no predecessor in T ). trail(tn) will denote the set of trailing tasks in T . Symmetrically, a task α(t)(t ∈ T ) is a last task if ∀t ′ ∈ T, (t, t ′ ) / ∈≺ (t has no successor in T ).

A method is a tuple m = (task(m), pre(m), tn(m)) where task(m) is the compound task decomposed by the method m, pre(m) is the method's preconditions and tn(m) is a task network. A method m is a resolver of a compound task τ if task(m) = τ . Note that a given compound task can have various methods to resolve it.

An action a = (name(a), pre(a), add(a), del(a)) can be applied to resolve a primitive task α(t) of the initial task network tn if t is trailing, name(a) = α(t) and pre(a) ⊆ I. The result is a new problem P ′ = (L, T , A, M, I ′ , tn ′ ) where I ′ = γ(I, a) and tn ′ = (T \ {t}, {(t ′ , t ′′ ) ∈ ≺ | t ′ ̸ = t}, α\(t, α(t))). In a symmetrical manner, a method m = (task(m), pre(m), tn(m)) can be applied to resolve a compound task α(t) of the task network tn if t is trailing, task(m) = α(t) and pre(m) ⊆ I. The result of applying the method m with tn(m) = (T m , ≺ m , α m ) is a new problem P ′ = (L, T , A, M, I, tn ′ ) where tn ′ = (T ′ , ≺ ′ , α ′ ) and:

T ′ = (T \ {t}) ∪ T m ≺ ′ = {(t ′ , t ′′ ) ∈ ≺ | t ′ ̸ = t} ∪ ≺ m ∪ {(t ′′ , t ′ ) ∈ T m × T | (t, t ′ ) ∈≺} α ′ = {(t ′ , α(t ′ ))| t ′ ∈ T \{t}} ∪ α m
In other words, in ≺ ′ we keep all the precedence constraints of ≺ that do not involve t, add all the precedence constraints in ≺ m , and propagate precedence transitivity between ≺ and ≺ m through t.

Applying either an action a or a method m to resolve a task in a planning problem P is called a progression. If t p ∈ T is a primitive task of P , resolving t p by a is a progression denoted P → a tp P ′ . Similarly, if t c is a compound task of P , decomposing t p using m is a progression denoted P → m tc P ′ . To conclude, a layered plan Π = ⟨π 1 , . . . , π n ⟩ is a solution for a HTN planning problem P = (L, T , A, M, I, tn) if (1) a sequence of progressions exists that transforms P into P ′ = (L, T , A, M, I ′ , (∅, ≺ ′ , α ′ )) (i.e. all the tasks of P have been resolved), and (2) a i ≺ a j ⇔ task(a i ) ≺ ′ task(a j ) (i.e. action precedence constraints in the layered plan Π are equivalent to the primitive task precedence constraints in P ′ ). In section 2, we show how CPFD builds a layered solution plan by applying progressions on P .

C. HTN to STRIPS Encoding Problems

The Hierarchical Task Network (HTN) formalism has been shown to be more expressive than STRIPS [START_REF] Erol | Complexity Results for HTN Planning[END_REF]. This means that any STRIPS problem can be formulated as a HTN problem but not the other way round. Therefore, the translation of a HTN problem into a STRIPS problem is not always possible. However, it has been proven by [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF] that this translation is possible if the size of the solution task network can be bounded. Given a HTN problem and a sequential solution plan, the minimum (respectively maximum) bound is the smallest (respectively largest) number of tasks in any task network visited by the sequence of progressions carried out to find this solution plan.

In practice, not all problems have a maximum bound, but all solvable problems have a minimum bound. These bounds are not directly related to the length of a problem solution, though the minimum progression bound is smaller than the optimal plan length1 .

Our encoding also assumes the bound existence. In addition and as [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF] we make three other assumptions on the HTN problem to encode:

1) In the initial HTN problem, T is singleton. Otherwise, it is always possible to add a root dummy-task and a dummy-method to decompose it. 2) Every method of the HTN problem has a task network with a single last task. If a method does not have it, a dummy-task with no successor is added to the task network. 3) Methods have no preconditions. Otherwise, a trailing dummy action is added to the method task network with no effects and the method's preconditions. These assumptions are made without loss of generality and will simplify the notations in the following.

III. CONCURRENT PARTIAL-ORDER FORWARD DECOMPOSITION

In this section, we introduce the procedure called CPFD (Concurrent Partial-order Forward Decomposition) (see Alg. 1) on which our encoding is based. The objective is to give on overview of our encoding and its properties. The encoding of this procedure as a STRIPS planning problem is presented in the next section.

CPFD is an adaptation of PFD (Partial-order Forward Decomposition) [START_REF] Ghallab | Automated Planning: Theory and Practice[END_REF] procedure to output layered plans (see Figure 1). It takes as input a HTN problems and generates layered plans. Keep in mind that a layered plan is a solution of a HTN problem if actions resolve all the tasks of the task network, and if the ordering constraints of the actions in the layered plan satisfy the precedence constraints in this task network. Therefore, CPFD has to solve recursively the trailing tasks as in the PFD procedure. The difference lies on the resolution of the primitive tasks: while PFD adds actions to a sequential plan, CPFD adds them to layers of independent actions.

More precisely, CPFD takes as input four parameters: a HTN problem P = (L, T , A, M, I, (T, ≺, α)), a layered plan Π, the index i of the current layer π i and τ the set of primitive tasks resolved by the actions in π i . At the first call of CPFD, Π is an empty layered plan, i = 0 and τ = ∅. At each recursive call, CPFD checks if the list of tasks T of the task network is empty, i.e., no more tasks have to be resolved. If this condition is satisfied, the layered plan Π is a solution to P and Π is returned. Otherwise, a task t ∈ T is non deterministically selected among the trailing tasks (tasks without predecessors with respect to precedence constraints), and a resolver is non deterministically chosen. As in the PFD procedure, there are two ways to resolve t depending on whether t is primitive or compound.

• Case 1. (Primitive task) The resolvers of t are actions a whose preconditions are satisfied in the current state I and that are independent of all the actions already planned in the current layer π i . Two cases are possible: either t has no resolvers and the current layer π i is empty, meaning no action can solve t in the current state I, and CPFD returns FAILURE. Or t has a resolver but this resolver is not an independent action in the current layer: then CPFD moves to the next layer by applying to the current state all the actions already committed in the current layer.

The idea is that t could be resolved by an action in a next state concurrently with other independent actions. Obviously, if t has an independent resolver a, a is added to the current layer π i and t is added to the set of resolved primitive tasks τ . • Case 2. (Compound task) CPFD computes all the methods resolving the compound task t, i.e., whose preconditions are satisfied in the current state I. If there is no method, then t cannot be solved, and CPFD returns FAILURE. Otherwise, CPFD non deterministically chooses a method m decomposing t, updates the task set and the ordering constraints accordingly. CPFD is then called recursively until the tasks to solve in P are emptied (T = ∅, line 2 in Algo. 1) or a failure condition is met (line 9 and 24 in Algo. 1).

CPFD is sound and complete. a) Proof sketch (Soundness): All produced plans come from a progression of the initial task network, thus there is a sequence of task decompositions that produces the primitive tasks in the solution plan. Furthermore, since a primitive task can be added to a layer if the corresponding node is trailing, all tasks preceding the one added have been planned on previous layers. Thus, the ordering constraints in ≺ are satisfied in the solution plan. Thus output plans are sound.

b) Proof sketch (Completeness): We will show that CPFD is complete based on the demonstration that PFD is complete. Let P = (L, T , A, M, I, tn) be a HTN problem and Π = ⟨π 1 , . . . , π n ⟩ a layered solution plan of P . Let us show that there is a sequence of recursive calls of CPFD outputting Π. First, let us note that given a concurrent layer π = {a 1 , . . . , a k }, any linearization of that layer ⟨a γ(1) , . . . , a γ(k) ⟩ where γ is a permutation function of {1, . . . , k}, is a sequence of actions that can be applied to the same states as π. This is due to the mutual independence property of the actions within a concurrent layer. From there, any sequential plan produced by linearizing every layer of Π (by taking any permutation function on the layers) is a sound plan that also solves P . Let us consider the linearization Π l defined by the n permutation functions γ 1 , . . . , γ n . Since PFD is a complete algorithm, there

≺ ′ = {(t ′ , t ′′ ) ∈ ≺ | t ′′ ̸ = t} ∪ ≺m ∪ 17 {(t ′′ , t ′ ) ∈ Tm × T | (t, t ′ ) ∈≺}
≺← {(t ′ , t ′′ ) ∈ ≺ | t ′′ ̸ = t} ∪ ≺m ∪ 30 {(t ′′ , t ′ ) ∈ Tm × T | (t, t ′ ) ∈≺} 31 return CPFD(P, Π, i, τ )
is a sequence of recursions of PFD that outputs Π l . At each recursion, PFD and CPFD either solve a trailing abstract task, or a trailing primitive task. While they solve abstract tasks the same way, PFD solves a primitive task by adding an action resolving it to the head of the plan, meanwhile CPFD adds the action resolving the task to the concurrent layer at the head of the plan. If the task cannot be resolved, PFD returns FAILURE while CPFD tries to add a new concurrent layer to the plan. Thus, for each recursive PFD call resolving an abstract task, the analogous call of CPFD is to solve the same abstract task. Each recursive call of PFD resolving a primitive task is analogous to a CPFD call adding the action to the current concurrent layer. However, CPFD requires extra recursive calls to switch layers.

IV. PLANNING THE PLANNING

In the following section, we present the basic concepts used to encode the CPFD procedure into STRIPS planning problems.

A. Taskholder and Current layer Encoding

The CPFD procedure resolves recursively trailing primitive tasks and compound tasks by modifying the initial task network of the problem until the task network contains an empty set of tasks. To encode this procedure, we need first to model a task network with STRIPS. To achieve this, we use the concept of taskholder introduced first by [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF]. A taskholder is a STRIPS object that will act as a container for a task. By way of extension, a task network is modeled by a stack of taskholders and by fluent propositions modelling the ordering constraints between the tasks contained in the taskholders. The number of taskholders has to be fixed before translating the HTN problem. Similarly to HTN2STRIPS, our encodings require at least as many taskholders as there are tasks in the largest explored task network, thus the number of taskholders in our encodings can be estimated as described in HTN2STRIPS [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF].

In addition, we model the current layer from CPFD by a set of fluent propositions. Each proposition denotes whether or not an action a ∈ A is planned in the current layer. The main idea is to allow an action to be added to the current layer only if every action contained in the current layer is independent with the newly added one.

A graphical representation of the initial structure of a problem, i.e., taskholders and current layer, is given in Figure 2.

B. Encoding CPFD as STRIPS Actions

To encode the dynamic of the CPFD procedure (Alg . 1) we need to define three types of STRIPS actions: (1) the first type of actions resolves a trailing compound task and update the current task network according to a method decomposition, (2) the second type of actions resolves a primitive task and add an action to the current layer, and (3) the last type of actions is the one switching layers, making the algorithm build the next layer of the solution plan. The planning process will choose one action among the three types. Applying one of these actions is equivalent to one recursive call of the CPFD procedure:

1) Actions for resolving compound tasks: These actions reflect the decomposition of a compound task into subtasks according to a method. It corresponds to the lines 27 to 30 of the CPFD procedure. In order to apply these actions, the taskholder must be unconstrained and there must be enough empty taskholders in the stack. An example of taskholder usage is represented on Figure 3. The substasks of the method M 1 decomposing T 0 are added to the stack of taskholders and the task T 0 is replaced by the last task of the current task network. As M 1 has no last task, the no-op action is used. Finally, the ordering constraints are set over the taskholders. 2) Actions for resolving primitive tasks: In CPFD, trailing primitive tasks are resolved by adding their corresponding action into the current layer (lines 21 to 23 of Alg. 1). In our encodings, we define corresponding actions that take as parameters an unconstrained taskholder containing a primitive task which add its corresponding action to the current layer if no concurrent action is already in it. An example of application is displayed on Figure 4. The taskholder th2 is unconstrained and contains a primitive task t1 that can be resolved by the action a(t1). The task is resolved by adding a(t1) to the current layer, th2 is emptied and marked as resolved.

As in Alg. 1, the constraints implied by the resolved taskholder are not removed yet. They will be removed when moving to the next layer. 3) Action for switching of plan layer: This action corresponds to switching to the next layer. This action empties the current layer, setting up the next one in the solution plan. It also removes the constraints implying the resolved taskholders. This action can be applied with no precondition and works as displayed in Figure 5. In this example, only th2 is marked as resolved. After the application of the action, the constraints implying th2 are removed, so the constraint between th2 and th1 is deleted, additionally th2 is unmarked as resolved and set as empty. Then the current layer is emptied by removing all actions in it.

V. CONCURRENT TASKHOLDER DECOMPOSITION ENCODINGS

In this section, we present two encodings of the CPFD procedure based on the previous introduced concepts, called respectively Static Concurrent TaskHolder Decomposition (sC-THD) and Push Concurrent TaskHolder Decomposition (pC-THD). The main difference of these encodings relies in the taskholders usage. The first encoding called sCTHD constrains the planner to use the taskholders in an increasing order according to the static relationship defining the taskholders stack. The second encoding called pCTHD (Push CTHD) always sets the newly added tasks into the last taskholders and uses the concept of Push action defined in [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF]. Similarly to HTN2STRIPS, both proposed encodings depend on an integer parameter, the progression bound denoted b in the rest of the paper representing the number of taskholders.

In the remainder of this section, we will first present the predicates used to model the STRIPS problem that are common to both encodings. Secondly, we will present the encoding of the initial state and the goal, which are also common to both encodings. Finally, we will present the actions that encode the CPFD procedure that are specific to the encodings.

A. Predicates Definition

Our two encodings, sCTHD and pCTHD, model the CPFD procedure. In that regard, they share the predicates related to the taskholders stack, to the ordering constraints and to the current layer modelling. They also have specific predicates that are related to their taskholders management. In the following, every predicate is used by both sCTHD and pCTHD unless specified otherwise.

• (not constraint ?th1 ?th2 -taskholder) represents the fluent constraints over the taskholders. The predicate is inverted for convenience, so when the proposition (not constraint th1 th2) is false, it means that the task contained in th1 must be planned before the task contained in th2. • (empty ?th -taskholder) represents the fact that a taskholder is empty. The proposition (empty th) is true if the taskholder th does not contain a task. • (in ?t -task ?th -taskholder) is the predicate representing whether or not the task ?t ∈ T is set in the taskholder. The proposition (in t th) is true if t is set in th. • (not planned ?a -action) is true if a is not planned in the current plan step.

• (resolved ?th -taskholder) is a predicate representing whether or not a taskholder has been resolved. So the proposition (resolved th) is true if the taskholder th has been resolved. • (prec th ?th1 ?th2 -taskholder) is a predicate defining the static relationship between the taskholders. The proposition (prec th th1 th2) is true if th1 is preceding th2 in the stack. In the following, this order will be fixed, and for all 0 ≤ i, j < b the proposition (prec th th i th j ) will be true if and only if i ≤ j. This predicate is specific to sCTHD. • (next ?th -taskholder) is a predicate used to denote the taskholder prioritized for the next push action. This predicate is specific to pCTHD.

B. Initial and Goal State Encoding

The initial state of the translated problems is defined by setting the initial task into the first taskholder. The remaining taskholders are set as empty and ordered in a stack. As there is no constraint over the taskholder yet, all constraint predicates are initialized accordingly.

I ′ = I ∧ (in task 0 th 0 ) ∧ 1≤i<b (empty th i ) 0≤i,j<b (not constraint th i th j ) ∧ 1≤i<b (prec t th i-1 th i ) ∧ a∈A (not planned a)
For the goal state, the problem is solved when all taskholders are empty, meaning that all tasks are planned, and when the goal state is reached. Then we have:

G ′ = G ∧ p-1 i=0 (empty th i ) C.

sCTHD Actions Encoding sCTHD generates the set of actions A

′ = A c ∪ A p ∪ A l
where A c is the set of actions resolving compound tasks, A p the set of actions resolving primitive tasks and A l the set of actions switching plan layers:

• Actions resolving compound tasks:

Let m = (task(m), pre(m), tn(m)) and (task 1 , task 2 , . . . , task k ) the subtasks in tn. We assume that task k is the last task of tn. For all methods m ∈ M there is an action a m ∈ A c with k parameters (?th 1 , ?th 2 , . . . , ?th k ) defined as follows:

-pre(a m ) = (in task(m) ?th 1 ) ∧ b-1 i=0 (not constraint th i ?th 1 ) ∧ k i=2 (prec th ?th i ?th i+1 ) ∧ k i=2 (empty ?th i ) -add(a m ) = k i=2 (in task i ?th i ) ∧ (in task k ?th 1 ) -del(a m ) = k i=2 (empty ?th i ) ∧ taski≺taskj (not constraint ?th i ?th j ) ∧ k i=2 (not constraint ?th i ?th 0 )
Note that the k-1 last taskholder parameters are required to be ordered according to the static relationship defined by the prec th predicate. For instance, if three new taskholders are required to decompose the task in th6, (th6 th2 th4 th7) is a valid combination of parameters, while (th6 th2 th5 th3) is not.

• Actions resolving primitive tasks:

For all actions a ∈ A there is an action a p ∈ A p with one parameter: a taskholder containing p and denoted ?th.

The action is defined as follows:

pre(a p ) = pre(a) ∧ (in task(a) ?th) ∧ b-1 i=0 (not constraint th i ?th) ∧ t∈nInd(p) (not planned ?a) add(a p ) = add(a) ∧ (empty ?th) ∧ (resolved ?th) del(a p ) = del(a) ∧ (not planned ?a)

• Action switching layers:

A l is composed of one conditional action a l with no parameter. This action has a non conditional part: emptying the current layer, and a conditional part: unconstraining and making the resolved taskholders available for a new use. It is defined as follows:

pre(a l ) = ∅ add(a l ) = a∈A (not planned ?a) ∧ ∀(?th -taskholder) when (resolved ?th), b-1 i=0 (not constraint ?th th i ) del(a l ) = ∅

D. pCTHD Actions Encoding

The pCTHD encoding generates the set of action A ′ = A c ∪ A p ∪ A l ∪ A P ush . pCTHD encodes the CPFD procedure the same way as CTHD does, in that regard the sets of actions encoding the primitive tasks resolving A p and action for the layer switch A l are defined the same way as in CTHD. pCTHD manages the taskholders as the Push version of HTN2SAS does [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF]. Then we have:

• Actions resolving compound tasks: Let m = (task(m), pre(m), tn(m)) and (task 1 , task 2 , . . . , task k ) the subtasks in tn, task k denotes the last task of tn. For every method m ∈ M there is an action a m ∈ A c with one parameter (?th -taskholder) defined as follows:

pre(a m ) = (in task(m) ?th)

∧ b i=1 (not constraint th i ?th 1 ) ∧ k-1 i=1 (empty th b-i+1 ) -add(a m ) = k-1 i=1 (in task i th b-i+1 ) ∧ (in task k ?th) -del(a m ) = k-1 i=1 (empty th b-i+1 ) ∧ taski≺taskj (not constraint ?th b-i+1 th b-j+1 ) ∧ k-1 i=1 (not constraint th b-i+1 ?th)
In pCTHD, the subtasks inherited from a method decomposition are always set in the same taskholders (the last ones). This allows the method actions to only have one parameter, thus reducing the number of operators generated.

• Push Actions:

For every task t ∈ T , and for every taskholder index 2 ≤ k ≤ b there is a push action p k t ∈ A p defined as follows:

pre(

p k t ) = (in t th k ) ∧ (empty th k-1 ) ∧ b i=1,i̸ =k ¬(next th i ) -add(p k t ) = (in t th k-1 ) ∧ (empty th k ) b i=1
(not p recedes th k th i ) when (empty th k-2 ), (next th k-1 ) del(p k t ) = (next th k ) ∧ (empty th k-1 ) ∧ (in t th k ) ∧ ∀(?th -taskholder) : when ¬(not p recedes ?th th k ), b-1 i=0 ¬(not precedes ?th th k-1 ) when ¬(not p recedes th k ?th), b-1 i=0 ¬(not precedes th k-1 ?th) A Push action moves a task and its constraints from a taskholder to the preceding one in the stack. Note that the push actions rely on conditional effects, allowing for a much more compact encoding.

VI. EXPERIMENTATIONS AND RESULTS

In this section we present the experiments and results obtained to evaluate sCTHD and pCTHD efficiency. We compare our encodings with the two other known encodings: HTN2STRIPS and HTN2SAS encodings [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF], [START_REF] Behnke | Making Translations to Classical Planning Competitive With Other HTN Planners[END_REF]. Note that these encodings are not able to generate concurrent plans unlike our encodings. Our aim is to show how a concurrent procedure can perform against non concurrent ones, both on problems with totally ordered solution plans and problems with concurrent plans. Hence we selected 7 domains from the IPC partially ordered benchmarks that can have concurrent solution plans, and, in addition, a domain that is susceptible to concurrent actions, Miconic. We also added concurrent version of sequential domains where additional agents can perform the tasks simultaneously (nameConc represents the concurrent version of the domain name).

A. Experimental Setup

We ran all experiments on a single core of a Intel Core i7-9850H CPU using the Fast Downward library [START_REF] Helmert | The Fast Downward Planning System[END_REF] with enforced hill climbing and then lazy greedy search with Fast Forward heuristics [START_REF] Hoffmann | The FF Planning System: Fast Plan Generation Through Heuristic Search[END_REF]. All experiments were set a limit of 8GB of RAM over 600 seconds. We compared all four encodings according to two criteria: 1) Solving time: We measured the time spent by Fast Downard to find a solution to the translated problems.

We perform an iterated search over the progression bound until a solution is found. 2) Plan quality: As we want to demonstrate the efficiency of our approach at producing concurrent plans, we measure the makespan of the solution output by the solving of the translated problems. We compared these encodings by scoring them relatively to each other. The score of an encoding k over the domain d with a set of instances P d is defined as:

s d (k) = 1 |P d | i∈P d min e∈encodings (score(e, i)) score(k, i)
where score(k, i) is the score measured of the encoding k on the instance i. The results are displayed on Tables I and II.

B. Solving Time

Table I represents the results of our experimentations with regards to the solving time. On the Satellite and Transport domains sCTHD is the most efficient. On the Rover and Blocksworld domains, HTN2SAS Push is dominating the other encodings. This discrepancy displays the main difference between the taskholder management and the Push management. As Push encodings decompose subtasks in the last taskholders, these encodings perform worst on tail-recursive problems such as Satellite and Transport. On the other hand, sCTHD does not suffer from this and has the same performances whatever the problem structure. However, Push encodings are very efficient on head-recursive problems or problems with low recursivity as the conditionnal Push actions are rarely needed, hence representing the problem in a very compact and almost non conditional way. This efficiency is apparent on the Rover, Blocksworld and Miconic domains.

C. Plan Quality

Table II represents the results concerning the makespan of the solution plans. As we can see it on this table, our encodings obtain the best results on every domain, followed by the pCTHD encoding on every domain too. Obviously this is due to the fact that these encodings are able to produce concurrent plans, and thus to reduce the makespan of the solution. Note however that sCTHD and pCTHD can increase the concurrency of the solution plan by increasing the number of taskholders. This is not apparent on our experimentations as the tests end at the first valid solution (hence at the lowest valid number of taskholder). The effect of increasing the number of taskholders in our encodings over the resulting makespan is displayed in Figure 6 on a typical problem from Satellite. As displayed on the figure, sCTHD cannot find a solution until it reaches the minimal taskholder number to form a solution. Then the makespan of the solution plan decreases as the number of taskholders increases. Indeed, the more taskholders are available, the more concurrent tasks can live simultaneously in the progression network, and the more possibilities are offered to the STRIPS planner. However, increasing the number of taskholders has a negative effect on the solving time. The more taskholders, the more complex is the translated problem. Note that increasing the number of taskholders cannot have a negative impact on plan quality: the more taskholders there are, the more reachable through progression the task networks are, hence the more concurrent actions added simultaneously to the current layer there are.

Finally, on some instances, the maximum size of progression can be bounded. Using this bound as progression bound will lead sCTHD and pCTHD to explore and output the solution plans with the smallest makespan as every progression network can be represented in the taskholder stack. An algorithmic method to estimate this bound has been proposed in [START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF].

D. Discussion on CTHD optimality

Two factors affect the optimality of the CTHD encoding: the first is the number of taskholders used in the encoding and the second is the cost associated to each translated action. Having more taskholders allows for more primitive tasks to live simultaneously within the taskholder stack. Thus there are more opportunities for concurrent tasks to be resolved within the same layer. The makespan-optimal solution can be obtained only if enough taskholders have been encoded. Figure 6 shows the effect of increasing the number of taskholder on the makespan of the solution. The cost of the translated actions allows to guide the search procedure towards a better quality solution: finding the makespan-optimal solution means finding the plan with the smallest amount of layers within it. By increasing the cost of the actions switching layers, the search procedure is guided towards the better plans.

VII. CONCLUSION AND FUTURE WORKS

In this article, we have presented a new HTN procedure, CPFD, solving HTN problems with layered solution plans. We have proposed two HTN to STRIPS encodings of this procedure that can be solved by any STRIPS planner. Then we have showed experimentally that our translations perform well comparatively to the state of the art approaches, and more importantly produce concurrent solution plans. However, our representation of the concurrency still remains limited. There are stronger ways to represent concurrency by returning a partial order of the planned actions. This concurrency allows to have solution plans that are more resilient and flexible, and thus are more applicable in real world applications. This kind of partially-ordered plans will be addressed in our future works.

  action a is a tuple a = (name(a), pre(a), add(a), del(a)) where name(a) is the name of the action, pre(a) is the action's preconditions, add(a) is its positive effects and del(a) its negative ones, each one being a set of propositions. Two actions (a, b) are independent iff del(a)∩(pre(b)∪add(b)) = ∅ and del(b) ∩ (pre(a) ∪ add(a)) = ∅. Note that action independence only depends on action definitions. In the following, for all a ∈ A, nInd(a) will denote the set of actions b ∈ A dependent on a.

Fig. 1 .

 1 Fig. 1. A layered plan with the successive states resulting from the action layer application. Circles represent states, and rectangles action layers.

Algorithm 1 : 12 I 13 Π 14 i ← i + 1 // Update the layer index 15 T

 1121314115 CPFD(P, Π, i, τ ) 1 Let P = (L, T , A, M, I, (T, ≺, α) 2 Let πi the i th layer of Π 3 Let τ set of tasks already resolved at layer i 4 if T = ∅ then return Π 5 tasks ← trail(tn) \ τ 6 nondeterministically choose t ∈ tasks 7 if t is primitive then 8 resolvers ← {a ∈ A | task(a) = t, pre(a) ⊆ I and (∀b ∈ πi, a independent of b)} 9 if resolvers = ∅ then 10 if πi = ∅ then return Failure 11 else ← γ(I, πi) // Apply the layer effects ← Π + [] // Add a new empty layer ← T \ τ // Update the task network 16

20 nondeterministically choose a ∈resolvers 21 πi

 2021 ← πi ∪ {a} // Add a to the current layer 22 τ ← τ ∪ {t} // Add t to the resolved tasks 23 else 24 resolvers ← {m ∈ M | task(m) = t} 25 if resolvers = ∅ then return Failure 26 nondeterministically choose m ∈ resolvers 27 {m = (Tm, ≺m)} 28 T ← (T \ {t}) ∪ Tm // Decomposing tn with m 29

Fig. 2 .

 2 Fig. 2. The problem is initialized by setting the initial task into the first taskholder.

Fig. 3 .

 3 Fig.3. T0 is decomposed into four tasks, two compound ones T1 and T2, and two primitive ones t1 and no-op. Since neither T1, T2 or t1 is a last task, a no-op action is inserted instead of T0. The constraint over the taskholders are represented on the top right graph: each directed edge represents a precedence constraint. So for instance, the task in th2 should be planned before the one in th1.

Fig. 4 .

 4 Fig. 4. th2 is unconstrained, and contains a primitive task. It is added to the plan step by removing the task from the taskholder, adding the action a(t1) resolving t1 to the plan step, and marking the taskholder as resolved (represented by the black dot).

Fig. 5 .

 5 Fig. 5. The plan step is terminated by emptying it, the constraints implied by the resolved taskholders are removed.

Fig. 6 .

 6 Fig. 6. The makespan of the solution plan returned by sCTHD with regards to the number of parameters on the instance 6 from Satellite p06.

For more details about the method to compute the bounds of the solution task network, see[START_REF] Alford | Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems[END_REF]