Thesis LEADER-FOLLOWER FORMATION CONTROL USING ON-BOARD SENSORS IN NOISY ENVIRONMENT The Graduate School YEUNGNAM UNIVERSITY Department of Electrical Engineering Robotics and Control Major TRAN VIET HONG Advisor: Professor Lee Suk Gyu December 2010 Ph. Thesis LEADER-FOLLOWER FORMATION CONTROL USING ON-BOARD SENSORS IN NOISY ENVIRONMENT Advisor: Professor Lee Suk Gyu Presented in Partial Fulfillment of the Requirements for the Degree of Doctor of Engineering December 2010 The Graduate School of Yeungnam University Department of Electrical Engineering Robotics and Control Major TRAN VIET HONG Tran Viet Hong’s Ph. Thesis is approved by Committee members Professor Lee, Ki Dong Professor Lee, Suk Gyu Professor Lee, Hai Young Professor Park, Ju Hyun Professor Lee, Jeh Won December 2010 The Graduate School of Yeungnam University Acknowledgments To be accepted for a PhD position at Robotics and Control Laboratory, Department of Electrical Engineering, Yeungnam University under the supervision of Professor Lee Suk-Gyu is like a fate. Right at the first meeting with him, I felt that this is a good chance for my career.
After four years, I have had a happy time and learnt a lot. I have even more experience of a new academic life and a new culture when following PhD course abroad. Looking back on the time that I spent to study and finish this thesis, I must admit that I enjoyed doing this research very much, even though it was not easy. I am glad to recall many wonderful people who accompanied me in that tough road to assist me in various ways.
I cannot reach this point by only myself. First and foremost, my very special thank gives to Professor Lee Suk-Gyu for giving me a chance to do research on simultaneous localization and mapping, and multi-robot system. His expertise, motivation, enthusiasm, understanding, and patience, taken together, make him a great mentor. Thank you for directing me through my research and for all your help during my stay.
Many thanks go to Professors at Yeungnam University, in general, and Department of Electrical Engineering, in particular, who gave me valuable lectures and advices. Especially, I would like to express my sincere appreciation to Professor Noh Seok-Kyun, my wife’s supervisor, for his valuable and numerous help to our living in Korea. I would like to thank the members of my thesis committee, Professor Lee Ki-Dong, Professor Lee Hai-Young, Professor Jessie Park Ju-Hyun and Professor Lee Jeh-Won to kindly for their time, interest, and helpful suggestions and comments. I consider myself fortunate to be with all of my past and present colleagues in Robotics and Control Laboratory and other laboratories such as Wee Sung-Gil, - iv - Park Je-Yong, Kim Jong-Uk, Joo Jin-Hwan, Lee Ho-Geun, Dilshat Saitov, Choi Kyung-Sik, Choi Yun-Won, Kim Kyung-Dong, Ryu Hee-Rack, Im Sung-Gyu, Jo Young-rae, Qu Xiaochuan, Xu Zhiguang, Dai YanYan, Liu Fenggang, Lee Tae-Hee, Kim Hon-Hee, and too many others to put all your names here.
With great appreciation, I shall acknowledge Hochiminh city University of Technology (Vietnam National University, Hochiminh city), Faculty of Mechanical Engineering for the permission to study abroad. I will never forget four years of living with a solidary and affectionate community of Vietnamese students in Yeungnam University. You helped me to overcome the difficulties of living abroad. Thanks also go to Vietnamese students in Korea for kind help, encouragement, friendship, and happy times.
And last but not least, I deeply thank Doctor Park Jung-Tae and Doctor Park Jin-Wook for your patience to take care of the health for my family. Mommy and daddy, please receive my gratitude for sacrificing your lives for us, and providing unconditional love and care. Viet Hung, my brother, is a wonderful model of scientific passion that gives me more self-confidence. It is lucky to have Nhon, my sister-in-law, here with us.
Her help is invaluable. I am also very grateful to my wife’s family who have dealt with my personal issues in Vietnam, and encouraged me constantly. Finally, my wife is one extraordinary person deserving most of the acknowledgements. She is always right beside me with listening ears, loving smiles and gives me the feeling of warmth, hope and peace.
Especially, she is spending the hard time in Vietnam to prepare for delivering our first baby. December 2010 Tran Viet Hong Yeungnam University, South Korea. -v- Contents Acknowledgments iv Contents vi List of tables viii List of Figures ix List of Abbreviations xii Abstract xiii CHAPTER 1 Introduction 14 1. Contributions and outline of the thesis.
18 CHAPTER 2 Formation and Formation Control 20 2. Introduction to formation. Applications of formation. Introduction to formation control.
Formation control structures. Formation control approaches. A leader-follower formation example and basic tasks to be controlled. 34 CHAPTER 3 Stable On-board Sensor Based Formation Control in the Presence of Obstacles 38 3.
Formation control framework for SLSF scheme. Formation control framework for TLSF scheme. Proposed control law. Obstacle Avoidance Algorithm.
Choose new desired position. Stability of obstacle avoidance algorithm. Simulations and Analysis. First simulation: small-scale robot team, merits of TLSF scheme.
Second simulation: big-scale robot team, merits of TLSF scheme. Third simulation – formation switching. Fourth simulation – single obstacle. Fifth simulation – multiple obstacles, schemes switching.
Summary and Possible Extensions. 70 CHAPTER 4 Wavelet-based Methods to Enhance Sonar Measurement 72 4. Direct Cross Correlation (CC). Generalized Cross Correlation (GCC).
Wavelet-based Generalized Cross Correlation. Enhanced Wavelet-based Methods. Improved Wavelet Pre-filter GCC (IWP-GCC). Improved Wavelet-domain Inner Product GCC (IWDIP).
Computational complexity comparison. Application in formation control. Summary and Possible Extensions. 97 CHAPTER 5 Conclusions and Future Research 99 5.
Summary of contributions. Future research directions. 101 Bibliography 103 Appendix A Calculation of ϕkm 115 Appendix B Proof of Lyapunov stability 117 - vii - List of tables Table 3.1 Parameters of the first simulation 55 Table 3.2 Displacement errors of control law [GH08] 61 Table 3.3 Displacement errors of control law (3.4 Parameters of the third simulation 63 Table 3.5 Displacement errors of control law [GH08] in third simulation 65 Table 3.6 Displacement errors of control law (3.14) in third simulation 65 Table 3.7 Parameters of the fourth simulation for 4-robot team 67 Table 3.8 Parameters of the fifth simulation 68 Table 4.1 Computational time using Matlab 91 Table 4.2 Error range of each method when SNR < –40dB 92 Table 4.3 Displacement errors of control law (3.14) at various error levels 95 ∆d Table 4.4 Relation between increment of std dk 0 and increment of ed 96 - viii - List of Figures Figure 1.1 Examples of biological systems exhibiting cooperative behaviors 15 Figure 1.2 Applications of formation control 16 Figure 1.3 Block diagram of a mobile robot 17 Figure 1.4 Outline of the thesis in corresponding with block diagram of the robot 18 Figure 2.1 Formation of UGVs working in a terrain and a field 22 Figure 2.2 Some applications of formation of UAVs and satellites 24 Figure 2.3 Two applications of formation on and under water 25 Figure 2.4 Centralized and decentralized structures 26 Figure 2.5 Motion and formation process of a group of robots with three basic tasks: forming, maintaining, and obstacle avoiding.1 (a) SLSF scheme in diamond formation (b) SLSF scheme in zigzag formation (c) TLSF scheme in diamond formation of a four-robot team.2 SLSF scheme 41 Figure 3.3 TLSF scheme 43 Figure 3.4 TLSF scheme with detailed information 45 Figure 3.5 An example of TLSF scheme in obstacle avoidance with one obstacle 50 Figure 3.6 An example of TLSF scheme in obstacle avoidance with two obstacles 50 - ix - Figure 3.7 TLSF scheme control without obstacle avoidance.8 TLSF scheme control with obstacle avoidance algorithm.9 Choose new desired position for follower robot to avoid obstacle 53 Figure 3.10 Performance of (a) control law [GH08] and (b) control law (3.11 Trajectory seen from leader robot R0 of (a) R1 and (b) R2.12 Relative distance over time between (a) R1 and R0 and (b) R2 and R0.13 Relative bearing angle over time between (a) R1 and R0, and (b) R2 and R0.14 Performance of a team of 5 robots using (a) the control law [GH08] and (b) the control law (3.14) in the TLSF scheme.15 Performance of a team of 3 robots in switching from a triangular formation to a line formation using (a) control law [GH08] and (b) control law (3.16 Robot team avoids a single obstacle when switching from formation ΩC to ΩD 66 Figure 3.17 Robot team avoids a single obstacle in maintaining formation ΩE.18 Robot team avoids obstacles without changing role of local leaders (formation ΩF).19 Robot team avoids obstacles with changing roles (formation ΩF before the first obstacle and formation ΩG after the first obstacle).1 Direct cross correlator configuration 75 Figure 4.2 A generalized cross correlator configuration [AH84] 76 -x- Figure 4.3 Wavelet Pre-filter GCC configuration 77 Figure 4.4 Wavelet-domain inner product GCC (WDIP) configuration 78 Figure 4.5 Denoise and recognition comparison.6 Original WP-GCC process 80 Figure 4.7 Improved WP-GCC process (a) Delay prediction in the wavelet domain (b) Calculate the delay by the cross correlation in the time domain 82 Figure 4.8 Improved WDIP process (a) Delay time calculation (b) Optimal cross correlation 84 Figure 4.9 Block diagram of the simulation process 87 Figure 4.10 The transmitted signal 88 Figure 4.11 The received signal at SNR = –10 dB 89 Figure 4.12 The delay error rate versus the SNR 90 Figure 4.13 Trajectories of 5 robots when ed = 42% 92 Figure 4.14 Trajectory of robot R2 when no error, ed = 30% and ed = 42% 93 Figure 4.15 Trajectory of robot R3 when no error, ed = 30% and ed = 42% 93 Figure 4.16 Trajectory of robot R2 in R0 coordinate when no error, ed = 30% and ed = 42% 94 Figure 4.17 Trajectory of robot R3 in R0 coordinate when no error, ed = 30% and ed = 42% 94 - xi - List of Abbreviations CC Cross Correlation DSP Digital Signal Processing DWT Discrete Wavelet Transform EERUF Error Eliminating Rapid Ultra-sonic Firing FFT Fast Fourier transform GCC Generalized Cross Correlation IWDIP Improved Wavelet-Domain Inner Product GCC IWP-GCC Improved Wavelet Pre-filter GCC PHAT Phase Transform SCOT Smoothed Coherent Transform SLSF Single Leader – Single Follower SNR Signal-to-Noise Ratio Sym8 Symplet whose vanishing moment is 8 TLSF Two Leaders – Single Follower UAV Unmanned Air Vehicle UGV Unmanned Ground Vehicle UUV Unmanned Underwater Vehicle WDIP Wavelet-Domain Inner Product GCC WP-GCC Wavelet Pre-filter GCC - xii - Abstract This thesis addresses three problems of leader-following formation control for multiple non-holonomic mobile robot system: stable control using only on-board sensors, obstacles avoidance, and noise’s effect reduction. Specifically, via kinematic analysis, we estimate the leaders’ translational and angular accelerations to build a stable controller whose inputs are only distance and angle information acquired from on-board sensors (do not need to measure velocities of leader robot).
In addition, the controller is common for both single leader – single follower (SLSF) and two leaders – single follower (TLSF) schemes in order to have an ability of flexible switching between those schemes. Taking full advantage of this ability, we also extend the function of the controller by an obstacle avoidance algorithm to help the formation overcome harassment of static obstacles in the environment. Moreover, because of high error from distance measurement by using ultrasonic sensor, the stability property is not enough for disturbance rejection. Therefore, we present two enhanced wavelet-based method as a supplement to ability of reducing effect of noise.
Although, the controller is such multi-functional and effective, it is still simple for quick processing, so that the time delay is kept small. Theoretical and simulation analysis show that all the functions of the controller work very well and rapidly.