Many real-life problems such as distributed meeting scheduling, mobile frequency allocation and resource allocation can be solved using multi-agent paradigms. Distributed constraint satisfaction problems (DisCSPs) is a framework for describing such problems in terms of related subproblems, called a complex local problem (CLP), which are dispersed over a number of locations, each with its own constraints on the values their variables can take. An agent knows the variables in its CLP plus the variables (and their current value) which are directly related to one of its own variables and the constraints relating them. It knows little about the rest of the problem. Thus, each CLP is solved by an agent which cooperates with other agents to solve the overall problem. Algorithms for solving DisCSPs can be classified as either systematic or local search with the former being complete and the latter incomplete. The algorithms generally assume that each agent has only one variable as they can solve DisCSP with CLPs using “virtual” agents. However, in large DisCSPs where it is appropriate to trade completeness off against timeliness, systematic search algorithms can be expensive when compared to local search algorithms which generally converge quicker to a solution (if a solution is found) when compared to systematic algorithms. A major drawback of local search algorithms is getting stuck at local optima. Significant researches have focused on heuristics which can be used in an attempt to either escape or avoid local optima. This thesis makes significant contributions to local search algorithms for DisCSPs. Firstly, we present a novel combination of heuristics in DynAPP (Dynamic Agent Prioritisation with Penalties), which is a distributed synchronous local search algorithm for solving DisCSPs having one variable per agent. DynAPP combines penalties on values and dynamic agent prioritisation heuristics to escape local optima. Secondly, we develop a divide and conquer approach that handles DisCSP with CLPs by exploiting the structure of the problem. The divide and conquer approach prioritises the finding of variable instantiations which satisfy the constraints between agents which are often more expensive to satisfy when compared to constraints within an agent. The approach also exploits concurrency and combines the following search strategies: (i) both systematic and local searches; (ii) both centralised and distributed searches; and (iii) a modified compilation strategy. We also present an algorithm that implements the divide and conquer approach in Multi-DCA (Divide and Conquer Algorithm for Agents with CLPs). DynAPP and Multi-DCA were evaluated on several benchmark problems and compared to the leading algorithms for DisCSPs and DisCSPs with CLPs respectively. The results show that at the region of difficult problems, combining search heuristics and exploiting problem structure in distributed constraint satisfaction achieve significant benefits (i.e. generally used less computational time and communication costs) over existing competing methods.

In order to improve the design of mechanical or mechatronic systems, mathematical optimization techniques have become an efficient and attractive tool with the increasing development of computer resources. However, the application of such optimization methods to multibody systems (MBS) remains a challenge when the MBS analysis requires the solving of assembly constraints. Hence, this PhD research focuses on the optimization of such closed-loop MBS, particularly when the objective function is of geometrical or kinematic nature. For kinematic optimization of MBS, we propose two penalty strategies to deal with assembly constraints during optimization. Both strategies are compared and illustrated via applications such as the isotropy maximization of parallel manipulators: the 3-dof Delta robot and the 6-dof Hunt platform. Following the same strategies, geometrical optimization of MBS is then investigated. However, due to a higher complexity, we propose to relax the problem, combining two modeling approaches: rigid-body and extensible-link formulations. This leads to a two-step strategy which is then successfully applied to synthesize mechanisms for path-following or function-generation problems. Through these applications, the existence of multiple local optima is highlighted. Therefore, instead of focusing on the unique global optimum solution, we have developed original methods to search and propose several local solutions for the design problem. This approach is called morphological optimization. This enables the designer to choose finally the best solution among several local optima using additional design criteria. Such morphological optimization techniques open the doors for the topology optimization of MBS which remains a challenging problem for future research / Afin d'améliorer la conception de systèmes mécaniques ou mécatroniques, les techniques d'optimisation mathématique sont devenues un outil efficace et attrayant étant donné le développement croissant des ressources informatiques. Cependant, l'application de telles méthodes d'optimisation sur les systèmes multicorps demeure un défi quand l'analyse du système nécessite la résolution de contraintes d'assemblage. C'est pourquoi cette recherche doctorale se concentre sur l'optimisation de tels systèmes multicorps, particulièrement lorsque la fonction objectif est de nature géométrique ou cinématique. Pour l'optimisation cinématique des systèmes multicorps, nous proposons deux stratégies de pénalité pour traiter les contraintes d'assemblage en cours d'optimisation. Ces deux stratégies sont comparées et illustrées par des applications telles que la maximisation d'isotropie de manipulateurs parallèles. Suivant les mêmes stratégies, l'optimisation géométrique des systèmes multicorps est alors étudiée. Cependant, vu la plus grande complexité, nous proposons de relaxer le problème en combinant deux approches de modélisation : une formulation en termes de corps rigides et une autre en termes de liens extensibles. Ceci nous mène à une stratégie en deux étapes qui est alors appliquée avec succès pour la synthèse de mécanismes. A travers ces applications, on a mis en évidence l'existence d'optimums locaux multiples. Dès lors, plutôt que de se focaliser sur l'unique optimum global, nous avons développé des méthodes originales afin de rechercher et proposer plusieurs solutions locales pour le problème de conception. Cette approche est baptisée "optimisation morphologique". Elle permet au concepteur de choisir finalement la meilleure solution parmi plusieurs optimums locaux en utilisant des critères supplémentaires de conception. De telles techniques d'optimisation morphologique ouvrent les portes pour l'optimisation topologique des systèmes multicorps qui demeure un challenge motivant pour des recherches futures.