Tesis para optar al grado de Magíster en Ciencias, Mención Computación / El modelo cosmológico actual y más aceptado del universo se llama Lambda Cold Dark Matter. Este modelo nos presenta el modelo más simple que proporciona una explicación razonablemente buena de la evidencia observada hasta ahora. El modelo sugiere la existencia de estructuras a gran escala presentes en nuestro universo: Nodos, filamentos, paredes y vacíos. Los vacíos son de gran interés para los astrofísicos ya que su observación sirve como validación para el modelo. Los vacíos son usualmente definidos como regiones de baja densidad en el espacio, con sólo unas pocas galaxias dentro de ellas. En esta tesis, presentamos un estudio del estado actual de los algoritmos de búsqueda de vacíos. Mostramos las diferentes técnicas y enfoques, e intentamos deducir la complejidad algorítmica y el uso de memoria de cada void-finder presentado. Luego mostramos nuestro nuevo algoritmo de búsqueda de vacíos, llamado ORCA. Fue construido usando triangulaciones de Delaunay para encontrar a los vecinos más cercanos de cada punto. Utilizando esto, clasificamos los puntos en tres categorías: Centro, borde y outliers. Los outliers se eliminan como ruido. Clasificamos los triángulos de la triangulación en triángulos de vacíos y centrales. Esto se hace verificando un criterio de distancia, y si los triángulos contienen outliers. Este método nos permite crear un algoritmo de búsqueda de vacíos rápido y robusto. Adicionalmente, se presenta una versión paralela del algoritmo.

En esta tesis, el algoritmo de SLAM localización y mapeo simultáneoha sido integrado con técnicas de planificación, con el fin de obtener trayectorias para vehículos terrestres en ambientes exteriores. El algoritmo de SLAM permite que el vehículo obtenga una representación del ambiente en un mapa variante en el tiempo al que podrían asociarse múltiples capas de datos, donde estas capas pueden incluir información diversa tal como: presencia de obstáculos, pendiente o altura del terreno, tipo de suelo, etc. Este mapa es dividido en regiones con alta correlación interna utilizando técnicas de geometría altamente eficientes desde el punto de vista computacional, con estructuras de datos y abstracciones que permitan manejar grandes cantidades de información. Estas regiones a su vez son divididas logrando una resolución en dos niveles de la información. Una que se denomina global y divide a todo el mapa conocido, y otra local que fracciona cada una de esas regiones. Con esta representación del ambiente, o en forma simultánea con la adquisición de ésta, es posible hallar trayectorias mediante técnicas de planificación. Con este fin, se definen criterios que permitan utilizar en la plani-ficación las múltiples capas de información permitiendo la utili-zación de cualquier algoritmo existente para este propósito. Esta aproximación permite lograr un algoritmo que es más eficiente que cualquier algoritmo de planificación existente para ambientes en exploración como se enfrentan en aplicio-nes de SLAM. Finalmente, como ejemplo de la estrategia propuesta, se generan trayectorias a partir de un modelo cinemático de un vehículo de cuatro ruedas y una estrategia de control. Se elige la velocidad lineal deseada del vehículo y se observa la limitación en el ángulo de giro del volante, con el objetivo de evaluar el desempeño del mismo mediante simulaciones numéricas y datos experimentales. / In this thesis, the SLAM algorithm Simultaneous Localization and Mapping has been integrated with planning strategies in order to achieve trajectories for land vehicles in outdoor environments. The SLAM algorithm allows the vehicle to obtain a representation of the environment in a time varying map. This time varying map could contain multiple layers of information, where these layers may include many types of data such as obstacles, slope or height of the terrain, etc. The map is divided into regions that have a high correlation using computational geometry techniques, which are highly efficient from the computational point of view. Towards this end, data structures and abstractions which can handle a significant amount of data are defined. Additionally, these regions are divided achieving two levels of inform: global and local. At global level, the whole known map is divided and at local level, each region is partitioned. Either once the repre-sentation of the environment is achieved or simultaneously with this process, it is possible to find trajectories using planning techniques. Criteria are defined to make use of the multiple layers of information at the planning stage and a particular type of planning algorithm is used, but there is a wide range of possible algorithms. This approach allows to achieve an algorithm that is more efficient than any existing planning algorithm for environments under exploration. Finally, to exemplify the proposed strategy, a kinetic model of a carlike vehicle is used with a control strategy to obtain trajectories. In these trajectories, the speed of the vehicle is chosen roughly constant and the limits of the steering angle are observed. The performance of the whole scheme is assessed through numerical simulations and experimental data.