Sage Journals: Discover world-class research

Abstract

A hierarchical memetic algorithm (MA) is proposed for the path planning and formation control of swarm robots. The proposed algorithm consists of a global path planner (GPP) and a local motion planner (LMP). The GPP plans a trajectory within the Voronoi diagram (VD) of the free space. An MA with a non-random initial population plans a series of configurations along the path given by the former stage. The MA locally adjusts the robot positions to search for better fitness along the gradient direction of the distance between the swarm robots and the intermediate goals (IGs). Once the optimal configuration is obtained, the best chromosomes are reserved as the initial population for the next generation. Since the proposed MA has a non-random initial population and local searching, it is more efficient and the planned path is faster compared to a traditional genetic algorithm (GA). The simulation results show that the proposed algorithm works well in terms of path smoothness and computation efficiency.

Keywords

Genetic algorithm memetic algorithm hierarchical local motion planner Voronoi diagram formation control swarm robots

1. Introduction

In recent years an increasing number of multi-robot systems have been proposed. Swarm robotics (Yogeswaran and Ponnambalam, 2010; Samitha and Pubudu, 2009; Winfield et al., 2008) is an approach for coordinating multi-robot systems. The swarm shares information about the environment and individual members interact with each other. Cooperative behaviour may be used to complete a task.

Most studies on robot swarm cooperation have focused on formation control, which refers to the task of controlling a group of mobile robots to follow a predefined path or trajectory while maintaining the desired formation pattern, as shown in Fig. 1. Numerous methods have been proposed for formation control, which can be roughly categorized into four basic approaches: behavioural, virtual structure, leader-follower and potential field.

In virtual structure approaches, the robot swarm is considered as a single rigid robot and a rigid geometric relationship among group members is maintained (Beard et al., 2001; Belta and Kumar, 2004; Eren et al., 2002; Lewis and Tan, 1997; Ren and Beard, 2004; Zhang et al., 2009). Therefore, the path planning of a robot swarm can be simplified as the path planning of a rigid robot (Lewis and Tan, 1997). The advantage of the virtual structure approach is ease of implementation, however, the approach has low path planning flexibility. Virtual structure approaches were proposed for coordinating multiple spacecraft (Beard et al., 2001; Ren and Beard, 2004). In Belta and Kumar (2004), the algorithm derives scale-parameterized interpolated trajectories for a team of fully actuated mobile robots. The scale parameter controls the distances between robots and minimizes the overall energy consumption due to motion.

Figure 1.

A group of mobile robots follow a predefined path or trajectory while maintaining the desired formation pattern

For behaviour-based approaches (Balch and Arkin, 1998; Baldassarre et al., 2007; Gazi, 2005; Lawton et al., 2003; Monteiro and Bicho, 2002; Parker, 1998; Veloso et al., 1999; Chen and Luh, 1994; Schneider-Fontan and Mataric, 1998; Sugihara and Suzuki, 1996), several desired behaviours, i.e., movement towards the goal, obstacle avoidance, collision avoidance and keeping formation, are defined for each robot to create its trajectory. The planning of robots can be done concurrently. Since each robot is considered individually, it is difficult to guarantee precise formation control. In Lawton et al. (2003), formation control comprised a sequence of manoeuvres between formation patterns. The algorithm consists of three strategies: (i) using relative position information configured in a bi-directional ring topology to maintain the formation, (ii) injecting inter-robot damping via passivity techniques and (iii) accounting for actuator saturation.

In leader-follower approaches (Burgard et al., 2005; Egerstedt and Xiaoming, 2001; Mariottini et al., 2007; Shao and Xie, 2007; Kloder and Hutchinson, 2006; Moreau, 2005; Olfati-Saber, 2006; Tanner et al., 2004; Vig and Adams, 2006; Ren and Beard, 2005; Chen and Wang, 2005), the ability of a robot depends on its job. In the swarm, one or a few robots act as leaders which move along predetermined trajectories and other robots in the group follow while maintaining the desired relative position with respect to the leader. Generally, leader-follower-based robot systems are implemented as centralized systems. However, most leader-follower approaches are not complete algorithms because the safe path, that which gives a robot sufficient distance from obstacles and other robots, is difficult to derive. In Mariottini et al. (2007), the centralized leader-follower formation control algorithm uses panoramic vision to maintain the swarm formation.

In potential-based approaches (Gazi and Passino, 2003; Khatib, 1985; Liu et al., 2000; Yun and Tan, 1997; Zhu et al., 2009), the formation of the robot swarm is modelled by a potential field. In Barnes et al. (2009), artificial potential fields were generated from normal and sigmoid functions. Due to the potential fields, the motion of swarm members and the individual member spacing are limited. In Ge and Fua (2005), queues and formation vertices represented the desired formation pattern. Artificial potential trenches represented the desired pattern and trajectory for the group of robots. In Balch and Hybinette (2000), a set of artificial points was used as beacons that guide the robots to their goal. The approach uses the geometric relationship between beacon points to move the robots in formation. Other examples of potential field approaches can be found in Balch and Hybinette (2000), Elkaim and Kelbley (2006), and Gazi (2005). Pereira et al. (2008) proposed a navigation function with a Lyapunov stable function. Lyapunov functions are used to prove closed-loop stability and to solve the local minima problem of potential fields.

In general there are some different optimal constraints in the path planning problem, e.g., time-optimal, the shortest path and path safety. In this paper, the optimization of path safety is considered.

In order to obtain a safe path for swarm robots, the present paper proposes a hierarchical path planning algorithm. The proposed algorithm consists of a global path planner (GPP) and a local motion planner (LMP). The global path planning algorithm searches for a path, which the centre of the robot swarm should move along, within a Voronoi diagram of the free space. The motion planner is a genetic algorithm based on an artificial potential field. The potential functions are used to keep robots away from obstacles and to keep the robot swarm within a certain distance from each other. With the potential models, the local motion paths derived by the memetic algorithm are safe in terms of being collision-free and away from obstacles. Therefore, the safety of the obtained path consists of a safe global path and safe local motion. The global path derived from a Voronoi diagram is an optimal path in terms of safety because the path is maximally clear of obstacles. As for the local motion, the proposed MA generates an optimal local motion which takes account of the distance to IG, the distance to obstacle and the connectivity of robots.

While some Lyapunov-based formation control algorithms (Pereira et al., 2008) usually use stability to guide robots to their desired configurations, the stability of a GA-based algorithm is defined as the best fitness value of the chromosome when the change of the best fitness value of the chromosome is negligible. In this paper, the optimal configuration of robot swarm is obtained when the evolution reaches a stability state.

The rest of this paper is organized as follows. The GPP and the LMP of the proposed hierarchical path planning algorithm for swarm robots are introduced in Section 2 and 3, respectively. In Section 4, simulation results are given. Finally, conclusions and suggestions for future work are given in Section 5.

2. Global Path Planning

Due to the coupling of global planning and local planning, many existing algorithms require complex search algorithms and can become trapped at local minima. The proposed algorithm consists of a GPP and an LMP. The former determines the primary movement direction of the swarm robots and the latter derives a frame of robot configurations. Details of the two planning algorithms are introduced in the next section.

Figure 2.

Simple path of moving straight from start to goal

Figure 3.

Voronoi graph for Fig. 2

Global path planning can be considered as a planning problem for a point robot. In Fig. 2, a swarm of two robots moves to the goal configuration; the planned path is close to obstacles (Erinc and Carpin, 2007; Ghanbari and Noorani, 2011). In order to obtain a safe path, a Voronoi diagram (VD) is adopted since it is easy to implement and has been shown to work well in many cases. There are many variants of VDs (Choset et al., 1989; Erinc and Carpin, 2007; Kloetzer and Belta, 2007; Wein et al., 2005). In the present study a VD consisting of line segments (Choset et al., 1989) is considered. The VD shows a set of free points which are equidistant to the two closest obstacles. In Wein et al. (2005), the VD was constructed using Voronoi vertices and Voronoi arcs. The Voronoi vertices in this case are points equidistant to the closest features of three (or more) polygons. The vertices are connected by continuous chains of Voronoi arcs. An arc may be equidistant to the two closest vertices or to the two closest obstacle edges or to an obstacle vertex and an obstacle edge.

As shown in Fig. 3, all edges and vertices of obstacles are used to construct the VD. The computation complexity is proportional to the total number of features of obstacles. Only a partial VD is used for global path planning for swarm robots. An efficient approach for constructing the partial VD is proposed in this paper.

Unlike approaches which construct the whole Voronoi diagram of the free space and then search for the path, the proposed scheme constructs a partial VD of the region of interest. As shown in Fig. 4(a), the proposed approach explores Voronoi vertices constructed from obstacles which are near the straight line from start to goal. Then, the Voronoi vertices are connected by a Voronoi arc which is formed by the nearest edges along the line, as shown in Fig. 4(b). The approach significantly reduces the computation complexity. Since a VD is the medial axis of the free space, the global path derived using a VD for swarm robots is the safest path.

Figure 4.

Voronoi vertices constructed using obstacles which are near the straight line from start to goal. The vertices are connected by a Voronoi arc which is formed by the nearest edges along the line.

3. Local Motion Planning

The global path obtained in the previous stage can be sampled as a series of positions, denoted as (q₁, q₂, q₃,…,q_n), which the centre of the swarm robots should follow. These positions can be considered as the intermediate goals (IGs). For each position q_i, the memetic algorithm (MA)-based local motion planner plans a set of configurations for the robots to which the centre of swarm is fixed at point, q_i.

Figure 5.

Flow chart of proposed memetic algorithm

Basically, the operators, mutation and crossover of GA can avoid becoming trapped in local minima. The MA, a modified GA, uses a local search scheme for searching optimal solutions. Thus, the proposed MA-based planner is faster than the traditional GA-based planner without the local minima issue. The flow chart of the proposed memetic algorithm is shown in Fig. 5. The algorithm is:

Potential-based Memetic Algorithm Begin i= 1; /* Initialize the first intermediate goal */ t = 0; /* Initialize the evolutionary generations */ Randomly generate an initial population P_i (t); fitness(P_i(t)); repeat until (reach the final goal q_n) Do P_i+1(t)= P_i(t); repeat until (reach the intermediate goal q_i) Do select P_i(t+l) from P_i(t); crossover(P_i(t+l)); mutate (P_i(t+l)); fitness(P_i(t+l)); apply FT Local Search to P_i(t+l) t = t +1; end i= i +1; end End

To apply an MA search for the optimal configurations for robots, the coordinates of the robot swarm are encoded into one chromosome. The configuration of k robots is defined as their displacements, denoted as ((x₁, y₁), (x₂, y₂), …, (x_k, y_k)). The proposed algorithm can be extended to 3-D workspaces without significant modification. For example, the gene of a robot can be represented as (x, y, z).

Initialization

The population, P₁(0), of the first intermediate goal is generated randomly. The initial populations, (P_i(0),i >1), of other intermediate goals are partially obtained from the last generation of the preceding intermediate goal and are partially randomly generated. Since these initial populations are eugenic and inherit from ancestors, the evolution time is reduced.

Natural Selection

Natural selection is a genetic operator that chooses a chromosome from the current generation's population for inclusion in the next generation's population. Before making it into the next generation's population, selected chromosomes may undergo crossover and/or mutation (depending upon the probability of crossover and mutation) in which case the offspring chromosome(s) are actually the ones that make it into the next generation's population.

The aim of selection is to preserve optimal chromosomes and abandon suboptimal ones. Generally, selection is performed according to the fitness of every chromosome, where the fitness evaluation of the GA is an objective function for chromosomes. There are several types of selection, including roulette, tournament, best, random, and top percent. In the present study, the top percent scheme is adopted. The top 10 percent of the population is reserved as the next generation's population and the others are selected randomly.

Crossover and Mutation Operators

Selection alone cannot generate any new chromosomes for the population. The reproduction operators, crossover and mutation, are used to generate new offspring for the next generation. Crossover is performed between two selected chromosomes, called parents, by exchanging parts of their genomes to form two new chromosomes, called offspring. The most popular types of crossover operations are one-point, two-point, uniform, and blending. In this paper, since the i-th gene of a chromosome represents the position of robot i, the crossover operator exchanges similarly positioned genes of a pair of chromosomes.

For the mutation operator, an arbitrary bit in a genetic sequence is changed with a probability. The purpose of mutation in an evolutionary algorithm (EA) is as a genetic operator used to maintain genetic diversity from one generation of a population of chromosomes to the next, while attempting to avoid local minima.

Fitness Function

In general selection is conducted according to the fitness of every chromosome, where the fitness evaluation of the GA is an objective function for chromosomes. The simple definition of a fitness function is the distance between the robots and the goal. Therefore, the fitness function of a configuration can be defined as:

V_{q} = \sum_{i = 1}^{k} D_{q}^{i}

(1)

where $D^{i}_{q}$ is the distance between robot i and the intermediate goal of the swarm centre, q. The distance can be simplified as:

\begin{array}{l} D_{q}^{i} = \sqrt{{(T_{x} - B_{x})}^{2} + {(T_{y} - B_{y})}^{2}} \\ \approx | T_{x} - B_{x} | + | T_{y} + B_{y} | \end{array}

(2)

where (T_x, T_y) are the coordinates of the intermediate goal and (B_x, B_y) are the coordinates of robot i. In this paper, an optimal chromosome, a frame of configurations of swarm robots, should be collision-free and should reach the goal. In other words, a good chromosome should be close to the goal and not collide with obstacles. Motions that lead to collisions with obstacles or other robots should be removed. Thus, the fitness function is defined as:

V_{q} = {\begin{cases} \sum_{i = 1}^{k} D_{q}^{i} + ρ U_{r e p} (q) if  no  collision \\ V_{\max,} if collision \end{cases}

(3)

where ρ is a constant and U_rep(q) is the repulsive potential of swarm robots from obstacles. When a configuration collides with obstacles, the collision function, f_collide(q), is equal to V_max, which is a penalty; otherwise, it is equal to 1. The potential U_rep(q) can be calculated analytically (Moreau, 2005; Schneider-Fontan and Mataric, 1998) as:

U_{r e p} (q) = \sum_{i = 1}^{k} U_{r e p}^{i} (q)

(4)

where Uⁱ_rep(q) is the repulsive potential of robot i from the nearest obstacle.

U_{r e p}^{i} (p) = {\begin{array}{r} \frac{1}{2} η {(\frac{1}{D i s t (p)} - \frac{1}{Q^{*}})}^{2}, & D i s t (p) \leq Q^{*} \\ 0, & D i s t (p) > Q^{*} \end{array}

(5)

where Q* is the minimum distance from obstacles and η is a gain of the repulsive gradient. Disp (i) is the distance between robot i and the closest obstacle.

For swarm cohesion, a robot in the swarm should keep a certain distance from the swarm centre and not stray far from other robots, as shown in Fig. 6. Thus, a spring function is adopted as a repulsive/attractive potential function in the fitness function. The fitness function can be rewritten as:

V_{q} = {\begin{cases} \sum_{i = 1}^{k} D_{q}^{i} + ρ U_{r e p} (q) + \frac{1}{2} k \sum_{i = 1}^{n} X_{i}^{2}, if no collision \\ V_{\max,} if collision \end{cases}

(6)

where

X_{i}^{2} = {(l - l_{i})}^{2}

(7)

where l_i is the distance between robot i and the nearest neighbour robot, and l is the safe distance which should be kept between robots. The desired formation of the swarm robots can be maintained using the spring function. Two weighting factors, ρ and k, are added to the repulsion and the spring function, respectively. The selection stage of the GA is performed according to the fitness function in (7).

Local Search of a Memetic Algorithm using a Gradient between Swarm Robots and IGs

Conventional genetic algorithms (CGAs) do not have a fine-tuning (FT) process to get closer to optimal solutions. Unlike CGAs, an MA is an EA with a local search process to refine individuals. In this paper, the local research scheme is used to adjust the position of the centre of the robot swarm moving toward the IG. The top 20 percent of chromosomes are reserved for the next generation. The chromosomes are fine-tuned before the next evolution. Consider the position of the swarm centre of a chromosome as $R^{c} = (R_{x}^{c}, R_{y}^{c})$ and the current intermediate goal as $I G_{i} = (I G_{i x}, I G_{i y})$ . The best movement direction is defined as:

\vec{p} = I G_{i} - R^{c} = (I G_{i x} - R_{x}^{c}, I G_{i y} - R_{y}^{c})

(8)

Therefore, the fine-tuning procedure of the genes of the chromosomes is defined as:

g e n e_{1} {\begin{array}{l} g e n e_{1} + P_{i}, i f g e n e + P_{i} \leq g e n e_{\max} \\ g e n e_{\max}, i f g e n e_{1} + P_{i} > g e n e_{\max} \end{array}

(9)

Figure 6.

The follower keeping a safe distance from the leader or other followers in a 3-robot swarm (Lin et al., 2010)

4. Simulation Results

The proposed algorithm consists of the GPP and the LMP. The former was implemented using a modified Voronoi algorithm. The latter was implemented using the JGAP 3.3.4_full API, an open source Java-based GA and genetic programming package. The simulations were run on a PC with a Core2 Duo 2.83-GHz CPU running the Windows XP operating system. The population was 100 and the maximum number of generations was set to 120. The probabilities of mutation and crossover were both 10%. The safe distances, l and Q*, were set to 10 pixels and 2 pixels, respectively. The range of the genes was 30 to −30.

Figure 7.

Three trajectories for 3-robot swarm example. Motion planning obtained using (a) MA and (b) CGA.

Figure 8.

Eight trajectories for 8-robot swarm example. Motion planning obtained using (a) MA and (b) CGA

Swarm Robot Path Planning by Genetic Algorithm and Memetic Algorithm

Case 1

The first example is the 3-robot swarm shown in Fig. 7(a). There are 5 IGs and 3 obstacles in this case. The simulation took 8.609 seconds to plan a 10-configuration collision-free path. A similar simulation of the CGA is shown in Fig. 7(b). The CGA took 10.11 seconds to plan a 12-configuration path. The proposed algorithm is faster and more efficient.

Case 2

An 8-robot swarm example is shown in Fig. 8(a). There are 4 IGs and 2 obstacles in this case. The obtained path is straighter than that obtained using the CGA shown in Fig. 8(b). The simulation took 178.594 seconds to plan an 85-configuration collision-free path. A similar simulation of the CGA is shown in Fig. 8(b). The simulation took 877.938 seconds to plan a 272-configuration path.

Comparison between CGA and MA motion planning

According to the simulation results of the above four cases, the proposed algorithm is more efficient than CGA. Fig. 9 shows the distances from the centre of the swarm to IG1, IG2, IG3, IG4 and IG5 for the two algorithms, respectively. The proposed algorithm requires fewer generations than the CGA. In Fig. 9(a), peaks are caused by the random initialization of genes when the swarm reaches an IG and moves to the next IG.

Figure 9.

(a)-(e) Distance between the centre of the swarm and IGs versus number of generations

The results of a simulation similar to an example given in Kloetzer and Belta (2007) are shown in Fig. 10. In this case, there is a 30-robot swam system in a two-obstacle environment. The simulation shows that the proposed algorithm works well for large swarms.

5. Conclusion

A potential-based memetic algorithm was proposed for the motion planning of swarm robots. The proposed algorithm consists of a global path planner (GPP) and a local motion planner (LMP). The GPP searches for a path, which the swarm robots should follow, from the start to the goal within a Voronoi diagram of the workspace. The LMP is an MA-based planner based on a fine-tuning (FT) structure. The repulsion keeps robots away from obstacles and a spring function maintains the robot swarm within a certain distance from each other. The proposed MA has a non-random initial population and fine-tuning based local searching, which make it more efficient and faster than the traditional CGA.

Since the proposed approach is a hierarchical algorithm which plans the global path and local motion individually, the robot swarm moves toward the goal by sequentially traversing a sequence of IGs and intermediate IGs. Therefore, the robot swarm can avoid becoming trapped in local minima. Simulation results demonstrate that the proposed algorithm can plan collision-free paths for swarm robots.

In future works we will focus on smoothing the planned paths to reduce redundant movements, especially for 8-robot swarms. Some constraints may be considered in the planning stage, e.g., a minimum curvature constraint. With this modification, the proposed algorithm should be more efficient.

Figure 10.

Path planning results for an example similar to that shown in Kloetzer and Belta (2007)

Footnotes

6. Acknowledgments

This work was supported by the National Science Council of Taiwan under grants NSC 99-2220-E-224-007 and NSC 100-2218-E-224-009-MY3.

References

Balch

Arkin

R.C.

(1998) Behavior-based formation control for multirobot teams. IEEE Transactions on Robotics and Automation: 14, 926–939.

Balch

Hybinette

(2000) Social potentials for scalable multi-robot formations. Proceedings of IEEE International Conference on Robotics and Automation: 1, 73–80

Baldassarre

Trianni

Bonani

Mondada

Dorigo

Nolfi

(2007) Self-organized coordinated motion in groups of physically connected robots. Proceedings of IEEE Transactions on Systems, Man, and Cybernetics: 37, 224–239.

Barnes

L.E.

Fields

M.A.

Valavanis

K.P.

(2009) Swarm formation control utilizing elliptical surfaces and limiting functions. Proceedings of IEEE Transactions on Systems, Man, and Cybernetics: 39, 1434–1445.

Beard

R.W.

Lawton

Hadaegh

F.Y.

(2001) A coordination architecture for spacecraft formation control. Proceedings of IEEE Transactions on Control Systems Technology: 9, 777–790.

Belta

Kumar

(2004) Optimal motion generation for groups of robots: A geometric approach. ASME Journal of Mechanical Design: 126, 63–70.

Burgard

Moors

Stachniss

Schneider

F.E.

(2005) Coordinated multi-robot exploration. Proceedings of IEEE Transactions on Robotics: 21, 376–386.

Chen

Luh

J.Y.S.

(1994) Coordination and control of a group of small mobile robots. Proceedings of IEEE International Conference on Robotics and Automation: 3, 2315–2320.

Chen

Y.Q.

Wang

(2005) Formation control: A review and a new consideration. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems: 3181–3186.

10.

Choset

Lynch

K.M.

Hutchinson

Kantor

Burgard

Kavraki

L.E.

Thrun

(1989) Principles of robot motion: Theory, algorithms, and implementations. MIT Press, Boston.

11.

Egerstedt

Xiaoming

Hu.

(2001) Formation constrained multi-agent control. Proceedings of IEEE Transactions on Robotics and Automation: 17, 947–951.

12.

Elkaim

G.H.

Kelbley

R.J.

(2006) A lightweight formation control methodology for a swarm of non-holonomic vehicles. Proceedings of IEEE Aerospace Conference: 8–13.

13.

Eren

Belhumeur

P.N.

Morse

A.S.

(2002) Closing ranks in vehicle formations based on rigidity. Proceedings of IEEE Conference on Decision and Control: 3, 2959–2964.

14.

Erinc

Carpin

(2007) A genetic algorithm for nonholonomic motion planning. Proceedings of IEEE International Conference on Robotics and Automation: 1843–1849.

15.

Gazi

(2005) Swarm aggregations using artificial potentials and sliding-mode control. Proceedings of IEEE Transactions on Robotics: 21, 1208–1214.

16.

Gazi

Passino

K.M.

(2003) Stability analysis of swarms. Proceedings of IEEE Transactions on Automatic Control: 48, 692–697.

17.

S.S.

Fua

C.H.

(2005) Queues and artificial potential trenches for multirobot formations. Proceedings of IEEE Transactions on Robotics: 21, 646–656.

18.

Ghanbari

Noorani

SMRS

. (2011) Optimal trajectory planning for design of a crawling gait in a robot using genetic algorithm. International Journal of Advanced Robotic Systems: 8(1), 29–36

19.

Khatib

(1985) Real-time obstacle avoidance for manipulators and mobile robots. Proceedings of IEEE International Conference on Robotics and Automation: 2, 500–505.

20.

Kloder

Hutchinson

(2006) Path planning for permutation-invariant multi-robot formations. Proceedings of IEEE Transactions on Robotics: 650–665.

21.

Kloetzer

Belta

(2007) Temporal logic planning and control of robotic swarms by hierarchical abstractions. Proceedings of IEEE Transactions on Robotics: 23, 320–330.

22.

Lawton

J.R.T.

Beard

R.W.

Young

B.J.

(2003) A decentralized approach to formation maneuvers. Proceedings of IEEE Transactions on Robotics and Automation: 19, 933–941.

23.

Lewis

M.A.

Tan

K.-H.

(1997) High precision formation control of mobile robots using virtual structures. Proceedings of Journal on Autonomous Robots: 4, 387–403.

24.

Lin

C.C.

Hsiao

P.Y.

Chen

K.C.

(2010) A motion planning of swarm robots using genetic algorithm. Proceedings of IEEE International Conference on Broadband, Wireless Computing, Communication and Applications: 538–543.

25.

Liu

Ang

M.H.

Krishnan

Lim

S.Y.

(2000) Virtual obstacle concept for local-minimum-recovery in potential-field based navigation. Proceedings of IEEE International Conference on Robotics and Automation: 2, 983–988.

26.

Mariottini

G.L.

Morbidi

Prattichizzo

Pappas

G.J.

Daniilidis

(2007) Leader-follower formations: Uncalibrated vision-based localization and control. Proceedings of IEEE International Conference on Robotics and Automation: 2403–2408.

27.

Monteiro

Bicho

(2002) A dynamical systems approach to behavior-based formation control. Proceedings of IEEE International Conference on Robotics and Automation: 3, 2606–2611.

28.

Moreau

(2005) Stability of multiagent systems with time-dependent communication links. Proceedings of IEEE Transactions on Automatic Control: 50, 169–182.

29.

Olfati-Saber

(2006) Flocking for multi-agent dynamic systems: Algorithms and theory. Proceedings of IEEE Transactions on Automatic Control: 51, 401–420.

30.

Parker

L.E.

(1998) ALLIANCE: An architecture for fault tolerant multirobot cooperation. Proceedings of IEEE Transactions on Robotics and Automation: 14, 220–240.

31.

Pereira

G. A. S.

Kumar

Campos

M. F. M.

(2008) Closed loop motion planning of cooperating mobile robots using graph connectivity. Proceedings of Robotics and Autonomous Systems: 56, 373–384.

32.

Ren

Beard

R.W.

(2004) A decentralized scheme for spacecraft formation flying via the virtual structure approach. Journal of Guidance, Control, and Dynamics: 27(1), 73–82.

33.

Ren

Beard

R.W.

(2005) Consensus seeking in multiagent systems under dynamically changing interaction topologies. Proceedings of IEEE Transactions on Automatic Control: 50, 655–661.

34.

Samitha

W. E.

Pubudu

N. P.

(2009) Formations of robotic swarm: An artificial force based approach. International Journal of Advanced Robotic Systems: 6(1), 7–24.

35.

Schneider-Fontan

Mataric

M.J.

(1998) Territorial multi-robot task division. Proceedings of IEEE Transactions on Robotics and Automation: 14, 815–822.

36.

Shao

Xie

(2007) Leader-following formation control of multiple mobile vehicles. Institution of Engineering and Technology on Control Theory and Applications: 1, 545–552.

37.

Sugihara

Suzuki

(1996) Distributed algorithms for formation of geometric patterns with many mobile robots. Journal of Robotic Systems: 13, 127–139.

38.

Tanner

H.G.

Pappas

G.J.

Kumar

(2004) Leader-to-formation stability. Proceedings of IEEE Transactions on Robotics and Automation: 20, 443–455.

39.

Veloso

M.M.

Stone

Han

(1999) The CMUnited-97 robotic soccer team: Perception and multi-agent control. Proceedings of Robotics and Autonomous Systems: 29, 133–143.

40.

Vig

Adams

J.A.

(2006) Multi-robot coalition formation. Proceedings of IEEE Transactions on Robotics: 22, 637–649.

41.

Wein

Berg

Halperin

(2005) The visibility–voronoi complex and its applications. Proceedings of the 21th annual symposium on Computational geometry: 63–72.

42.

Winfield

Fernandez-Gago

Dixon

Fisher

(2005) On formal specification of emergent behaviours in swarm robotic systems. International Journal of Advanced Robotic Systems: 2(4), 363–370.

43.

Yogeswaran

Ponnambalam

S. G.

(2010) Swarm Robotics: An Extensive Research Review. Advanced Knowledge Application in Practice. Fuerstner

Igor

(Ed.), InTech.

44.

Yun

Tan

K.C.

(1997) A wall-following method for escaping local minima in potential field based motion planning. Proceedings of 8th International Conference on Advanced Robotics: 421–426.

45.

Zhang

Bastani

F.B.

Yen

I.L.

(2009) Decentralized path planner for multi-robot systems. Proceedings of IEEE International Conference on Tools with Artificial Intelligence: 171–175.

46.

Zhu

Zhang

Song

(2009) An improved wall following method for escaping from local minimum in artificial potential field based path planning. Proceedings of the 48th IEEE Conference on Decision and Control: 6017–6022.

Motion Planning Using a Memetic Evolution Algorithm for Swarm Robots

Abstract

Keywords

1. Introduction

2. Global Path Planning

3. Local Motion Planning

4. Simulation Results

5. Conclusion

Footnotes

6. Acknowledgments

References