英语科技论文写作

英语科技论文写作

论文题目：学生姓名：学号：

Robot formation motion planning

using Fast Marching

Dear Editor,

Cover letter

We would like to submit the enclosed manuscript entitled \Fast Marching\

We are particularly interested in leader-following deformable formations, where the leader can be virtual and tracks a given trajectory, pulling the followers behind it according to nominal geometry specifications (e.g., desired inter-vehicle distances) that can change within a given range so as to accommodate environmental conditions. Leonard and Fiorelli introduced the concept of artificial potential fields between formation vehicles, some of them virtual leaders. The nominal inter-vehicle distance corresponds to minima of the potential functions, representing equilibrium points. We deeply appreciate your consideration of our manuscript, and we look forward to receiving comments from the reviewers. If you have any queries, please don’t hesitate to contact me. Thank you and best regards. Yours sincerely.

Highlight：As stated before, the FM method is based on a potential function without local minima that

provides smooth trajectories. The advantage of using the VFM method, as proposed here, is that each robot, at each time, has one single potential which is attractive to the objective and repulsive from walls, obstacles, and the other robots of the formation, while keeping the desired nominal inter-robot distances.

Robot formation motion planning using Fast

Marching

Abstract: This paper presents the application of the Voronoi FastMarching (VFM) method to path planning of mobile formation robots. The VFM method uses the propagation of awave (FastMarching) operating on the world model to determine a motion plan over a viscosity map (similar to the refraction index in optics) extracted from the updated map model. The computational efficiency of the method allows the planner to operate at high rate sensor frequencies. This method allows us to maintain good response time and smooth and safe planned trajectories. The navigation function can be classified as a type of potential field, but it has no local minima, it is complete (it finds the solution path if it exists) and it has a complexity of order n(O(n)), where n is the number of cells in the environment map. The results presented in this paper show how the proposed method behaves with mobile robot formations and generates trajectories of good quality without problems of local minima when the formation encounters non-convex obstacles.

OCIS codes: (100.0100) Image processing; (100.6890) Three-dimensional image processing

References and links

1. R.W. Beard, J. Lawton, F.Y. Hadaegh, A coordination architecture for spacecraft formation control, IEEE Transactions on Control Systems Technology 9 (2001) 777–790.2

2. H.G. Tanner, ISS properties of non-holonomic vehicles, Systems and ControlLetters 53 (2004) 229–235.

3. T. Balch, R.C. Arkin, Behavior-based formation control for multirobot systems, IEEE Transaction on Robotics and Automation 14 (1998) 926–939.

4. M. Egerstedt, X. Hu, Formation constrained multi-agent control, IEEE Transaction on Robotics and Automation 17 (2001) 947–951.

5 A.K. Das, R. Fierro, V. Kumar, J.P. Ostrowski, J. Spletzer, C.J. Taylor, A vision-based formation control framework, IEEE Transaction on Robotics and Automation 18 (2002) 813–825.

6 R. Fierro, P. Song, A. Das, V. Kumar, Cooperative control of robot formations, in: R. Murphey, P. Pardalos (Eds.) , perative Control and Optimization, Kluwer Academic Press, Hingham, MA, 2002.

7. P. Ogren, E. Fiorelli, N.E. Leonard, Cooperative control of mobile sensor networks: adaptive gradient climbing in a distributed environment, IEEE

Transactions on Automatic Control 49 (2003) 1292–1302.

8. N.E. Leonard, E. Fiorelli, Virtual leaders, artificial potentials and coordinated control of groups, in: Proc. of the 40th IEEE Conference on Decision and Control, pp. 2968–2973.

9. E.Z. MacArthur, C.D. Crane, Compliant formation control of a multi-vehicle system, in: Proc. of the 2007 IEEE International Symposiumon Computational Intelligence in Robotics and Automation, pp. 479–484.

10. P.V. Fazenda, P.U. Lima, Non-holonomic robot formations with obstacle compliant geometry, in: Proc. of the 6th IFAC Symposium on Intelligent Autonomous Vehicles (IAV 2007).

11. S. Garrido, L.Moreno, D. Blanco, Sensor-based global planning formobile robot navigation, Robotica 25 (2007) 189–199. 12. S. Garrido, L. Moreno, D. Blanco, Exploration of a cluttered environment using voronoi transform and fast marching method, Robotics and Autonomous Systems 56 (2008) 1069–1081.

13. S.Garrido, L.Moreno,M. Abderrahim,D. Blanco, FM2: a real-time sensor-based feedback controller for mobile robots, International Journal of Robotics and Automation 24 (2009) 3169–3192.

15. S. Garrido, L. Moreno, D. Blanco, Voronoi diagram and fast marching applied to path planning, in: Proceedings of ICRA, pp. 3049–3054.

16. O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, International Journal of Robotics Research 5 (1986) 90–98.

17. J.A. Sethian, A fast marching levelset method for monotonically advanc-ing fronts, Proceedings of the National Academy of Science 93 (1996)1591–1595.

18. S. Garrido, L. Moreno, D. Blanco, F. Martin, Smooth Path Planning for non- holonomic robots using Fast Marching, in: Proceedings of the 2009 IEEE International Conference on Mechatronics. Malaga, Spain.. 19. J. Kim, P. Khosla, Real-time obstacle avoidance using harmonic potential functions, in: IEEE Int’l Conf. on Robotics and Autom, pp. 790–796.

1. Introduction

Formation control is currently a topic of vast research in the literature. Different approaches can be classified according to different criteria. Beard et al. [1] consider the different design approaches and classify them into the following three groups. Leader-following,where one vehicle is designated as the leader and the others as followers. The leader posture (position and orientation) is determined by a trajectory to be tracked or by external control objectives (e.g., joy sticked by a human) and the followers must track the leader following some prescribed geometry, possibly dynamically changing over time [2]. Behavioral, where the motion of each vehicle results from a weighted average of several behaviors, ultimately contributing to a desired group behavior [3]. Virtual structure, where the entire formation is treated as a single structure, whose desired motion is translated into the desired motion of each vehicle [4]. Another possible criterion takes into account the rigidity of the formation geometry: some authors specify the full geometry, e.g., the distances and bearings between the vehicles of the formation, and control each vehicle to ensure that these are accurately achieved [5], requiring a coordination architecture to switch between geometries when required by the environmental characteristics (e.g., narrow passages, open spaces) [6]; others see the formation as a dynamic geometry structure, that naturally becomes distorted in the presence of obstacles and/or environmental geometry changes [7].

We are particularly interested in leader-following deformable formations, where the leader can be virtual and tracks a given trajectory, pulling the followers behind it according to nominal geometry specifications (e.g., desired inter-vehicle distances) that can change within a given range so as to accommodate environmental conditions. Leonard and Fiorelli [8] introduced the concept of artificial potential fields between formation vehicles, some of them virtual leaders. The nominal inter-vehicle distance corresponds to minima of the potential functions, representing equilibrium points.

that balance inter-vehicle repulsion, vehicle–obstacle repulsion,and follower–leader attraction. MacArthur and Crane proposed a similar approach but virtual spring-damper systems were used to ‘‘connect’’ the formation vehicles [9]. The drawback of such approaches is the well-known local minima problem of potential fields, that may lead to breaking of the formation in the presence of non-convex shaped obstacles.

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.We have also introduced a method to avoid local minima of potential fields for a single vehicle, using the Voronoi Fast Marching (VFM) method and the Fast Marching squared (FM2) method [11–13].

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, ateach 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.

The paper is organized as follows. In Section 2 the FastMarching method and some of its variants are summarized. Its application to robot formations is described in Section 3. The results of applying the method to two different formation geometries in a diversity of simulation scenarios are presented in Section 4. The paper ends with conclusions and prospects for future work (Section 5). 2. Fast Marching method and Voronoi Fast Marching method 2.1. Introduction to Fast Marching and level sets

The FM algorithm was introduced by Sethian in 1996 and is a numerical algorithm that approximates the viscosity solution of the eikonal equation |?(D(x))| = P(x), (1)i.e., the equation for light propagation in a non-homogeneous medium. The level set {x/D(x) = t} of the solution represents the wave front advancing with a medium velocity P(x), which is the inverse of the medium’s refraction index R(x). Therefore, the eikonal equation can be written as |?(D(x))| = 1/R(x). The resulting function D is a distance function, and if the medium velocity P is constant, it can be seen as the Euclidean distance function to a set of starting points, usually the goal points. If the medium is non-homogeneous and the velocity P is not constant, the function D represents the distance function measured with the metrics P(x) or the arrival time of the wave front to point x. The FM method is used to solve the eikonal equation and is very similar to the Dijkstra algorithm that finds the shortest paths on graphs, though it is applied to continuous media. Using a gradient descent of the distance function D, one is able to extract a good approximation of the shortest path (geodesic) in various settings (Euclidean distance with constant P and a weighted Riemannian manifold with varying P). 2.2. Intuitive introduction to the Fast Marching motion planner

To get a motion planner for mobile robots with desirable properties, such as smoothness and safety,we can think of attractive potentials. In Nature, there are phenomena with a similar behaviour,e.g., electromagnetic waves. If there is an antenna at the goal point that emits an electromagnetic wave, then the robot can drive to the destination by tracing the waves back to the source. In general, the concept of electromagnetic waves is especially interesting, since the potential and its associated vector field have the good properties desired for the trajectory, such as smoothness and the absence of local minima.

This attractive potential still has some problems. The most important one that typically arises in mobile robotics is that optimal motion plans may bring robots too close to obstacles or people, which is not safe. This problem has been treated by

Latombe [14], and the resulting navigation function is called NF 2The Voronoi method also tries to follow a maximum clearance map [15]. To obtain a safe path, it is necessary to add a component that repels the robot from obstacles, as proposed by Khatib [16]. In addition, this repulsive potential and its associated vector field should have good properties such as those of electrical fields. If we consider that the robot has an electrical charge of the same sign as obstacles, then the robot would be pushed away from obstacles. The properties of this electric field are very good because it is smooth and there are no singular points in the space of interest (Cfree). The main problem of attractive and repulsive potentials is how to mix the two fields together. This union between an attractive

and a repulsive field has been the biggest problem of potential fields in path planning since the works by Khatib [16]. The problem is that the sum, difference, or similar operations provoke the appearance of local minima.

In the proposed algorithm, this problem has been solved in the same way as Nature does: the electromagnetic waves, such as the light, have a propagation velocity that depends on the medium due to the refraction index. For example, a flint glass has a refraction index of 1.6, while in air it is approximately 1. This refraction index of the medium is the quotient between the light velocity in vacuum and its velocity in the medium, i.e., the slowness index of the wave front propagation in a medium. This idea of mixing the two potentials as Nature does is the main contribution of the VFM and FM2 methods [11–13].

According to Fermat’s principle, the path taken by light to go om one point to another is the path that minimizes the time. In he case of a homogeneous medium, in which the light velocity is

onstant, the light follows a straight line. The set of points achieved a fixed time is a circle. Consider two media with different fractive indexes, e.g., air and water. If a ray of light passes from

he first medium to the second one, the phenomenon known as fraction occurs. The beam appears to bend when the medium hanges. The light seems to prefer to stay in the medium with eater light velocity, as shown in Fig. 1(a). If there is a continuous hange in the refraction index of the medium, the path obtained is curve that goes away from area swith lower light velocity (higher fractive index), as shown in Fig. 1(b) and Fig. 2. This is the case the well-known hot road surface mirage, in which there appearsbe ‘‘fake water’’ on the road which is produced by the light rays ending due to a change of the refraction index in air, with higher mperature (and lower refraction index) near the road surface.

Fig. 1. (a) Propagation of a wave and the correspondingminimumtime path when there are two media of different slowness (refraction) index; (b) the same with a vertical gradient of refraction index.

Fig. 2. Hot road surface mirage: light rays bending due to change of the refraction index in air with higher temperature (and lower refraction index) near the road surface.

Fig. 3. (a) Repulsive potential. (b) Its associated vector field. This potential can be considered as themetrics, the refraction index, or a viscosity index. (c) Attractive potential.(d) Its associated vector field and typical trajectory obtainedwith the attractive potential alone. (e)Union of the two potentials, the second one having the first one as refractive index. (f) Associated vector field and typical trajectory obtained with this metho

In the proposed methods, the repulsive potential is used as the refraction index of the medium where the wave emitted from the goal point propagates, as shown in Fig. 3(a) and (b). Fig. 3(c) and (d) Show the behavior of the attractive potential used alone.When the attractive potential uses the repulsive potential as the refraction index, a unique field is obtained and its associated vector field is attracted to the goal point and repulsed from the obstacles, as shown in Fig. 3(e) and (f). This method inherits the properties of the electromagnetic field, i.e., it is C∞ if the refraction index is C∞.Intuitively, the FM method gives the propagation of a wave front in non-homogeneous media.

This repulsive potential can be obtained using the Extended Voronoi Transform (EVT) of the binary image of the map. The EVT computes the Euclidean distance of the binary image. In a binary image, a pixel is referred to as background if corresponds to complete absence of obstacles and its value is one. The value of a pixel is zero if it corresponds to an obstacle or a wall. For a given distance metric, the EVT of an image produces a distance map of the same size. For each pixel in the image, the EVT assigns a number which is the distance to the nearest zero pixel of the image. For each pixel inside the objects in the binary image, the corresponding pixel in the distance map has a value equal to the minimum distance to the background. This is the solution adopted in the VFM method.

Clearly, the EVT is closely related to the Voronoi diagram. The Voronoi diagram concept is involved in many EVT approaches, either explicitly or implicitly. Another possibility is to build the repulsive potential using FM. This is the solution adopted in the FM2 method. In this case, a wave is propagated starting from the points representing the obstacles and walls. This wave propagation is achieved through the FM method. The result is a potential map,which can be interpreted as a velocity map (or slowness map) because it gives a clear idea of the robot’s permissible velocity at each environmental cell. This

potential map is represented in grey scale, where the walls and obstacles are black and the cells become lighter as long as the distance to these obstacles increases. 2.3. Implementation of a smooth slowness potential This implementation starts with the calculation of the loga- rithmof the inverse of the EVT of the 2D environment updated map (a priori + sensor data) (or the inverse of the EVT in the case of 3D maps). Each white point of the initial image (which represents free cells in the map) is associated to a level of grey that is the logarithm of the inverse of the 2D distance to the nearest obstacles. As a result of this process, a potential is obtained, proportional to the distance to the nearest obstacles, for each cell.

This function introduces a potential similar to a repulsive electric one (in 2D), that can be expressed

as φ = c1 log(1/r) + c2, where r represents the distance to the charge and c1, c2 are constants. If n > 2, the potential is φ = c3rn?2 + c4, where c3, c4 are constants. These expressions of the potential φ correspond to the electric potentials in 2D and higher dimensional cases. 2.4. Fundamentals of the method

Maxwell’s laws govern the propagation of electromagnetic waves.We can use the most typical simplification of the problem in isotropic and possibly non-homogeneous media for a monochromatic wave, considering the so-called almost flat waves. In this case, the optical wave propagates at wavelengths much smaller than the image objects, and therefore the ray optics approximates wave optics. These equations along with the mentioned approach allow us to develop the theories based on rays, such as the geometrical optics, the theory of sound waves, etc. The eikonal equation is derived from these equations. In the Sethian [17] notation.

where D(x) represents the distance to the initial set, R(x) is the refraction index of the medium, and x = (x, y) in 2D or x =(x, y, z) in 3D. In geometrical optics, Fermat’s least time principle for light propagation in a medium with space varying refractive index R(x) is equivalent to the eikonal equation. The eikonal solution D(x) is a scalar function whose isolevel contours are normal to the light rays, and the refractive index of a medium is the quotient of the light velocity in the vacuum and its velocity in the given medium. This equation is also known as the Fundamental Equation of geometrical optics. The most important aspect in this equation, from the path planning point of view, is that the solution is an exponential function of the refractive index

is the angular frequency, which is constant because

the considered wave is monochro matic, T is the period, R(x) = c v(x) is the refraction index, c is the light velocity in vacuum, λ is the wavelength, v(x) is the light velocity in the anisotropic medium, and v = λT .In this expression, ω and c are constants and the refraction index is a function of the position, i.e., the considered medium is anisotropic.

Since this solution is exponential, if the refraction index or first potential R(x) is C∞ then the second potential D(x) is also C∞, and therefore the trajectories calculated by the gradient method over this potential would be of the same class. 3. Robot formations and Fast Marching

Robot formation motion planning deals with the problem of how to find the paths and postures between robots so that the whole formation can adapt to obstacles and other environmental characteristics.

In this work, we have considered two types of formations: (1) leader-following, where two robots (followers) follow the leader as if they were bodyguards, forming a triangle among the three of them; (2) le formation (leader). The leader will not be represented in the leader-protecting figures for the sake of clarity and simplicity.ader-protecting, a formation of six robots in hexagonal configuration protecting the centre of the

As stated before, the FM method is based on a potential function without local minima that provides smooth trajectories. The main problem to deal with is how to apply this method to the robot formation’s motion, keeping its good properties. To solve this problem a repulsive force is needed between the formation robots so that they keep a security distance and do not end up crashing into each other. Furthermore, an internal attractive force is also required for maintaining the formation while adapting to the environment. The advantage of using the VFM method, as proposed here, is that each robot, at each time, has one single potential which is attractive to the objective and repulsive from walls, obstacles, and the other robots of the formation, while keeping the desired nominal inter-robot distances.

Our first approach to implement the repulsive force was to add Gaussian functions to the distance potential Dt i of each robot, centred with the other formation robots, so as to keep inter-robot desired distances balanced with the need to avoid obstacles and reach the goal. This approach is fast and works for a wide range of cases, though the behaviour is not natural in some special situations such as the ones presented in Figs. 8 and 9, for the corridor at the bottom of the images.

Taking this into account, the best solution for a robot to keep its distance from the others is to set them as obstacles in the environment map, expressed in a matrix Woti. The computational cost of this method is higher, since similar matrices Woti, WtiandDti (see next section) have to be computed at

each step. However, this approach preserves the good properties of FM and avoids the appearance of local minima.

The solution adopted for the implementation of the repulsive force is detailed next and summarized in Fig. 4.

Fig. 4. Flowchart of the proposed algorithm.

3.1. Description of the algorithmof robot formationmotion using Fast Marching

The objective of this algorithm is to integrate in a potential without local minima a force that attracts the robots to the goal,a force that repels the robots from the obstacles and a force that maintains the formation.

Fig. 5. (a) Trajectory of the leader obtained with VFM. (b) Robot formation (rectangles) with the corresponding partial objectives (circles) and the partial trajectories of the followers. (c), (d) Metrics matrixWt i for each of the follower robots in a particular step using the method proposed in this paper: the other robots are treated as obstacles in the map, then the metrics matrixWti is calculated over this map, and finally the distance matrix Dt i is calculated usingWt i. (e), (f) The distance matrix Dti measured with themetricsWti for each of the follower robots.

3.1.2. Adding springs

When there are highly symmetric situations, i.e., the robots have to traverse a small door and they are initially placed orthogonally to the wall, the two follower robots have problems in passing together through the door. 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 first follower and then the complete trajectory for the last follower. This provides an effect similar to using springs with different stiffnesses between the robots. This effect can be seen in Figs. 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.

3.1.3. 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 direction. 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 minimum radius of the robot formation. Then, the trajectory of the leader is found using this dilated map. In this way, it is ensured that the formation passes through the passage used by the leader trajectory. Using this trajectory, the rest of the algorithm is similar to the main method:

1. The partial goal points are calculated using the leader path and the desired formation. The distance from a partial goal to the leader path is proportional to the grey level of the partial goal’s position. 2. The distance matrices D are calculated using the metrics matrix W for each robot, using as goal the partial goal of the previous step.

3. The minimum distance path to the partial goal is found using the potential D. 4. All the robots move a fixed number of steps on the corresponding path. 5. The leader advances its path position a fixed number of steps. 3.2. Reduction of the operational cost

Although the FM method is very fast (the computation time is 0.2 sec for Figs. 6 and 7, where the map has a size of 628 × 420 cells), the proposed algorithm for robot formations has to calculate the FM wave propagation for each follower robot at each cycle of the algorithm. For this reason some techniques should be used to make the algorithm faster.

Since the FM method can be considered as the continuous version of Dijkstra’s algorithm, our goal is to turn it into an almost one-dimensional algorithm. 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 steps are:

(1) Enlargement of the trajectory calculated for the leader to get a tube. 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 matrixWoti(see Fig. 10).

(2) VFM—1st step. Using the map obtained in the previous step, a wave is propagated starting from the points representing the obstacles and walls. This is done with the Extended Voronoi Transform (also called Distance Transform in Computer Vision). The result is a potential map, which can be interpreted as a velocity map (or slowness map), as shown in Fig. 10(c).

(3) VFM—2nd step. Based on the previous slowness map, the FM method creates a new potential Dt I that represents the propagation of the electromagnetic wave from the goal to the robot position. An even more important reduction of the computation time is related to the matrix Dt i, as follows. As the vehicles are very close to the partial objectives, 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.2 s to 0.016 s, which implies an algorithm cycle of about 0.5 s without parallelization (using a MacBook Pro platform at 3.06 GHz). The parallelized version of the algorithm has an algorithm cycle of about 0.3 s and permits the use of many followers without increasing the computation time.

Fig. 6. Consecutive steps of the robots’ formation traveling around the maze using the main method.

Fig. 7. Consecutive steps of the robots’ formation traveling around the maze using the method with springs.

Fig. 9. 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.

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’s trajectory. Using this trajectory, the followers’ trajectories are calculated in the same way as in the main proposed method. In this case, the direction in the given points changes abruptly. It is important to study the behaviour of the method at these points, and we can observe that it behaves very well and even smoothes the followers’ trajectories in comparison with the leader’s one, as shown in the figures.

The inter-vehicle desired distance has a maximum value in open areas and is proportional to the refraction index in the rest. In this way, in small corridors the followers can be near each other. Fig. 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 the vehicles to the circles are the partial paths calculated using VFM. Fig. 7 shows a similar case using the proposed method with springs of different stiffnesses. With this improvement the symmetry of the followers’ paths is broken and it is easier to pass trough small passages.

Fig. 8 shows consecutive steps of the robots’ formation traveling around the maze using the main method, with a formation of six robots protecting the centre of the formation. The EVT can be

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.

本文来源：https://www.bwwdw.com/article/4eha.html