Evaluación de técnicas de representación del espacio en 3D para su uso en navegación

Abstract

El área de la navegación es muy importante en campos como la robótica, la simulación, la animación y los juegos. [1] Aunque el problema de la navegación está muy estudiado en entornos 2D, en entornos 3D ha sido menos estudiado. Esto es debido a su mayor complejidad, e históricamente a un uso más reducido, especialmente en el campo de la robótica. Con la popularización de los vehículos aéreos no tripulados, la aplicación en el campo de la robótica de algoritmos que funcionan en tres dimensiones ha aumentado de manera radical.[3][4] En este estudio se comparan distintas técnicas de representación del espacio en tres dimensiones para medir su efectividad y su eficiencia en su uso para procesos de navegación. En particular, compararemos la técnica de PRM (del inglés Probabilistic Roadmap, Hoja de Ruta Probabilística), que será probado en distintas configuraciones (que generarán distintos grafos que pueden ser más o menos apropiados para distintas situaciones), y una búsqueda por celdas basada en el uso de un Octree de Vóxeles. También compararemos ambos con una búsqueda en una simple grid de celdas, que nos permitirá tener una aproximación de la ruta óptima. Todas las técnicas serán comparadas mediante una implementación propia en el motor de videojuegos Unity. En particular, se expondrá a un agente a distintos tipos de mapa, generados proceduralmente, divididos en distintos niveles de complejidad, y en tamaños distintos. Para cada mapa, el agente tendrá que hacer un recorrido desde un punto inicial a uno final utilizando distintas representaciones del espacio. En el caso del PRM, lo probaremos en distintas configuraciones para ver el impacto de estas configuraciones. Todas las técnicas, y las diferentes configuraciones de PRM, serán probadas varias veces para tener en cuenta la variabilidad estocástica y las posibles variaciones producidas por la propia máquina como por el propio motor de Unity. La comparación se hará en base al tiempo de creación de la representación, el tiempo de creación de la ruta (en ambos casos en milisegundos), la cantidad de memoria usada, y a la longitud de la ruta obtenida.---ABSTRACT---The area of navigation is particularly important in fields such as robotics, simulation, animation, and games. [1] Although the problem of navigation has been researched extensively in 2D environments, in 3D environments it has been less studied. This is due to their bigger complexity, and, historically, to a reduced use, especially in the field of robotics. With the popularity of unmanned aerial vehicles, the application in robotics of algorithms working with three dimensions has radically increased. [3][4] In this study, different techniques of space representations are compared to measure their effectivity and efficiency in their use for navigation processes. In particular, we will compare the PRM (Probabilistic Road Map) technique, which will be tested in different configurations (which will generate different graphs that could be more or less appropriate for different situations), and a cell search based on the use of a Voxel Octree. We will also compare both with a simple cell grid search, which will give us an approximation of the most optimal path possible. All the techniques will be compared through a custom implementation in the game engine Unity. In particular, an agent will be exposed to distinct types of procedurally generated environments, with various levels of complexity, and of different sizes. For each environment, the agent will have to create a path from a starting point to a goal using different space representation techniques. In the case of PRM, we will test it with different configurations to see the impact of these configurations. All the techniques and different configurations of PRM will be tested multiple times to consider the stochastic variability and the possible variations produced by the machine and by the Unity engine. The comparison will be made based on the time to create the space representations, the time to calculate the path (both in milliseconds), the amount of memory used and the length of the final path.