A unique mathematical tool is developed to deal with global optimization of a set of engineering problems. These include image processing, mechanical topology optimization, and optimal path planning in a variational framework, as well as some benchmark problems in parameter optimization. The optimization tool in these applications is based on the level set theory by which an evolving contour converges toward the optimum solution. Depending upon the application, the objective function is defined, and then the level set theory is used for optimization. Level set theory, as a member of active contour methods, is an extension of the steepest descent method in conventional parameter optimization to the variational framework. It intrinsically suffers from trapping in local solutions, a common drawback of gradient based optimization methods. In this thesis, methods are developed to deal with this drawbacks of the level set approach. By investigating the current global optimization methods, one can conclude that these methods usually cannot be extended to the variational framework; or if they can, the computational costs become drastically expensive. To cope with this complexity, a global optimization algorithm is first developed in parameter space and compared with the existing methods. This method is called "Spiral Bacterial Foraging Optimization" (SBFO) method because it is inspired by the aggregation process of a particular bacterium called, Dictyostelium Discoideum. Regardless of the real phenomenon behind the SBFO, it leads to new ideas in developing global optimization methods. According to these ideas, an effective global optimization method should have i) a stochastic operator, and/or ii) a multi-agent structure. These two properties are very common in the existing global optimization methods. To improve the computational time and costs, the algorithm may include gradient-based approaches to increase the convergence speed. This property is particularly available in SBFO and it is the basis on which SBFO can be extended to variational framework. To mitigate the computational costs of the algorithm, use of the gradient based approaches can be helpful. Therefore, SBFO as a multi-agent stochastic gradient based structure can be extended to multi-agent stochastic level set method. In three steps, the variational set up is formulated: i) A single stochastic level set method, called "Active Contours with Stochastic Fronts" (ACSF), ii) Multi-agent stochastic level set method (MSLSM), and iii) Stochastic level set method without gradient such as E-ARC algorithm. For image processing applications, the first two steps have been implemented and show significant improvement in the results. As expected, a multi agent structure is more accurate in terms of ability to find the global solution but it is much more computationally expensive. According to the results, if one uses an initial level set with enough holes in its topology, a single stochastic level set method can achieve almost the same level of accuracy as a multi-agent structure can obtain. Therefore, for a topology optimization problem for which a high level of calculations (at each iteration a finite element model should be solved) is required, only ACSF with initial guess with multiple holes is implemented. In some applications, such as optimal path planning, objective functions are usually very complicated; finding a closed-form equation for the objective function and its gradient is therefore impossible or sometimes very computationally expensive. In these situations, the level set theory and its extensions cannot be directly employed. As a result, the Evolving Arc algorithm that is inspired by "Electric Arc" in nature, is proposed. The results show that it can be a good solution for either unconstrained or constrained problems. Finally, a rigorous convergence analysis for SBFO and ACSF is presented that is new amongst global optimization methods in both parameter and variational framework.

Motion planning is central to the efficient operation and autonomy of robots in the industry. Generally, motion planning of industrial robots is treated in a two-step approach. First, a geometric path between the start and goal position is planned where the objective is to achieve as short path as possible together with avoiding obstacles. Alternatively, a pre-defined geometric path is provided by the end user. Second, the velocity profile along the geometric path is calculated accounting for system dynamics together with other constraints. This approach is computationally efficient, but yield sub-optimal solutions as the system dynamics is not considered in the first step when the geometric path is planned. In this thesis, an alternative to the two-step approach is investigated and a trajectory planner is designed and implemented which plans both the geometric path and the velocity profile simultaneously. The motion planning problem is formulated as an optimal control problem, which is solved by a direct collocation method where the trajectory is parametrised by splines, and the spline nodes and knots are used as optimization variables. The implemented trajectory planner is evaluated in simulations, where the planner is applied to a simple planar elbow robot and ABB's SCARA robot IRB 910SC. Trade-off between computation time and optimality is identified and the results indicate that the trajectory planner yields satisfactory solutions. On the other hand, the simulations indicate that it is not possible to apply the proposed method on a real robot in real-time applications without significant modifications in the implementation to decrease the computation time.

This thesis is concerned with the robots' motion planning problem. In particular it is focused on the path planning and motion planning for Autonomously Guided Vehicles (AGVs) in well-structured, two-dimensional static and dynamic environments. Two algorithms are proposed for solving the aforementioned problems. The first algorithm establishes the shortest collision-semi-free path for an AGV from its start point to its goal point, in a two-dimensional static environment populated by simple polygonal obstacles. This algorithm constructs and searches a reduced visibility graph, within the AGV's configuration space, using heuristic information about the problem domain. The second algorithm establishes the time minimal collision-semi-free motion for an AGV, from its start point to is goal point, in a two-dimensional dynamic environment populated by simple polygonal obstacles. This algorithm considers the AGV's spacetime configuration space, thus reducing the dynamic motion planning problem to the static path planning problem. A reduced visibility graph is then constructed and searched using information about the problem domain, in the AGV's space-time configuration space in order to establish the time-minimal motion between the AGV's start and goal configurations. The latter algorithm is extended to solve more complicated instances of the dynamic motion planning problem, where the AGV's environment is populated by obstacles, which change their size as well as their position over time and obstacles, which have piecewise linear motion. The proposed algorithms can be used to efficiently and safely navigate AGVs in well structured environments. For example, for the navigation of an AGV, in industrial environments, where it operates as part of the manufacturing process or in chemical and nuclear plants, where the hostile environment is inaccessible to humans. The main contributions in this thesis are, the systematic study of the V*GRAPH algorithm and identification of its methodic and algorithmic deficiencies; recommendation of corrections and further improvements on the V* GRAPH algorithm, which in turn lead to the proposition of the V*MECHA algorithm for robot path planning; proposition of the D*MECHA algorithm for motion planning in dynamic environments; extension to the D*MECHA algorithm to solve more complicated instances of the dynamic robot motion planning problem; discussion of formal proofs of the proposed algorithms' correctness and optimality and critical comparisons with existing similar algorithms for solving the motion planning problem.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

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.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

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.

Todos os dias a quantidade de veículos nas estradas em todo o mundo está aumentando. Este crescimento combinado com a negligência dos motoristas e alguns fatores externos, tais como estradas mal conservadas e condições climáticas adversas resultaram em um enorme aumento na quantidade de acidentes e, conseqüentemente, de mortes. Atualmente muitos grupos de pesquisa e empresas automotivas estão desenvolvendo e adaptando tecnologias que podem ser incorporadas nos veículos para reduzir esses números. Um exemplo interessante dessas tecnologias é a detecção e classificação de obstáculos móveis (veículos, pessoas, etc.) em ambientes urbanos. Este trabalho apresenta o desenvolvimento de algoritmos para identificação, rastreamento e previsão de obstáculos móveis, determinação de direções proibidas para tráfego do veículo e cálculo de trajetórias livres de colisões. Para isso, foram utilizados dados do sistema de medidas de distância, SICK LMS 291-S05, para monitorar o ambiente a frente do veículo de teste (um automóvel de passeio modificado). Com base nesses dados foi realizado um tratamento computacional através da técnica de Trackers para classificar todos os obstáculos detectados em duas classes principais: os obstáculos estáticos e móveis. Uma vez identificado o obstáculo, este será acompanhado mesmo no caso em que saia do campo de visão do sensor. Após a classificação dos obstáculos presentes no ambiente, suas posições são analisadas e direções proibidas para tráfego são determinadas peloalgoritmo Velocity Obstacle Approach. Finalmente é aplicada a técnica de cálculo de trajetórias E* que gera um caminho suave e livre de colisões. No caso de algum obstáculo obstruir ou gerar risco de colisão com o caminho gerado é possível recalcular a rota sem que o mapa do ambiente seja novamente completamente analisado. Os resultados obtidos demonstraram a aplicabilidade da metodologia utilizada. O algoritmo de Trackers detectou pedestres e veículos e determinou suas características dinâmicas. O algoritmo Velocity Obstacle Approach conseguiu acompanhar os obstáculos e foi capaz de determinar as direções proibidas e, finalmente, o algoritmo E* foi capaz de gerar trajetórias livre de obstáculos em ambientes desconhecidos. / Every day the number of vehicles on the roads around the world is increasing. This growth combined with the negligence of drivers and some external factors such as poorly maintained roads and adverse weather conditions resulted in a huge increase in the number of accidents and hence casualties. Currently many research groups and automotive companies are developing and adapting technologies that can be incorporated into vehicles to reduce these numbers. An interesting example of these technologies is the detection and classification of moving obstacles (vehicles, people, etc.) in urban environments. This dissertation presents the development of algorithms which main objective are identify, track and predict moving obstacles, determine prohibited directions of traffic and calculate collision free trajectories. In order to accomplish with such task, data from the laser sensor SICK LMS 291-S05 later treated using computational resources such as the Trackers technique was used to monitor the environment ahead of the test vehicle (a modified passenger car). The Trackers technique was used to classify all the hurdles identified in two main classes: static and mobile obstacles. Once the obstacle was identified, this still been followed even if they leave the field of vision sensor. After classification of obstacles in the environment, their positions are analyzed and prohibited for traffic directions are determined by the algorithm Velocity Obstacle Approach. Finally the technique is applied to calculate trajectories of E* that generates a smooth path and free of collisions. If any obstacle block, or create a risk of collision through the generated path, the trajectory can be recalculated without the need to fully re-analyze de environment map. The results demonstrated the applicability of the methodology used. The Trackers algorithm has detected pedestrians and vehicles determining their dynamic characteristics. The algorithm Velocity Obstacle Approach keep up with the obstacles and was able to determine the prohibited directions and, finally, E* the algorithm was able to generate obstacle-free paths in unknown environments.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-03-27T13:16:05Z No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-03-27T13:40:24Z (GMT) No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Made available in DSpace on 2018-03-27T13:40:24Z (GMT). No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) Previous issue date: 2018-02-08 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esse trabalho apresenta uma metodologia para a concepção de missões autônomas utilizando robôs móveis com tração diferencial em ambientes internos. As missões consistem em deslocar o robô até uma posição objetivo partindo de uma pose inicial. Para que as missões ocorram com sucesso, são implementados algoritmos de localização e planejamento de caminhos. Para localização, foi utilizado Filtro de Kalman Estendido (do inglês, Extended Kalman Filter EKF) para fundir a odometria com visão computacional. A visão é responsável por encontrar marcadores artificiais conhecidos como Ar codes que são alocados no ambiente. O planejamento é caracterizado por uma forma híbrida que corresponde a união de um método deliberativo e reativo. No Planejamento deliberativo, foi proposto e utilizado o método Direct-DRRT* cuja base é oriunda do RRT (Rapidly Exploring Random Tree). Além do RRT, esse planejador também apresenta características de dois outros métodos já presentes na literatura: RRT* e DRRT. O planejador deliberativo enviará para o reativo um conjunto de sub-objetivos que conecta a posição em que o robô se encontra até o objetivo final. O planejamento reativo é aplicado durante a missão e é o responsável pelo desvio de obstáculos dinâmicos que não foram mapeados. No Reativo, é utilizado o método dos Campos Potenciais Artificiais (CPA), que também se comporta como o controlador do robô durante a navegação. Para encontrar os obstáculos, utilizou-se o sensor de profundidade Asus Xtion, pois, a partir das imagens geradas por esse sensor, é possível encontrar as distâncias que os bloqueios se encontram. As informações desse sensor também será de grande valia na atualização do mapa. O sistema é integrado através da framework ROS (Robot Operating System). Todos os algoritmos foram implementados por meio da linguagem de programação Python. Os resultados do trabalho foram apresentados por meio do simulador Gazebo e testes práticos a partir da plataforma P3DX. Foram analisados o comportamento do robô em alguns problemas que podem ocorrer durante a navegação, como o sequestro e aparecimento mínimos locais. Ao final desse trabalho, apresentou-se a melhoria nos resultados do planejador de caminhos Direct-DRRT*, onde foi possível constatar a queda no tempo para obter um caminho, a quantidade de iterações, de nós e do comprimento do caminho em comparação aos outros métodos. No que tange à localização, essa dissertação obteve significativas melhoras comparado com o método que utiliza somente a odometria. Além desse resultado, esse trabalho também obteve sucesso em apresentar uma solução para a implementação de missões autônomas. / This work presents a design methodology for autonomous missions using mobile robots with differential traction in indoor environments. The missions consist of moving the robot to a goal position starting from an initial pose. For missions success, it is necessary to implement localization and path planning algorithms. For localization, Extended Kalman Filters (EKF) used to fuse odometry with computational vision. The view is responsible for finding artificial markers known as Ar codes that are presented in the environment. The planning is characterized by a hybrid form that corresponds to the union of a deliberative and reactive methods. In the Deliberative Planning, the Direct-DRRT * method, whose base is derived from the Rapidly Exploring Random Tree (RRT), is proposed and used. In addition to the RRT, this planner also presents characteristics of two other methods already presented in the literature, i.e. RRT * and DRRT. The deliberative planner sends to the reactive a set of sub-objectives that connects the initial position to the final goal. Reactive planning is applied during the mission and it is responsible for the dynamic obstacles avoidance that have not been mapped. In the reactive, the Artificial Potential Fields (APF) method is used, which also behaves as the robot controller during navigation. To find the obstacles, we use the sensor Asus Xtion, due to the possibility to find the distances that the locks are in the images generated by this sensor. All the algorithms were implemented through the programming language Python. The results of the work were presented through the simulator Gazebo and practical tests using the P3DX platform. We analyzed the robot behavior in some problems that may occur during navigation, such as kidnapped and local minimum appearance. At the end, the improvement in the results of the Direct-DRRT * path planner is also presented. It is possible to verify the decrease in the time to obtain a path, the number of iterations of nodes and the path length in comparison to other methods. Regarding the location, this dissertation has obtained significant improvements when compared to the methods that use only odometry. Besides, the work was also successful in presenting a solution for the autonomous missions implementation.