Description

309 PAPER Genetic Algorithms for Adaptive Planning of Path and Trajectory of a Mobile Robot in 2D Terrains Kazuo SUGIHARA, Member and John SMITH, Nonmember SUMMARY This paper proposes genetic algorithms

Categories

Published

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Similar Documents

Share

Transcript

309 PAPER Genetic Algorithms for Adaptive Planning of Path and Trajectory of a Mobile Robot in 2D Terrains Kazuo SUGIHARA, Member and John SMITH, Nonmember SUMMARY This paper proposes genetic algorithms (GAs) for path planning and trajectory planning of an autonomous mobile robot. Our GA-based approach has an advantage of adaptivity such that the GAs work even if an environment is time-varying or unknown. Therefore, it is suitable for both off-line and on-line motion planning. We first presents a GA for path planning in a 2D terrain. Simulation results on the performance and adaptivity of the GA on randomly generated terrains are shown. Then, we discuss an extension of the GA for solving both path planning and trajectory planning simultaneously. key words: genetic algorithms, adaptivity, autonomous mobile robots, path planning, trajectory planning 1. Introduction Motion planning [7], [9] is one of important tasks in intelligent control of an autonomous mobile robot. It is often decomposed into path planning and trajectory planning, although they are not independent of each other. Path planning is to generate a collision-free path in an environment with obstacles and optimize it with respect to some criterion. An algorithm for path planning is said to be off-line if the environment is a known static terrain and it generates a path in advance. It is said to be on-line if it is capable of producing a new path in response to environmental changes. Trajectory planning is to schedule the movement of a mobile robot along the planned path. There have been a number of methods proposed for motion planning of a mobile robot [7]. However, few algorithms have been developed for on-line motion planning of a mobile robot in a time-varying or unknown terrain. In this paper, we address adaptive motion planning which can modify the existing path whenever an environmental change occurs (e.g., a mobile robot detects an unknown obstacle). It has an immediate application to sensor-based motion planning of an autonomous underwater vehicle (AUV ) [3]. Recently, applications of genetic algorithms (GAs for short) [1], [4] to path planning or trajectory planning have been recognized [2], [6], [10], [15]. GA is a search strategy using a mechanism analogous to evolution of life in nature. It has widely been recognized that GA works even for complex problems such that traditional Manuscript received July 22, Manuscript revised March 28, The authors are with the Department of Information and Computer Sciences, the University of Hawaii at Manoa, Honolulu, HI 96822, U.S.A. algorithms cannot find a satisfactory solution within a reasonable amount of time [5]. However, the previously proposed GAs have drawbacks and could not fully exploit benefits and ability of GAs. First, a coding which maps solutions to symbolic representations often employs a variable-length string such as a sequence of line segments in path planning [10]. Since the string length of an optimal solution is not known, the configuration (e.g., genetic operators) of a GA must be designed in an ad hoc manner to guarantee generation of strings of any lengths. Second, the GAs solve either path planning or trajectory planning, but not both. This paper proposes genetic algorithms (GAs) for path planning and trajectory planning of an autonomous mobile robot. Our GA-based approach has an advantage of adaptivity such that the GAs work even if an environment is time-varying or unknown. Therefore, it is suitable for both off-line and on-line motion planning. We first present a GA for path planning in a 2D terrain with obstacles of two kinds: A solid obstacle and a hazardous obstacle which allows a path to intersect it at the expense of some cost. A coding used in the GA represents a path with a binary string of fixed-length. The performance of the GA is evaluated by simulation on randomly generated 25 terrains. We also show simulation results on the adaptivity. Then, we discuss an extension of the GA for solving both path planning and trajectory planning of a mobile robot simultaneously. 2. Preliminaries Assume that path planning is considered in a rectangular terrain and a path between two locations is approximated with a sequence of adjacent cells in the grid corresponding to the terrain. Note that the grid structure is conceptual rather than physical and the granularity of cells in the grid is not necessarily uniform. The distance d(i, j) from cell i to its adjacent cell j is the Euclid distance from the center ρ i of cell i to the center ρ j of cell j. The length l(i, j) from i to j is defined as d(i, j) (1+w(ρ i,ρ j,t i,t j )), where w denotes the average weight (i.e., extra cost) of travel from location ρ i at time t i to location ρ j at time t j, assuming 310 that a robot moves at a constant speed. Note that any way of storing map data such as quadtrees can be used as long as we can efficiently retrieve information for a given location (e.g., whether there exists an obstacle at the location). Path Planning Problem Input: (1) n by n grid where the start cell s and the destination cell d are corner cells located diagonally to each other and (2) obstacles (a collection of cells in the grid) of two types solid and hazardous such that a path cannot intersect solid obstacles at all while hazardous obstacles allow a path to intersect them at the expense of a longer path length for each cell in proportion to the obstacles weights representing various cost factors Output: A path (defined as a sequence of adjacent cells) between s and d such that the total length of the weighted path is minimum, subject to the constraint that the path does not intersect any solid obstacle In 2D space, a path is said to be monotone with respect to x-coordinate (x-monotone for short) if no lines parallel to y-axis cross the path at two distinct points, i.e., the projection of the path on x-axis is nondecreasing. Similarly, y-monotone is defined. When there is no confusion, we simply say monotone. A genetic algorithm (GA) [1], [4] for an optimization problem consists of two major components. First, GA maintains a population of individuals, where each individual corresponds to a candidate solution and the population is a collection of such potential solutions. In GA, an individual is commonly represented by a binary string. The mapping between solutions and binary strings is called a coding. The number of individuals in a population is called the population size. Second, GA repeatedly transforms the population by using a mechanism analogous to biological evolution. The mechanism includes the following steps. 1. Fitness Evaluation: The fitness corresponding to an optimization criterion (i.e., objective function) is calculated for each individual. 2. Selection: Some individuals are chosen from the current population as parents, based on their fitness values. 3. Recombination: New individuals (called offspring) are produced from the parents by applying genetic operators such as crossover and mutation. 4. Replacement: Some individuals (not necessarily parents in general) are replaced by some offspring. The population produced at each transformation is called a generation. By giving highly fit individuals more opportunities to reproduce, the population becomes likely to include good individuals throughout generations. 3. Path Planning First, we need to choose a coding which maps a path from start s to destination d into a binary string. Although we can represent an arbitrary path by using a binary string of variable length, it is much more desirable to use fixed-length strings. Thus, we assume that a path from s to d is either x-monotone or y-monotone (but not necessarily both). Obviously, not all paths are monotone. Hence this assumption theoretically implies the possibility of excluding an optimum path in a terrain with extremely crowded obstacles like a maze. As shown in examples below, however, monotone paths are reasonably powerful to express complicated paths. An x-monotone (or y-monotone) path can be represented by a column-wise (or row-wise) sequence of n 1 pairs of direction and distance such that each pair corresponds to each column (or each row, respectively), where n is the number of columns (and equally the number of rows). Thus, the path can be encoded into a binary string of the fixed length proportional to n as shown in Fig. 1. Note that the path in Fig. 1 is x-monotone, but not y-monotone. The first bit α indicates that a path is x-monotone if α = 0; and it is y-monotone if α = 1. A block of 3+ log 2 n bits represents direction and distance on each column or row. The first 2 bits of each block denote the direction, e.g., 00 (vertical), 01 (upper diagonal), 10 (horizontal), and 11 (lower diagonal) in case of α = 0; and 00 (horizontal), 01 (left diagonal), 10 (vertical), and 11 (right diagonal) in case of α = 1. The other bits of the block denote the distance as a signed integer if the direction is 00; otherwise they are Fig. 1 Binary representation of a path. Since the weight may be time-dependent (e.g., the weight strongly depends on the tide and current in a shallow water), a straightforward application of the Dijkstra s shortest path algorithm does not work in this context. SUGIHARA and SMITH: GENETIC ALGORITHMS FOR ADAPTIVE PATH PLANNING 311 ignored. In case of 00 for an x-monotone path, the path goes upward and then goes upper right to the next column diagonally if the distance is positive and otherwise downward and lower right diagonally. In case of 00 for a y-monotone path, the path goes left and then goes lower left diagonally to the next row if the distance is positive and otherwise right and lower right diagonally. For example, the 4th (direction, distance) pair in Fig. 1 corresponds to the segment of a path between the 4th and 5th columns denoting 3 represents that the path goes downward by 2 from the starting location on the 4th column and lower right to the starting location on the 5th column. To interpret binary strings as paths and evaluate their fitness values, we use the following convention which produces more valid paths in generations and hence improves the performance of our GA. If consecutive blocks of a binary string make the corresponding path go beyond boundary cells, that part of the path is regarded as a straight-line short cut along the boundary cells. Note that we leave the binary string as it is, since the uninterpreted substring may become valid and useful later if the substring is inherited to new generations by genetic operators. This coding has two advantages. First, as mentioned above, binary strings are of the same fixed length. If binary strings are of variable length, we need to carefully customize genetic operators such as crossover and mutation. For example, the operators must be able to generate strings of any length from an arbitrarily given initial population, since the length of a string representing an optimal solution is not known a priori. Second, straightforward applications of genetic operators to strings of the fixed length always produce syntactically valid strings. This simplifies a process of recombination and makes the entire GA efficient. Therefore, with the coding, a simple GA [4] works well without any special operator. Now, we analyze space requirements of the GA. Since the GA does not need any special data structure for storing map data of a terrain, it does not require any more space for the terrain information than other algorithms. Thus, we focus on additional space requirements, i.e., overhead of the GA. Let p be the population size and n be the number of cells on each dimension. As mentioned above, each individual is represented by a binary string of length (1 + (n 1)(3 + log 2 n )). Thus, the amount of space needed to store a population is p(1 + (n 1)(3 + log 2 n )) bits. Since p is a constant chosen through experiments on performance evaluation (typically, from dozens to hundreds), the total space requirement is O(n log n). For example, suppose that p = 400 and n = 200. It means that each cell is 5 m square in case of a 1 km square grid. Then, the length of each string is about 200 (3 + 8) bits = 275 bytes. That is, the total amount of space is about 110 Kbytes. We have implemented the GA for path planning by using the GA Toolkit [11] which we developed for design and prototyping of GAs on WWW. The GA Toolkit is available on WWW at sugihara/research/ga-updates.html with a Javaenabled Web browser such as Netscape. For convenience, we changed minimization of a path into maximization by defining the fitness function as (1+w max )n 2 (the length of a weighted path) if the path does not intersect any solid obstacle and otherwise 1, where w max is the maximum weight. The reason for choosing (1+w max )n 2 is that it is the maximum length of a zigzag path in either column-wise or row-wise. The initial population includes two binary strings which represent the straight-line path connecting s and d in the x-monotone and y-monotone representations, respectively. The remaining p 2 individuals in the initial population are random binary strings generated by a random number generator. Even if a random binary string has large perturbation, the convention chopping off a path along the boundary mentioned above often make the random string represent a path consisting of a few straight line segments. Two genetic operators are used. The first one is a 1-point crossover [1] which gets two individuals, cuts their strings at a randomly chosen position, swaps their second substrings, and produces two new strings of the original length. It has a parameter called crossover rate that is the ratio of individuals involved in the crossover over the entire population. The second genetic operator is a mutation [1] which gets an individual, flips bits of its string at random, and produces a new string. It has a parameter called mutation rate that is the probability of bit alternation per bit on a string. In this implementation, all parents are replaced by their offspring. Next, we show example runs of the GA, where n = 16, the population size is 30, the crossover rate is 0.8, and the mutation rate is Note that s is depicted by a circle at the upper left corner, d is depicted by X at the lower right corner, N denotes the generation number and Fit denotes a fitness function value. Figure 2 shows how a path was evolved during an example run for a fairly complicated terrain, where black cells denote solid obstacles and three kinds of shaded cells denote hazardous obstacles with weights (i.e., extra length) 1, 2 and 3 in increasing order of their darkness. Note that there are at least 6 local optima within 0.4% fitness difference. The GA examined some of the local optima, which are completely different from each other, and eventually found an optimum path. Figure 3 shows another terrain which is harder to find a path at the beginning than the above example. The first valid path was found in the 53rd generation. One of the most important advantages of our GA We have observed that our GA generated the 6 local optima in the simulation whose results will be presented in Sect. 4. 312 N =1,Fit = N = 85, Fit = N =1,Fit= N =2,Fit = environmental change N = 520, Fit = N = 645, Fit = Fig. 2 An example run of the path planning GA. N =7,Fit = N = 239, Fit= Fig. 4 Adapting for an environmental change. N = 53, Fit = N = 251, Fit= Fig. 3 An example run for a zigzag terrain. approach is adaptivity. A path may need to be changed when a mobile robot detects an unknown obstacle or inaccuracy of the map information used for generation of the path. GA is a dynamic system in the sense that it starts changing a population once an environment changes and tries to adapt for the change. In other words, GA works even if input data is changed on fly. Therefore, it is suitable for not only off-line path planning but also on-line path planning. We present an example to show how adaptive the GA is. Suppose that the current path is a straight line as shown in the top left of Fig. 4. Then, a mobile robot has encountered an unknown solid obstacle of size 2 by 2 surrounded by a hazardous region (see the top right of Fig. 4). The new solid obstacle is first regarded as a new hazardous obstacle with the largest weight (3 in this example). Once the current path is evolved into a path which does not intersect the new solid obstacle, the dummy hazardous obstacle is changed to the solid obstacle. This is because if the current path intersects the new solid obstacle, then it suddenly becomes an invalid path and a population will quickly loose its good features due to selection based on fitness values. The top right of Fig. 4 shows a path that the GA produced just after the environmental change. The bottom left and right of Fig. 4 show an intermediate and final results of our GA for the environmental change, respectively. Note that the path shown at the top right is a local minimum and some techniques such as potential fields and hill-climbing may be trapped there. 4. Simulation Results We have conducted simulation study of the proposed GA by using the GA toolkit [11]. The GA was first tuned by preliminary simulation on the terrain in Fig. 2 and two more terrains of similar sizes. The simulation examined all combinations of 3 selection operators, 3 genetic operators, 1 mutation operator, and various parameter values for each operator with respect to several performance measures [12] such as the average fitness value and likelihood of optimality L opt (k) which is defined as follows. We observe n runs of a GA executed for k generations each. Let m be the number of runs which produced an optimal solution within k generations. Lopt(k) is equal to m/n. If the GA is completely random, the runs are Bernoulli trials and Lopt(k) is regarded as the estimated probability of finding an optimal solution within k generations. SUGIHARA and SMITH: GENETIC ALGORITHMS FOR ADAPTIVE PATH PLANNING 313 Fig. 5 Normalized L opt for various population sizes. Fig. 6 L opt(1000) [%] for combinations of µ and ω. Preliminary simulation with 100 runs for each combination suggested the following tuning [12]. 1. Operators: A sequence of roulette tournament selection, 1-point crossover and multi-point mutation is best. 2. Population size p = 30: It is the number of individuals in a population. This choice is for the grid size Mutation rate µ = : It is the probability of bit flipping per bit. 4. Crossover rate γ =0.8: It is the proportion to the entire population whose individuals are involved in crossover. 5. Win rate ω = : It is the probability that a better individual wins at each binary tournament in the roulette tournament selection. With the preliminary simulation, we identified µ and ω as the primary factors whose values drastically affect the performance and narrowed down the range of each parameter s value for fine tuning. Regarding the population size p, Fig. 5 summaries simulation results on the likelihood of optimality L opt (k) normalized under a constraint of constant computational cost kp = (e.g., k = 1500 generations for p = 20 and k = 300 for p = 100). They show that L opt with the constant computational cost is not improved much when p exceeds 2n and L opt drastically decreases when p is reduced to n or further down. This suggests a conjecture that the best choice of p with respect to the normalized L opt is about 2n. It may be justified as follows. For each gene corresponding to a column or row in an n n grid, there are n possible pairs of direction and distance. Hence, an initial population which randomly chooses nx-monotone paths and ny-monotone paths likely covers most of possible values for every gene and makes crossover effective. On the other hand, once a population becomes large enough, increasing the population size further does not make much difference. Table 1 L opt(1000) [%] for combinations of µ and ω. µ \ ω For the f

Search

Similar documents

Related Search

International Society for the Philosophy of ARole of a formative OSCE in improving ClinicaCannonisation and justice for Mary Queen of SApplied GIS for Urban Planning and DemographiMETHOD AND THEORY FOR THE STUDY OF RELIGIONAdaptive function of literature and the otherDesign and Technological Planning of ArchitecEuropean Group for the Study of Deviance and Research and Planning of Systems MethodologyDevelopment of algorithms for medical image s

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x