Haosheng Liang

Andryj M Borys

Eva Hevia

Marie-Eve L Perrin

Pierre-Adrien Payard

Shedding Light on the Hidden Roles of Lithium in the Nickel-Catalyzed Cross-Coupling of Aryl Ethers

Keywords: Nickel, Catalysis, Cross-Coupling, Mechanism, Heterobimetallics, DFT

The Ni-catalyzed cross-coupling of aryl ethers is a powerful synthetic tool to transform widely available phenolderivatives into functionalized aromatic molecules. Recent theoretical and experimental mechanistic studies have identified the involvement of heterobimetallic nickelates as key intermediates that facilitate the challenging transformation under mild conditions, and often without the need for external ligands or additives. In this work, based on calculations performed at the DFT level and by comparison with spectroscopic and kinetic data, we investigate the mechanism of the Ni(COD)2 catalyzed cross-coupling of 2-methoxynaphthalene with PhLi, and assess the speciation of lithium nickelate intermediates. The crucial role of solvent on the reaction is explained and the multiple roles played by lithium are unveiled. Experimental studies have identified key lithium nickelate species which support and help evolve the calculated reaction mechanism, and ultimately complete the catalytic cycle. Based on this new mechanistic knowledge, a well-known experimental challenge of these transformations, the so-called "naphthalene problem" which restricts the use of electrophilic coupling partners to π-extended systems, can be addressed to enable the cross-coupling of unbiased aryl ethers under mild conditions.

INTRODUCTION

The selective cleavage of C-O bonds and subsequent functionalization by transition-metal-catalyzed cross-coupling reactions constitutes an attractive strategy for the direct valorization of widely available phenol derivates. [START_REF] Zarate | Phenol Derivatives: Modern Electrophiles in Cross-Coupling Reactions[END_REF][START_REF] Rosen | Nickel-Catalyzed Cross-Couplings Involving Carbon-Oxygen Bonds[END_REF][START_REF] Qiu | Transformations of Less-Activated Phenols and Phenol Derivatives via C-O Cleavage[END_REF] Ethereal C-O bonds are rather unreactive however, and most of the well-established Pdcatalyzed cross-coupling methods are generally ineffective for these challenging substrates. Ni-catalysis, on the other hand, has proven to be powerful for many types of C-O bond functionalization reactions, including the cross-coupling and hydrogenolysis of aryl ethers. [START_REF] Tobisu | Cross-Couplings Using Aryl Ethers via C-O Bond Activation Enabled by Nickel Catalysts[END_REF][START_REF] Borys | Mechanisms of the Nickel-Catalysed Hydrogenolysis and Cross-Coupling of Aryl Ethers[END_REF] As early as 1979, Wenkert reported the first Ni-catalyzed activation of inert Caryl-OMe bonds in a Kumada-Tamao-Corriu type cross-coupling reaction. [START_REF] Wenkert | Nickel-Induced Conversion of Carbon-Oxygen into Carbon-Carbon Bonds. One-Step Transformations of Enol Ethers into Olefins and Aryl Ethers into Biaryls[END_REF] In more recent years, aryl ether derivatives have been used as electrophilic coupling partners in several types of cross-coupling reactions, including Suzuki, Negishi and Murahashi. [START_REF] Tobisu | Cross-Couplings Using Aryl Ethers via C-O Bond Activation Enabled by Nickel Catalysts[END_REF] Nevertheless, the range of aryl ethers that can be activated under these conditions is still quite limited, although the use of specific ligands or nucleophiles has helped overcome this so-called "naphthalene problem". [START_REF] Zarate | A Mild and Ligand-Free Ni-Catalyzed Silylation via C-OMe Cleavage[END_REF][START_REF] Dankwardt | Nickel-Catalyzed Cross-Coupling of Aryl Grignard Reagents with Aromatic Alkyl Ethers: An Efficient Synthesis of Unsymmetrical Biaryls[END_REF][START_REF] Xie | Cross-Coupling of Aryl/Alkenyl Ethers with Aryl Grignard Reagents through Nickel-Catalyzed C-O Activation[END_REF][START_REF] Iglesias | Kumada-Tamao-Corriu Coupling of Heteroaromatic Chlorides and Aryl Ethers Catalyzed by (IPr)Ni(Allyl)Cl[END_REF] For cross-coupling reactions involving aryl ethers, the choice of solvent, ligand and nucleophilic coupling partner have proven to be crucial, but mechanistic details on how these reactions proceed is still rather limited. [START_REF] Borys | Mechanisms of the Nickel-Catalysed Hydrogenolysis and Cross-Coupling of Aryl Ethers[END_REF] The conventional mechanism of cross-coupling reactions starts from a neutral Ni 0 complex and involves three key steps: (i) oxidative addition of the C-X bond to a ligated Ni 0 center; (ii) transmetalation between the organometallic nucleophile and the Ni II complex; and (iii) reductive elimination between the organic substituents to deliver the cross-coupled product and regenerate Ni 0 . [START_REF] Diccianni | Mechanisms of Nickel-Catalyzed Cross-Coupling Reactions[END_REF] Based on both experimental and computational mechanistic studies however, this simplified mechanism has been shown to be inappropriate for aryl ethers due to the high bond dissociation enthalpy of the Caryl-OMe bond. [START_REF] Borys | Mechanisms of the Nickel-Catalysed Hydrogenolysis and Cross-Coupling of Aryl Ethers[END_REF] DFT calculations by Wang and Uchiyama provided support for an alternative anionic pathway which instead involve anionic nickelate intermediates. [START_REF] Ogawa | How and Why Does Ni 0 Promote Smooth Etheric C-O Bond Cleavage and C-C Bond Formation? A Theoretical Study[END_REF][START_REF] Kojima | Ethereal C-O Bond Cleavage Mediated by Ni(0)-Ate Complex: A DFT Study[END_REF][START_REF] Rawat | Nickel-Catalyzed Homo-Coupling of Aryl Ethers with Magnesium Anthracene Reductant[END_REF] Nevertheless, the lack of experimental evidence, the use of a simplified chemical model and the limited speciation of both nickelate complexes and polar organometallic aggregates temper the conclusions drawn. More recently, our group has provided an in-depth experimental mechanistic study into the cross-coupling reaction between 2methoxynaphthalene and phenyl-lithium catalyzed by Ni(COD)2 (where COD = 1,5-cyclooctadiene) (Scheme 1). [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] The co-complexation of Ni(COD)2 with PhLi gives rise to two different heterobimetallic nickelates; a 1:1 species [Li(THF)2PhNi(COD)n] (where n = 1 or 2) and a 2:1 species [Li2(THF)4Ph2Ni(COD)], which were found to exist in equilibria. Stoichiometric, catalytic and kinetic studies support the involvement of these lithium nickelates in the cross-coupling reaction, but precise details on how they facilitate the C-OMe bond cleavage were still unclear. Notably, the cross-coupling reaction has a strong solvent and donor influence, suggesting that Li and Ni work cooperatively to enable the transformation under mild conditions. 15 In this work, based on calculations performed at the DFT level and by comparison with spectroscopic and kinetic data, we clarify the nature (stoichiometry and ligands) of the active lithium nickelate complexes formed under catalytic reaction conditions. The crucial role of solvent on the reaction are explained and the multiple roles played by lithium are evidenced. Further stoichiometric reactions have identified additional nickelate intermediates which offer further support for the calculated mechanism. Based on this new mechanistic knowledge, we also demonstrate how the "naphthalene problem" can be overcome to enable the cross-coupling of unbiased aryl ethers under mild conditions.

COMPUTATIONAL DETAILS

All calculations were performed at the DFT level using the Gaussian 09 (Rev D.01) suite of programs. [START_REF] Frisch | Revision D.01[END_REF] The speciation of PhLi(THF)n and Ni(COD)2 in THF was first considered to benchmark the computational method and to define the reference state of the catalytic system (see the SI for further details). Structure of minima and transition states were fully optimized using the M06 DFT functional, [START_REF] Zhao | The M06 Suite of Density Functionals for Main Group Thermochemistry, Thermochemical Kinetics, Noncovalent Interactions, Excited States, and Transition Elements: Two New Functionals and Systematic Testing of Four M06-Class Functionals and 12 Other Function[END_REF] this functional shows good performance to predict the structure and energy of organonickel complexes. [START_REF] Sperger | Computational Studies of Synthetically Relevant Homogenous Organometallic Catalysis Involving Ni, Pd, Ir, and Rh: An Overview of Commonly Employed DFT Methods and Mechanistic Inisghts[END_REF] First to third period atoms (C, H, Li, and O) were described using the double-ζ Karlsruhe basis sets (def2-SVP). [START_REF] Weigend | Accurate Coulomb-Fitting Basis Sets for H to Rn[END_REF][START_REF] Weigend | Balanced Basis Sets of Split Valence, Triple Zeta Valence and Quadruple Zeta Valence Quality for H to Rn: Design and Assessment of Accuracy[END_REF] The fully relativistic effective-core potential (ECP10MDF) [START_REF] Dolg | Energy-adjusted Ab Initio Pseudopotentials for the First Row Transition Elements[END_REF] from the Stuttgart/Köln group and its associated basis set [START_REF] Martin | Correlation Consistent Valence Basis Sets for Use with the Stuttgart-Dresden-Bonn Relativistic Effective Core Potentials: The Atoms Ga-Kr and In-Xe[END_REF] was used to describe Ni. Bulk solvent effects were represented using the SMD implicit solvent model as implemented in Gaussian. [START_REF] Marenich | Universal Solvation Model Based on Solute Electron Density and on a Continuum Model of the Solvent Defined by the Bulk Dielectric Constant and Atomic Surface Tensions[END_REF] The default cavity parameters, static and optical dielectric constants for THF and benzene were used. The impact of explicit THF coordination to Li was investigated using a microsolvation approach. The nature of optimized stationary points was checked by analytical frequency calculations. Transition state (TS) connectivity was confirmed by following the intrinsic reaction coordinate (IRC) in both directions. Harmonic frequencies were computed to estimate Gibbs energies at 298 K under 1 atm pressure using the usual harmonic approximation. [START_REF] Zarate | Phenol Derivatives: Modern Electrophiles in Cross-Coupling Reactions[END_REF] H NMR shielding of optimized lithium nickelate complexes were computed at the DFT level, [START_REF] Schreckenbach | Density Functional Calculations of NMR Chemical Shifts and ESR G-Tensors[END_REF] using the Gauge-Independent Atomic Orbital (GIAO) method. [START_REF] London | Théorie Quantique Des Courants Interatomiques Dans Les Combinaisons Aromatiques[END_REF][START_REF] Mcweeny | Perturbation Theory for the Fock-Dirac Density Matrix[END_REF][START_REF] Ditchfield | Self-Consistent Perturbation Theory Diamagnetism I. A Gauge-Invariant LCAO Method for N.M.R. Chemical Shifts[END_REF][START_REF] Wolinski | Efficient Implementation of the Gauge-Independent Atomic Orbital Method for NMR Chemical Shift Calculations[END_REF][START_REF] Cheeseman | A Comparison of Models for Calculating Nuclear Magnetic Resonance Shielding Tensors[END_REF] For these calculations, EPR-III basis sets [START_REF] Barone | Structure, Magnetic Properties and Reactivities of Open-Shell Species From Density Functional and Self-Consistent Hybrid Methods[END_REF] were used for H atoms to better describe the electronic density around the nuclear region. Micro-kinetics integrations were performed using the COPASI software. [START_REF] Hoops | COPASI -A COmplex PAthway SImulator[END_REF] Initial species concentrations were defined accordingly to the experimental conditions (see Figure S26). To simulate equilibria between intermediates, fast reactions were inferred, based on the computed equilibria constant K = exp(-∆rG/RT) = k1/k-1. Kinetic constants k1 and k-1 have been chosen large enough to account for a fast reaction, and to fit with the thermodynamics of the equilibria. Natural Population Analysis (NPA) was performed within Gaussian 09 calling the NBO 6 code. [START_REF] Glendening | NBO 6.0[END_REF] The Electron Localized Function (ELF) and condensed DFT functions analyses were performed using the Multiwfn package. [START_REF] Lu | A Multifunctional Wavefunction Analyzer[END_REF] Standard state correction on going from the gas phase standard state (1 atm) to the more relevant solute state (1 mol L -1 ) was applied. This rG1atm to rG1M correction is of 1.89 kcal mol -1 for an associative pathway (r = -1). [START_REF] Kelly | Aqueous Solvation Free Energies of Ions and Ion-Water Clusters Based on an Accurate Value for the Absolute Aqueous Solvation Free Energy of the Proton[END_REF] Finally, structures optimized in benzene are tagged X, whereas structures computed in THF are tagged X'. Covalent bonds are indicated with plain lines, non-covalent bonds are indicated by hashed lines and bond formed or broken during transition states are indicated by bolded hashed lines.

RESULTS AND DISCUSSION

Speciation of Lithium Nickelates in THF solution.

As evidenced by [START_REF] Zarate | Phenol Derivatives: Modern Electrophiles in Cross-Coupling Reactions[END_REF] H NMR spectroscopy, the addition of 1 equivalent of PhLi to Ni(COD)2 in THF leads to the formation of two lithium nickelate complexes that are in equilibrium. These species have been experimentally attributed to [Li2(THF)4Ph2Ni(COD)] and [Li(THF)2PhNi(COD)], and it has been observed that their relative proportion depends on the total concentration of the solution. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] Computationally, lithium nickelate complexes potentially formed upon successive addition of PhLi to Ni(COD)2 (1') and COD dissociations were optimized at the DFT level. Their stability was assessed relative to separated Ni(COD)2 (1') and [PhLi(THF)2]2 used as reference states. As shown in Figure 1, COD dissociation from Ni(COD)2 (1') to form [Ni(COD)] (2') is endergonic by 34.2 kcal mol -1 and thus thermodynamically unfeasible. Conversely, the co-complexation of [PhLi(THF)2]2 with Ni(COD)2 (1') to form the mono-nickelate complex [PhLi2(THF)4PhNi(COD)2] (3') is computed exergonic by 1.1 kcal mol -1 . Dissociation of one COD from 3' leads to the formation of the di-nickelate complex [Li2(THF)4Ph2Ni(COD)] (4') in which Ni 0 is directly bonded to two Ph groups. Relative to 1' and [PhLi(THF)2]2, the formation of 4' is computed exergonic by 13.3 kcal mol -1 , in agreement with the experimental isolation and characterization of this complex. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] The release of one [PhLi(THF)2] unit from 3' to yield [Li(THF)2PhNi(COD)2] (5') is also computed thermodynamically favorable (-2.8 kcal mol -1 ) but to a lesser extent than the release of COD. Starting from 5', further dissociation of one COD to yield complex [Li(THF)2PhNi(COD)] (6') is endergonic by 14.0 kcal mol -1 and is thus unlikely, although its formation was previously inferred experimentally based on estimated molecular weights determined by 1 H DOSY NMR spectroscopy. 15 Based on this apparent contradiction, additional computational speciation of the structures of mono-nickelate complexes formed in THF solution combined with DFT 1 H NMR calculations and proportioning simulations were performed. As shown in Tables S1a-d, calculated 1 H NMR chemical shifts of [Li2(THF)4Ph2Ni(COD)] (4') and [Li(THF)2PhNi(COD)2] (5') fit well with experimental ones. This suggests that complexes 4' and 5' are the species formed under experimental conditions. This is further supported by the simulation of the relative proportions of nickel complexes for equimolar solutions of Ni(COD)2 and PhLi(THF)2 at various total concentrations (Figure S1a).

Oxidative addition of Lithium Nickelates in THF solution.

The activity of complexes [Li2(THF)4Ph2Ni(COD)] (4') and [Li(THF)2PhNi(COD)2] (5') towards oxidative addition of 2methoxynaphthalene in THF solution was then computationally investigated. As shown in Figures S2-S3, the energy barriers are too high and thus account for the lack of reactivity observed experimentally in THF solution at ambient temperature (31.7 kcal mol -1 for complex 4' and 47.7 kcal mol -1 for complex 5'). It should be noted however that the competing ortho-lithiation of 2-methoxynaphthalene by PhLi also occurs in THF solution or when using low-aggregated PhLi dimers or monomers, even in the absence of Ni. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] Nevertheless, stoichiometric reactions between 4' and 2-methoxynaphthalene shows that the rate of the oxidative addition and cross-coupling is heavily dependent on the nature of the Li-donor ligand: slower reaction rates were observed for stronger donors. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] Speciation of Lithium Nickelates in benzene solution. The speciation of lithium nickelates was broadened to the case of "PhLi(THF)" in benzene solution (Figure 2a). The Gibbs energy of the resulting heterobimetallic nickelate complexes was computed relative to separated Ni(COD)2 (1) and [PhLi(THF)]2 in benzene, in the absence of additional free THF. Compared to the speciation performed in THF solution (see Figure 1), in benzene and in the presence of only one THF per lithium center, similar nickelate complexes (3 to 5) are formed but the span of their Gibbs energies is significantly narrowed. Co-complexation of [PhLi(THF)]2 with Ni(COD)2 to yield [PhLi2(THF)2PhNi(COD)2] (3) is computed exergonic by 3.5 kcal mol -1 (Figure 2a). In contrast with the THF solution case, the formation of [{Li(THF)PhNi(COD)2] ( 5) is endergonic by 4.5 kcal mol -1 . In benzene solution, the dissociation of COD from 3 to yield [Li2(THF)2Ph2Ni(COD)] ( 4) is still exergonic but only by 1.2 kcal mol -1 , a lesser extent than in THF solution.

Since the Gibbs energies of [PhLi2(THF)2PhNi(COD)2] (3) and [Li2(THF)2Ph2Ni(COD)] (4) are close, they both likely coexist in equilibria at ambient temperature. THF exchange from the Li centers of [PhLi(THF)]2 to those of 4 has also been considered. In this case, the formation of the di-solvated 2:1 lithium nickelate 4a is thermoneutral relative to 4 (Figure 2a).

Oxidative addition of Lithium Nickelates in benzene solution.

Starting from [Li2(THF)2Ph2Ni(COD)] (4), and compared to the oxidative addition pathway involving [Ni(COD)] (Figure S4), the overall Gibbs energy barrier for the oxidative addition mediated by [Li2(THF)2Ph2Ni(COD)] ( 4) is decreased by 11 kcal mol -1 (Figure S4). This decrease in energy barrier is enabled by Li + that promotes the binding of 2-methoxynaphthalene to the nickelate complex, and by the second "ancillary" Ph substituent that favors the displacement of COD. However, the oxidative addition energy barrier via this pathway remains too high to account for the reactivity observed experimentally (+35.8 kcal mol -1 , Figure 2 and TS3 in Figure S4). This high energy barrier most likely results from the transfer of the electronic density from the Ph groups to the COD instead of the σ*-C-O antibonding orbital. In this interaction scheme, the Ni center acts as an electron density shuttle as supported by the NBO charge analysis displayed in Figure S5. The lower energy barrier computed for the oxidative addition of the Caryl-OMe bond to complex [Li2(THF)2Ph2Ni(COD)] (4) mainly originates from a facilitated release of COD that in turn reduces the endergonicity of 2-methoxynaphthalene coordination without modifying the oxidative addition step. Based on this observation, we assessed the influence of the de-coordination of the second COD on the oxidative addition barrier. In the absence of 2-methoxynaphthalene, the dissociation of the second COD from [Li2(THF)2Ph2Ni(COD)] ( 4) is computed endergonic by 18 kcal mol -1 (Figure S6). However, in the presence of 2-methoxynaphthalene, the formation of a nickelate adduct in which both COD ligands are dissociated is thermodynamically accessible. Indeed, COD dissociation starting from 13) is only endergonic by 4.8 kcal mol -1 (Figure 2a-b). Interestingly, relative to complex 4, adduct 13 has an improved ability to perform the oxidative addition as indicated by a computed overall energy barrier of 19.5 kcal mol -1 , which is ca. 16 kcal mol -1 less than for the pathway in which one COD remains bonded Ni 0 such as in complex [Li2(THF)2Ph2Ni(COD)] (4) (Figures 2b, S4 andS7). In the produced [Li2(THF)2(OMe)Ph2Ni(Naph)] ( 14), the methoxy group is bonded to the Li centers, and not interacting with Ni, so that the reaction can be viewed as a σ-bond metathesis rather than an oxidative addition. [START_REF] Altus | The Continuum of Carbon-Hydrogen (C-H) Activation Mechanisms and Terminology[END_REF][START_REF] Perutz | Metathesis by Partner Interchange in σ-Bond Ligands: Expanding Applications of the σ-CAM Mechanism[END_REF] To summarize this section, the rate determining step of the cross-coupling reaction is the oxidative addition of 2-methoxynaphthalene to the ate-complex [Li2(THF)2Ph2Ni(COD)] (4) via the di-nickelate complex [Li2(THF)2Ph2Ni(η 2 -NaphOMe)] (13). Coordination of PhLi(THF) and 2-methoxynaphthalene to Ni 0 promotes the consecutive dissociation of two COD ligands. PhLi(THF) facilitates oxidative addition by improving the electron donating ability of Ni 0 whilst Li acts as a Lewis acid to coordinate and prime the oxidative addition of the Caryl-OMe bond of 2-methoxynaphthalene. This demonstrates that Ni and Li truly work cooperatively to enable this challenging catalytic transformation under mild reaction conditions. Possible Involvement of LiOMe. Our previously reported monitoring of the cross-coupling reaction between 2-methoxynaphthalene and PhLi catalyzed by Ni(COD)2 in benzene shows three apparent stages with different reaction rates (Figure S9). [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] The first one can be seen as an induction period, the second one is the fastest, and the third one indicates a possible deactivation of the system. To account for this phenomenon, the influence of a potential Li-based by-product [PhLi•LiOMe(THF)2]2, which results from the aggregation of MeOLi and PhLi, on the reactivity was assessed computationally. In the presence of [PhLi•LiOMe(THF)2]2 release of COD and binding of 2-methoxynaphthalene to yield complex 17 is almost thermoneutral (Figure 3, see Figure S10 for possible intermediates). From 17, the oxidative addition step requires to overcome a Gibbs energy barrier of 14.5 kcal mol -1 to proceed (Figure 3). This barrier is almost equal to the one previously commented in the absence of LiOMe (14.7 kcal mol -1 , Figures 2b andS7). NBO charge analysis reveals that, in the absence or presence of LiOMe, the 2-methoxynaphthalene adduct and transition state of oxidative addition share very similar charge distribution as illustrated in Figure S11. Relative to the most stable dormant complex 9 and in the presence of LiOMe, oxidative addition of 2-methoxynaphthalene proceeds via TS5 (Figure 3) with an overall Gibbs energy barrier of 16.3 kcal mol -1 , i.e. 3.2 kcal mol -1 less than the one computed in absence of LiOMe via TS4 (Figure 2b). This reactivity trend jointly results from an easier coordination of 2-methoxynaphthalene and an easier decoordination of COD in presence of lithium methoxide. The enhanced catalytic activity that is characteristic of the second stage of the kinetic profile is therefore proposed to result from the non-innocent behavior of Li-OMe that is concomitantly produced by the reaction. Finally, the reaction slowing down could be due to PhLi deactivation during the reaction. For instance, due to the co-precipitation of PhLi with MeOLi in stable adducts such as [PhLi2OMe(THF)2]2. Experimentally however, attempts to confirm or rule out the involvement of LiOMe or mixed aggregates were inconclusive, likely due to the insolubility of LiOMe in THF or benzene (see SI for full details). Isolation of Identified Intermediates. With several potential intermediates identified by the computational studies, we next set out to experimentally validate some of these species. We have previously demonstrated that the treatment of in situ generated Li2(solv)4Ph2Ni(COD) (4) with 2-methoxynaphthalene leads to cross-coupling and clean regeneration of Ni(COD)2 (1). [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] Whilst the rate of the coupling reaction was found to depend on the identity of the donor or solvent, which supports the initial coordination of the substrate to Li + , no intermediates could be isolated or spectroscopically observed. We therefore turned to Ni(ttt-CDT) (where CDT = 1,5,9-cyclododecatriene) as an alternative Ni 0 source, since the ttt-CDT olefin is known to be more labile when compared to COD. [START_REF] Bogdanović | Olefin Complexes of Nickel(0)[END_REF][START_REF] Jonas | Alkali Metal-Transition Metal π-Complexes[END_REF] Treatment of Ni(ttt-CDT) with 3 equivalents of PhLi and 1 equivalent of 2-methoxynaphthalene at -30 °C afforded yellow crystals, which were identified as the oxidative addition product [Li2(THF)4Ph3Ni(Naph)] (19a) by single-crystal X-ray diffraction (Figure 4a). This compound forms regardless of PhLi stoichiometry, indicating that its formation is favorable over a lower order (i.e. 1:1 Li/Ni II ratio) species. Since the C-OMe bond cleavage and oxidative addition occurs readily even at low temperatures, we turned to naphthalene as an inert substitute to seek the η 2 -coordination proposed in intermediate 13. Gratifyingly, treatment of Ni(ttt-CDT) with 2 equivalents of PhLi and 1 equivalent of naphthalene at -30 °C in the presence of TMEDA (where TMEDA = N,N,N',N'-tetramethylethylenediamine) afforded deep red crystals of the target complex Li2(TMEDA)2Ph2Ni(η 2 -naphthalene) (13.Naph, Figure 4b). In compound 19a, the Ni II center adopts a square planar geometry (Figure 4c) and shows similar structural features to the homoleptic analogue, Li2(THF)4Ph4Ni. [START_REF] Lamm | Binuclear Oxalamidinate Complexes (MePd)2(Oxam) and Homoleptic Complexes of the Type [(THF)nLi4(Me8)M2] and[END_REF] In compound 13.Naph, the Ni 0 center adopts a pseudo-trigonal planar confirmation (Figure 4d) and shows similar structural features to the previously characterized Li2(solv)nPh2Ni(COD) complexes. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] A comparison of the structural and spectroscopic features of 13.Naph with {Cy2PC3H6PCy2}Ni(η 2 -naphthalene) [START_REF] D'accriscio | Dcpp)Ni(η 2 -Arene)] Precursors: Synthesis, Reactivity, and Catalytic Application to the Suzuki-Miyaura Reaction[END_REF] illustrate the high σ-donating ability of the phenyl-carbanion ligands when compared to typically employed neutral phosphine or Nheterocyclic carbene ligands. For example, in the 1 H NMR spectrum, {Cy2PC3H6PCy2}Ni(η 2 -naphthalene) displays a broad singlet at δ 5.75 for the coordinated naphthalene ring, [START_REF] D'accriscio | Dcpp)Ni(η 2 -Arene)] Precursors: Synthesis, Reactivity, and Catalytic Application to the Suzuki-Miyaura Reaction[END_REF] whilst compound 13.Naph displays two well-resolved multiplets at δ 4.96 and δ 4.26 (in C6D6) or δ 4.24 and δ 4.09 (in THF-d8). Similarly, the C1=C2 distance in {Cy2PC3H6PCy2}Ni(η 2naphthalene) is 1.435(3) Å, [START_REF] D'accriscio | Dcpp)Ni(η 2 -Arene)] Precursors: Synthesis, Reactivity, and Catalytic Application to the Suzuki-Miyaura Reaction[END_REF] S22-S25) and reveals that these three analogs contribute to the overall activity and the formation of both heteroand homo-coupling products that are respectively identified in 58%, 15% and 15% yield. Experimentally, the reductive elimination from Li2(THF)4Ph3Ni(Naph) (19a) can be followed by [START_REF] Zarate | Phenol Derivatives: Modern Electrophiles in Cross-Coupling Reactions[END_REF] H NMR spectroscopy and occurs readily in the presence of COD (2 equivalents) to give Li2(THF)4Ph2Ni(COD) (4') with selective formation of 2-phenylnaphthalene [71% GC yield; biphenyl (9%); 2,2'-binaphthyl (2%); naphthalene (5%); To complement, as we have shown experimentally that the selectivity of the reaction depends on the availability of [PhLi(THF)]2, we have also investigated the reactivity of complex [Li2(THF)2Ph2Ni(Naph)(OMe)] ( 14) that is the resting state of the catalyst when the concentration of [PhLi(THF)]2 is low. In this case, the lowest energy profile leads to the formation of biphenyl via TS11 over the formation of the crosscoupling product (Figure S17). To summarize this mechanistic section, three complexes that can be formulated as [NaphOMe•Li2(THF)2(R)(R')Ni(COD) where R, R' = Ph, Naph] all contribute to the catalytic activity with slightly different selectivities between homo-and crosscoupling products. The role played by [Li2(THF)2Ph2Ni(Naph)(OMe)] in modifying the selectivity of the reaction depending on the concentration of PhLi, especially at the end the reaction, has also been highlighted.

[NaphOMe•Li2(THF)2Ph2Ni(COD)] (9) to yield [Li2(THF)2Ph2Ni(η 2 -NaphOMe)] (

Revised Catalytic Cycle(s).

The set of energy profiles computed for the Ni-catalyzed cross-coupling under study suggests an interesting mechanistic scenario that differs from previously reported pathways [START_REF] Borys | Mechanisms of the Nickel-Catalysed Hydrogenolysis and Cross-Coupling of Aryl Ethers[END_REF][START_REF] Ogawa | How and Why Does Ni 0 Promote Smooth Etheric C-O Bond Cleavage and C-C Bond Formation? A Theoretical Study[END_REF][START_REF] Kojima | Ethereal C-O Bond Cleavage Mediated by Ni(0)-Ate Complex: A DFT Study[END_REF] and that is summarized in Figures 7a andS15. It involves six key steps: (i) Nickelate formation (1 → 4) through the complexation of two "ancillary" Ph groups to promote the release of one COD from Ni(COD)2 and to enhance the electron donating ability of Ni 0 ; (ii) Li binding (4 → 9) of 2-methoxynaphthalene due to its Lewis acidic character which is key to facilitate the next step; (iii) π-arene coordination to Ni (9 → 13) that favors the release of the second COD and enables the transfer of charge density from [Li2Ph2Ni] moiety to the naphthyl substrate; (iv) Rate determining oxidative addition of the C-OMe bond (13 → 14) with transfer of the methoxy group to Li; (v) LiOMe-PhLi exchange (14 → 19) experimentally supported by the isolation of 19a; (vi) Reductive eliminations (19 → 4) to selectively yield the cross-coupling product 2-phenylnaphthalane and to regenerate Ni 0 -ate complex 4. To confidently support this overall mechanistic picture, we have solved the set of kinetic equationsby means of a microkinetic model considering the initial experimental concentrations to simulate catalytic activity curves over time. As mentioned above, the three nickelate complexes that feature all combinations of Ph and Naph groups are contributing to the overall selectivity and activity of the reaction and were thus included in kinetics simulations. Overall, a remarkable agreement between experimental and simulated kinetic results is obtained. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] When only cycle (a) "without involvement of LiOMe" (Figures S15, S22, S25, S26) was considered, the apparent zeroth order with respect with PhLi was successfully reproduced (Figure S27a) but the conversion of the substrate was limited relative to the experimental one. Adjunction to cycle (a) of cycle (b) "with the joint involvement of [PhLi•LiOMe(THF)2]2 and PhLi" allowed to finely represent, in addition, the short induction period and the subsequent acceleration of the rate of the reaction but though increased, the final simulated conversion remained low relative to the experimental one (Figure S27b). Finally, the combination of cycles (a), (b) and (c) "with involvement of [PhLi•LiOMe(THF)2]2 only" (Figures 7c andS27) afforded an almost ideal simulation of the experimental kinetic profile (Figure 7b). Unlocking the "Naphthalene Problem". With this mechanistic knowledge in hand, we next sought to use these insights to try and overcome a current challenge in Ni-catalysis, the so-called "naphthalene problem". [START_REF] Borys | Mechanisms of the Nickel-Catalysed Hydrogenolysis and Cross-Coupling of Aryl Ethers[END_REF] This phenomenon generally restricts the electrophilic coupling partner to π-extended systems, such as 2-methoxynaphthalene, meaning that C-C cross-couplings of unbiased aryl ethers such as anisole itself is rare. [START_REF] Dankwardt | Nickel-Catalyzed Cross-Coupling of Aryl Grignard Reagents with Aromatic Alkyl Ethers: An Efficient Synthesis of Unsymmetrical Biaryls[END_REF][START_REF] Xie | Cross-Coupling of Aryl/Alkenyl Ethers with Aryl Grignard Reagents through Nickel-Catalyzed C-O Activation[END_REF][START_REF] Iglesias | Kumada-Tamao-Corriu Coupling of Heteroaromatic Chlorides and Aryl Ethers Catalyzed by (IPr)Ni(Allyl)Cl[END_REF] Computationally, the oxidative addition of anisole to Ni 0 -ate complex 4 accordingly to a mechanism analogous to the one computed for 2-methoxynaphthalene in the presence of [PhLi(THF)]2 in benzene was assessed. In this case, a Gibbs energy barrier of 26.4 kcal mol -1 was computed for the Caryl-OMe oxidative addition (Figure S28). This trend agrees with the expected lower reactivity of non π-extended derivatives compared to the naphthyl-derived system, but this value remains too high to account for a feasible transformation at room temperature. In the absence of any coordinating THF however, the addition of one more equivalent of [PhLi]2 to complex 1 to yield the higher-order lithium nickelate complex [Li4Ph4Ni(COD)] (62) is exergonic by 19.8 kcal mol -1 (Figures 8 andS29). Notably, we have previously demonstrated that the further co-complexation of additional molecules of organolithium (which are not directly coordinated to Ni 0 ) has been shown to be possible for several lithium nickelates, particularly in weakly coordinated solvent systems. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF][START_REF] Somerville | Unmasking the Constitution and Bonding of the Proposed Lithium Nickelate "Li3NiPh3(Solv)3": Revealing the Hidden C6H4 Ligand[END_REF][START_REF] Borys | Towards Hexagonal Planar Nickel: A Dispersion-Stabilised Tri-Lithium Nickelate[END_REF][START_REF] Borys | Organolithium Aggregation as a Blueprint to Construct Polynuclear Lithium Nickelate Clusters[END_REF][START_REF] Borys | New Frontiers in Alkali-Metal Nickelates[END_REF] From complex 62, oxidative addition of anisole proceeds after COD release with an overall Gibbs energy barrier of 16.5 kcal mol -1 (Figures 8 andS31). This suggests that anisole activation can occur under THF-free conditions. Experimentally, the cross-coupling reaction between anisole and PhLi catalyzed by Ni(COD)2 was enabled simply by using the aryl ether substrate in a sufficient excess in pure benzene (Figure 9a). This has two consequences: (i) it enables the solubilization of PhLi and any lithium nickelate intermediates; and (ii) promotes the dissociation of COD through η 2 -arene coordination of anisole, as identified computationally and confirmed experimentally. The solubility of PhLi and the rate of the cross-coupling reaction was monitored with 0.5 to 8 equivalents of anisole. Complete solubility of PhLi requires 7 to 8 equivalents of anisole (Figure S45), whilst the optimal cross-coupling rates are observed with 2 to 3 equivalents of anisole (Figure S47). Regardless of the experimental conditions however (equivalents of PhOMe, catalyst loading, reaction time), the yield of biphenyl never exceeded ~60% with respect to PhLi. This may be attributed to co-precipitation of PhLi with the LiOMe by-product, or due to the observation that multiple equivalents of PhLi co-complex per Ni center to form the active lithium nickelate intermediates (see Figure 8). (64-i) are all similar (see also Figure S29 for additional structures), suggesting that they likely coexist in solution at ambient temperature. The calculated 1 H NMR spectrum of complex 64i however was found to match well with the detected signals (Table S2). Spectroscopic monitoring of the reaction over 60 minutes shows the clean formation of biphenyl (60% yield after 1 hour) with concomitant consumption of PhLi and the proposed lithium nickelate intermediate (64-i), along with the partial regeneration of Ni(COD)2 (Figures 9b-c). Experimental kinetic studies indicate that the reaction is firstorder in catalyst concentration (Figure S48-50), as previously observed for the 2-methoxynaphthalene/PhLi/Ni(COD)2 catalytic system. [START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] An apparent zeroth-order with respect to PhLi and PhOMe is observed consistent with the fast formation of detected intermediate (64-i) and the subsequent rate determining oxidative addition (Figure S39). Worthy of note, the addition of another equivalent of PhLi to the reaction mixture after 9c-d). This suggests that the overall Gibbs energy barrier for oxidative addition can be slightly underestimated but additional solubility/physico-chemical issuesthat are not modelledcan also contribute to the time scale description in kinetic profiles.

CONCLUSIONS

By combining detailed theoretical calculations with spectroscopic and kinetic investigations, together with the isolation of key organometallic intermediates, new mechanistic insights have been provided in the Ni-catalyzed cross-coupling reaction of phenyl-lithium and aromatic ethers using Ni(COD)2. Underpinned by bimetallic cooperativity, these reactions involve the formation of highly reactive lithium nickelates. A six-step reaction mechanism is proposed in which each metal plays a pivotal role. Using 2-methoxynaphthalene as a model substrate; initially two equivalents of PhLi undergo co-complexation with Ni(COD)2 to form an electron rich lithium nickelate [Li2(THF)2Ph2Ni(COD)] (4) with the release of one equivalent of COD (step 1) to which the aromatic ether can coordinate via Li•••O interaction (step 2) which facilitates the displacement of the remaining COD ligand through -coordination of the naphthyl ring to Ni (step 3). This coordination enables the efficient charge transfer from the nickelate to the substrate which is required to promote the oxidative cleavage of the Caryl-OMe bond which is the rate determining step, with concomitant formation of LiOMe (step 4). Exchange of co-complexed LiOMe with PhLi (step 5), followed by reductive elimination (step 6) furnishes the cross-coupled product 2-phenylnaphthalane and regenerates the lithium Ni 0 -ate complex. This mechanistic proposal not only provides a rational for the dramatic solvent effects previously noted for this reaction but also uncovers the multiple roles of lithium in facilitating this Ni-catalyzed process. Furthermore, building on this knowledge, the well-known "naphthalene problem" for these reactions can be addressed, as demonstrated when using anisole as a crosscoupling partner.

Scheme 1 .

 1 Scheme 1. a) Cross-coupling reaction between 2-methoxynaphthalene and PhLi catalyzed by Ni(COD)2. b) Influence of solvent on the yield of 2-phenylnaphthalene. c) Identified lithium nickelates derived from Ni(COD)2 and PhLi.

Figure 1 .

 1 Figure 1. Structures and Gibbs energy (enthalpy) of lithium nickelates potentially formed upon addition of PhLi to Ni(COD)2 (1') in THF. Energies are given in kcal mol -1 and are relative to separated Ni(COD)2 (1') and [PhLi(THF)2]2.

Figure 2 .

 2 Figure 2. a) Structures and Gibbs energy (enthalpy) of the lithium nickelate complexes potentially formed under addition of PhLi(THF) to Ni(COD)2 (1) in benzene. Energies are given with respect to Ni(COD)2 (1) and [PhLi(THF)]2. The coordination of 2-methoxynaphthalene (NaphOMe) to complex (4) is favored and prompts the release of the second COD to form [Li2(THF)2Ph2Ni(NaphOMe)] (13). b) Reaction pathway for the second COD release (TS2) and subsequent oxidative addition (TS4) in benzene. Energies are given in kcal mol -1 (see FigureS4for alternative pathways).In terms of electronic properties, the activation of the Caryl-OMe bond by Ni 0 is facilitated by the increased donation ability of the [Li2Ph2Ni 0 ]-ate-moiety to 2-methoxynaphthalene as indicated by the augmentation of the negative NPA charge of the 2methoxynaphthalene group upon COD release [(-0.87 |e -| vs. 0.03 |e -|), see FigureS8]. This effect is also visible in the geometry of TS4. The Caryl-OMe bond length increases from 1.78 Å to 1.84 Å relative to TS3 (Figure2b). Once again, as in the case of [Li2(THF)2Ph2Ni(COD)] (4, see above), Ni is acting as an electron density shuttle between the Ph groups and the naphthalene moiety with little charge variation on the Ni itself (Fig-ure S5).To summarize this section, the rate determining step of the cross-coupling reaction is the oxidative addition of 2-methoxynaphthalene to the ate-complex [Li2(THF)2Ph2Ni(COD)] (4) via the di-nickelate complex [Li2(THF)2Ph2Ni(η 2 -NaphOMe)] (13). Coordination of PhLi(THF) and 2-methoxynaphthalene to Ni 0 promotes the consecutive dissociation of two COD ligands. PhLi(THF) facilitates oxidative addition by improving the electron donating ability of Ni 0 whilst Li acts as a Lewis acid to coordinate and prime the oxidative addition of the Caryl-OMe bond of 2-methoxynaphthalene. This demonstrates that Ni and Li truly work cooperatively to enable this challenging catalytic transformation under mild reaction conditions. Possible Involvement of LiOMe. Our previously reported monitoring of the cross-coupling reaction between 2-methoxynaphthalene and PhLi catalyzed by Ni(COD)2 in benzene shows three apparent stages with different reaction rates (FigureS9).[START_REF] Borys | The Anionic Pathway in the Nickel-Catalysed Cross-Coupling of Aryl Ethers[END_REF] The first one can be seen as an induction period, the second one is the fastest, and the third one indicates a possible deactivation of the system. To account for this phenomenon, the influence of a potential Li-based by-product [PhLi•LiOMe(THF)2]2, which results from the aggregation of MeOLi and PhLi, on the reactivity was assessed computationally.

Figure 3 .

 3 Figure 3. Structures and Gibbs energy (enthalpy) of the reaction pathway for the oxidative addition of 2-methoxynaphthalene to lithium nickelates under the co-existence of [PhLi•LiOMe(THF)2]2 and [PhLi(THF)]2 in benzene. The most stable adduct 9 was used as an energy reference. Energies are given in kcal mol -1 .

Figure 4 .

 4 Figure 4. a) Synthesis of heteroleptic oxidative addition product Li2(THF)4Ph3Ni(Naph) (19a). b) Synthesis of coordination complex Li2(TMEDA)2Ph2Ni(η 2 -naphthalene) (13.Naph). c) Molecular structure of Li2(THF)4Ph3Ni(Naph) (19a). Hydrogen atoms omitted and coordinated THF shown as wireframe for clarity. d) Molecular structure of Li2(TMEDA)2Ph2Ni(η 2 -naphthalene) (13.Naph). Hydrogen atoms omitted and coordinated TMEDA shown as wireframe for clarity.

  and 1.462(2) Å in 13.Naph. These features are indicative of significant backdonation from the electron-rich Ni 0 center into the C=C π* orbital which is elongated by 0.09 Å relative to free naphthalene [1.373(1) Å]. 41 Reductive Elimination from Nickel(II) Intermediates. Computationally, the exchange of LiOMe with PhLi to afford compound Li2(THF)2Ph3Ni(Naph) (19) is exergonic by 32.8 kcal mol -1 (Figure 5), in agreement with experimental studies. Remarkably, reductive elimination from 19 or 26 (with co-complexed LiOMe) are selective towards the formation of the crosscoupled product over the homo-coupled species (Figures 5, S14 and S16). The formation of homo-coupling products via reductive elimination from complex 19 to yield complex 25 raises the question of the catalyst regeneration. Indeed, complex 25 can undergo 2-methoxynaphthalene/COD exchange, subsequent oxidative addition, and reductive eliminations to yield 2phenylnaphthalene, biphenyl and 2,2'-binaphthyl with low selectivities (TS16 to TS18 in Figures S18-S20) as summarized in Figure S21. Interestingly, these pathways lead to the formation of complex [NaphOMe•Li2(THF)2(Naph)2Ni(COD)] (48) that only differs from complexes [NaphOMe•Li2(THF)2Ph2Ni(COD)] (9) and [NaphOMe•Li2(THF)2(Ph)(Naph)Ni(COD)] (25) by the relative proportion of Ph and Naph groups bonded to Ni. The reactivity and selectivities of 48 relative to the oxidative addition of 2-NaphOMe and subsequent reductive eliminations have also been investigated computationally. The energy profiles computed are very similar to those computed for complexes 9 and 25 (Figures

15

 15

Figure 5 .

 5 Figure 5. Structures and Gibbs energy (enthalpy) comparing the different pathways for reductive elimination and explaining the origin of selectivity between cross-coupling and homo-coupling products. Energies are given in kcal mol -1 .

Figure 6

 6

Figure 6 .

 6 Figure 6. Reductive elimination from Li2(THF)4Ph3Ni(Naph) (19a) in the presence of COD to give Li2(THF)4Ph2Ni(COD) (4'), 2-phenylnaphthalene, biphenyl and 2,2'-binaphthyl.

Figure 7 .

 7 Figure 7. a) Mechanistic proposal (Structures, Gibbs energy) for the cross-coupling reaction between 2-methoxynaphthalene (0.4 M) and phenyl-lithium (0.44 M) catalyzed by Ni(COD)2 (5 mol%) (1) in benzene. Energies [+/-] are given in kcal mol -1 with respect to [NaphOMe•Li2(THF)2Ph2Ni(COD)] (9), [PhLi(THF)]2 and [PhLi2(OMe)(THF)2]2. (+/-) is the regenerative energy of complex 1, 4 and 9. The complexes are named with black bold numbers. b) A plot of concentration (M) vs. time (seconds) for the cross-coupled product 2phenylnaphthalane and homo-coupled 2,2'binaphthyl by experimental work. c) Micro-kinetics integration obtained by stationary state simulation (see also Figures S15, S22 and S26).

Figure 8 .

 8 Figure 8. Structures and Gibbs energy (enthalpy) for the oxidative addition of anisole to lithium nickelates formed from Ni(COD)2 and [PhLi]2 in benzene. The most stable adduct 64-i was used as an energy reference. Energies are given kcal mol -1 .

Figure 9 .

 9 Figure 9. a) Ni(COD)2 catalyzed cross-coupling of anisole with PhLi. c) Experimental reaction profile showing the quantities of biphenyl, Ni(COD)2, COD, and the proposed lithium nickelate intermediate [Li4Ph4Ni(PhOMe)] (64-i) over time. d) Simulated reaction profile over time based on the steady state approximation (see Figure S34, and pathway i of Figure S36).

  The 1 H NMR spectra of the reaction with 1 equivalent of PhLi, 5 equivalents of PhOMe and 12.5 mol% of Ni(COD)2 is shown in Figure 9b. Upon addition of Ni(COD)2, a new doublet signal (J = 7.0 Hz) appears at δ 8.4 ppm which is attributed to the formation of an anisole-solvated lithium nickelate complex. The Gibbs energies of [Ph4Li4PhNi(COD)] (62), [Ph4Li4PhNi(COD)(PhOMe)] (63) and [Ph4Li4PhNi(PhOMe)]

  45 minutes appears to restart the reaction (Figures S38 and S51), illustrating the stability of the Ni-catalyst and potential deactivation of PhLi under the reaction conditions, which are likely due to solubility issues or co-complexation with the Li-OMe by-product. Further validation of this mechanistic proposal using kinetic modelling with COPASI 31 successfully reproduces the apparent zeroth-order dependance with respect to PhLi and PhOMe, intermediate concentration patterns and PhLi spiking tests (Figure S38-40). However, simulated reaction times are shorter than those determined experimentally (Figures

ACKNOWLEDGMENT

EH and AMB thank the Swiss National Science Foundation (SNF) (Project 200021_188573) and Universität Bern for their generous sponsorship of this research. H. L. thanks the Chinese Scholarship Council (CSC NO. 202009370047) for a fellowship. The authors are grateful to the CNRS, ICBMS (UMR 5246), Université Lyon 1 and the Region Auvergne Rhone Alpes for financial support. The CCIR of ICBMS, PSMN and GENCI (allocation A10, A0100812501) are acknowledged for a generous allocation of computational resources and providing technical support.

ASSOCIATED CONTENT Supporting Information

The Supporting Information is available free of charge on the ACS Publications website. Additional energy profiles, electron density analyses, experimental procedures, and spectral data are provided (pdf). Cartesian coordinates of all the optimized structures and their associated uncorrected (XYZ) and corrected (pdf) energies are provided.

AUTHOR INFORMATION Corresponding Authors

* Eva Hevia. E-mail: e.hevia@unibe.ch * Marie-Eve L. Perrin. E-mail: marie-eve.perrin@univ-lyon1.fr * Pierre-Adrien Payard. E-mail: pierre-adrien.payard@univ-lyon1.fr Author Contributions ‡ HL and AMB contributed equally to this work. Experiments were performed by AMB, computations were performed by HL. EH, PAP and MEP supervised the overall project. The manuscript was written through contributions of all authors.

ABBREVIATIONS

CDT (1,5,9-cyclododecatriene); COD (1,5-cyclooctadiene); DFT (density functional theory); DOSY (diffusion ordered spectroscopy); NBO (natural bond orbital); NMR (nuclear magnetic resonance); TMEDA (N,N,N',N'-tetramethylethylenediamine); THF (tetrahydrofuran).


Smail Ait Bouhsain

Rachid Alami

Thierry Siméon

Extending Task and Motion Planning with Feasibility Prediction: Towards Multi-Robot Manipulation Planning of Realistic Objects

The hybrid discrete/continuous nature of task and motion planning (TAMP) results often in a combinatorial explosion. This challenge is even more pronounced in multirobot TAMP problems due to the increase in dimensionality of the action space. Previous works use action feasibility prediction as a heuristic to accelerate TAMP. However, these methods are limited to box-shaped objects and specific single or dual robot settings. In this paper, we expand on our previous work on action and grasp feasibility prediction [1] by extending its use to complex-shaped objects and multi-robot systems. Also, we propose a feasibility-enabled multi-robot TAMP algorithm capable of tackling complex multi-robot manipulation problems. We demonstrate the performance of our method compared to a non feasibility-informed baseline, and show its ability to handle TAMP problems requiring the collaboration of multiple robots.

I. INTRODUCTION

Task and motion planning (TAMP, see e.g survey [START_REF] Garrett | Integrated task and motion planning[END_REF]) in robotics involves finding a sequence of steps a robot should take to achieve a goal, along with their corresponding motions. It mixes discrete symbolic planning and continuous geometric planning. This combination results in a high combinatorial complexity making the search for a geometrically feasible task plan tedious, time consuming and, in some cases, unsolvable in a reasonable amount of time. These challenges do not only come from the combinatorial complexity of the search, but also the high time cost of calling geometric planners to verify the feasibility, particularly infeasibility, of actions and plan their motions.

Recent works [START_REF] Wells | Learning feasibility for task and motion planning in tabletop environments[END_REF]- [START_REF] Yang | Sequence-based plan feasibility prediction for efficient task and motion planning[END_REF] leverage learning methods in order to tackle this shortcoming of geometric planners. They propose to learn to predict the feasibility of actions without the need for querying geometric planning. These feasibility predictions can then be used as heuristics during task and motion planning. In a previous work [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], we propose the AGFP-Net neural network, which predicts the feasibility of pick and place actions in 3D environments, as well as the feasibility of subsets of grasps. This model is integrated in a feasibility-informed TAMP algorithm which uses feasibility predictions as a heuristic to accelerate planning. The method proposed in [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] is however limited to box-shaped objects and obstacles. Also, it is limited to single-robot TAMP problems and is not able to handle multi-robot settings.

In this work, we tackle these limitations by extending the use of AGFP-Net to complex-shaped objects, allowing This work is partially supported by the EU-funded project euROBIN under grant agreement no. 101070596 (https://www.eurobin-project.eu/) efficient action and grasp feasibility predictions in realistic environments containing real-life objects. We also develop a framework for feasibility prediction in multi-robot TAMP problems, and introduce a new way of estimating the feasibility of composite actions involving more than one robot. Moreover, we propose a feasibility-informed multi-robot TAMP algorithm capable of solving single and multi-robot problems such as the ones shown in Figure 1, while taking advantage of feasibility prediction to notably accelerate the planning process.

II. RELATED WORK

A. Classical TAMP

Early TAMP research [START_REF] Alami | A geometrical approach to planning manipulation tasks. the case of discrete placements and grasps[END_REF]- [START_REF] Barry | A hierarchical approach to manipulation with diverse actions[END_REF] focused on the geometric aspect, approaching the problem as a multi-modal motion planning problem, which involves planning among multiple motion modes. Many current TAMP techniques [START_REF] Cambon | A hybrid approach to intricate motion, manipulation and task planning[END_REF]- [START_REF] Garrett | Sampling-based methods for factored task and motion planning[END_REF] integrate a task planner with a geometric planner, relying on geometric backtracking to connect the two. These approaches, nevertheless, face challenges due to the combina-torics of the hybrid discrete/continuous search. and the heavy time consumption of geometric planning, as verifying the feasibility of symbolic plans still necessitates a large number of costly calls to the geometric planner.

B. Learning for TAMP

In recent years, learning methods became increasingly popular in TAMP [START_REF] Wells | Learning feasibility for task and motion planning in tabletop environments[END_REF]- [START_REF] Yang | Sequence-based plan feasibility prediction for efficient task and motion planning[END_REF], [START_REF] Chitnis | Guided search for task and motion plans using learned heuristics[END_REF]- [START_REF] Khodeir | Learning to search in task and motion planning with streams[END_REF], [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF]. Many works aim at providing a learned heuristic to a TAMP planner, such as evaluating action affordances [START_REF] Xu | Deep affordance foresight: Planning through what can be done in the future[END_REF], leveraging experience to propose promising actions [START_REF] Kim | Learning to guide task and motion planning using score-space representation[END_REF], [START_REF] Kim | Learning value functions with relational state representations for guiding task-and-motion planning[END_REF], or providing fast geometric feedback to the task planner thanks to action feasibility prediction [START_REF] Wells | Learning feasibility for task and motion planning in tabletop environments[END_REF]- [START_REF] Yang | Sequence-based plan feasibility prediction for efficient task and motion planning[END_REF]. These methods are however limited to tabletop environments. In [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], [START_REF] Ait Bouhsain | Learning to predict action feasibility for task and motion planning in 3d environments[END_REF], we propose a learning approach for predicting action and grasp feasibility in 3D environments. As most feasibility prediction methods, ours is limited to box-shaped objects. Wells et al. [START_REF] Wells | Learning feasibility for task and motion planning in tabletop environments[END_REF] propose to use SVMs to predict the feasibility of pick and place actions on complex-shaped objects. These objects are represented using hand-designed features, which makes the generalizability to various shapes difficult. Park et al. [START_REF] Park | Scalable learned geometric feasibility for cooperative grasp and motion planning[END_REF] propose a neural network for predicting the feasibility of grasp modes in scenes containing one complex-shaped object and a number of obstacles. However, this method is object-centric, meaning that the proposed model needs to be retrained for each new object shape. In this paper, we extend our action and grasp type feasibility prediction neural network [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] to complexshaped objects, while maintaining generalizability to 3D environments containing multiple objects of various shapes.

C. Multi-Robot TAMP

Multi-robot TAMP suffers from a higher combinatorial complexity due to the increased number of robots, and thus the increased dimensionality of the action space [START_REF] Antonyshyn | Multiple mobile robot task and motion planning: A survey[END_REF]. Previous works [START_REF] Cambon | A hybrid approach to intricate motion, manipulation and task planning[END_REF], [START_REF] Umay | An integrated task and motion planning technique for multi-robot-systems[END_REF]- [START_REF] Motes | Hypergraph-based multi-robot task and motion planning[END_REF] propose various approaches for task and motion planning in multi-robot settings such as graph-based and MDP-based techniques. These methods suffer however from a combinatorial explosion as the number of robots increases, resulting in a notable increase in the already high number of calls to the geometric planner. Also, in most multi-robot TAMP research, the focus is on coordinated motion planning (e.g handover tasks). In this paper, we propose to accelerate multi-robot TAMP using robot-centric feasibility predictions, allowing the planner to mitigate the combinatorial explosion due to the presence of multiple robots. We focus on sequential motion planning, rather than coordinated motion planning, in which objects are passed between two robots using a pair of pick-place actions. Driess et al. [START_REF] Driess | Deep visual heuristics: Learning feasibility of mixed-integer programs for manipulation planning[END_REF], [START_REF] Driess | Deep visual reasoning: Learning to predict action sequences for task and motion planning from an initial scene image[END_REF] train a neural network to predict action feasibility on box-shaped objects in tabletop environments using two robotic arms. This learning approach is limited, nevertheless, to the multi-robot setting it is trained on, requiring a new training if the number of robots increases, or the robots' placements change. Our proposed feasibility prediction framework does not depend on these parameters, since it queries the neural network for each robot individu-ally. Park et al. [START_REF] Park | Scalable learned geometric feasibility for cooperative grasp and motion planning[END_REF] propose a similar method, but focus on environments containing one movable object only.

III. PROBLEM DESCRIPTION

We tackle manipulation problems where the goal is to rearrange a set of movable objects in a 3D environment, comprising n R robot arms with fixed bases, n ss stable support surfaces, n obs fixed obstacles and n O movable objects.

We define the state of the environment as the configuration of each robot together with the support surface and pose of all movable objects. The configuration of a robot r at state s is denoted s(r), whilst the configuration of an object O is denoted s(O). A transition between two states s and s ′ is defined as an action a which involves a specific robot r picking an object O from its configuration in s, and placing it at a new configuration q, which becomes the configuration of O in s ′ . The action a can be explicitly represented as:

a = M ove(r, O, s(O) → q) (1)
The solution to the TAMP problem is a sequence of actions τ and their corresponding motions Π, which brings the environment from the initial state s 0 to a goal state s goal . We define 3 types of actions at the symbolic level. The first is a Goal action, which moves an object to its goal state. The second is a T emp action, which places an object at a temporary placement. The third is a P ass action, which aims at placing an object inside the intersection between two robots' workspaces, so that the second robot can reach it. We consider the workspace of a robot r, denoted W (r), as a sphere centered at the first joint of the robot, with a radius equal to its reach1 .

IV. FEASIBILITY PREDICTION A. Neural Network

In [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], we propose a learning approach based on the Action and Grasp Feasibility Prediction neural NETwork (AGFP-Net). Given a representation of the current state of the environment and the object of interest, it simultaneously predicts the probability of feasibility of a P ick or P lace action, but also the feasibility of 6 grasp types. Each grasp type is a set of grasps related to the side from which the object is approached by the robot. The 3D environment is represented using 5 depth images corresponding to different views of the scene, which show all the objects in the workspace of the robot. Also, all objects poses are shown in the frame of the robot. Note that these depth images are constructed internally during planning, and are not obtained from depth cameras. The object of interest, on the hand, is represented using a mask over each depth image, showing the object only at the pose it should picked or placed at.

AGFP-Net is trained on a fully synthetic dataset, comprised of randomly generated scenes containing a single robot, 2 box-shaped objects and up the 4 support surfaces. The dimensions and poses of these objects are sampled randomly within fixed bounds. Our results in [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] show a good generalization to new environments with a higher number of objects, obstacles and support surfaces. Nonetheless, the neural network is by design limited to a single robot, and it can be used on box-shaped objects only. We refer the reader to [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] for more details.

B. Generalization to Complex-shaped Objects

In this work, we aim at generalizing AGFP-Net to objects with more complex shapes. One possibility could be to generate a new dataset with scenes containing complexshaped objects, and retrain the neural network using the newly generated dataset. However, since the scene projections are constructed internally, building depth images of mesh objects can be time consuming, which defeats the purpose of accelerating TAMP. Also, this method does not guarantee the generalizability to unseen shapes during training. Therefore, we propose to represent complex-shaped objects at the feasibility prediction level using their bounding boxes. This allows the neural network to generalize to objects with complex shapes, without the need for any additional data generation/annotation and training effort to [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], and without an overhead in inference time.

Given an environment containing mesh objects, the tested action and the object to manipulate, we generate depth images as explained in Section IV-A and [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], using the bounding box of each object. These depth images are then given as input to AGFP-Net to obtain the probability of feasibility of performing the action on the object of interest, as well as the feasibility of each one of the defined grasp types. Since these grasp types represent continuous subsets of grasps, all grasps (obtained using an off-the-shelf grasp planner or from a grasp database) can be associated with one of these grasp types using simple geometric transforms (cf. Figure 2). The action a defined in (1) can be decomposed into P ick and P lace sub-actions as follows:

a(r, O, s(O), q) = P ick(r, O, s(O)) + P lace(r, O, q) (2)
where P ick corresponds to picking object O using r from s(O), and P lace refers to placing O using robot r at q. Following [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], we define the probability of feasibility p a F of the action as:

p a F = p P ick F × p P lace F × max(p a G ) (3)
where p P ick F and p P lace F are the predicted probabilities of the P ick and P lace sub-actions respectively, and p G (a) is the vector of combined grasp type probabilities:

p a G = p P ick G ⊗ p P lace G (4)
⊗ being the element-wise product.

These probabilities of feasibility of grasp types are used in (3) to ensure that there is at least one common grasp type between the P ick and P lace actions. Additionally, during geometric planning, grasps are sorted according to the probability of feasibility of their corresponding grasp type. Motion planning is then performed on the most promising grasps first, allowing a faster planning time.

C. Generalization to Multi-Robot Settings

The design choices behind AGFP-Net [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] ensure that feasibility prediction is able to cover the whole workspace of a single robot. One important property of the model is that it is centered around the robot, meaning that it is dependent on the kinematics of the robot only, and does not depend on any other factors such as where the robot is placed in the environment. This is achieved by expressing all objects poses, fixed or movable, in the frame of the robot. Also, the scene projections are constructed such that the center of the robot's workspace is at the center of the depth images, and each projection covers the whole workspace of the robot. As a result, the scene projections only show the objects inside the robot's workspace.

These capabilities allow a smooth generalization of AGFP-Net to multi-robot problems. Indeed, the neural network can be queried for each robot individually by making sure the scene projections show the objects (or parts of objects) in the workspace of the said robot only, and that the shown poses of these objects are in the frame of the latter. Given an object pose in the world frame q O and a robot's frame transform T r , an object's pose expressed in the frame of the robot is simply q r O = T r q O . Using this approach, AGFP-Net can be used to predict feasibility for each robot to move the objects inside its own workspace.

Moreover, this method allows testing composite actions such as P ass actions. An object placed inside the intersection between two robots' workspaces would be visible in the scene projections corresponding to each robot, as shown in Figure 2. A P ass action aims at placing an object at an intersection region for another robot to manipulate. Therefore, a P ass action is feasible only if the first robot is able to pick the object from s(O) and place it at the intersection placement q, and if the second robot is able to pick it from this placement. Given a P ass action a pass (r 1 , O, s(O), q) between two robots r 1 and r 2 , we transform the pick and place poses to the frame of each robot to obtain s(O) r1 , q r1 and q r22 . Then, we compute the probability of feasibility p apass F of the P ass action between r 1 and r 2 as:

p apass F = p a F (r 1 , O, s(O) r1 , q r1 ) × p P ick F (r 2 , O, q r2 ) (5)
For actions a goal of type goal, and a temp of type T emp using a robot r:

p a goal F = p atemp F = p a F (r, O, s(O) r , q r ) (6)
We develop a TAMP algorithm which uses these probabilities of feasibility to prioritize feasible actions and speedup the search of a geometrically feasible task plan.

V. TASK AND MOTION PLANNING

We propose a feasibility-informed multi-robot TAMP algorithm capable of solving problems involving multiple robots. The main algorithm, shown in Algorithm 1, remains similar is based on a best-first tree search, where nodes represent states and edges are actions allowing transitions between states, following the definitions of Section III. A list Q of open nodes is maintained and sorted according to a defined cost. At each iteration, the node s with the minimum cost is extracted from Q and compared to the goal state s goal . If s is a goal state, we retrieve the complete task plan leading to s then query the geometric planner to check the feasibility of every action in the task plan and plan their corresponding motions. If the action sequence is feasible, then a solution was found. Otherwise, the search continues. During geometric planning, the probabilities of feasibility of grasp types for each action are given to the geometric planning to prioritize feasible grasps.

If s in not a goal state, we expand the node using the function f indChildren, shown in Algorithm 2. It first samples applicable actions at state s, by calling the function f indP ossibleActions which is detailed in Algorithm 3. For each movable object O in the environment, we find the set of robots capable of reaching O at its pose in s, using the function f indReachingRobots(s(O), E). For each robot r i in the obtained set, we generate Goal, P ass and T emp actions. In the case where O is not already at its goal pose, if s goal is reachable by r i , we sample a set of goal placements in the workspace of r i . Otherwise, if the goal pose of O is not reachable by r i , we try to generate P ass placements.

Algorithm 1 Task and motion planner

Input: E, s0, s goal ▷ Environment, Initial and goal states

1: Q ← {s0}
▷ Set of nodes to expand 2: while Solution not found do 3:

s ← argmincostQ

4:

if s ∈ s goal then 5:

[τ, Π] ← retrieveSolution(s)]
6:

if Π is feasible then

7:

return τ , Π

8:

end if

9:

else 10: We first find the set of robots that are able to reach s goal . The planner needs to figure out how to bring O to each one of these robot's workspace. In order to do that, we build a graph Γ which vertices are all the robots in the environment, and edges represent the existence of an intersections between two robots' workspaces. For each robot r g reaching s goal , we use a Breadth-First Graph Search to find all possible paths from r i to r g , and we extract the first robot from each path. These are all the robots r i can pass object O to in order to bring it closer to its goal pose. For each robot r j in the obtained set of robots, we sample a number of P ass placements at the intersection between W (r i ) and W (r j ).

Q ← Q ∪ f indChildren(s,
Finally, we sample a set of T emp placements in the workspace of r i . Then, we generate actions corresponding to each one of the Goal, P ass and T emp placements sampled 3 . Once all possible actions are found, we call predictF easibility for each action a, which queries AGFP-Net and uses (3), ( 4) and ( 5) to compute the probability of feasibility of the action and the feasibility of the grasp types. We construct a new child as the result of applying a at s, we compute its cost and add it to the list of open nodes.

We define the cost of a node as:

C T otal = C SoF ar + C T oGoal + C F easibility (7)
where C SoF ar is the number of actions in the branch leading to the node, C T oGoal is the minimum number of actions for each ri in f indReachingRobots(s(O), E) do 4:

P ← ∅ 5: if s(O) / ∈ s goal (O) then 6:
if s goal (O) is reachable by ri then 7:

P ← P ∪ sampleGoal(ri, E, s goal (O))
8:

else 9:
for rg in f indReachingRobots(s goal (O), E) do 10:

next robots ← BF S(ri, rg)

11:

for rj ∈ next robots do

12:

P ← P ∪ sampleP ass(ri, rj , E)

13:

end for

14:

end for

15:

end if

16:

end if

17:

P ← P ∪ sampleT emp(ri, E)

18:

for each q ∈ P do

19:

a ← M ove(ri, O, s(O) → q)

20:

A ← A ∪ a

21:

end for

22:

end for 23: end for 24: return A to reach the goal state, and C F easibility is the feasibility cost detailed in [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF]. In this work, C T oGoal is constructed differently compared to [1] [33] in order to tackle multirobot problems. Indeed, we take advantage of the previously constructed graph Γ to compute the shortest path length to the goal for each object using Breadth-First Graph Search.

We then sum these path lengths to obtain the minimum number of actions to reach the goal state.

VI. EXPERIMENTS A. Test TAMP problems

In order to demonstrate the performance of our TAMP algorithm, we construct multiple TAMP problems with varying challenges in single, dual and triple robot settings. Each problem contains a number of complex-shaped objects extracted from the YCB [START_REF] Calli | The ycb object and model set: Towards common benchmarks for manipulation research[END_REF] and KIT [START_REF] Kasper | The kit object models database: An object model database for object recognition, localization and manipulation in service robotics[END_REF] objects databases. Note that none of these objects nor their bounding boxes were used during the training of AGFP-Net. Since grasp planning is outside the scope of this work, we manually annotate each object with up to 200 grasps.

We modify the Access and Sort domains defined [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] to measure the performance of our generalization to mesh objects and multi-robot settings. In the Access problem shown in Figure 3a, a single robot has to access and move a meat can. The difficulty is due to a number of objects blocking access to the wanted object, which requires removing all blocking objects to access the wanted one, before returning them to their initial pose. The Sort problem, illustrated in Figure 3b is a dual-robot problem where the goal is to sort objects on two pre-occupied tables. Here, the algorithm has to find feasible sets of placements on narrow surfaces. Moreover, each robot can reach one of the tables only.

We also define TAMP problems in which the presence of multiple robots might either make the problem easier or more challenging. The dual-robot Assist problem, shown in Figure 1b, is similar to the previously defined Access problem. For one robot, the red object is not accessible due to a number of blocking objects. The second robot, however, has direct access to it. This problem aims at testing the ability of our algorithm to find the simplest solution, which involves one robot assisting the other. In the Clear problem, illustrated in Figure 1a, two large objects (in red) span over the intersection region of two robots' workspaces, rendering P ass actions infeasible. The robots have to first clear the intersection region before moving a set of objects from one table to another.

Additionally, we test our approach on two three-robot problems, each with a different setting. The first is the M iddleman problem (Figure 1c), in which three robots form a triangle such that there is an intersection between every pair of robots' workspaces. One of the intersection regions is blocked by a number of obstacles, forcing the robots to perform two P ass actions via a middleman robot to move two objects from one counter to the other. The second is the Longswap problem in which three sequential robots have to collaborate to swap the placements of 4 objects. For increased difficulty, the intersection regions between robots' workspaces are partially blocked by a set of obstacles.

B. Implementation details

We run our feasibility-informed TAMP algorithm on each one of these problems for 10 trials each, with a timeout set to 900 seconds per trial. We use Moveit! Task Constructor [START_REF] Görner | Moveit! task constructor for task-level motion planning[END_REF] for geometric planning with a BiTRRT motion planner [START_REF] Devaurs | Enhancing the transition-based rrt to deal with complex cost spaces[END_REF]. On the feasibility prediction side, we reuse the neural network weights obtained using the training approach detailed in [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF]. Experiments were conducted on an Intel i9-11950H @ 2.60GHz, with 32GB of RAM and NVIDIA RTX A3000 GPU. For comparison, we also run a baseline version our algorithm that does not leverage feasibility prediction, by setting all probabilities of feasibility to 1 during the search.

VII. RESULTS

Table I shows the averaged results obtained for each problem. Results show that our feasibility-informed TAMP algorithm is able to solve all problems with 100% success rate, compared to the non-informed algorithm which fails TABLE I: Planning performances with and without using feasibility prediction, averaged over 10 trials. Speedup is computed over all the trials by considering the timeout for failed cases and the average total planning time for successful ones. at least once, and completely fails to solve the single-robot Access, and the dual-robot Sort problems. Given the high combinatorial complexity of these problems, this outcome can be expected and shows that our proposed method is able to efficiently filter the tree search and reach a solution faster, allowing a total planning time of 76.8s for the Access problem and 81s for the Sort problem. These results are also comparable to the ones obtained in [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF], which shows that our method is able to handle complex-shaped objects and multirobot systems without hurting the planning time.

For the Assist problem, using AGFP-Net allows at least a 35 times speedup in planning time. In this problem, the noninformed planner is sensitive to the order in which objects are processed during the search. If the action moving the red object to a P ass region (using the robot with easy access to it) appears early in the search, planning time can be low. Our approach removes this sensitivity to the order of objects by prioritizing actions according to their feasibility. Results on the Clear problem, on the other hand, show a 92% reduction in planning time using feasibility prediction. This gain in performance is obtained thanks to our proposed method for evaluating the probability of P ass actions. Indeed, since the intersection region between two robots' workspaces is not fully covered by the red objects, both the P ick and the P lace actions of the passing robot might be feasible. However, taking into account the feasibility of the following P ick action using the receiving robot allows the planner to prioritize clearing the intersection region before performing P ass actions between the robots. This is demonstrated by the reduction in infeasible task plans generated. The three-robot M iddleman problem presents a similar scenario, except the objects blocking the intersection region are fixed obstacles. Also, the added robot adds to the combinatorial complexity of the problem. Results show an improvement in success rate from 30% without feasibility prediction to 100% using AGFP-Net. Also, total planning time using the latter is at least 55 times faster than when no heuristic is used. This shows that our feasibility-informed planner avoids spending extensive effort on trying to perform a single P ass action directly to the goal robot, and prefers the use of a middleman robot with two P ass actions for each object.

The performance yielded on the Assist, Clear and M iddleman problems show that using feasibility prediction, our TAMP algorithm is able to identify scenarios where robot collaboration is advantageous or necessary, generally resulting in the first generated task plan being geometrically feasible as shown in Table I. Results on the Longswap problem demonstrate the ability of our approach to generalize to different multi-robot settings. In addition to an improvement in success rate from 20% to 100%, our feasibilityinformed planner reduces the total planning time by at least 84%. Using AGFP-Net, our algorithm identifies which of the sampled P ass placements are free and prioritizes them. It also recognizes occupied goal placements and includes T emp placements in its solution in order to free them.

These results show that our proposed approach is able to tackle single and multi-robot TAMP problems involving complex shaped objects. Feasibility prediction not only guarantees 100% success rate on all problems, but it also reduces considerably the planning time. Also, the overhead due to feasibility prediction is largely compensated by the time saved in geometric planning time.

VIII. CONCLUSION

In this paper, we present a method for extending the use of AGFP-Net [START_REF] Bouhsain | Simultaneous action and grasp feasibility prediction for task and motion planning through multi-task learning[END_REF] to complex-shaped objects, allowing action and grasp feasibility prediction on realistic objects. We also propose a framework for predicting the feasibility of actions in arbitrary multi-robot settings, taking advantage of the robot-centric nature of the neural network, and using a new approach for computing the probability of feasibility of collaborative actions such as P ass actions. Moreover, we develop a feasibility-informed multi-robot TAMP algorithm, capable of solving complex TAMP problems involving multiple robots. We demonstrate the performance of our method on six TAMP problems containing multiple complexshaped objects, and different single and multi-robot settings. Results show a notable gain in success rate and planning time using feasibility prediction as a heuristic. Future work might involve extending the approach to coordinated motion planning problems, and handling more collaborative actions such as handovers, allowing a parallel execution of tasks.

  Fig. 1: A visualization of the initial and goal states of 3 of the multi-robot TAMP problems solved by our method.

Fig. 2 :

 2 Fig. 2: Visualization of the feasibility prediction pipeline on an example 2-robot scene. (Top) Scene depth images are constructed for each robot such that only the objects in the workspace of the robot are shown. Objects present is both robots workspaces are visible in both scene projections (yellow mustard bottle). (bottom) Scene projections and object masks are given to AGFP-Net to obtain the action feasibility and the feasibility of 6 grasp types, illustrated on an example object.

(a)Fig. 3 :

 3 Fig. 3: Visualization of the initial and goal states for 3 of the 6 problem domains used to test our approach. Algorithm 3 findPossibleActions Input: s, E, s goal 1: A ← ∅ 2: for each O in movable objects do 3:

  E, s goal )

	11:	end if
	12: end while
	Algorithm 2 findChildren

Input: s, E, s goal

1: children ← ∅ 2: A ← f indP ossibleActions(s, E, s goal ) 3: for each a in A do 4: [p a F , p a G )] ← predictF easibility(s, E

, a) 5:

child ← nextState(s, a)

6:

child.cost ← computeCost(child, s goal , p F (a), E)

7:

children ← children ∪ child 8: end for 9: return children

LAAS-CNRS, Toulouse, France, {saitbouhsa, alami, simeon}@laas.fr

Note that this simple model of W (r) is generalizable to more precise workspace representations, provided that mapping the intersection between two workspaces is possible.

Note that q r 1 and q r 2 represent the placement pose expressed in the frame of robots r 1 and r 2 respectively, and are not robot configurations.

Although the number of samples is a parameter fixed by the user, we give the planner the possibility to resample new placements, in case the previous ones do not lead to a feasible solution.