[pt] O surgimento de tecnologias de enlace de rádio baratas e com altas taxas de transmissão possibilitou o desenvolvimento de métodos rápidos e economicamente viáveis para a implantação de infraestruturas de comunicação, algo antes possível apenas com a utilização de enlaces confinados. Uma manifestação deste avanço são as malhas sem fio. A ratificação da emenda IEEE 802.11s, que versa sobre as modificações necessárias para o suporte a LANs sem fio com múltiplos saltos por parte de dispositivos compatíveis com 802.11, apresenta o protocolo HWMP, para a seleção de caminhos multissalto em uma malha. Em um ambiente com comunicação bidirecional, nem sempre e garantido que as melhores opções de ida e volta sejam coincidentes, uma condição conhecida como assimetria de caminhos, e que não e considerada pelo protocolo HWMP. Este trabalho apresenta algumas adaptações ao protocolo que buscam permitir a melhor utilização dos enlaces assimétricos, bem como mensura as diferenças de desempenho em comparação com o protocolo original. / [en] The rise of inexpensive, high-bitrate wireless link technologies enabled the development of rapid and affordable techniques for the deployment of communication infrastructures, something only available before with the use of wired links. The ratification of the IEEE 802.11s ammendment, which establishes the necessary modifications to 802.11-compliant devices for supporting multi-hop WLANs, presents the HWMP protocol, that addresses multi-hop path selection in a wireless mesh. In a bidirectional communication environment, it is not always ensured that the best options for sending and receiving data are coincident, a condition known as path asymmetry, and not considered by HWMP. This work presents some adaptations to the protocol, seeking to allow better use of asymmetric links, as well as measures its performance differences in comparison to the original protocol.

A classic problem Computational Geometry is finding all euclidean shortest paths in a simple polygon from a given source vertex to every other vertex in the boundary. In this text, we give a detailed description of the Visibility Graph and Shortest Path Tree structures that solve this problem and also present the Shortest Path Map structure that extends the solution to shortest paths to every point inside the polygon. / Um problema clássico em Geometria Computacional é: encontrar todos os caminhos mínimos euclidianos dentro de um polígono simples a partir de um dado vértice fonte para todos os outros vértices da borda. Neste texto, apresentamos detalhadamente as estruturas de Grafo de Visibilidade e Árvore de Caminhos Mínimos que resolvem este problema e descrevemos também a estrutura Mapa de Caminhos Mínimos que estende a solução para todos os pontos contidos dentro do polígono.

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

O problema de caminhos mínimos (SP shortest path problem) é frequentemente colo- cado em prática em uma grande variedade de aplicações em diversas áreas. Nessas aplicações geralmente se deseja realizar algum tipo de deslocamento ou transporte entre dois ou mais pontos específicos em uma rede. Tal ação deve ser executada de forma ótima em relação a algum critério, por exemplo o menor custo possível, ou o menor gasto de tempo ou o máximo de confiabilidade/segurança. Na prática, muitas vezes não desejamos apenas o menor custo ou o menor tempo, mas desejamos otimizar uma combinação de diferentes critérios, por exemplo, um caminho que seja rápido e barato. Como não é possível otimizar sobre todos os critérios de uma só vez, nós escolhemos um dos critérios para representar a função custo, que será minimizada, e para os demais critérios representamos como recursos e definimos os limites que julgamos aceitáveis para o consumo de cada um desses recursos. Esta variação é cha- mada de problema de caminhos mínimos com restrições por recursos, ou como preferimos chamar, problema de caminhos mínimos com recursos limitados (RCSP resource constrained shortest path problem), o qual será o objeto de estudo neste trabalho. A adição de restrições por recursos no SP, infelizmente torna o problema NP-difícil, mesmo em grafos acíclicos, com restrições sobre um único recurso, e com todos os consu- mos de recursos positivos. Temos reduções dos famosos problemas N P-difíceis Mochila e Partição para o nosso problema. Em contextos diversos são encontrados problemas de cunho teórico e prático que po- dem ser formulados como problemas de caminhos mínimos com recursos limitados, o que nos motivou a estudá-lo a fim de desenvolver um trabalho que resumisse informações sufi- cientes para auxiliar pesquisadores ou desenvolvedores que tenham interesse no problema. Nós apresentamos aqui, uma detalhada revisão bibliográfica do RCSP, tendo como foco o desenvolvimento de algoritmos exatos para o caso onde possuímos um único recurso e a im- plementação e comparação dos principais algoritmos conhecidos, observando-os em situações práticas. / The problem of choosing a route to a trip, where we want minimize the distance of the path is a major problem in computing. In this basic form, this is the shortest path problem. But sometimes, besides the length we need to consider more parameters for selecting a good path. A common parameters to consider is the consumption of resources in a limited budget. A shortest path with these additional constraints is called resource constrained shortest path - RCSP. This paper has two main objectives: to present a literature review of the problem RCSP, focusing on exact algorithms for the case where we have a single resource, and implement and compare some algorithms, observing them in practical situations. The Shortest Path (SP) problem is among the fundamental problems of computer sci- ence. Its been deeply studied and subject of many publications. Also, many efficient solutions (polynomial time algorithms) are known for this problem. The SP is widely applied in many fields of science, not only computer science. These situations usually need to transport a load between two or more specific spots of a network. This action must be taken optimally regarding to some criterion, for instance the least cost, or the least time or maximum relia- bility. While new solutions for SP were presented, new demands were issued too, with new variations for the problem. One of these variations comes from the fact that, in a real scenario, a combination of many criteria must be optimized, for instance a path with least cost and least time. This problem is known as Multiobjective Shortest Path. Since its not possible to optimize all criteria at once, one of them is chosen to represent the cost function to be minimized and the others to represent resources with defined boundary. This variation, known as Resource Constrained Shortest Path (RCSP), was the object of the present study. By adding resource constraints, the SPbecomes N P-hard, even in acyclic graphs with only one resource constrained and all resource consumption being positive. There are reduc- tions from the famous NP-hard problems Knapsack and Partition to our problem. In many fields, are found theoretical and practical problems that may be expressed as a Resource Constrained Shortest Path Problem, which motivated us to study this problem in order to summarize enough information to researchers and developers involved with this problem. This paper presents a detailed bibliographic revision to RCSP, focusing on the development of exact algorithms for the case when there is only only one resource and on the implementation and comparison of the main known algorithms in practical situations.

Este trabalho aborda o problema de planejamento de caminhos em robótica móvel autônoma utilizando campos potenciais. Dentre as várias técnicas de campos potenciais para controlar robôs, encontram-se as técnica de Campos Potenciais de Khatib1 (CP), Campo Potencial Harmônico (CPH), Campo Potencial Orientado (CPO) e Campo Potencial Localmente Orientado (CPLO). As técnicas CPH, CPO e CPLO são chamadas de técnicas baseadas em Problema de Valor de Contorno (PVC), pois são obtidas a partir de soluções de Equações Diferenciais Parciais (EDP) Elípticas em uma determinada condição de contorno, é obtido um sistema planejador de caminhos. Tais técnicas necessitam de uma etapa de solução de sistemas lineares, na qual se utiliza métodos iterativos, decorrentes da aplicação do método de diferenças finitas como solucionador das EDP. No presente trabalho, as técnicas de Campos Potenciais baseados em PVC foram estudadas e implementadas (usando processamento sequencial e paralelo), de modo a obter resultados de forma mais rápida e confiável. Foram utilizadas arquiteturas paralelas do tipo manycore. Finalmente, são feitas análises comparativas entre os vários métodos implementados. Todos os métodos estão prontos para serem incorporados tanto no simulador quanto nos times de robôs em desenvolvimento pelo grupo Warthog Robotics / This works details the task o path planning in autonomous mobile robots using potential fields techniques. Among potential fields techniques to control robots, there are Khatibs Potential Field2 (KPF), Harmonic Potential Field (HPF), Oriented Potential Field (OPF) and Locally Oriented Potential Field (LOPF). The HPF, OPF and LOPF techniques are called Boundary Value Problem (BVP) based, bacause they are obtained from numerical solutions of Elliptic Partial Differential Equations (PDE) in a well-defined boundary condition. These techniques go through a step of solving linear systems, in which is used iterative methods, that came from numerical solution of PDE. In this work, potential fields BVP based was studied and coded (using sequential and parallel architectures), to obtain results more quickly and reliably. And, finally, a comparative analyses of the various methods implemented are made. All methods are ready to be incorporated in the intelligent systens that are being developed by Warthog Robotics

Com a necessidade de analisar dados cada vez mais complexos nas mais diversas áreas, surge também a necessidade de novas técnicas e novas modelagens. Nesse contexto, os Modelos de Equações Estruturais são uma evolução da análise de caminhos proposto por Wright (1921), que por sua vez, consegue captar as relações de causa e efeito entre diferentes tipos de variáveis. Este trabalho tem como objetivo abordar uma revisão em torno dessa técnica, com ênfase aos modelos recursivos que utilizam em sua maioria apenas variáveis observadas. A aplicação deste trabalho está fundamentada em um processo de simulação considerando assim, seis cenários com diferentes tipos de relações numa mesma estrutura. As médias das estimativas dos parâmetros no processo de simulação resultam em valores próximos aos valores verdadeiros. Por meio de figuras e gráficos, pode-se observar o comportamento dos parâmetros por meio do erro quadrático médio e boxplot. A análise foi realizada com a utilização do software R e programas implementados com pacote sem (FOX; WEISBERG, 2012) e programação apresentada no Apêndice deste trabalho. / With the increasingly need to analyze complex data in several areas, comes the need for new techniques and new models. In this context, the Structural Equation Modeling is an evolution of the path analysis proposed by Wright (1921), which, can capture the relations of cause and effect between different types of variables. The present work aims to approach a review about this technique with emphasis on recursive models using mostly observed variables only. The application of this work is based on a simulation process considering six scenarios with different types of relationships within the same structure. The mean estimates of the parameters in the simulation result in values that are close to the true values, and by means of figures and graphs, one can observe the behavior of the parameters by means of the mean squared error and boxplot. The analysis was performed using the software software R and implemented programs as sem package (FOX; WEISBERG, 2012) and the programming is presented in the Appendix of this work.

Esta dissertação expõe o estudo realizado sobre o artigo de R. Brown, citado na bibliografia, e sobre os conceitos necessários para a compreensão deste material. Entre os principais conceitos e resultados preliminares discutidos, podemos citar: topologia de espaços de funções, teoria de homotopia, espaços compactos ANR, característica de Euler de um compacto ANR, teorema de Lefschetz, espaços fibrados, e campos de caminhos. Os principais resultados discutidos na dissertação são os teoremas centrais do artigo de Brown: toda n-variedade topológica compacta admite um campo de caminhos com no máximo uma singularidade; e, uma n-variedade topológica compacta orientável admite um campo de caminhos sem singularidades se, e somente se, sua característica de Euler é zero. Discutimos também, suas respectivas consequências em teoria de ponto fixo / This essay has the purpose of exposing the studies on the paper by R. Brown, quoted on the references, and on the concepts necessary to the comprehension of it. Among the main concepts and preliminary results discussed, we can cite: topology of function spaces, homotopy theory, ANR compact spaces, Euler characteristic of a compact ANR, Lefschetz theorem, fiber spaces, and field paths. The main results discussed in the text are the central theorems presented on Brown\'s paper: every compact topological n-manifold admits a path field with at most one singularity, and a compact orientable topological n-manifold M admits a nonsingular path field if and only if the Euler characteristic of M is zero. We also discussed their consequences on fixed point theory

Neste trabalho, buscou-se compreender a morfologia e os componentes do sinal da deglutição. Na busca desse entendimento diversas técnicas foram empregadas. No intuito de fazer marcações fidedignas em trechos específicos do sinal, o qual foi analisado simultaneamente com a imagem da videofluoroscopia da deglutição, considerado o melhor método atual na avaliação da dinâmica da deglutição. Os parâmetros numéricos utilizados para análise também foram abrangentes e com base em técnicas atuais de processamento de sinais, como emprego de transformada Wavelet. Quanto à classificação dos sinais, foram utilizados classificadores modernos como floresta de caminhos ótimos, máquinas de vetores de suporte, redes neurais artificiais e classificador Bayesiano, dando maior ênfase ao primeiro, por possuir um custo computacional bem menor quando comparado aos outros 3, e consequentemente convergindo mais rapidamente ao resultado. Foram avaliados 84 sinais, divididos em 2 grupos separados pela consistência do bolo alimentar oferecido (líquido e pastoso). Na distinção e/ou caracterização desses tipos foi definido um subconjunto com 4 variáveis que proporcionou uma boa acurácia na separação das classes representantes de cada tipo de bolo alimentar. / This work proposes to understand the morphology and the components of the swallowing signal. In pursuit of this understanding, a variety of techniques were employed. In order to make reliable markings on specific portions of the signal, the signal was examined simultaneously with videofluoroscopic swallowing, which is considered the best method in the evaluation of swallowing dynamics. The parameters used for numerical analysis were based on current signal processing techniques, such as: Wavelet transform, Optimum path forest, Support vector machines, Artificial neural networks and Bayesian classifier, emphasizing the first technique, due to a much lower computational cost when compared to the previous, and, consequently, the results converged much faster. Eighty four signals, divided into 2 groups separated by the consistency of food bolus offered (liquid and thickened), were evaluated. For distinction and/or characterization of such types, a subset with 4 variables was defined, providing a good accuracy in the separation of these classes representing each type of consistency of the food bolus.

Esta dissertação busca identificar os elementos integrados pelos caminhoneiros autônomos em suas vidas móveis. Analisa como estes motoristas extraem permanência de suas mobilidades, constitutivas desses modos de vidas. Os caminhoneiros são profissionais especializados em operar veículos automotores de carga e fazer circular mercadorias a partir do transporte rodoviário. Trata-se de um conjunto disperso e heterogêneo que executa grandes jornadas de trabalho distantes de seus endereços fixos, para onde retornam intermitentemente. Sem desvincular-se dos cotidianos mais sedentários, intensificam o convívio com os caminhões e as estradas. Instrumento de trabalho, mas também casa móvel, o caminhão é onde se realiza obrigações, prazeres e lazeres. Os veículos adquirem diverso usos, modificações, valores, afetos e podem operar nas distinções entre pares. Cuidados de si e dos caminhões se misturam e revestem a boleia de domesticidade masculina que ajuda a viabilizar o ser caminhoneiro. Nas estradas, cumpre-se o itinerário, cujas rotas e prazos são estipulados pelo mercado. O itinerário é preenchido pelos caminhoneiros por intensas negociações entre tarefas laborais e extralaborais manifestadas nas escolhas e efetivações das paradas que pontuam o trajeto. Nos estabelecimentos comerciais, os motoristas se vinculam ao pessoal do posto, chapas e putas. São interações afetivas, trabalhistas, sexuais e de consumo que se articulam e animam as estradas. Tendo em vista a vida social das BRs esta etnografia se desenvolveu a partir de caronas nas boleias de caminhão, um tipo de mobilidade informal e gratuita inteligível neste contexto, em especial, para os caminhoneiros. As teorias elaboradas pelos motoristas inspiraram esta dissertação e suscitam dialogo com algumas discussões acadêmicas sobre mobilidades e trabalho caminhoneiro no campo das humanidades. Com isso, leva-se em conta que quando os motoristas e caminhões se movem pelas estradas, não só as mercadorias são postas em circulação através de itinerários. Junto a elas se movimentam também certa economia corporal, material e simbólica numa trama adensada de relações que cria e recria caminhos. Estes, indispensáveis para a permanência dessas vidas móveis. / This dissertation aims to identify what are the elements that truck drivers integrate in their mobile lives. We analyze how these truck drivers extract permanence of their mobilities, constitutive of those ways of living. The truck drivers professionals specializes in operate cargo automotive vehicles, transporting goods across the road network. They are a heterogeneous disperse set of professionals performing long work periods away from their fixed homes, to which they return intermittently. Thus, they keep bonds with their settled dwellings while they intensify their sociality with trucks and roads. The truck is both a work tool and a mobile house, where they perform duties, pleasures and leisure. The vehicles are put to different uses, customizations, values, affections and may engender distinction amongst colleagues. Drivers intertwine self-care and truck maintenance, investing the truck lorry of a masculine domesticity which instantiate what is to be a truck driver. On the road, an itinerary is fulfilled, with market stipulated routes and schedules. Meanwhile, truck drivers entangle their itinerary with intense negotiations between work tasks and other activities, which take place in the truck drivers choices of where they stop along the way. At side road shops and stores, drivers relate to gas station workers, local guides and prostitutes. Labor, affective, sexual and consumption relations that makes the road alive. Regarding the social life of Brazilian federal highways and roads, this ethnographic research was carried out by means of hitchhiking truck lorries, a free and non-official way of faring used to translate to the drivers the anthropological research. The theories conceived by those truckers have inspired this work and are presented in dialogue with academic debates on mobilities and truck drivers professional realities. Thus, we consider that not only goods are set in motion when drivers and trucks fare their itineraries, but there is also a specific bodily, material and symbolic economy moving along a thick meshwork of relations that make and unmake paths. Those are constitutive of the permanence of those mobile lives.

Esta dissertação busca identificar os elementos integrados pelos caminhoneiros autônomos em suas vidas móveis. Analisa como estes motoristas extraem permanência de suas mobilidades, constitutivas desses modos de vidas. Os caminhoneiros são profissionais especializados em operar veículos automotores de carga e fazer circular mercadorias a partir do transporte rodoviário. Trata-se de um conjunto disperso e heterogêneo que executa grandes jornadas de trabalho distantes de seus endereços fixos, para onde retornam intermitentemente. Sem desvincular-se dos cotidianos mais sedentários, intensificam o convívio com os caminhões e as estradas. Instrumento de trabalho, mas também casa móvel, o caminhão é onde se realiza obrigações, prazeres e lazeres. Os veículos adquirem diverso usos, modificações, valores, afetos e podem operar nas distinções entre pares. Cuidados de si e dos caminhões se misturam e revestem a boleia de domesticidade masculina que ajuda a viabilizar o ser caminhoneiro. Nas estradas, cumpre-se o itinerário, cujas rotas e prazos são estipulados pelo mercado. O itinerário é preenchido pelos caminhoneiros por intensas negociações entre tarefas laborais e extralaborais manifestadas nas escolhas e efetivações das paradas que pontuam o trajeto. Nos estabelecimentos comerciais, os motoristas se vinculam ao pessoal do posto, chapas e putas. São interações afetivas, trabalhistas, sexuais e de consumo que se articulam e animam as estradas. Tendo em vista a vida social das BRs esta etnografia se desenvolveu a partir de caronas nas boleias de caminhão, um tipo de mobilidade informal e gratuita inteligível neste contexto, em especial, para os caminhoneiros. As teorias elaboradas pelos motoristas inspiraram esta dissertação e suscitam dialogo com algumas discussões acadêmicas sobre mobilidades e trabalho caminhoneiro no campo das humanidades. Com isso, leva-se em conta que quando os motoristas e caminhões se movem pelas estradas, não só as mercadorias são postas em circulação através de itinerários. Junto a elas se movimentam também certa economia corporal, material e simbólica numa trama adensada de relações que cria e recria caminhos. Estes, indispensáveis para a permanência dessas vidas móveis. / This dissertation aims to identify what are the elements that truck drivers integrate in their mobile lives. We analyze how these truck drivers extract permanence of their mobilities, constitutive of those ways of living. The truck drivers professionals specializes in operate cargo automotive vehicles, transporting goods across the road network. They are a heterogeneous disperse set of professionals performing long work periods away from their fixed homes, to which they return intermittently. Thus, they keep bonds with their settled dwellings while they intensify their sociality with trucks and roads. The truck is both a work tool and a mobile house, where they perform duties, pleasures and leisure. The vehicles are put to different uses, customizations, values, affections and may engender distinction amongst colleagues. Drivers intertwine self-care and truck maintenance, investing the truck lorry of a masculine domesticity which instantiate what is to be a truck driver. On the road, an itinerary is fulfilled, with market stipulated routes and schedules. Meanwhile, truck drivers entangle their itinerary with intense negotiations between work tasks and other activities, which take place in the truck drivers choices of where they stop along the way. At side road shops and stores, drivers relate to gas station workers, local guides and prostitutes. Labor, affective, sexual and consumption relations that makes the road alive. Regarding the social life of Brazilian federal highways and roads, this ethnographic research was carried out by means of hitchhiking truck lorries, a free and non-official way of faring used to translate to the drivers the anthropological research. The theories conceived by those truckers have inspired this work and are presented in dialogue with academic debates on mobilities and truck drivers professional realities. Thus, we consider that not only goods are set in motion when drivers and trucks fare their itineraries, but there is also a specific bodily, material and symbolic economy moving along a thick meshwork of relations that make and unmake paths. Those are constitutive of the permanence of those mobile lives.