Binary using fast marching method research paper pdf download

Need an account? Click here to sign up. Download Free PDF. Fast marching methods in path planning. Santiago Garrido. Luis Moreno. Alberto Valero-gomez. Javier Gomez. A short summary of this paper. Gomez, Santiago Garrido, Luis Moreno Abstract—This paper gives a comprehensive view of the fast collision-free branches are stored and new branches are created marching methods for path planning developed by the authors iteratively until the goal point is reached.

Another option is of this work. The saturated variation of the existing FM2 There are also potential field based approaches [5] in which the provides safe paths which avoid unnecessary long trajectories robot is treated as a particle under the influence of an artificial like in the Voronoi Diagram computed trajectories. The main problem with these methods is that reduces considerably the computation time.

As a result, these they can have local minima. If the path falls in a local minima methods provide not only a trajectory, but also an associated control speed for the robot at each point of the trajectory. The a correct path will not be found even if it exists.

These methods are based on cre- time. The Heuristic Fast Marching Method can be applied to create the potential fields and to obtain artificial local minima free fields, thereby I. The authors have applied the Fast Marching Path planning is a well-known problem with a well- method successfully combining it with a Voronoi diagram [6] understood mathematical basis.

It already has many ap- and applying the Fast Marching method iteratively [7]. The characteristics of the paths provided by the the Fast Marching Method, its formulation, implementation different existing algorithms change if the path planning is and first approaches to path planning solving. The path planning objective has changed since variation is introduced: Fast Marching Square - Star Method. In the beginning, the goal Next, in Section IV the results of the new proposed method are was to create an algorithm able to find a path from an initial shown in comparison with the Fast Marching Square Method.

Since this objective has been work is outlined. Dijkstra algorithm and computational capacity has increased exponentially, the objective has become more challenging: the current objective is to find the shortest II.

These The Fast Marching Method is a particular case of Level solutions are also expected to provide smooth, human-like Set Methods, initially developed by Osher and Sethian [8]. It paths. This method has been applied to different depending on the way the information is discretized [1]: research fields including computer graphics, medical imaging, Combinatorial Planning, which constructs structures which computational fluid dynamics, image processing, computation capture all the information needed in path planning [2], [3] of trajectories, etc.

If a stone is thrown into [3]. In the first group the most widespread methods are those a pond, a wavefront is originated, and this wave expands with based on road maps, which mainly consist in obtaining pre- a circle shape around the point where the stone fell. In this calculated short paths from the map road map and creating example the fluid is always water, thus the wave expansion the path by taking the needed sections of the road map.

Instead, if we repeat this experiment mixing water exploring random trees RRTs [4] provide a fast solution and oil, we would observe that the wave expands at different based on creating random branches from an initial point.

The speeds in each medium. As a consequence, the wavefront will not be circular any more. In the fast marching method, the wavefront is called the interface. The interface can be a flat curve in 2D, or a surface in 3D but the mathematical model can be generalized to n dimensions. The fast marching method calculates the time T that a wave needs to reach every point of the space.

The wave can be originated from more than one point, each source point originates one wave. The speed, denoted F , does not have to be same everywhere, Figure 1: Iterative Wave Expansion with 1 Source Point but it is always non-negative. The T x function orig- a Initialization.

These cells are only a global minima at the source and no local minima. As labelled as frozen. A local minima would of them. This cell is then labeled as frozen. The narrow band to solve the Eikonal Equation over a gridmap. Cells are ordered by increasing T value first cells have lesser T values. Implementation c Finalization: When all the cells are frozen the narrow band is empty the algorithm finishes. In Fig. To do so, the cells of the gridmap must be labelled wave is originated from one point.

In 2 there are two wave as one of the following types: sources. Gray points are the narrow band, while white ones are wave front has not reached the cell. They are assigned a T value that can themselves growing together. The iterative process expands still change in future iterations of the algorithm. If we consider T as the third dimension over the z axis, the The algorithm has three stages: initialization, main loop, and result of completing the wave expansion of Figures 1 and 2 finalization.

These stages are described below. It should be noted that end with a single source, there is only one minima located at the end source. Fast Marching and Path Planning gkl. At obstacles, if gkl. If we want to compute the path between two points p0 and p1 we could expand a wave from p0 end until it reaches p1 or viceversa.

Due to the wave expansion end properties, the path that the wave interface has followed from end the target to the source point will always be the shortest end trajectory in time. As the wave expansion speed is constant, end this trajectory is also the shortest solution in distance.

The Algorithm 1: Fast Marching Algorithm wave is originated from the target point, hence, the computed T x field will have only one global minima at the target point.

Hence, following the maximum gradient direction from To trace the path between po and p1 we just need to the initial point we will reach the target point, obtaining follow the maximum gradient direction starting at p1 target the trajectory. This solution is unique and the algorithm is point. The path is computed iteratively. We want to trace the shortest path process is repeated successively until p0 is reached. As p0 is from po to p1. The resulting gridmap stores at any pixel the time T III.

The isocurves join together all the points that have been passed through The path calculated in the previous section is the shortest at the same instant of time Fig. These curves are the in length but it might not be a safe due to its proximity to trace of the front wave.

If we compute the maximum gradient obstacles. This aspect also causes that it is not the shortest in direction at any point of the gridmap we obtain the normal time, as the robot must move slowly when it is close to the direction to the isocurve, that is, the direction the curve has obstacles in order to avoid collisions or risky movements. The maximum gradient direction is The usual solution is to expand obstacles before calculating computed applying the Sobel operator over the gridmap.

FM over Voronoi Diagram Since the Voronoi Diagram concept is simple and intuitive, it can be applied to a large number of applications, including path planning.

Given a finite set of objects in a space, all locations in that space are associated with the closest member of the object set. Thus, the space is partitioned into a set a Original Map of regions, called Voronoi regions. The Generalized Voronoi Diagram is the set of the points which belong to the frontier between regions.

The Voronoi Diagram is used as a way to obtain a roadmap of the map. Then the Fast Marching method is used to search for a path over the Voronoi Diagram.

Applying fast marching over the Voronoi roadmap decreases the time spent in the search with respect to other existing methods. The main steps of this method are the following: 1 Map preprocessing. The map is turned into a binary grid b Path and Wave Expansion in Gray Scale map, where the obstacles are black value 0 and the clear space is white value 1.

The obstacles and walls are enlarged in order to ensure the robot will not collide with walls or obstacles nor accept passages narrower than its size. Also, an averaging filter is applied with the objective of erasing small hairs of the diagram. The diagram is obtained using mor- phological image processing techniques concretely the methods proposed by Breu in 2D [13] and Gagvani [14] in 3D. The diagram is dilatated, obtaining a thickened Voronoi Diagram wherein to apply the Fast Marching method.

The Fast Marching method is used to create a potential field which represents the propagation of a wave from the goal point , to which time is added as the third axis in 2D or the fourth in 3D see Fig.

This matrix is obtained using the obstacles and walls initially set for the FM method. This way, the matrix Wit is composed of real num- bers, with value 0 in the walls and obstacles and real grey levels in the rest. The grey levels are darker near walls and obstacles. The partial goal points are calculated using the leader path and the desired formation. The distance from the partial goals to the leader path is proportional to the grey level of the partial goals position. This way, the formation tends to be near the initial positions and partial goals act as attractive forces between the vehicles.

The distance matrices Dti are calculated applying the FM method to the metrics matrix Wit for each robot, using as goal the partial goal of the previous step. The path of minimum distance measured with the metrics Wit from each vehicle to its partial goal is found using its Dti potential and the gradient method. All the robots move a fixed number of points on the corresponding path.

The leader advances its path position a fixed number of points on the initialization path. The aforementioned attractive and repulsive forces between the vehicles act as glue in order to maintain the formation, but with enough freedom to take the other obstacles, bends, and narrow passages into account.

Some interesting aspects of the process are shown in figure 5. Adding Springs When there are highly symmetric situations, i. In order to solve this problem, it is necessary to introduce a precedence order. For example, if there is no room for the two robots to pass, the second one has to pass first, and then the third the first is the leader.

The solution proposed to this problem is to calculate first the complete trajectory for the second follower and then the complete trajectory for the last follower. This provides an effect similar to using springs with different stiffness between the robots. This effect can be seen in figures 7 and 9. Another possible solution to solve these highly symmetrical situations is to find the VFM joined trajectory for two followers in four dimensional configuration space resulting from the union of the two followers.

This matrix is binary. The fact of having the other vehicles as obstacles acts as repulsive force between the vehicles. The matrix W i t is composed by grey levels that are darker near walls and obstacles. The distance of the partial goals to the leader path is proportional to the grey level of the position. This way the formation tends to be near the initial ones and partial goals act as attractive forces between the vehicles. Figure 4: Flowchart of the proposed algorithm.

Maximum Energy Configuration Another interesting problem refers to what the formation must do if the nearest passage is narrower than the width of the robot formation, where the width of the formation is the orthogonal diameter to the movement direc- tion. The solution is to specify the smallest possible formation size or the maximum energy configuration beforehand and search for another possible passage larger than this size. The solution proposed is to dilate the walls and obstacles with the min- imum radius of the robot formation.

Then, the trajectory of the leader is found using this dilated map. This way, it is ensured that the formation passes through the passage used by the leader trajectory. Using this trajec- tory, the rest of the algorithm is similar to the main method: 1.

The distance matrices D are calculated using the metrics matrix W for each robot, using as goal the partial goal of the previous step. The minimum distance path to the partial goal is found using the po- tential D. All the robots move a fixed number of steps on the corresponding path. The leader advances its path position a fixed number of steps.

Reduction of the operational cost Although the FM method is very fast the computation time is 0. For this reason some techniques should be used to make the algorithm faster. To achieve this, the VFM method is applied in a tube around the trajectory calculated for the leader.

Thus, the propagation of the FM wave across the map is calculated only the first time to find the trajectory for the leader; the other times once per cycle and follower robot it is calculated in a tube around this trajectory, which drastically reduces the computation time. The formation does not use passages narrower than its maximum energy configuration.

To achieve this, this trajectory is dilated to get a tube, and the intersection between this tube and the map obtained from the environment walls and obstacles is used as the starting matrix Woti see figure Using the map obtained in the previous step, a wave is propagated starting from the points representing the obstacles and walls.

The result is a potential map, which can be interpreted as a velocity map or slowness map , as shown in figure 10c. Based on the previous slowness map, the FM method creates a new potential Dti that represents the propagation of the electro- magnetic wave from the goal to the robot position. An even more important reduction of the computation time is related to the matrix Dti , as follows.

As the vehicles are very close to the partial objec- tives, the expansion of the wave over the whole map is not necessary, but just its expansion into the tube, from the partial goal point to the corresponding vehicle. With this change the computation time of the matrix Dti , which is the most time consuming part of the algorithm, goes from 0. The parallelized version of the algorithm has an algorithm cycle of about 0.

Simulation Results The algorithms of the previous sections have been tested using Matlab simulations. A program has been created in which the initial and goal points are given and the VFM method is used for the leader and the rest of the formation. The method uses a nominal desired formation that are the partial goals with a distance orthogonal to the leader trajectory proportional to the grey level of the actual position.

The results are shown from figure 6 to figure 8. The method has been designed for holonomic robots, but it is possible to apply the techniques that we used for non-holonomic robots in [18].

The method has been used giving a sequence of points, joining these points with lines to obtain the leader trajectory. In this case, the direction in the given points changes abruptly. The inter-vehicle desired distance has a maximum value in open areas and proportional to the refraction index in the rest. This way, in small corridors the followers can be near each other.

Figure 6 shows an example of a team composed by two vehicles following a moving leader using the main proposed method. The lines connecting each of the three vehicles represent the formation links between them. The circles represent the partial objectives that change at each step of the algorithm. The lines from vehicles to the circles are the partial paths calculated using VFM. Figure 7 shows a similar case using the proposed method with springs of different stiffness.

With this improvement the symmetry of the followers paths is broken and it is easier to pass trough small passages. The EVT can be considered as a viscosity or the inverse of the velocity of the medium. This way the method gives a maximum velocity in each point of the trajectory as shown in Figure 8e.

In the simulations, the algorithms always determine a safe path where the robots avoid obstacles, keep the formation geometry in open space, and deform it when necessary to handle the presence of obstacles. Simulation results show that the method does not have local minima, which naturally results from the method used light propagation has no local minima and is a distinctive property with respect to potential fields and other similar meth- ods in the class of motion planning algorithms.

Furthermore, the method naturally ensures trajectory tracking by all the formation robots, since it naturally induces the required velocities at each point, if one wants to reach the goal in minimum time, taking into account the constraints imposed by the presence of obstacles and the formation geometry.

Conclusions and Future Work This paper presents a new methodology for the motion of a formation of holonomic robots. The formation is maintained by calculating the trajectory of the formation leader. In each iteration of the algorithm, using this tra- jectory, the partial robot objectives are calculated.

These partial objectives maintain the formation and have a variable distance between them propor- tional to the light velocity in that point inverse of the refraction index. Each robot has an environment map with the other robots as objects. This map is used to construct the refraction index map or metric P x using the FM method.

Using this metrics, the distance function D x representing the distance function measured with the metrics P x is built with the FM method. The partial trajectory of each robot is calculated with the gradient method. The general trajectories have a behavior like the light trajectory in a space with larger refraction index near the obstacles and walls and with an attraction force that tries to maintain the formation.

The proposed method is highly efficient from a computational point of view, since the Fast Marching complexity is O n and the Extended Voronoi Transform complexity is O n , where n is the number of cells in the environ- ment map. The main contribution of the method is that it robustly achieves smooth and safe motion plans in real time that can be used at low control levels with- out an additional smoothing interpolation process.

This allows the method to fuse collision avoidance and global planning in only one module, which can simplify the control architecture of the mobile robot, and without local minima, as in the case of the potential fields original method and some other algorithms in the same class. Additionally, it pushes the state of the art in formation control since it introduces an algorithm that simultaneously enables deformable formations, as in [8], but avoids the local minima problem of potential fields [14] by using a distance function based on a metric built with the FM method.

This is particularly relevant for the formation to handle concave obstacles without some of the formation robots being trapped in the obstacles, due to local minima of the inter-robot composition of attractive and repulsive potentials, as reported in [10].

Moreover, the path of the leader to the goal avoids obstacles and is free of local minima, since it relies on the VFM method. Other local-minima free methods could be used for the latter purpose, e. The future work is related with the introduction of sensor noise, uncer- tainty in the map with connections with SLAM and the introduction of small obstacles and moving obstacles.

All these questions can be implemented by adding Gaussian functions that model the uncertainty to the distance potential Dti of each robot. References [1] R. Beard, J. Lawton, F. Balch, R. Egerstedt, X. Das, R. Fierro, V. Kumar, J. Ostrowski, J. Spletzer, C. Fierro, P. Song, A. Das, V. Kumar, Cooperative control of robot formations, in: R.

Murphey, P. Pardalos Eds. Ogren, E. Fiorelli, N. Leonard, Cooperative control of mobile sen- sor networks: Adaptive gradient climbing in a distributed environment, IEEE Transactions on Automatic Control 49 — Leonard, E.

Fiorelli, Virtual leaders, artificial potentials and coordinated control of groups, in: Proc. MacArthur, C. Crane, Compliant formation control of a multi- vehicle system, in: Proc. Fazenda, P. Lima, Non-holonomic robot formations with ob- stacle compliant geometry, in: Proc.

Garrido, L. Moreno, D. Moreno, M. Abderrahim, D. Blanco, F.