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 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.

LIMA, Ítalo Siqueira. Extensões induzidas de altura mínima de um conjunto parcialmente ordenado. 2007. 78 f : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:49:21Z No. of bitstreams: 1 2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-07-01T19:49:52Z (GMT) No. of bitstreams: 1 2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5) / Made available in DSpace on 2016-07-01T19:49:52Z (GMT). No. of bitstreams: 1 2007_dis_islima.pdf: 567978 bytes, checksum: 3ba284ffabfddf975efc4b51ef98ffe6 (MD5) Previous issue date: 2007

El uso de elementos finitos para analizar fenómenos físicos modelados por ecuaciones diferenciales parciales requiere de una discretización del dominio, como lo son las triangulaciones en dos dimensiones. En este contexto se distinguen tres problemas: generar una triangulación a partir de un conjunto de vértices y segmentos, refinar una malla y mejorar la calidad de una malla. Los algoritmos que refinan triangulaciones Delaunay en general se basan en seleccionar nuevos puntos y realizar una inserción Delaunay de éstos. Los criterios usados para comparar algoritmos se basan en la cantidad de inserciones que realizan, la cantidad de triángulos generados y el tiempo de ejecución. Sin embargo, es difícil encontrar implementaciones que realicen las comparaciones bajo un mismo ambiente y condiciones. En esta memoria se ha diseñado un marco de experimentación que permite investigar y comparar algoritmos de refinamiento Delaunay dentro de un mismo ambiente. Se propone un proceso de refinamiento genérico y se desarrolla una herramienta que, haciendo uso de patrones de diseño de programación con orientación a objetos, implementa el proceso con la flexibilidad de poder extender la herramienta con nuevos algoritmos de forma simple. Se provee una interfaz gráfica que permite seguir el proceso de refinamiento en una forma clara y didáctica. La herramienta genera resultados comparables con los resultados de Triangle, una herramienta de refinamiento Delaunay rápida y eficiente, pero limitada en su extensibilidad y usabilidad. La extensibilidad de la herramienta se puso a prueba implementando los siguientes criterios de selección de puntos asociados a triángulos de mala calidad: Circuncentro, Off-Center, Lepp - Punto Medio, Lepp - Centroide y Lepp - Bisección (No Delaunay). Se evalúan también técnicas de priorización en el procesamiento de los triángulos de mala calidad. Se experimentó con un algoritmo nuevo, Lepp -Circuncentro, el cual presentó un buen rendimiento con las mallas estudiadas, alcanzando en algunos casos una exigencia de 37º como ángulo interior mínimo. Se estudiaron criterios de priorización en la selección de triángulos de mala calidad, concluyendo que el comportamiento de los algoritmos de tipo Lepp es independiente del uso de técnicas de priorización. En cambio, el algoritmo Off-Center aumenta considerablemente el número de puntos insertados si no se utiliza un orden de procesamiento adecuado.

Ingeniero Civil Matemático / El objetivo principal del presente trabajo de memoria de título es el cálculo de cotas para precio de la anarquía de algunos juegos asociados a problemas de scheduling. Se comienza realizando una revisión general de lo que son los problemas de scheduling, un algoritmo de aproximación y la relación que existe entre teoría de juegos y los problemas de scheduling. Ahí se identifica el cuociente de aproximación del algoritmo de Smith para problemas de scheduling, con el precio de la anarquía de un juego asociado. Se realiza también una revisión de los principales resultados conocidos útiles para el presente trabajo. Más adelante se calcula el precio de la anarquía para ciertos juegos de scheduling donde la función objetivo es la suma ponderada de los tiempos de completación. Se demuestra que en el caso de máquinas idénticas, el precio de la anarquía en estrategias mixtas es 3/2. Se demuestra también que en máquinas paralelas con velocidades, el precio de la anarquía es mayor o igual a 2. Por último, se prueba acá que en el caso en que todos los trabajos tienen el mismo tamaño, el precio de la anarquía del juego de scheduling en máquinas paralelas con velocidades y suma ponderada de los tiempos de completación como función objetivo es 1. Para seguir se estudia el juego asociado al problema de scheduling en el cual la función objetivo es la suma de los tiempos de completación, y las máquinas son todas excepto una idénticas entre sí, la máquina restante es de velocidad mayor a las demás, y las máquinas que son más lentas son una cantidad suficientemente grande. Para este juego de scheduling se demuestra que el precio de la anarquía es e/(e-1). Después se estudia el juego mencionado anteriormente en su caso más general, en el cual la cantidad de máquinas lentas no está restringida a ser suficientemente grande. Para este problema se demuestra que el precio de la anarquía está acotado superiormente por 5/3. Se muestra además un problema de programación lineal cuyo óptimo acota superiormente el precio de la anarquía del juego de scheduling de máquinas paralelas con velocidades y suma de los tiempos de completación como función objetivo. Finalmente, se plantea como conjetura que el precio de la anarquía del juego asociado al problema de scheduling más general antes mencionado es efectivamente e/(e-1), y se muestran pruebas computacionales que fueron realizadas, con las cuales se justifica el plantear esta conjetura.

Ingeniero Civil Mecánico / La presencia de una grieta en una estructura, no solo varía las propiedades mecánicas del material, sino que también influye sobre sus características dinámicas. Es por esa razón que el monitoreo de las vibraciones de una estructura es una técnica muy utilizada en ingeniería y permite la detección temprana del daño. Generalmente, la decisión del posicionamiento de sensores de monitoreo, pasa por el juicio y la experiencia del ingeniero a cargo; sin embargo, un error puede provocar que el daño no se detecte. Se han desarrollado variados métodos de optimización de posición de sensores que monitorean el comportamiento dinámico de la estructura. Sin embargo, hasta hoy no existe un procedimiento estándar que optimice la posición y el número de sensores a utilizar, enfocado en la identificación del daño. Se desea desarrollar una metodología para optimizar la posición y número de sensores de monitoreo dinámico en una estructura tipo viga, utilizando algoritmos genéticos paralelos. En particular, se desea encontrar la configuración óptima de sensores cuando se monitorean las frecuencias de anti-resonancia de la estructura. El algoritmo genético es un método de optimización basado en la teoría de la evolución de Darwin, el que ha cobrado una alta popularidad en todo el mundo durante los últimos años, debido a su robustez y a su independencia de la función objetivo. Es un algoritmo matemático que transforma un conjunto de objetos matemáticos usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del más apto. Dentro de estas operaciones genéticas destacan la mutación y la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija denominado cromosoma. Cada gen dentro del cromosoma representa una variable a optimizar. La aptitud de cada cromosoma se mide evaluando en la función objetivo. V Para desarrollar esta metodología, primeramente se encontraron las frecuencias de anti-resonancia de la estructura y luego se determinó su sensibilidad al daño. Seguidamente, se define una función objetivo que relacione la información al daño y la ubicación de los sensores. Esta función es optimizada a través de la programación de algoritmos genéticos paralelos. Finalmente, se realiza una verificación experimental de la metodología creada, utilizando un algoritmo de detección de daño disponible y datos experimentales. Para la programación en elementos finitos y algoritmos genéticos, se utiliza el software MatLab y su extensión GAOT. Para la verificación experimental, se trabajará en el laboratorio de sólidos Mecesup ubicado en la Facultad de Ciencias Físicas y Matemáticas de la Universidad de Chile. Este trabajo es parte del proyecto Fondecyt de iniciación Nº 11110446 desarrollado por la Dra. en Ingeniería Viviana Meruane, Profesora Guía de este Trabajo de Título.

Ingeniero Civil Matemático / El propósito de esta memoria es estudiar un modelo de aprendizaje en juegos repetidos. A diferencia de otros esquemas estudiados en la literatura, en este caso se estudia una situación en que los jugadores disponen de muy poca información, pudiendo observar solamente el pago recibido en cada etapa pero sin observar las estrategias usadas por los demá́s jugadores ni sus correspondientes pagos. En base a la información individual recolectada a medida que se desarrolla el juego, cada jugador genera una percepción del pago esperado de las distintas estrategias puras, y en base a estas percepciones adapta su comportamiento para las siguientes etapas del juego. En el capítulo 1 se presentan los modelos de las principales referencias bibliográficas, junto a los resultados mas relevantes que allí se obtienen. Se definen además las instancias y variantes a los modelos anteriores con las que se trabajará a lo largo de esta memoria. El capítulo 2 contiene todas las herramientas técnicas y conocimientos previos que fueron necesarias para desarrollar los resultados obtenidos. Se comienza con una sección de introducción a la topología diferencial, cuya principal referencia es el texto Topology from the differentiable viewpoint de Milnor, donde el resultado de mayor interés es el conocido Teorema de Poincaré-Hopf. En la siguiente sección se describen resultados referentes a martingalas, diferencias de martingalas y algunos teoremas de convergencia. La última sección está dedicada a estudiar los algoritmos de aproximación estocástica, basado en trabajos de las principales referencias en el tema, como Benaïm, Chen y Kushner. El capítulo 3 está dedicado a estudiar el proceso de aprendizaje propuesto, que consiste en una regla de actualización de las percepciones de los jugadores sobre su espacio de estrategias puras al enfrentarse a un juego repetido, los resultados asintóticos (cuando la iteración n tiende a ∞) guarda estrecha relación con una dinámica continua asociada, cuyos puntos estacionarios corresponden a los equilibrios de Nash de un juego potencial subyacente. Bajo la regla de decisión Logit y algunas condiciones sobre los parámetros del modelo, se obtienen interesantes resultados de convergencia casi segura y con probabilidad positiva a atractores de la dinámica continua. Finalmente en el capítulo 4 se estudia el modelo de Cominetti et al. [7], para unas instancias específicas (caso de 2 y 3 jugadores con 2 rutas) con el objetivo de contar a cantidad de equilibrios del sistema.

El problema de corte y empaquetado en dos dimensiones, es un problema NP- difícil perteneciente a la familia de problemas de la optimización combinatoria. El problema combinatorio estriba en la gran cantidad de patrones de corte que puede construirse a partir de un número determinado de requerimientos y un conjunto de objetos los cuales deben ser cortados para satisfacer estos. Este problema es muy importante debido a la gran cantidad de aplicaciones que tiene en la industria. En este trabajo presentamos un estudio de los diferentes métodos que resuelven el problema, clasificándolos por métodos exactos, heurísticas y meta heurísticas. También presentamos conceptos, modelos del problema y las relaciones con otros problemas combinatorios. / -- Two dimensional cutting and packing problems is NP-hard, it belong to the family of problems of the optimization combinatory. This problem is based in the great amount of cut patterns that can be constructed from a determined number of requirements and a set of objects which must be cut to satisfy these. This problem is very important because it presents enormous applicability in the industry. In this work we presented a study of the different methods that solve the problem, classifying them by exact methods, heuristic and meta heuristic. Also we presented concepts, models and the relations with other combinatory problems.

Se tiene un grupo de requerimientos de piezas con una cantidad ilimitada de barras de algún tipo de material de tamaño estándar y éste posee mayor dimensión que el grupo de requerimientos. El problema de cortes 1D describe la utilización de las barras de tamaño estándar realizando cortes sobre ellas, de manera que se satisfaga todos los requerimientos con el menor número de barras de tamaño estándar. El problema es catalogado como NP-Difícil [Garey+79], y es ampliamente aplicado en diversos sectores de la industria tales como la maderera, vidrio, papelera, siderúrgica, etc. La presente tesis propone dos algoritmos GRASP Reactivo para el problema de cortes 1D, basado en los algoritmos GRASP BFD y GRASP FFD propuestos por [Mauricio+02], además, desarrolla un sistema de optimización basado en los algoritmos propuesto. Se realizan experimentos numéricos del algoritmo propuesto sobre 100 instancias de pruebas, de donde se obtiene una eficiencia promedio de 97.04% y una eficiencia ponderada de 97,19% para el GRASP Reactivo BFD con proceso de mejoría, además se observa que el GRASP BFD con proceso de mejoría converge más rápido al encontrar una solución, donde realiza en promedio 1237 iteraciones. Los resultados numéricos muestran una mejora del GRASP Reactivo con respecto al GRASP básico implementado por Ganoza y Solano [Ganoza+02] que obtuvo una eficiencia promedio de 96.73%. Estas mejorías se pueden explicar porque el parámetro de relajación y se ajusta de manera automática y es guiada en la búsqueda de una mejor solución. / It has a set of requirements of parts with an unlimited number of bars of some kind of standard size and material and this has increased the group size requirements. The cutting stock problem 1D describes the use of standard-size bars of making cuts on them, so that it meets all requirements with the least number of standard size bars. The problem is listed as NP-Hard [Garey+79], and is widely used in various industry sectors such as wood, glass, paper, steel, and so on. This thesis proposes two algorithms Reactive GRASP to the cutting stock problem 1D, based on the algorithms GRASP BFD and GRASP FFD proposed by [Mauricio+02], also, developed an optimization system based on the proposed algorithms. Numerical experiments are conducted of the proposed algorithm on 100 instances of testing, where you get an average efficiency of 97.04% and a weighted efficiency of 97,04%, also be seen that the GRASP BFD with improvement converges faster to find a solution average of 1237 iterations. The numerical results show an improvement of reactive GRASP with respect to the basic GRASP implemented by Ganoza and Solano [Ganoza+02], who obtained an average efficiency of 96,73%. These improvements can be explained as the relaxation parameter and is set automatically and is guided in the search for a better solution.

Magíster en Ciencias, Mención Computación / Este trabajo de tesis está dedicado al diseño e implementación de algoritmos aproximados que permiten explorar las mejores soluciones para el problema de Clustering Balanceado, el cual consiste en dividir un conjunto de n puntos en k clusters tal que cada cluster tenga como m ́ınimo ⌊ n ⌋ puntos, k y éstos deben estar lo más cercano posible al centroide de cada cluster. Estudiamos los algoritmos existentes para este problema y nuestro análisis muestra que éstos podrían fallar en entregar un resultado óptimo por la ausencia de la evaluación de los resultados en cada iteración del algoritmo. Entonces, recurrimos al concepto de Particles Swarms, que fue introducido inicialmente para simular el comportamiento social humano y que permite explorar todas las posibles soluciones de manera que se aproximen a la óptima rápidamente. Proponemos cuatro algoritmos basado en Particle Swarm Optimization (PSO): PSO-Hu ́ngaro, PSO-Gale-Shapley, PSO-Aborci ́on-Punto-Cercano y PSO-Convex-Hull, que aprovechan la característica de la generación aleatoria de los centroides por el algoritmo PSO, para asignar los puntos a estos centroides, logrando una solución más aproximada a la óptima. Evaluamos estos cuatro algoritmos con conjuntos de datos distribuidos en forma uniforme y no uniforme. Se encontró que para los conjuntos de datos distribuidos no uniformemente, es impredecible determinar cuál de los cuatro algoritmos propuestos llegaría a tener un mejor resultado de acuerdo al conjunto de métricas (intra-cluster-distancia, índice Davies-Doublin e índice Dunn). Por eso, nos concentramos con profundidad en el comportamiento de ellos para los conjuntos de datos distribuidos en forma uniforme. Durante el proceso de evaluación se descubrió que la formación de los clusters balanceados de los algoritmos PSO-Absorcion-Puntos-Importantes y PSO-Convex-Hull depende fuertemente del orden con que los centroides comienzan a absorber los puntos más cercanos. En cambio, los algoritmos PSO-Hungaro y PSO-Gale-Shapley solamente dependen de los centroides generados y no del orden de los clusters a crear. Se pudo concluir que el algoritmo PSO-Gale-Shapley presenta el rendimiento menos bueno para la creación de clusters balanceados, mientras que el algoritmo PSO-Hungaro presenta el rendimiento más eficiente para lograr el resultado esperado. Éste último está limitado al tamaño de los datos y la forma de distribución. Se descubrió finalmente que, para los conjuntos de datos de tamaños grandes, independiente de la forma de distribución, el algoritmo PSO-Convex-Hull supera a los demás, entregando mejor resultado según las métricas usadas.