臺灣博碩士論文加值系統

本篇論文主要是以基因演算法與DNA演算法為基礎，分別探討3D空間中以及六自由度動態平台最佳路徑規劃及障礙物迴避問題。
3D空間中，我們提出以DNA為基礎之最佳路徑規劃演算法。在提出的方法中，工作空間被DNA編碼結構進化過程中分成幾層，每一層中較少(多)的區塊相當於區域包含著較稀疏(稠密)的障礙物。由分子所組成編碼程序演算法仿效生物演化過程，透過編碼程序，搜尋最短移動路徑並同時迴避障礙物的路徑。
另外，我們也分別對一個六自由度動態平台提出以基因演算法與DNA演算法為基礎尋找迴避奇異點的最佳路徑。該平台主要是由三個線性無刷同步馬達和三個直流伺服馬達配合導螺桿所構成。工作空間中奇異點的位置係利用基因演算法則所求出，而工作空間和路徑規劃分別利用基因演算法則與DNA演算法建構之。本研究特別將焦點放在奇異點的特性描述以及奇異點的迴避。模擬結果證實了本論文所提出的方法對於3D空間以及六自由度動態平台最佳路徑規劃的有效性。

The thesis proposes a genetic algorithm and a DNA computing-based algorithm to solve the optimal path planning problem on three dimensional (3D) space.
We propose a new DNA computing-based optimal path planning algorithm on 3D space. In the proposed approach, the path searching space is converted into several slices by using the DNA coding scheme and the numbers of slices are changeable in the evolutionary process so as to fit the locations of obstacles. The molecular programming algorithm imitates the biological evolution mechanism through artificial programming to enhance the opportunity for searching the shortest moving path while avoiding obstacles. Extensive numerical experiments are presented to confirm superiority of the proposed approach.
In addition, the genetic algorithm and DNA computing-based algorithm are also proposed to search for the optimal path while avoiding singularities for a 6 degree-of-freedoms (DOFs) dynamic platform. The base platform of this dynamic system has three linear slideways each actuated by a linear DC motor, each extensible vertical link connecting the upper and base platforms is actuated by an inductive AC servo motor. The problem of finding the precise singular attitudes is solved by applying a genetic algorithm. Characterization of the workspace and development of the path planning technique are presented by genetic algorithm and DNA algorithm. Special emphasis is put on characterizing the platform singularity characterization and singularity avoidance of the moving platform path planning based on genetic algorithm and DNA algorithm. Simulation results are presented to show the effectiveness of the proposed methods.

中文摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vii
Chapter 1 Introduction 1
Chapter 2 Preliminary 4
2.1 Genetic Algorithms 4
2.1 DNA Algorithms 7
Chapter 3 Platform Kinematics 11
3.1 Coordinates Transformation 11
3.2 Inverse Kinematics 12
3.3 Forward Kinematics 14
Chapter 4 Experimental Architecture 18
Chapter 5 Singularity Analysis based on Genetic Algorithm 19
5.1 Determination for Singularity 19
5.2 Searching for Singularities 20
5.3 Simulation Results 22
Chapter 6 Optimal Path Planning and Singularity Avoidance using Generic Algorithm 24
6.1 Searching for Optimal Path while Avoiding Singularities 24
6.2 Simulation Results 26
Chapter 7 Optimal Path Planning and Obstacles Avoidance on DNA Computing Algorithm 28
7.1 DNA Computing Algorithm 28
7.2 Optimal Path Planning and Avoiding Obstacles on 3D Space 28
7.2.1 Searching for Optimal path while Avoiding Obstacles 28
7.2.2 Simulation Results 33
7.3 Optimal Path Planning and Singularity Avoidance on Platform’s workspace 34
7.3.1 Determination for Singularity 35
7.3.2 Simulation Results 35
Chapter 8 Conclusions 37
References 38





List of Figures
FIGURE 1 The schematic flowchart of genetic algorithms 40
FIGURE 2 The structure of DNA algorithms 40
FIGURE 3 The experimental parallel manipulator 41
FIGURE 4 Top view of the upper and base platforms 41
FIGURE 5 Position and orientation of the upper platform 42
FIGURE 6 Relative position between the joint of the upper platform and linear motor’s translator on the base platform 42
FIGURE 7 Three-dimensional illustration of the workspace 43
FIGURE 8 Top view of the workspace 43
FIGURE 9 Dismemberment of the platform workspace 44
FIGURE 10 Distribution of singularities 44
FIGURE 11 Top view of a part of singularities being searched (unit: mm) 45
FIGURE 12 Singular attitude of the platform in zone 37 (unit: mm) 45
FIGURE 13 Result of searching the singularity by means of GA in zone 37 46
FIGURE 14 Singular attitude of the platform in zone 40 (unit: mm) 46
FIGURE 15 Result of searching the singularity by means of GA in zone 40 47
FIGURE 16 Path computations in 3D space 47
FIGURE 17 Coding and decoding scheme for an individual 48
FIGURE 18 Demonstrative path generation while avoiding two static obstacles 48
FIGURE 19 Demonstrative path generation while avoiding three static obstacles 49
FIGURE 20 Path generation-I while avoiding the whole singular area (unit: 100 mm) 49
FIGURE 21 Path generation-I while avoiding the major singular areas (unit: 100 mm) 50
FIGURE 22 Path generation-II while avoiding the whole singular area (unit: 100 mm) 51
FIGURE 23 Path generation-II while avoiding the major singular areas (unit: 100 mm) 52
FIGURE 24 Demonstrative dismemberment of the 3D search space 52
FIGURE 25 Top view of Fig.22 53
FIGURE 26 Coding and decoding schemes for an individual 53
FIGURE 27 Crossover operation 54
FIGURE 28 Mutation operation 54
FIGURE 29 Virus operation 55
FIGURE 30 Enzyme operation 55
FIGURE 31 Definitions of and 56
FIGURE 32 Demonstrative case 1 (a) 3D view, (b) top view, (c) alternative 3D view 57
FIGURE 33 Demonstrative case 2 58
FIGURE 34 Demonstrative case 3 58
FIGURE 35 Path generated by imposing the virus operation (a) six bits virus codon, (b) three bits virus codon 59
FIGURE 36 Demonstrative case 1 (a) path planning on 3D valley terrain, (b) alternative 3D view 60
FIGURE 37 Demonstrative case 2 (a) path planning on 3D valley terrain, (b) alternative 3D view 61
FIGURE 38 Convergence of the fitness function of GA 62
FIGURE 39 Convergence of the fitness function of DNA algorithm 62
FIGURE 40 (a) Comparison of the paths generated by GA and DNA algorithms, (b) top view 63
FIGURE 41 Path generation-I while avoiding the whole singular area (unit: 100 mm) 64
FIGURE 42 Path generation-I while avoiding the major singular areas (unit: 100 mm) 65
FIGURE 43 Path generation-II while avoiding the whole singular area (unit: 100 mm) 65
FIGURE 44 Path generation-II while avoiding the major singular areas (unit: 100 mm) 66


List of Tables
TABLE 1 Specification of parallel manipulator 67
TABLE 2 Probability of the virus operation 67
TABLE 3 Probability of the enzyme operation 67

[1]D. Stewart, “A platform with six degrees-of-freedom,” Proc. Institution of Mechanical Engineers, 180(Pt 1, 5), pp. 371-386, 1965.
[2]E. F. Fichter, “A Stewart platform-based manipulator general theory and practical construction,” International Journal of Robotics Research, 5(2), pp. 157-182, 1986.
[3]M. Raghavan, “The Stewart platform of general geometry has 40 configurations,” ASME Journal of Mechanical Design, 115(2), pp. 277-282, 1993.
[4]M. Ceccarelli, “A new 3 D.O.F. spatial parallel mechanism,” Mechanism and Machine Theory, 32, No. 8, pp. 895-902, 1997.
[5]J. Wang, and C. Gosselin, “Kinematic analysis and singularity representation of spatial five-degree-of-freedom parallel mechanism,” Journal of Robotic Systems, 14(2), pp. 851-869, 1997.
[6]J. H. Ryu, J. Song, and D. S. Kwon, “A nonlinear friction compensation method using adaptive control and its practical application to an in-parallel actuated 6-DOF manipulator,” Control Engineering Practice, 9, pp. 159-167, 2001.
[7]D. E. Goldberg, Genetic Algorithm in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, 1989.
[8]J. C. Latombe, Robot Motion Planning. Kluwer Academic Publishers, 1991.
[9]H. Toogood, H. Hao, and C. Wong, “Robot path planning using genetic algorithm,” Proc. IEEE International Conference on Systems, Man and Cybernetics, pp. 489-494, 1995.
[10]A. R. Khoogar, and J. K. Parker, “Obstacle avoidance of redundant manipulators using genetic algorithms,” Proc. IEEE International conference on Robotics and Automation, pp. 317-320, 1991.
[11]L. M. Adeleman, “Computing with DNA,” Scientific American, pp. 54-61, 1998.
[12]M. H. Garzon, and R. J. Deaton, “Bimolecular computing and programming,” IEEE Trans. on Evolutionary Computation, 3, pp. 236-250, 1999.
[13]H. Hao, and C. Wong, “Robot path planning using genetic algorithm,” Proc. IEEE International Conference on Systems, Man and Cybernetics, pp. 489-494, 1995.
[14]A. R. Khoogar, and J. K. Parker, “Obstacle avoidance of redundant manipulators using genetic algorithms,” Proc. IEEE International Conference on Robotics and Automation, pp. 317-320, 1991.
[15]J. C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
[16]W. G. Han, S. M. Baekn, and T. Y. Kuc, “Genetic algorithm based path planning and dynamic obstacle avoidance of mobile robots,” Proc. IEEE International Conference on Computational Cybernetics and Simulation, pp. 2747-2751, 1997.
[17]T. Shibata, and T. Fukuda, “Coordinative behavior in evolutionary multi-agent system by genetic algorithm,” Proc. IEEE International Conference on Neural Networks, pp. 209-214, 1993.
[18]Y. Xia, and A.E.A. Almaini, “Genetic algorithm based state assignment for power and area optimization,” Proc. of IEE International Conference on Computers and Digital Techniques, pp. 128-133, 2002.
[19]K. Kiguchi, K. Watanabe, and T. Fukuda, “Trajectory planning of mobile robots using DNA computing,” Proc. IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 380-385, 2001.
[20]S. Y. Shin, B. T. Zhang, and S. S. Jun, “Solving traveling salesman problems using molecular programming,” Proc. Congress on Evolutionary Computation, pp. 994-1000, 1999.
[21]Y. Ding, and R. Ren, “DNA genetic algorithm for design of the generalized membership-type Takagi-Sugeno fuzzy control system,” Proc. IEEE International Conference on Systems, Man, and Cybernetics, pp. 3862-3867, 2000.
[22]蔡瑞崇， “以線性馬達為基礎之動態平台設計及分析”逢甲大學自動控制工程研究所，碩士論文，2002。
[23]S. Madhav, Quality Engineering Using Robust Design. AT&T Bell Laboratories, 1989.
[24]O. Ma, and J. Angeles, “Architecture singularities of parallel manipulators,” International Journal of Robotics and Automation, 7, pp. 23-27, 1992.