Grid Graph Reduction for Efficient Shortest Pathfinding

作者：CHAN-YOUNG KIM AND SANGHOON SULL

文章提出了一種“基于模式識別的網格阻塞”（ Pattern-Based Blocking on grid graphs，PBGG）的預處理方法，以加快最短路徑規劃算法的運行速度。
文章設計了多種大小為 $3\times 3$ 的卷積核，通過卷積的方式的方式迭代地將非障礙物單元格阻塞，通過阻塞這些非障礙物單元格達到減少搜索空間的目的，同時能夠確保構成最短路徑的單元格不受到阻塞。
文章針對的兩種類型網格地圖：一類是占據網格地圖，不帶有權重信息（最簡單表示方式是二進制表示）；另一類是帶有權重或路徑代價的網格（在這種情況下，鄰接網格之間的路徑代價通常不是距離）。文章中Fig11給出的是針對占據網格地圖設計的卷積核；Fig13給出的是針對帶有cost信息的網格地圖設計的卷積核。

模式識別方面：
文章共考慮了四種模式：Dead-end模式（死胡同模式）、Avoidable模式（可避免模式）、$\alpha$-type模式、nonblock模式（不可阻塞模式）。
文章中Fig3給出了該模式識別的一個流程示意（不過文章并沒有標注出來這是4鄰域分支的PBGG方法）

Dead-end模式（死胡同模式）：網格地圖中存在一些可通行網格，它們通常被障礙物網格包圍，當這些網格不是起始網格或目標網格時，它們將不是構成路徑一部分的網格，因此沒有必要進行計算和搜索。

Avoidable模式（可避免模式）：網格地圖中存在一些可通行網格，這些網格并沒有被障礙物所包圍，但是這些網格由于并不是構成最短路徑的最佳候選區域，因為可以避免在規劃過程中被計算，從而加快規劃速度。

$\alpha$-type模式和nonblock模式被提出是為了解決卷積缺乏全局視野的問題。本文提出的Dead-end模式和Avoidable模式識別使用的$3\times 3$的卷積，每次卷積只能注意該范圍的視野，這就導致在卷積過程中，由于缺乏全局信息而將某些非障礙物網格阻塞，從而無法搜索出最佳路徑。
$\alpha$-type模式和nonblock主要是為應對Avoidable模式而存在的（我個人的看法，粗略地計算了一下，感覺只有Avoidable會比較有影響）
文中給出的實驗結果

代碼實現部分文章并沒有給出來（但是我這里有python實現No cost map的版本PBGG)

并且自己用了兩張圖做了一下實驗，采用的地圖來自于(Benchmarks for Grid-Based Pathfinding)[https://movingai.com/benchmarks/grids.html]，分別是random-512-20-6、maze-512-4-4和Shanghai-1-1024地圖。
![在這里插入圖片描述](https://img-blog.csdnimg.cn/direct/5


效果還是可以的，尤其是對于迷宮、狹窄走廊類的地形看起來很不錯。
該論文非常具有創造力，將網格地圖和圖像進行聯系，并提出相應的模式別技術，減少網格空間加快路徑規劃。