Hybrid A Star 路徑規劃（2）

1 人贊了文章

Hybrid A Star和普通的A Star的最大不同可見下圖，在普通的A Star中，我們不會考慮運動物體的方向，而且也不考慮物體的運動實際，我們假定物體總能轉移到鄰近格點中。但在Hybrid A Star中我們需要考慮物體的方向，在下圖中我們用帶箭頭的點來表示一個物體的位置。而且在普通的A Star中物體總是出現在網格的中心，但是由於Hybrid A Star中，我們考慮了物體的實際運動約束，所以它們並不一定出現在格點的中心。由一個特定的位置出發，物體在下一步搜索中只能到達它可能到達的位置，比如在汽車中，受制於汽車轉向角的限制。下圖中綠色箭頭表示車輛前進時候可能到達的幾個位置，藍灰色箭頭表示倒退時幾個可能的位置。

不過Hybrid A Star繼承了A Star的很多思想，比如都還有Open和Close集合，都還有兩種花費，實際花費g，預期花費h。但是這兩種花費定義的都比A Star中來的複雜，在A Star中我們定義的g只有走過的距離，但在Hybrid A Star就考慮很多其他因素，比如說轉向角轉向角的改變，是否倒車，車輛行駛方向是否改變等。如果用 表示車輛的轉向角，D表示車輛的行駛方向，s表示每次搜索所走的路程。下圖是該計算實際花費的過程， 是參數。

另外預期花費h也不同於A Star中的歐式距離，我們選擇了由A Star所得的到達終點的花費來作為Hybrid A Star的預期花費。

上圖是所有的障礙物點，終點被定為7, 2，那麼下圖就是通過A Star得出的每一個格點到終點的花費，在這裡每個格點的解析度是2。

還有一個就是必要演算法就是柳夢璃：Reeds-Shepp 曲線的Matlab實現，我之前就已經介紹過了，不在這裡介紹了，也就對應下面的RSExpand演算法。Id就是求物體在所在格點位置，注意不同於A Star演算法，格點共有三個維度，因為物體多了方向屬性。演算法簡列如下：

下面給幾個視頻感受一下，由於演算法比較長，就不在這邊放源碼了，感興趣可以私信哈。

https://www.zhihu.com/video/1006924511857532928 https://www.zhihu.com/video/1006924555599908864 https://www.zhihu.com/video/1006924606246105088 https://www.zhihu.com/video/1006924655126581248
推薦閱讀：