Sylvia Soares

Ysander Von Boxberg

Fatiha Nothias

Repair strategies for traumatic spinal cord injury, with special emphasis on novel biomaterial-based approaches

Keywords:

Repair strategies for traumatic spinal cord injury, with special emphasis on novel biomaterial-based approaches

1-Introduction

Human traumatic spinal cord injury (SCI) can lead to life-long disability with loss of sensation and voluntary motor functions (paralysis). Neurological outcomes depend on the level of the spinal segment affected (resulting in either paraplegia, or tetraplegia in case of cervical trauma), and the severity of the local damage (partial, or complete destruction of the underlying nervous tissue). Very often, the case of SCI patients is further aggravated by diverse complications, such as spasticity and loss of autonomous urinary function, and/or associated with development of various respiratory, digestive, musculo-skeletal or circulatory disorders, as well as infectious diseases (septicemia, pneumonia) [START_REF] Nas | Rehabilitation of spinal cord injuries[END_REF]. Both individual, and societal costs for this condition are extremely high. SCI pathology is particularly frequent among young adults between 18 and 35 years, and touches more men than women (four out of five in the U.S.: traffic accidents, sports, ...).

Incidence of SCI is estimated at around 54 new cases per year per million population in the U.S., and while the average life expectancy of SCI patients has greatly improved during the last decades, cases may become more severe due to an ageing population.

First-year post-trauma care (hospitalization and re-education) costs are by far the most important (about 1 Mio. $ for a patient with complete tetraplegia), but summed up annual costs during a normal life time can be much higher, even without considering indirect costs such as losses in productivity and wages*.

2-SCI pathology on the molecular and cellular level

While peripheral nervous system (PNS) can adapt to traumatic lesions by regenerating axons and, depending on the lesion severity, restore synaptic connectivity, adult mammalian CNS (brain and spinal cord) displays only a poor capacity for selfrepair in response to traumatic lesions. Major differences in the endogenous repair mechanisms of PNS vs. CNS concern the nature of their respective neurons and glial cells, and particularly their local extracellular environment, as well as the specific inflammatory processes provoked by a lesion. Thus, although adult neurons of the mammalian CNS can initially survive a traumatic lesion, regrowth of their axons through the lesion site ultimately fails due to a cascade of cellular and molecular events, starting within minutes after the initial impact and continuing for weeks and even years, leaving the affected neural tissue in a permanently altered, regeneration-inhibited state [for refs. see 2, 3]. In the last two decades, several factors have been identified that contribute to the complexity of the SCI physiopathology. The injury-associated vascular damage inevitably leads to hypoxia, hemorrhage and edema, thereby accelerating necrosis of the damaged neural tissue. The associated breakdown of the blood-spinal cord barrier (BSBC) favors infiltration of blood-derived monocytes/macrophages that, together with activated microglia (the immune resident cells), will spread inflammation, further exacerbated by formation of free radicals and glutamate excitotoxicity [START_REF] Beck | Quantitative analysis of cellular inflammation after traumatic spinal cord injury: evidence for a multiphasic inflammatory response in the acute to chronic environment[END_REF]. This detrimental environment will cause secondary damage through neurodegenerative lesions that spread caudally and rostrally from the initial impact, aggravating the neurological deficits [2, 5, 6, and refs. therein].

The cavities that develop because of necrosis of the neural tissue become walled off by the astrocytic scar, creating a barrier to axon growth that is both mechanical, and chemical due to expression of inhibitory molecules such as chondroitin sulfate proteoglycans (CSPG) as well as certain semaphorins and matrix-metalloproteinases.

3-Therapeutic approaches: what has been tried so far?

Few, if any, effective therapies exist for the thousands of patients suffering from spinal cord trauma. The only treatment for human CNS injury approved thus far, methylprednisolone administration, only marginally improves clinical outcomes, despite promising preclinical results. Nevertheless, evidence from studies over the past three decades indicates that mammalian CNS maintains, to a previously unexpected level, a capacity for neural tissue remodeling and axonal plasticity (i.e., sprouting). Indeed, depending on the level of their intrinsic capacity to activate a regeneration-associated gene (RAG) expression program, damaged axons are able to regenerate to some degree and within a certain time window [START_REF] Soares | Extensive structural remodeling of the injured spinal cord revealed by phosphorylated MAP1B in sprouting axons and degenerating neurons[END_REF][START_REF] Galtrey | Promoting plasticity in the spinal cord with chondroitinase improves functional recovery after peripheral nerve repair[END_REF]. Unraveling of the mechanisms underlying such remodeling has provided the basis for the development of experimental strategies to treat SCI using animal models, particularly in rodents. Such strategies include neutralization of myelin-derived inhibitors (e.g., anti-Nogo-antibodies [START_REF] Bareyre | Long-lasting sprouting and gene expression changes induced by the monoclonal antibody IN-1 in the adult spinal cord[END_REF]), or downstream inhibition of the related intracellular signaling pathways [Rho-GTPase signaling; [START_REF] Kopp | Smallmolecule-induced Rho-inhibition: NSAIDs after spinal cord injury[END_REF]), and degradation of inhibitory components of the glial scar (CSPG degradation by Chondroïtinase-ABC enzyme [3, 11, 12; for review, 6]. Axon growth through the traumatic lesion site can also be stimulated by administration of neurotrophic factors, or by manipulation of pro-regenerative or inhibitory neuronal signaling pathways (mTOR/PTEN [START_REF] Liu | PTEN deletion enhances the regenerative ability of adult corticospinal neurons[END_REF]). Regeneration of neural tissue is further enhanced by transplantation strategies employing genetically modified fibroblasts, Schwann cell bridges, olfactory ensheathing cells, or neuronal progenitors and stem cells (see above reviews, and [START_REF] Assunção-Silva | Hydrogels and Cell Based Therapies in Spinal Cord Injury Regeneration[END_REF]). Furthermore, some progress has been reached by active rehabilitation programs, shown to be effective and beneficial at least for patients with incomplete SCI scoring C-D on the ASIA (American Spinal Injury Association) scale, and even for a small number with cervical injury [START_REF] Côté | Rehabilitation Strategies after Spinal Cord Injury: Inquiry into the Mechanisms of Success and Failure[END_REF][START_REF] Dietrich | Protection and Repair After Spinal Cord Injury: Accomplishments and Future Directions[END_REF][START_REF] Loy | Rehabilitation following spinal cord injury: how animal models can help our understanding of exercise-induced neuroplasticity[END_REF]. Certainly the most promising breakthrough concerning rehabilitation is the recent introduction of epidural electrical stimulation (EES), a technique intended to reactivate and reinforce spared, but so far "subfunctional" descending (supraspinal) neural connections ("subfunctional" since these sparse residual connections are initially not robust enough to eventually drive muscle function). Thus, epidural implantation of an anode-cathode electrode array just below the lesion site coupled to a pulse generator, has allowed complete motor paraplegic patients to acquire standing and stepping capacities when associated with task-specific training. To this end, the technique has been more and more refined, from an initially more diffuse stimulation towards "multi-modal rehabilitation" sessions, in which the combination of individual electrodes delivering pulses of variable frequency and amplitude is fine-tuned for particular tasks and notably, for bilateral function.

Electromyogram analysis helps determining the best-suited stimulation pattern for eliciting a response from specific muscles. After a certain number of training sessions with gravity assistance, some patients are finally capable of voluntary leg movements without the need for concomitant EES [START_REF] Gill | Neuromodulation of lumbosacral spinal networks enables independent stepping after complete paraplegia[END_REF][START_REF] Angeli | Recovery of Over-Ground Walking after Chronic Motor Complete Spinal Cord Injury[END_REF]. Progress through EES training was reported to be particularly rapid when lumbosacral proprioceptive circuits were stimulated with a temporal and spatial selectivity in correspondence with the intended movement, thereby allowing even weak residual supraspinal commands to act on the appropriate spinal motor neuron pools. After several months of spatio-temporally coordinated EES-assisted training, patients that had been paralyzed for several years thus regained the capacity for voluntary control of muscle function even in the absence of EES [START_REF] Wagner | Targeted neurotechnology restores walking in humans with spinal cord injury[END_REF].

4-Regeneration-inhibiting obstacles to overcome

Unfortunately, despite the significant progress in recent years, translation of experimental therapeutic strategies to clinical practice is still limited. More preclinical research is needed in view of the diverse, important caveats that need to be overcome or be better controlled, as outlined below:

-Adult axon growth through the lesion (regeneration or sprouting of axons), the real contribution of which to functional recovery is largely unknown. Thus, the number of fibers sprouting or regenerating through the lesion site is always small, and the distance of outgrowth is modest (e.g., for corticospinal axons that would need to grow for long distances), even more so in the context of human spinal cord anatomy [START_REF] Dietz | Restoration of sensorimotor functions after spinal cord injury[END_REF][START_REF] Oudega | Corticospinal reorganization after spinal cord injury[END_REF].

-Incomplete restoration of the blood-spinal cord barrier (BSCB), and poor revascularization at the lesion site: this impairs self-repair, as well as grafting interventions due to poor oxygen and nutrient supply for transplanted cells [START_REF] Silver | Central nervous system regenerative failure: role of oligodendrocytes, astrocytes, and microglia[END_REF][START_REF] Oudega | Molecular and cellular mechanisms underlying the role of blood vessels in spinal cord injury and repair[END_REF].

-Demyelination and remyelination: Oxidative stress, excitotoxicity, low oxygen supply, and the persisting inflammatory process lead to the death of oligodendrocytes.

Although oligodendrocyte precursor cells (OPCs) are recruited to the injury site [START_REF] Keirstead | Response of the oligodendrocyte progenitor cell population (defined by NG2 labelling) to demyelination of the adult spinal cord[END_REF], the subsequent spontaneous remyelination will usually remain abnormal or incomplete (for review, [START_REF] Franklin | Remyelination in the CNS: from biology to therapy[END_REF]). Schwann cells migrating into the lesion site, or arising from resident OPCs [START_REF] Zawadzka | CNS-resident glial progenitor/stem cells produce Schwann cells as well as oligodendrocytes during repair of CNS demyelination[END_REF], also participate in the remyelination process, but their survival is rapidly compromised [START_REF] Oudega | Schwann cell transplantation for repair of the adult spinal cord[END_REF][START_REF] Bunge | Realizing the maximum potential of Schwann cells to promote recovery from spinal cord injury[END_REF]. Since denuded axons are particularly vulnerable, much effort has been devoted to boost their remyelination, either by transplanting OPCs that may be generated from human embryonic stem cells [START_REF] Keirstead | Human embryonic stem cell-derived oligodendrocyte progenitor cell transplants remyelinate and restore locomotion after spinal cord injury[END_REF], or by inducing recruitment and differentiation of resident OPCs via trophic factors, hormones, or by targeting potential inhibitory factors in the environment such as LINGO-1, Sema-3A, and CSPGs (for review, [START_REF] Plemel | Remyelination after spinal cord injury: is it a target for repair?[END_REF]). However, although these approaches did seem to favor functional recovery to a certain degree, most are not exclusively acting on myelination, and recent work has put a serious doubt on the actual contribution of oligodendrocyte-driven remyelination to spontaneous locomotor recovery [START_REF] Duncan | Locomotor recovery following contusive spinal cord injury does not require oligodendrocyte remyelination[END_REF].

-Retrograde degeneration of axons ("axon die-back"): Axons damaged by the initial impact that are no longer connected to their target will eventually undergo a retrograde degeneration process, thereby liberating more toxic myelin degradation products that in turn, aggravate the spreading of inflammation beyond the primary lesion site.

-Scarring is recognized as a major obstacle to CNS repair, as it both physically and chemically impedes axon regrowth. However, it should be noted that astrogliosis is also beneficial for neuronal repair, since reactive astrocytes at the lesion site are essential for neural protection and regulation of the injury-induced inflammatory response.

Therefore, efforts to avoid completely scar formation through reduced expression of genes selectively expressed by reactive astrocytes, or by eliminating proliferating astrocytes themselves, appear not suitable as therapeutic approach for SCI (for review, [START_REF] Sofroniew | Molecular dissection of reactive astrogliosis and glial scar formation[END_REF]). On the contrary, there is direct evidence that scar-forming astrocytes are indispensable for enhancing axon regeneration from adult neurons [START_REF] Anderson | Astrocyte scar formation aids central nervous system axon regeneration[END_REF], see discussion in [START_REF] Chedly | Physical chitosan microhydrogels as scaffolds for spinal cord injury restoration and axon regeneration[END_REF].

-Immune response and inflammation: inflammation, involving multiple cell types and effector molecules, can have both negative (secondary damage), and positive effects [for review , 34]. Wound healing generally involves an ordered immune response that relies on time-dependent activation of phenotypically and functionally distinct macrophage subsets. Thus, during the first days in normal wound healing outside the CNS, "classically activated" inflammatory macrophages (M1) assure the clearance of cell debris and ECM material. Thereafter, diverse subtypes of "alternatively activated", antiinflammatory macrophages (M2) take over that will contribute to tissue reconstitution, then remodeling (also termed "resolution") via release of anti-inflammatory cytokines, stimulation of proliferation of fibroblasts and endothelial cells (angiogenesis), and production of ECM [START_REF] Gensel | Macrophage activation and its role in repair and pathology after spinal cord injury[END_REF][START_REF] Wermuth | The significance of macrophage polarization subtypes for animal models of tissue fibrosis and human fibrotic diseases[END_REF]. This sequence, however, is deregulated after SCI. The immune response to SCI initially implies a release of proinflammatory cytokines (mostly by activated tissue-resident microglia), reactive oxygen species (ROS) and nitric oxide (NOx), thereby attracting blood-borne M1 macrophages that will release even more proinflammatory factors (pro-inflammatory feedback loop). While at first beneficial due to clearance of debris, this inflammatory reaction will later accelerate glial scar formation, neural cell death, and axon retraction and demyelination [START_REF] Benowitz | Inflammation and axon regeneration[END_REF][START_REF] Gensel | Macrophage activation and its role in repair and pathology after spinal cord injury[END_REF][START_REF] Kigerl | Identification of two distinct macrophage subsets with divergent effects causing either neurotoxicity or regeneration in the injured mouse spinal cord[END_REF][START_REF] Fitch | Cellular and molecular mechanisms of glial scarring and progressive cavitation: in vivo and in vitro analysis of inflammation-induced secondary injury after CNS trauma[END_REF][START_REF] Horn | Another barrier to regeneration in the CNS: activated macrophages induce extensive retraction of dystrophic axons through direct physical interactions[END_REF]. M2 macrophages are initially present in the lesion, but disappear rapidly (around 1 week post-lesion in the rat), whereas pro-inflammatory M1 macrophages persist indefinitely [START_REF] Chedly | Physical chitosan microhydrogels as scaffolds for spinal cord injury restoration and axon regeneration[END_REF][START_REF] Gensel | Macrophage activation and its role in repair and pathology after spinal cord injury[END_REF][START_REF] Kigerl | Identification of two distinct macrophage subsets with divergent effects causing either neurotoxicity or regeneration in the injured mouse spinal cord[END_REF]. Today, this impaired immune response cascade appears as one of the major obstacles to SCI repair, and may even compromise some repair strategies such as cell therapy. Precise, time-dependent regulation of the necessary balance between inflammatory and anti-inflammatory macrophages may thus have enormous therapeutic potential [START_REF] Raposo | CNS repair requires both effector and regulatory T cells with distinct temporal and spatial profiles[END_REF].

Today, it is consensus among researchers in the SCI field that maximal restoration will most likely be achieved with a combination of therapies overcoming the multiple hindrances, and synergistically improving functional recovery. Accordingly, several such combined therapies were shown to boost axon regeneration and tissue restoration after SCI, e.g. associating ChABC treatment with peripheral nerve autograft [START_REF] Houle | Combining an autologous peripheral nervous system "bridge" and matrix modification by chondroitinase allows robust, functional regeneration beyond a hemisection lesion of the adult rat spinal cord[END_REF][START_REF] Alilain | Functional regeneration of respiratory pathways after spinal cord injury[END_REF], or ChABC or Nogo-A antibody treatments with locomotor training [START_REF] García-Alías | Training and anti-CSPG combination therapy for spinal cord injury[END_REF][START_REF] Chen | Sequential therapy of anti-Nogo-A antibody treatment and treadmill training leads to cumulative improvements after spinal cord injury in rats[END_REF]. Strategies employing a complex cocktail of trophic factors together with implantation of stem cell-derived neurons or embryonic neurons embedded in a fibrin polymer bridge were also explored [45, and refs. therein].

5-Novel biomaterial-based approaches

New hope for SCI treatment appears to arise not least thanks to recent progress in the field of bio-inspired new materials that has already seen the development of promising tools for medical applications in wound healing and regeneration of various tissues. For SCI treatment, biomaterials in the form of implantable hydrogels appears particularly interesting, and evidence is accumulating that future combinatorial approaches will need to integrate such "bio-scaffolds" as substitute for lost neural extracellular matrix (ECM). Various biomaterials have been designed, both natural and synthetic, differing in their physical state (solutions, hydrogels, solids with controlled porosity), in situ biodegradability, and specific functionalization (charged surface favoring cell attachment, capacity for drug delivery, etc.). Ideally, any such material should have properties specifically adapted to the spinal cord environment, i.e. allow for cell migration and attachment, and axon growth, improve revascularization, and be well integrated such as to not generate a frontier at the host tissue-scaffold interface [for review, see [START_REF] Madigan | Current tissue engineering and novel therapeutic approaches to axonal regeneration following spinal cord injury using polymer scaffolds[END_REF][START_REF] Straley | Biomaterial design strategies for the treatment of spinal cord injuries[END_REF][START_REF] Joosten | Biodegradable biomatrices and bridging the injured spinal cord: the corticospinal tract as a proof of principle[END_REF]. Essential parameters of the polymer considered so far are stiffness, permeability, swelling, and degradation. In preclinical tests, diverse hydrogels have shown significant therapeutic potential for CNS lesion repair, in particular for SCI, but generally also have some specific disadvantages [START_REF] Haggerty | Biomaterials for spinal cord repair[END_REF].

Among the synthetic polymers, the methacrylate-derived pHEMA (poly-(2hydroxyethyl) methacrylate) is one of the hydrogels exhibiting mechanical properties similar to those of nerve tissue, and has been used mainly in SCI [START_REF] Nomura | Complete spinal cord transection treated by implantation of a reinforced synthetic hydrogel channel results in syringomyelia and caudal migration of the rostral stump[END_REF]. It provides good cell adhesion and neural development when combined with ECM molecules, such as laminin or collagen. Neurogel in particular, a cross-linked pHEMA hydrogel, has led to the development of a revascularized bridge that promotes spinal cord restoration in rats and cats, and also reduces glial scarring [START_REF] Woerly | Prevention of gliotic scar formation by NeuroGel allows partial endogenous repair of transected cat spinal cord[END_REF]. Other hydrogels of similar composition, such as collagen-impregnated poly (glyceryl methacrylate) (pGMA), have been tested in brain lesions. However, pHEMA hydrogel synthesis implies the use of a toxic monomer, of which only the polymerized form can be used.

Polyethylene glycol (PEG) is another quite attractive synthetic hydrogel for SCI repair, as it is hydrophilic, non-toxic, biodegradable and bioabsorbable. Injectable in liquid form, PEG can be cross-linked by photopolymerization. Its use in experimental SCI has yielded encouraging results, including a chronic lesion paradigm, although the latter only after surgical resection of the glial scar prior to PEG injection [START_REF] Estrada | Long-lasting significant functional improvement in chronic severe spinal cord injury following scar resection and polyethylene glycol implantation[END_REF][START_REF] Brazda | Experimental Strategies to Bridge Large Tissue Gaps in the Injured Spinal Cord after Acute and Chronic Lesion[END_REF]. PEG-based hydrogels can further be used to generate implantable microspheres for drug release (e.g. of neurotrophic factors) into the spinal lesion site [START_REF] Roam | Controlled release and gradient formation of human glial-cell derived neurotrophic factor from heparinated poly(ethylene glycol) microsphere-based scaffolds[END_REF].

Natural carbohydrate-based polymers, notably of the glycosaminoglycan (GAG) type, are likely to form physical hydrogels, the degradation of which can be modulated by their microstructure and crosslinking degree. Various ECM components, such as collagen and hyaluronic acid (HA), as well as plasma-derived polymers, such as fibrin, were also employed as spinal cord scaffolds, in addition to agarose, alginate, and chitosan [START_REF] Johnson | Controlled release of neurotrophin-3 from fibrinbased tissue engineering scaffolds enhances neural fiber sprouting following subacute spinal cord injury[END_REF][START_REF] Lu | Long-distance growth and connectivity of neural stem cells after severe spinal cord injury[END_REF][START_REF] Wang | Biomaterial Scaffolds in Regenerative Therapy of the Central Nervous System[END_REF].

Natural polymers (e. g. GAGs, or polysaccharides, i. e. polymers of sugar moieties) can generally be considered biocompatible with the host tissue, and are non-toxic with a modular resorption rate, properties rendering them attractive for nerve tissue engineering. Agarose was the first biomaterial used as hydrogel, but proved unsuitable for tissue repair because it is not biodegradable, and its gelation temperature lies below 37°C. Alginate hydrogel scaffolds are also not biodegradable, although they can be colonized by cells, and may stimulate axonal growth. Collagen, the most common ECM component in mammals, is widely used as a scaffold to promote axon regeneration in PNS, but is not sufficient by itself in CNS. Fibrin, commonly used as scaffold and particularly for cell therapy [ex., 56], degrades too rapidly, and when contaminated with blood-borne pathogens activates astrocytes and resident inflammatory cells (microglia).

Matrigel TM (BD Biosciences) is the trade name for a gelatinous protein mixture obtained from mouse sarcoma, liquid below 4°C and gelling rapidly above this temperature.

Generally used as a three-dimensional substrate for cell culture studies, the use of Matrigel TM in clinical therapy is limited because its exact composition is unknown.

Hyaluronan (hyaluronic acid or hyaluronate), a hydrogel forming polysaccharide (GAG), is widely used in cosmetology and regenerative medicine. Tested in different models of PNS lesions, hyaluronan hydrogels are capable of being invaded by nerve fibers, and stimulate axon outgrowth. However, hyaluronan is not very effective in the case of traumatic CNS injury because of its rapid degradation, especially in an inflammatory environment.

Chitosan, derived from chitin by deacetylation, refers to a family of linear copolysaccharides of N-acetyl-D-glucosamine and D-glucosamine residues, and is structurally and functionally similar to GAGs (heparan sulfates, or other oligosaccharides such as hyaluronic acid). Several investigators have used chitosanbased biomaterials (usually combined with other natural or synthetic compounds), together with other strategies to improve axon regrowth. In most of these studies the biomaterial was designed as a structure containing macro-or microchannels for seeding cells into their inner lumen (i.e. neural stem and progenitor cells [NSPCs], or Schwann cells), and/or for trophic factor delivery [START_REF] Kim | Chitosan implants in the rat spinal cord: biocompatibility and biodegradation[END_REF][START_REF] Nomura | Delayed implantation of intramedullary chitosan channels containing nerve grafts promotes extensive axonal regeneration after spinal cord injury[END_REF][START_REF] Yang | NT3-chitosan elicits robust endogenous neurogenesis to enable functional recovery after spinal cord injury[END_REF]. However, the effect of the biomaterial alone was either not reported, or shown to have no significant effect on axon regeneration. Thus, these studies did generally not analyze the effect of the biomaterial used alone on scar formation (glial reaction), inflammation, and vascularization, with the exception of a report by [START_REF] Kim | Chitosan implants in the rat spinal cord: biocompatibility and biodegradation[END_REF], who found that chitosan is principally compatible with SC tissue, and does not provoke an inflammatory reaction. Chitosan-based materials and derivatives are indeed receiving increased attention in tissue engineering because of their unique and appealing biological properties, such as biocompatibility, biodegradability, and non-toxicity that make them suitable in the biomedical field. They have been extensively evaluated for regeneration of epithelial and soft tissues. Their beneficial characteristics include preservation of cellular phenotypes, binding and activity enhancement of bioactive factors, and synthesis and deposition of tissue-specific extracellular matrix [START_REF] Montembault | A material decoy of biological media based on chitosan physical hydrogels: application to cartilage tissue engineering[END_REF]62]. Moreover, other properties such as analgesic, antitumor, hemostatic, anticholesterolemic, anti-microbial, permeation enhancing, and antioxidant effects have also been documented [for review , 63, 64]. Accordingly, our recent study employing chitosan as fragmented physical hydrogel suspension (Chitosan-FPHS) showed that its implantation in acute rat spinal bilateral dorsal hemisection promoted the reconstitution of spinal tissue with functional vasculature. It did so not least by modulating the inflammatory response, favoring inflammation resolution through macrophage polarization towards the M2 phenotype. Chitosan-FPHS also diminished fibrous glial scarring, and the border between lesion site and intact tissue was rendered permissive for regrowth of numerous axons into, and for some even beyond the lesion site. Growing axons were myelinated or ensheathed by endogenous Schwann cells that migrated into the lesion site and whose survival was prolonged. This structural remodeling was associated with significant, long-lasting recovery of locomotor function [START_REF] Chedly | Physical chitosan microhydrogels as scaffolds for spinal cord injury restoration and axon regeneration[END_REF]. Thus, implantation of Chitosan-FPHS into an acute SCI lesion site seems a very promising strategy, and our perspective for a follow-up of the present study is to test its relevance in a chronic lesion. Determination of the suitable time window for chitosan hydrogel implantation is also important when considering a combination with other strategies, such as cell therapy or drug delivery. Furthermore, for a proof of concept, this strategy should be tested in an experimental model more relevant to humans, i.e. a contusion lesion.

At this point, it should be mentioned that the use of novel biomaterials for therapeutic approaches in the field of SCI is still in its infancy, and particular efforts should be made to carefully evaluate the effect of any biomaterial at first alone, before passing on to combinatorial strategies, and employing them in preclinical and clinical tests. Indeed, analyzing the effect of a combinatorial treatment is not possible without a thorough understanding of the mechanisms of action and the outcome of each treatment individually. Even then, this does not preclude the possibility that therapies, which when used alone do show a beneficial effect, will not always work synergistically when combined [see for ex., [START_REF] Oda | Effects of polyethylene glycol administration and bone marrow stromal cell transplantation therapy in spinal cord injury mice[END_REF][START_REF] Wilems | Combination therapy of stem cell derived neural progenitors and drug delivery of anti-inhibitory molecules for spinal cord injury[END_REF][START_REF] Ryu | Effects of Treadmill Training Combined with Serotonergic Interventions on Spasticity after Contusive Spinal Cord Injury[END_REF]. Nevertheless, since the introduction of bioengineering in SCI therapeutic approaches it has become evident that implanting a biomaterial will be important as support structure ("bio-scaffold") for the reconstitution of injured tissue, once potential safety issues can be ruled out, and the feasibility has been proven both for acute, and chronic spinal cord injury. We have good reason to believe that biomaterial formulations that will finally make it into clinical trials, will be able to prevent the irreversibility of a complete lesion, in the acute phase by creating a pro-regenerative environment preventing necrotic cavity formation, in cases of chronic lesions by potentiating the outcome of current approaches like re-education, or electrical stimulation.

6-Concluding remarks

Today, patients with complete SCI remain paralyzed for the rest of their life, with no possible relief in the foreseeable future. Therefore, there is enormous societal expectation for a therapeutic approach to come, and the slightest hope for improving the condition of patients is the focus of a lot of attention and compassion. For this reason, one has to carefully manage news about progress in the field in order not to raise false hope.

Regeneration of the CNS is a major challenge for modern tissue engineering in fundamental and clinical research, and research on SCI in particular is of high priority in North America and in Europe (EU recom. 1560-2002). SCI offers tremendous challenges for fundamental and clinical scientists, as it requires in-depth knowledge of the cellular and molecular mechanisms triggered by the injury, of axon growth in general, as well as of the anatomical and functional organization of the spinal cord and connected CNS structures. As outlined above, therapeutic strategies may, in addition to providing a biomaterial-based scaffold replacing lost ECM, target the balance between pro-and antiinflammatory factors, stabilize affected neurons and axons to prevent excessive neurodegeneration, degrade regeneration-inhibitory molecules, and use cell therapy to provide "bridges" of neural cells allowing to be contacted by regrowing or sprouting axons [START_REF] Koffler | Biomimetic 3D-printed scaffolds for spinal cord injury repair[END_REF].

Only few clinical trials (phase-1/2a) with FDA approval for chronic SCI are currently under way [START_REF] Raspa | Recent therapeutic approaches for spinal cord injury[END_REF]. Thus, small biotech companies are exploring safety, tolerance, and efficacy of transplanting human neural stem cells (StemCells Inc., and Neuralstem Inc.) or oligodendrocyte progenitors (Asterias Biotherapeutics), and implantation of scaffolds based on a synthetic, resorbable (degradable) biomaterial (polylysine-coated PLGA: InVivo Therapeutics). These companies had demonstrated the efficacy of the proposed treatment in pre-clinical studies, using the BBB locomotor rating scale (open field test, The main challenge remains therapeutic efficacy, which is still rather limited for the diverse strategies developed so far. Indeed, the consequences of traumatic SCI are so complex and diverse that a combination of several treatments with complementary mechanisms of action is required, necessitating the establishment of multidisciplinary collaborations between neuro-surgeons and researchers in multiple fields. Moreover, because of the lesion variability from one case to another (level, volume, severity; acute or chronic), it may not be feasible to devise just one "standard" approach. Rather, several strategies should be developed and evaluated in different lesion paradigms, thus giving the clinician in charge the possibility to use the best-suited combination of treatments according to the case. Briefly, chitosan powder is dissolved in acetic acid, a gel is formed from the solution by neutralization in ammonia vapor, and after intense washing in H2O the gel is fragmented into ~20 µm particles by blending with an Ultra-Turrax apparatus. (B) Untreated (left) vs. chitosan-FPHS-filled (right) bilateral spinal cord dorsal hemisection, 3 weeks after the lesion. Note that with chitosan-FPHS treatment, the astrocytic scar (GFAP-labeling, green) is reduced, numerous axons (neurofilament [NF] labeling, red) are growing through the lesion site, and no lesion cavity is forming. The hydrogel is invaded by numerous cells reconstructing a nervous tissue (nuclei stained with Dapi). (C) Chitosan-FPHS-treated lesioned animals exhibit stronger, and more rapid locomotor function recovery, as demonstrated here using the BBB (Basso, Beattie, Bresnahan) locomotor scale (based on an "open field" test where animals freely moving in an enclosure are filmed, and the quality of their hindlimb movements is evaluated by specially trained, but "naïve" observers with respect to the applied treatment). Only animals with a BBB of "0" the day after the lesion were selected for further evaluation; a BBB of "10" corresponds to full weight support by the hindlimbs. The difference between treated and untreated animals is significant from 3-4 weeks onwards. (D) Gait analyses via the GaitLab system (the animal is filmed from underneath while moving through a 1m long corridor; all four paws are marked in different colors by the evaluation software), a first analysis being performed the day before the injury, the following once a week when animals have regained weight support, i.e. at around 6 weeks after the lesion for the majority of animals (BBB score 9/10). Right after the lesion, the hindpaws (turned upside down) are simply pulled behind the animal that advances only with its forelimbs; 10 weeks later, the same animal has regained weight support, and coordination of foreand hindlimb movements.

  Axon regrowth is further inhibited by degradation products of CNS myelin, namely MAG (myelin associated glycoprotein), Omgp (oligodendrocyte myelin glycoprotein), and Nogo, and hampered by the low levels of neurotrophic factors present in adult CNS [for review, 6].

[

  70]), which provides a baseline for data comparison. Recently, the FDA also approved a phase-1 clinical trial to evaluate transplantation of human autologous Schwann cells, conducted by the Miami Project [71].

Fig. legend -

 legend Fig. legend -Chitosan-FPHS implantation leads to reduced astrocytic scar formation, robust axon regrowth, and improved locomotor function:(A) Preparation of fragmented physical hydrogel suspension (FPHS) from chitosan:

Acknowledgments

Research of the authors is supported by IRME, FRM, Wings for life, Satt-Lutech Illustrations are adapted from Chedly et al., 2017 (cited reference #2), with permission.

Disclosure of interest

The authors declare that they do not have any competing interests.


Maxence Grand
email: maxence.grand@univ-grenoble-alpes.fr

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

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

AMLSI: A Novel Accurate Action Model Learning Algorithm

This paper presents a new algorithm based on grammar induction, called AMLSI (Action Model Learning with State machine Interactions), to learn PDDL domains by querying the system to model with action sequences and by observing the state transitions. AMLSI takes as input a training set of feasible and infeasible action sequences built from partial and noisy observations and returns a PDDL domain. A key issue for domain learning is the ability to plan with the learned domains. It often happens that a small learning error leads to a domain that is unusable for planning. Unlike other algorithms, we show that AMLSI is able to lift this lock by learning domains from partial and noisy observations with sufficient accuracy to allow planners to solve new problems. Input Observations Noise Negative preconditions Static relations Numerical functions Conditional effects EXPO Partial domain, Plan traces Complete No NA

Introduction

Hand-encoding PDDL (Planning Domain Description Language) domains [START_REF] Mcdermott | PDDL-the planning domain definition language[END_REF]) is generally considered as difficult, tedious and error-prone. The experts of the system to model are not always PDDL experts and vice versa. In order to tackle this issue, planning domain learning algorithms have been proposed to automatically generate PDDL domains, e.g., [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF][START_REF] Shahaf | Learning partially observable action schemas[END_REF][START_REF] Mourão | Learning STRIPS operators from noisy and incomplete observations[END_REF][START_REF] Cresswell | Acquisition of object-centred domain models from planning examples[END_REF][START_REF] Cresswell | Generalised domain model acquisition from action traces[END_REF][START_REF] Gregory | Domain model acquisition in the presence of static relations in the LOP system[END_REF]. A challenging issue for these learning algorithms is their ability to generate domains that planners can use to solve new planning problems. In practice, most state of the art approaches do not evaluate this ability. They use rather the syntactical error (differences in the preconditions and the effects of operators) between International Planning Competition (IPC) benchmarks and learned domains. Unfortunately, it is not because one learned domain is syntactically closer to a IPC domain that it is better than another. It often happens that a small syntactical error leads to a domain that is unusable for planning: the ability of a PDDL domain to solve planning problems can depend on a few number of decisive preconditions/effects.

In this paper, we propose a new algorithm based on grammar induction, called AMLSI (Action Model Learning with State machine Interactions), to learn PDDL domains by Copyright c 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

querying the system to model with action sequences and observing the state transitions. AMLSI takes as input a training set of feasible and infeasible action sequences built from partial and noisy observations and returns a PDDL domain. Unlike other approaches, we show that AMLSI is able to learn domains from partial and noisy observations with sufficient accuracy to allow planners to solve new problems.

The rest of the paper is organized as follows. In section 2 we present the related works. In section 3 we present the problem statement and, in section 4, we detail the AMLSI algorithm. Finally, section 5 evaluates the performance of AMLSI on IPC benchmarks.

Related Works

Many approaches have been proposed to learn planning domains. Table 1 proposes a synthesis of these works, which can be classified according to the input data of the learning process and the complexity of the language used in the output domain. The input data can be plan traces obtained by resolving a set of planning problems, e.g, ARMS [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF], plan traces and partial planning domains to complete, e.g, EXPO [START_REF] Gil | Learning by experimentation: Incremental refinement of incomplete planning domains[END_REF]) and more recently RIM [START_REF] Hankui Zhuo | Refining incomplete planning domain models through plan traces[END_REF], or random walks, e.g., IRaLe [START_REF] Rodrigues | Incremental learning of relational action models in noisy environments[END_REF]. The input data can be complete (states and actions), e.g., Observer [START_REF] Wang | Learning by observation and practice: An incremental approach for planning operator acquisition[END_REF] or completely blind, e.g., LOCM [START_REF] Cresswell | Acquisition of object-centred domain models from planning examples[END_REF], LOP [START_REF] Gregory | Domain model acquisition in the presence of static relations in the LOP system[END_REF] or NLOCM [START_REF] Gregory | Domain model acquisition in domains with action costs[END_REF], noisy, e.g., Plan-Milner (Segura-Muros et al. 2018) or noiseless, e.g., Louga [START_REF] Kucera | LOUGA: learning planning operators using genetic algorithms[END_REF]. As output, the learned planning domains can have different levels of expressivity: negative preconditions, e.g., Louga [START_REF] Kucera | LOUGA: learning planning operators using genetic algorithms[END_REF], static relations, e.g., LSO-NIO [START_REF] Mourão | Learning STRIPS operators from noisy and incomplete observations[END_REF], numerical functions, e.g., LOCM2 [START_REF] Cresswell | Generalised domain model acquisition from action traces[END_REF] or conditional effects, e.g., SLAF [START_REF] Shahaf | Learning partially observable action schemas[END_REF].

AMLSI differs from the state-of-the-art algorithms in several points. Firstly, AMLSI is one of the few algorithms able to deal with noisy and partial observations. Secondly, AMLSI works with both feasible and infeasible action sequences while most approaches use only feasible action sequences or plan traces. To our best of knowledge, only IRALe and LSO-NIO use failures in action sequences, but AMLSI differentiates feasible and infeasible action sequences. In addition, AMLSI uses random walks to generate its training datasets of both feasible and infeasible ac-Table 1: State-of-the-art action model learning algorithms. For some algorithms, there is no indication on the ability of the algorithm to learn static relations and/or negative preconditions. These algorithms are rated NA for these criteria. tion sequences, whereas most of the algorithms like ARMS, Louga and Plan-Milner either only use plan traces or random walks generating feasible action sequences. Thirdly, in terms of expressivity, AMLSI learns PDDL domains including static relations in preconditions as well as negative preconditions. To our best knowledge, only Louga has the same expressivity but it cannot work with noisy traces. Fourthly, AMLSI uses automata representations like LOCM though differently: LOCM generates several automata, one for each domain object while AMLSI generates a single automaton representing the whole domain for a given initial state. The advantage of this method is that we can use regular grammar induction algorithms, which is a well-defined area with accurate algorithms. More importantly, AMLSI is the only algorithm able to learn planning domains accurate enough to be used by planners to solve new planning problems (i.e. that are not in the training sets) with such a level of noise in the observations (see Section 5).

Problem Statement

We work in the context of classical planning. World states s are modeled as sets of propositions and actions change the world states. For instance, in the gripper domain,

s = (at -robby r 1 ) ∧ ¬(at -robby r 2 ) ∧ (at b r 1 )∧ ¬(at b r 2 ) ∧ (f ree lef t) ∧ (f ree right)∧ ¬(carry b right) ∧ ¬(carry b lef t)
states that robby is in the room r1 as well as the ball b, and robby's arms are both f ree.

Formally, let S be a set of all the propositions modeling properties of world, and A the set of all the possible actions in this world. A state s is a subset of S and each action a ∈ A is a triple of proposition sets (ρ a , + a , - a ), where ρ a , + a , - a ⊆ S, and + a ∩ - a = ∅. ρ a are the preconditions of action a, that is, the propositions that must be in the state before the execution of action a. + a and - a are respectively the positive (add list) and the negative (del list) effects of action a, that is, the propositions that must be added or deleted in s after the execution of the action a.

In practise, actions are abstracted as operators in first order logic Planning Domain Description Language. For instance move(?f rom ?to) stands for all the possible groundings of the parameters ?f rom and ?to and the actions move(r 1 r 2 ), move(r 2 r 1 ) etc. Let γ : S × A → S be the state transition function such that s = γ(s, a) = (s ∪ + a ) \ - a . γ(q, a) is defined if and only if ρ a ⊆ s. Let π = [a 0 , a 1 , . . . , a n ] be a sequence of actions, and + the concatenation of two sequences. Γ(s 0 , π) is defined recursively as follows:

Γ(s 0 , π) =    [s 0 ] if π = [] [s 0 ] if ρ a0 s 0 [s 0 ] + Γ(γ(s 0 , a 0 ), [a 1 , . . . , a n ]) otherwise
In this work, we assume that:

• the set of all the possible actions A is known (for instance A = {move(r 1 r 2 ), move(r 2 r 1 ), pick(b r 1 grip), pick(b r 2 grip), drop(b r 1 grip), drop(b r 2 grip)}) and for all a ∈ A, (ρ a , + a , - a ) is unknown, • γ is the state machine to model and Γ represents the observed states: if a query (s 0 , π) is sent to the state machine, it sends back a sequence of observable states Γ(s 0 , π). This kind of state machines is, for instance, an ATM on which a sequence of actions (inserting a credit card, a PIN number etc.) is tested, any process computing streams of user commands, an industrial process simulator or a person who is interviewed ("what if in this state, we perform such and such action?") to collect the expertise on such a process etc.

• the observations Γ(s 0 , π) are possibly partial and noisy. A partial observation is a state where some propositions are missing. For instance, in the gripper domain,

(at -robby r 1 ) ∧ . . . ∧ (at b r 1 )∧ ¬(at b r 2 ) ∧ . . . ∧ (f ree right)∧ ¬(carry b right) ∧ ¬(carry b lef t)
And in a noisy observation, the truthiness of some predicates is incorrect: π = [a 0 , a 1 , . . . , a n ] is a feasible sequence given s 0 if and only if Γ(s 0 , [a 0 , a 1 , . . . , a n ]) = [s 0 , s 1 , . . . , s n ]: both sequences have the same length. Therefore, π = [a 0 , a 1 , . . . , a n ] is an infeasible sequence given s 0 if and only if Γ(s 0 , [a 0 , a 1 , . . . , a n ]) = [s 0 , s 1 , . . . , s i ] and i < n. Or, equivalently, [a 0 , a 1 , . . . , a i-1 ] is feasible and [a 0 , a 1 , . . . , a i-1 , a i ] is infeasible (given s 0 ).

(at -robby r 1 ) ∧ . . . ∧ (at b r 1 )∧ ¬(at b r 2 ) ∧ . . . ∧ (f
In this paper we tackle the following problem: by repeatedly querying a state machine with different (possibly infeasible) (s 0 , π) and observing Γ(s 0 , π) (possibly partial and noisy), is it possible to learn the state transition function γ and express it as a PDDL domain?

The AMLSI approach

The AMLSI approach, resumed by algorithm 1, is composed of four steps: (1 -line 1) a dataset generation step, (2 -lines 2-3) a grammar induction step, (3 -lines 4-5) a PDDL induction step and (4 -lines 6-14) a refinement step.

Step 1. Dataset generation

The objective of this step is to built up two training datasets: I + (positive samples) containing the feasible action sequences and the corresponding observations, and I -(negative samples) containing the infeasible action sequences: at a given state s, we query the system about the feasibility of an action a randomly chosen in A. If a is feasible, the current state is observed and we add a to the current π. This random walk is iterated until π reaches an arbitrary length, and added to I + . If a is infeasible in the current state, the concatenation of π and a is added to I -.

Step 2. Grammar Induction

In the second step, we use the RPNI algorithm [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF] to learn the regular grammar based on I + and I -inputs. RPNI has a polynomial complexity and is optimal: it returns the smallest automaton (a regular grammar can be represented as a deterministic finite automaton) accepting all the positive samples I + and rejecting all the negative samples Iwhen I + and Iare "characteristic" [START_REF] Oncina | Inferring regular languages in polynomial update time[END_REF]. Formally, the deterministic finite automaton learned is a quintuple < A, N, n 0 , γ, F >, where A is the set of action, N is the set of nodes, n 0 ∈ N is the initial node, γ is the node transition function, and F ⊆ N is the set of final nodes.

Finally, to prepare the grammar induction, we carry out two preprocessing steps for I + and I -. These two preprocessing steps aim to extend I + and I -:1

Step 1. Sequence prefixes. Any prefix of a feasible sequence is itself feasible. The correct grammar has to accept them, so they are added to

I + . For instance, if [move(r 1 r 2 ), move(r 2 r 1 ), pick(b r 1 lef t)] ∈ I + , [move(r 1 r 2 ), move(r 2 r 1 )] and [move(r 1 r 2 )] are also in I + .
Step 2. Pairwise constraints. Pairwise constraints are pairs of actions that cannot be consecutive in a sequence. These constraints are based on the fact that for an action to be feasible a certain number of resources must be produced (add list) and others must be consumed (del list). For instance, in the gripper domain, move(r 1 r 2 ) is never followed by pick(b r 1 grip) because (at -robby r 1 ) must be true to execute pick(b r 1 grip), and after the execution of move(r 1 r 2 ), (at -robby r 1 ) is always false, therefore pick(b r 1 grip) cannot follow move(r 1 r 2 ). Pairwise constraint computation is based on I + : we assume that only pairs of actions in I + are possible. Therefore, every pair of actions that is not in a sequence of I + is added to I -. Formally, the set of pairwise constraints is built as follows:

{∀a i , a j ∈ A 2 | π ∈ I + s.t. π = π 1 , a i , a j , π 2 }
Step 3. Operator generation Operator generation is based on four steps:

1. Observation mapping Once the automaton is induced, we need to know which node of the automaton correspond to which observed state. To do that, we input in the automaton all the positive samples in I + and map the pairs "node, action" in the automaton with the pairs "state, action" in I + . There are two different mapping: the mapping (A)nte µ A and the mapping (P)ost µ P . µ A (n, a) (resp. µ P (n, a)) gives the state before (resp. after) the execution of the transition a in node n. Then, we compute a reduced mapping µ A (resp µ P ), which contains the common propositions of all the states for a given (n, a). For instance, consider the classical gripper planning domain:

(at b r 1 ) is in µ A (0, pick(b r 1 grip)) iff (at b r 1 ) is in all µ A (0, pick(b r 1 grip))
. Likewise, we remove from µ A (0, pick(b r 1 grip)) and µ P (0, pick(b r 1 grip)) all the propositions whose parameters are not a subset of The advantage to use the common pattern in the mapping is that it reduces the noise in the mapping. Indeed, when we have a high level of compression, it is unlikely that a proposition present in the mapping is a misjudged proposition.

Precondition generation

The algorithm 2 describes how we generate operator preconditions. To learn the preconditions of an operator o, we compute the reduced mapping of all the nodes where an action a, instantiating o, is feasible. At line 8, ρ a is the reduced mapping of all the µ A mappings of the action a. The generalization of ρ a at line 9 replaces all the constant symbols by variables (for instance, (b r 1 grip) by (?obj ?room ?gripper)).

Effect generation

Effect generation is analogous to precondition generation with the difference that we use µ A (n, a) and µ P (n, a) to compute a reduced mapping of + a , the propositions that are never in µ A (n, a) and always in µ P (n, a), and - a , the propositions that are always in µ A (n, a) and never in µ P (n, a).

Step 4. Operator refinement

The refinement steps of the PDDL operators are necessary because the observations are partial and noisy. The refinement is divided into 3 substeps:

1. Effect refinement This step ensures that the generated operators allow to regenerate the induced grammar. We use the reduced mappings µ A to verify that for each couple of consecutive actions a and a , the effects of the action a generate the preconditions of action a . If it is not the case, we add in the effects of a the propositions satisfying the preconditions of a . For instance, suppose we have n = γ(n, move(r 1 r 2 )) and n = γ(n , pick(b r 2 grip)). Now suppose we have ¬(atrobby r 2 ) ∈ µ A (n, move(r 1 r 2 )), (at -robby r 2 ) ∈ ρ pick(b r2 grip) and (at -robby r 2 ) ∈ + move(r1 r2) . We need to have (at -robby r 2 ) ∈ + move(r1 r2) in order to make γ(n, move(r 1 r 2 )) and γ(n , pick(b r 2 grip)) feasible. Thus, we add (at -robby ?to) to + move(?f rom ?to) .

2. Precondition refinement In this step, we assume like [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF]) that the propositions of the negative effects must be in the action preconditions. Thus for each negative effects in an operator, we add the corresponding proposition in the preconditions. For instance, suppose ¬(at -robby ?f rom) ∈ - move(?f rom ?to) , then (atrobby ?f rom) ∈ ρ move(?f rom ?to) after refinement.

Since effect refinement depends on the preconditions and precondition refinement depends on the effects, we repeat these two steps until convergence. They converge because the adding of preconditions is limited by the effects, and the adding of effects is limited by the preconditions of the next action in the induced automaton (In our experiments, see Section 5, less than 10 iterations are needed to converge).

3. Tabu search Finally, we perform a tabu search to improve the PDDL operators independently of the induced grammar, on which operator generation is based.

. The neighborhood of a candidate domain is the set of domains where a precondition or an effect is added or removed. And the search space of the tabu search is the set of all possible domains compatible with the PDDL syntax constraints [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF]. The fitness function used to evaluate a candidate set D of PDDL operators is:

J(D|I + , I -) = J ρ (D|I + ) + J (D|I + )+ J + (D|I -) + J -(D|I -)
where :

• J ρ (D|I + ) = π∈I+ s∈Γ(s0,π)
Accept(ρ a , s) -Reject(ρ a , s)

computes the fitness score for the preconditions of the actions a. Accept(ρ a , s) counts the number of positive and negative preconditions in the observed state s, and Reject(ρ a , s) counts the number of positive and negative preconditions that are not in s.

• J (D|I + ) = π∈I+ s∈Γ(s0,π)

Equal(s, ŝ) -Different(s, ŝ)

computes the fitness score for the effects of the actions a. s are the observed states and ŝ are the states obtained by applying the actions of π. Equal(s, ŝ) counts the number of similar propositions in s and ŝ, and Dif f erent(s, ŝ) counts the differences.

• J + (D|I + ) = π∈I+ |π| × 1 Accept(D,π) where 1 Accept(D,π) = 1 if
and only if D can generate the positive sample π. |π| is the length of π.

• J -(D|I -) = π∈I-
1 Accept(D,π+)∧Reject(D,π) . As detailed in section 15, the negative sample π ∈ I -is a sequence of n + 1 actions where the n first actions are a prefix of a sequence in I + : π + is this prefix.

1 Accept(D,π+)∧Reject(D,π) = 1 if and only if D can generate π + and not π.

Fitness functions J ρ (D|I + ) and J (D|I + ) measure the ability of D to explain the observed states whereas fitness functions J + (D|I + ) and J -(D|I -) measure its ability to regenerate the induced grammar. J + (D|I + ) is weighted by the length of π ∈ I + but not J -(D|I -) because I -is larger than I + .

Once tabu search is done, we repeat all the refinement steps until convergence.

Experiments

Our experiments 2 are based on 10 IPC domains: Blocksworld, Gripper, Hanoi, N-Puzzle, Peg Solitaire, Parking and Zenotravel, Sokoban, Neg-Visit-All and Neg-Elevator. Neg-Visit-All and Neg-Elevator are modified versions of Visit-All and Elevator with negative preconditions to show AMLSI ability to learn them. All the used benchmarks are STRIPS domain. Table 2 shows our experimental setup.

We deliberately chose the size of the test sets larger than the learning sets to show AMLSI's ability to learn accurate domains with small datasets. The training and test sets are generated as explained in Section 15. In the training sets, we generate positive action sequences with a length randomly chosen between 10 and 20, and in the test sets, we generate positive action sequences with a length randomly chosen between 1 and 100. I -are bigger than I + because it is more likely to generate infeasible actions.

We test each IPC domain with 3 different initial states over five runs, and we used five seeds randomly generated for each run. Tabu search is computed over 200 runs. For each IPC domain, we generate observed states by randomly removing a fraction of the propositions (partial states) and by randomly modifying their truth values. All tests were performed on an Ubuntu 14.04 server with a multi-core Intel Xeon CPU E5-2630 clocked at 2.30 GHz with 16GB of memory. Precondition error rate The precondition error rate [START_REF] Yang | Learning action models from plan examples using weighted MAX-SAT[END_REF]) computes the rate of preconditions that are not satisfied in the positive test set. This metric measures the quality of the preconditions in the learned domain. It is 2 AMLSI and our experimental setup can be found in an anonymous dropbox: https://www.dropbox.com/sh/3gpcdasycuy4r9h/ AACYDrwNeseOMFLX6tlmMZcWa?dl=0

Evaluation Metrics

3 Note that we compute the syntactical error without taking into account the negative preconditions of the operators because some of the chosen IPC domains do not have them. computed as follows:

E ρ = π∈E + a∈π error(ρ a , ŝ) a∈π |ρ a | error(ρ a , ŝ) = |{p ∈ ρ a ∧ ¬p ∈ ŝ}| + |{¬p ∈ ρ a ∧ p ∈ ŝ}|
gives the number of positive and negative preconditions p in actions a that are not satisfied in the observed state ŝ.

Effect error rate The effect error rate [START_REF] Kucera | LOUGA: learning planning operators using genetic algorithms[END_REF] computes the error rate on the effects of the learned domain. It is computed as follows:

E = π∈E + a∈π error( a , ŝ) a∈π | a | error( a , ŝ) = |{p ∈ + a ∧ ¬p ∈ ŝ}| + |{¬p ∈ - a ∧ p ∈ ŝ}|
gives the number of positive and negative effects p in the actions a that are not satisfied in the observed state ŝ.

Accuracy The accuracy (Zhuo et al. 2013) quantifies the usability of the learned model for planning. Most of the works addressing the problem of learning planning domains uses the syntactical error to quantify the performance of the learning algorithm. However, domains are learned to be used for planning, and it often happens that one missing precondition or effect makes them unable to solve new planning problems. Formally, the accuracy Acc = N N * is the ratio between N the number of correctly solved problems with the learned domain and N * the total number of problems to solve. The accuracy is computed over 20 problems. Although rarely used, we argue that the accuracy is the most important metric because it measures to what extent a learned domain is useful in practise for planning. Problem are solved with Fast Downward 19.06 [START_REF] Helmert | The Fast Downward planning system[END_REF]). Plan validation is realized with the automatic validation tool used in the IPC competition: VAL [START_REF] Howey | Val's progress: The automatic validation tool for pddl2. 1 used in the international planning competition[END_REF]. Finally, we also report in our results the ratio of solved problem that are not necessarily correctly solved.

Results

In order to study the performances of AMLSI with respect to noisy and partial observations, we use three different experimental scenarios: Table 3: Domain learning results on 10 IPC domains. AMLSI performance is measured in terms of error rates for preconditions (resp. effects) E ρ (resp. E ), syntactical error E σ , the rate of solved problem Solved and accuracy Acc. AMLSI's performance are compare with LSO-NIO's performance with the same experimental setup. We report the averages computed over 15 runs (5 runs over 3 different initial states).

0 3.9 - - 0 0 3.9 - - 0 0 4.1 - - 0.2 0 4.3 - - Generation step 0 0 3.9 - - 0 0 30.2 - - 0 0 21.2 - - 0 0 30.9 - - Simple refinement 0 1 4.2 - - 0 0 30.1 - - 0 1 4.2 - - 0 0 30.7 - - Tabu search alone 0 0 8.2 - - 0 0 8.1 - - 0 0 8.4 - - 0 0 8.3 - - Without PC - - - - - - - - - - - - - - - - - - - - LSO-NIO - - - - - - - - - - - - - - - - - - - -
- 0 0.1 6.2 - - LSO-NIO - - - - - - - - - - - - - - - - - - - - Neg Visit

Impact of noisy and partial observations

The results of the first scenario (complete intermediate observations and no noise) show that AMLSI perfectly learns the preconditions and the effects of the operators of the IPC domains. Note that for 4 IPC domains, Hanoi, N-Puzzle, Peg-Solitaire and Parking, the syntactical error is not equal to 0. This is because AMLSI learns preconditions that are not in the IPC domain. On the other hand, the obtained accuracy is optimal for all domains. This means that the domains learned with AMLSI can be used to solve all the problems of the IPC domains.

The results of the second scenario (complete intermediate observations and high level of noise (20%) are almost similar to the first scenario. Noise slightly reduces the quality of learning in terms of syntactical error and accuracy for two IPC domains (Blocksworld and Zenotravel). For Peg Solitaire, the impact is stronger, however the majority of the problems are correctly solved (Acc = 63.3%). The impact of noise on the performance of AMSLI with complete intermediate observations is generally low.

The results of the third scenario (partial intermediate observations (25%) and no noise) are almost similar to the first scenario. Partial observation slightly reduces the quality of learning in terms of syntactical error and accuracy for one IPC domain (Parking). The impact of partial observation on the performance of AMLSI with noiseless observations is low.

Finally, the results of the fourth scenario (partial intermediate observations (25%) and high level of noise (20%)) show that partial intermediate observations downgrade the global performances of AMLSI. However, they remains high for all the IPC domains and metrics, and specifically for the accuracy. Despite partial and noisy observations, AMLSI is able to generate accurate PDDL domains. To our best knowledge, AMLSI is the only approach able to generate usable planning domains with these levels of noisy and partial observations.

Moreover, we can observe that domains including both positive and negative preconditions (Neg-Visit-All and Neg-Elevator) are easier to learn that domains including only positive preconditions. This is due to the fact that negative preconditions have a stronger impact on the fitness score of tabu search. Then, for domain using only positive preconditions, the easiest domains to learn (Gripper and N-Puzzle) are domains with the highest level of compression (see in the induced automaton, and the most difficult domain to learn (Peg Solitaire) is the domain with the lowest level of compression.

Impact of the initial state The choice of the initial state impacts the quality of the induced grammar induction used to generate the PDDL operators when domains. shows the standard deviation between the different initial states for each experimental scenario and for each of perfor-mance metrics. We can observe that for some domains the choice of the initial state has little to no impact on AMLSI's performances, e.g., Gripper, N-Puzzle, Neg-Visit-All, Neg-Elevator or Zenotravel. In other domains, e.g., Blocksworld, Hanoi, Parking and Peg Solitaire the impact is significant.

The performance gap between initial states can be explained by the different complexities of the grammars to induce. For instance, for the Peg Solitaire domain, the automaton learnt with the first initial state contains generally 20 nodes and 40 transitions and the compression level varies between 7 and 9, while the automaton learnt with the third initial state contains generally 50 nodes and 70 transitions and the compression level varies between 4 and 6. It is, therefore, easier to learn the domain with the first initial state than the third initial states. Also, the choice of the initial state impacts the coverage of the random walk in the generation step that can cause overfitting.

Ablation study In addition, we perform an ablation study of the AMLSI approach. We test each part of the AMLSI approach independently:

1. Generation Step: We learn domain by taking into account only the operator induction step. We can observe that for the majority of domains, this step is sufficient for the first experimental scenario (complete and noiseless observations). However when observations are partial and/or noisy, this step is not able to learn domains.

2. Simple refinement: We learn refined domain by taking into account only preconditions/effects precondition step, ie, without the Tabu search. As for the generation step, this step is generally able to learn domains when observations are complete and noiseless. In addition, this step is able to learn some domains (Blocksworld, Gripper, Hanoi and N-Puzzle) when observations are partial and noiseless. However when observations are noisy, this step is not able to learn domains. This is due to the fact that, during the mapping, noisy propositions will delete a large amount of information. The effect refinement steps will therefore no longer be able to detect all of the missing effects. In addition, when observations are noisy, there is a high risk that this step will detect additional effects that will not be removed by Tabu research.

3. Tabu search alone: We learn domain with only the Tabu search without the operator induction and preconditions/effects refinement steps. We can observe that for the majority of domains, tabu research alone is not capable of learning domains, whatever the experimental scenario. We can also note that taboo research alone generally learns the best areas when observations are noisy. Tabu search is therefore not sufficient to learn domains, and AMLSI is not able to learn domains without Tabu research either. This implies that it is the combination of tabu search effects and preconditions refinement step that allow AMLSI to learn accurate domains in each experimental scenario.

Grammar induction without pairwise constraints

Then, we test a variant of the AMLSI algorithm where the grammar induction was performed without pairwise The performance gap can be explained by the quality of induced grammar. Indeed, as we have seen in section 4, RPNI is optimal if and only if samples are "characteristic". The construction of a characteristic sample is not feasible a priori and we can't assume that the dataset generation produces characteristic samples. That implies that grammars induced without PC are generally more general that grammars induced with PC, and so there are generally more unfeasible paths, ie paths present in the grammar induced and not present in the ground truth grammar, in grammars induced without PC. These unfeasible paths causes noises in the effects refinement, ie, when grammars are induced without PC, extra effects are detected during the effects refinement step.

Finally, we can note that, when grammars are induced without PC, domains are generally better when observations are noisy. This due to the fact that when observations are noisy, effects refinement step detect less effects, so the tabu search has greater importance, and tabu search being independent of the induced grammar, induce grammars without PC has less impact when observations are noisy.

Comparison with LSO-NIO Then, we compare performance of AMLSI and LSO-NIO [START_REF] Mourão | Learning STRIPS operators from noisy and incomplete observations[END_REF]) which is the approach with the closest input setting. Indeed, LSO-NIO takes as input random walks including action failures with partial and noisy observations. LSO-NIO has been tested with I + and I -. Random walks including action failures are obtained by merging I + and I -. Note that, in our experiment LSO-NIO's training set contains between 2000 and 5000 with a majority of failed actions, while LSO-NIO was tested in [START_REF] Mourão | Learning STRIPS operators from noisy and incomplete observations[END_REF] with training set containing 20000 actions with an equal mixture of successful and unsuccessful actions. Also, for our experimentation, there are fewer objects in initial states than for the experimentation of [START_REF] Mourão | Learning STRIPS operators from noisy and incomplete observations[END_REF]. We use our own implementation of the LSO-NIO approach 4 .

We can observe that AMLSI outperforms LSO-NIO. These results can be explained in several ways. First of all, we generally have a lot of negative information than positive information. This is beneficial for AMLSI because it makes it possible to have a good automaton, moreover it makes it 4 Our implementation is available at https://www.dropbox.com/ sh/3gpcdasycuy4r9h/AACYDrwNeseOMFLX6tlmMZcWa?dl=0 possible to effectively lead tabu search. This is handicapping for LSO-NIO because the updated weights of the different classifiers need more positive information. In addition, LSO-NIO learns effects and preconditions by taking actions one by one into. While AMLSI, during the Tabu search, learns effects and preconditions by taking into account all action sequences.

Finally, we can note that the results of LSO-NIO are close to the results of AMLSI with Simple refinement.

Conclusion

In this paper we present AMLSI, a novel algorithm to learn PDDL domains. We assume that it is possible to query a system to model and to collect partial and noisy observations. AMLSI is composed of four steps. The first step consists in building two training sets of feasible and infeasible action sequences. In the second step, AMLSI induces a regular grammar. The third step is the generation of the PDDL operators, and the last step refines the generated operators. Our experimental results show that AMLSI successfully learns PDDL domains with high levels of noise and incomplete observations.

The performance of AMLSI depends a lot on the induced regular grammar. If the grammar is too complex, or too simple, AMLSI becomes more sensitive to noise and partial observations. As the complexity of the grammar depends on the initial states, future works will focus on the selection of the initial states. Moreover, it should be possible to bias the training set generation in order to obtain the best possible grammar while minimizing the queries. Finally, AMLSI will be extended in order to learn more expressive PDDL operators with disjunctive preconditions, conditional effects and numerical functions.

  f ectRef inement(D, Aut, µ A , µ P ); D ← preconditionRef inement(D); until D = D ; D ← tabuSearch(I + , I -, D); until D = D ; return D

Algorithm 2 :Ξ

 2 Precondition generation input : o: an operator output : ρ o : preconditions of o 1 Ξ ← {}; 2 for a instance of o do 3 τ ← {}; 4 for n in the automaton do 5 if a is an outgoing edge of n then 6 if µ A (n, a) = ∅ then 7 τ ← τ ∪ { µ A (n, a)}; ← Ξ ∪ {generalize(ρ a )}; 13 end 14 ρ o ← (Ξ); 15 return ρ o (b r 1 grip), the parameters of pick(b r 1 grip) (classical planning assumption (Fikes and Nilsson 1971)).

  AMLSI is evaluated with 4 metrics of the literature: Syntactical error The syntactical error error(o) (Zhuo et al. 2010) for an operator o is defined as the number of extra or missing predicates in the preconditions 3 ρ o , the positive effects + o and the negative effects - o divided by the total number of possible predicates. The syntactical error for a domain with a set of operator O is: E σ = 1 |O| o∈O error(o).

Table 2 :

 2 Benchmark domain characteristics (from left to right): number of operators, number of predicates, number of objects in each initial states, number of actions in each initial states, number of propositions in each initial states, average size of |I + | and |I -| training sets, the average length of the positive (resp. negative) training sequences π + ∈ I + (resp. π -∈ I -), average size of |E + | and |E -| test sets, the average length of the positive (resp. negative) test sequences e + ∈ E + (resp. e -∈ E -).

	1. Complete intermediate observations (100%) and no noise
	(0%),
	2. Complete intermediate observations (100%) and high
	level of noise (20%),
	3. Partial intermediate observations (25%) and no noise
	(0%).
	4. Partial intermediate observations (25%) and high level of
	noise (20%).
	Results are given by the Table -3.

Table 5 :

 5 Standard deviation between initial states for all the domains and metrics constraints (noted Without PC in Table -3). First of all, we can observe that the results are generally worse for each domain and for each experimental scenario.

Note that these preprocessing are only used for the grammar induction step.

Acknowledgements

This work was funded by the Circular project -IDEX.

No NA No No Yes Louga Plan traces Partial No Yes Yes No No Plan-Milner Plan traces Partial Yes NA No Yes No LOCM Plan traces No Observation -NA No No No LOCM2 Plan traces No Observation -NA No No No LOP Plan traces No Observation -NA Yes No No NLOCM Plan traces No Observation -NA Yes Yes No IRALe Random walk Complete Yes NA NA No No LSO-NIO Random walk Partial Yes No Yes No No AMLSI Random walk Partial Yes Yes Yes No No