As teorias científicas surgiram da necessidade do homem entender o funcionamento das coisas. Novos métodos e técnicas são então criados com o objetivo não só de melhor compreender, mas também de desenvolver essas próprias teorias. Nesta dissertação, vamos estudar várias dessas técnicas (aqui chamadas de algoritmos) com o objetivo de obter estados fundamentais em sistemas de spin e de revelar suas possíveis propriedades de auto-organização crítica. No segundo capítulo desta dissertação, apresentamos os algoritmos de otimização: simulated annealing, algoritmo genético, otimização extrema (EO) e evolutivo de Bak-Sneppen (BS). No terceiro capítulo apresentamos o conceito de criticalidade auto-organizada (SOC), usando como exemplo o modelo da pilha de areia. Para uma melhor compreensão da importância da criticalidade auto-organizada, apresentamos vários outros exemplos de onde o fenômeno é observado. No quarto capítulo apresentamos o modelo de relógio quiral de p-estados que será nosso sistema de testes. No caso unidimensional, determinamos a matriz de transferência e utilizamos o teorema de Perron-Frobenius para provar a inexistência de transição de fase a temperaturas finitas a temperaturas finitas. Esboçamos os diagramas de fases dos estados fundamentais que obtivemos de maneira analítica e numérica para os casos de p = 2, 3, 4, 5 e 6, no caso numérico fazendo uso do algoritmo de Bak-Sneppen com sorteio (BSS). Apresentamos ainda um breve estudo do número de mínimos locais para o modelo de relógio quiral de p-estados, para os casos de p = 3 e 4. Por último, no quinto capítulo, propomos uma dinâmica Bak-Sneppen com ruído (BSR) como uma nova técnica de otimização para tratar sistemas discretos. O ruído é introduzido diretamente no espaço de configuração de spins. Conseqüentemente, o fitness (adaptabilidade) passa a assumir valores contínuos, num pequeno intervalo em torno do seu valor original (discreto). Os resultados dessa dinâmica indicam a presença de criticalidade auto-organizada, evidenciada pelo decaimento em leis de potências das correlações espacial e temporal. Também estudamos o método EO e obtivemos uma confirmação numérica de que sua dinâmica exibe um comportamento não crítico com alcance espacial infinito e decaimento exponencial das avalanches. Finalmente, para o modelo de relógio quiral, comparamos a eficiência das três dinâmicas (EO, BSS e BSR) no que tange às suas habilidades de encontrar o estado fundamental do sistema. / In order to understand how things work, man has formulated scientific theories. New methods and techniques have been created not only to increase our understanding on the subject but also to develop and even expand those theories. In this thesis, we study several techniques (here called algorithms) designed with the objective to get the ground states of some spin systems and eventually to reveal possible properties of critical self-organization. In the second chapter, we introduce four fundamental optimization algorithms: simulated annealing, genetics algorithms, extremal optimization (EO) and Bak-Sneppen (BS). In the third chapter we present the concept of self-organized criticality (SOC), using as an example the sandpile model. To understand the importance of the self-organized criticality, we show many other situations where the phenomenon can be observed. In the fourth chapter, we introduce the p-states chiral clock model. This will be our test or toy system. For the one-dimensional case, we first determined the corresponding transfer-matrix and then proved the nonexistence of phase transitions by using the Perron-Frobenius theorem. We calculate the ground state phase diagrams both analytically and numerically in the cases of p = 2, 3, 4, 5 and 6. We also present a brief study of the number of local minima for the cases p = 3 and 4 of the chiral clock model. Finally, in the fifth chapter, we propose a Bak-Sneppen dynamics with noise (BSN) as a new technique of optimization to treat discrete systems. The noise is directly introduced into the spin configuration space. Consequently, the fitness now take values in a continuum but small interval around its original value (discrete). The results of this dynamics indicate the presence of self-organized criticality, which becomes evident with the power law scaling of the spacial and temporal correlations. We also study the EO algorithm and found a numerical con_rmation that it does not show a critical behavior since it has an in_nite space range and an exponential decay of the avalanches. At the end, we compare the e_ciency of the three dynamics (EO, BSD and BSN) for the chiral clock model, concerning their abilities to _nd the system\'s ground state.

A tarefa de planejamento de trajetórias de robôs móveis autônomos consiste em determinar objetivos intermediários para que um robô seja capaz de partir de sua localização inicial e alcançar seu objetivo final. Além do planejamento, é importante definir um método de controle da navegação (seguimento da trajetória) do robô para que ele seja capaz de realizar seu trajeto de forma segura. Este projeto propõe uma abordagem híbrida para planejamento exploratório e execução de trajetórias de robôs móveis autônomos em ambientes indoor. Para o planejamento de trajetória, foram investigados algoritmos de busca em espaço de estados, dando ênfase ao uso de algoritmos evolutivos e algoritmos de otimização por colônia de formigas para a descoberta e otimização da trajetória. O controle da navegação é realizado por meio de comportamentos locais reativos, baseado na exploração e uso de mapas topológicos, os quais permitem uma maior flexibilidade em termos de definição da localização da posição do robô móvel e sobre os detalhes do mapa do ambiente (mapas com informações aproximadas e não métricos). Assim, foi proposto e desenvolvido um método robusto capaz de planejar, mapear e explorar um caminho ótimo ou quase ótimo para que o robô possa navegar e alcançar seu objetivo de forma segura, com pouca informação prévia do ambiente ou mesmo sobre sua localização. Além disso, o robô pode reagir a ambientes com alterações dinâmicas em sua estrutura, considerando por exemplo, elementos dinâmicos como portas que possam ser abertas ou fechadas e passagens que são obstruídas. Por fim, foram realizados diversos testes e simulações a fim de validar o método proposto, com a avaliação da qualidade das soluções encontradas e comparação com outras abordagens tradicionais de planejamento de trajetórias (algoritmos A* e D*). / The task of planning path for autonomous mobile robots consists in determine intermediary goals in order to allow a robot be able to leave its initial location and reach its final goal. Besides the planning, it is important to define a method of navigation control (the trajectory following) of the robot for it be able to do its path safely. This project proposes a hybrid approach to path planning and execution of an autonomous mobile robot in indoor environments. For the path planning, search algorithms in state space have been investigated, with emphasis in evolutionary algorithms and ant colony optimization algorithms for the trajectory search and optimization. The navigation control is done by local reactive behaviors, based on topological maps, which allow more flexibility concerning localization definition of position of the mobile robot and about the details of the environment map (maps with approximate information and not metric). Thus, a robust method able to plan an optimum or almost optimum path for the robot to reach its goal safely has been proposed, with little previous information of the environment. Furthermore, the robot can react to dynamic elements in the environment structure, concerning, for example, dynamic elements such as doors that can be opened or closed and ways that are blocked. Finally, several tests and simulations has been carried out to validate the proposed method, with evaluation of the solutions quality and comparison with others traditional approaches for the path planning task (A* and D* algorithms).

As teorias científicas surgiram da necessidade do homem entender o funcionamento das coisas. Novos métodos e técnicas são então criados com o objetivo não só de melhor compreender, mas também de desenvolver essas próprias teorias. Nesta dissertação, vamos estudar várias dessas técnicas (aqui chamadas de algoritmos) com o objetivo de obter estados fundamentais em sistemas de spin e de revelar suas possíveis propriedades de auto-organização crítica. No segundo capítulo desta dissertação, apresentamos os algoritmos de otimização: simulated annealing, algoritmo genético, otimização extrema (EO) e evolutivo de Bak-Sneppen (BS). No terceiro capítulo apresentamos o conceito de criticalidade auto-organizada (SOC), usando como exemplo o modelo da pilha de areia. Para uma melhor compreensão da importância da criticalidade auto-organizada, apresentamos vários outros exemplos de onde o fenômeno é observado. No quarto capítulo apresentamos o modelo de relógio quiral de p-estados que será nosso sistema de testes. No caso unidimensional, determinamos a matriz de transferência e utilizamos o teorema de Perron-Frobenius para provar a inexistência de transição de fase a temperaturas finitas a temperaturas finitas. Esboçamos os diagramas de fases dos estados fundamentais que obtivemos de maneira analítica e numérica para os casos de p = 2, 3, 4, 5 e 6, no caso numérico fazendo uso do algoritmo de Bak-Sneppen com sorteio (BSS). Apresentamos ainda um breve estudo do número de mínimos locais para o modelo de relógio quiral de p-estados, para os casos de p = 3 e 4. Por último, no quinto capítulo, propomos uma dinâmica Bak-Sneppen com ruído (BSR) como uma nova técnica de otimização para tratar sistemas discretos. O ruído é introduzido diretamente no espaço de configuração de spins. Conseqüentemente, o fitness (adaptabilidade) passa a assumir valores contínuos, num pequeno intervalo em torno do seu valor original (discreto). Os resultados dessa dinâmica indicam a presença de criticalidade auto-organizada, evidenciada pelo decaimento em leis de potências das correlações espacial e temporal. Também estudamos o método EO e obtivemos uma confirmação numérica de que sua dinâmica exibe um comportamento não crítico com alcance espacial infinito e decaimento exponencial das avalanches. Finalmente, para o modelo de relógio quiral, comparamos a eficiência das três dinâmicas (EO, BSS e BSR) no que tange às suas habilidades de encontrar o estado fundamental do sistema. / In order to understand how things work, man has formulated scientific theories. New methods and techniques have been created not only to increase our understanding on the subject but also to develop and even expand those theories. In this thesis, we study several techniques (here called algorithms) designed with the objective to get the ground states of some spin systems and eventually to reveal possible properties of critical self-organization. In the second chapter, we introduce four fundamental optimization algorithms: simulated annealing, genetics algorithms, extremal optimization (EO) and Bak-Sneppen (BS). In the third chapter we present the concept of self-organized criticality (SOC), using as an example the sandpile model. To understand the importance of the self-organized criticality, we show many other situations where the phenomenon can be observed. In the fourth chapter, we introduce the p-states chiral clock model. This will be our test or toy system. For the one-dimensional case, we first determined the corresponding transfer-matrix and then proved the nonexistence of phase transitions by using the Perron-Frobenius theorem. We calculate the ground state phase diagrams both analytically and numerically in the cases of p = 2, 3, 4, 5 and 6. We also present a brief study of the number of local minima for the cases p = 3 and 4 of the chiral clock model. Finally, in the fifth chapter, we propose a Bak-Sneppen dynamics with noise (BSN) as a new technique of optimization to treat discrete systems. The noise is directly introduced into the spin configuration space. Consequently, the fitness now take values in a continuum but small interval around its original value (discrete). The results of this dynamics indicate the presence of self-organized criticality, which becomes evident with the power law scaling of the spacial and temporal correlations. We also study the EO algorithm and found a numerical con_rmation that it does not show a critical behavior since it has an in_nite space range and an exponential decay of the avalanches. At the end, we compare the e_ciency of the three dynamics (EO, BSD and BSN) for the chiral clock model, concerning their abilities to _nd the system\'s ground state.

A tarefa de planejamento de trajetórias de robôs móveis autônomos consiste em determinar objetivos intermediários para que um robô seja capaz de partir de sua localização inicial e alcançar seu objetivo final. Além do planejamento, é importante definir um método de controle da navegação (seguimento da trajetória) do robô para que ele seja capaz de realizar seu trajeto de forma segura. Este projeto propõe uma abordagem híbrida para planejamento exploratório e execução de trajetórias de robôs móveis autônomos em ambientes indoor. Para o planejamento de trajetória, foram investigados algoritmos de busca em espaço de estados, dando ênfase ao uso de algoritmos evolutivos e algoritmos de otimização por colônia de formigas para a descoberta e otimização da trajetória. O controle da navegação é realizado por meio de comportamentos locais reativos, baseado na exploração e uso de mapas topológicos, os quais permitem uma maior flexibilidade em termos de definição da localização da posição do robô móvel e sobre os detalhes do mapa do ambiente (mapas com informações aproximadas e não métricos). Assim, foi proposto e desenvolvido um método robusto capaz de planejar, mapear e explorar um caminho ótimo ou quase ótimo para que o robô possa navegar e alcançar seu objetivo de forma segura, com pouca informação prévia do ambiente ou mesmo sobre sua localização. Além disso, o robô pode reagir a ambientes com alterações dinâmicas em sua estrutura, considerando por exemplo, elementos dinâmicos como portas que possam ser abertas ou fechadas e passagens que são obstruídas. Por fim, foram realizados diversos testes e simulações a fim de validar o método proposto, com a avaliação da qualidade das soluções encontradas e comparação com outras abordagens tradicionais de planejamento de trajetórias (algoritmos A* e D*). / The task of planning path for autonomous mobile robots consists in determine intermediary goals in order to allow a robot be able to leave its initial location and reach its final goal. Besides the planning, it is important to define a method of navigation control (the trajectory following) of the robot for it be able to do its path safely. This project proposes a hybrid approach to path planning and execution of an autonomous mobile robot in indoor environments. For the path planning, search algorithms in state space have been investigated, with emphasis in evolutionary algorithms and ant colony optimization algorithms for the trajectory search and optimization. The navigation control is done by local reactive behaviors, based on topological maps, which allow more flexibility concerning localization definition of position of the mobile robot and about the details of the environment map (maps with approximate information and not metric). Thus, a robust method able to plan an optimum or almost optimum path for the robot to reach its goal safely has been proposed, with little previous information of the environment. Furthermore, the robot can react to dynamic elements in the environment structure, concerning, for example, dynamic elements such as doors that can be opened or closed and ways that are blocked. Finally, several tests and simulations has been carried out to validate the proposed method, with evaluation of the solutions quality and comparison with others traditional approaches for the path planning task (A* and D* algorithms).

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-24T12:12:06Z No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 1937921 bytes, checksum: 0472ffffb70cabf120dc5de86d6626b1 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-24T16:55:00Z (GMT) No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 1937921 bytes, checksum: 0472ffffb70cabf120dc5de86d6626b1 (MD5) / Made available in DSpace on 2017-04-24T16:55:00Z (GMT). No. of bitstreams: 1 eduardopestanadeaguiar.pdf: 1937921 bytes, checksum: 0472ffffb70cabf120dc5de86d6626b1 (MD5) Previous issue date: 2011-08-30 / A presente dissertação tem como objetivo discutir o uso de técnicas de otimização baseadas no gradiente conjugado e de informações de segunda ordem para o treinamento de sistemas de inferência fuzzy singleton e non-singleton. Além disso, as soluções computacionais derivadas são aplicadas aos problemas de classificação de distúrbios múltiplos e isolados em sinais elétricos. Os resultados computacionais, obtidos a partir de dados sintéticos de distúrbios em sinais de tensão, indicam que os sistemas de inferência fuzzy singleton e non-singleton treinados pelos algoritmos de otimização considerados apresentam maior velocidade de convergência e melhores taxas de classificação quando comparados com aqueles treinados pelo algoritmo de otimização baseada em informações de primeira ordem e é bastante competitivo em relação à rede neural artificial perceptron multicamadas - multilayer perceptron (MLP) e ao classificador de Bayes. / This master dissertation aims to discuss the use of optimization techniques based on the conjugated gradient and on second order information for the training of singleton or non-singleton fuzzy inference systems. In addition, the computacional solutions obtained are applied to isolated a multiple disturbances classification problems in electric signals. Computational results obtained from synthetic data from disturbances in electric signals indicate that singleton or non-singleton fuzzy inference systems trained by the considered optimization algorithms present greater convergence speed and better classification rates when compared to those data trained by an optimization algorithm based on first order information and is quite competitive with multilayer perceptron neural network and Bayesian classifier.