François Bonnardel

Serge Perez

Frédérique Lisacek
email: frederique.lisacek@sib.swiss

Anne Imberty
email: anne.imberty@cermav.cnrs.fr

Structural Database for Lectins and the UniLectin Web Platform

Keywords: Lectin, Carbohydrate-binding protein, Database, Classification, Sequence, 3D structure, Profile-based prediction

The search for new molecules requires a clear understanding of biosynthesis and degradation pathways. This view applies to most metabolites as well as other molecule types such as glycans whose repertoire is still poorly characterized. Lectins are proteins which recognize specifically and interacts non-covalently with glycans. This particular class of proteins is considered as playing a major role in biology. Glycan-binding is based on multivalence, which gives lectins a unique capacity to interact with surface glycans and significantly contribute to cell-cell recognition and interactions. Lectins have been studied for many years using multiple technologies and part of the resulting information is available online in databases. Unfortunately, the connectivity of these databases with the most popular omics databases (genomics, proteomics and glycomics), remains limited. Moreover, lectin diversity is extended and requires setting out a flexible classification that remains compatible with new sequences and 3D structures that are continuously released. We have designed UniLectin as a new insight in the knowledge of lectins, their classification and their biological role. This platform encompasses UniLectin3D, a curated database of lectin 3D structures that follow a periodically updated classification , a set of comparative and visualizing tools and gradually released modules dedicated to specific lectins predicted in sequence databases. The second module is PropLec, focused on -propeller lectin prediction in all species based on five distinct family profiles. This chapter describes how UniLectin can be used to explore the diversity of lectins, their 3D structures and associated functional information as well as to perform reliable predictions of -propeller lectins.

Introduction

Lectins are oligomeric proteins that bind mono-and oligosaccharides reversibly and specifically while displaying no catalytic or immunological activity [START_REF] Lis | Lectins: Carbohydrate-specific proteins that mediate cellular recognition[END_REF]. Those complex carbohydrates (also referred to as glycans) occur in the form of single molecules, or as part of glycoconjugates (glycoproteins and glycolipids). They constitute the most abundant class of biomolecules on Earth. Complex carbohydrates are built for highdensity bio-coding, the information being carried and encoded in their 3D-structures and sometimes in their dynamics. Lectins are powerful macromolecular tools to decipher the high-density bio-encoding of complex carbohydrates. Along with a high-specificity, lectins exhibit diverse architectures and modes of multivalence relating to their function. Some lectins exhibit ''architectural multivalence'', consisting of one macromolecular structure with several, equivalent carbohydrate recognition domains. Other lectins, such as adhesins, are membrane-bound and include only one carbohydrate recognition domain, attached to fimbriae or flagella tethered to the cell surface. Several fimbrial structures clustered together at the cell surface also give a multivalent presentation of the lectins in the extracellular environment. All of these recognition processes play important roles in fertilization, embryogenesis, inflammation, metastasis, and parasitesymbiote recognition in microbes, invertebrates, plants, and vertebrates.

In 1984, Gallagher [START_REF] Gallagher | Carbohydrate-binding properties of lectins: A possible approach to lectin nomenclature and classification[END_REF] made a first attempt to classify and establish a nomenclature of lectins. Then, an overview of seven families of plant lectins [START_REF] Peumans | Classification of plant lectins in families of structurally and evolutionary related proteins[END_REF] and a classification of animal lectins [START_REF] Kaltner | Animal lectins: from initial description to elaborated structural and functional classification[END_REF] were proposed. Historically, these classifications were based on the discovery of new lectins supported by the resolution of their 3D structures. The accumulation of data revealed the occurrence of similar or closely similar protein motifs across several kingdoms. Consequently, a species-independent classification based on lectin sequence and 3D structure appeared more relevant. Such an approach was proposed through the association of 3D features and Pfam domains [START_REF] Fujimoto | Lectin structures: Classification based on the 3-D structures[END_REF]. Unfortunately, the approximate definition of Pfam domains [START_REF] Finn | Pfam: The protein families database[END_REF] that are rarely specific to lectin sequences not only reduces the accuracy of classes but also precludes the classification of newly discovered lectins. In the same vein, a classification of fucose-binding lectins based on Pfam domains was suggested by H. Makyio and R. Kato in 2016 [START_REF] Makyio | Classification and comparison of fucose-binding lectins based on their structures[END_REF]. The following examples illustrate the possible sources of ambiguity. Using "lectin" and "glycan binding" as keywords to search the UniProtKB database [START_REF] Bateman | UniProt: The universal protein knowledgebase[END_REF] returns roughly 159,000 and 230,000 distinct proteins, respectively (UniProt 2019-03 release). Searching the Protein Data Bank (PDB) through PDBe [START_REF] Mir | PDBe: Towards reusable data delivery infrastructure at protein data bank in Europe[END_REF] with the same keywords returns 3634 and 121 structures, respectively (PDB 2019-04-24 release). A close examination of the results indicates that some of these proteins are in fact glycoproteins that bind glycan covalently, and others are enzymes that recognize and modify glycans. This highlights the need for a robust classification of lectins and their ligands based on a large panel of finely curated or filtered information extracted from genomic data as well as 3D structures and their inter-atomic features.

Existing Lectin Databases

Due to the crucial role of lectins in cell recognition and interactions, a large amount of experimental information has been published. They encompass peptide sequences of the lectin domain as well as full protein sequences, 3D structures derived from diffraction studies which possibly contain the interacting carbohydrate, and glycan arrays which reflect the specificity for different glycans and their target affinity. Such a large body of information needs to be integrated and organized in a public database that is interoperable with other relevant omics databases. Several initiatives that we now briefly summarize, have been launched to address this question.

Glyco3D [START_REF] Pérez | Glyco3d: A portal for structural glycosciences[END_REF] includes a family of databases covering the 3D features of monosaccharides, disaccharides, oligosaccharides, polysaccharides, glycosyltransferases, lectins, monoclonal antibodies and glycosaminoglycan binding proteins that have been developed with nonproprietary software and are freely available to the scientific community (http://glyco3d.cermav.cnrs.fr).

The Lectin Frontier Database (LfDB: https://acgg.asia/lfdb2/) [START_REF] Hirabayashi | The lectin frontier database (LfDB), and data generation based on frontal affinity chromatography[END_REF] contains 400 lectins with curated information including lectin name, Pfam family, name of the interacting glycan, species, fold, PDB 3D structure, protein sequence and reference. It is now integrated in GlyCosmos, a newly developed portal (https://glycosmos.org/lectins/) for accessing and exploring knowledge in glycobiology.

LectinDB (http://proline.physics.iisc.ernet.in/lectindb/) [START_REF] Chandra | Lectindb: A plant lectin database[END_REF] is an annotated database mainly of plant lectins.

It can be searched based on their species, accession number, lectin domain, fold, PDB code and interacting glycan; a protein sequence can be compared to the lectins in lectinDB; an overview of lectin available in each species is also available; each lectin is associated with ataxon and a UniProt entry. SugarBindDB (http://sugarbind.expasy.org/) [START_REF] Mariethoz | SugarBindDB, a resource of glycan-mediated hostpathogen interactions[END_REF] provides integrated information on pathogen lectins and their corresponding glycan targets. This curated database describes either bacterial or viral proteins and details their binding specificity. Each ligand can be matched to full glycan structures of GlyConnect [START_REF] Alocci | GlyConnect: Glycoproteomics goes visual, interactive, and analytical[END_REF] and their associated glycoproteins to reveal potential glycan-mediated interactions between pathogen lectins and host glycoproteins. When 3D structures are available from PDB, they can be visualized with the LiteMol software [START_REF] Sehnal | LiteMol suite: interactive web-based visualization of large-scale macromolecular structure data[END_REF]. It also includes affinity data when available. Despite this high level of data and tool integration SugarBindDB remains focused on pathogenic virus and bacterial species.

The databases of the Consortium for Functional Glycomics (CFG resources: http://www.functionalglycomics.org/static/consortium/resources.shtml) [START_REF] Raman | Advancing glycomics: Implementation strategies at the consortium for functional glycomics[END_REF] include a repository of glycan array data used to measure the specificity of a lectin to multiples glycans. These databases are unfortunately no longer maintained. The latest related resource is GLAD (https://glycotoolkit.com/GLAD/) [START_REF] Mehta | GLAD: GLycan Array Dashboard, a visual analytics tool for glycan microarrays[END_REF] a webbased tool designed to visualize and analyze glycan microarray data, providing a list of available glycan array for lectins.

Most of these lectin-dedicated databases lack interaction details with protein and protein family [START_REF] Bairoch | The Universal Protein Resource (UniProt)[END_REF][START_REF] Jones | InterProScan 5: Genome-scale protein function classification[END_REF], protein structure classification databases [START_REF] Fox | SCOPe: Structural Classification of Proteins -Extended, integrating SCOP and ASTRAL data and classification of new structures[END_REF][START_REF] Sillitoe | CATH: Comprehensive structural and functional annotations for genome sequences[END_REF], glycans or protein glycan interaction analysis tools [START_REF] Lütteke | pdb-care (PDB CArbohydrate REsidue check): A program to support annotation of complex carbohydrate structures in PDB files[END_REF][START_REF] Salentin | PLIP: Fully automated protein-ligand interaction profiler[END_REF], and do not necessarily comply with glycan textual and visual representations now commonly accepted in the glycoscience community [START_REF] Haltiwanger | Symbol Nomenclature for Glycans (SNFG)[END_REF]. Such spread out information led us to design and implement the UniLectin platform (https://unilectin.eu) in order to address the data integration and classification issues. The present chapter describes the current content and the possible use of the UniLectin comparative, predictive and visualizing tools. The platform consists of modules the main one being UniLectin3D a curated database of 3-dimensional structures of lectins, as established mainly from crystallographic methods. It includes a classification of lectins, along with the knowledge of interacting glycans. Based on this information, we are gradually populating other modules dedicated to specific lectins predicted in sequence databases.The second module, PropLec, is focused on families of lectins that display a -propeller structure.

UniLectin3D, Database of Curated Lectin 3D Structure and their Interacting Ligands

The UniLectin3D database includes structural information on lectins along with their interactions with carbohydrate ligands. A curated classification is proposed based on origin and fold in association with the literature and functional data such as known specificity. The content of UniLectin3D is centered on 3dimensional data, using PDB information, with an appropriate curation of the glycan topology. It provides a family-based classification and cross-links to specialized glyco-related databases. Finally, the 3D visualization of contacts between the lectin and the ligand, is visualized via the Protein-Ligand Interaction Profiler (PLIP) application. The introduction of such a feature is likely to meet the expectations of lectin specialists. The threedimensional structures reported in UniLectin3D are those of lectins crystallized with or without their carbohydrates (glycans) ligands and non-carbohydrate ligands (see Background for detailed information). The current 2117 lectin structures were all manually curated; this corresponds to 534 different lectins (as of 2019-04-17). Bibliographic entries cover 860 published articles describing at least one structure. The first classification level, referred to as "origins", separates the lectins into seven different classes reflecting the main orders of the living kingdom. The second level orders the lectins according to the protein fold into 75 classes. The third level separates the lectins according to their species in 309 families.

Among the 2117 3D structures, 1338 occur as complexed with glycans. The most commonly observed monosaccharides are as follows: Galactose (Gal) 31%(730); N-Acetyl glucosamine (GlcNAc) 16%(377), Glucose (Glc) 15%(345), Mannose (Man) 12%(283), Fucose (Fuc) 9%(211), sialic acid (Neu5Ac) 9% (211), N-Acetyl galactosamine (GalNAc) 7% (170). Rarer sugars are also observed in complexes with lectins (Rhamnose, Arabinose …). The ligands occur as monosaccharides, but also as oligosaccharides or glycoconjugates. The set of distinct glycan ligands amounts to 222.

The following options are available for searching by: (1) keywords, (2) kingdom order, (3) historical classification, (4) monosaccharide and associate IUPAC sequence, (5) fold of the binding site and (6) multiple criteria. Once selected, lectins can be explored (and their features pictured and downloaded) by sequence (with the UniProt AC) and structure (with the PDB ID). For each lectin a detailed page is available with 3D visualization, interactions and links to external databases.

Searching by Keywords

The search can be performed by entering keywords as textual input: i.e. human, PDB code, UniProt accession number, lectin name, type of domains, fragment of glycan sequence, or textual fragments of the title of a publication: .e : human, propeller, 1TL2 (PDB), Q47200 (UniProt), GalNAc, Lewis.

Searching by Kingdom Order, Carbohydrate Binding Site Class and Species Family

Different modes are available for browsing the database and visualizing data coverage with respect to taxonomy. Lectin structures can be explored using two interactive graphical representations: a sunburst and a tree. The inner circle of the sunburst corresponds to the kingdom orders along with their respective percentage of occurrence. For a given kingdom order, (for example animal) the class of the carbohydrate binding site is displayed in the central section (for example galectins) whereas the species families can be browsed on the outer section (for example galectin 3). The hierarchical taxonomic tree (Figure 1A) can be used to explore the classification with the tree leaves expanding by clicking on the blue node and at each level. An advanced search can be launched by clicking on the label of the corresponding level.

Searching by Monosaccharide and Associate IUPAC Aequence

Glycans are described following the encoded IUPAC condensed nomenclature (http://www.sbcs.qmul.ac.uk/iupac/2carb/38.html). Ex. Gal(b1-4)GlcNAc(b1-2)Man(a1-3)[GlcNAc(b1-2)Man(a1-6)]Man

The nature of the interacting glycans can be visualized on a sunburst (Figure 1B). The inner circle corresponds to the monosaccharide that composes the carbohydrate chains interacting with the lectins, together with their respective percentage of occurrence. The outer circle corresponds to the carbohydrate chains. For a given monosaccharide (D-Galp for example) the number of occurrences of glycans containing the selected monosaccharide is displayed (for example 29 in the case of Gal(b1-3)GalNAc). Clicking on a selected glycan (for example Gal(b1-3)GalNAc) lists the 3D structures of lectins complexed with this carbohydrate.

A distinct interface is accessible (Figure 1C) by clicking the glycan search button. It allows searching for glycans through a combination of monosaccharides. Only the carbohydrates present in at least one lectin 3D structure and containing the selected monosaccharides are displayed in the SNFG format (Figure 1D). By clicking on a carbohydrate name, an advanced search is launched based on it.

Searching by Fold

The lectin fold is defined by the relative spatial arrangement of secondary structure elements. It characterizes the multiplicity of glycan binding and it is directly linked to the ability of lectins to bind and cross-link glycan containing molecules in a multivalent fashion. A sunburst representation indicates the occurrence of the main fold of lectins. Clicking on a selected section of the circle displays the nature and the occurence of the folds as identified in the crystal structures. Upon a click, buttons prompt the information pertaining to the lectin displaying the particular fold.

Figure 1. Interfaces for the exploration of the lectin classification and associated carbohydrates ligands. A. Treeview of the classification highlighting the option of opening each node to display branching at the lower level. B. Sunburst as an overview of the glycans distribution. C. Glycan search dedicated page for selecting monosaccharides to be searched in all structures. D. Example of the oligosaccharides obtained by selecting D-Neup5Gc in the monosaccharide panel.

Advanced Search, Searching by Multiple Criteria

This advanced search option offers a range of criteria to be selected in a combined fashion in order to search the whole database for specific lectins or structures. Practically, lectins can be searched by 3D structure or by sequence family with the support of drop-down lists (Figure 2A) and they can be filtered based on a large number of features (Figure 2B). (i) The classification of lectins (Origin, Class, and Family); (ii) the nature of the fold and taxonomic details of the lectin; (iii) Keywords from the title of a reference article; (iv) A unique feature is the search of fragments of glycan ligands, also called oligosaccharide motifs, that interact with the lectin. (v) Finally, a cutoff on the resolution (Å) of the X-ray structure can be used as a filter for selecting of high-quality data. UniLectin3D allows precise taxonomic search (vi) for all lectins that have been structurally characterized in a given organism.

The resolution criteria relate to the quality of the structural determination (High numeric values of resolution, such as 4 Å, mean poor resolution, while low numeric values, such as 1.5 Å, indicate a good resolution. (The median resolution for X-ray crystallographic results in the Protein Data Bank is 2.05 Å). Whenever the resolution is set to 0, the structures are not filtered.

Figure 2. Multiple criteria search of a lectin, with a detailed interface with information and 3D-visualization. A. Multicriterion window for advanced search. B. Example of results obtained by searching for an oligosaccharide. C. Detailed graphical information provided for the entry shown in B.

Lectin Sequence Setailed Interface

The accession number (AC) which is assigned to each lectin sequence upon inclusion into UniProtKB can be used for searching. As one lectin sequence can be related to multiple PDB structures these are displayed in the results together with the ligand(s) shown in the SNFG representation. Some structures may have been published in multiple articles; these are listed together with the corresponding link to PubMed (http://www.ncbi.nlm.nih.gov/pubmed). When available, the structures are displayed on the main protein sequence in a 2D viewer provided by PDBe [START_REF] Mir | PDBe: Towards reusable data delivery infrastructure at protein data bank in Europe[END_REF].

X-Ray Structure Detailed Interface

The PDB code which is assigned to each lectin structure is used to list available lectin structures and to display more detailed information (Figure 2C). Each structure is related to a protein with a UniProt AC. Other related PDB structures are listed together with their interacting glycans if any. The 3D X-ray structure of the lectin is visualized directly and interactively with the integration of the LiteMol [START_REF] Sehnal | LiteMol suite: interactive web-based visualization of large-scale macromolecular structure data[END_REF] and NGL [START_REF] Rose | NGL viewer: Web-based molecular graphics for large complexes[END_REF] viewers (Figure 2D).

Information about the interaction occurring between the glycan and the combining sites of the lectin can be obtained using the Protein-Ligand Interaction Profiler (PLIP) server [START_REF] Salentin | PLIP: Fully automated protein-ligand interaction profiler[END_REF]. The description of the glycan complies with representations and numerical descriptors that allow for cross-linking to other databases in glycoscience. The architecture and navigation tools are designed to extend the search to all organisms, as well as to search for all glycan epitopes complexed within specified binding sites. The NGL viewer adapted to SwissModel [START_REF] Bienert | The SWISS-MODEL Repository-new features and functionality[END_REF] displays the interactions as resulting from the PLIP application. This offers a detailed 3D visualization of the specific features of the interactions between the glycans and the surrounding amino-acid residues and possible metal ions. A complementary description of the 3D interactions between the lectin and glycan is given by the domain viewer of the PDBe.

PropLec, database of structure-based predicted β-propellers

The PropLec database includes predicted β-propeller lectins along with their features and conserved regions. In structural biology, a β-propeller is a particular type of beta-sheet protein architecture characterized by 4 to 8 highly symmetrical blade-shaped β-sheets arranged toroidally around a central axis. Together the β-sheets form a funnel-like active site. The blade consists of a small domain of less than 50 amino acids. The repeated blades hamper the identification of similar lectins when using common software based on pairwise sequence alignment such as BLAST [START_REF] Camacho | BLAST+: architecture and applications[END_REF]. However, the multiple alignment of blades manually adjusted with knowledge of 3D structures produces a unique conserved domain. This blade domain can then be used to compare all known β-propeller lectins and this systematic comparison led to the definition of five distinct families. To simplify the nomenclature, each family is named based on the number of blades, e.g. PropLec5A (Tachylectin 2 like), PropLec6A (RSL and AAL like), PropLec6B (Tectonin like), PropLec7A (PLL like) and PropLec7B (PVL like) (Figure 3A).

Figure 3. β-Propeller families. A. The five families of β-propellers used to build the database. B. Analysis of repartition of the different families exemplified by searching for animal lectins (metazoan) and fungal lectin

The specific signature of each family has been used to predict with HMMER [START_REF] Finn | HMMER web server: 2015 Update[END_REF] possible β-propeller lectins from the UniProt sequence database [START_REF] Bateman | UniProt: The universal protein knowledgebase[END_REF] and are associated with RefSeq if available [START_REF] O'leary | Reference sequence (RefSeq) database at NCBI: Current status, taxonomic expansion, and functional annotation[END_REF]. The results of this prediction are stored and can be searched in the PropLec module of UniLectin, based on their family, species, taxonomy, number of blades, associated enzymatic functions and other additional features.

Searching by Keywords and by Family

The features of the predicted β-propeller lectins can be explored using multiple criteria from the homepage. A quick search can be performed by keywords: i.e. accession number, species name or protein name. The five families are then made accessible through buttons along with a pie chart depiction of the distribution of the number of predicted proteins in each family. Based on the two distinct sets Animal and Fungi, the distribution of the number of predicted β-propellers is represented (Figure 3B). As expected, a majority of the predicted animal β-propeller are PropLec6B and a majority of the predicted Fungi β-propellers are PropLec6A. Surprisingly, ProLec7A from Photorhabdus luminescens is predicted in both Animals and Fungi, and PropLec 7B from Psathyrella velutina is predicted in Animals.

Searching by Number of Blades in the Propeller

The number of blades in the predicted β-propeller lectins can be used to search for particular structures. The result is shown as a histogram representing the distribution of the predicted lectins relative to the number of blades identified in sequences. Clicking on any of the bars of the histogram prompts the details of the corresponding predicted lectins.

Searching by Phylum

The search can be performed by selecting in the Taxonomy sunburst either a superkingdom, a phylum or species. The distribution of predicted lectins across species can be explored at each level. As the sunburst is built as concentric circles, the inner circle represents the superkingdom, the next circle the kingdom, the third circle the phylum, the fourth circle the species group and the outer circle the species. Clicking on any of the circle sections prompts the details of the predicted lectins found in the selected taxonomic group.

Advanced Search

Predicted propeller lectins can be selected using a combination of criteria, and the corresponding lectins are then ordered by scores (highest to lowest). Possible combinations involve: (i) the prediction score threshold, which is set 0.25 by default; (ii) the identified propeller family; (iii) the number of blades identified; (iv) the maximum distance between blades; (v) keywords that exclude proteins based on their description, set by default set to "partial, synthetic and undefined", (vi) taxonomy, (vii) Pfam domains, (viii) RefSeq AC, (ix) protein name and description; (x) UniProt AC. The "checkbox pathogen" button offers the possibility to restrict the search to a particular pathogen species, based on the NIH predefined list of pathogen species.

A graphic overview of the properties of predicted propeller lectins resulting from searching with a single criterion or a combination of criteria, is generated. It shows : (i) the distribution of the PropLec families; (ii) the distribution of the number of blades; (iii) a sunburst and a tree representation -as in the homepage. Clicking on the graphic sections displays further details. The predicted lectins matching the criteria are ordered by score with 20 items per page. For each predicted lectin, the following features are displayed: (i) protein name; (ii) UniProt AC and RefSeq AC which can be clicked to access the corresponding pages in the respective sequence databases; (iii) protein length, (iv) species, (v) domain identified in the Proplec families, (vi) number of blades; (vii) similarity score of the predicted protein blades to the reference blade; (viii) protein-coding gene list including chromosome number(s) and location.

For each predicted lectin, an in-house 2D sequence viewer indicates the localization of the predicted blades and possible Pfam domains. Zooming in the sequence is performed via a drag and drop button. Further details are available by clicking the more information button.

Detailed Results

For each lectin, a detailed panel and page are available with the NCBI gene viewer and a representation of the blade conservation compared to the reference. The protein features were described in the previous section. The protein-coding gene and its location on a chromosome is represented by the NCBI viewer, when the information is available [START_REF] Brown | Gene: A gene-centered information resource at NCBI[END_REF]. The view can be scrolled back and moved by drag and drop to check the surrounding genes. To compute the score, the predicted lectin blades have been aligned against the reference blades by the MUltiple Sequence Comparison by Log-Expectation (MUSCLE) [START_REF] Edgar | MUSCLE: multiple sequence alignment with high accuracy and high throughput[END_REF]. To provide a more detailed view of the blade conservation, the resulting alignment is represented in two distinct bar charts. The first bar chart, on top, contains the amino acid conservation of the predicted blades. The second represents the amino acid conservation of the reference blade. As all blades are aligned, the bar chart position facilitates the comparison between sequences. The binding sites are represented, along with the amino acids known to interact with glycans either by a hydrogen bond or by hydrophobic interactions.

Searching by Other Pfam Functional Domains

Lectin domains can either bea whole lectin protein or only one part of a larger multi functional protein.

Proteins with a predicted lectin β-propeller domain(s) and other functional Pfam domains can be explored to evaluate possible combination(s). Such complex architecture is of particular interest as it highlights the specificity of lectins towards a definite carbohydrate in combination with other functional domain(s) (ie. a glycan transferase). For each component of the protein architecture, a button prompts the list of predicted lectins displaying a similar pattern.

Conclusion and Discussion

The development of high quality glycomics databases counteracts the lack of precision reflected in the abundance of unreviewed and incorrect information regarding both glyconjugates and glycan-binding proteins in genome and protein databases. Here, we reviewed databases with information on lectins and their interacting glycans (mono, oligo, and polysaccharides). The recently released UniLectin platform provides a curated classification of lectins along with their reviewed interactions with glycans. Tools that facilitate lectin knowledge exploration were implemented. UniLectin has recently exceeded 2000 lectin structures. The platform also includes a tutorial that describes step by step the usage of simple and advanced search of the UniLectin databases covering lectin 3D structures and predicted β -propeller lectins .

We strive to ensure content accuracy and regular updates of the UniLectin platform as well as to provide a user-friendly tool collection (search, visualization, etc). Currently, UniLectin has a growing community whose feedback is key to driving further development. Based on UniLectin3D curated information and lectin classes, a high-quality prediction of lectins in genomes is a reachable short term goal but it still requires the revision of the current classification criteria, including amino acid sequence patterns.

Acknowledgments

The authors acknowledge support by the ANR PIA Glyco@Alps (ANR-15-IDEX-02) and the Alliance Campus Rhodanien Co-funds (http://campusrhodanien.unige-cofunds.ch).


Elena Ivanova
email: elena.ivanova@l2s.centralesupelec.fr

Antoine Girard
email: antoine.girard@l2s.centralesupelec.fr

Lazy Safety Controller Synthesis with Multi-Scale Adaptive-Sampling Abstractions of Nonlinear Systems

Keywords: Safety, lazy controller synthesis, multi-scale abstraction, adaptive sampling

In this paper, we present an abstraction-based approach to safety controller synthesis for continuous-time nonlinear systems. To reduce the computational burden associated with symbolic control approaches, we develop a lazy controller synthesis algorithm, which uses the incremental forward exploration of the symbolic dynamics, allowing us to restrict the controller synthesis computations to reachable states only. We propose using this algorithm with novel multi-scale abstractions, which also use adaptive time sampling. Transition duration is constrained by intervals that must contain the reachable set, which enables a better control of the symbolic transitions as opposed to using transitions of predetermined duration. Implementation of the algorithm and controller refinement are discussed. We provide a simple example to illustrate this benefits of the approach.

INTRODUCTION

Robust control synthesis for nonlinear dynamical systems subject to state and input constraints is a challenging problem in modern control theory. To tackle this problem, computational techniques are used within an abstractionbased framework. This method consists in creating a finitestate abstraction (or a symbolic model) for a continuous or a hybrid system, a procedure where a controller synthesized for the abstraction can be refined to a controller for the original system [START_REF] Belta | Formal Methods for Discrete-Time Dynamical Systems[END_REF], [START_REF] Tabuada | Verification and control of hybrid systems: a symbolic approach[END_REF]). This approach makes it possible to use discrete controller synthesis techniques [START_REF] Cassandras | Introduction to Discrete Event Systems[END_REF], [START_REF] Cormen | Introduction to Algorithms[END_REF]), which in turn allow us to address a broad class of specifications given, for instance, by automata or temporal logic formula. In this paper, though, we focus on simple safety specifications, which consist in keeping the state of the system inside a given safe set. This type of specification often appears in real-world problems, e.g. temperature regulation in smart-buildings [START_REF] Meyer | Compositional abstraction and safety synthesis using overlapping symbolic models[END_REF], [START_REF] Thavlov | A heat dynamic model for intelligent heating of buildings[END_REF]), blood glucose rate control for diabetic patients [START_REF] Kushner | Models, devices, properties, and verification of artificial pancreas systems[END_REF], [START_REF] Gillis | Glucose estimation and prediction through meal responses using ambulatory subject data for advisory mode model predictive control[END_REF]), safety of vehicle platoons [START_REF] Saoud | Efficient synthesis for monotone transition systems and directed safety specifications[END_REF], [START_REF] Ames | Control barrier function based quadratic programs for safety critical systems[END_REF], [START_REF] Alam | Guaranteeing safety for heavy duty vehicle platooning: Safe set computations and experimental evaluations[END_REF]), satellite station keeping [START_REF] Weiss | Station keeping and momentum management of low-thrust satellites using mpc[END_REF]), etc.

A key-issue in abstraction-based control is computational complexity. Indeed, symbolic models are usually obtained by partitioning or by discretizing the sets of states and inputs, and finer discretizations that provide more accurate abstractions result in symbolic models with a larger num-ber of states and inputs, and thus require more time and memory for computations. Moreover, the computational complexity of the discrete controller synthesis algorithms typically depends on the size of symbolic models. Finally, while all these computations are typically handled offline, a controller obtained via abstraction-based techniques using symbolic models with a large number of states would require a huge amount of memory for its real-time implementation. Possibilities to mitigate these intensive computational requirements are to refine abstractions iteratively [START_REF] Gol | Languageguided controller synthesis for linear systems[END_REF]; [START_REF] Nilson | Augmented finite transition systems as abstractions for control synthesis[END_REF]), e.g. using multilayered grids [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]; [START_REF] Hsu | Multi-layered abstraction-based controller synthesis for continuous-time systems[END_REF]). Starting from coarse abstractions, these are refined locally only where it is needed. Symbolic models are often represented as finite transition systems. The computation of the transition relation is a demanding process, requiring over-approximation of the reachable sets. Several methods exist for computing such over-approximations [START_REF] Girard | Reachability of uncertain linear systems using zonotopes. Hybrid Systems: Computation and Control[END_REF], [START_REF] Kurzhanski | Dynamics and Control of Trajectory Tubes[END_REF], [START_REF] Reissig | Feedback refinement relations for the synthesis of symbolic controllers[END_REF], Meyer et al. (2018a)), with a compromise between precision and simplicity of implementation. We can occasionally use structural properties of the dynamics such as monotonicity [START_REF] Coogan | Efficient finite abstraction of mixed monotone systems[END_REF]) or incremental stability [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]) to ease these computations. However, reducing the number of transitions that should be computed, renders the process less demanding. This is the purpose of lazy controller synthesis algorithms [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]; [START_REF] Hussien | Lazy controller synthesis using three-valued abstractions for safety and reachability specifications[END_REF]; Hsu et al. (2018a); [START_REF] Saoud | Efficient synthesis for monotone transition systems and directed safety specifications[END_REF]) where the transitions are explored as needed and computed on the fly during a controller synthesis. Given an ordering of transitions, transitions of lower priority are only explored if the specification cannot be enforced using transitions of higher priority.

In the first part of this paper, we present a novel lazy controller synthesis algorithm for safety (set invariance) specifications. A major difference with [START_REF] Hussien | Lazy controller synthesis using three-valued abstractions for safety and reachability specifications[END_REF]; Hsu et al. (2018a); [START_REF] Saoud | Efficient synthesis for monotone transition systems and directed safety specifications[END_REF]) is that our algorithm uses incremental forward exploration of the symbolic dynamics and thus allows us to restrict the controller synthesis computations to reachable states only. While this idea was used in [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]) for deterministic symbolic models, the algorithm presented in this paper makes it possible to deal with non-deterministic transition relations. In the second part of the paper, we propose a novel approach to compute multi-scale abstractions. Similar to [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]; Hsu et al. (2018a)), our approach uses multi-layered grids on the state-space. The main contribution in this part is a novel method for adaptive time sampling. The duration of the transitions is constrained by a state interval that should contain the reachable set, as opposed to a predetermined duration. This provides the opportunity to control, approximately, where symbolic transitions end. The resulting abstraction is equipped with priorities on transitions, which makes it possible to use lazy controller synthesis algorithms. This paper is organized as follows. In Section 2, we present a lazy safety controller synthesis algorithm for non-deterministic transition systems. In Section 3, we present an abstraction-based approach for synthesizing safety controllers for nonlinear systems. We introduce a type of multi-scale adaptive-sampling abstractions, which can be used in combination with lazy synthesis algorithms. Practical implementation of the algorithm and controller refinement are discussed. In Section 4, we consider a simple illustrative example to show the benefits of the approach.

LAZY SAFETY CONTROLLER SYNTHESIS

In this section, we present a lazy controller synthesis algorithm for finite transition systems and safety specifications. Definition 1. A finite transition system is a tuple Σ = (Q, U, F ), consisting of a finite set of states Q, a finite set of inputs U , and a transition relation

F ⊆ Q × U × Q.
For every transition (q, u, q ) ∈ F the state q is named u-predecessor of q and similarly the state q is named u-successor of q. For the set of all u-predecessors of the state q the notation F -1 (q, u) is used, while the set of all u-successors of a state q is denoted by F (q, u). If there is q ∈ Q, u ∈ U such that | F (q, u) | > 1, then the transition system is called non-deterministic, otherwise it is deterministic.

Since F (q, u) may be empty let us introduce a set Enab F (q) = {u ∈ U | F (q, u) = ∅} of all enabled inputs at a state q ∈ Q. If Enab F (q) = ∅, then q is said to be blocking, otherwise it is non-blocking. We also use notation Block F (Q ) to describe the set of all blocking states in a set Q ⊆ Q. If Block F (Q) = ∅, then the transition system is called non-blocking. Definition 2. A trajectory of a transition system Σ = (Q, U, F ) is a finite or infinite sequence of transitions

q 0 u0 -→ q 1 u1 -→ q 2 u2 -→ q 3 u3 -→ . . ., s.t. q i ∈ Q, u i ∈ U and q i+1 ∈ F (q i , u i ) for all i ≥ 0.
A state q ∈ Q is reachable from the state q, if q = q or there exists a trajectory connecting them. The set of all reachable states from the state q is denoted by Reach F (q). This definition could be naturally extended for a subset Q of the set of states Q:

Reach F (Q ) = ∪ q∈Q Reach F (q).

Safety Controllers

Definition 3. A controller for a transition system Σ = (Q, U, F ) is a map C: Q → 2 U , such that C(q) ⊆ Enab F (q) for every q ∈ Q.

Let us use notation Dom(C) = {q ∈ Q | C(q) = ∅} for a domain of controller C. We also define the controlled transition relation F C = {(q, u, q ) ∈ F | u ∈ C(q)}. Definition 4. A safety controller for a transition system Σ = (Q, U, F ) and a safe set Q s ⊆ Q is a controller C such that the following two properties holds (1) Dom(C) ⊆ Q s ;

(2) for all q ∈ Dom(C) and for all u ∈ C(q) the inclusion F (q, u) ⊆ Dom(C) is satisfied.

For a given specification, there are usually several safety controllers, however, the following standard result [START_REF] Tabuada | Verification and control of hybrid systems: a symbolic approach[END_REF]) states that there is a unique maximal one: Lemma 5. For a given transition system Σ = (Q, U, F ), a safety specification Q s ⊆ Q there is a unique maximal safety controller C such that for any safety controller C the following holds

(1) Dom(C) ⊆ Dom( C);

(2) for all q ∈ Dom(C), C(q) ⊆ C(q).

The maximal safety controller C is the best possible safety controller in the sense that any other controller solving the same safety problem would be more restrictive. That justifies the following notion of controllability. Definition 6. Let Q s be a safe set. A state q ∈ Q of the transition system Σ = (Q, U, F ) is safety controllable if and only if q ∈ Dom( C). The set of safety controllable states is denoted Cont(Σ, Q s ).

Though there is (see Tabuada ( 2009)) a simple fixedpoint algorithm converging to the controller C for any given finite safe set Q s , its computational complexity essentially depends on the number of safe states, making C too labour-intensive for many real-world problems. In light of this, in the next section, we relax, under certain assumptions, the maximality requirement for a desirable controller, while retaining other important properties.

Maximal Lazy Safety Controller

Let us suppose that the initial set

Q init ⊆ Q is fixed.
In this case, we have no interest in providing a controller for non-reachable states. Moreover, if a set of inputs U is equipped with a partial order, and for some state several inputs preserve safety, it would to be reasonable to keep only those which have the highest priority. Here we say that an input u ∈ U has higher priority than u ∈ U if and only if u u .

Assumption 7. Let the set of inputs U be split into N non-intersecting subsets U = U 1 ∪ U 2 . . . ∪ U N and for all u ∈ U i , u ∈ U j , i < j, i, j ∈ {1, . . . , N } it holds that u ≺ u , while inputs belonging to the same subset are considered as equivalent. Definition 8. [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]). For a given transition system Σ = (Q, U, F ), a safety specification Q s ⊆ Q, and a fixed initial set Q init ⊆ Q a maximal lazy safety (MLS) controller C * is a safety controller satisfying the following properties

(1)

Q init ∩ Cont(Σ, Q s ) ⊆ Dom(C * ); (2) Dom(C * ) ⊆ Reach F C * (Q init ∩ Dom(C * )); (3) for all states q ∈ Dom(C * ): (a) if u ∈ C * (q) then for all u ∈ Enab F (q) such that u u, it holds that u ∈ C * (q) if and only if F (q, u ) ⊆ Cont(Σ, Q s ); (b) if u ∈ C * (q), then for all u ∈ Enab F (q) with u ≺ u , it holds that F (q, u )∩Cont(Σ, Q s ) = F (q, u ).
The term maximal comes from the fact that all safety controllable initial states are in Dom(C * ), and if the controller enables an input, it also enables all inputs which have the same priority and preserve safety. The term lazy refers to the fact that while several inputs can preserve safety, the controller enables only inputs with the highest priority. Hence, C * represents a trade-off between maximal permissiveness and efficiency. Theorem 9. [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF]). For a given transition system Σ = (Q, U, F ), a finite safety specification

Q s ⊆ Q, and a fixed initial set Q init ⊆ Q there is a unique MLS controller C * .
Intuitively, the MLS controller C * can be obtained from the maximal safety controller C by keeping, for every state, only those enabled controls which have a higher priority, and by removing the states that are not reachable from initial states. Of course, it is not the best way to find C * since it needs first to compute C.

Efficient MLS Controller Synthesis

In this section, we provide a more efficient algorithm for computing the MLS controller, which is based on two ideas: to explore, for each state, inputs with a lower priority only if we failed to find a safe input with higher priority, and to set aside states that are non-reachable from the initial set.

To implement the first idea, we introduce for every state q ∈ Q a notion of a state priority p(q) and define for every given p: Q → {0, . . . , N } a reduced transition relation F p such that (q, u, q ) ∈ F p if and only if p(q) ∈ {1, . . . , N }, u ∈ U p(q) , (q, u, q ) ∈ F and for all q ∈ F (q, u) the equality p(q ) = 0 is satisfied. Intuitively, this means that for states with priority from 1 to N, only transitions with the same priority inputs are considered, while states with priority 0 are blocking and non-reachable. Starting with the highest priority for states in a safe set Q s and with the lowest one for the others (line 2-6), we iteratively update the function p in the main block of Algorithm 1 (lines 7-12) until a corresponding transition relation F p can be used as a basis for a desirable safety controller (lines 13-17). As concerns the second idea, only states that are In simple words, Algorithm 1 is an alternation procedure between a forward state space exploration and a backward correction of the obtained transition system in order to satisfy the safety requirements. At the beginning of every iteration, we update for every state a set of enabled inputs, which depends on the priority of the state. Then we try to find a safety controller. If we fail, we reduce the priorities of all uncontrollable states by one point and start again.

Algorithm 1: MLS Controller Synthesis Input: Σ = (Q, U, F ), Q init , Q s Output: MLS controller C 1 begin 2 for q ∈ Q do 3 if q ∈ Q s then 4 p(q) := N ; 5 else 6 p(q) := 0; 7 R := Reach Fp ({q ∈ Q init | p(q) = 0}) ; 8 while Block Fp (R) = ∅ do 9 B := Block Fp (R); 10 for q ∈ B do 11 p(q) := p(q) -1; 12 R := Reach Fp ({q ∈ Q init | p(q) = 0}) ; 13 for q ∈ Q do 14 if q ∈ R then 15 C(q) := Enab Fp (q);

ABSTRACTION BASED CONTROL SYNTHESIS

In this section, we consider a safety control problem for continuous-time nonlinear systems, and propose a solution based on Algorithm 1, combined with a novel type of multiscale adaptive sampling abstractions.

Problem Formulation

A control system Σ = (T, R n , U, W, f ) consists of a time domain T = [0, +∞), a state space R n , a compact set U ⊂ R m , a compact set W ⊂ R p , and a non-linear function f : R n × U × W → R n , such that for any control u(•) ∈ L ∞ (T, U ), any disturbance w(•) ∈ L ∞ (T, W ) and any initial condition x(0) ∈ R n there is a unique solution x f (t | x(0), u(•), w(•)), t ∈ T of the following differential equation ẋ(t) = f (x(t), u(t), w(t)
) in the sense of Caratheodory. The notation L ∞ (T, S) is used for the space of all measurable on T functions s(•) such that s(t) ∈ S, for almost all t ∈ T .

In this paper, we are looking for admissible safety controllers, which keep all trajectories of the closed-loop sys-tem inside a safety set Y , while supposing that an initial set X 0 is known before computation. Here the controller is said to be admissible if it is robust against any measurable bounded disturbance w(•) ∈ L ∞ (T, W ) and a solution of the closed-loop system exists. To synthesize such a controller, we use an abstraction-based approach. In the next section, the continuous system Σ = (T, R n , U, W, f ) is abstracted by a finite transition system Σ A = (Q A , U A , F A ), which approximates the behavior of the original plant. Then, we explain how to refine the controller for the abstraction (which could be found using Algorithm 1) to a controller for the concrete system.

Symbolic Model for the Original Plant

Let us first remark that all the vector operations appearing in this section are considered as component-wise.

We start the construction of a symbolic model for the original plant Σ = (T, R n , U, W, f ) by discretizing the state space R n . Let X = [x, x) be an n-dimensional interval including a safe set Y . Given a number L > 0, and a state space sampling parameter n x > 0, n x ∈ N n we introduce for every l = 1, . . . , L a uniform partition

Q l = {q ∈ 2 X | ∃z ∈ Z n s.t. q = [x + z * η l , x + (z + 1) * η l )}
where η l = (x -x)/(2 l-1 n x ) and we associate every state x ∈ X with a unique cell q ∈ Q l such that x ∈ q. We also define for every q ∈ Q l , the center of the interval q c = x+(z+ 1 2 ) * η l . Depending on the context, we regard an element q ∈ Q l either as an atomic symbol, representing an infinite number of states from X, or as a subset of X. It is obvious from the definition that for any q i , q j ∈ Q l , q i = q j the intersection q i ∩ q j = ∅ and that X = ∪ q∈Q l q. Proposition 11. For any l = {1, . . . , L -1} and for any q ∈ Q l there exists a unique set a states {q i } 2 n i=1 , q i ∈ Q l+1 such that q = ∪ 2 n i=1 q i .

Regarding the safety specification, an element q ∈ Q l is a safe state if and only if q ⊆ Y , an initial state if and only if q ∩ X 0 = ∅. Let us denote by Q l,s a set of all safe states in Q l , and by Q l,init a set of all initial states.

We then combine all these partitions into a multilayered grid Q A = ∪ L l=1 Q l and use it as a set of states for the abstraction Σ A = (Q A , U A , F A ). Considering that for any q ∈ Q A there exists a unique layer Q l ⊂ Q A such that q ∈ Q l , let us define a function l : Q A → {1, . . . , L} returning the index of the layer to which q belongs. We also introduce an input up, allowing switching from the current layer to the previous (coarser) one.

In the next step, a control set U is approximated by its finite subset U µ ⊆ U . For every q ∈ Q l , u µ ∈ U µ we consider the set of all reachable states at the time t ∈ T :

Reach(t | q, u µ ) = {x ∈ R n | ∃ x(0) ∈ q and ∃ w(•) ∈ L ∞ ([0, t], W ) such that x f (t | x(0), u * (•), w(•)) =
x}, corresponding to an initial set q, a constant control function u * : [0, t] → u µ and all admissible disturbances w(•). Since exact computation of reach set is seldom possible, an over-approximation Reach(t | q, u µ ) is commonly used to built symbolic models. In this paper, a multi-scale symbolic model is considered, which means that for every given state q ∈ Q A and control u µ ∈ U µ we construct n p transition with different duration. Let us now define a transition relation F A for every available input in the set U A = (U µ × {1, . . . , n p }) ∪ {up}.

Reach(τ u,2 q | q, u) q ′ q up u Reach(τ u2,2 q | q, u 2 ) Reach(τ u1,1 q | q, u 1 ) q q c u 2 u 1 (2 + 1/2)η l (1 + 1/2)η l η l
• for any q ∈ Q A \ Q 1 the transition (q , up, q) ∈ F A if and only if q ∈ Q l(q)-1 and q ⊂ q . See Fig. 1 (left). • for any q ∈ Q A and any (u µ , j) ∈ U µ × {1, . . . , n p } the transition (q, (u µ , j), q ) ∈ F A if and only if

q ∈ Q L , q ∩ Reach(τ uµ,j q | q, u µ ) = ∅,
(1) and the condition of a collision avoidance

Reach(t | q, u µ ) ∩ (X \ Y ) = ∅, t ∈ [0, τ uµ,j q ] (2)
is satisfied. Here τ uµ,j q = min(τ l , τ uµ,j q -ε), where τ l is a given parameter which determines the maximal evolution time allowed at this layer, while τ uµ,j q is a moment in time

τ uµ,j q = inf t∈[0,+∞) Reach(t | q, u µ ) ⊂ ⊂ [q c -(j + 1/2) * η l , q c + (j + 1/2) * η l ) (3)
when the over-approximation of a reachable set leaves the interval with a radius (j+1/2)η l and a center in q c . We chose ε < τ uµ,j q arbitrary small to stop evolution just before leaving, while τ l should be big enough since it serves only to manage situations where a solution is stuck within the box. In the Fig. 1 there is illustration of the idea. Such a definition of transition duration using adaptive time-sampling is a contribution of this paper. Instead of using prescribed time sampling parameters [START_REF] Girard | Safety controller synthesis for incrementally stable switched systems using multiscale symbolic models[END_REF], [START_REF] Hsu | Multi-layered abstraction-based controller synthesis for continuous-time systems[END_REF]), this approach allows us to control, approximately, where symbolic transitions finish and better analyze the behaviour of the system. At the same time, the collision avoidance condition allows us to eliminate solutions, which start and end in the safe set but passes some unsafe regions during the evolution. However, since the intersection of the reachable set with the grid is checked at every instant of time, the authors recommend using simple interval over-approximations [START_REF] Reissig | Feedback refinement relations for the synthesis of symbolic controllers[END_REF], [START_REF] Moor | Abstraction based supervisory controller synthesis for high order monotone continuous systems[END_REF], Meyer et al. (2018a), [START_REF] Zamani | Symbolic models for nonlinear control systems without stability assumptions[END_REF], [START_REF] Maidens | Reachability analysis of nonlinear systems using matrix measures[END_REF]), trading accuracy for simplicity of implementation. We also finish any non-up transition at the finest layer to be more flexible while moving close to the obstacles.

Since the idea of working with a multi-layered grid is to explore states from a coarser level before exploring states from a finer one, control up has the highest priority. We also prefer a transition with a longer duration to a transition with a shorter one. That is why it is reasonable to define a partial order on U µ × {1, . . . , n p } as follows: (u µ , j 1 ) < (u µ , j 2 ) if and only if j 1 < j 2 for all j 1 , j 2 ∈ {1, . . . , n p }, u µ , u µ ∈ U µ . As illustration in the Fig. 1(right) a control (u 2 , 2) is more prioritized than a control (u 1 , 1). Splitting a set U A into n p + 1 equivalence classes with respect to the introduced partial order and defining a safe set Q A,s = ∪ L l=1 Q l,s and an initial set Q A,init = Q L,init we can use now the Algorithm 1 to find a maximal lazy safety controller. Let us underline here that Algorithm 1 does not require that the transition relation F A is precomputed and we calculate transitions on the fly and only for reachable states.

From a Multilayered to an Adaptive Grid

Though the introduction of an artificial input up allows us to manipulate a multi-layered grid and transition duration using one general framework, the abstraction considered in the previous section has two significant disadvantages. First, when we run Algorithm 1, we have to store a multilayered grid Q A , while it is better to work with an adaptive grid, consisting of cells with different sizes. Second, for every fixed distribution of priorities of states p: Q A → {0, . . . , n p + 1} a reduced transition relation F A,p (see section 2.2 for the definition) includes a lot of auxiliary transitions which serves only for switching from a finer layer to a coarser one, while we prefer to keep in memory only those transitions which are directly related to the dynamic of the original system. For a given p let us choose as an adaptive grid

Q * ,p = Q p up (Q L ), where Q p up : Q L → Q A is defined as follows Q p up (q) = {q ∈ Q A | F A,p (q , up) = ∅ and ∃{q i } N i=0 , q i ∈ Q A , i = 0, N s. t. q 0 = q, q = q N , q j+1 = F A,p (q j , up), j = 0, N -1} and its extension for all Q ⊆ Q L is Q p up (Q) = ∪ q∈Q Q p up (q). So, a state of multilayered grid Q A is included in Q * ,p if
and only if it is reachable from the finest layer only with up transitions and there is no possibility to go higher for this state. Let us remark that for any q i , q j ∈ Q * ,p , q i = q j the following q i ∩ q j = ∅ is satisfied, moreover X = ∪ q∈Q * ,p q.

For the associated transition relation let us introduce

F * ,p ⊆ Q * ,p × U A × Q * ,p such that (q, u, q ) ∈ F * ,p if and only if q ∈ Q p up (F A,p (q, u)). Its definition is correct because for any q ∈ Q * ,p , u ∈ U A the set F A,p (q, u) either empty, or included in Q L .
The following propositions show why we can operate with a grid Q * ,p and a transition relation F * ,p , instead of Q A and F A,p , respectively. Proposition 12. For any q ∈ Q A , q ∈ R * , where So, we can reinitialize the priority of states p (line 11), using only knowledge about Q * ,p and F * ,p . Now we explain how to update the adaptive grid Q * ,p and a transition relation F * ,p , while changing p during the evolution of Algorithm 1.

R * = Reach F * ,p (Q p up ({q ∈ Q A,init | p(q) = 0})) if and only if q ∈ R, where R = Reach F A,p ({q ∈ Q A,init | p(q) = 0}) and F A,p (q, up) = ∅. Reach(τ u,2 q | q, u) Reach(τ u,2 q | q, u) q q u u
After execution of lines 2-6, a state in Q A is reachable from the finest layer if and only if it is safe or belonging to Q L . Hence, if we start from the coarsest layer Q 1 and recursively split all unsafe states into 2 n pieces while it is possible (i.e. while they do not belong to the finest layer Q L ) we finally get a grid Q * ,p , corresponding to the distribution of priority of states p just before the loop 8-12 execution. Since with every iteration of the loop only states included in Q * ,p change their priorities (see Proposition 13), we can also update our adaptive grid Q * ,p without direct usage of the transition relation F A,p . Indeed, if a state q ∈ Q A \ Q L gets a priority 0, then, from Lemma 11 and definition of up transition, it follows that we should replace it by 2 n states q i ∈ Q l(q)+1 , such that q = ∪ 2 n i=1 q i . There also exists a way to compute the transition relation F * ,p , using only current version of Q * ,p . Proposition 14. For any q ∈ Q * ,p , u ∈ U A \ {up} a state q ∈ Q * ,p belongs to a set F * ,p (q, u) if and only if q ∩ Reach(τ uµ,j q | q, u µ ) = ∅, and the condition of a collision avoidance

Reach(t | q, u µ ) ∩ (X \ Y ) = ∅ is satisfied for all t ∈ [0, τ uµ,j q ].
We illustrate the difference between a multilayered grid and an adaptive grid in Fig. 2. There, unsafe states are marked with black boxes, and successors filled with blue color.

Finally, we show that we can fully simulate the main part of Algorithm 1, using only adaptive grid Q * ,p and a transition relation F * ,p . It also important to mention that the abstraction is not required to be pre-computed, but constructed on the fly. Let us write, C * (q) := Enab F * ,p (q) for all q ∈ R * and empty otherwise, for a controller initialization part (lines 13-17). It is obvious, that C * (q) is a safety controller for a transition system Σ * = (Q * , U A , F * ), where a state space Q * and a transition relation F * are correspondingly Q * ,p and F * ,p after we exit the loop. Moreover, since for any p: Q A → {0, . . . , n p + 1}, any q ∈ Q * ,p the set F * ,p (q, up) = ∅, the input up never appears in a final safety controller C * . So, we can just skip it from the earlier beginning by initializing in line 4 every safe state with priority N -1, instead of N .

Refinement of the controller

In the previous section, we computed a safety controller C * (q) for a transition system Σ * = (Q * , U µ × {1, . . . , n p }, F * ), which is an abstraction for the original plant. Let us now provide a safety controller for the system Σ = (T, R n , U, W, f ).

First of all we introduce a controller C dur * : Q * → U µ × T, such that for every q ∈ Q * \ Dom(C * ) we say C dur * (q) = ∅, while if q ∈ Dom(C * ) and (u µ , j) ∈ Enab F * (q), then the pair (u µ , τ uµ,j q

) ∈ C dur * (q). Hence, a controller C dur * store real durations of safe transitions, instead of the sizes of the boxes.

We then explain with the following proposition how to refine the controller C dur * to a safety controller u for the original continuous system. Proposition 15. There exists a unique trajectory of the closed

-loop system                  ẋ(t) = f (x(t), u(t), w(t)), t ∈ T u = 0, t ∈ [t k , t k+1 ) t k+1 = t k + τ (u(x(t k ), t k ), τ ) = C dur * (q), where q ∈ Q * s.t. x(t k ) ∈ q t 0 = 0 x(t 0 ) = x 0 , x 0 ∈ X 0 ∩ Dom(C dur
* ) and it remains inside the safe set Y , no matter which disturbance w(•) ∈ L(T, W ) has been applied.

The statement of the proposition directly follows from the discussion above. We only remark here, that the computation of the controller for the abstraction is usually implemented off-line and then stored in a control device memory, while a controller for the continuous system is calculated online using this pre-computed information.

NUMERICAL ILLUSTRATION

In this section, we consider a problem of temperature regulation in a two-room building. Each room is equipped with a heater and T i is the temperature in the room i, i = 1, 2. The evolution of the temperatures is described by the following system of the differential equations

Ṫ1 = α(T 2 -T 1 ) + β 1 (t e -T 1 ) + γ 1 (t h1 -T 1 )u 1 Ṫ2 = α(T 1 -T 2 ) + β 2 (t e -T 2 ) + γ 2 (t h2 -T 2 )u 2
Here t e is the temperature of the external environment of the building, t h1 , t h2 are temperatures of the heaters, α is the conduction factor between rooms, β 1 , β 2 are conduction factors between external environment and the first room and the second room respectively, γ 1 , γ 2 are conduction factor between heater and rooms. Control parameter u i equals 1 if the room i is heated and 0 otherwise. Temperature t e is considered as a bounded disturbance. In Fig. 3, the results of the simulation are provided. We use a dark grey and a light grey for states, which are controllable with a (u µ , 1), u µ ∈ U µ and with a (u µ , 2), u µ ∈ U µ correspondingly, while white region is uncontrollable. The closed loop trajectory is simulated for 24 hours, supposing that external temperature varies between -10C • and 10C • and initial point x 0 = [19.084; 19.27]. The orange color correspond to a control {0, 0}, green to a control {0, 1}, violet to a control {1, 0}.

To evaluate efficiency, we also run a simulation for two extreme cases: L = 1, n x = [4; 4] and L = 1, n x = [25; 25], which correspond to a coarsest grid and to a finest grid of considered four-layered adaptive grid. One can see the comparison of the results in Tab.1. The controllable sets coincides for the adaptive grid and the finest grid, but we get a noticeable time and memory gain. The implementations has been done in C++, processor Intel Core i7-8700, 2.5 Hg, RAM 16 GB.

CONCLUSION

In this paper, we introduced a new method of construction of symbolic models for a continuous dynamic system, based on the adaptive sampling of time and multilayered state-space discretization. Then, we proposed an efficient way of computing a safety controller for the nondeterministic transition system. The lazy algorithm is based on the forward exploration of the state space, while the term lazy refers to the fact, that if we can guarantee safety using a higher priority input, we do not explore inputs with smaller priorities at all. Future work will focus on extending the approach to other types of specification such as reachability or more general properties specified by automata or temporal logical formula.

  ) := ∅; 18 return C; reachable (regarding the current version of F p ) from initial set (lines 7, 12) are explored. Because of space limitations, the following result is stated without proof: Theorem 10. Let C computed by Algorithm 1. Then, C is the MLS controller.

Fig. 1 .

 1 Fig. 1. Transitions on a 2-layered grid. Left figure illustrates (1), (2). Right figure illustrates (3).

Fig. 2 .

 2 Fig. 2. Left: 2-layered grid. Right: adaptive grid Proposition 13. Let us run Algorithm 1 for the transition systemΣ A = (Q A , U A , F A ). The following Block F A,p (R) = Block F * ,p (R *) is satisfied at every iteration of loop 8-12.

Fig. 3 .

 3 Fig. 3. Temperature regulation in two rooms building. We run our simulation for the following set of parameters α = 1/2 * 10 -4 W/J, β 1 = 1/6 * 10 -4 W/J, β 2 = 1/11 * 10 -4 W/J, γ 1 = 1.5 * 10 -4 W/J, γ 2 = 1.5 * 10 -4 W/J, t h1 = 30 C • , t h1 = 40 C • . A safety specification is given by an initial set X 0 = [19, 23] × [19, 23], safe set Y = [19, 23] × [19, 23], and a disturbance t e ∈ [-10, 10]. We also suppose that at given instant at most one heater is switched on, i.e. a control set U = {{0, 0}, {0, 1}, {1, 0}}. For the abstraction, we chose L = 4, n x = [4; 4], U µ = U , and n p = 2.

Table 1 .

 1 Numerical results

	Grid	Number of states	Time	Cont. Ratio
	Adaptive grid	18	7 s	98%
	Coarsest grid	9	5 s	89%
	Finest grid	625	50 s	98%

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 725144).

APPENDIX

Proof of Theorem 10

The proof requires first to establish the following lemmas regarding properties of Algorithm 1: Lemma 16. With every iteration of the loop 8-12, the priority of a state either decreases by one point, or remains unchanged. If some state obtained priority 0, it keeps this value until the end of Algorithm 1 execution.

Proof. The first part of the statement is obvious. The second follows from the facts that B ⊆ R and any state with priority 0 is non-reachable. 2 Lemma 17. We decrease the priority p of a state q, if either Enab F (q) ∩ U p(q) = ∅, or for all u ∈ Enab F (q) ∩ U p(q) there exists q ∈ F (q, u) such that p(q ) = 0.

Proof. It follows immediately from the definition of F p and the definition of a blocking state. 2 Lemma 18.

Proof. Let us use induction to prove this fact. First, before the loop 8-12 the set Q zero consists only of unsafe (see line 6), and, as a consequence, uncontrollable states.

Second, in the loop Q zero updates only when some state q ∈ B ⊆ Q gets at line 11 a priority zero (see Lemma 16). Supposing that

So, let us show, that q ∈ Cont(Σ, Q s ). Since p(q) got value 0 using Lemma 17 we have that for all j = 1, . . . , N either Enab F (q) ∩ U j = ∅, or for all u ∈ Enab F (q) ∩ U j there exists q ∈ F (q, u) \ {q} such that p(q ) = 0, i.e q ∈ Q i zero and q / ∈ Cont(Σ, Q s ). Hence, C(q) is empty and q is uncontrollable. 2

We can now provide the proof of Theorem 10.

Using the definition of F p , Lemma 16, and the finiteness of Q, we immediately get, that the loop 8-12 can not be infinite. Also, we have that Enab Fp (q) ⊆ Enab F (q) for any q ∈ Q, so, the Algorithm 1 returns a controller. Let us show that it is a maximal lazy one.

We start with safety. Since, exit condition for loop 8-12 is Block Fp (R) = ∅ then for all q ∈ R it holds, that Enab Fp (q) = ∅. Hence, Dom(C) coincides with R. Since, unsafe states are non-reachable Dom(C) ⊆ Q s and the first condition from the definition of safety controller holds. Moreover, from the definition of Reach operator we have that for all q ∈ Dom(C) and for all u ∈ U it holds F p (q, u) ⊆ Dom(C). Combining with the fact that for all q ∈ Dom(C) and for all u ∈ Enab Fp (q) the set F p (q, u) coincides with F (q, u), the second requirement is satisfied. Now, let us show that all properties of MLS controller are satisfied (see Definition 8). Let q ∈ Cont(Σ, Q s ) ∩ Q init . It is equivalent to q ∈ Q init and q ∈ Cont(Σ, Q s ). From where, using the Lemma 18, we get that q ∈ Q init and p(q) = 0. Consequently, q ∈ R = Dom(C) (see line 7,12), and the first property is satisfied. Second property is straightforward from the line 12. For any q ∈ Dom(C) a control u ∈ C(q) if and only if u ∈ Enab Fp (q). Then for any u ∈ Enab F (q) ∩ U p(q) we have: if u ∈ Enab Fp (q) then F (q, u ) = F p (q, u ) ⊆ Dom(C) ⊆ Cont(Σ, Q s ), because C is a safety controller; if F (q, u ) ⊆ Cont(Σ, Q s ) then there is no q ∈ F (q, u ) such that p(q ) = 0 and u ∈ Enab Fp (q). So, we have (3a). The (3b) follows from the Lemma 17. 2

Proof of Proposition 12

Remembering that any non-up transition always finishes at the lowest layer, while input up strictly prioritized that all the others, we have from the definition of Reach F A,p , that q ∈ R, F A,p (q, up) = ∅ is equivalent to the existence of a trajectory

q m,nm = q such that q 0,0 ∈ {q ∈ Q A,init | p(q) = 0}, q i,0 ∈ Q L for all i = 0, . . . , m and q j,nj ∈ Q * ,p for all j = 0, . . . , m. This is true (see the the definition of Q p up (q)) if and only if there exist a trajectory

) and q j,nj ∈ Q * ,p for all j = 0, . . . , m. The last is equivalent to the fact q ∈ R * . 2

Proof of Proposition 13

So, q ∈ Block F A,p (R) if and only if q ∈ R and F A,p (q, u) = ∅ for any u ∈ U A , which is equivalent to q ∈ R * and Q p up (F A,p (q, u)) = ∅ for any u ∈ U A . The last is true if and only if q ∈ Block F * ,p (R * ). 2

Proof of Proposition 14

Let q ∈ F * ,p (q, u). From the definition of F * ,p , this is true if and only if q ∈ Q p up (F A,p (q, u)). From the definition of Q p up last is equivalent to existence q ∈ Q L such that q ∈ Q p up (q ) and q ∈ F A,p (q, u). This is satisfied if and only if there exists q ∈ Q L such that q ∈ Q p up (q ), q ∩ Reach(τ uµ,j q | q, u µ ) = ∅ and the condition of a collision avoidance Reach(t | q, u µ ) ∩ (X \ Y ) = ∅ is not violated for all t ∈ [0, τ uµ,j q

]. From Lemma 11 and definition of up transition the last is equivalent to q ∈ Q * ,p , q ∩ Reach(τ uµ,j q | q, u µ ) = ∅, and the condition of a collision avoidance Reach(t | q, u µ ) ∩ (X \ Y ) = ∅ is satisfied for all t ∈ [0, τ uµ,j q

]. That ends the proof. 2