considered as a viscosity or the inverse of the velocity of the medium. In this way the method gives a maximum velocity at each point of the trajectory as shown in Fig. 8(e). Fig. 9 shows consecutive steps of the robots’ formation using the maximum energy configuration with springs. The formation does not use passages narrower than its maximum energy configuration.
Fig. 10. VFM calculated in a tube. (a) Trajectory calculated for the leader. (b) Intersection between the dilatation of the leader’s trajectory and the walls and obstacles.(c) Extended Voronoi Transform of the tube. (d) Robot formation (rectangles) with the corresponding partial objectives (circles) and the partial trajectories of the followers calculated in the tube. (e) Maximum possible velocities of the three robots.
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 this is a distinctive property with respect to potential fields and other similar methods 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’s geometry. 5. 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 trajectory, the robots’ partial objectives are calculated. These partial objectives maintain the formation and have a variable distance between them proportional to the light velocity at 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 these 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 behaviour like the trajectory of light 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 environment 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 without 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.g. [19].
Future work is related to the introduction of sensor noise, uncertainty 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.
1．What is the problem?
In a previous paper [10], we have introduced one possible solution to this problem, where the followers keep track of the n most recent positions of the leader, and not only its current position, to be dragged away from the obstacle trap. However, this method has not been proven to work for all possible situations. The main problem to deal with is how to apply this method to the robot formation’s motion, keeping its good properties.
2. How did I solve the problem?
In this paper we use the FastMarching (FM) algorithm to control a leader–follower deformable formation, where the trajectory of the leader in an environment cluttered by obstacles is computed using the VFM algorithm. Each follower attempts to reach, at each iteration step, a nominal sub-goal position related to the desired leader trajectory, but takes into account the positions o The other followers and the environmental objects, both seen as obstacles. This influences the metrics used by these algorithms effectively deforming the followers’ trajectories. In this way we ensure that non-convex obstacles do not break the formation and that the inter-vehicle distances are smoothly deformed while the formation moves from open areas to regions with obstacles narrow corridors, and narrow passages.
3. What did I find out?
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 trajectory, the robots’ partial objectives are calculated. These partial objectives maintain the formation and have a variable distance between them proportional to the light velocity at that point (inverse of the refraction index). This method allows us to maintain good response time and smooth and safe planned trajectories.
4. What does it mean?
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 without 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.