Suivant le domaine où on les sollicite, les solutions d’un système de contraintes géométriques (SCG) peuvent être : – formelles et exactes : elles prennent par exemple la forme d’un plan de construction produisant toutes les solutions, obtenu en appliquant des règles dérivées de lemmes de géométrie. Beaucoup de SCG, surtout en 3D, résistent à cette approche ; – numériques et approchées : elles sont les solutions d’un système d’équations construit à partir des contraintes et trouvées grâce à des méthodes numériques efficaces quand elles ne recherchent qu’une solution. De par la nature des problèmes traités, chercher toutes les solutions conduit à une complexité exponentielle. Les méthodes par continuation, ou homotopie, permettent d’obtenir toutes les solutions d’un système d’équations polynomiales. Leur application à des SCG est coûteuse et difficilement sujette aux raisonnements permis par l’origine géométrique du problème car elles opèrent hors de l’espace des figures géométriques. Notre travail a pour objet la spécialisation d’une méthode par continuation à des SCG. La géométrie simplifie et justifie sa mise en œuvre dans l’espace des figures, ou des raisonnements géométriques sont possibles. On aborde également les cas ou l’ensemble de solutions d’un problème contient des éléments isolés et des continuums. Des solutions proches d’une esquisse fournie par un utilisateur sont d’abord trouvées. La recherche d’autres solutions, malgré sa complexité exponentielle, est rendue envisageable par une approche itérative. Une nouvelle méthode de décomposition est proposée pour maîtriser le coût de la résolution. / Depending on the required application field, the solutions of a geometric constraints system (GCS) are either : – symbolic and exact such as construction plans, providing all the solutions, obtained by applying geometric rules. Many problems, mostly in a 3D context, resist to this approach ; – or numerical and approximated : they are the solutions of a system of equations built from the constraints, provided by generical numerical methods that are efficient when only one solution is sought. However, searching all the solutions leads to an exponential computation cost, due to the nature of problems. Continuation methods, also called homotopic methods, find all the solutions of a polynomial system. Using them to solve systems of equations associated to systems of constraints is nevertheless costly. Moreover, combining them with geometric reasoning is a challenge, because they act in a projective complex space and not in the realizations space. The aim of this work is to specialize a continuation method to GCS. Geometry is exploited to simplify and justify its adaptation in the space of realizations, so allowing geometric reasoning. Cases where the connected components of the solution space of a problem have heterogeneous dimensions are addressed. The method discussed here provides in a first step solutions that are similar to a sketch drawn by the user. Then a procedure is proposed to search new solutions. Its iterative nature seems to make the exponential complexity of this task bearable. A new decomposition method is proposed, that restrains the resolution cost.

On étudie dans cette thèse des méthodes de localisation coopérative de robots mobiles sans utilisation de mesures extéroceptives relatives, comme des angles ou des distances entre robots. Les systèmes de localisation considérés sont basés sur des mesures de radionavigation sur des balises fixes ou des satellites. Pour ces systèmes, on observe en général un écart entre la position observée et la position réelle. Cet écart systématique (appelé biais) peut être dû à une mauvaise position de la balise ou à une différence entre la propagation réelles des ondes électromagnétiques par rapport aux conditions standard utilisées pour établir les modèles d’observation. L’influence de ce biais sur la localisation des robots est non négligeable. La coopération et l’échange de données entre les robots (estimations des biais, estimations des positions et données proprioceptives) est une approche qui permet de corriger ces erreurs systématiques. La localisation coopérative par échange des estimations est sujette aux problèmes de consanguinité des données qui peuvent engendrer des résultats erronés, en particulier trop confiants. Lorsque les estimations sont utilisées pour la navigation autonome à l’approche, on doit éviter tout risque de collision qui peut mettre en jeu la sécurité des robots et des personnes aux alentours. On doit donc avoir recours à un mécanisme d’intégrité vérifiant que l’erreur commise reste inférieure à une erreur maximale tolérable pour la mission. Dans un tel contexte, il est nécessaire de caractériser des domaines de confiance fiables contenant les positions des robots mobiles avec une forte probabilité. L’utilisation des méthodes ensemblistes à erreurs bornées est considérée alors comme une solution efficace. En effet, ce type d’approche résout naturellement le problème de consanguinité des données et fournit des domaines de confiance fiables. De surcroît, l’utilisation de modèles non-linéaires ne pose aucun problème de linéarisation. Après avoir modélisé un système coopératif de nr robots avec des mesures biaisées sur des balises, une étude d’observabilité est conduite. Deux cas sont considérés selon la nature des mesures brutes des observations. En outre, des conditions d’observabilité sont démontrées. Un algorithme ensembliste de localisation coopérative est ensuite présenté. Les méthodes considérées sont basées sur la propagation de contraintes sur des intervalles et l’inversion ensembliste. La coopération est effectuée grâce au partage des positions estimées, des biais estimés et des mesures proprioceptives.L’échange des estimations de biais permet de réduire les incertitudes sur les positions des robots. Dans un cadre d’étude simple, la faisabilité de l’algorithme est évaluée grâce à des simulations de mesures de distances sur balises en utilisant plusieurs robots. La coopération est comparée aux méthodes non coopératives. L’algorithme coopératif ensembliste est ensuite testé sur des données réelles en utilisant deux véhicules. Les performances de la méthode ensembliste coopérative sont enfin comparées avec deux méthodes Bayésiennes séquentielles, notamment une avec fusion par intersection de covariance. La comparaison est conduite en termes d’exactitude et d’incertitude. / In this work, we study some cooperative localization issues for mobile robotic systems that interact with each other without using relative measurements (e.g. bearing and relative distances). The considered localization technologies are based on beacons or satellites that provide radio-navigation measurements. Such systems often lead to offsets between real and observed positions. These systematic offsets (i.e, biases) are often due to inaccurate beacon positions, or differences between the real electromagnetic waves propagation and the observation models. The impact of these biases on robots localization should not be neglected. Cooperation and data exchange (estimates of biases, estimates of positions and proprioceptive measurements) reduce significantly systematic errors. However, cooperative localization based on sharing estimates is subject to data incest problems (i.e, reuse of identical information in the fusion process) that often lead to over-convergence problems. When position information is used in a safety-critical context (e.g. close navigation of autonomous robots), one should check the consistency of the localization estimates. In this context, we aim at characterizing reliable confidence domains that contain robots positions with high reliability. Hence, set-membership methods are considered as efficient solutions. This kind of approach enables merging adequately the information even when it is reused several time. It also provides reliable domains. Moreover, the use of non-linear models does not require any linearization. The modeling of a cooperative system of nr robots with biased beacons measurements is firstly presented. Then, we perform an observability study. Two cases regarding the localization technology are considered. Observability conditions are identified and demonstrated. We then propose a set-membership method for cooperativelocalization. Cooperation is performed by sharing estimated positions, estimated biases and proprioceptive measurements. Sharing biases estimates allows to reduce the estimation error and the uncertainty of the robots positions. The algorithm feasibility is validated through simulation when the observations are beacons distance measurements with several robots. The cooperation provides better performance compared to a non-cooperative method. Afterwards, the cooperative algorithm based on set-membership method is tested using real data with two experimental vehicles. Finally, we compare the interval method performance with a sequential Bayesian approach based on covariance intersection. Experimental results indicate that the interval approach provides more accurate positions of the vehicles with smaller confidence domains that remain reliable. Indeed, the comparison is performed in terms of accuracy and uncertainty.

L'émergence et la croissance rapide des services multimédia dans les réseaux IP ont créé de nouveaux défis pour les fournisseurs de services réseau, qui, au-delà de la Qualité de Service (QoS) issue des paramètres techniques de leur réseau, doivent aussi garantir la meilleure qualité de perception utilisateur (Quality of Experience, QoE) dans des réseaux variés avec différentes technologies d'accès. Habituellement, différentes méthodes et techniques sont utilisées pour prédire le niveau de satisfaction de l'utilisateur, en analysant l'effet combiné de multiples facteurs. Dans cette thèse, nous nous intéressons à la commande du réseau en intégrant à la fois des aspects qualitatifs (perception du niveau de satisfaction de l'usager) et quantitatifs (mesure de paramètres réseau) dans l'objectif de développer des mécanismes capables, à la fois, de s'adapter à la variabilité des mesures collectées et d'améliorer la qualité de perception. Pour ce faire, nous avons étudié le cas de deux services multimédia populaires, qui sont : le streaming vidéo, et la voix sur IP (VoIP). Nous investiguons la QoE utilisateur de ces services selon trois aspects : (1) les méthodologies d'évaluation subjective de la QoE, dans le cadre d'un service vidéo, (2) les techniques d'adaptation de flux vidéo pour garantir un certain niveau de QoE, et (3) les méthodes d'allocation de ressource, tenant compte de la QoE tout en économisant l'énergie, dans le cadre d'un service de VoIP (LTE-A). Nous présentons d'abord deux méthodes pour récolter des jeux de données relatifs à la QoE. Nous utilisons ensuite ces jeux de données (issus des campagnes d'évaluation subjective que nous avons menées) pour comprendre l'influence de différents paramètres (réseau, terminal, profil utilisateur) sur la perception d'un utilisateur d'un service vidéo. Nous proposons ensuite un algorithme de streaming vidéo adaptatif, implémenté dans un client HTTP, et dont le but est d'assurer un certain niveau de QoE et le comparons à l'état de l'art. Notre algorithme tient compte de trois paramètres de QoS (bande passante, taille de mémoires tampons de réception et taux de pertes de paquets) et sélectionne dynamiquement la qualité vidéo appropriée en fonction des conditions du réseau et des propriétés du terminal de l'utilisateur. Enfin, nous proposons QEPEM (QoE Power Efficient Method), un algorithme d'ordonnancement basé sur la QoE, dans le cadre d'un réseau sans fil LTE, en nous intéressant à une allocation dynamique des ressources radio en tenant compte de la consommation énergétique / The emerging and fast growth of multimedia services have created new challenges for network service providers in order to guarantee the best user's Quality of Experience (QoE) in diverse networks with distinctive access technologies. Usually, various methods and techniques are used to predict the user satisfaction level by studying the combined impact of numerous factors. In this thesis, we consider two important multimedia services to evaluate the user perception, which are: video streaming service, and VoIP. This study investigates user's QoE that follows three directions: (1) methodologies for subjective QoE assessment of video services, (2) regulating user's QoE using video a rate adaptive algorithm, and (3) QoE-based power efficient resource allocation methods for Long Term Evaluation-Advanced (LTE-A) for VoIP. Initially, we describe two subjective methods to collect the dataset for assessing the user's QoE. The subjectively collected dataset is used to investigate the influence of different parameters (e.g. QoS, video types, user profile, etc.) on user satisfaction while using the video services. Later, we propose a client-based HTTP rate adaptive video streaming algorithm over TCP protocol to regulate the user's QoE. The proposed method considers three Quality of Service (QoS) parameters that govern the user perception, which are: Bandwidth, Buffer, and dropped Frame rate (BBF). The BBF method dynamically selects the suitable video quality according to network conditions and user's device properties. Lastly, we propose a QoE driven downlink scheduling method, i.e. QoE Power Escient Method (QEPEM) for LTE-A. It esciently allocates the radio resources, and optimizes the use of User Equipment (UE) power utilizing the Discontinuous Reception (DRX) method in LTE-A

Une approche efficace pour la résolution de problèmes inverses consiste à définir le signal (ou l'image) recherché(e) par minimisation d'un critère pénalisé. Ce dernier s'écrit souvent sous la forme d'une somme de fonctions composées avec des opérateurs linéaires. En pratique, ces fonctions peuvent n'être ni convexes ni différentiables. De plus, les problèmes auxquels on doit faire face sont souvent de grande dimension. L'objectif de cette thèse est de concevoir de nouvelles méthodes pour résoudre de tels problèmes de minimisation, tout en accordant une attention particulière aux coûts de calculs ainsi qu'aux résultats théoriques de convergence. Une première idée pour construire des algorithmes rapides d'optimisation est d'employer une stratégie de préconditionnement, la métrique sous-jacente étant adaptée à chaque itération. Nous appliquons cette technique à l'algorithme explicite-implicite et proposons une méthode, fondée sur le principe de majoration-minimisation, afin de choisir automatiquement les matrices de préconditionnement. L'analyse de la convergence de cet algorithme repose sur l'inégalité de Kurdyka-L ojasiewicz. Une seconde stratégie consiste à découper les données traitées en différents blocs de dimension réduite. Cette approche nous permet de contrôler à la fois le nombre d'opérations s'effectuant à chaque itération de l'algorithme, ainsi que les besoins en mémoire, lors de son implémentation. Nous proposons ainsi des méthodes alternées par bloc dans les contextes de l'optimisation non convexe et convexe. Dans le cadre non convexe, une version alternée par bloc de l'algorithme explicite-implicite préconditionné est proposée. Les blocs sont alors mis à jour suivant une règle déterministe acyclique. Lorsque des hypothèses supplémentaires de convexité peuvent être faites, nous obtenons divers algorithmes proximaux primaux-duaux alternés, permettant l'usage d'une règle aléatoire arbitraire de balayage des blocs. L'analyse théorique de ces algorithmes stochastiques d'optimisation convexe se base sur la théorie des opérateurs monotones. Un élément clé permettant de résoudre des problèmes d'optimisation de grande dimension réside dans la possibilité de mettre en oeuvre en parallèle certaines étapes de calculs. Cette parallélisation est possible pour les algorithmes proximaux primaux-duaux alternés par bloc que nous proposons: les variables primales, ainsi que celles duales, peuvent être mises à jour en parallèle, de manière tout à fait flexible. A partir de ces résultats, nous déduisons de nouvelles méthodes distribuées, où les calculs sont répartis sur différents agents communiquant entre eux suivant une topologie d'hypergraphe. Finalement, nos contributions méthodologiques sont validées sur différentes applications en traitement du signal et des images. Nous nous intéressons dans un premier temps à divers problèmes d'optimisation faisant intervenir des critères non convexes, en particulier en restauration d'images lorsque l'image originale est dégradée par un bruit gaussien dépendant du signal, en démélange spectral, en reconstruction de phase en tomographie, et en déconvolution aveugle pour la reconstruction de signaux sismiques parcimonieux. Puis, dans un second temps, nous abordons des problèmes convexes intervenant dans la reconstruction de maillages 3D et dans l'optimisation de requêtes pour la gestion de bases de données / An efficient approach for solving an inverse problem is to define the recovered signal/image as a minimizer of a penalized criterion which is often split in a sum of simpler functions composed with linear operators. In the situations of practical interest, these functions may be neither convex nor smooth. In addition, large scale optimization problems often have to be faced. This thesis is devoted to the design of new methods to solve such difficult minimization problems, while paying attention to computational issues and theoretical convergence properties. A first idea to build fast minimization algorithms is to make use of a preconditioning strategy by adapting, at each iteration, the underlying metric. We incorporate this technique in the forward-backward algorithm and provide an automatic method for choosing the preconditioning matrices, based on a majorization-minimization principle. The convergence proofs rely on the Kurdyka-L ojasiewicz inequality. A second strategy consists of splitting the involved data in different blocks of reduced dimension. This approach allows us to control the number of operations performed at each iteration of the algorithms, as well as the required memory. For this purpose, block alternating methods are developed in the context of both non-convex and convex optimization problems. In the non-convex case, a block alternating version of the preconditioned forward-backward algorithm is proposed, where the blocks are updated according to an acyclic deterministic rule. When additional convexity assumptions can be made, various alternating proximal primal-dual algorithms are obtained by using an arbitrary random sweeping rule. The theoretical analysis of these stochastic convex optimization algorithms is grounded on the theory of monotone operators. A key ingredient in the solution of high dimensional optimization problems lies in the possibility of performing some of the computation steps in a parallel manner. This parallelization is made possible in the proposed block alternating primal-dual methods where the primal variables, as well as the dual ones, can be updated in a quite flexible way. As an offspring of these results, new distributed algorithms are derived, where the computations are spread over a set of agents connected through a general hyper graph topology. Finally, our methodological contributions are validated on a number of applications in signal and image processing. First, we focus on optimization problems involving non-convex criteria, in particular image restoration when the original image is corrupted with a signal dependent Gaussian noise, spectral unmixing, phase reconstruction in tomography, and blind deconvolution in seismic sparse signal reconstruction. Then, we address convex minimization problems arising in the context of 3D mesh denoising and in query optimization for database management

La performance d'un algorithme sur une architecture donnée dépend à la fois de la vitesse à laquelle le processeur effectue des opérations à virgule flottante (flops) et de la vitesse d'accès à la mémoire et au disque. Etant donné que le coût de la communication est beaucoup plus élevé que celui des opérations arithmétiques, celle-là forme un goulot d'étranglement dans les algorithmes numériques. Récemment, des méthodes de sous-espace de Krylov basées sur les méthodes 's-step' ont été développées pour réduire les communications. En effet, très peu de préconditionneurs existent pour ces méthodes, ce qui constitue une importante limitation. Dans cette thèse, nous présentons le préconditionneur nommé ''Communication-Avoiding ILU0'', pour la résolution des systèmes d’équations linéaires (Ax=b) de très grandes tailles. Nous proposons une nouvelle renumérotation de la matrice A ('alternating min-max layers'), avec laquelle nous montrons que le préconditionneur en question réduit la communication. Il est ainsi possible d’effectuer « s » itérations d’une méthode itérative préconditionnée sans communication. Nous présentons aussi deux nouvelles méthodes itératives, que nous nommons 'multiple search direction with orthogonalization CG' (MSDO-CG) et 'long recurrence enlarged CG' (LRE-CG). Ces dernières servent à la résolution des systèmes linéaires d’équations de très grandes tailles, et sont basées sur l’enrichissement de l’espace de Krylov par la décomposition du domaine de la matrice A. / The performance of an algorithm on any architecture is dependent on the processing unit’s speed for performing floating point operations (flops) and the speed of accessing memory and disk. As the cost of communication is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation of these methods. In this thesis, we present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method with no communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We discuss two new versions of Conjugate Gradient, multiple search direction with orthogonalization CG (MSDO-CG) and long recurrence enlarged CG (LRE-CG).

Dans le présent travail, des nouvelles méthodes de décomposition de domaine et des nouvelles implémentations pour des méthodes existantes sont développées. Une nouvelle méthode basée sur les méthodes antérieures de décomposition du domaine est formulée. Les méthodes classiques FETI plus FETI-2LM sont utilisées pour construire le nouveau Hybrid-FETI. L'idée de base est de développer un nouvel algorithme qui peut utiliser les deux méthodes en même temps en choisissant dans chaque interface l'état le plus adapté en fonction des caractéristiques du problème. En faisant cela, nous recherchons un code plus rapide et plus robuste qui peut fonctionner avec des configurations selon lesquelles les méthodes de base ne le géreront pas de manière optimale par lui-même. La performance est testée sur un problème de contact. La partie suivante implique le développement d'une nouvelle implémentation pour la méthode S-FETI, l'idée est de réduire l'utilisation de la mémoire de cette méthode, afin de pouvoir fonctionner dans des problèmes de taille plus important. Différentes variantes pour cette méthode sont également proposées, tout en cherchant la réduction des directions stockées chaque itération de la méthode itérative. Finalement, une extension de la méthode FETI-2LM à sa version en bloc comme dans S-FETI, est développée. Les résultats numériques pour les différents algorithmes sont présentés. / In this work new domain decomposition methods and new implementations for existing methods are developed. A new method based on previous domain decomposition methods is formulated. The classic FETI plus FETI-2LM methods are used to build the new Hybrid-FETI. The basic idea is to develop a new algorithm that can use both methods at the same time by choosing in each interface the most suited condition depending on the characteristics of the problem. By doing this we search to have a faster and more robust code that can work with configurations that the base methods will not handle it optimally by himself. The performance is tested on a contact problem. The following part involves the development of a new implementation for the S-FETI method, the idea is to reduce the memory usage of this method, to make it able to work in larger problem. Different variation for this method are also proposed, all searching the reduction of directions stored each iteration of the iterative method. Finally, an extension of the FETI-2LM method to his block version as in S-FETI, is developed. Numerical results for the different algorithms are presented.

La simulation numérique de phénomènes physiques complexes requiert généralement l’utilisation d’un maillage. En mécanique des fluides numérique, cela consisteà représenter un objet dans un gros volume de contrôle. Cet objet étant celui dont l’on souhaite simuler le comportement. Usuellement, l’objet et la boîte englobante sont représentés par des maillage de surface linéaires et la zone intermédiaire est remplie par un maillage volumique. L’objectif de cette thèse est de s’intéresser à deux manières différentes de représenter cet objet. La première approche dite immergée consiste à mailler intégralement le volume de contrôle et ensuite à simuler le comportement autour de l’objet sans avoir à mailler explicitement dans le volume ladite géometrie. L’objet étant implicitement pris en compte par le schéma numérique. Le couplage de cette méthode avec de l’adaptation de maillage linéaire est notamment étudié. La deuxième approche dite d’ordre élevé consiste quant à elle consiste à augmenter le degré polynomial du maillage de surface de l’objet. La première étape consiste donc à générer le maillage de surface de degré élevé et ensuite àpropager l’information de degré élevé dans les éléments volumiques environnants si nécessaire. Dans ce cadre-là, il s’agit de s’assurer de la validité de telles modifications et à considérer l’extension des méthodes classiques de modification de maillages linéaires. / The numerical simulation of complex physical phenomenons usually requires a mesh. In Computational Fluid Dynamics, it consists in representing an object inside a huge control volume. This object is then the subject of some physical study. In general, this object and its bounding box are represented by linear surface meshes and the intermediary zone is filled by a volume mesh. The aim of this thesis is to have a look on two different approaches for representing the object. The first approach called embedded method consist in integrally meshing the bounding box volume without explicitly meshing the object in it. In this case, the presence of the object is implicitly simulated by the CFD solver. The coupling of this method with linear mesh adaptation is in particular discussed.The second approach called high-order method consist on the contrary by increasing the polynomial order of the surface mesh of the object. The first step is therefore to generate a suitable high-order mesh and then to propagate the high-order information in the neighboring volume if necessary. In this context, it is mandatory to make sure that such modifications are valid and then the extension of classic mesh modification techniques has to be considered.

Les problématiques de sécurité sont aujourd’hui un facteur différentiateur clé dans le secteur aéronautique. Bien que certains systèmes d’assistance aux hélicoptères existent et qu’une partie de la connaissance associée aux situations d’urgence ait pu être identifiée, reste que les travaux antérieurs se limitent pour la plupart à une autonomie de bas niveau. Ainsi la génération d’un plan de vol sous fortes contraintes de temps représente à ce jour une voie d’exploration nouvelle, et un défi technologique essentiel pour l’hélicoptère de demain. A cet égard, AIRBUS HELICOPTERS accorde un fort intérêt à la conception d’un système décisionnel capable de générer des plans de vols en temps réel. L’enjeu de l’intelligence répartie au travers de systèmes décisionnels distribués constitue un axe de recherche fort, et un des contributeurs clés pour un positionnement leader d’AIRBUS HELICOPTERS sur la thématique sécurité. Aujourd’hui, l’étude des systèmes décisionnels embarqués dans les engins volants constitue un défi majeur pour divers groupes de travail académiques et industriels. En effet, la résolution de ce défi fait appel généralement à différentes compétences afin de maîtriser plusieurs aspects du système recouvrant les domaines d’acquisition, d’analyse et de traitement de données. Et ce dans le but de prendre des décisions en temps-réel en prenant en considération plusieurs paramètres contextuels et environnementaux. Les défis scientifiques à contourner dans la présente thèse s’articulent sur deux axes majeurs. Dans un premier temps, il faut proposer une approche complète pour une planification en temps réel d’un plan de vol d’hélicoptères. Permettant à cette dernière de faire face à d’éventuels événements dynamiques tel que l’apparition de nouveaux obstacles ou un changement de mission. Ensuite, nous nous intéressons à une implantation embarquée de la solution proposée sur une architecture hétérogène haute performance. / Security issues are today a key-differentiator in the aviation sector. Indeed, it comes to ensure the safety of expensive equipments but above all to save human lives. In this context, it is necessary to offer an important level of autonomy to helicopters. Although some studies have been carried out in this area, the dynamic generation of a sequence of maneuvers under hard time constraints in an unknown environment still represents a major challenge for many academic and industrial working groups. AIRBUS HELICOPTERS as a leader of helicopters manufacturing, looks forward to integrate an assistance system for mission re-planning in the next generation of aircrafts.The work conducted in this PhD thesis falls within a collaboration between AIRBUS HELICOPTERS and UNIVERSITE DE VALENCIENNES ET DU HAINAUTCAMBRESIS. One of the main purposes of this work is efficient flight plan generation. Indeed, for intelligent assistant systems we need to generate a new path planning inorder to face emergency events such as an equipment failure or adverse weather conditions. The second major objective of this work is the deployment of mission planning tasks onto a high performance architecture CPU/FPGA in order to meet real-time requirements for the dynamic optimization process. In the present work, we first studied efficient flight plan generation. Indeed, we developed efficient and effective algorithms for helicopter path planning. Then, in order to obtain a real-time system, we resolved the problem of scheduling optimization on a heterogeneous architecture CPU / FPGA by proposing several scheduling methods including exact approaches and heuristics.

Les moteurs de recherche exploratoire (MRE) sont des logiciels aidant les utilisateurs à explorer un domaine d’intérêt pour y faire des découvertes. Ces moteurs se distinguent en cela des moteurs de recherche classiques tels que Google, Bing ou Yahoo!, lesquels supportent plutôt des recherches ciblées ou recherches de consultation (lookup). Si l’on admet que l’évaluation des MRE vise à vérifier si ces derniers aident effectivement les utilisateurs à réaliser leur tâche d’exploration, on constate que les méthodes existantes d’évaluation de ces systèmes ne permettent pas réellement cette vérification. L’une des raisons à cela est que ces méthodes ne reposent pas sur un modèle approprié de la recherche exploratoire (RE) ou qu’elles restent accrochées à un modèle de la recherche de consultation. L’objectif principal de cette thèse est de proposer aux concepteurs de ces MRE des méthodes d’évaluation centrées utilisateurs reposant sur un modèle du processus de RE. Ainsi, après avoir modélisé le processus de RE, nous proposons deux méthodes d’évaluation qui peuvent être utilisées tout au long du processus de conception. La première méthode, une méthode d’inspection sans utilisateurs, peut être utilisée dès les premières maquettes, et repose sur des heuristiques de RE. Nous avons également proposé des outils facilitant l’utilisation de ces heuristiques : un formulaire en ligne ainsi qu’une extension Google Chrome appelée CheXplore. La seconde méthode, avec utilisateurs, peut être utilisée dès la première version d’un prototype fonctionnel. Cette méthode se présente comme une procédure de test utilisateur personnalisable. Dans cette thèse, nous nous intéressons plus particulièrement à deux éléments de cette procédure : un protocole d’élaboration de tâches de RE et une grille d’analyse d’enregistrements vidéo de session de RE. La pertinence du modèle ainsi que les méthodes qui en découlent ont été évaluées à l’occasion de tests utilisateurs. Le modèle, les heuristiques et le protocole d’élaboration des tâches de RE ont été validés. Les premières évaluations de la grille d’analyse d’enregistrements vidéos ont révélé des points à améliorer. / Exploratory search systems are search engines that help users to explore a topic of interest. A shortcoming of current evaluation methods is that they cannot be used to determine if an exploratory search system can effectively help the user in performing exploratory search tasks. Indeed, the assessment cannot be the same between classic search systems (such as Google, Bing, Yahoo!...) and exploratory search systems. The complexity and the difficulty to have a consensus definition of the exploratory search concept and process are reflected in the difficulties to evaluate such systems. Indeed, they combine several specifics features and behaviors forming an alchemy difficult to evaluate. The main objective of this thesis is to propose for the designers of these systems (i.e. computer scientists) user-centered evaluation methods of exploratory search systems. These methods are based on a model of exploratory search process in order to help the evaluators to verify if a given system supports effectively the exploratory search process. Thus, after elaborating a model of exploratory search process, we propose two model-based methods, with and without users, which can be used all along the design process. The first method, without users, can be used from the first sketch of the system, consists of a set of heuristics of exploratory search and a procedure for using them. We also propose two tools facilitating their use: an online form format and an Google Chrome plugin, CheXplore. The second method involves real end-users of exploratory search systems who test a functional prototype or version of an exploratory search system. In this thesis, we mainly focus on two model-based elements of a customizable user testing procedure: a protocol for the elaboration of exploratory search tasks and a video analysis grid for the evaluation of recorded exploratory search sessions.

Avec l'avènement de machine parallèles multi-coeurs, de nombreux algorithmes doivent être modifiés ou conçus pour s'adapter à ces architectures. Ces algorithmes consistent pour la plupart à diviser le problème original en plusieurs petits sous-problèmes et à les distribuer sur les différentes unités de calcul disponibles. La résolution de ces petits sous-problèmes peut être exécutée en parallèle, des communications entre les unités de calcul étant indispensables pour assurer la convergence de ces méthodes.Ma thèse propose de nouveaux algorithmes parallèles pour résoudre de grands systèmes linéaires.Les algorithmes proposés sont ici basés sur la méthode du gradient. Deux points fondamentaux de la méthode du gradient sont la direction de descente de la solution approchée et la valeur du pas de descente, qui détermine la modification à effectuer à chaque itération. Nous proposons dans cette thèse de calculer la direction et le pas indépendamment et localement sur chaque unité de calcul, ce qui nécessite moins de synchronisation entre les processeurs, et par suite rend chaque itération simple et plus rapide, et rend son extension dans un contexte asynchrone possible.Avec les paramètres d'échelle appropriés pour le pas des longueurs, la convergence peut être démontrée pour les deux versions synchrone et asynchrone des algorithmes. De nombreux tests numériques illustrent l’efficacité de ces méthodes.L'autre partie de ma thèse propose d'utiliser une méthode d'extrapolation pour accélérer les méthodes itératives classiques avec retard. Bien que les séquences de vecteur générées par des méthodes itératives asynchrones générales classiques ne peut être accélérée, nous sommes en mesure de démontrer que, une fois le modèle de calcul et de communication fixés au cours de l’exécution, la séquence de vecteurs générés peut être accéléré. De nombreux tests numériques illustrent l’efficacité de ces accélérations dans le cas des méthodes avec retard. / With the increase of architectures composed of multi-cores, many algorithms need to revisited and be modified to exploit the power of these new architectures. These algorithms divide the original problem into “small pieces” and distribute these pieces to different processors at disposal, thus communications among them are indispensible to assure the convergence. My thesis mainly focus on solving large sparse systems of linear equations in parallel with new methods. These methods are based on the gradient methods. Two key parameters of the gradient methods are descent direction and step-length of descent for each iteration. Our methods compute the directions locally, which requires less synchronization and computation, leading to faster iterations and make easy asynchronization possible. Convergence can be proved in both synchronized or asynchronized cases. Numerical tests demonstrate the efficiency of these methods. The other part of my thesis deal with the acceleration of the vector sequences generated by classical iterative algorithms. Though general chaotic sequences may not be accelerated, it is possible to prove that with any fixed retard pattern, then the generated sequence can be accelerated. Different numerical tests demonstrate its efficiency.