Since changes appear dynamically in the cost function, any configuration x e Q may be updated more than once. The computation process of the distance function needs to be dynamic and the previous division between Accepted, Current and Unvisited sets of configurations is not compliant any more with a refresh of an Accepted configuration. Recall that an Accepted configuration in the static FM algorithm is frozen. Several updates of the estimate v(x) of the distance function u for a configuration x in Current is possible but the exploration process can only proceed forward from Unvisited to Accepted such as a flame in a landscape. The "engine" of this mechanism is that, at each iteration of the FM algorithm, the configuration xtop is moved from Current to Accepted. Then, its neighbours are updated, and the process continues until the goal configuration (initially tagged as Unvisited) is set as Accepted. The "Unvisited-Current-Accepted" scheme is well designed for static problems since a configuration can only proceed one way:
In the DFM algorithm, the "tripartite" structure "Unvisited-Current-Accepted" is removed and replaced by a more subtle mechanism between the estimate v and the distance function u. The latter structure is made dynamic by the fact that the relationship between u and v is bilateral. The estimate v, which is affected by changes in the cost function t, is computed from u, but u itself is computed from v:
This mechanism, described in detail in the pseudo-code of the next section, stops when v and u match. The "engine" that leads to the "bipartite" agreement between v and u is the processing of a priority queue Q that contains exactly the inconsistent configurations defined as follows (Koenig et al., 2004). A configuration x is called locally consistent if v(x) = u(x) and is called locally inconsistent if v(x) ^ u(x). In (Philippsen & Siegwart, 2005), the authors reproduce this inequality in their pseudo-code. However, since Fast Marching methods use real numbers for approximating the distance function, a tolerance 8 (set empirically at 0.1 in our implementations) must be introduced in the DFM algorithm so that the previous inequality becomes:
Was this article helpful?