Population-based global optimization algorithms including Particle Swarm Optimization (PSO) have become popular for solving multi-optima problems much more efficiently than the traditional mathematical techniques. In this research, we present and evaluate a new parallel PSO algorithm that provides a significant performance improvement as compared to the serial PSO algorithm. Instead of merely assigning parts of the task of serial version to several processors, the new algorithm places multiple swarms on the available nodes in which operate independently, while collaborating on the same task. With the reduction of the communication bottleneck as well the ability to manipulate the individual swarms independently, the proposed approach outperforms the original PSO algorithm and still maintains the simplicity and ease of implementation.

Submitted by Maykon Nascimento (maykon.albani@hotmail.com) on 2015-08-03T18:48:30Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) / Approved for entry into archive by Elizabete Silva (elizabete.silva@ufes.br) on 2015-08-13T21:44:43Z (GMT) No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) / Made available in DSpace on 2015-08-13T21:44:43Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Um algoritmo PSO híbrido para planejamento de caminhos em navegação de veículos utilizando A.pdf: 2604695 bytes, checksum: ed8f69e49eaefe272bccd6025290c381 (MD5) Previous issue date: 2015 / Utilizar robôs autônomos capazes de planejar o seu caminho é um desafio que atrai vários pesquisadores na área de navegação de robôs. Neste contexto, este trabalho tem como objetivo implementar um algoritmo PSO híbrido para o planejamento de caminhos em ambientes estáticos para veículos holonômicos e não holonômicos. O algoritmo proposto possui duas fases: a primeira utiliza o algoritmo A* para encontrar uma trajetória inicial viável que o algoritmo PSO otimiza na segunda fase. Por fim, uma fase de pós planejamento pode ser aplicada no caminho a fim de adaptá-lo às restrições cinemáticas do veículo não holonômico. O modelo Ackerman foi considerado para os experimentos. O ambiente de simulação de robótica CARMEN (Carnegie Mellon Robot Navigation Toolkit) foi utilizado para realização de todos os experimentos computacionais considerando cinco instâncias de mapas geradas artificialmente com obstáculos. O desempenho do algoritmo desenvolvido, A*PSO, foi comparado com os algoritmos A*, PSO convencional e A* Estado Híbrido. A análise dos resultados indicou que o algoritmo A*PSO híbrido desenvolvido superou em qualidade de solução o PSO convencional. Apesar de ter encontrado melhores soluções em 40% das instâncias quando comparado com o A*, o A*PSO apresentou trajetórias com menos pontos de guinada. Investigando os resultados obtidos para o modelo não holonômico, o A*PSO obteve caminhos maiores entretanto mais suaves e seguros. / Autonomous robots with the ability of planning their own way is a challenge that attracts many researchers in the area of robot navigation. In this context, this work aims to implement a hybrid PSO algorithm for planning paths in static environments for holonomic and non-holonomic vehicles. The proposed algorithm has two phases: the first uses A* algorithm to generates an initial and feasible trajectory which is optimized by the PSO algorithm in the second stage. Finally a post path planning phase can be applied in order to adapt it to non-holonomic vehicle kinematic constraints. The Ackerman model has been considered for the experiments. The Carnegie Mellon Robot Navigation Toolkit (CARMEN) was used to perform the computational experiments considering five instances of maps artificially generated with obstacles. The performance of the A*PSO algorithm was compared with A*, PSO and A*-Hybrid State. The results of the dynamic instances were not compared with other algorithms. The computational results indicates that the algorithm A*PSO outperformes the PSO algorithm. With respect to the algorithm A*, the A*PSO achieved better solutions for 40% of the tested instances, but all of them, with less waypoints. For non-holonomic instances, the A*PSO obtained longer paths, however smoother and safer.

O presente trabalho avalia a otimização de parâmetros concentrados de suspensão em veículos e considera a importância deste processo para minimizar a aceleração vertical rms transmitida para garantir conforto e segurança ao motorista. Dessa forma, o trabalho objetiva desenvolver uma modelagem capaz de representar o veículo completo para então otimizar os parâmetros de rigidez e amortecimento no domínio da frequência e identificar, em torno do ponto ótimo, quais desses parâmetros mais influenciam nessa minimização. Para atingir esses objetivos, dois modelos veiculares (com dois e oito graus de liberdade respectivamente) são propostos conforme as orientações das normas BS 6841 (1987), ISO 8608 (1995) e ISO 2631 (1997). Os modelos são analisados linearmente e otimizados por um algoritmo heurístico de enxame de partículas. Finalmente, os resultados de rigidez e amortecimento da suspensão são obtidos e reduzem em até 35,3% a aceleração vertical rms transmitida ao motorista. Por meio de uma análise de sensibilidade, as variáveis de projeto que mais contribuem para essa redução são identificadas. / The present work evaluates the optimization of lumped parameters of suspension on vehicles and considers the importance of this process to minimize the rms vertical acceleration transmitted to ensure comfort and safety to the driver. Thus, this work aims to develop a model able to represent the whole vehicle and, then, optimize the parameters of stiffness and damping in the frequency domain and identify, around the optimal point, those parameters which most influence in this minimization. To achieve these goals, two vehicle models (with two and eight degrees of freedom respectively) are proposed according to the guidelines of the standards BS 6841 (1987), ISO 8608 (1995) and ISO 2631 (1997). The models are linearly analyzed and optimized by a heuristic algorithm of particle swarm. Finally, the results of stiffness and damping of suspension are obtained and reduces up to 35,3% of rms vertical acceleration transmitted to the driver. Through a sensitivity analysis, the design variables that most contribute to this reduction are identified.

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, Departamento de Engenharia Elétrica, 2014. / Submitted by Ana Cristina Barbosa da Silva (annabds@hotmail.com) on 2014-11-25T17:23:31Z No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2014-11-25T17:58:53Z (GMT) No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Made available in DSpace on 2014-11-25T17:58:54Z (GMT). No. of bitstreams: 1 2014_RafaelCortesdePaiva.pdf: 7660330 bytes, checksum: eaad53db8e1c76edec638a3e30ee5f3e (MD5) / Nesse trabalho foi realizado o estudo de técnicas bio-inspiradas para gerar a marcha de um robô bípede. Foi utilizado o conceito de CPG, Central Pattern Generator (CPG), que é uma rede neural capaz de produzir respostas rítmicas. Elas foram modeladas como osciladores acoplados chamados de osciladores neurais. Para tanto foram utilizados alguns modelos de osciladores, o modelo de Matsuoka, o modelo de Kuramoto e o modelo de Kuramoto com acoplamento entre a dinâmica do oscilador e a dinâmica da marcha. Foram usados dois modelos de robôs, o Bioloid e o NAO. Para otimizar os parâmetros dos osciladores foram utilizados o Algoritmo Genético (AG), o Particle Swarm Optimization (PSO) e o Nondominated sorting Genetic Algorithm II (NSGA-II). Foi utilizada uma função de custo que através de determinadas condições tem como objetivo obter uma marcha eficiente. No NSGA-II, além dessa função de custo, foi utilizada outra função de custo que considera o trabalho realizado pelo robô. Além disso, também foi utilizada a aprendizagem por reforço para treinar um controlador que corrige a postura do robô durante a marcha. Foi possível propor um framework para obter os parâmetros dos osciladores e através dele obter uma marcha estável em ambas as plataformas. Também foi possível propor um framework utilizando aprendizagem por reforço para treinar um controlador para corrigir a postura do robô com a marcha sendo gerado pelo oscilador de Kuramoto com acoplamento. O objetivo do algoritmo foi minimizar a velocidade do ângulo de arfagem do corpo do robô, dessa forma, a variação do ângulo de arfagem também foi minimizada consequentemente. Além disso, o robô andou mais “cautelosamente” para poder manter a postura e dessa forma percorreu uma distância menor do que se estivesse sem o controlador. ______________________________________________________________________________ ABSTRACT / This document describes computational optimized bipedal robot gait generators. Thegaits are applied by a neural oscillator, composed of coupled central pattern generators(CPG), which are neural networks capable of producing rhythmic output. The models ofthe oscillators used were the Matsuoka model, Kuramoto model and Kura moto model withcoupling between the dynamics of the oscillator and dynamics of the gait. Two bipedalrobots, a NAO and a Bioloid, were used. The neural oscillators were optimized with threealgorithms, a Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Nondominatedsorting Genetic Algorithm II (NSGA-II). It was used a fitness function that has theobjective to obtain an efficient gait through some conditions. In NSGA-II, besides this fitnessfunction, another one was used that has the objective to minimize the work done by therobot. Additionally, reinforcement learning techniques were used to train a controller thatcorrects the robots gait posture. It was proposed a framework to obtain the parameters of theoscillators used and obtain efficient gaits in both robots. Also, it was proposed a frameworkusing reinforcement learning to train a controller to correct the robots gait posture. The objective of the algorithm was to minimize the pitch angular velocity, consequently the pitchangle standard deviation was minimized. Additionally, the robot moved with more “caution” and walked less compared with the walk without the posture controller.

O presente trabalho avalia a otimização de parâmetros concentrados de suspensão em veículos e considera a importância deste processo para minimizar a aceleração vertical rms transmitida para garantir conforto e segurança ao motorista. Dessa forma, o trabalho objetiva desenvolver uma modelagem capaz de representar o veículo completo para então otimizar os parâmetros de rigidez e amortecimento no domínio da frequência e identificar, em torno do ponto ótimo, quais desses parâmetros mais influenciam nessa minimização. Para atingir esses objetivos, dois modelos veiculares (com dois e oito graus de liberdade respectivamente) são propostos conforme as orientações das normas BS 6841 (1987), ISO 8608 (1995) e ISO 2631 (1997). Os modelos são analisados linearmente e otimizados por um algoritmo heurístico de enxame de partículas. Finalmente, os resultados de rigidez e amortecimento da suspensão são obtidos e reduzem em até 35,3% a aceleração vertical rms transmitida ao motorista. Por meio de uma análise de sensibilidade, as variáveis de projeto que mais contribuem para essa redução são identificadas. / The present work evaluates the optimization of lumped parameters of suspension on vehicles and considers the importance of this process to minimize the rms vertical acceleration transmitted to ensure comfort and safety to the driver. Thus, this work aims to develop a model able to represent the whole vehicle and, then, optimize the parameters of stiffness and damping in the frequency domain and identify, around the optimal point, those parameters which most influence in this minimization. To achieve these goals, two vehicle models (with two and eight degrees of freedom respectively) are proposed according to the guidelines of the standards BS 6841 (1987), ISO 8608 (1995) and ISO 2631 (1997). The models are linearly analyzed and optimized by a heuristic algorithm of particle swarm. Finally, the results of stiffness and damping of suspension are obtained and reduces up to 35,3% of rms vertical acceleration transmitted to the driver. Through a sensitivity analysis, the design variables that most contribute to this reduction are identified.

Context. Building autonomous racing car controllers is a growing field of computer science which has been receiving great attention lately. An approach named Artificial Potential Fields (APF) is used widely as a path finding and obstacle avoidance approach in robotics and vehicle motion controlling systems. The use of APF results in a collision free path, it can also be used to achieve other goals such as overtaking and maneuverability. Objectives. The aim of this thesis is to build an autonomous racing car controller that can achieve good performance in terms of speed, time, and damage level. To fulfill our aim we need to achieve optimality in the controller choices because racing requires the highest possible performance. Also, we need to build the controller using algorithms that does not result in high computational overhead. Methods. We used Particle Swarm Optimization (PSO) in combination with APF to achieve optimal car controlling. The Open Racing Car Simulator (TORCS) was used as a testbed for the proposed controller, we have conducted two experiments with different configuration each time to test the performance of our APF- PSO controller. Results. The obtained results showed that using the APF-PSO controller resulted in good performance compared to top performing controllers. Also, the results showed that the use of PSO proved to enhance the performance compared to using APF only. High performance has been proven in the solo driving and in racing competitions, with the exception of an increased level of damage, however, the level of damage was not very high and did not result in a controller shut down. Conclusions. Based on the obtained results we have concluded that the use of PSO with APF results in high performance while taking low computational cost.

The Ant Colony Optimization and Particle Swarm Optimization are two Swarm Intelligence algorithms often utilized for optimization. Swarm Intelligence relies on agents that possess fragmented knowledge, a concept not often utilized in games. The aim of this study is to research whether there are any benefits to using these Swarm Intelligence algorithms in comparison to standard algorithms such as A* for pathfinding in a game. Games often consist of dynamic environments with mobile agents, as such all experiments were conducted with dynamic destinations. Algorithms were measured on the length of their path and the time taken to calculate that path. The algorithms were implemented with minor modifications to allow them to better function in a grid based environment. The Ant Colony Optimization was modified in regards to how pheromone was distributed in the dynamic environment to better allow the algorithm to path towards a mobile target. Whereas the Particle Swarm Optimization was given set start positions and velocity in order to increase initial search space and modifications to increase particle diversity. The results obtained from the experimentation showcased that the Swarm Intelligence algorithms were capable of performing to great results in terms of calculation speed, they were however not able to obtain the same path optimality as A*. The algorithms' implementation can be improved but show potential to be useful in games.

By enabling coordinated task execution and movement, robotic swarms can achieve efficient exploration or disaster site management. When utilizing Ultra-wideband (UWB) radio technology for ranging, the proposed relative localization sensor can be made lightweight and relatively indifferent to the ambient environment. Infrastructure dependency is eliminated by making the whole sensor fit on a swarm agent, while allowing for a certain amount of positional error. In this thesis, a novel algorithm is implemented in to constrained hardware and compared to a more traditional trilateration approach. Both algorithms utilize Particle Swarm Optimization (PSO) to be more robust towards noise and achieves similar accuracy, but the proposed algorithm can run up to ten times faster. The antenna array which forms the localization sensor weighs only 56g, and achieves around 0.5m RMSE with a 10Hz update rate. Experiments show that the accuracy can be further improved if the rotational bias observed in the UWB devices are compensated for.

The recent advent of bioinformatics has given rise to the central and recurrent problem of optimally aligning biological sequences. Many techniques have been proposed in an attempt to solve this complex problem with varying degrees of success. This thesis investigates the application of a computational intelligence technique known as particle swarm optimization (PSO) to the multiple sequence alignment (MSA) problem. Firstly, the performance of the standard PSO (S-PSO) and its characteristics are fully analyzed. Secondly, a scalability study is conducted that aims at expanding the S-PSO’s application to complex MSAs, as well as studying the behaviour of three other kinds of PSOs on the same problems. Experimental results show that the PSO is efficient in solving the MSA problem and compares positively with well-known CLUSTAL X and T-COFFEE. / Dissertation (MSc)--University of Pretoria, 2009. / Computer Science / Unrestricted

Non-rigid shapes are generally known as objects whose three dimensional geometry may deform by internal and/or external forces. Deformable shapes are all around us, ranging from protein molecules, to natural objects such as the trees in the forest or the fruits in our gardens, and even human bodies. Two deformable shapes may be related by isometry, which means their intrinsic geometries are preserved, even though their extrinsic geometries are dissimilar. An important problem in the analysis of the deformable shapes is to identify the three-dimensional correspondence between two isometric shapes, given that the two shapes may be deviated from isometry by intrinsic distortions. A major challenge is that non-rigid shapes have large degrees of freedom on how to deform. Nevertheless, irrespective of how they are deformed, they may be aligned such that the geodesic distance between two arbitrary points on two shapes are nearly equal. Such alignment may be expressed by a permutation matrix (a matrix with binary entries) that corresponds to every paired geodesic distance in between the two shapes. The alignment involves searching the space over all possible mappings (that is all the permutations) to locate the one that minimizes the amount of deviation from isometry. A brute-force search to locate the correspondence is not computationally feasible. This thesis introduces a novel approach created to locate such correspondences, in spite of the large solution space that encompasses all possible mappings and the presence of intrinsic distortion. In order to find correspondences between two shapes, the first step is to create a suitable descriptor to accurately describe the deformable shapes. To this end, we developed deformation-invariant metric descriptors. A descriptor constitutes pair-wise geodesic distances among arbitrary number of discrete points that represent the topology of the non-rigid shape. Our descriptor provides isometric-invariant representation of the shape irrespective of its circumstantial deformation. Two isometric-invariant descriptors, representing two candidate deformable shapes, are the input parameters to our optimization algorithm. We then proceed to locate the permutation matrix that aligns the two descriptors, that minimizes the deviation from isometry. Once we have developed such a descriptor, we turn our attention to finding correspondences between non deformable shapes. In this study, we investigate the use of both classical and quantum particle swarm optimization (PSO) algorithms for this task. To explore the merits of variants of PSO, integer optimization involving test functions with large dimensions were performed, and the results and the analysis suggest that quantum PSO is more effective optimization method than its classical PSO counterpart. Further, a scheme is proposed to structure the solution space, composed of permutation matrices, in lexicographic ordering. The search in the solution space is accordingly simplified to integer optimization to find the integer rank of the targeted permutation matrix. Empirical results suggest that this scheme improves the scalability of quantum PSO across large solution spaces. Yet, quantum PSO's global search capability requires assistance in order to more effectively manoeuvre through the local extrema prevalent in the large solution spaces. A mutation based genetic algorithm (GA) is employed to augment the search diversity of quantum PSO when/if the swarm stagnates among the local extrema. The mutation based GA instantly disengages the optimization engine from the local extrema in order to reorient the optimization energy to the trajectories that steer to the global extrema, or the targeted permutation matrix. Our resultant optimization algorithm combines quantum Particle Swarm Optimization (PSO) and mutation based Genetic Algorithm (GA). Empirical results show that the optimization method presented is scalable and efficient on standard hardware across different solution space sizes. The performance of the optimization method, in simulations and on various near-isometric shapes, is discussed. In all cases investigated, the method could successfully identify the correspondence among the non-rigid deformable shapes that were related by isometry.