Abstract: Because of the necessity of product transportation using an autonomous robot in industries, the path-planning in finding an appropriate way without collision is essential. The main purpose of this study is to solve the problem of robotic path-planning utilizing a Genetic Algorithm (GA), a robust scheme used in searching for the global optimum by imitating a genetic evolutionary process. In this study, a two dimensional mobile robot used in four kinds of multi-layer barrier systems (a one-layer barrier, a two-layer, a three-layer and a four-layer barrier system) has been introduced. To access a shortest path when an autonomous robot passing through multi-layer barrier systems, an objective function of the path length is minimized using a GA optimizer in conjunction with a minimum square root method as well as a penalty function. The genetic algorithm provides a solid alternative to conventional methods of path-planning. Moreover, the optimization parameters for the desired path can easily be changed without a total overhaul of the overall algorithm. Results reveal that the path optimization within a limited working area can be simplified by presetting the fixed steps in an x-axis. Five kinds of GA parameters (pop, bit, iter, pc and pm) play essential roles in the solution’s accuracy during GA optimization. Obstacle with more layer-barriers will increase the difficulty of short-path searching. An appropriate path can be obtained by increasing the iter from 500 to 5000 or 10000 during GA optimization process. Consequently, an efficient path that avoids multiple obstacles within a working area can be easily found using the GA algorithm.
INTRODUCTION
One of the most difficult problems in building truly autonomous robotic systems is developing robust automatic motion planning (Hwang and Ahuja, 1992; Kobayashi, 1981; Yuh, 1995; Latombe, 1991). Motion planning is typically complicated by the need to generate paths that satisfy various constraints, i.e., barriers. In order to efficiently and safely traverse from some starting point to a destination without colliding into obstacles, a path-planning for an autonomous robot is essential. Many researchers have proposed various path-planning schemes, but they all have shortcomings. Barraquand (1991) developed a potential-field method which can produce smooth paths using the steepest descent of the potential toward the goal (Connolly and Grupen, 1992). However, the computation is time-consuming and expensive. Additionally, potential field and bug approaches, which are local methods (Khosla and Volpe, 1988; Rimon and Doditschek, 1992; Sato, 1993; Amadieu and Heloret, 1998), will often cause this class of path-plans to fail (Choset et al., 2005). Recently, genetic algorithms have been applied in finding a shortest path planning (Lin et al., 1994; Hocaoglu and Sanderson, 1996). However, the researches have a drawback in a coding which adopts a variable-length string such as a sequence of line segment in path planning. Because of the uncertain number of steps, the usage of GA becomes troublesome when performing a path optimization within a limited working area. Chiu et al. (2009) developed a vacuum robot to sweep the ground by planning a longest path. However, it has been planned to be a fixed rectangular path during sweeping process. To overcome the above mentioned drawbacks, a novel alternative which may simplify the process of path searching by presetting the fixed steps in an x-axis and adjusting the coordinates in a y-axis via a GA optimization is proposed. The optimal coordinates of the grids which presenting the fixed-length of the chromosome in a y-axis will be globally searched using the GA algorithm flexibly.
This study discusses path-planning in two dimensions which can be directly applied to various systems such as an industrial carrier or a novelty vacuum robot (Chiu et al., 2009). Working in two dimensions allows us to view the appropriate path under various operators.
| Fig. 1: | The layout of a barrier system for an autonomous robot in a working area |
MATHEMATICAL MODELS
As indicated in Fig. 1, an autonomous robotic carrier which can be used in transporting product in industries is programmed to traverse a working area from a starting point to a destination. First, an optimum path must avoid collisions with obstacles. Additionally, the proposed total distance traversed from the starting point to the destination should be minimized during path-planning. A suitable objective function (Azizi and Aghapour, 2007) can be expressed as follows:
| (1) |
| (2) |
The first item to consider is the length of the entire path which is composed of pieces of the segment path. P(k) is the penalty function (Navidi et al., 2009) and is proportional to k, which is the number of segment paths that traverse across the obstacle. Moreover, the span of Δxi in the x-axis is preset.
In order to avoid the obstacles and quickly traverse from the starting point (xo, yo) to the destination (xn+1, yn+1), the shortest path length and minimal penalty function is required. Therefore, the minimization of OBJ is necessary.
CASE STUDY
To access the path-planning in multiple obstacles, the project supported by Topstech Company (CCUT-AI-95-AC07) is performed in Taiwan from Oct. 1, 2009 to March 31, 2010. Four kinds of multi-layer barrier systems (A: a one-layer barrier; B: a two-layer barrier; C: a three-layer barrier; D: a four-layer barrier) within a working area are exemplified and shown in Fig. 2.
| Fig. 2: | Four kinds of multiple barrier system for an autonomous robot
in a working area with x spanning 1 m (A: a one-layer barrier; B: a two-layer
barrier; C: a three-layer barrier; D: a four-layer barrier) |
In all cases,the coordinates of the starting location and targeted location are specified at (0, 1) and (15, 9), respectively.
| Fig. 3: | The given coordinates of the x-axis |
In order to quickly traverse through the working area without colliding into obstacles, accessing the path-planning of the autonomous robot in advance is necessary. To simplify the path-planning, the coordinates of the x-axis are evenly divided by 1 m. The given path coordinates of the axis are shown in Fig. 3.
GENETIC ALGORITHM
As widely known, the concept of Genetic Algorithms, first formalized by Holland (1975) and then extended to functional optimization by De-Jong (1975), involves the use of optimization search strategies patterned after the Darwinian notion of natural selection. In the present work for the optimization of the objective function (OBJ), the design parameters of (y1, y2,…,yk) were determined. When the bit (the bit length of the chromosome) was chosen, the interval of the design parameter (yk) with [Lb,Ub]k was then mapped to the band of the binary value. The mapping system between the variable interval of [Lb,Ub]k and the kth binary chromosome of
was then built. The encoding from x to B2D (binary to decimal) was performed as:
| (3) |
The initial population was built up by randomization. The parameter set was encoded to form a string which represented the chromosome. By evaluating the objective function (OBJ), the whole set of chromosomes [B2D1 , B2D2 , …., B2Dk ] that changed from binary form to decimal form was then assigned a fitness by decoding the transformation system:
| (4a) |
where
| (4b) |
The flow diagram during a path-planning optimization is depicted in Fig. 4.
As indicated in Fig. 4, to process the elitism of a gene, the tournament selection, a random comparison of the relative fitness from pairs of chromosomes, was applied. During the GA optimization, one pair of offspring from the selected parent was generated by a uniform crossover with a probability of pc. Genetically, a mutation occurred with a probability of pm where the new and unexpected point was brought into the GA optimizer’s search domain. To prevent the best gene from disappearing and to improve the accuracy of optimization during reproduction, the elitism scheme of keeping the best gene (one pair) in the parent generation with the tournament strategy was developed.
The process was terminated when a number of generations exceeded a pre-selected value of iter. The operations in the GA method are pictured in Fig. 5.
| Fig. 4: | Operations in the GA method |
| Fig. 5: | The block diagram of the GA optimization on an autonomous robot’s path-planning |
RESULTS
To achieve acceptable optimization, five kinds of GA parameters, including population size (pop), chromosome length (bit), maximum generation (iter), crossover ratio (pc) and mutation ratio (pm) are obtained by varying their values during optimization. The results of path optimization with respect to four kinds of barrier systems are described below:
A one-layer barrier system: Under the first barrier system shown in Fig. 2A, the minimization of the OBJ - total path length of the autonomous robot - was performed. As indicated in Table 1, ten sets of GA parameters (pop, bit, iter, pc, pm) were tried in the path optimization. Table 1 indicates that better design data can be obtained from the last set of GA parameters. The shortest path obtained in the 10th solution is 31.1 m when the GA parameters (pop, bit, iter, pc and pm) are equal to (80, 40, 5000, 0.8, 0.9).
A two-layer barrier system: Under the second barrier system shown in Fig. 2B, the minimization of the OBJ - total path length of the autonomous robot - was performed. By using the above GA parameters and varying iter with 500 and 5000, the optimal path design data for a two-layer barrier system is obtained and shown in Fig. 6.
Obviously, the paths obtained by numerical assessment can successfully pass through the two-layer barrier system. Moreover, the shortest path is 34.5 m at iter = 500.
| Table 1: | Optimal path for an autonomous robot with respect to various GA parameters (pop, bit, iter, pc, pm) for a one-layer barrier system (Δ =1.0 m) |
| Fig. 6: | The path curves with respect to various iter at [(pop, bit, pc and pm) = (80, 40, 0.8, 0.9)] (Δ = 1.0 m; for a two-layer barrier system) |
A three-layer barrier system: Under the third barrier system shown in Fig. 2C, the minimization of the OBJ- total path length of the autonomous robot - was performed. By using the above GA parameters and varying iter with 500 and 5000, the optimal path design data for a three-layer barrier system is obtained and shown Fig. 7.
Obviously, only the path optimized at iter = 5000 can successfully pass through the three-layer barrier system. Moreover, the shortest path obtained is 67.3 m at iter = 5000.
A four-layer barrier system: Under the fourth barrier system shown in Fig. 2D, the minimization of the OBJ - total path length of the autonomous robot - was performed. By using the above GA parameters and varying iter with 500, 5000 and 10000, the optimal path design data for a four-layer barrier system is obtained and shown in Fig. 8.
Obviously, only the path optimized at iter = 10000 can successfully pass through the four-layer barrier system. Moreover, the shortest path is 55.1 meter at iter = 10000.
| Fig. 7: | The path curves with respect to various iter at [(pop, bit,
pc and pm) = (80, 40, 0.8, 0.9)] (Δ = 1.0 m; for a three-layer barrier
system) |
| Fig. 8: | The path curves with respect to various iter at [(pop, bit,
pc and pm) = (80, 40, 0.8, 0.9)] (Δx = 1.0 m; for a four-layer barrier
system) |
DISCUSSION
To achieve a sufficient optimization, the selection of the appropriate GA parameter set is essential. As indicated in Table 1 and Fig. 6-8, the best GA set with respect to four kinds of multi-layer barrier systems (a one-layer, a two-layer, a three-layer and a four-layer barrier system) has been shown. Using the appropriate GA sets as well as the distance interval of Δx = 1.0 m at four kinds of multi-layer barrier systems, the shortest length of paths with respect to 1~4 layers barrier systems is 31.1, 34.5, 67.3 and 55.1 m. As indicated in Table 1 and Fig. 6, for a one-layer and a two-layer barrier system, the appropriate path in avoiding the obstacles and passing through the openings can be assessed easily at iter = 500. Also, as indicated in Fig. 7 and 8, for a obstacle system with three-layer and four-layer barrier, the assessed paths obtained at iter = 500 will not traverse through the working area successfully. To achieve an appropriate path during optimization process, the increment of iter from 500 to 5000 or 10000 is required. Also, the calculation time will increase from 1.22~1.33 to 12.03~25.44 min.
CONCLUSIONS
It has been shown that path-searching in conjunction with fixed steps in an x-axis can be easily and efficiently optimized within a fixed barrier system. As indicated in Table 1, the previously mentioned GA parameters (pop, bit, iter, pc, pm) play an essential role in the solution’s accuracy during GA optimization. Moreover, obstacle with more layer-barriers will increase the difficulty a robot traversing through the limited openings allocated in the barriers. As indicated in Fig. 7 and 8, to avoid a collision with 3~4 layers of barrier systems, an appropriate path is obtained by increasing the iter from 500 to 5000 or 10000 during GA optimization process.
It is obvious that the appropriate path for four kinds of multi-layer obstacles can be optimally obtained using 14 position parameters in y-axis via five kinds of GA controlling parameters (pop, bit, iter, pc, pm). The optimization parameters for the desired path can easily be changed without a total overhaul of the overall algorithm. Consequently, the method using the GA algorithm as well as the penalty function used in the objective function can efficiently find an appropriate path and easily avoid obstacles within the working area.
NOMENCLATURE
This study is constructed on the basis of the following notations:
| bit | = | Bit length |
| elt | = | Elitism (1 for yes, 0 for no) |
| iter | = | Maximum generation |
| OBJi | = | Objective function |
| pc | = | Crossover ratio |
| pm | = | Mutation ratio |
| pop | = | No. of population |
| P(k) | = | Penalty function of the objective function |
ACKNOWLEDGMENT
The author acknowledges the financial support of the Project (CCUT-AI-95-AC07).