Grid fast path finding using 2k neighborhood

Tesis (Magíster en Ciencias de la Computación)Moving from a place and reaching a goal through a path can be tedious, especially when you are looking for efficiency. People, robots or even entities in video games, use Path Planning, which will deliver a sequence of actions to achieve their goal. The representation of this worlds is made through regular grids, where exist an Agent with the ability to move through this discreet world. Usually the co connectivity allow 4 or 8 movement for an Agent in each position, which can be really limited to find a better path, because the range of motion. One solution for this is a 2 k neighborhood, with the ability of get a bigger range of motion as the k is increased for k ≥ 2. In this thesis we use a 2 k neighborhoodapproaches to extend the range of motion in the algorithms Sub Goal Graph and to a different approach of Jump Point Search. The first, Sub Goal Graph look for all corner or sub goal in the map, to create a graph with only the subgoal to find a solution, with a better range of motion the solution will be more realistic. The second one is and approach of Jump Point Search but using a Canonical search and saving the best candidate to the next search. Both of the algorithms are based in A* Search. The objective is to measure the performance of the Sub Goal Graph and Jump Point Search algorithms, with the new connectivity implemented, with respect ANYA an any angle planner and Sub2-Theta*. Measuring the path cost delivered and the execution time, as a comparison. The planner based in sub goals with a 2 k neighborhoodgot optimal path faster than ANYA, having a margin of sub optimality of 0.0005%. While Jump Point Search has an 0.19% of sub optimality and 25% quicker in some cases. Also all solution had an improvement in performance and lower cost as the k is increased.Moverse desde un lugar y llegar a un objetivo por medio de un camino pueder ser tedioso, especialmente cuando se busca eficiencia. Las personas, robots o incluso entidades en video juegos, utilizan Path Planning, el cual les entrega una secuencia de acciones para lograr su objetivo. La representación de este mundo se realiza a través de grillas regulares, donde existe un Agente, que tiene la habilidad de desplazarse por este mundo discreto. Usualemente la conecticidad permite 4 o 8 movimientos para una Agente en cada posición, lo cual puede limitar el encontrar un mejor camino, dado la libertad de movimiento. Una solución para esto es 2 k , que presenta la habilidad de obtener mayores libertades de movimiento a medida que k aumenta para un k ≥ 2. En esta tesis se utiliza un acercamiento de 2 k con el fin de extender o aumentar los posibles movimientos en los algoritmo Grafos de Sub Objetivos y a un acercamiento a Jump Point Search. Primero, Grafos de Sub Objetivos, buscan por todo el mapa todas als equinas que son subobjetivos, para crear un nuevo mapa solo con los sub objetivos para encontrar una solución, con una mayor cantidad de movimientos la solución sera más realista. El segundo es un acercamiento a Jump point Seach, pero usando una busqueda cannonica y guardando los mejores candidatos para la siguiente busqueda. Ambos de los algoritmos tienen como base la Busqueda A*. El objetivo es medir el rendimiento de los algoritmos Grafos de Sub Objetivos y Jump Point Search, con la nueva contectividad implementada. La comparación sera con respecto a ANYA planificador de cualquier angulo y Sub2-Theta*. Midiendo el cosoto del plan y tiempo de ejecución como punto de comparación. El algoritmo basado en sub objetivos con 2 kobtiene un camino optimo más rapido que ANYA con un margen de suboptimilidad de 0.0005%. Mientras que Jump Pint Search tienen un 0.19% de sub optimalidad y es un 25% más rapido en algúnos casos. Cabe destacar que la solución tiene un mejor rendiemiento y un menos costo del camino cada vez que se aumentaba el valor de k