INTRODUCTION

1.BFS (Breadth-First Search):

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes first, before moving to the next level neighbors.

It simply add neighbors of the given square on the grid into a queue for next search, and use a so-called closed list(in python we use 'set') to record whether a square is visited

2.A* Search:

A* Search algorithm is one of the best and popular technique used in path-finding and graph traversals.

What A* Search Algorithm does is that at each step it picks the node according to a value-‘f’ which is a parameter equal to the sum of two other parameters – ‘g’ and ‘h’. At each step it picks the node/cell having the lowest ‘f’, and process that node/cell.

We define ‘g’ and ‘h’ as simply as possible below

g = the movement cost to move from the starting point to a given square on the grid, following the path generated to get there.

h = the estimated movement cost to move from that given square on the grid to the final destination. This is often referred to as the heuristic, which is nothing but a kind of smart guess

3.JPS(Jump Point Search):

Jump Point Search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers.

Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude

4.Subgoal Graphs

This method preprocesses eight neighbor grids to generate subgoal graphs which can be used to find shortest paths fast. We place subgoals at the corners of obstacles and add those edges between subgoals that are necessary for finding shortest paths, while ensuring that each edge connects only subgoals that are easily reachable from one another.

After compressing the original grid map to high-level graphs, we can simply use A* search to find the shortest path.


Fig. 1


Fig. 2


Fig. 3


Fig. 4

心得感想

這次專題一開始的目標是做Deep Learning相關的東西,所以一開始接觸了很多跟DL有關的課程跟paper,後來因為工作分配的關係變成做一些路徑搜尋的演算法,所以也讀了這部分的一些paper,這次專題帶我們認識了目前很火紅的人工智慧,也接觸了演算法的領域,收穫很多。