Autonomous vehicles have increasingly become an attractive field due its promising capabilities of improvements regarding safety, comfort, traffic flow etc. A required attribute for those vehicles is the ability of autonomously compute its path towards a destination point. The path must be planned considering the constructive aspects of the vehicle in order to guarantee the maneuver feasibility. This work consists on computing a feasible path for autonomous vehicles with non-holonomic constraints. Piecewise linear continuouscurvature paths constituted of clothoids, circular arcs, and straight lines are used for this purpose, providing passenger\'s comfort. The road network is modeled from GPS (Global Positioning System) vehicle trajectories by defining lanes, roundabouts and intersections. GPS points are used later to parameterize lanes using clothoids and to extract roundabout centers and radii. This approach provides a sparse road network model since GPS points are replaced by parameterized curves. The information about connections between roads coming from the model is used by a global path planner, which computes a minimal length route from the vehicle current position to the destination point. After that, path planners compute intersection and roundabout paths depending on the nature of connections between roads. Also, lanes changes are performed to obey traffic rules. These three path planners that connects adjacent roads use clothoids, circular arc, and straight lines as interpolating curves whose curvature is constrained to that the vehicle can perform: the intersection path planner uses only a minimal amount of steering to perform the maneuver, increasing the comfort level; the roundabout path planner takes the roundabout center and radius as well as parameters that defines the entrance and exit maneuvers to compute the path; the lane change path planner connects lanes belonging to the same road with a prescribed longitudinal traveled distance depending on whether this maneuver is required. In the end, an global continuous-curvature path is generated. As the result of this work, a real urban scenario is modeled and the proposed approaches are validated. / Veículos autônomos têm cada vez mais se tornado um campo atraente de pesquisa devido às suas capacidades promissoras de melhorias em segurança, conforto, fluxo de tráfego, etc. Um atributo necessário para esses veículos é a capacidade de calcular, de forma autônoma, o seu caminho para um ponto de destino. O percurso deve ser planejado considerando os aspectos construtivos do veículo para que a viabilidade das manobras a serem executadas seja garantida. Este trabalho consiste no planejamento de trajetória para veículos autônomos com restrições não-holonômicas. Utilizam-se, para esse efeito, trajetórias cuja curvatura seja contínua e linear por partes, constituídas por clotóides, arcos de circunferência e retas, de forma a proporcionar conforto aos passageiros. A topologia de vias é modelada a partir de trajetórias definidas por pontos de GPS (Sistema de Posicionamento Global), definindo pistas, rotatórias e cruzamentos. Pontos de GPS são usados posteriormente para parametrizar as pistas usando clotóides a para extrair centros e raios das rotatórias. Essa abordagem proporciona um modelo esparso de topologia de vias uma vez que pontos de GPS são substituídos por curvas parametrizadas. A informação a cerca das conexões entre vias advinda do modelo é usada por um planejador de caminho global, o qual calcula a rota mais curta da posição atual do veículo até seu ponto de destino. Após essa etapa, planejadores calculam caminhos em cruzamentos e rotatórias dependendo do tipo de conexão entre as vias. Também, trocas de faixa devem ser executadas para obedecer regras de trânsito. Esses três planejadores de caminho usam clotóides, arcos de circunferência e retas como curvas interpoladoras, cuja curvatura é restrita a valores que o veículo é capaz de executar: o planejador de caminho em cruzamentos usa apenas um mínimo de velocidade de rotação do volante do veículo para executar a manobra, melhorando o nível de conforto; o planejador de caminho em rotatórias requer as coordenadas do centro e o raio da rotatória, bem como parâmetros que definem as manobras na entrada e na saída da rotatória para calcular o caminho; o planejador de caminho para troca de faixa conecta pistas pertencentes à mesma via com uma distância longitudinal do caminho previamente determinada. Ao final, um caminho com curvatura globalmente contínua é gerado. Como resultado deste trabalho, um cenário urbano real é modelado e os métodos propostos são validados.

Autonomous vehicles have increasingly become an attractive field due its promising capabilities of improvements regarding safety, comfort, traffic flow etc. A required attribute for those vehicles is the ability of autonomously compute its path towards a destination point. The path must be planned considering the constructive aspects of the vehicle in order to guarantee the maneuver feasibility. This work consists on computing a feasible path for autonomous vehicles with non-holonomic constraints. Piecewise linear continuouscurvature paths constituted of clothoids, circular arcs, and straight lines are used for this purpose, providing passenger\'s comfort. The road network is modeled from GPS (Global Positioning System) vehicle trajectories by defining lanes, roundabouts and intersections. GPS points are used later to parameterize lanes using clothoids and to extract roundabout centers and radii. This approach provides a sparse road network model since GPS points are replaced by parameterized curves. The information about connections between roads coming from the model is used by a global path planner, which computes a minimal length route from the vehicle current position to the destination point. After that, path planners compute intersection and roundabout paths depending on the nature of connections between roads. Also, lanes changes are performed to obey traffic rules. These three path planners that connects adjacent roads use clothoids, circular arc, and straight lines as interpolating curves whose curvature is constrained to that the vehicle can perform: the intersection path planner uses only a minimal amount of steering to perform the maneuver, increasing the comfort level; the roundabout path planner takes the roundabout center and radius as well as parameters that defines the entrance and exit maneuvers to compute the path; the lane change path planner connects lanes belonging to the same road with a prescribed longitudinal traveled distance depending on whether this maneuver is required. In the end, an global continuous-curvature path is generated. As the result of this work, a real urban scenario is modeled and the proposed approaches are validated. / Veículos autônomos têm cada vez mais se tornado um campo atraente de pesquisa devido às suas capacidades promissoras de melhorias em segurança, conforto, fluxo de tráfego, etc. Um atributo necessário para esses veículos é a capacidade de calcular, de forma autônoma, o seu caminho para um ponto de destino. O percurso deve ser planejado considerando os aspectos construtivos do veículo para que a viabilidade das manobras a serem executadas seja garantida. Este trabalho consiste no planejamento de trajetória para veículos autônomos com restrições não-holonômicas. Utilizam-se, para esse efeito, trajetórias cuja curvatura seja contínua e linear por partes, constituídas por clotóides, arcos de circunferência e retas, de forma a proporcionar conforto aos passageiros. A topologia de vias é modelada a partir de trajetórias definidas por pontos de GPS (Sistema de Posicionamento Global), definindo pistas, rotatórias e cruzamentos. Pontos de GPS são usados posteriormente para parametrizar as pistas usando clotóides a para extrair centros e raios das rotatórias. Essa abordagem proporciona um modelo esparso de topologia de vias uma vez que pontos de GPS são substituídos por curvas parametrizadas. A informação a cerca das conexões entre vias advinda do modelo é usada por um planejador de caminho global, o qual calcula a rota mais curta da posição atual do veículo até seu ponto de destino. Após essa etapa, planejadores calculam caminhos em cruzamentos e rotatórias dependendo do tipo de conexão entre as vias. Também, trocas de faixa devem ser executadas para obedecer regras de trânsito. Esses três planejadores de caminho usam clotóides, arcos de circunferência e retas como curvas interpoladoras, cuja curvatura é restrita a valores que o veículo é capaz de executar: o planejador de caminho em cruzamentos usa apenas um mínimo de velocidade de rotação do volante do veículo para executar a manobra, melhorando o nível de conforto; o planejador de caminho em rotatórias requer as coordenadas do centro e o raio da rotatória, bem como parâmetros que definem as manobras na entrada e na saída da rotatória para calcular o caminho; o planejador de caminho para troca de faixa conecta pistas pertencentes à mesma via com uma distância longitudinal do caminho previamente determinada. Ao final, um caminho com curvatura globalmente contínua é gerado. Como resultado deste trabalho, um cenário urbano real é modelado e os métodos propostos são validados.

A capacidade de encontrar e aprender as melhores trajetórias que levam a um determinado objetivo proposto num ambiente e uma característica comum a maioria dos organismos que se movimentam. Dentre outras, essa e uma das capacidades que têm sido bastante estudadas nas ultimas décadas. Uma consequência direta deste estudo e a sua aplicação em sistemas artificiais capazes de se movimentar de maneira inteligente nos mais variados tipos de ambientes. Neste trabalho, realizamos uma abordagem múltipla do problema, onde procuramos estabelecer nexos entre modelos fisiológicos, baseados no conhecimento biológico disponível, e modelos de âmbito mais prático, como aqueles existentes na área da ciência da computação, mais especificamente da robótica. Os modelos estudados foram o aprendizado biológico baseado em células de posição e o método das funções potencias para planejamento de trajetórias. O objetivo nosso era unificar as duas idéias num formalismo de redes neurais. O processo de aprendizado de trajetórias pode ser simplificado e equacionado em um modelo matemático que pode ser utilizado no projeto de sistemas de navegação autônomos. Analisando o modelo de Blum e Abbott para navegação com células de posição, mostramos que o problema pode ser formulado como uma problema de aprendizado não-supervisionado onde a estatística de movimentação no meio passa ser o ingrediente principal. Demonstramos também que a probabilidade de ocupação de um determinado ponto no ambiente pode ser visto como um potencial que tem a propriedade de não apresentar mínimos locais, o que o torna equivalente ao potencial usado em técnicas de robótica como a das funções potencias. Formas de otimização do aprendizado no contexto deste modelo foram investigadas. No âmbito do armazenamento de múltiplos mapas de navegação, mostramos que e possível projetar uma rede neural capaz de armazenar e recuperar mapas navegacionais para diferentes ambientes usando o fato que um mapa de navegação pode ser descrito como o gradiente de uma função harmônica. A grande vantagem desta abordagem e que, apesar do baixo número de sinapses, o desempenho da rede e muito bom. Finalmente, estudamos a forma de um potencial que minimiza o tempo necessário para alcançar um objetivo proposto no ambiente. Para isso propomos o problema de navegação de um robô como sendo uma partícula difundindo em uma superfície potencial com um único ponto de mínimo. O nível de erro deste sistema pode ser modelado como uma temperatura. Os resultados mostram que superfície potencial tem uma estrutura ramificada.

A capacidade de encontrar e aprender as melhores trajetórias que levam a um determinado objetivo proposto num ambiente e uma característica comum a maioria dos organismos que se movimentam. Dentre outras, essa e uma das capacidades que têm sido bastante estudadas nas ultimas décadas. Uma consequência direta deste estudo e a sua aplicação em sistemas artificiais capazes de se movimentar de maneira inteligente nos mais variados tipos de ambientes. Neste trabalho, realizamos uma abordagem múltipla do problema, onde procuramos estabelecer nexos entre modelos fisiológicos, baseados no conhecimento biológico disponível, e modelos de âmbito mais prático, como aqueles existentes na área da ciência da computação, mais especificamente da robótica. Os modelos estudados foram o aprendizado biológico baseado em células de posição e o método das funções potencias para planejamento de trajetórias. O objetivo nosso era unificar as duas idéias num formalismo de redes neurais. O processo de aprendizado de trajetórias pode ser simplificado e equacionado em um modelo matemático que pode ser utilizado no projeto de sistemas de navegação autônomos. Analisando o modelo de Blum e Abbott para navegação com células de posição, mostramos que o problema pode ser formulado como uma problema de aprendizado não-supervisionado onde a estatística de movimentação no meio passa ser o ingrediente principal. Demonstramos também que a probabilidade de ocupação de um determinado ponto no ambiente pode ser visto como um potencial que tem a propriedade de não apresentar mínimos locais, o que o torna equivalente ao potencial usado em técnicas de robótica como a das funções potencias. Formas de otimização do aprendizado no contexto deste modelo foram investigadas. No âmbito do armazenamento de múltiplos mapas de navegação, mostramos que e possível projetar uma rede neural capaz de armazenar e recuperar mapas navegacionais para diferentes ambientes usando o fato que um mapa de navegação pode ser descrito como o gradiente de uma função harmônica. A grande vantagem desta abordagem e que, apesar do baixo número de sinapses, o desempenho da rede e muito bom. Finalmente, estudamos a forma de um potencial que minimiza o tempo necessário para alcançar um objetivo proposto no ambiente. Para isso propomos o problema de navegação de um robô como sendo uma partícula difundindo em uma superfície potencial com um único ponto de mínimo. O nível de erro deste sistema pode ser modelado como uma temperatura. Os resultados mostram que superfície potencial tem uma estrutura ramificada.

A capacidade de encontrar e aprender as melhores trajetórias que levam a um determinado objetivo proposto num ambiente e uma característica comum a maioria dos organismos que se movimentam. Dentre outras, essa e uma das capacidades que têm sido bastante estudadas nas ultimas décadas. Uma consequência direta deste estudo e a sua aplicação em sistemas artificiais capazes de se movimentar de maneira inteligente nos mais variados tipos de ambientes. Neste trabalho, realizamos uma abordagem múltipla do problema, onde procuramos estabelecer nexos entre modelos fisiológicos, baseados no conhecimento biológico disponível, e modelos de âmbito mais prático, como aqueles existentes na área da ciência da computação, mais especificamente da robótica. Os modelos estudados foram o aprendizado biológico baseado em células de posição e o método das funções potencias para planejamento de trajetórias. O objetivo nosso era unificar as duas idéias num formalismo de redes neurais. O processo de aprendizado de trajetórias pode ser simplificado e equacionado em um modelo matemático que pode ser utilizado no projeto de sistemas de navegação autônomos. Analisando o modelo de Blum e Abbott para navegação com células de posição, mostramos que o problema pode ser formulado como uma problema de aprendizado não-supervisionado onde a estatística de movimentação no meio passa ser o ingrediente principal. Demonstramos também que a probabilidade de ocupação de um determinado ponto no ambiente pode ser visto como um potencial que tem a propriedade de não apresentar mínimos locais, o que o torna equivalente ao potencial usado em técnicas de robótica como a das funções potencias. Formas de otimização do aprendizado no contexto deste modelo foram investigadas. No âmbito do armazenamento de múltiplos mapas de navegação, mostramos que e possível projetar uma rede neural capaz de armazenar e recuperar mapas navegacionais para diferentes ambientes usando o fato que um mapa de navegação pode ser descrito como o gradiente de uma função harmônica. A grande vantagem desta abordagem e que, apesar do baixo número de sinapses, o desempenho da rede e muito bom. Finalmente, estudamos a forma de um potencial que minimiza o tempo necessário para alcançar um objetivo proposto no ambiente. Para isso propomos o problema de navegação de um robô como sendo uma partícula difundindo em uma superfície potencial com um único ponto de mínimo. O nível de erro deste sistema pode ser modelado como uma temperatura. Os resultados mostram que superfície potencial tem uma estrutura ramificada.

Submitted by Clebson Anjos (clebson.leandro54@gmail.com) on 2016-02-15T20:03:45Z No. of bitstreams: 1 arquivototal.pdf: 2424729 bytes, checksum: 0b742be3286a70e0901c3d5a00813f6f (MD5) / Made available in DSpace on 2016-02-15T20:03:45Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2424729 bytes, checksum: 0b742be3286a70e0901c3d5a00813f6f (MD5) Previous issue date: 2015-08-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / One of the main issues related to the mobile robotics area is to find the most efficient way to perform the navigation from one point to another over environments, considering maximum safety and spending as less as possible time and computer resources. From this perspective, the aim of this work was to specify improved heuristics that could be applicable to cost functions of key A* based algorithms and use, more efficiently, the available computational resources. In this way, our approach aimed at minimizing the amount of collisions, the length of paths, and the processing time by minimizing the importance of g(n) term, which accounts for storing information from past steps of A* family algorithms. To show the effects of this modification, a survey of the best search strategies in dynamic and static environments was carried out and, after that, we analyzed the four best and latest algorithms, according to the specialized literature. Some comparisons have been made considering static and highly dynamic environments with different directions and search parameters to measure the quality of generated paths. Then, these algorithms were again analyzed with their cost functions modified according to our approach. The results of the comparison show that the R* algorithm, with forward search, is the most efficient for different spaces and searches. However, the change in their respective cost functions provided a significant improvement in the already excellent results achieved by the algorithms. In static environments, this modification showed up to be more effective for large and complex problems, which are commonly used for real robots. In highly dynamic environments, the cost function modification provided a considerable reduction in the time of planning and number of iterations to find the goal, as well as reductions in the memory utilization. / Uma das principais questões relacionados ao tema da robótica móvel é descobrir a maneira mais eficiente para realizar a navegação, de um ponto a outro no ambiente, com máxima segurança e despendendo a menor quantidade de tempo e de recursos computacionais possível. À vista disso, o presente trabalho se motiva a desenvolver uma melhoria heurística que possa ser aplicável às funções custo dos principais algoritmos baseados na família A* e que propõe utilizar, de forma mais eficiente, os recursos computacionais disponíveis, aperfeiçoando assim, os resultados obtidos através dos principais algoritmos de buscas aplicados à robótica móvel. A mesma tem o objetivo de minimizar a quantidade de colisões, a duração do trajeto, bem como o tempo de processamento através da minimização da importância da variável g(n) - responsável em armazenar informações subutilizadas do passado dos algoritmos. Para visualizar os efeitos dessa modificação, um levantamento das melhores estratégias de busca em ambiente estático e dinâmico foi realizado e, através deste, foram analisados os quatro melhores e mais atuais algoritmos destacados pela literatura técnica especializada. Algumas comparações foram efetuadas considerando ambientes estáticos e altamente dinâmico com diferentes direções de busca e parâmetros que visavam mensurar a qualidade das trajetórias geradas. Em seguida, esses foram novamente analisados com suas respectivas funções custo modificada. Os resultados da comparação demonstraram que o algoritmo R*, com direção de busca direta, é o mais eficiente para diferentes espaços e pesquisas. No entanto, a modificação em suas respectivas funções custo proporcionou uma melhora significativa nos resultados conquistados pelos algoritmos originais. Em ambientes estáticos, esta modificação se mostrou mais eficaz para problemas grandes e complexos, os que são efetivamente utilizados por robôs reais. Em ambientes altamente dinâmicos, a mesma apresentou uma redução considerável no tempo de planejamento e no número de iterações para localizar o objetivo, bem como reduziu a utilização de memória o que, consequentemente, tornou os robôs mais ágeis e habilidosos.

Made available in DSpace on 2014-12-17T14:55:02Z (GMT). No. of bitstreams: 1 AndreMS.pdf: 553881 bytes, checksum: b2c5c5f17b0c8205f6f6da967252fae4 (MD5) Previous issue date: 2007-07-10 / ?This work presents the localization and path planning systems for two robots: a non-instrumented humanoid and a slave wheeled robot. The localization of wheeled robot is made using odometry information and landmark detection. These informations are fused using a Extended Kalman Filter. The relative position of humanoid is acquired fusing (using another Kalman Filter) the wheeled robot pose with the characteristics of the landmark on the back of humanoid. Knowing the wheeled robot position and the humanoid relative position in relation to it, we acquired the absolute position of humanoid. The path planning system was developed to provide the cooperative movement of the two robots,incorporating the visibility restrictions of the robotic system / ?Esse trabalho apresentar? os sistemas de localiza??o e planejamento de caminho para um sistema rob?tico formado por um human?ide n?o instrumentado e um rob? escravo com rodas. O objetivo do sistema ? efetuar a navega??o do human?ide, que n?o possui sensores mas que pode ser remotamente controlado por infra-vermelhos, utilizando um rob? escravo com rodas. O rob? com rodas dever? se posicionar atr?s do human?ide e, atrav?s da imagem, estabelecer o posicionamento relativo do human?ide em rela??o a ele. A localiza??o do rob? com rodas ser? obtida fundindo informa??es de odometria e detec??o de marcos utilizando o Filtro de Kalman Extendido. A posi??o relativa do hu-man?ide ser? encontrada a partir da fus?o da pose do rob? com rodas juntamente com as caracter?sticas do marco fixado nas costas do human?ide utilizando outro Filtro de Kalman. Sabendo a posi??o do rob? com rodas e a posi??o relativa do human?ide em rela??o a ele tem-se a posi??o absoluta do human?ide. O planejador de caminho foi desenvolvido de forma a proporcionar a movimenta??o cooperativa dos dois rob?s incorporando as restri??es de visibilidade existente do sistema rob?tico.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-10-17T23:47:38Z No. of bitstreams: 1 YuriSarmentoSilveira_DISSERT.pdf: 7722507 bytes, checksum: 6d1444bedd713386875e463932606d82 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-10-18T00:00:53Z (GMT) No. of bitstreams: 1 YuriSarmentoSilveira_DISSERT.pdf: 7722507 bytes, checksum: 6d1444bedd713386875e463932606d82 (MD5) / Made available in DSpace on 2017-10-18T00:00:53Z (GMT). No. of bitstreams: 1 YuriSarmentoSilveira_DISSERT.pdf: 7722507 bytes, checksum: 6d1444bedd713386875e463932606d82 (MD5) Previous issue date: 2016-12-16 / O processo de planejamento de caminho ? um problema bastante estudado na rob?tica. A capacidade de analisar o ambiente e definir a sequ?ncia de a??es que levam um rob? de uma localiza??o inicial at? uma localiza??o final desejada, sem colidir com os obst?culos presentes no ambiente, ? uma habilidade fundamental requerida para a cria??o de sistemas rob?ticos aut?nomos que possam executar diversas fun??es. Nesta disserta??o, apresenta-se um estudo sucinto do estado da arte na ?rea de planejamento de caminhos para sistemas rob?ticos aut?nomos, de forma a contextualizar o tema abordado neste trabalho. Cada m?todo de planejamento possui sua pr?pria estrat?gia de explora??o do ambiente e planejamento do caminho. Nesta disserta??o ? proposto um novo m?todo de planejamento de caminho para rob?s. No m?todo proposto, o espa?o livre do ambiente ? coberto de forma aproximada por um conjunto denominado Espuma Aleat?ria, a qual ? composta por subconjuntos convexos superpostos denominados Bolhas. A partir da localiza??o inicial, novas bolhas s?o criadas aleatoriamente na superf?cie da espuma, que se propaga pelo espa?o livre, com comportamento semelhante ? propaga??o de frentes de onda, gerando uma ?rvore de busca, at? atingir a localiza??o final. Desta forma, ? poss?vel encontrar uma sequ?ncia de bolhas concatenadas, denominada Ros?rio, que conecta a localiza??o final ? inicial. Um caminho v?lido pode ser facilmente obtido dentro do espa?o de manobra definido pelo ros?rio. O processo de busca no m?todo proposto ? determinado por apenas dois par?metros. Crit?rios para a sua sintonia s?o estudados e apresentados neste trabalho. De forma a validar o m?todo proposto, o seu desempenho foi avaliado atrav?s de simula??es computacionais para diferentes estudos de caso. / Path planning is a well studied problem in robotics. The capability of analyzing the environment and defining a sequence of actions that leads a robot from an initial location to a final desired location, without colliding with obstacles, is a fundamental ability when creating autonomous robotic systems that can perform various functions. In order to contextualize the theme addressed in this work, a succinct study of the state-of-the-art on path planning for autonomous robotic systems is presented. Each planning method has its own strategy to explore the ambient and plan the path. In this dissertation, a new robot path planning method is proposed. In the proposed method, the ambient free space is partially covered by a set called Random Foam, composed of the union of overlapping convex subsets called Bubbles. Starting from the initial robot localization, new bubbles are randomly created on the surface of the foam, that propagates through the free space, with a behavior similar to a wave front propagation, generating a search tree that grows until reaching the desired final robot localization. In this way, it is possible to find a sequence of concatenated bubbles, called Rosary, connecting the desired final localization to the initial localization of the robot. A valid path contained in the maneuvering space defined by the rosary can be easily found. In the proposed method, the search process is guided by only two parameters. Tuning criteria for these parameters are studied and presented in this work. In order to validate the proposed path planning method, its performance was evaluated through computer simulations of different case studies.

Submitted by Marcos Roberto Gomes (mrobertosg@gmail.com) on 2017-06-22T15:28:21Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-23T14:38:14Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-06-23T14:44:39Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5) / Made available in DSpace on 2017-06-23T14:44:39Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Rodrigo_Farias_Araujo.pdf: 2432590 bytes, checksum: a0accf6a453257550a0ea9f75b50b687 (MD5) Previous issue date: 2017-03-30 / This work presents a new method of optimization applied to different classes of problems, such as non-convex and convex. The methodology consists in the use the counterexample generated from the model checking technique based on Boolean satisfiability theory (SAT) and satisfiability modulo theory (SMT), to guide the optimization process. Three algorithms of optimization are developed: Generic Algorithm, applied to any class of optimization problem, it will be used in the optimization of non-convex functions, Simplified Algorithm, used in the optimization of functions in which there is some previous knowledge, e. g., semi-defined or defined positive functions and Fast Algorithm, used to optimize convex functions. In addition, convergence proofs are provided for the respective algorithms. The algorithms are implemented using two model verifiers, CBMC which uses the SAT-based MiniSAT solver as back-end, and the ESBMC, which supports SMT-based solvers, such as Z3, Boolector and MathSAT. For perfomance evaluation, the algorithms are applied to a set of thirty functions taken from the literature and used to test optimization algorithms, they are also compared with traditional optimization algorithms usually used in solving non-convex optimization problems, such as genetic algorithm, particle swarm, pattern search, simulated annealing and nonlinear programming. Through the analysis of the results it can be concluded that the developed algorithms are suitable the classes of functions for which they were developed and have a higher rate of success in the search for the optimal value in comparison with the other algorithms. Finally, the developed methodology is applied to solve optimization problems in the context of the two-dimensional path planning for autonomous mobile robots. / Este trabalho apresenta um novo método de otimização aplicado a diferentes classes de problemas, como não-convexos e convexos. A metodologia consiste na utilização do contraexemplo gerado a partir da técnica de verificação de modelos, baseada na teoria de satisfatibilidade booleana (SAT) ou na teoria do módulo de satisfatibilidade (SMT), para guiar o processo de otimização. São desenvolvidos três algoritmos de otimização, são eles: Algoritmo Genérico, aplicado a qualquer classe de problema de otimização, neste será utilizado na otimização de funções não-convexas, Algoritmo Simplificado, empregado na otimização de funções nas quais tem-se algum conhecimento prévio, por exemplo, funções semi-definidas ou definidas positivas e Algoritmo Rápido, utilizado para otimização de funções convexas. Adicionalmente, são fornecidas as provas de convergência para os respectivos algoritmos. Os algoritmos são implementados utilizando dois verificadores de modelos, o CBMC que utiliza como back-end o solucionador MiniSAT baseado em SAT, e o ESBMC, que tem suporte aos solucionadores baseados em SMT, como: Z3, Boolector e MathSAT. Para avaliação de desempenho, os algoritmos são aplicados a um conjunto de trinta funções retiradas da literatura e utilizadas para teste de algoritmos de otimização, os mesmos também são comparados com algoritmos de otimização tradicionais usualmente empregados na resolução de problemas de otimização não-convexa, como: algoritmo genético, enxame de partícula, busca de padrões, recozimento simulado e programação não-linear. Através da análise dos resultados pode-se concluir que os algoritmos desenvolvidos são adequados as classes de funções para os quais foram desenvolvidos e possuem maior taxa de acerto na busca pelo valor ótimo em comparação com os outros algoritmos. Finalmente a metodologia desenvolvida é aplicada para resolver problemas de otimização no contexto de planejamento de caminhos bidimensionais para robô móveis autônomos.

Made available in DSpace on 2014-12-17T14:56:03Z (GMT). No. of bitstreams: 1 DiogoPFP.pdf: 929475 bytes, checksum: cfb18a5bf43c92f6830aa123446e6f33 (MD5) Previous issue date: 2001-08-31 / The main task and one of the major mobile robotics problems is its navigation process. Conceptualy, this process means drive the robot from an initial position and orientation to a goal position and orientation, along an admissible path respecting the temporal and velocity constraints. This task must be accomplished by some subtasks like robot localization in the workspace, admissible path planning, trajectory generation and motion control. Moreover, autonomous wheeled mobile robots have kinematics constraints, also called nonholonomic constraints, that impose the robot can not move everywhere freely in its workspace, reducing the number of feasible paths between two distinct positions. This work mainly approaches the path planning and trajectory generation problems applied to wheeled mobile robots acting on a robot soccer environment. The major dificulty in this process is to find a smooth function that respects the imposed robot kinematic constraints. This work proposes a path generation strategy based on parametric polynomials of third degree for the 'x' and 'y' axis. The 'theta' orientation is derived from the 'y' and 'x' relations in such a way that the generated path respects the kinematic constraint. To execute the trajectory, this work also shows a simple control strategy acting on the robot linear and angular velocities / Um dos maiores problemas em rob?tica m?vel diz respeito ? sua navega??o. Conceitualmente, o ato de navegar em rob?tica consiste em guiar um rob? em um espa?o de trabalho durante um determinado intervalo de tempo, por um caminho que possa ser percorrido e que leve o rob? de uma posi??o e orienta??o iniciais para uma posi??o e orienta??o finais. Esta ? a principal tarefa que um rob? m?vel deve executar. Ela implica em subproblemas que s?o a localiza??o do rob? no espa?o de trabalho, o planejamento de um caminho admiss?vel, a gera??o de uma trajet?ria e, por fim, a sua execu??o. Al?m disso, rob?s m?veis aut?nomos com rodas possuem restri??es cinem?ticas, chamadas tamb?m de restri??es n?o-holon?micas, que fazem com que o rob? n?o possa se mover livremente em seu espa?o de trabalho, limitando a quantidade de caminhos admiss?veis entre duas posi??es distintas. Este trabalho aborda principalmente os subproblemas do planejamento de caminho e gera??o de trajet?ria aplicado a minirrob?s m?veis com rodas que atuam em um projeto de futebol de rob?s. O maior desafio para a navega??o destes ve?culos ? determinar uma fun??o cont?nua que respeite suas restri??es cinem?ticas e evolua no tempo segundo as restri??es impostas pelo problema quanto ? posi??o e orienta??o iniciais e finais e quanto ? velocidade do movimento. Prop?e-se uma estrat?gia de gera??o de caminho baseada em polin?mios param?tricos de terceiro grau em 'x' e 'y'. A orienta??o 'theta' do minirrob? ? obtida da rela??o entre 'y' e 'x' de modo que os caminhos gerados respeitem a restri??o cinem?tica imposta. Para que a trajet?ria seja executada e os resultados experimentais validados ? apresentada uma estrat?gia simples de controle que atua sobre as velocidades linear e angular desenvolvidas pelo rob? m?vel