In the Fast Marching algorithm the highest priority is assigned to the Current configuration xtop with the lowest estimate etop = v(xtop), see table 3.
Table 3. List of Current configurations stored in a priority queue. The highest priority is given the to lowest estimate e: etop < e1 < e2 < ... < eN.
Since u(x) does not depend on the goal configuration, the distance function u is built symmetrically around the start configuration, see figure 2.a. In this figure, distance maps and trajectories have been computed over a constant cost map. We use cool colours for small distances and hot colours for high distances (in arbitrary units).
In the FM* algorithm the highest priority is assigned to the Current configuration xtop with 1 1
the lowest estimate etop = — v(xtop) + — He(xtop, xgoai). Here He(xtop, xgoal) is the heuristic that estimates the residual distance between the Current configuration xtop and the goal configuration xgoal. Similarly to the A* algorithm, instead of exploring around the start configuration, the FM* algorithm focuses the search towards the goal configuration, see figure 2.b.
Bi-directional versions of these grid-search algorithms can also be implemented. We just have to launch the grid-search algorithm simultaneously from the start and the goal configurations. We stop it when the two sets of Accepted configurations are merging.
Was this article helpful?