Zoljargal Baatarkhuu

Philippe Chaignon

Franck Borel

Jean-Luc Ferrer

Alain Wagner

Myriam Seemann
email: mseemann@unistra.fr

Synthesis and Kinetic evaluation of an azido analogue of methylerythritol phosphate: a Novel Inhibitor of E. coli YgbP/IspD

As multidrug resistant pathogenic microorganisms are a serious health menace, it is crucial to continuously develop novel medicines in order to overcome the emerging resistance. The methylerythritol phosphate pathway (MEP) is an ideal target for antimicrobial development as it is absent in humans but present in most bacteria and in the parasite Plasmodium falciparum. Here, we report the synthesis and the steady-state kinetics of a novel potent inhibitor (MEPN 3 ) of Escherichia coli YgbP/IspD, the third enzyme of the MEP pathway. MEPN 3 inhibits E. coli YgbP/IspD in mixed type mode regarding both substrates. Interestingly, MEPN 3 shows the highest inhibitory activity when compared to known inhibitors of E. coli YgbP/IspD. The mechanism of this enzyme was also studied by steadystate kinetic analysis and it was found that the substrates add to the enzyme in sequential manner.

Drug resistance is an ever-growing concern that poses a major challenge for new drug development. In the field of antibiotic discovery, the situation is alarming as some infections are already impossible to treat due to resistance. Enterobacteriaceae, in particular Klebsiella pneumonaiae and Escherichia coli, are highly pervasive in community-acquired and nosocomial infections. The worldwide emergence of carbapenemase-producing Enterobacteriaceae represents a serious public health threat as carbapenems are often the last option for treatment of patients infected by these bacteria [START_REF] Grundmann | Occurrence of carbapenemase-producing Klebsiella pneumoniae and Escherichia coli in the European survey of carbapenemase-producing Enterobacteriaceae (EuSCAPE): a prospective, multinational study[END_REF] . WHO already estimated in 2014 that 44% of its member states reported E. coli strains resistant to third-generation cephalosporins and fluoroquinolones and highlighted the high resistance rates of E. coli strains to the last-generation drugs [START_REF]ANTIMICROBIAL RESISTANCE Global Report on Surveillance[END_REF] . In September 2017, WHO classified carbapenem-resistant and third-generation cephalosporin resistant Enterobacteriaceae among the most critical priority for Research and Development of new antibiotics as strains that cannot be fought by any antibiotic on the market are emerging worldwide [START_REF]Prioritization of pathogens to guide discovery, research and development of new antibiotics for drug resistant bacterial infections, including tuberculosis[END_REF] . Given the severe threat from organisms resistant to conventional antibacterial agents, targeting the MEP pathway responsible for the biosynthesis of the universal isoprenoid precursors in most bacteria and in the parasite responsible for malaria was proposed as an attractive strategy in the search for new antimicrobial agents [START_REF] Rohmer | Isoprenoid biosynthesis as a novel target for antibacterial and antiparasitic drugs[END_REF][START_REF] Gräwert | Biochemistry of the non-mevalonate isoprenoid pathway[END_REF][START_REF] Zhao | Methylerythritol Phosphate Pathway of Isoprenoid Biosynthesis[END_REF][START_REF] Masini | Development of Inhibitors of the 2C-Methyl-D-erythritol 4-Phosphate (MEP) Pathway Enzymes as Potential Anti-Infective Agents[END_REF] .

Isoprenoids are the most diverse family of natural products that comprises over 55000 known compounds. They are found in all living organisms and are involved in numerous essential biological processes such as electron transport, cell-wall biosynthesis, and protein prenylation [START_REF] Rohmer | The discovery of a mevalonate-independent pathway for isoprenoid biosynthesis in bacteria, algae and higher plants[END_REF][START_REF] Heuston | Isoprenoid biosynthesis in bacterial pathogens[END_REF] . Isoprenoids are synthesised through multiple condensation of two main building blocks: dimethylallyl diphosphate (DMADP, 1) and isopentenyl diphosphate (IDP, 2, Fig. 1) [START_REF] Rohmer | The discovery of a mevalonate-independent pathway for isoprenoid biosynthesis in bacteria, algae and higher plants[END_REF] . The MEP pathway, absent in humans, is an alternative to the well-known mevalonate pathway existing in animals [START_REF] Bloch | Sterol Molecule -Structure, Biosynthesis, and Function[END_REF] for the formation of IDP and DMADP. The MEP pathway (Fig. 1) starts with condensation of pyruvate (3) and glyceraldehyde 3-phosphate (4) to form 1-deoxy-D-xylulose 5-phosphate (5), which is further converted to 2-C-methyl-D-erythritol 4-phosphate (MEP, 6). MEP reacts with cytidine triphosphate (CTP) to generate 4-diphosphocytidyl-2-C-methyl-D-erythritol (CDP-ME, 7), which is further phosphorylated to yield 4-diphosphocytidyl-2-C-methyl-D-erythritol 2-phosphate (CDP-MEP, 8). After cyclisation and cytidine monophosphate (CMP) release, 2-C-methyl-D-erythritol 2,4-cyclodiphosphate (ME-cPP, 9) forms. ME-cPP then generates (E)-4-hydroxy-3-methylbut-2-en-1-yl diphosphate (HMBDP, 10) that further produces DMADP and IDP.

To date only one compound targeting the MEP pathway, namely fosmidomycin, an inhibitor of the second enzyme 1-deoxyxylulose 5-phosphate reductoisomerase (DXR), is under clinical trial as an antimalarial agent in combination with clindamycin and piperaquine [START_REF]Evaluation of Fosmidomycin and Piperaquine in the Treatment of Acute Falciparum Malaria[END_REF] , highlighting the potential of the MEP pathway for drug development [START_REF] Wells | Malaria medicines: a glass half full?[END_REF] . Exploring new inhibitors of the MEP pathway could be a source of new therapeutic agents that are urgently needed to fight life-threatening infections. Here we report the synthesis and inhibition studies of MEPN 3 , (11, Fig. 2a) as a potential inhibitor of E. coli YgbP (also called IspD), the third enzyme of the MEP pathway.

Results and Discussion

E. coli YgbP/IspD. E. coli YgbP/IspD (EC 2.7.7.60) is encoded by the ygbP gene and catalyses the transformation of MEP and CTP into 4-diphosphocytidyl-2-C-methyl-D-erythritol (CDP-ME; 7) and inorganic diphosphate (PPi) (Fig. 1) in the presence of a divalent cation such as Mn 2+ , Mg 2+ or Co 2+13 . YgbP was checked for activity using a similar method as described previously and based on the transformation of inorganic diphosphate to phosphate by inorganic pyrophosphatase followed by the quantification of the resulting phosphate by complexation with malachite green ammonium molybdate [START_REF] Bernal | A colorimetric assay for the determination of 4-diphosphocytidyl-2-C-methyl-D-erythritol 4-phosphate synthase activity[END_REF] . This method is robust, simple, fast, reliable and inexpensive for checking the activity of YgbP. The activity of YgbP limiting the concentration of CTP to 200 µM (as substrate inhibition was reported at high concentrations [START_REF] Richard | Kinetic Analysis of Escherichia coli 2-C-Methyl-D-erythritol-4-phosphate Cytidyltransferase, Wild Type and Mutants, Reveals Roles of Active Site Amino Acids[END_REF] ) was 3.47 µmol.min -1 .mg -1 and is in the same range as published [START_REF] Bernal | A colorimetric assay for the determination of 4-diphosphocytidyl-2-C-methyl-D-erythritol 4-phosphate synthase activity[END_REF] . The kinetic parameters of YgbP/IspD were determined using either varied MEP concentrations and a fixed CTP concentration (200 µM) or varied CTP concentrations and a fixed MEP concentration (250 µM). The reaction rates could be fitted according to the Michaelis-Menten equation and apparent K m values of 40 ± 7 µM for MEP (k cat = 1.77 s -1 ) and 84 ± 9 µM for CTP (k cat = 6.87 s -1 ) were estimated, which are in agreement with the reported values using the same method for the quantification of the activity [START_REF] Bernal | A colorimetric assay for the determination of 4-diphosphocytidyl-2-C-methyl-D-erythritol 4-phosphate synthase activity[END_REF] . A similar K m for MEP (32 ± 3 µM) was reported by Cane et al. [START_REF] Cane | Molecular cloning, expression and characterization of the first three genes in the mevalonate-independent isoprenoid pathway in Streptomyces coelicolor[END_REF] using a radiolabeled assay. Rohdich et al. [START_REF] Rohdich | Cytidine 5′-triphosphate-dependent biosynthesis of isoprenoids: YgbP protein of Escherichia coli catalyzes the formation of 4-diphosphocytidyl-2-C-methylerythritol[END_REF] published a smaller K m for MEP (3.14 µM) but a similar K m for CTP (131 µM) when the detection of inorganic diphosphate was achieved indirectly after its consumption through a cascade of reactions leading to the reduction of NADP + . Richard et al. [START_REF] Richard | Kinetic Analysis of Escherichia coli 2-C-Methyl-D-erythritol-4-phosphate Cytidyltransferase, Wild Type and Mutants, Reveals Roles of Active Site Amino Acids[END_REF] reported 370 ± 60 µM (10-fold higher than our result) K m value for MEP but used different conditions with high CTP concentrations (above 7 mM).

Our aim was to design an E. coli YgbP/IspD inhibitor that would be suitable for fragment-based drug discovery approaches. We searched a position for the insertion of an azide functionality while introducing minimal structural perturbation on the MEP substrate and keeping chemical stability. Therefore, we tested MEPN 3 (11, Fig. 2), a MEP analogue harbouring an azido on the methyl group.

Synthesis of MEPN 3 . The route to MEPN 3, (11) is outlined in Fig. 2 and starts with ketone 12 which was previously described by Coates and coworkers [START_REF] Lagisetti | The Dioxanone Approach to (2S,3R)-2-C-Methylerythritol 4-Phosphate and 2,4-Cyclodiphosphate, and Various MEP Analogues[END_REF] . Submitted to a Corey-Chaykovsky reaction, ketone 12 was diastereoselectively converted to epoxide 13 [START_REF] Corey | Dimethyloxosulfonium Methylide ((CH 3 ) 2 SOCH 2 ) and Dimethylsulfonium Methylide ((CH 3 ) 2 SCH 2 ). Formation and Application to Organic Synthesis[END_REF][START_REF] Mazitschek | Synthesis and biological evaluation of novel fumagillin and ovalicin analogues[END_REF] ; this represents a valuable improvement compared to Coates' synthesis of 13, which featured a two-step "olefin formation-epoxidation" procedure that led to a diastereomeric mixture [START_REF] Lagisetti | The Dioxanone Approach to (2S,3R)-2-C-Methylerythritol 4-Phosphate and 2,4-Cyclodiphosphate, and Various MEP Analogues[END_REF] . Epoxide 13 was further transformed into azido alcohol 14 with sodium azide, followed by deprotection of the primary alcohol with tetra-n-butylammonium fluoride. The resulting azido diol 15 was phosphorylated with dimethyl chlorophosphate to yield compound 16. Hydrolysis of benzylidene acetal with an acidic resin followed by deprotection of the phosphate group using a McKenna reaction [START_REF] Błażewska | Reaction-Which Oxygen Attacks Bromotrimethylsilane?[END_REF] afforded MEPN 3 (11).

MEPN 3 is a poor substrate of YgbP/IspD. As MEPN 3 (11) structurally resembles MEP, YgbP was further assayed using MEPN 3 as a substrate. Poulter et al. [START_REF] Krasutsky | Synthesis of Methylerythritol Phosphate Analogues and Their Evaluation as Alternate Substrates for IspDF and IspE from Agrobacterium tumefaciens[END_REF] have previously reported that 2-C-ethyl-D-erythritol phosphate was a substrate for Agrobacterium tumefaciens YgpP/IspD showing replacement of the methyl at C-2 of MEP by an alternative substituent could still allow catalysis. Initial studies showed that MEPN 3 was a substrate of YgbP but the enzymatic reaction velocity declined at higher MEPN 3 concentrations (>500 µM), revealing substrate inhibition (Fig. S1). From the obtained data, the activity of YgbP (at 300 µM of MEPN 3 ) was 100-fold less than the activity of YgbP with MEP (at 250 µM) showing that MEPN 3 is a poor substrate.

The previous assay was based on the detection of the released diphosphate but not on the detection of CDP-MEN 3 (18) (Fig. 3a) that should be produced if MEPN 3 behaved like MEP in the active site of YgbP. In this context, strain-promoted alkyne-azide cycloaddition (SPAAC) using BCN ((1R,8S,9S)-bicyclo[6.1.0]non-4-yn-9-yl)methanol) derivative 23 encompassing a TMPP (tris(2,4,6-trimethoxyphenyl phosphonium, 21, Fig. 2) tag was employed to detect CDP-MEN 3 (18) in the YgbP assay with MEPN 3 as substrate. TMPP had been previously applied as a charge derivatisation agent for small biological molecules to enhance their detectability using positive ion ESI-MS analysis, as it carries a permanent positive charge [START_REF] Cartwright | Detection of phosphorus tagged carboxylic acids using HPLC-SF-ICP-MS[END_REF][START_REF] Woo | Phosphonium labeling for increasing metabolomic coverage of neutral lipids using electrospray ionization mass spectrometry[END_REF][START_REF] Huang | A Picomole-Scale Method for Charge Derivatization of Peptides for Sequence Analysis by Mass Spectrometry[END_REF] . BCN-TMPP (23) was prepared as described in Fig. 2. BCN was activated with p-nitrochloroformate to generate molecule 19 [START_REF] Ursuegui | An in vivo strategy to counteract post-administration anticoagulant activity of azido-Warfarin[END_REF] which was further converted into compound 20 using ethylenediamine [START_REF] D' Alessandro | Bioorthogonal Probes for the Study of MDM2-p53 Inhibitors in Cells and Development of High-Content Screening Assays for Drug Discovery[END_REF] . In parallel, TMPP and bromoacetic acid N-hydroxysuccinimide ester were used to produce TMPP derivative 22. Reaction of BCN derivative 20 with the activated TMPP (22) afforded the target molecule 23 in good yield. In a preliminary experiment, BCN-TMPP was incubated with MEPN 3 and after LC-MS analysis (C 18 column, UV detection for LC, positive mode detection for MS) the major product was detected at m/z 534 Da (calculated mass = 1067 Da) consisting of BCN-TMPP-MEPN 3 (24) (Fig. 3b) carrying a second positive charge in addition to TMPP's permanent charge (Fig. 3c). In order to identify the product of YgbP using MEPN 3 as substrate, the completed enzymatic reaction was incubated with BCN-TMPP, and after LC-MS analysis, a product displaying m/z 686 Da corresponding to 25 (calculated mass = 1372 Da) harboring two charges was detected confirming that MEPN 3 was turned over by YgbP to CDP-MEN 3 (Fig. 3d). The fact that MEPN 3 was a poor substrate compared to MEP was surprising as the only difference between both molecules was the azide function. To better understand the slow turnover of MEPN 3 by YgbP, we further evaluated the inhibition potential of 11 on YgbP.

Inhibition of E. coli YgbP/IspD by MEPN 3 .

Preliminary experiments revealed the YgbP reaction rate using its natural substrates (MEP and CTP) was decreasing when MEPN 3 was present. In order to further determine the inhibition parameters and the inhibition mode of MEPN 3 , steady-state inhibition kinetic studies were performed (Fig. 4,a,d). The data were fitted according to the double reciprocal analysis (Fig. 4b,e) and highlighted that MEPN 3 inhibited YgbP in a mixed type inhibition mode with respect to both substrates. From the replots (Fig. 4c,f), we have found K i = 21 ± 3 µM and αK i = 54 ± 4 µM (α = 2.5) when MEP was the varied substrate while K i = 47 ± 6 µM and αK i = 105 ± 24 µM (α = 2.2) when CTP was the varied substrate. As αK i value was higher than K i value in both cases, it suggests that MEPN 3 has a higher affinity for the free enzyme than for the enzyme-substrate complex.

Although there are number of reports describing potent inhibitors of YgbP from malaria parasites [START_REF] Imlay | Plasmodium IspD (2-C-Methyl-D-erythritol 4-Phosphate Cytidyltransferase), an Essential and Druggable Antimalarial Target[END_REF][START_REF] Price | Molecular Mechanism of Action of Antimalarial Benzoisothiazolones: Species-Selective Inhibitors of the Plasmodium spp. MEP Pathway enzyme[END_REF] and Mycobacteria [START_REF] Gao | Identification and validation of a novel lead compound targeting 4-diphosphocytidyl-2-C-methylerythritol synthetase (IspD) of mycobacteria[END_REF][START_REF] Varikoti | Structure based de novo design of IspD inhibitors as anti-tubercular agents[END_REF] as well as from the plant Arabidopsis thaliana [START_REF] Witschel | Inhibitors of the Herbicidal Target IspD: Allosteric Site Binding[END_REF][START_REF] Kunfermann | Pseudilins: Halogenated, Allosteric Inhibitors of the Non-Mevalonate Pathway Enzyme IspD[END_REF][START_REF] Witschel | In search of new herbicidal inhibitors of the non-mevalonate pathway[END_REF] , there are hardly any inhibitors reported for E. coli YgbP (Fig. 5) and they all display very high IC 50 reflecting their poor inhibition potential. The first inhibitor described for E. coli YgbP was D-erythrol-4-phosphate (26) with IC 50 value of 1.36 mM which was also a substrate and reduced the turnover rate compared to natural substrate MEP 34 . Two years later, L-erythrol-4-phosphate (27) was reported to be a weak competitive inhibitor of MEP in E. coli YgbP, displaying a K i value of 240 mM [START_REF] Lillo | Functional expression and characterization of EryA, the erythritol kinase of Brucella abortus, and enzymatic synthesis of L-erythritol-4-phosphate[END_REF] . Interestingly fosmidomycin (28), the only inhibitor of MEP pathway currently in clinical trial and targeting DXR, was also reported to be an inhibitor of YgbP. Odom and co-workers reported an increase of MEP level and decrease of CDP-ME level when Plasmodium falciparum was treated with fosmidomycin and further showed that 28 inhibited E. coli YgbP activity with an IC 50 value of 20.4 mM [START_REF] Zhang | A Second Target of the Antimalarial and Antibacterial Agent Fosmidomycin Revealed by Cellular Metabolic Profiling[END_REF] . Interestingly, in the course of this work, Freel Meyers and co-workers 37 described (5S)-D-methylerythritol monofluoromethyl phosphonate (29) as a new inhibitor of E. coli YgbP displaying an IC 50 value of 0.7 mM. Even though no detailed kinetics were reported, these results encouraged us in our approach. MEPN 3 is a mixed type inhibitor of E. coli YgbP regarding both substrates with K i values in the micromolar range (21 µM and 47 µM). IC 50 for MEPN 3 was estimated to be around 41.5 µM (see Fig. S4), making MEPN 3 the best inhibitor of E. coli YgbP known to date.

As MEPN 3 is a substrate analogue of MEP, we expected the inhibition to be competitive with MEP and uncompetitive with CTP. In order to further understand the mixed type inhibition observed for MEPN 3 on YgbP regarding both substrates, set of docking studies were performed to investigate the binding mode of 11.

Docking experiments of MEPN

3 with E. coli YgbP. Three different X-ray structures of E. coli YgbP have been reported [START_REF] Richard | Structure of 4-diphosphocytidyl-2-C-methylerythritol synthetase involved in mevalonate-independent isoprenoid biosynthesis[END_REF] : the apo form of the protein (1INJ) and its complexes with CTP (1I52) or CDP-ME (1INI). However, no structure of E. coli YgbP in complex with MEP has been obtained to date. To identify the mode of binding of 11, we attempted to solve the crystal structure of E. coli YgbP in complex with 11 but we were unsuccessful. The lack of crystal structure of YgbP in complex with MEP or with its structural analogue MEPN 3 may be due to an ordered sequential mechanism, in which CTP binds first to the enzyme followed by MEP, as proposed by Cane and co-workers [START_REF] Richard | Kinetic Analysis of Escherichia coli 2-C-Methyl-D-erythritol-4-phosphate Cytidyltransferase, Wild Type and Mutants, Reveals Roles of Active Site Amino Acids[END_REF] . To further investigate the binding mode of MEPN 3 , docking experiments were performed using the E. coli YgbP homodimeric CTP form (1I52). Indeed, this form appears to be the most suitable since it has the highest resolution and is the only one that displays a well-defined P-loop (residues 17-25) [START_REF] Richard | Structure of 4-diphosphocytidyl-2-C-methylerythritol synthetase involved in mevalonate-independent isoprenoid biosynthesis[END_REF] . Two sets of docking were done: the first one using a protein target containing a bound CTP and a second one using an empty protein target. To avoid bias linked to the use of a too small docking area, we defined, for both cases, a search area covering the entire YgbP CTP/CDP-ME binding site. To validate our docking procedure, CTP for which the crystallographic structure in complex with YgbP is available, was submitted to our docking protocol. The docked CTP superimposed very well onto the CTP observed in the crystal structure. The closest docking pose displays a docking score of -11.27 and a RMSD value of 0.11 Å (Fig. 6).

When using a target already containing CTP, we were able to identify two binding sites for MEP and MEPN 3 (Fig. 6): one deeply buried at the bottom of the CDP-ME pocket with docking scores of -7.86 and -7.96 for MEPN 3 and MEP respectively, and a second site located closest to the surface of the protein which appears to be more favorable for the binding of the two molecules given the slightly better docking scores obtained in that case (-9.28 and -8.64 for MEPN 3 and MEP respectively). When the empty protein (no CTP bound) was used as a target, we observed that MEPN 3 preferentially docked into the CTP binding pocket with a docking score for the best pose of -8.85.

The docking results confirmed that MEPN 3 can bind either to the CTP binding pocket or to the hypothetical MEP binding pocket explaining the mixed type inhibition of MEPN 3 for E. coli YgbP revealed by the kinetic data. These results show that the very high inhibition potential of MEPN 3 compared to the other E. coli YgbP described inhibitors is most probably due to the fact that MEPN 3 can bind to both substrate pockets. The design of such inhibitors has never been achieved previously. Interestingly, fosmidomycin (28), has also been reported to bind to the CTP binding site of E. coli YgbP according to docking experiments [START_REF] Zhang | A Second Target of the Antimalarial and Antibacterial Agent Fosmidomycin Revealed by Cellular Metabolic Profiling[END_REF] . The high potential of fosmidomycin as a drug compared to the other known DXR inhibitors might be linked to this additional binding property. The druggability of the CTP-binding pocket in the homologue protein of M. tuberculosis has actually been reported by Hirsch and co-workers [START_REF] Masini | Druggability of the enzymes of the non-mevalonate-pathway[END_REF] . In this context, the binding of MEPN 3 into the CTP-binding site should be considered as a starting point for new antibacterial development.

As MEPN 3 is an analogue of MEP, we further checked whether MEP could also bind to the CTP pocket of E. coli YgbP. Using the target without bound CTP, our experiments revealed that MEP also preferentially docks to this pocket with a docking score of -9.40 (Fig. S5). No other evidence suggesting the binding of MEP to the CTP-binding pocket has been reported but if this hypothesis based on docking were to be true, the multiple binding sites revealed here for MEP would be puzzling from the catalytic point of view. This has prompted us to further investigate the mechanism of E. coli YgbP using a more detailed kinetic analysis.

Investigation of E. coli YgbP mechanism by using a bi-substrate kinetic analysis. Cane and

co-workers [START_REF] Richard | Kinetic Analysis of Escherichia coli 2-C-Methyl-D-erythritol-4-phosphate Cytidyltransferase, Wild Type and Mutants, Reveals Roles of Active Site Amino Acids[END_REF] highlighted, using pulse-chase experiments, that the formation of CDP-ME was accomplished by an ordered sequential mechanism, in which CTP binds first to the enzyme followed by MEP binding. Nucleophilic attack on α-phosphate group of CTP by the phosphate moiety of MEP will then afford a pentacoordinate intermediate that will subsequently collapse to produce CDP-ME and diphosphate [START_REF] Richard | Kinetic Analysis of Escherichia coli 2-C-Methyl-D-erythritol-4-phosphate Cytidyltransferase, Wild Type and Mutants, Reveals Roles of Active Site Amino Acids[END_REF][START_REF] Richard | Structure of 4-diphosphocytidyl-2-C-methylerythritol synthetase involved in mevalonate-independent isoprenoid biosynthesis[END_REF] . However, the ordered sequential catalytic mechanism of YgbP has never been characterised using a complete bisubstrate kinetic analysis. Such a kinetic analysis was performed here by measuring the velocity of different assays in which one of the substrate concentration was varied at different but fixed concentrations of the second substrate. Double reciprocal plots of initial velocity for both substrates resulted in lines intersecting left to the vertical axis and above to the horizontal axis (Fig. 7a,c) confirming that YgbP mechanism is sequential where ternary complex forms before any product release [START_REF] Copeland | Evaluation of enzyme inhibitors in drug discovery. A guide for medicinal chemists and pharmacologists[END_REF][START_REF] Borra | Substrate specificity and kinetic mechanism of the Sir2 family of NAD(+)dependent histone/protein deacetylases[END_REF] .

After fitting the data to the rate equation for sequential bi-substrate mechanism (See supporting information for more details), the complete kinetic scheme for E. coli YgbP was obtained for the first time (Fig. 8). K m values of 149 μM (K iA ) for CTP and 46 μM (K iB ) for MEP were retrieved and were found to be in agreement with the K m values obtained using the classical Michaelis-Menten equations (K m = 84 μM for CTP and K m = 40 μM for MEP). The dissociation constant of YgbP-CTP complex for MEP (K B ) was revealed to be very low (20 μM) while the dissociation constant of YgbP-MEP complex for CTP (K A ) was thirteen times higher (265 μM). These values show that if CTP binds to the free enzyme first, the affinity of MEP for YgbP-CTP complex is increased (low dissociation constant) leading to the production of CDP-ME. If MEP binds to the free enzyme first, the affinity of CTP for YgbP-MEP complex will be very low (high dissociation constant) and the YgbP-MEP complex might not be productive and would dissociate to regenerate the free enzyme. This achievement is compatible with the hypothesis that MEP could bind to the CTP pocket and if this happens, the resulting complex would be expected to dissociate to allow the binding of CTP in the CTP pocket. Then, once MEP is present in the active site, the reaction would proceed.

Selectivity of MEPN 3 . Fosmydomycin is the only inhibitor of the MEP pathway currently under clinical trial. It targets DXR but also to a weaker extend YgbP. This double targeting of fosmidomycin for the MEP pathway is very interesting and may be at the origin of the high potential of fosmidomycin as an antibiotic compared to the other MEP pathway inhibitors. This unique property of fosmidomycin encouraged us to investigated whether MEPN 3 is selective for YgbP or if it targets another enzyme of the MEP pathway. In this context, DXR was investigated as a potential target for our inhibitor, as it lays just before YgbP in the MEP pathway and produces MEP. Docking experiments were carried out based on the structure of E. coli YgbP in complex with 1-deoxy-D-xylulose 5-phosphate (5) and NADPH (1Q0Q). Two sets of docking were performed: one with only NADPH bound and another with the empty target. Interestingly, we observed that MEPN 3 binds in the binding site of the substrate 5 with a docking score of -9.09 for the best pose (Fig. S6). These results need to be further confirmed using kinetic investigations on DXR but they already highlight that MEPN 3 is a good starting point in the search for new drugs as it might target several enzymes of the MEP pathway.

Conclusion

We have successfully synthesised MEPN 3 , the best inhibitor of E. coli YgbP/IspD known to date and the first inhibitor shown to bind to either or both substrate binding sites. This special binding feature appears to be at the origin of the potency of MEPN 3 . In addition, our in-depth kinetic studies of YgbP, using a bi-substrate model for the first time also highlighted that the binding of MEP to the free enzyme disfavored the formation of the product. Building on the knowledge gained from our study, new inhibitors derived from MEPN 3 might be further elaborated either by developing new analogs bearing this dual binding profile or via structure-based fragment selection and in situ chemistry since MEPN 3 is already a good starting point for such strategy. With this aim, fragments could be among other MEP analogues or other molecules binding to the CTP pocket. In this context, preliminary docking experiments were performed using the empty target and a ligand obtained by replacing the azido function of 11 by a methyltriazole moiety. Docking scores and the pose obtained when 11 is in the CTP pocket show that fragment growing using click chemistry is feasible.

Therefore, the discovery of MEPN 3 as a new YgbP inhibitor as well as its unusual mode of action paves the way for original approaches toward the discovery of drug candidates that are urgently needed for the treatment of antimicrobial-resistant Enterobacteriacea infections.

Materials and Methods

General conditions for enzyme kinetics. Colorimetric assay reported by Bernal et al. [START_REF] Bernal | A colorimetric assay for the determination of 4-diphosphocytidyl-2-C-methyl-D-erythritol 4-phosphate synthase activity[END_REF] was used with some modifications. The standard reaction mixture contained 50 mM Tris-HCl pH = 8, 1 mM MgCl 2 , 1 mM DTT, 133 mU/mL of inorganic pyrophosphatase, 200 µM CTP (when MEP was the variable substrate), 250 µM MEP (when CTP was the variable substrate) unless otherwise stated and 0.065 µg YgbP enzyme in the final volume of 400 µL. Assays were initiated by addition of YgbP and incubated eight min at 30 °C before being quenched with 100 µL dye reagent (for preparation see SI). The assays were further incubated for ten min before measuring OD at 630 nm. A blank reaction that contained every component except YgbP was carried out at the same time for each assay and the corresponding OD 630 value of the blank was subtracted from the OD 630 value measured for the assay. The phosphate concentration of the assays was determined from standard curves obtained by measuring OD 630 values of different phosphate standards with concentrations varying from 2 to 30 µM. Data were fitted with the least-squares method to the corresponding equations using GraphPad Prism 7.

YgbP kinetic parameter determination. MEP concentrations were 15, 30, 45, 60, 100, 150 and 250 µM when MEP was the variable substrate and CTP concentration was fixed at 200 µM. CTP concentrations were 30, 60, 90, 120, 180, 270 and 450 µM when CTP was the variable substrate and MEP concentration was fixed at 250 µM.

YgbP inhibition kinetic studies. Steady-state kinetic constants were determined from different assays at several fixed inhibitor concentrations and varying the concentration of one substrate and keeping the concentration of the other substrate constant. The initial velocities and concentrations were fitted according to the appropriate model of inhibition [START_REF] Segel | Enzyme kinetics: Behavior and Analysis of Rapid Equilibrium and Steady State Enzyme Systems[END_REF] .

YgbP mechanism determination.

YgbP bi-substrate kinetic assays were performed, first by varying MEP concentrations at several fixed CTP concentrations and second by varying CTP concentrations at several fixed MEP concentrations. The data were fitted to the corresponding equations to determine kinetic values as described in SI.

YgbP kinetic studies with MEPN 3 as a substrate. MEPN 3 concentrations were 40, 150, 300, 400, 600, 1000, 1500, 2000 and 3000 µM and CTP concentration was fixed at 200 µM.

MEPN 3 as substrate of YgbP. MEPN 3 (0.2 mM) was added to a mixture of CTP (1 mM), MgCl 2 (5 mM), DTT (1 mM) in a final volume of 200 μL buffer (Tris HCl, 50 mM pH = 8). E. coli YgbP (34 µg) was added to initiate the reaction. The reaction mixture was incubated at 30 °C for one h then MeCN (200 µL) was added, and the mixture was left at 0 °C for 20 min to precipitate proteins. The precipitate was removed by centrifugation (13000 rpm, 10 min). BCN-TMPP (0.8 mM) was added to the supernatant that was further incubated at 37 °C overnight. The mixture was analysed by LC-MS (Waters Alliance 2690 LC system with C 18 column coupled with Waters ACQUITY QDa mass detector) using 10 µL of injection volume.

Docking experiments.

In silico docking experiments were carried out with the Schrödinger suite (Schrödinger LLC, New York, NY, USA). The X-ray structure of the CDP-ME synthase with CTP (PDB ID 1I52) was used for the studies [START_REF] Richard | Structure of 4-diphosphocytidyl-2-C-methylerythritol synthetase involved in mevalonate-independent isoprenoid biosynthesis[END_REF] . The protein structure was processed with the protein preparation wizard tool. Ligand 3D structures, tautomers and ionisation states were produced with LigPrep. The CDP-ME binding pocket was used to generate the docking grid. We defined a docking area of 32 Å × 32 Å × 32 Å centered on the reaction product (CDP-ME). No constraints (such as hydrogen bond or atom position) were applied to guide the binding. All the compounds were docked using Glide [START_REF] Friesner | Extra precision glide: Docking and scoring incorporating a model of hydrophobic enclosure for protein-ligand complexes[END_REF] in extra precision (XP) mode [START_REF] Halgren | Glide: A new approach for rapid, accurate docking and scoring. 2. Enrichment factors in database screening[END_REF] . The Glide docking score was used to rank the docking poses.

Figure 1 .

 1 Figure 1. MEP pathway.

Figure 2 .

 2 Figure 2. Synthesis of MEPN 3 (11) and BCN-TMBPP (23). (a) Synthetic route to MEPN 3 . (a) (CH 3 ) 3 SOI, NaH, DMSO, 10 min, r.t; (b) NaN 3 , NH 4 Cl, DMF, 2 h, 60 °C; (c) TBAF, THF, 0 °C to r.t; (d) (CH 3 O) 2 POCl, DMAP, DCM, 2 h, 0 °C; (e) DOWEX (H + ), MeOH, 48 h, r.t; (f) (CH 3 ) 3 SiBr, H 2 O, DCM, 0 °C to r.t. (b) Synthetic scheme for BCN-TMPP. (a) Ethylenediamine, TEA, DMF, 2 h, r.t; (b) Bromoacetic acid N-hydroxysuccinimide ester, toluene, 0.5 h, r.t; (c) NEt 3 , DCM, 16 h, r.t.

Figure 3 .

 3 Figure 3. LC-MS analysis of MEPN 3 or its product in the YgbP catalysed reaction after derivatisation with TMPP-BCN (23). (a) Structure of CDP-MEN 3 (b) Structure of MEPN 3 or of its product after derivatisation with TMBPP-BCN. (c) Mass-to-charge ratio of MEPN 3 clicked with TMPP-BCN. (d) Mass-to-charge ratio of the product of 11 in the YgbP catalysed reaction clicked with 23.

Figure 4 .

 4 Figure 4. Inhibition of E. coli YgbP by MEPN 3 . (a) Steady state kinetics at variable MEP concentrations and fixed MEPN 3 concentrations (0 µM, r 2 = 0.99; 20 µM, r 2 = 0.98; 40 µM, r 2 = 0.99; 60 µM, r 2 = 0.99). (b) Double reciprocal plot of (a) (0 µM, r 2 = 0.99; 20 µM, r 2 = 0.99; 40 µM, r 2 = 0.98; 60 µM, r 2 = 0.99) (c) Replot of slope and intercept of (b) (slope, r 2 = 0.98; intercept, r 2 = 0.95). (d) Steady state kinetics at variable CTP concentrations and fixed MEPN 3 concentrations (0 µM, r 2 = 0.98; 30 µM, r 2 = 0.99; 60 µM, r 2 = 0.99; 90 µM, r 2 = 0.98). (e) Double reciprocal plot of (d) (0 µM, r 2 = 0.99; 30 µM, r 2 = 0.98; 60 µM, r 2 = 0.98; 90 µM, r 2 = 0.99). (f) Replot of slope and intercept of (e) (slope, r 2 = 0.99; intercept, r 2 = 0.95). Mean and SEM values are displayed, n ≥ 3.

Figure 5 .

 5 Figure 5. Structures of E. coli YgbP described (26-28) and new (11) inhibitors. Ki values are displayed when available, otherwise they are replaced by the reported IC 50 values.

Figure 6 .

 6 Figure 6. In silico docking results. Docking experiments were performed with the X-ray structure of E. coli YgbP: CTP complex (PDB ID: 1I52). The best docking poses and their corresponding docking scores (D.S) are reported. (A,B) CTP and respectively MEPN 3 docked using a target with an empty binding pocket. (C) to (F) docking poses revealing the two possible binding sites observed for MEP (C,E) or MEPN 3 (D,F) when the docking experiments were performed with a target already containing bound CTP. The compounds were docked using Glide in extra precision (XP) mode and the Glide docking score was used to rank the docking poses.

Figure 7 .

 7 Figure 7. Bi-substrate steady-state kinetic analysis of E. coli YgbP. (a) Double reciprocal plot of initial velocities at variable MEP concentrations and fixed CTP concentrations (30 µM, r 2 = 0.99; 50 µM, r 2 = 0.99; 80 µM, r 2 = 0.96; 240 µM, r 2 = 0.99). (b) Slope and intercept replot of (a) (slope, r 2 = 0.97; intercept, r 2 = 0.90). (c) Double reciprocal plot of initial velocities at variable CTP concentrations and fixed MEP concentrations (10 µM, r 2 = 0.99; 20 µM, r 2 = 0.96; 40 µM, r 2 = 0.95; 120 µM, r 2 = 0.98). (d) Slope and intercept replot of (c) (slope, r 2 = 0.97; intercept, r 2 = 0.92). Mean and SEM values are displayed, n ≥ 3.

Figure 8 .

 8 Figure 8. E. coli YgbP bi-substrate steady state kinetic analysis. For reasons of clarity, the scheme was simplified as in the YgbP-MEP complex, MEP could also bind in the CTP binding site. See Fig.S3for detailed reaction mechanism.

Scientific REPORTS | (2018) 8:17892 | DOI:10.1038/s41598-018-35586-y

Acknowledgements

This work was supported by a grant from "Centre International de Recherche aux Frontieres de la Chimie", by the Centre National de la Recherche Scientifique (CNRS) and University of Strasbourg. We are thankful to Magali Parisse for technical assistance. We appreciate the help from the staff of the computing facility provided by the Commissariat à l'Energie Atomique (CEA/DSV/GIPSI), Saclay, France, and the Centre de Calcul Recherche et Technologie (CEA/CCRT), Bruyères-le-Châtel, France.

Author Contributions

Additional Information

Supplementary information accompanies this paper at https://doi.org/10.1038/s41598-018-35586-y.

Competing Interests:

The authors declare no competing interests.

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.


Valentin Antuori

Florian Richoux

Constrained optimization under uncertainty for decision-making problems: Application to Real-Time Strategy games

Keywords: Combinatorial optimization, Uncertainty, Decision-making problems, Constraint programming, Decision theory, Real-Time Strategy games

HAL is a

I. Introduction

Decision-making problems can be modeled as combinatorial optimization problems through a given formalism, and then can be solved with appropriated tools, i.e., solvers. Combinatorial optimization problems are very frequent problems in domains such as logistics, finance, supply chain, planning, scheduling and in industries such as pharmaceutical industry, transportation, manufacturing and automotive industry [START_REF] Rossi | The Handbook of Constraint Programming[END_REF].

Strategy games propose a rich environment to study decision-making problems, allowing researchers to develop new algorithmic approaches to model and solve such problems. This is particularly true for Real-Time Strategy games, or RTS games, offering a dynamic environment under a fog of war forbidding players to have a complete information about the game state. Such environments contain many challenging combinatorial optimization problems.

This research was supported by the Pays de la Loire region through the Atlanstic 2020 research grant COPUL.

Combinatorial optimization problems can be expressed through different formalisms. One convenient formalism used in AI is Constraint Satisfaction Problems (CSP) and Constrained Optimization Problems (COP). The first formalism deals with satisfaction problems, i.e., problems where all solutions have the same quality. In this paper, a solution is an assignment of each variable of the problem such that all constraints are satisfied. The second formalism COP deals with optimization problems, i.e., problems where there is a criteria to rank solutions.

There exist many extensions of the CSP formalisms dealing with uncertainty, but very few of them have been extended to handle optimization problems, and when they did, they force to declare additional parameters that might be undesirable and inconvenient while modeling a problem.

This paper proposes a way to deal with a specific kind of decision-making problems through combinatorial optimization under uncertainty within the classical COP formalism using the Rank Dependent Utility from decision theory. We exhibit a proof of concept with a simple bot playing to the µRTS game while solving a decision-making problem of choosing the right units to produce. Our bot has won the partially observable track of the 2018 µRTS AI competition.

This paper is organized as follows: We first motivate why we focus on single-stage decision-making problem and why uncertainty is exclusively in the objective function in Section II. Then, we introduce basic notions about Constraint Programming and Decision Theory in Section III. In Section IV, we expose our main contribution: a way to handle uncertainty within the classical COP formalism using the Rank Dependent Utility and finally give a proof of concept in Section V by modeling with a COP a decision-making problem under uncertainty in µRTS. Related works can be found in Section VI. We conclude in Section VII.

II. Motivation

We introduce in this section the type of problems we focus on, and motivate why such problems worth to be specifically tackled.

In this paper, we study single-stage decision-making problem an agent must solve under uncertainty, where uncertainty lies on the value of some stochastic variables controlled by a third-party agent (such as the environment where our agent evolves). Such stochastic values only have an impact on the objective function the agent tries to maximize or minimize, and not on constraints it must satisfy.

We think important to motivate the two following points: why single-stage decision-making problems only, and why only considering uncertainty on the objective function rather than on both the objective function and the constraints.

Studying single-stage decision-making problems means that a decision must be made before revealing stochastic values so far unknown. Once these values are known, the agent can only observe the consequences of its decision without having the possibility to sharpen or fix it like in multi-stage decision-making processes. Although multistage decision-making problems are interesting and would deserve a proper study, we think single-stage decisionmaking problems are still relevant and capture all one-shot decision-making problems that must be made recurrently. Concrete examples can be 1. a factory manager deciding about the production of the month taking into account the stock (known) and client orders (unknown), 2. blind auctions where one aims to win some auctions taking into account the available money (known) and other participants bid (unknown) or 3. air traffic management where one must take into account the number of waiting planes for taking off and landing (known) and future demands (unknown). In his PhD thesis [START_REF] Piette | Une nouvelle approche au General Game Playing dirigée par les contraintes[END_REF], Éric Piette shows that decision-making problems in strategy games can be handle in practice by single-stage decision-making problems only. Finally, another reason to study single-stage decisionmaking problems is that some environments do not allow multi-stage problems: to do multi-stage decision-making, some stochastic variables must be revealed at each stage. However, it is easy to find natural problems where stochastic variables are never completely revealed. This is the case in RTS games for instance, where the fog of war is never completely dissipated. The problem we tackle in the paper belongs to this category.

Considering uncertainty having only an impact on a solution quality (the objective function) rather than its possibilities (the constraints) makes sense for the same reasons as above: There are many concrete decision-making problems where one knows what is possible and what is not, but does not known what the quality of its decisions will be. In other words, the scope of our possible decisions is known (our constraints) but we live in an uncertain, dynamic environment where events out of our control can impact not the applicability of our decisions but their quality. Examples cited in the previous paragraph are still relevant here: whatever our client orders, we can make a production plan of the month regarding our available stock only; we can bid to an auction regarding only our available money, but we can lose because of better bids; and we can plan air traffic knowing the current situation, but we can be overwhelmed by a group of arriving planes if we made bad runway assignments.

III. Preliminaries A. Constraint Programming

The basic idea behind Constraint Programming is to deal with combinatorial problems by splitting them up into two distinct parts: the first part is modeling your problem via one Constraint Programming formalism. This is usually done by a human being and this task must be ideally easy and intuitive. The second part consists in finding one or several solutions based on your model. This is done by a solver, i.e., a program running without any human interventions.

The two main formalisms in Constraint Programing are Constraint Satisfaction Problems (CSP) and Constrained Optimization Problems (COP). The difference between a CSP and a COP is simple:

A CSP models a satisfaction problem, i.e., a problem where all solutions are equivalent; the goal is then to just find one of them, if any. For instance: finding a solution of a Sudoku grid. Good grids lead to a unique solution, but let's consider several solutions are possible for a given grid. Then, finding one solution is sufficient, and no solutions seem better than another one. Sometimes, we may also be interested in finding all solutions of a problem instance.

A COP models an optimization problem, where some solutions are better than others. For instance: Several paths may exist from home to workplace, but one of them is the shortest.

Formally, a CSP is defined by a tuple (V , D, C) such that:

• V is a set of variables, • D is a domain, i.e., a set of values for variables in V , • C is a set of constraints. A constraint over k variables can be seen as a function from D k to {true, f alse} to make explicit what combinations of values among its k variables are allowed or not.

Notice that D should formally be the set of the domain for each variable in V , thus a set of sets of values. However, it is common to define the same set of values for all variables of V , thus one can simplify D to be the set of values each variable in V can take.

A CSP models a problem, and a problem instance is expressed by a CSP formula, i.e., a set of constraints applied on variables in V where all constraints are linked by a logical and. The goal is then to attribute a value in D for each variable in V such that all constraints in C are satisfied, i.e., outputs true.

A COP is defined by a tuple (V , D, C, f ) where V , D and C represent the same sets as a CSP, and f is an objective function applied on variables in V . The goal is first to find a solution, i.e., a value of each variable such that all constraints are satisfied, like for CSP, but moreover to find the solution minimizing or maximizing the objective function f among all possible solutions.

CSP and COP deal with certain information only. There exist many extensions of the CSP formalisms dealing with uncertainty: Mixed CSP, Probabilistic CSP, Stochastic CSP, etc. We invite the reader to look at surveys [START_REF] Verfaillie | Constraint solving in uncertain and dynamic environments: A survey[END_REF] and [START_REF] Hnich | A Survey on CP-AI-OR Hybrids for Decision Making Under Uncertainty[END_REF] on this topic. However, few are convenient to model a decision-making problem where one does know what his or her possible choices are (i.e., variables, domains and constraints are known and fixed), but a thirdparty agent (a person, an environment, etc) fixes the values of some specific variables. These values are unknown at the moment we must make a decision and impact the value output by the objective function. Stochastic CSP [START_REF] Walsh | Stochastic Constraint Programming[END_REF] is the most well adapted formalism to model such problems, but with the huge drawback that constraints are considered to be chance-constraints, i.e., constraints are considered true if their probability to be true reaches a given threshold. The main problem with such a formalism is that this threshold must be provided by the human being modeling the problem, and it is often unclear in practice how to fix a good threshold value for a given problem. This does not follow the Constraint Programming philosophy where problem models must be easy to produce by a human being, without any arbitrary choices.

Moreover, while COP are a trivial extension of CSP with an objective function, it is absolutely not clear how to extend constraint satisfaction formalisms under uncertainty to deal with optimization problems. Indeed, to each solution of a problem can correspond several possible objective function values, due to uncertainty on stochastic variables, and such values depend on the state of an environment determining stochastic variable values. How is it then possible to discriminate solutions between them?

To the best of our knowledge, no Constraint Programming formalisms without chance-constraints able to handle optimization problems under uncertainty have ever been proposed. We propose in Section IV a way to deal with uncertainty within the classical COP formalism, allowing us to solve such problem models with classical solvers.

B. Decision Theory

We consider the set D of decisions an agent can take. The goal is to define a preference relation D on this set. Preferring the decision d 1 over d 2 means to prefer d 1 consequences over d 2 ones, thus we can also consider a space X of consequences, and study a preference relation X on this space in such a way that we have

d 1 D d 2 ⇐⇒ x 1 X x 2
where x i is the consequence of the decision d i . However, we do not have this equivalence anymore when uncertainty comes into play, because we are not sure anymore the decision d will lead to the consequence x.

In uncertain environments, we consider the set S of possible states of the environment. We consider consequences to be sets of states after making a decision. Thus, we have X = P(S).

Utility-based theories consider P a probability distribution over X , i.e., a probability distribution over sets of possible states in S. Let p d be the probability following P of obtaining the consequence x d ∈ X after making the decision d.

We can then introduce the notion of lottery. A lottery l is a tuple (x 1 , p 1 ; ...; x n , p n ) where x i is a consequence and p i its associated probability, such that

n i=1 p i = 1.
A lottery is thus a sum-up of a decision in the sense it represents the list of possible consequences of a decision with their associated probabilities. Let L be the set of lotteries. We can then define a preference relation L on L. How we define L exactly depends on the decision theory, but the idea is to bring back the equivalence

d 1 D d 2 ⇐⇒ l 1 L l 2 .
There exist different works on decision theory to establish this equivalence. We have thus the notion of Expected Utility (EU) defined by [START_REF] Neumann | Theory of Games and Economic Behavior[END_REF] in the game theory framework. However EU has a limited power of expression since one can quickly derivate paradoxes such as the Allais Paradox violating the independence axiom, telling that if someone has no preference between decisions A and B, then he or she must still not have no the preference if we mix A and B with some decision C.

Choquet Expected Utility is a decision theory based on capacities, a notion generalizing probabilities. A special case of Choquet Expected Utility restricted to probability deformation function is the Rank Dependent Utility (RDU) introduced by [START_REF] Quiggin | A Theory of Anticipated Utility[END_REF], [START_REF]Generalized Expected Utility Theory: The Rank Dependent Model[END_REF]. RDU has more power of expression than EU since it can explain the Allais Paradox. Unlike EU, RDU allow to model attraction or repulsion to risks through a probability deformation function. This can help to modify on-the-fly the behavior of an agent taking a decision regarding its environment.

The Rank Dependent Utility is then a way to compute L , and then to evaluate and compare lotteries such that l 1 L l 2 ⇐⇒ RDU (l 1 ) ≥ RDU (l 2 ). RDU applied to the lottery l is the function defined by Equation 1. In Equation 1, u(x) is a utility function over the consequence space, intuitively giving a score to consequences, and φ(p) an increasing function from [0, 1] to [0, 1] and interpreted as a probability deformation function. The function φ(p) can be anything, as soon as it is monotone and both equalities φ(0) = 0 and φ(1) = 1 hold. Consequences in the lottery l are ordered such that ∀x i , x j with i < j, we have u(x i ) ≤ u(x j ).

This probability deformation function φ allows to model risk-aversion since a concave φ function defines an attraction to risks and a convex φ function a repulsion to risks. Intuitively, if we have φ(p) ≤ p for all p, then the agent taking a decision will underestimate gains probabilities and then will show a kind of pessimism about risks. We

RDU (l) = u(x 1 ) + u(x 2 ) -u(x 1 ) * φ n i=2 p i + u(x 3 ) -u(x 2 ) * φ n i=3 p i + . . . + u(x n ) -u(x n-1 ) * φ(p n ) (1)
will have the opposite behavior if we have φ(p) ≥ p for all p. Notice that sigmoid functions, which are neither concave nor convex, are also possible. In our experiments in Section V, we use a sigmoid function rather than a convex function to model pessimism, to decrease probabilities of good outcomes and increase probabilities of unfavorable ones.

Remember that consequences x i in l are ordered according to the value of u(x i ), such that consequences with a small score outputed by the utility function u are placed at the beginning of the lottery l. The intuition behind Equation 1 is then the following: With probability p = 1, by making the decision d, you are sure to have at least the score of the worst consequence x 1 , i.e., u(x 1 ). Then, with (deformed) probability φ(p 2 + . . . + p n ), you can have the score u(x 1 ) plus a gain equals to u(x 2 )-u(x 1 ) . With probability φ(p 3 +. . .+p n ), you can have an additional gain equals to u(x 3 ) -u(x 2 ) , and so on until having an additional gain equals to u(x n ) -u(x n-1 ) with probability φ(p n ). The obtained value depends on the order, or rank, of the value of the utility function applied to consequences, justifying the name "Rank Dependent Utility".

However, defining a utility function u over the consequence space it not easy, even for numerical-only consequences. This space is completely dependent on the problem and even on the problem instance so it is not realistic to propose general-purpose utility functions that could work and certify a behavior on any kind of decision-making problem. This is however possible with the probability deformation function φ since it is always a function from [0, 1] to [0, 1].

Our decision-making problems being modeled as optimization problems, a consequence x of a decision d is the value of our objective function. Therefore, the relation X is merely the relation ≥ over real numbers. This implies that u is a function from R to R. In this work, we consider u to be the identity function id(x) = x and will use generic probability deformation functions φ to change an agent's behavior regarding risks.

IV. Main contribution

The main difficulty to tackle a combinatorial optimization problem under uncertainty via Constraint Programming is the lack of reliable criterion to attribute a quality to each possible solution. How do you rank solutions if they lead to different objective function values regarding possible values of stochastic variables?

The main contribution of this paper is proposing to inject the Rank Dependent Utility from decision theory into the classical COP formalism to solve optimization problems under uncertainty.

We consider decision-making problem where one knows what our variables are, what values they can take (i.e., we know the domain of each variable), what values combinations are possible or not (i.e., we know our constraints), but where we have an objective function to optimize implicating stochastic variables for which values are unknown at the moment we must take a decision, such that only a third-party (the environment, an independent agent, etc) has the power to set the value of these variables.

This describes in fact most common decision-making situations: when we have to take a decision, we often miss some pieces of information (we cannot have a perfect knowledge about everything) that still have an impact on the quality of our decision. Should I invest my money in stocks or bitcoins? We do not know if the price will climb up or fall down, but we know however what we can or cannot do (how much money can we invest for instance). The quality of our decision will be only revealed once stochastic variables values will be known.

A. Injecting RDU into COP

We recall we are interested in modeling uncertainty in decision-making problems. These problems without uncertainty can be modeled through the COP formalism. For many cases, uncertainty in decision-making problems does not affect what you can or cannot do but on external unknown elements that have a direct impact on the decision quality.

An easy way to model such decision-making problems is to model it through the regular COP formalism, by defining 1. a set of decision variables, i.e., regular variables which the solver has the control on, 2. a set of stochastic variables, representing all unknown pieces of information, 3. a domain for both decision and stochastic variables, 4. a probability distribution for the domain of each stochastic variable, 5. a set of constraints upon decision variables and 6. an objective function mixing decision and stochastic variables. If probability distributions of stochastic variables are unknown, we can approximate them with statistics. A convenient point with games is that we can often simulate their environment or analyze replays and then collect those statistics fairly easily.

Like Equation 1 suggests, we need to know all consequences of a decision to compute RDU. This is of course intractable since we have |D| |S| consequences for each decision, with |S| the number of stochastic variables and |D| the cardinality of their domain. A convenient way to approximate RDU is to do Monte Carlo sampling of stochastic variable values, following their probability distribution.

We can now apply our objective function to compute the RDU and get a usable metric under uncertainty, which allows us to rank solutions and guide our decisions.

Let's consider a problem modeled by a COP with decision variables v i , stochastic variables s j and an objective function f . Like described in Subsection III-B, consequences x i of a decision d corresponds to values output by f . In the context of a COP, a decision d is a vector of values assigned to each decision variables v i . Using Algorithm 1, we can compute the relation D among decisions by approximating the RDU of their respective lottery with Monte Carlo samplings.

In our experiments next section, we draw k = 50 samples. In Algorithm 1, k being a parameter and not an input, we do not take it into count to compute the algorithm complexity. The complexity of Algorithm 1 is then in Θ(f ), depending on the complexity of the objective function f only. Sampling m stochastic variables is also outside the scope of the complexity of Algorithm 1 since stochastic variables are not among its inputs.

V. Proof of concept

We give a proof of concept of our contribution to show it is implementable and use it to solve a decisionmaking problem under uncertainty in a RTS game. We have included this decision-making solving system into a bot playing to the game µRTS. Our bot, named POAdaptive, has won the partially observable track of the 2018 µRTS AI competition organized within the CIG 2018 conference. The code of our bot, our experimental setup and our experimental results can be found in the following github repository: github.com/richoux/micrortsuncertainty/releases/tag/v1.0.

We will consider the following problem: RTS game propose to train units which often follow a rock-paper-scissors scheme. Because of the fog of war, we do not perfectly know the enemy army composition and we must infer his or her strategy from some partial observations. We must constantly take a production decision answering this question: "What next units should I produce to counter my enemy strategy?"

A. µRTS

We decided to use µRTS has an experimental environment. µRTS is an open-source, minimalist real-time strategy game developed by Santiago Ontañón for research purpose [START_REF] Ontañón | The Combinatorial Multi-armed Bandit Problem and Its Application to Real-time Strategy Games[END_REF].

The game is made upon classical RTS mechanisms: there are resources (or money) to gather (green squares in Figure 1). This money allow us to build buildings and train units. In µRTS, there are two kind of buildings: bases (white squares) where money is stocked and barracks (grey squares) where army units are produced. Four units are available in µRTS: workers (small grey circles), light units (orange circles, not appearing in Figure 1), ranged units (blue circles) and heavy units (large yellow circles). Workers are weak against all units but are the only ones able to gather resources and build buildings. Light, ranged and heavy units are following a rock-paper-scissors scheme, in the sense that heavy units are strong against light units, light units are strong against range units and range units are strong against heavy units.

To win, a player must destroy all enemy units and buildings. If nobody reaches that goal before a fixed number of frames, the game ends in a draw.

µRTS supports both complete and partially observable games. In order to test our method solving decisionmaking problem under uncertainty, we used µRTS exclusively in partially observable mode.

B. Deciding about unit production

We propose here a model of our production problem through the regular COP formalism. Let's consider {H, L, R} the heavy, light and ranged type of units, respectively. We have:

• Two kind of decision variables: plan X , with X ∈ {H, L, R}, representing the total number of units of type X we should have (i.e., the total number of units we currently possess plus the number of units we plan to produce), and assign XY , ∀X, Y ∈ {H, L, R}, the number of our units of type X we plan to use to counter enemy units of type Y . • One kind of stochastic variables: enemyU nits X , with X ∈ {H, L, R}, representing the total number of units of type X the enemy currently possesses. • Domains for each variable are natural numbers from 0 to a threshold. We used 20 as a threshold in our experiments, which is sufficient for small maps in µRTS.

RDU ← x[1] + (x[2] -x[1]) * φ( k-1 k ) + (x[3] -x[2]) * φ( k-2 k ) + . . . + (x[k] -x[k -1]) * φ( 1 k ); 8 return RDU 2(plan L -ourU nits L ) ≤ stockResource
The first three constraints create the bridge between the total number of units of type X we aim to have and the number of units of type X we consider we need to counter an unknown number of enemy units of type Y . The last constraint is the resource balance constraint: given ourU nits X the number of units of type X we currently have, (plan X -ourU nits X ) corresponds to the number of units X we have to produce. A heavy unit costs 3 resource points, a light and ranged units only 2. The parameter stockResources corresponds to the current resource points we possess at the moment of we must decide about our production. The min function for target X is to avoid a mere sum of the expressions HX * assign HX + RX * assign RX + LX * assign LX -enemyU nits X for the three possible X ∈ {H, L, R}, otherwise it would lead to simply produce the unit with the highest AB-type coefficient. We take the minimum between these expressions and the value 1 to allow to produce up to one more unit than necessary.

Our AB-type coefficients have been estimated by running 200 games of 10 units of A against 10 units of B, for each combination of AB ∈ {H, L, R} 2 . We then took the ratio of the total numbers of surviving units over 200 simulations. For instance, after 200 games of type "10 heavy versus 10 light", we had 1284 surviving heavy units and 480 surviving light units. Then our parameter HL is equals to 480 1284 = 0.3738 (i.e., we need 0.3738 heavy unit to deal against 1 light unit) and LH is equals to 1284 480 = 2.675. Finally, statistics on enemyU nits X stochastic variables have been made by analyzing 800 replays of µRTS games from 2017 competitions. For each frame and each unit type, we counted these units occurrence. These statistics are sharpen by observations while playing a game: if we observe for instance 3 enemy light units at the same moment, we nullify probabilities that the enemy has 0, 1 or 2 light units only, and we normalize remaining probabilities.

C. Experiments

Few µRTS bots have been developed for partially observable games, and most of them are in fact scripted bots. We have taken a basic rush bot and only modify its production behavior, giving our bot POAdaptive. We did not modify its initial build order (produce no additional workers, start immediately a barracks with our unique worker and then gather resources until the end of the game). We only add a quick hit-and-run behavior for our ranged units and a light seek-and-destroy behavior.

Our bot adapts its production in function of the RDU preference computed according to the objective function. We give our pure COP model to the GHOST solver [START_REF] Richoux | GHOST: A Combinatorial Optimization Framework for Real-Time Problems[END_REF], a solver dealing with classical CSP or COP models and unable to handle uncertainty directly. This shows that our way to inject decision theory into the classical COP formalism is sufficient to handle uncertainty and do not required to develop a new formalism neither dedicated solvers. We give to the solver 100 milliseconds per frame as computation budget to solve our COP problem, to be consistent with µRTS competitions rules.

With our bot POAdaptive, we won the partially observable track of the 2018 µRTS AI competition, over 7 competitors. We did not tweak our bot before the competition to be efficient on the competition maps neither against specific bots (such as 2017 competitors). This show that our decision-making solving is efficient enough to beat scripted rush bots as well as MCTS-based and Hierarchical Task Network-based bots. Figure 2 shows final scores of the 2018 µRTS AI competition, over 720 games for each bot within a round-robin tournament over 12 maps (4 of them were kept secret before the beginning of the competition). The cumulative score is the sum of the score result for each game, i.e., 1 for a win, 0.5 for a tie and 0 for a loss. The scores are normalized by dividing the cumulative scores by the number of games per bots, i.e., 720. To evaluate our decision-making process, we run 100 games (50 starting at the North-East position, 50 starting at the South-West position) between the second best bot of the competition, POLightRush bot, and four methods: POAdaptive using RDU with a pessimistic φ function, POAdaptive using RDU with an optimistic φ function, POAdaptive using Expected Utility instead of RDU (this can be easily done by using RDU with φ as the identity function), and finally a baseline bot having exactly the same behavior as POAdaptive except for the unit production decision, taken randomly among the three military units. The pessimistic function we use is the logistic function φ(p) = with λ = 10. We run experiments on three small basic maps 8x8, 12x12 and 16x16 as well as on three large basic maps 24x24, 32x32 and 64x64. Results on small maps are shown in Table I, and normalized scores are illustrated by Figure 3. We choose to show results on small maps only since they are more representative of our decisionmaking system performances. Indeed on larger maps, POAdaptive has too few occasions to meet enemy units since no scouting behavior has been written (we know by experience that coding a proper scouting behavior would not be so trivial). Thus, behavior of these four methods tends to be the same. POAdaptive's adaptation skills give it a slight advantage and then slight better scores than the baseline method. On these larger maps, RDU with the optimistic φ gives the best results (this optimistic version was besides used for the CIG 2018 competition), slightly better than the pessimistic version. In average on these maps, normalized scores of both RDU versions is around 0.8.

On small maps, Table I and Figure 3 show that both RDU versions outperformed the EU version, itself outperforming our baseline. Unlike for large maps, the pessimistic version gives slightly better results than the optimistic version. This can be explained by the fact that small maps do not give you a lot of time to react when you spot an unfavorable enemy army composition. Being already prepare to the worst helps in that case.

VI. Related works

Uncertainty has been intensively studied for the last 30 years in fields dealing with combinatorial optimization such as Operational Research [START_REF] Birge | Introduction to Stochastic Programming[END_REF], but significantly less works have been done for optimization under uncertainty in Constraint Programming [START_REF] Hnich | A Survey on CP-AI-OR Hybrids for Decision Making Under Uncertainty[END_REF]. To the best of our knowledge, all methods to solve optimization problems through Stochastic Constraint Programming use a formalism considering chance-constraints, usually handled by scenariobased methods. [START_REF] Babaki | Stochastic Constraint Programming with And-Or Branch-and-Bound[END_REF] is a recent example where the authors inject a probabilistic inference engine from the graphical model community into a classical solver to solve Stochastic CSP instances, thus dealing with chance-constraints.

There are also few works in RTS Game AI using Constraint Programming techniques, in particular through Constraint Satisfaction/Optimization Problems, and few of them dealing with uncertainty. However, we can cite works of [START_REF] Koriche | General game playing with Stochastic CSP[END_REF]- [START_REF] Koriche | Constraint-Based Symmetry Detection in General Game Playing[END_REF] where authors use Stochastic CSP to make a bot participating to the General Game Playing competition. Their bot has won the 2016 competition.

Although the following papers do not deal with uncertainty, they all focus on solving optimization problems in RTS games, in particular StarCraft. Thus [START_REF] Richoux | Walling in Strategy Games via Constraint Optimization[END_REF] propose to model with COP the optimal building placement to make a wall at a base entrance in order to make easier its defense. [START_REF] Richoux | GHOST: A Combinatorial Optimization Framework for Real-Time Problems[END_REF], [START_REF] Fradin | Robustness and Flexibility of GHOST[END_REF] propose a CSP and COP solver, GHOST, that we used for our experiments. Their Constraint Programming solver as been designed to output good quality solution within some tenth of milliseconds, make it usable in RTS games.

Beyond Constraint Programming but close enough, [START_REF] Churchill | Build order optimization in Star-Craft[END_REF] use a branch and bound algorithms to optimize build order in the RTS game StarCraft. Like [START_REF] Richoux | Walling in Strategy Games via Constraint Optimization[END_REF], [START_REF] Čertický | Implementing a Wall-In Building Placement in StarCraft with Declarative Programming[END_REF] tackle the problem to optimize a wall-in building placement in StarCraft but through the prism of Answer-Set Programming.

VII. Conclusion

In this paper, we proposed a way to deal with combinatorial optimization problems under uncertainty within the classical Constrained Optimization Problems formalism by injecting the Rank Dependent Utility from decision theory. The difficulty for Constraint Programming formalisms of handling both optimization and uncertainty at the same time was due to the impossibility to rank solutions if they lead to different objective function values regarding possible values of stochastic variables.

We get around this difficulty by computing preferences over decisions with the Rank Dependent Utility using our objective function to score decisions. This allow us to show it is possible to handle uncertainty with regular Constraint Programming solvers, without having to define a new formalism neither to develop dedicated solvers for uncertainty. This brings new perspective to tackle uncertainty in combinatorial optimization problems that where considered so far to be intractable.

To show our result is usable in practice, we propose a proof of concept of our result by modeling a decisionmaking problem under uncertainty in the µRTS game via the classical COP formalism, and we solve it using a regular COP solver. We thus tackle a production unit problem and implement a bot playing partially observable µRTS games and deciding what units to produce in order to maximize its chance to counter its opponent strategy. Our bot has won the partially observable track of the 2018 µRTS AI competition and outperforms equivalent bots based on Expected utility or randomly producing units.

Our result only concern short-horizon decision-making problems. We could adapt it to take into account larger horizons of action planning and integrate it into a bot taking long-term strategy decision under uncertainty. We also would like to investigate problems where constraints contain stochastic variables. Finally, it would be interesting to implement our result into a bot playing a more ambitious game such as StarCraft. This method should scale to a larger game like StarCraft since we already successfully used GHOST in that game to solver other optimization problems.

Figure 1 .

 1 Figure 1. A game frame of µRTS on a 8x8 map. Resources are in green, squares are buildings and round items are units.

Figure 2 .

 2 Figure 2. Final normalized scores of the partially observable track of the 2018 µRTS AI competition.

1 1+exp(

 1 -λ * (2 * p-shif t)) where p is the probability and with parameters λ = 10 and shif t = 1.3. The optimistic function is the logit function φ(p) = 1 + log( p 2-p ) λ

Figure 3 .

 3 Figure 3. Normalized sum of scores of TableIfor each method.

  Estimating a preference on the decision d input : A decision d, i.e., a vector in D n , with D the domain of decision variables v 1 , . . . , v n output: A preference on d, i.e., a real value 1 Initialize an empty vector x of size k, with k a parameter for the number of wanted samples; Sample values for stochastic variables s 1 , . . . , s m according to their probability distribution; // f is our objective function, taking both decision and stochastic variables

	4	x[i] ← f (v 1 , . . . , v n , s 1 , . . . , s m );
	5 end
	6 Sort(x);
		// Considering each sample has a probability 1 k , computes RDU
	7

• Two kind of constraints: assign HL + assign HR + assign HH = plan H assign RL + assign RR + assign RH = plan R assign LL + assign LR + assign LH = plan L 3(plan H -ourU nits H ) + 2(plan R -ourU nits R ) + Algorithm 1: 2 for i = 1 to k do 3

Table I

 I Results of 100 games played against LightRush bot on three maps. In bold, results with the highest score for each map.

				Map size
			8x8	12x12	16x16
		Win	14	38	50
	Baseline	Tie Loss	0 86	2 60	12 38
		Score	14	39	56
		Win	27	35	52
	Expected utility	Tie Loss	2 71	6 59	9 39
		Score	28	38	56.5
		Win	23	44	55
	RDU with optimistic φ	Tie Loss	10 67	7 49	13 32
		Score	28	47.5	61.5
		Win	26	50	57
	RDU with pessimistic φ	Tie Loss	6 68	5 45	5 38
		Score	29	52.5	59.5