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.

No contexto da Internet convencional, são várias as soluções oferecidas para transferência de fluxos de áudio e vídeo. Este trabalho é realizado no contexto de uma rede de grande largura de banda e de baixa latência, como aquela que está sendo investigada no contexto do Programa FAPESP TIDIA. O grupo de pesquisa no qual este trabalho foi realizado propôs a arquitetura S-MOJOHON (Lobato et al., 2007a), elaborada com o intuito de permitir transmissão de vários tipos de dados, principalmente áudio e vídeo, no ambiente TIDIA. Os componentes intermediários de uma arquitetura voltada para transmissão de fluxos de áudio e vídeo na Internet, como é o caso da S-MOJOHON, precisam ser selecionados de maneira que possibilitem a entrega de informações entre componentes finais da melhor forma possível. Nesse sentido, o trabalho reportado nesta dissertação envolveu a avaliação dos algoritmos de seleção utilizados nas diferentes implementações da arquitetura S-MOJOHON. Analisando os resultados obtidos, criou-se um novo algoritmo de seleção de componentes que explora as vantagens dos algoritmos avaliados anteriormente. Este texto apresenta a arquitetura S-MOJOHON, a avaliação dos algoritmos de seleção, o novo algoritmo proposto e sua avaliação / Several solutions are available in the context of the Internet with respect to supporting the transfer of audio and video. The work reported in this text considers a gigabit Internet network environment, such as the one supported in the context of the FAPESP TIDIA Project. The research group in which this work has been developed has proposed the S-MOJOHON architecture (Lobato et al., 2007), aimed at supporting the transfer of audio and video in the TIDIA environment. The distributed and complementary nature of the components of an architecture such as the S-MOJOHON demands that they must be selected so as to allow the best transfer rate possible. In such a context, the work reported in this dissertation involved the evaluation of the algorithms deployed in two different S-MOJOHON implementations. As a result, a new algorithm has been designed and evaluated, as detailed in this text

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.

No contexto da Internet convencional, são várias as soluções oferecidas para transferência de fluxos de áudio e vídeo. Este trabalho é realizado no contexto de uma rede de grande largura de banda e de baixa latência, como aquela que está sendo investigada no contexto do Programa FAPESP TIDIA. O grupo de pesquisa no qual este trabalho foi realizado propôs a arquitetura S-MOJOHON (Lobato et al., 2007a), elaborada com o intuito de permitir transmissão de vários tipos de dados, principalmente áudio e vídeo, no ambiente TIDIA. Os componentes intermediários de uma arquitetura voltada para transmissão de fluxos de áudio e vídeo na Internet, como é o caso da S-MOJOHON, precisam ser selecionados de maneira que possibilitem a entrega de informações entre componentes finais da melhor forma possível. Nesse sentido, o trabalho reportado nesta dissertação envolveu a avaliação dos algoritmos de seleção utilizados nas diferentes implementações da arquitetura S-MOJOHON. Analisando os resultados obtidos, criou-se um novo algoritmo de seleção de componentes que explora as vantagens dos algoritmos avaliados anteriormente. Este texto apresenta a arquitetura S-MOJOHON, a avaliação dos algoritmos de seleção, o novo algoritmo proposto e sua avaliação / Several solutions are available in the context of the Internet with respect to supporting the transfer of audio and video. The work reported in this text considers a gigabit Internet network environment, such as the one supported in the context of the FAPESP TIDIA Project. The research group in which this work has been developed has proposed the S-MOJOHON architecture (Lobato et al., 2007), aimed at supporting the transfer of audio and video in the TIDIA environment. The distributed and complementary nature of the components of an architecture such as the S-MOJOHON demands that they must be selected so as to allow the best transfer rate possible. In such a context, the work reported in this dissertation involved the evaluation of the algorithms deployed in two different S-MOJOHON implementations. As a result, a new algorithm has been designed and evaluated, as detailed in this text