Boolean Satisfiability (SAT) is a fundamental NP-complete problem of determining whether there exists an assignment of variables which makes a Boolean formula evaluate to True. SAT is a convenient representation for many naturally occurring optimization and decisions problems such as planning and circuit verification. SAT is most commonly solved by a form of backtracking search which systematically explores the space of possible variable assignments. We show that the order in which variable polarities are assigned can have a significant impact on the performance of backtracking algorithms. We present several ways of transforming SAT instances into non-linear objective functions and describe three value-ordering methods based on iterative optimization techniques. We implement and test these heuristics in the widely-recognized MiniSAT framework. The first approach determines polarities by applying Newton's Method to a sparse system of non-linear objective functions whose roots correspond to the satisfying assignments of the propositional formula. The second approach determines polarities by minimizing an objective function corresponding to the number of clauses conflicting with each assignment. The third approach determines preferred polarities by performing stochastic gradient descent on objective functions sampled from a family of continuous potentials. The heuristics are evaluated on a set of standard benchmarks including random, crafted and industrial problems. We compare our results to five existing heuristics, and show that MiniSAT equipped with our heuristics often outperforms state-of-the-art SAT solvers.

Boolean Satisfiability (SAT) is a fundamental NP-complete problem of determining whether there exists an assignment of variables which makes a Boolean formula evaluate to True. SAT is a convenient representation for many naturally occurring optimization and decisions problems such as planning and circuit verification. SAT is most commonly solved by a form of backtracking search which systematically explores the space of possible variable assignments. We show that the order in which variable polarities are assigned can have a significant impact on the performance of backtracking algorithms. We present several ways of transforming SAT instances into non-linear objective functions and describe three value-ordering methods based on iterative optimization techniques. We implement and test these heuristics in the widely-recognized MiniSAT framework. The first approach determines polarities by applying Newton's Method to a sparse system of non-linear objective functions whose roots correspond to the satisfying assignments of the propositional formula. The second approach determines polarities by minimizing an objective function corresponding to the number of clauses conflicting with each assignment. The third approach determines preferred polarities by performing stochastic gradient descent on objective functions sampled from a family of continuous potentials. The heuristics are evaluated on a set of standard benchmarks including random, crafted and industrial problems. We compare our results to five existing heuristics, and show that MiniSAT equipped with our heuristics often outperforms state-of-the-art SAT solvers.

L’objectif de cette thèse est le développement de méthodes d’optimisation multi-objectif pour la résolution de problèmes de conception des structures mécaniques. En effet, la plupart des problèmes réels dans le domaine de la mécanique des structures ont plusieurs objectifs qui sont souvent antagonistes. Il s’agit, par exemple, de concevoir des structures en optimisant leurs poids, leurs tailles, et leurs coûts de production. Le but des méthodes d’optimisation multi-objectif est la recherche des solutions de compromis entre les objectifs étant donné l’impossibilité de satisfaire tout simultanément. Les métaheuristiques sont des méthodes d’optimisation capables de résoudre les problèmes d’optimisation multi-objective en un temps de calcul raisonnable sans garantie de l’optimalité de (s) solution (s). Au cours des dernières années, ces algorithmes ont été appliqués avec succès pour résoudre le problème des mécaniques des structures. Dans cette thèse deux métaheuristiques ont été développées pour la résolution des problèmes d’optimisation multi-objectif en général et de conception de structures mécaniques en particulier. Le premier algorithme baptisé MOBSA utilise les opérateurs de croisement et de mutation de l’algorithme BSA. Le deuxième algorithme nommé NNIA+X est une hybridation d’un algorithme immunitaire et de trois croisements inspirés de l’opérateur de croisement original de l’algorithme BSA. Pour évaluer l’efficacité et l’efficience de ces deux algorithmes, des tests sur quelques problèmes dans littérature ont été réalisés avec une comparaison avec des algorithmes bien connus dans le domaine de l’optimisation multi-objectif. Les résultats de comparaison en utilisant des métriques très utilisées dans la littérature ont démontré que ces deux algorithmes peuvent concurrencer leurs prédécesseurs. / The objective of this thesis is the development of multi-objective optimization methods for solving mechanical design problems. Indeed, most of the real problems in the field of mechanical structures have several objectives that are often antagonistic. For example, it is about designing structures by optimizing their weight, their size, and their production costs. The goal of multi-objective optimization methods is the search for compromise solutions between objectives given the impossibility to satisfy all simultaneously. Metaheuristics are optimization methods capable of solving multi-objective optimization problems in a reasonable calculation time without guaranteeing the optimality of the solution (s). In recent years, these algorithms have been successfully applied to solve the problem of structural mechanics. In this thesis, two metaheuristics have been developed for the resolution of multi-objective optimization problems in general and of mechanical structures design in particular. The first algorithm called MOBSA used the crossover and mutation operators of the BSA algorithm. The second one named NNIA+X is a hybridization of an immune algorithm and three crossover inspired by the original crossover operator of the BSA algorithm. To evaluate the effectiveness and efficiency of these two algorithms, tests on some problems in literature have been made with a comparison with algorithms well known in the field of multi-objective optimization. The comparison results using metrics widely used in the literature have shown that our two algorithms can compete with their predecessors.

Atualmente as estruturas estão sendo avaliadas para um maior número de ações em relação há algumas décadas. Esta melhoria ao longo da fase de concepção é dada devido ao fato de que está se tornando mais competitivo o fornecimento de estruturas leves e esbeltas, sendo solicitados, cada vez mais, projetos com menor custo de implantação. Devido a isto, é necessário avaliar as estruturas não apenas sujeitas a cargas estáticas, mas também a carregamentos dinâmicos. As ações dinâmicas que atuam sobre uma estrutura podem ser muito mais prejudiciais do que as estáticas quando não são bem consideradas e dimensionadas. Ações dinâmicas podem ser provenientes de tremores de terra, vento, equipamentos em funcionamento, deslocamento de pessoas, veículos em movimento, motores desbalanceados, entre outras fontes, o que pode causar vibrações na estrutura, podendo levar a mesma ao colapso. A fim de controlar e reduzir as amplitudes de vibração, entre outras alternativas é possível a instalação de amortecedores de massa sintonizado (AMS), que é um dispositivo de controle passivo. O AMS tem várias vantagens, tais como a grande capacidade de reduzir a amplitude de vibração, fácil instalação, baixa manutenção, baixo custo, entre outras. Para se obter a melhor relação custo-benefício, ou seja, a maior redução de amplitude aliada a um menor número de amortecedores ou a uma menor massa, a otimização dos parâmetros do AMS tornase fundamental. Neste contexto, este trabalho visa, através de simulação numérica, propor um método para otimizar parâmetros de AMSs quando estes devem ser instalados em edifícios submetidos à excitação sísmica. Inicialmente é considerado apenas um único AMS instalado no topo do edifício e em seguida também são feitas simulações com múltiplos AMSs (MAMS), e por fim são descartados os AMSs desnecessários, obtendo assim a melhor resposta da estrutura. Para tanto, uma rotina computacional é desenvolvida em MatLab usando o método de integração direta das equações de movimento de Newmark para determinar a resposta dinâmica da estrutura. Para fins de análise podem ser considerados tanto sismos reais quanto artificiais. Os acelerogramas artificias são gerados a partir do espectro proposto por Kanai e Tajimi. Primeiramente, a estrutura é analisada somente com o seu amortecimento próprio para fins comparativos e de referência. Em seguida, a otimização do ou dos AMSs é feita, na qual a função objetivo é minimizar o deslocamento máximo no topo do edifício, e as variáveis de projeto, são a relação de massas (AMS - Estrutura), rigidez e amortecimento do ou dos AMSs. Para a otimização são utilizados os algoritmos Firefly Algotithm e Backtracking Search Optimization Algorithm. De acordo com as configurações do AMS, após a otimização dos seus parâmetros são determinadas as novas respostas dinâmicas da estrutura. Finalmente, pode-se observar que o método proposto foi capaz de otimizar os parâmetros do ou dos AMSs, reduzindo consideravelmente as respostas da estrutura após a instalação do mesmo, minimizando o risco de dano e colapso do edifício. Desta forma, este trabalho mostra que é possível projetar AMS e MAMS de forma econômica e eficaz. / Currently, structures are being evaluated for a greater number of actions when compared to a few decades ago. This improvement in designing stage is happening because projects providing lightweight and slender structures, with lower implantation costs, are being more requested. Thus, evaluating structures not only subjected to static loads, but also to dynamic loads has become necessary. Dynamic loads acting on a structure are more damaging than static loads, if they are not well considered and dimensioned. Dynamic loads could occur from earthquakes, wind, equipment, movement of people or vehicles, among other sources, which cause vibrations in structures and may lead to a collapse. Tuned mass damper (TMD), a passive control device, can be installed as an alternative to reduce vibration amplitudes. TMD has several advantages, such as large capacity to reduce amplitude of vibration, easy installation, low maintenance, low cost, among others. Optimizing TMD parameters is fundamental for obtaining best cost-benefit relation, i.e., greater amplitude reduction along with lower number of dampers or lower mass. In this context, this study aims at proposing, through numerical simulation, a method for optimizing TMD parameters when installing them on buildings under seismic excitation. Initially, a single-TMD case is considered, then simulations with multiple-TMDs (MTMDs) are run; lastly, unnecessary TMDs are discarded, obtaining the best structural response. For this purpose, a computational routine is developed on MatLab using Newmark direct integration method for equations of motion to determine the dynamic structural response. Both real and artificial earthquakes are considered for purposes of analysis. Artificial accelerograms are generated from proposed Kanai-Tajimi spectrum. First, structure is analyzed only with its own damping for comparison and reference. Second, a single or multiple-TMD optimization is carried out, in which the objective function is to minimize the maximum displacement at the top of the building, and the design variables are modal mass ratio (Structure-TMD), stiffness and damping of a single or multiple-TMD. Firefly and Backtracking Optimization algorithms are used for optimization. According to TMD settings, new dynamic structural responses are determined after optimizing parameters. Finally, the proposed method could optimize parameters of single or multiple-TMDs, considerably reducing structural responses after their installation, minimizing the risk of damage and building collapse. Thus, this study shows the possibility of designing TMDs or MTMDs both economically and effectively.

Atualmente as estruturas estão sendo avaliadas para um maior número de ações em relação há algumas décadas. Esta melhoria ao longo da fase de concepção é dada devido ao fato de que está se tornando mais competitivo o fornecimento de estruturas leves e esbeltas, sendo solicitados, cada vez mais, projetos com menor custo de implantação. Devido a isto, é necessário avaliar as estruturas não apenas sujeitas a cargas estáticas, mas também a carregamentos dinâmicos. As ações dinâmicas que atuam sobre uma estrutura podem ser muito mais prejudiciais do que as estáticas quando não são bem consideradas e dimensionadas. Ações dinâmicas podem ser provenientes de tremores de terra, vento, equipamentos em funcionamento, deslocamento de pessoas, veículos em movimento, motores desbalanceados, entre outras fontes, o que pode causar vibrações na estrutura, podendo levar a mesma ao colapso. A fim de controlar e reduzir as amplitudes de vibração, entre outras alternativas é possível a instalação de amortecedores de massa sintonizado (AMS), que é um dispositivo de controle passivo. O AMS tem várias vantagens, tais como a grande capacidade de reduzir a amplitude de vibração, fácil instalação, baixa manutenção, baixo custo, entre outras. Para se obter a melhor relação custo-benefício, ou seja, a maior redução de amplitude aliada a um menor número de amortecedores ou a uma menor massa, a otimização dos parâmetros do AMS tornase fundamental. Neste contexto, este trabalho visa, através de simulação numérica, propor um método para otimizar parâmetros de AMSs quando estes devem ser instalados em edifícios submetidos à excitação sísmica. Inicialmente é considerado apenas um único AMS instalado no topo do edifício e em seguida também são feitas simulações com múltiplos AMSs (MAMS), e por fim são descartados os AMSs desnecessários, obtendo assim a melhor resposta da estrutura. Para tanto, uma rotina computacional é desenvolvida em MatLab usando o método de integração direta das equações de movimento de Newmark para determinar a resposta dinâmica da estrutura. Para fins de análise podem ser considerados tanto sismos reais quanto artificiais. Os acelerogramas artificias são gerados a partir do espectro proposto por Kanai e Tajimi. Primeiramente, a estrutura é analisada somente com o seu amortecimento próprio para fins comparativos e de referência. Em seguida, a otimização do ou dos AMSs é feita, na qual a função objetivo é minimizar o deslocamento máximo no topo do edifício, e as variáveis de projeto, são a relação de massas (AMS - Estrutura), rigidez e amortecimento do ou dos AMSs. Para a otimização são utilizados os algoritmos Firefly Algotithm e Backtracking Search Optimization Algorithm. De acordo com as configurações do AMS, após a otimização dos seus parâmetros são determinadas as novas respostas dinâmicas da estrutura. Finalmente, pode-se observar que o método proposto foi capaz de otimizar os parâmetros do ou dos AMSs, reduzindo consideravelmente as respostas da estrutura após a instalação do mesmo, minimizando o risco de dano e colapso do edifício. Desta forma, este trabalho mostra que é possível projetar AMS e MAMS de forma econômica e eficaz. / Currently, structures are being evaluated for a greater number of actions when compared to a few decades ago. This improvement in designing stage is happening because projects providing lightweight and slender structures, with lower implantation costs, are being more requested. Thus, evaluating structures not only subjected to static loads, but also to dynamic loads has become necessary. Dynamic loads acting on a structure are more damaging than static loads, if they are not well considered and dimensioned. Dynamic loads could occur from earthquakes, wind, equipment, movement of people or vehicles, among other sources, which cause vibrations in structures and may lead to a collapse. Tuned mass damper (TMD), a passive control device, can be installed as an alternative to reduce vibration amplitudes. TMD has several advantages, such as large capacity to reduce amplitude of vibration, easy installation, low maintenance, low cost, among others. Optimizing TMD parameters is fundamental for obtaining best cost-benefit relation, i.e., greater amplitude reduction along with lower number of dampers or lower mass. In this context, this study aims at proposing, through numerical simulation, a method for optimizing TMD parameters when installing them on buildings under seismic excitation. Initially, a single-TMD case is considered, then simulations with multiple-TMDs (MTMDs) are run; lastly, unnecessary TMDs are discarded, obtaining the best structural response. For this purpose, a computational routine is developed on MatLab using Newmark direct integration method for equations of motion to determine the dynamic structural response. Both real and artificial earthquakes are considered for purposes of analysis. Artificial accelerograms are generated from proposed Kanai-Tajimi spectrum. First, structure is analyzed only with its own damping for comparison and reference. Second, a single or multiple-TMD optimization is carried out, in which the objective function is to minimize the maximum displacement at the top of the building, and the design variables are modal mass ratio (Structure-TMD), stiffness and damping of a single or multiple-TMD. Firefly and Backtracking Optimization algorithms are used for optimization. According to TMD settings, new dynamic structural responses are determined after optimizing parameters. Finally, the proposed method could optimize parameters of single or multiple-TMDs, considerably reducing structural responses after their installation, minimizing the risk of damage and building collapse. Thus, this study shows the possibility of designing TMDs or MTMDs both economically and effectively.

Atualmente as estruturas estão sendo avaliadas para um maior número de ações em relação há algumas décadas. Esta melhoria ao longo da fase de concepção é dada devido ao fato de que está se tornando mais competitivo o fornecimento de estruturas leves e esbeltas, sendo solicitados, cada vez mais, projetos com menor custo de implantação. Devido a isto, é necessário avaliar as estruturas não apenas sujeitas a cargas estáticas, mas também a carregamentos dinâmicos. As ações dinâmicas que atuam sobre uma estrutura podem ser muito mais prejudiciais do que as estáticas quando não são bem consideradas e dimensionadas. Ações dinâmicas podem ser provenientes de tremores de terra, vento, equipamentos em funcionamento, deslocamento de pessoas, veículos em movimento, motores desbalanceados, entre outras fontes, o que pode causar vibrações na estrutura, podendo levar a mesma ao colapso. A fim de controlar e reduzir as amplitudes de vibração, entre outras alternativas é possível a instalação de amortecedores de massa sintonizado (AMS), que é um dispositivo de controle passivo. O AMS tem várias vantagens, tais como a grande capacidade de reduzir a amplitude de vibração, fácil instalação, baixa manutenção, baixo custo, entre outras. Para se obter a melhor relação custo-benefício, ou seja, a maior redução de amplitude aliada a um menor número de amortecedores ou a uma menor massa, a otimização dos parâmetros do AMS tornase fundamental. Neste contexto, este trabalho visa, através de simulação numérica, propor um método para otimizar parâmetros de AMSs quando estes devem ser instalados em edifícios submetidos à excitação sísmica. Inicialmente é considerado apenas um único AMS instalado no topo do edifício e em seguida também são feitas simulações com múltiplos AMSs (MAMS), e por fim são descartados os AMSs desnecessários, obtendo assim a melhor resposta da estrutura. Para tanto, uma rotina computacional é desenvolvida em MatLab usando o método de integração direta das equações de movimento de Newmark para determinar a resposta dinâmica da estrutura. Para fins de análise podem ser considerados tanto sismos reais quanto artificiais. Os acelerogramas artificias são gerados a partir do espectro proposto por Kanai e Tajimi. Primeiramente, a estrutura é analisada somente com o seu amortecimento próprio para fins comparativos e de referência. Em seguida, a otimização do ou dos AMSs é feita, na qual a função objetivo é minimizar o deslocamento máximo no topo do edifício, e as variáveis de projeto, são a relação de massas (AMS - Estrutura), rigidez e amortecimento do ou dos AMSs. Para a otimização são utilizados os algoritmos Firefly Algotithm e Backtracking Search Optimization Algorithm. De acordo com as configurações do AMS, após a otimização dos seus parâmetros são determinadas as novas respostas dinâmicas da estrutura. Finalmente, pode-se observar que o método proposto foi capaz de otimizar os parâmetros do ou dos AMSs, reduzindo consideravelmente as respostas da estrutura após a instalação do mesmo, minimizando o risco de dano e colapso do edifício. Desta forma, este trabalho mostra que é possível projetar AMS e MAMS de forma econômica e eficaz. / Currently, structures are being evaluated for a greater number of actions when compared to a few decades ago. This improvement in designing stage is happening because projects providing lightweight and slender structures, with lower implantation costs, are being more requested. Thus, evaluating structures not only subjected to static loads, but also to dynamic loads has become necessary. Dynamic loads acting on a structure are more damaging than static loads, if they are not well considered and dimensioned. Dynamic loads could occur from earthquakes, wind, equipment, movement of people or vehicles, among other sources, which cause vibrations in structures and may lead to a collapse. Tuned mass damper (TMD), a passive control device, can be installed as an alternative to reduce vibration amplitudes. TMD has several advantages, such as large capacity to reduce amplitude of vibration, easy installation, low maintenance, low cost, among others. Optimizing TMD parameters is fundamental for obtaining best cost-benefit relation, i.e., greater amplitude reduction along with lower number of dampers or lower mass. In this context, this study aims at proposing, through numerical simulation, a method for optimizing TMD parameters when installing them on buildings under seismic excitation. Initially, a single-TMD case is considered, then simulations with multiple-TMDs (MTMDs) are run; lastly, unnecessary TMDs are discarded, obtaining the best structural response. For this purpose, a computational routine is developed on MatLab using Newmark direct integration method for equations of motion to determine the dynamic structural response. Both real and artificial earthquakes are considered for purposes of analysis. Artificial accelerograms are generated from proposed Kanai-Tajimi spectrum. First, structure is analyzed only with its own damping for comparison and reference. Second, a single or multiple-TMD optimization is carried out, in which the objective function is to minimize the maximum displacement at the top of the building, and the design variables are modal mass ratio (Structure-TMD), stiffness and damping of a single or multiple-TMD. Firefly and Backtracking Optimization algorithms are used for optimization. According to TMD settings, new dynamic structural responses are determined after optimizing parameters. Finally, the proposed method could optimize parameters of single or multiple-TMDs, considerably reducing structural responses after their installation, minimizing the risk of damage and building collapse. Thus, this study shows the possibility of designing TMDs or MTMDs both economically and effectively.

Many real life problems can be formulated as constraint satisfaction problems <i>(CSPs)</i>. Backtracking search algorithms are usually employed to solve <i>CSPs</i> and in backtracking search the choice of branching strategies can be critical since they specify how a search algorithm can instantiate a variable and how a problem can be reduced into subproblems; that is, they define a search tree. In spite of the apparent importance of the branching strategy, there have been only a few empirical studies about different branching strategies and they all have been tested exclusively for numerical constraints. In this thesis, we employ the three most commonly used branching strategies in solving finite domain <i>CSPs</i>. These branching strategies are described as follows: first, a branching strategy with strong commitment assigns its variables in the early stage of the search as in k-Way branching; second, 2-Way branching guides a search by branching one side with assigning a variable and the other with eliminating the assigned value; third, the domain splitting strategy, based on the least commitment principle, branches by dividing a variable's domain rather than by assigning a single value to a variable. In our experiments, we compared the efficiency of different branching strategies in terms of their execution times and the number of choice points in solving finite domain <i>CSPs</i>. Interestingly, our experiments provide evidence that the choice of branching strategy for finite domain problems does not matter much in most cases--provided we are using an effective variable ordering heuristic--as domain splitting and 2-Way branching end up simulating k-Way branching. However, for an optimization problem with large domain size, the branching strategy with the least commitment principle can be more efficient than the other strategies. This empirical study will hopefully interest other practitioners to take different branching schemes into consideration in designing heuristics.

Many real life problems can be formulated as constraint satisfaction problems <i>(CSPs)</i>. Backtracking search algorithms are usually employed to solve <i>CSPs</i> and in backtracking search the choice of branching strategies can be critical since they specify how a search algorithm can instantiate a variable and how a problem can be reduced into subproblems; that is, they define a search tree. In spite of the apparent importance of the branching strategy, there have been only a few empirical studies about different branching strategies and they all have been tested exclusively for numerical constraints. In this thesis, we employ the three most commonly used branching strategies in solving finite domain <i>CSPs</i>. These branching strategies are described as follows: first, a branching strategy with strong commitment assigns its variables in the early stage of the search as in k-Way branching; second, 2-Way branching guides a search by branching one side with assigning a variable and the other with eliminating the assigned value; third, the domain splitting strategy, based on the least commitment principle, branches by dividing a variable's domain rather than by assigning a single value to a variable. In our experiments, we compared the efficiency of different branching strategies in terms of their execution times and the number of choice points in solving finite domain <i>CSPs</i>. Interestingly, our experiments provide evidence that the choice of branching strategy for finite domain problems does not matter much in most cases--provided we are using an effective variable ordering heuristic--as domain splitting and 2-Way branching end up simulating k-Way branching. However, for an optimization problem with large domain size, the branching strategy with the least commitment principle can be more efficient than the other strategies. This empirical study will hopefully interest other practitioners to take different branching schemes into consideration in designing heuristics.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto. / Many applications of Swarm Robotic Systems (SRSs) require that a robot is able to discover its position. The location information of the robots is required, for example, to allow them to be correctly positioned within a predefined swarm formation. Similarly, when the robots act as mobile sensors, the position information is needed to allow the identification of the location of the measured events. Due to the size, cost and energy source restrictions of these devices, or even limitations imposed by the operating environment, the straightforward solution, i.e. the use of a Global Positioning System (GPS), is often not feasible. The method proposed in this work allows the estimation of the absolute positions of a set of unknown nodes, based on the coordinates of a set of reference nodes and the distances measured between nodes. The solution is achieved by means of a distributed processing strategy, where each unknown node estimates its own position and helps its neighbors to compute their respective coordinates. The solution makes use of a new method called Multi-hop Collaborative Min-Max Localization (MCMM), herein proposed, aiming to improve the quality of the initial positions estimated by the unknown nodes in case of failure during the recognition of the reference nodes. The positions refinement is achieved based on the Backtracking Search Optimization Algorithm (BSA) and the Particle Swarm Optimization (PSO), whose performances are compared. To compose the objective function, a new method to compute the confidence factor of the network nodes is introduced, the Min-max Area Confidence Factor (MMA-CF), which is compared with the existing Hops to Anchor Confidence Factor (HTA-CF). Based on the proposed localization method, four algorithms were developed and further evaluated through a set of simulations in MATLABr and experiments in swarms of type Kilobot robots. The performance of the algorithms is evaluated on problems with different topologies, quantities of nodes and proportion of reference nodes. The performance of the algorithms is also compared with the performance of other localization algorithms, showing improvements between 40% to 51%. The simulations and experiments outcomes demonstrate the effectiveness of the proposed method.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto. / Many applications of Swarm Robotic Systems (SRSs) require that a robot is able to discover its position. The location information of the robots is required, for example, to allow them to be correctly positioned within a predefined swarm formation. Similarly, when the robots act as mobile sensors, the position information is needed to allow the identification of the location of the measured events. Due to the size, cost and energy source restrictions of these devices, or even limitations imposed by the operating environment, the straightforward solution, i.e. the use of a Global Positioning System (GPS), is often not feasible. The method proposed in this work allows the estimation of the absolute positions of a set of unknown nodes, based on the coordinates of a set of reference nodes and the distances measured between nodes. The solution is achieved by means of a distributed processing strategy, where each unknown node estimates its own position and helps its neighbors to compute their respective coordinates. The solution makes use of a new method called Multi-hop Collaborative Min-Max Localization (MCMM), herein proposed, aiming to improve the quality of the initial positions estimated by the unknown nodes in case of failure during the recognition of the reference nodes. The positions refinement is achieved based on the Backtracking Search Optimization Algorithm (BSA) and the Particle Swarm Optimization (PSO), whose performances are compared. To compose the objective function, a new method to compute the confidence factor of the network nodes is introduced, the Min-max Area Confidence Factor (MMA-CF), which is compared with the existing Hops to Anchor Confidence Factor (HTA-CF). Based on the proposed localization method, four algorithms were developed and further evaluated through a set of simulations in MATLABr and experiments in swarms of type Kilobot robots. The performance of the algorithms is evaluated on problems with different topologies, quantities of nodes and proportion of reference nodes. The performance of the algorithms is also compared with the performance of other localization algorithms, showing improvements between 40% to 51%. The simulations and experiments outcomes demonstrate the effectiveness of the proposed method.