FM algorithm

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).

Fig. 2. Examples of distance maps and trajectories computed over a constant 100x100 cost map (t = 1) using a 4-connexity: a) FM algorithm and b) FM* algorithm (using the Euclidean distance He as a heuristic).

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?

0 0
Learn Photoshop Now

Learn Photoshop Now

This first volume will guide you through the basics of Photoshop. Well start at the beginning and slowly be working our way through to the more advanced stuff but dont worry its all aimed at the total newbie.

Get My Free Ebook

Post a comment