We present robust explicit construction of 3D configuration spaces using controlled linear perturbation. The input is two planar parts: a fixed set and a moving set, where each set is bounded by circle segments. The configuration space is the three-dimensional space of Euclidean transformation (translations plus rotations) of the moving set relative to the fixed set. The goal of constructing the 3D configuration space is to determine the boundary representation of the free space where the intersection of the moving set and fixed set is empty. To construct the configuration space, we use the controlled linear perturbation algorithm. The controlled linear perturbation algorithm assigns function signs that are correct for a nearly minimal input perturbation. The output of the algorithm is a consistent set of function signs. This approach is algorithm-independent, and the overhead over traditional floating point methods is reasonable. If the fixed and moving sets are computer representations of physical objects, then computing the configuration space greatly aids in many computational geometry problems. The main focus of computing the configuration space is for the path planning problem. We must find if a path exists from the start to the goal, where the fixed set is the obstacle, and the moving set is the object trying to reach the goal.

Submitted by Alison Vanceto (alison-vanceto@hotmail.com) on 2017-01-24T10:38:55Z No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:50:29Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Approved for entry into archive by Camila Passos (camilapassos@ufscar.br) on 2017-02-08T10:51:23Z (GMT) No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) / Made available in DSpace on 2017-02-08T10:51:33Z (GMT). No. of bitstreams: 1 TeseMGSF.pdf: 2372267 bytes, checksum: 33d2a1fb8316befd39ea4c2aa4e6a69e (MD5) Previous issue date: 2016-04-01 / Outra / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) / The object of this study is the routing and scheduling problem of vessels with pickup and delivery and time windows in the oil industry. A case study was performed in a Brazilian oil industry that produces crude oil in o shore platforms, that is, located in the ocean, and transports to the terminals located in the Brazilian coast. Then, it was proposed a mixed integer model to represent the problem adequately and for this, a detailed analysis of the real problem in order to know all its characteristics and consider some simplifying assumptions. Therefore, to the pickup and delivery problem with time windows present in the literature were aggregated other speci c restrictions of the case study, for example, multiple depots, ship mooring restrictions, exible draft and dynamic positioning. Besides that, the eet is heterogeneous related to capacity, LOA (length overall), dynamic positioning and velocity. In practice, in general there are no identical vessels. This problem can be represented as a combinatorial optimization model, which belongs to the NP-hard class and its solution is a challenging in practice depending on the size of the real problems. Then, were proposed several exact branch-and-cut methods based on models with 2 and 3-index variables for routing problems with pickup and delivery and time windows to solve speci cally the Brazilian oil industry problem. Finally, we proposed a branch-and-price method, which includes all characteristics of the problem in oil industry. In summary, the main contributions of this thesis are related to the study and modeling of this problem in practice, and the proposal and development of exact solution methods to solve it, based on branch-and-cut and branch-and-price. The performance of the mathematical model in optimization software and the exact methods were veri ed using a real data set provided by the company. Results show that these approaches may be e ective to solve problems of moderate size in real situations. / O objeto de estudo deste trabalho é o problema de roteamento e programação de navios com coleta e entrega e janelas de tempo na indústria petrolífera. Foi realizado um estudo de caso com uma empresa petrolífera brasileira que produz óleo cru em plataformas o shore, isto é, localizadas no oceano e os transporta até os terminais localizados na costa brasileira. Então, foi proposto um modelo de programação inteira mista para representar o problema adequadamente e para isso, foi necessária uma análise detalhada do problema real, com o intuito de conhecer todas as suas características e considerar hipóteses simpli cadoras. Desta maneira, ao problema de coleta e entrega e janelas de tempo da literatura foram agregadas outras restrições especí cas do problema do estudo de caso como, por exemplo, múltiplos depósitos, restrições de atracação dos navios, calado exível e posicionamento dinâmico. Além disso, a frota de navios é heterogênea em relação à capacidade, LOA (length overall ), posicionamento dinâmico e velocidade. Na prática, em geral não existem navios iguais. Este problema pode ser representado como um modelo de otimização combinatória que pertence à classe NP-difícil e sua solução é bastante desa adora na prática em função do tamanho dos problemas reais. Depois, foram propostos vários métodos do tipo branch-and-cut baseados em modelos com variáveis de 2 e 3-índices para problemas de roteamento com coleta e entrega e janelas de tempo para resolver especi camente o problema da empresa brasileira. E por m, foi proposto um método do tipo branch-and-price, o qual abrange todas as características do problema da indústria petrolífera. Em síntese, as principais contribuições desta tese referem-se ao estudo e modelagem deste problema na prática, e a proposta e desenvolvimento de métodos de solução exatos para resolvê-lo, baseados em branch-and-cut e branch-and-price. O desempenho do modelo matemático em softwares de otimização e também dos métodos exatos propostos foi veri cado usando-se exemplares reais fornecidos pela empresa. Os resultados mostram que essas abordagens podem ser efetivas para resolver problemas de tamanho moderado em situações reais.

Le travail réalisé dans cette thèse s'intègre globalement dans le cadre de I'observation et la surveillance maritime.Afin d'améliorer la reconnaissance et I'identification automatique de cibles noyées dans un environnement perturbé, nous avons opté à la fusion de différentes connaissances et informations concernant une scène observée à distance par des capteurs micro-ondes. En effet, plusieurs phénomènes physiques co-existent et perturbent la propagation des ondes électromagnétiques au-dessus d'une surface et notamment au-dessus d'une surface maritime hétérogène (la réfraction due aux gradients d'indice, la rugosité de la surface de mer, les effets hydrodynamiques non linéaires du type vagues déferlantes, la présence d'objets, les polluants, sillage de navires, zones côtières, ...). Dans ce contexte, le travail présenté dans cette thèse porte sur l'étude de la signature électromagnétique (coefficients de diffusion) d'une surface maritime hétérogène avec la prise en compte des phénomènes hydrodynamiques (linéaires : vagues de capillarité et de gravité, non linéaires : vagues déferlantes). Cette estimation de la signature électromagnétique est effectuée en configuration bistatique (monostatique et propagation avant) et en bande X. L'étude complète de cette problématique est difficile. En effet, le déferlement est un processus dissipatif de l'énergie qui correspond à la dernière étape de la vie d'une vague et qui a donc le plus souvent lieu à I'approche du rivage. Ce phénomène non linéaire produit un pic de mer qui est une augmentation rapide des coefficients de diffusion et qui peut dépasser 10 dB dans une période de 100 ms. Ce pic peut conduire à des échos parasites, qui peuvent être identifiés comme des cibles virtuelles, et par la suite elles peuvent perturber le système de détection radar (fausses alarmes). Par conséquent, pour améliorer le processus de détection et pour réduire le taux de fausses alarmes, il est important de distinguer entre les cibles et les pics de mer générés par des vagues déferlantes. Ceci constitue I’une des motivations et aussi I'intérêt d'étudier la signature électromagnétique des vagues déferlantes dans différentes configurations d'observation de sorte que nous puissions facilement indiquer la présence voir I'identification des pics de mer. Pour contribuer à cette problématique, nous avons proposé une méthodologie basée sur un modèle électromagnétique hybride basé sur une combinaison d'une part de méthodes asymptotiques(SPMI utilisée dans le cadre de ce travail) pour simuler la réponse radar des vagues linéaire (vagues de capillarité et de gravité décrites via le spectre de mer d'Elfouhaily), et d'autre part de méthodes exactes (MoM, FB < Forward-Backward ) retenue dans le travail présenté dans ce manuscrit) pour calculer la réponse électromagnétique des vagues non-linéaires (profils considérés sont issus des résultats du code LONGTANK). Afìn de compléter l'étude théorique et les simulations réalisées, nous avons effectué une phase d'évaluation et de validation par des mesures de signature radar réalisées dans la chambre anéchoïque de I'Ensta Bretagne. / The work done in this thesis fits generally under the observation and maritime surveillance. To improve the detection and automatic identification of targets embedded in a noisy environment targets, we opted for the fusion of different knowledge and information regarding a remotely observed scene by microwave sensors. Indeed, several physical phenomena co-exist and interfere with the propagation of electromagnetic waves over a heterogeneous sea surface (the refraction due to the index gradients, the roughness of the sea surface, nonlinear hydrodynamic effects like waves breaking, the presence of objects, pollutants, ship wake, coastal areas,..). In this context, the work presented in this thesis focuses on the study of electromagnetic signature (diffusion coefficients) of a heterogeneous sea surface with consideration of hydrodynamic phenomena (linear: capillary and gravity waves, nonlinear: breaking waves). The electromagnetic signature is performed in bistatic configuration (monostatic and forward propagating) and in X-band. The complete study of this problem is difficult.Indeed, the breaking wave is a dissipative process of energy that corresponds to the last stage of the life of a wave and therefore has most often held in the shore. This nonlinear phenomenon produces a sea peak which is a rapid increase of the diffusion coefficients and can exceed l0 dB in a 100 ms period. This peak can lead to clutter, which can be identified as virtual targets, and then they can disrupt the detection radar system (false alarms). Therefore, to improve the detection process and reduce the false alarm rate, it is important to distinguish between targets and sea peaks generated by breaking waves. This represents one of the motivations and also the interest to study the electromagnetic signature of breaking waves in different observation configurations so that we can easily detect and identify the sea peaks. To solve this problem, we proposed a methodology based on a hybrid electromagnetic model which is on a combination of asymptotic methods (SPMI used in this work) to simulate the radar response of linear waves (capillary and gravity waves described via the Elfouhaily sea spectrum) and an exact methods, the method of moment (the FB "Forward-Backward" method is used in this work), to calculate the electromagnetic response of nonlinear waves (profiles are produced by the LONGTANK code). To complement the theoretical study and simulations, we carried out an evaluation and validation phase by measuring the radar signature of breaking wave profiles in the ENSTA Bretagne anechoic chamber.