||Obstacle avoidance for non-convex map and dynamic environment
||Department of Aeronautics & Astronautics
近年來，自動駕駛的議題受到高度的關注，一台車子要可以達到完全的自動駕駛需要包含：自身定位、導航、路徑規劃、障礙物偵測與避障。本研究重點著眼於路徑規劃與複雜的未知環境避障，並使用U-字型障礙物作為非凸地圖之範例。在模擬環境中，使用單一感測器來測障礙物並得到自身位置與靜態障礙物的相對關係，引入Danger Zone的概念，即透過自走車與障礙物的相對速度，建立碰撞曲線，在以此概念發展動態物體即時閃避功能。最後利用Simultaneous Localization And Mapping (SLAM)演算法建立地圖，進而達成兼具探索與閃避移動障礙物之功能。
Autopilot technology is not yet fully mature. An autopilot vehicle requires self-localization, navigation, path planning, obstacle detection and obstacle avoidance. Path planning and obstacle avoidance in complex unknown environments are the focus of in this research, with a use U-shaped obstacle as an example of a non-convex map. In the simulation environment, single sensor is used to detect obstacles and get the relationship between the positions of the autonomous car and obstacles. In path planning and obstacle avoidance, we introduce the concept of a danger zone. which builds a collision curve based on the relative velocity between the autonomous car and obstacles. We also develop an avoidance function for dynamic obstacles, and then use the Simultaneous Localization And Mapping(SLAM) algorithm to build maps so that the autonomous car can explore these and avoid moving objects.
TABLE OF CONTENTS IV
LIST OF FIGURES VI
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 Motivation 1
1.2 Literature Review 3
1.3 Outline of This Research 7
CHAPTER 2 OBSTACLE AVOIDANCE METHOD 8
2.1 Previous Path Planning Algorithm 8
2.2 The Basic Concept of the Danger Zone 11
2.3 Derivation and Analysis of the Danger Zone 13
2.4 Calculation of the Danger Zone with Linear Inequality Constraints 16
2.5 Representation of the Danger Zone with Quadratic Inequality Constraints 19
2.6 R-composition 24
2.7 Objective Function 25
CHAPTER 3 EXCEPTION HANDLING OF DANGER ZONE ALGORITHM 27
3.1 U-shaped Obstacle 27
3.2 New Objective Function and Adding Constraint 29
3.3 Concept of Exception Handling 31
3.4 Dynamic Weighting 33
CHAPTER 4 SIMULATION OF THE SYSTEM 43
4.1 Experiment Hardware 44
4.2 Experiment Setup 45
4.2.1 Choosing the Operating System Platform and Software 45
4.2.2 Building a Car Model 47
4.2.3 Speed Control 49
4.3 Discussion and Result 53
CHAPTER 5 CONCLUSION AND FUTURE WORK 64
 Wikipedia. Rover(space exploration), Available: https://en.wikipedia.org/wiki/Rover_(space_exploration)
 Wikipedia. Uncrewed vehicle, Available: https://en.wikipedia.org/wiki/Uncrewed_vehicle
 G. Webster and D. C. Agle. NASA Mars Rover Begins Driving at Bradbury Landing, Available: https://www.nasa.gov/home/hqnews/2012/aug/HQ_12-292_Mars_Bradbury_Landing.html
 AP. Fukushima No. 1 cleanup chief issues call for creative thinking to succeed with robot probes, Available: http://www.japantimes.co.jp/news/2017/03/03/national/fukushima-no-1-cleanup-chief-creative-thought-needed-robot-probes-reactors/#.WX9-H4SGNhF
 B. Dynamics. BigDog - The Most Advanced Rough-Terrain Robot on Earth, Available: http://www.bostondynamics.com/robot_bigdog.html
 K. Lobosco. Army of robots to invade Amazon warehouses, Available: http://money.cnn.com/2014/05/22/technology/amazon-robots/index.html
 WAYMO. Journey, Available: https://waymo.com/journey
 Tesla. Full Self-Driving Hardware on All Cars, Available: https://www.tesla.com/autopilot?redirect=no
 B. Yamauchi, "PackBot: A versatile platform for military robotics," in Proc. SPIE, 2004, p. 229.
 C. M. Shoemaker and J. A. Bornstein, "The Demo III UGV program: A testbed for autonomous navigation research," in Intelligent Control (ISIC), 1998. Held jointly with IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA), Intelligent Systems and Semiotics (ISAS), Proceedings, 1998, pp. 644-651.
 S. Odedra, S. D. Prior, and M. Karamanoglu, "Investigating the mobility of unmanned ground vehicles," in International Conference on Manufacturing and Engineering Systems. Proceedings, 2009, pp. 380-385.
 A. Haytham, Y. Elhalwagy, A. Wassal, and N. Darwish, "Modeling and simulation of four-wheel steering unmanned ground vehicles using a PID controller," presented at the 2014 International Conference on,Engineering and Technology (ICET), 2014.
 K. A. Ghamry, Y. Dong, M. A. Kamel, and Y. Zhang, "Real-time autonomous take-off, tracking and landing of UAV on a moving UGV platform," in 2016 24th Mediterranean Conference on, Control and Automation (MED), 2016, pp. 1236-1241.
 Z. Yi, H. Y. Khing, C. C. Seng, and Z. X. Wei, "Multi-ultrasonic sensor fusion for mobile robots," in Intelligent Vehicles Symposium, 2000. IV 2000. Proceedings of the IEEE, 2000, pp. 387-391.
 S. Kohlbrecher, O. Von Stryk, J. Meyer, and U. Klingauf, "A flexible and scalable slam system with full 3d motion estimation," in 2011 IEEE International Symposium on, Safety, Security, and Rescue Robotics (SSRR), 2011, pp. 155-160.
 H. Choset, Kevin M. Lynch, Seth Hutchinson, George A. Kantor, Wolfram Burgard, Lydia E. Kavraki and Sebastian Thrun, Principles of robot motion: theory, algorithms, and implementation: MIT press, 2005.
 H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, et al. "Principles of Robot Motion: Theory, Algorithms, and Implementation ERRATA!!!!," 2007.
 N. Buniyamin, W. Wan Ngah, N. Sariff, and Z. Mohamad. "A simple local path planning algorithm for autonomous mobile robots," International journal of systems applications, Engineering & development, vol. 5, no. 2, pp. 151-159, 2011.
 J. Borenstein and Y. Koren. "The vector field histogram-fast obstacle avoidance for mobile robots," IEEE transactions on robotics and automation, vol. 7, no. 3, pp. 278-288, 1991.
 M. C. Lee and M. G. Park, "Artificial potential field based path planning for mobile robots using a virtual obstacle concept," in 2003. AIM 2003. Proceedings. 2003 IEEE/ASME International Conference on, Advanced Intelligent Mechatronics, 2003, pp. 735-740.
 R. Teo and C. J. Tomlin. "Computing danger zones for provably safe closely spaced parallel approaches," Journal of Guidance Control and Dynamics, vol. 26, no. 3, pp. 434-442, 2003.
 R. Teo and C. J. Tomlin, "Computing provably safe aircraft to aircraft spacing for closely spaced parallel approaches," in Digital Avionics Systems Conference, 2000. Proceedings. DASC. The 19th, 2000, pp. 2D2/1-2D2/9 vol. 1.
 T.-C. Wang and T.-J. Lin. "Unmanned vehicle obstacle detection and avoidance using danger zone approach," Transactions of the Canadian Society for Mechanical Engineering, vol. 37, no. 3, pp. 529-538, 2013.
 I. Susnea, V. Minzu, and G. Vasiliu, "Simple, real-time obstacle avoidance algorithm for mobile robots," in 8th WSEAS International Conference on Computational Intelligence, Man-Machine Systems and Cybernetics (CIMMACS’09), 2009.
 Q. Zhang, D. Chen, and T. Chen. "An obstacle avoidance method of soccer robot based on evolutionary artificial potential field," Energy Procedia, vol. 16, pp. 1792-1798, 2012.
 J.-Y. Chen, "Semialgebraic Set Representation of Danger Zone," M.S. thesis, Dept. Aeronautics and Astronautics, National Cheng-Kung Univ., Tainan, Taiwan, 2010.
 T.-C. Wang. "Obstacle detection and avoidance with noisy measurements using danger zone concepts," Journal of the Chinese Institute of Engineers, vol. 38, no. 8, pp. 1020-1025, 2015.
 A. Balestrino, A. Caiti, E. Crisostomi, and S. Grammatico, "R-composition of Lyapunov functions," in 2009. MED'09. 17th Mediterranean Conference on, Control and Automation, 2009, pp. 126-131.
 R. H. Byrd, J. C. Gilbert, and J. Nocedal. "A trust region method based on interior point techniques for nonlinear programming," Mathematical Programming, vol. 89, no. 1, pp. 149-185, 2000.
 M. J. Powell, "A fast algorithm for nonlinearly constrained optimization calculations," in Numerical analysis, Springer, 1978, pp. 144-157.
 T. F. Coleman and Y. Li. "On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds," Mathematical programming, vol. 67, no. 1-3, pp. 189-224, 1994.
 J. Borenstein and Y. Koren. "Real-time obstacle avoidance for fast mobile robots," IEEE Transactions on systems, man, and cybernetics, vol. 19, no. 5, pp. 1179-1187, 1989.
 J. L. Blanco, M. Bellone, and A. Gimenez-Fernandez. "TP-Space RRT–Kinematic Path Planning of Non-Holonomic Any-Shape Vehicles," International Journal of Advanced Robotic Systems, vol. 12, no. 5, pp. 55, 2015.