Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Eléctrica / La extracción de características es una tarea crítica en la localización y mapeo simultáneo o Simultaneous Localization and Mapping (SLAM) basado en características, que es uno de los problemas más importantes de la comunidad robótica. Un algoritmo que resuelve SLAM utilizando características basadas en LiDAR es el algoritmo LiDAR Odometry and Mapping (LOAM). Este algoritmo se considera actualmente como el mejor algoritmo SLAM según el Benchmark KITTI. El algoritmo LOAM resuelve el problema de SLAM a través de un enfoque de emparejamiento de características y su algoritmo de extracción de características detecta las características clasifican los puntos de una nube de puntos como planos o agudos. Esta clasificación resulta de una ecuación que define el nivel de suavidad para cada punto. Sin embargo, esta ecuación no considera el ruido de rango del sensor. Por lo tanto, si el ruido de rango del LiDAR es alto, el extractor de características de LOAM podría confundir los puntos planos y agudos, lo que provocaría que la tarea de emparejamiento de características falle. Esta tesis propone el reemplazo del algoritmo de extracción de características del LOAM original por el algoritmo Curvature Scale Space (CSS). La elección de este algoritmo se realizó después de estudiar varios extractores de características en la literatura. El algoritmo CSS puede mejorar potencialmente la tarea de extracción de características en entornos ruidosos debido a sus diversos niveles de suavizado Gaussiano. La sustitución del extractor de características original de LOAM por el algoritmo CSS se logró mediante la adaptación del algoritmo CSS al Velodyne VLP-16 3D LiDAR. El extractor de características de LOAM y el extractor de características de CSS se probaron y compararon con datos reales y simulados, incluido el dataset KITTI utilizando las métricas Optimal Sub-Pattern Assignment (OSPA) y Absolute Trajectory Error (ATE). Para todos estos datasets, el rendimiento de extracción de características de CSS fue mejor que el del algoritmo LOAM en términos de métricas OSPA y ATE.

No description available.

Ingeniero Civil en Computación / Los avances en computación móvil y redes inalámbricas están posibilitando grandes oportunidades de desarrollar sistemas colaborativos. La concepción y diseño de estos sistemas representa un desafío para los diseñadores de software debido a la heterogeneidad y dinamismo de las interacciones que deben ser soportadas. El poder modelar y evaluar el sistema en fase de diseño permite detectar errores y sugerir mejoras que ayuden al desarrollo dirigido a un producto final que realmente soporte el trabajo colaborativo. En este contexto, investigadores del Departamento de Ciencias de la Computación de la Universidad de Chile propusieron un lenguaje visual de modelamiento de sistemas colaborativos. El lenguaje asume que el sistema puede ser estructurado como una Human-centric Wireless Sensor Network. Éste es un tipo de red que permite modelar y entender los flujos de información de un sistema colaborativo que tiene como protagonistas a las personas. El lenguaje de modelamiento permite representar un sistema colaborativo como un grafo, en el que se encuentran caracterizados sus participantes y la forma en que estos interactúan. En este trabajo de memoria se diseñó e implementó una herramienta gráfica destinada a diseñadores de software que permite el modelamiento de sistemas colaborativos usando el lenguaje propuesto por los investigadores. La herramienta fue desarrollada como una aplicación web en la que interactivamente se pueden definir los participantes del sistema colaborativo y sus interacciones. La representación de los escenarios en forma de grafo permite aplicar metodologías de análisis en forma automática. En esta memoria se adaptaron e implementaron dos análisis que fueron desarrollados para un lenguaje similar. El primero es un análisis que permite evaluar la coherencia en las interacciones entre los participantes. Para este análisis se desarrolló un algoritmo eficiente que permitió la evaluación automática a medida que el diseñador va realizando cambios en el modelo. El segundo análisis permite generar requerimientos generales de software que deben estar presentes en la aplicación colaborativa para soportar apropiadamente las interacciones modeladas. La lista de requerimientos se genera para cada participante de la red, basado en como estos interactúan con los demás. La lista generada puede ser refinada por el diseñador del sistema, de acuerdo con las necesidades particulares de cada aplicación. Se espera que la herramienta contribuya a fomentar el uso del lenguaje y de esta forma facilitar el desarrollo de sistemas colaborativos que aprovechen los nuevos e interesantes escenarios de colaboración que está permitiendo el auge de los dispositivos móviles.

Ingeniero Civil en Computación / La simulación de cuerpos que interactúan entre sí por medio de fuerzas y la detección de colisiones entre cuerpos son problemas estudiados en distintas áreas, como astrofísica, fisicoquímica y videojuegos. Un campo en particular corresponde al estudio de los coloides, partículas microscópicas suspendidas sobre otra sustancia y que tienen aplicaciones en distintas industrias. El problema consiste en simular la evolución de un sistema con distintos tipos de partículas coloidales a través del tiempo, cumpliendo las propiedades de volumen excluido, movimiento aleatorio y condiciones de borde periódicas. Además, la interacción de largo alcance entre coloides presenta la particularidad de no cumplir con el principio de acción y reacción. Se desarrolló un algoritmo de simulación completamente paralelo en GPU, implementado en la plataforma CUDA y C++. La solución utiliza una triangulación de Delaunay en memoria de la tarjeta gráfica para conocer eficientemente la vecindad de cada partícula, lo que permite resolver traslapes entre partículas sin tener que evaluar todo el sistema. Se utilizó una implementación reciente del algoritmo de edge-flip para mantener la triangulación actualizada en cada paso de tiempo, extendiendo además el algoritmo para corregir los triángulos invertidos. Para el caso de fuerzas de corto alcance, además se desarrolló un algoritmo paralelo que construye y utiliza listas de Verlet para manejar las vecindades entre partículas de forma más eficiente que la implementación anterior. Los resultados obtenidos con la implementación paralela presentan una mejora de hasta dos órdenes de magnitud con respecto al tiempo de la solución secuencial existente. Por otro lado, el algoritmo para fuerza de corto alcance mejora de igual magnitud con respecto a la solución de largo alcance desarrollada. También se verificó que la corrección de traslapes con triangulación de Delaunay se hace de forma eficiente, y que esta estructura puede ser aplicada para otros problemas relacionados, como implementar el cálculo de fuerzas de corto alcance (y compararlo con la implementación ya existente) o realizar simulaciones aproximadas utilizando triangulaciones. / Financiado parcialmente por el Proyecto FONDECYT # 1140778

Ingeniero Civil en Computación / El universo visto a gran escala presenta estructuras llamadas murallas cósmicas y vacíos cósmicos. Las murallas poseen una alta densidad galáctica, mientras que los vacíos presentan una notable baja densidad. En Astronomía son objeto de estudio y para el efecto es necesario analizar grandes volúmenes de datos, lo cual no es factible hacerlo manualmente, siendo necesarios algoritmos que identifiquen automáticamente ambos tipos de zonas cósmicas. Actualmente existen muy pocos algoritmos diseñados para esa tarea. Uno de los más recientes fue presentado en el año 2014 por Hervías et al. y permite determinar bajas densidades en "rebanadas" bidimensionales de datos volumétricos, pudiéndose extender naturalmente la forma en que trabaja al caso tridimensional. Recibe como entrada un conjunto de puntos, cada uno siendo la abstracción geométrica de una galaxia. El algoritmo tiene dos fases: triangulación y clasificación de triángulos. Se basa en la identificación de aristas largas en la triangulación de Delaunay asociada a los n puntos de entrada, para determinar bajas densidades galácticas. En su segunda fase determina en forma secuencial los triángulos que pertenecen a vacíos con una complejidad O(nlog(n)). A mediados de este año, Alonso presenta una extensión del algoritmo, agregándole una tercera fase de fusión de vacíos adyacentes. Logra una implementación que clasifica con complejidad O(nlog(n)) en forma experimental. En esta memoria se hace un razonamiento profundo sobre las propiedades de los conjuntos de triángulos que son identificados como vacíos en una triangulación. La investigación teórica realizada permite presentar tres nuevas formas de clasificación que proporcionan los mismos resultados que la original: una O(n) secuencial, una O(n) paralela y una O(log(n)²) paralela. Se implementan las O(n) desarrolladas, resultando ser experimentalmente más eficientes que la clasificación de la implementación de Alonso. En particular, la O(n) paralela exhibe un mejor desempeño que la O(n) secuencial. Con lo anterior se logra el objetivo de esta memoria. La O(log(n)²) paralela se deja propuesta para su implementación a futuro y tal vez conectarse a una triangulación de Delaunay paralela.

Magíster en Ciencias, Mención Computación / Ingeniero Civil en Computación / El problema de que un computador determine la similitud entre objetos tridimensionales es un problema que tiene aplicaciones directas en diversas áreas como la medicina, la ingeniería y la arqueología, entre otras. Si bien, dentro de los últimos años se han desarrollado varias técnicas que permiten estimar la similitud entre objetos 3D, estas técnicas presentan serios problemas al momento de realizar consultas cuando la información tridimensional es parcial. Actualmente existen muy pocas técnicas que permiten el cálculo de similitud entre objetos 3D cuando la información es parcial. Por otra parte, la evaluación de estas técnicas se ha realizado utilizando información simulada, que no representa efectivamente cómo es la información tridimensional que una máquina puede obtener del mundo real, por lo que se tiene poca información sobre si estas técnicas son realmente útiles en aplicaciones reales. Uno de los objetivos principales de esta tesis consiste en determinar si existe alguna técnica que permita determinar la similitud entre objetos tridimensionales cuando la información es parcial y proveniente de objetos reales, y evaluar su eficacia. Se evaluaron algoritmos de matching parcial en objetos 3D utilizando la información proveniente de un escáner 3D óptico creado especialmente para este fin. El trabajo constó de tres fases: (1) la creación de un escáner 3D óptico utilizando un tablet Android y un proyector digital (2) la creación de una colección de referencia de objetos 3D que incluye mallas 3D parciales (3) la evaluación de algoritmos de matching parcial en objetos 3D. El trabajo de tesis es pionero en el ámbito de la evaluación de algoritmos de matching parcial en objetos 3D utilizando mallas 3D provenientes de objetos de la vida real, sin intervención alguna. Los resultados de este proyecto permitieron obtener métricas más realistas de precision vs recall que las existentes.

Memoria para optar al título de Ingeniero Civil Industrial / 21/11/2020

Tesis para optar al grado de Magíster en Gestión de Operaciones / Memoria para optar al título de Ingeniero Civil Industrial / 28/09/2023

Magíster en Ciencias de la Ingeniería, Mención Eléctrica / Con el incremento de la delincuencia se ha hecho necesario que las fuerzas de seguridad busquen más herramientas que les permitan analizar los procesos delictivos y evaluar el posible riesgo criminal, con el fin de poder determinar las acciones tácticas, asignación de recursos policiales y planificaciones a corto y largo plazo para enfrentar este problema. Una de las formas de realizar un análisis de los delitos que ocurren en una ciudad es mediante el análisis de patrones criminales, a través del modelamiento y simulación de datos que entreguen la información necesaria para el estudio de cada una de las variables que intervienen en cada hecho. De esta forma se podrá caracterizar al criminal, su forma de actuar, sus preferencias; factores que servirán para poder predecir hechos que atenten contra de la seguridad ciudadana. En la actualidad existen en el mercado códigos y programas que permiten realizar pre- dicciones de qué zona podrá tener un alto índice de criminalidad, pero los costos de estos programas son muy elevados. La propuesta de este proyecto es generar y verificar un método para caracterizar y predecir el riesgo criminal de un área urbana determinada, usando una base de datos generada en forma artificial. Para la generación de la base de datos se usa un algoritmo que permite al usuario seleccionar un número de zonas urbanas a considerar, las mismas que están constituidas por servicios públicos o privados de todo tipo, y que una vez que se han elegido las zonas el algoritmo generará en forma aleatoria delitos asociados a cada servicio. Los datos generados son utilizados para verificar una metodología de caracterización del riesgo criminal espacial. Pero no basta con esta distribución inicial, ya que el proceso delictivo está en constante cambio. Por esta razón es necesario simular con la inclusión de la variable temporal, mediante la inserción de nueva información de eventos delictivos y la aplicación de un modelo dinámico, donde se obtendrá una distribución espacial del riesgo actualizada. Para obtener un resultado óptimo del modelo espacial, se utiliza un algoritmo de optimización para encontrar la actualización adecuada de la distribución, siendo el resultado final el que se usará en la etapa de predicción. Para la etapa de predicción se realiza un agrupamiento o clustering de la nueva informa- ción (nuevos eventos delictivos), incluidos en la etapa temporal, con la finalidad de encontrar los posibles centros de las zonas de riesgo (atractores criminales). Una vez que se tienen los centros, por medio de un modelo empírico de un atractor criminal y con una determinada ventana de tiempo, se genera una distribución de predicción del riesgo criminal.

Magíster en Gestión de Operaciones. Ingeniero Civil Matemático / En este trabajo estudiamos un par de problemas de la teoría de paradas óptimas, y mostramos cómo aplicar estos resultados en el diseño de mecanismos. Consideramos dos versiones modificadas de la famosa desigualdad del profeta [10, 16, 17]: una no-adaptativa donde la regla de parada debe ser decidida de antemano, y una adaptativa --- que corresponde a la configuración clásica de la desigualdad del profeta ---, pero en el caso restringido cuando las distribuciones de las variables aleatorias están idénticamente distribuidas [13]. Para la primera situación, encontramos un factor de garantía para la regla de parada con respecto al máximo esperado de la secuencia de variables aleatorias y demostramos que es la mejor posible; para el segundo, probamos que una conjetura sobre cuál es el mejor factor posible es verdadera [14]. Cerramos esta tesis extendiendo estos resultados para resolver el problema de un vendedor que enfrenta a muchos compradores potenciales y debe diseñar una subasta secuencial para maximizar sus ingresos. El tipo de mecanismos que consideramos para estudiar este problema de pricing son los mecanismos posted price, y los resultados que obtenemos toman la forma de factores de aproximación con respecto al valor de la subasta óptima [19]. / In this work we study a pair of problems in optimal stopping theory, and show how to apply these results in mechanism design. We consider two modified versions of the famous prophet inequality [10, 16, 17]: a non-adaptive where the stop rule must be decided beforehand, and an adaptive one --- which corresponds to the classical prophet inequality setting ---, but when the distributions of the random variables are identical [13]. For the first set-up, we find a new factor guarantee with respect to the expected maximum of the random variables sequence and prove it is the best possible; for the second, we prove that a conjecture about the best possible factor achievable is true [14]. We close this dissertation by extending these results to solve the problem of a seller that faces many potential buyers and must design a sequential auction in order to maximize its revenue. The type of mechanisms we consider to study this pricing problem are the posted price mechanisms, and the results we get are in the form of approximation factors guarantees with respect to the optimal auction [19]. / Este trabajo ha sido parcialmente financiado por Conicyt y el Núcleo Milenio Información y Coordinación en Redes