Multi-Agent Path Finding (MAPF) focuses on determining conflict-free paths for multiple agents navigating through a shared space to reach specified goal locations. This problem becomes computationally challenging, particularly when handling large numbers of agents, as frequently encountered in practical applications like coordinating autonomous vehicles. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing power and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithms which are based on branch-and-cut-and-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and state-of-the-art MAPF solvers.

Classification of radar observations with machine learning tools is of primary importance for the identification of non-cooperative radar targets such as drones. These observations are made of complex-valued time series which possess a strong underlying structure. These signals can be processed through a time-frequency analysis, through their self-correlation (or covariance) matrices or directly as the raw signal. All representations are linked but distinct and it is known that the input representation is critical for the success of any machine learning method. In this article, we explore these three possible input representation spaces with the help of two kinds of neural networks: a temporal fully convolutional network and a Riemannian network working direcly on the manifold of covariances matrices. We show that all the considered input representations are a particular case of a generic machine learning pipeline which goes from the raw complex data to the final classification stage through con-volutional layers and Riemannian layers. This pipeline can be learnt end-to-end and is shown experimentally to give the best classification accuracy together with the best robustness to lack of data.

Covariance matrices have attracted attention for machine learning applications due to their capacity to capture interesting structure in the data. The main challenge is that one needs to take into account the particular geometry of the Riemannian manifold of symmetric positive definite (SPD) matrices they belong to. In the con- text of deep networks, several architectures for these matrices have recently been proposed. In our article, we introduce a Riemannian batch normalization (batch- norm) algorithm, which generalizes the one used in Euclidean nets. This novel layer makes use of geometric operations on the manifold, notably the Riemannian barycenter, parallel transport and non-linear structured matrix transformations. We derive a new manifold-constrained gradient descent algorithm working in the space of SPD matrices, allowing to learn the batchnorm layer. We validate our proposed approach with experiments in three different contexts on diverse data types: a drone recognition dataset from radar observations, and on emotion and action recognition datasets from video and motion capture data. Experiments show that the Riemannian batchnorm systematically gives better classification performance compared with leading methods and a remarkable robustness to lack of data.

The CMA-ES is one of the most powerful stochastic numerical optimizers to address difficult black-box problems. Its intrinsic time and space complexity is quadratic—limiting its applicability with increasing problem dimensionality. To circumvent this limitation, different large-scale variants of CMA-ES with subquadratic complexity have been proposed over the past ten years. To-date however, these variants have been tested and compared only in rather restrictive settings, due to the lack of a comprehensive large-scale testbed to assess their performance. In this context, we introduce a new large-scale testbed with dimension up to 640, implemented within the COCO benchmarking platform. We use this testbed to assess the performance of several promising variants of CMA-ES and the standard limited-memory L-BFGS. In all tested dimensions, the best CMA-ES variant solves more problems than L-BFGS for larger budgets while L-BFGS outperforms the best CMA-ES variant for smaller budgets. However, over all functions, the cumulative runtime distributions between L-BFGS and the best CMA-ES variants are close (less than a factor of 4 in high dimension). Our results illustrate different scaling behaviors of the methods, expose a few defects of the algorithms and reveal that for dimension larger than 80, LM-CMA solves more problems than VkD-CMA while in the cumulative runtime distribution over all functions the VkD-CMA dominates LM-CMA for budgets up to $$10^4$$ times dimension and for all budgets up to dimension 80.

We propose to use new shortest path computation methods based on Front propagation with Level Set approach for a radar application. This new radar function consists in computing most threatening trajectories & corridors in the radar coverage in order to adapt radar modes for detection optimization. This Radar problem may be declined as a variationnal problem solved by calculus of variations and front propagation based on an adaptation of Fermat's principle of least time with an Hamilton-Jacobi formulation. A partial differential equation PDE drives the temporal evolution of contours of constant action (level lines of the manifold defined by the minimal potential surface given by the integration of a local function of the detection probability along every potential trajectories). The orthogonality between geodesics (shortest path) and curves of iso-action provides a simple numerical scheme for geodesics computation based on a steepest gradient descent algorithm (backtracking on the level-lines of iso-action). We underline the analogy of this radar problem with Feynman/Schwinger's principle that states close connexion between variational principle and quantum theory. Finally, we have extended the problem to anisotropic constraint induced by Radar Cross Section.

The main challenge of future phased array multifunction radar will be to optimise the radar time budget to avoid deleterious overload effects. For this purpose, we propose a new technique for priority assignment of Search Domains. Then, we have developed new algorithms for most threatening trajectories computation based on Calculus of Variations approach developed for "shortest path computation" in image processing.

This paper considers interference cancellation in radar systems when the signal environment is non-stationary and focuses on the extended sample matrix inversion algorithm (ESMI) first proposed by Hay ward (1996). An explicit expression of the signal to noise plus interference ratio (SINR) obtained by this ESMI algorithm is given and analyzed. Compared to the SMI algorithm, it is shown that the performance improves for mainlobe jammers but degrades for sidelobe jammers. To overcome this drawback, an alternative constraint strategy is proposed which attains the good performances of the standard ESMI algorithm whatever the position of the jammers. Finally, the explicit expressions of these SINR are compared to Monte Carlo simulations w.r.t. implementation conditions

The DOLPHINS project is supported in part by the 4/sup th/ European RTD Framework Program, and deals with echographic applications dedicated to arterial walls and plaque segmentation, plaque motion and degree of stenoses analysis. For this purpose, we have adapted geodesic active contours methods for arterial walls segmentation, to characterize stenose severity with regularized high resolution Doppler spectrum analysis by turbulences mapping from a Doppler spectral width measurement. The original contribution of our approach consists in using the same calculus of variations framework for image segmentation and Doppler velocimetry. We prove that we can, by analogy, find the equivalent mean curvature flow equation, used for geodesic active contours, for Doppler analysis by considering the complex autoregressive polynomial as a closed plane curve immersed in the oriented Euclidean plane.

The aim of this study is to perform a short term forecasting of dynamic radar clutter evolution (shape and position). This dynamic clutter, like thunderstorms, can be tracked by means of adapted algorithms based on the matching of the morphological skeleton polygonal approximation by relaxation labeling processes. The efficiency of our methods is demonstrated on meteorological radar images. The objective of this application is dedicated to civil traffic regulation according to severe atmospheric phenomenon, as described in Monnier & al. (1997). Through radar environment assessment, we observe radar clutter, like precipitation, submitted to very complex deformations that cannot be modelized easily. In Barbaresco (1999), we proposed a method based on morphological skeleton deformation to forecast the fluid topological evolution. This method allows management of very complex shapes evolution thanks to polygonal approximation of the skeletons and matching of their closed couple of elements by the relaxation algorithm. The skeleton simplifies shape analysis and deformation but also distinguishes clutter displacement and articulated deformation by skeleton matching from homothetic deformation (inflation and deflation) by medial axis (radius of maximal disks contained in the shape) tracking.

A new recursive eigendecomposition algorithm of complex Hermitian Toeplitz matrices is studied. Based on Trench's inversion of Toeplitz matrices from their autoregressive analysis, we have developed a fast recursive iterative algorithm that takes into account the rank-one modification of successive order Toeplitz matrices. To speed up the computational time and to increase numerical stability of ill-conditioned eigendecomposition in case of very short data records analysis, we have extended this method by introducing an ago-antagonistic regularized reflection coefficient via Levinson equation. We provide a geometrical interpretation of this new recursive eigendecomposition.

The aim of this study is to perform a classification and a short term spatial estimation of radar clutter. Motion-based segmentation allows one to part clutter into two sets: the static ones and the dynamic ones. A spatial segmentation can then be processed, using Doppler data, in order to obtain homogeneous clutter. The dynamic clutter can be tracked by means of adaptive algorithms based on new techniques such as active contours, front propagation combined with Kalman filtering and motion estimation. The efficiency of our methods is demonstrated on atmospheric clutter in meteorological radar images.