Contribuições aos Processos de Clustering com Base em Métricas não-Euclidianas

In this work we present a new clustering method that groups up points of a data set in classes. The method is based in a algorithm to link auxiliary clusters that are obtained using traditional vector quantization techniques. It is described some approaches during the development of the work that are based in measures of distances or dissimilarities (divergence) between the auxiliary clusters. This new method uses only two a priori information, the number of auxiliary clusters Na and a threshold distance dt that will be used to decide about the linkage or not of the auxiliary clusters. The number os classes could be automatically found by the method, that do it based in the chosen threshold distance dt, or it is given as additional information to help in the choice of the correct threshold. Some analysis are made and the results are compared with traditional clustering methods. In this work different dissimilarities metrics are analyzed and a new one is proposed based on the concept of negentropy. Besides grouping points of a set in classes, it is proposed a method to statistical modeling the classes aiming to obtain a expression to the probability of a point to belong to one of the classes. Experiments with several values of Na e dt are made in tests sets and the results are analyzed aiming to study the robustness of the method and to consider heuristics to the choice of the correct threshold. During this work it is explored the aspects of information theory applied to the calculation of the divergences. It will be explored specifically the different measures of information and divergence using the Rényi entropy. The results using the different metrics are compared and commented. The work also has appendix where are exposed real applications using the proposed method

O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Estratégia de navegação com planejamento dinâmico e algoritmo genético aplicada a robôs móveis terrestres

This work proposes a new autonomous navigation strategy assisted by genetic algorithm with dynamic planning for terrestrial mobile robots, called DPNA-GA (Dynamic Planning Navigation Algorithm optimized with Genetic Algorithm). The strategy was applied in environments - both static and dynamic - in which the location and shape of the obstacles is not known in advance. In each shift event, a control algorithm minimizes the distance between the robot and the object and maximizes the distance from the obstacles, rescheduling the route. Using a spatial location sensor and a set of distance sensors, the proposed navigation strategy is able to dynamically plan optimal collision-free paths. Simulations performed in different environments demonstrated that the technique provides a high degree of flexibility and robustness. For this, there were applied several variations of genetic parameters such as: crossing rate, population size, among others. Finally, the simulation results successfully demonstrate the effectiveness and robustness of DPNA-GA technique, validating it for real applications in terrestrial mobile robots.

Estratégia de navegação com planejamento dinâmico e algoritmo genético aplicada a robôs móveis terrestres

This work proposes a new autonomous navigation strategy assisted by genetic algorithm with dynamic planning for terrestrial mobile robots, called DPNA-GA (Dynamic Planning Navigation Algorithm optimized with Genetic Algorithm). The strategy was applied in environments - both static and dynamic - in which the location and shape of the obstacles is not known in advance. In each shift event, a control algorithm minimizes the distance between the robot and the object and maximizes the distance from the obstacles, rescheduling the route. Using a spatial location sensor and a set of distance sensors, the proposed navigation strategy is able to dynamically plan optimal collision-free paths. Simulations performed in different environments demonstrated that the technique provides a high degree of flexibility and robustness. For this, there were applied several variations of genetic parameters such as: crossing rate, population size, among others. Finally, the simulation results successfully demonstrate the effectiveness and robustness of DPNA-GA technique, validating it for real applications in terrestrial mobile robots.

Multi-resolução com fóvea móvel para redução e abstração de dados em tempo real

We propose a new approach to reduction and abstraction of visual information for robotics vision applications. Basically, we propose to use a multi-resolution representation in combination with a moving fovea for reducing the amount of information from an image. We introduce the mathematical formalization of the moving fovea approach and mapping functions that help to use this model. Two indexes (resolution and cost) are proposed that can be useful to choose the proposed model variables. With this new theoretical approach, it is possible to apply several filters, to calculate disparity and to obtain motion analysis in real time (less than 33ms to process an image pair at a notebook AMD Turion Dual Core 2GHz). As the main result, most of time, the moving fovea allows the robot not to perform physical motion of its robotics devices to keep a possible region of interest visible in both images. We validate the proposed model with experimental results

Otimização do controle eletrônico do diagrama de radiação de arranjos de antenas usando algoritmos genéticos com codificação real

Antenna arrays are able to provide high and controlled directivity, which are suitable for radiobase stations, radar systems, and point-to-point or satellite links. The optimization of an array design is usually a hard task because of the non-linear characteristic of multiobjective, requiring the application of numerical techniques, such as genetic algorithms. Therefore, in order to optimize the electronic control of the antenna array radiation pattem through genetic algorithms in real codification, it was developed a numerical tool which is able to positioning the array major lobe, reducing the side lobe levels, canceling interference signals in specific directions of arrival, and improving the antenna radiation performance. This was accomplished by using antenna theory concepts and optimization methods, mainly genetic algorithms ones, allowing to develop a numerical tool with creative genes codification and crossover rules, which is one of the most important contribution of this work. The efficiency of the developed genetic algorithm tool is tested and validated in several antenna and propagation applications. 11 was observed that the numerical results attend the specific requirements, showing the developed tool ability and capacity to handle the considered problems, as well as a great perspective for application in future works.

Estimação de potência em tempo real utilizando a transformada wavelet

The goal of the power monitoring in electrical power systems is to promote the reliablility as well as the quality of electrical power.Therefore, this dissertation proposes a new theory of power based on wavelet transform for real-time estimation of RMS voltages and currents, and some power amounts, such as active power, reactive power, apparent power, and power factor. The appropriate estimation the of RMS and power values is important for many applications, such as: design and analysis of power systems, compensation devices for improving power quality, and instruments for energy measuring. Simulation and experimental results obtained through the proposed MaximalOverlap Discrete Wavelet Transform-based method were compared with the IEEE Standard 1459-2010 and the commercial oscilloscope, respectively, presenting equivalent results. The proposed method presented good performance for compact mother wavelet, which is in accordance with real-time applications.

Registro global de nuvens de pontos RGB-D em tempo real usando fluxo óptico e marcadores

Registration of point clouds captured by depth sensors is an important task in 3D reconstruction applications based on computer vision. In many applications with strict performance requirements, the registration should be executed not only with precision, but also in the same frequency as data is acquired by the sensor. This thesis proposes theuse of the pyramidal sparse optical flow algorithm to incrementally register point clouds captured by RGB-D sensors (e.g. Microsoft Kinect) in real time. The accumulated errorinherent to the process is posteriorly minimized by utilizing a marker and pose graph optimization. Experimental results gathered by processing several RGB-D datasets validatethe system proposed by this thesis in visual odometry and simultaneous localization and mapping (SLAM) applications.

Sistema mecatrônico de tempo real para monitoramento da qualidade da água embarcado em veleiro robótico autônomo

We propose a mechatronic system for monitoring water quality in rivers, lakes, dams and sea, able to perform the acquisition, processing and presentation of data via the web in real time, in order to facilitate analysis quickly and needs by interested communities. The hardware architecture and software monitoring system has been developed so that it can be generic, that is, supporting different applications. Nevertheless, as a validation of the proposed system, we built a prototype that operates embarked on an autonomous robotic sailboat, a responsible platform for collecting the data in multiple predefined points from a ground station with a planning system navigation. This final application combines the advantages of autonomy of a robotic sailboat with the need for fast and accurate monitoring of water quality, in addition to the use of an autonomous robotic sailboat unmanned facilitate the development of other research in this area.