臺灣博碩士論文加值系統

本論文中嘗試發展系統化的方法，來解決機器人避撞運動規劃之問題。本研究之核心導源於一種數學上用於模擬波前擴張運動的傳播介面模型。從搜尋問題的角度來看，波前的傳播可視為一隊從出發點向所有方向搜索的偵察兵。當波前傳播到目標點時，這期間所花費的累計傳播時間可被用來當作避撞路徑規劃所需之人造位能場。此外，我們定義了一種新的量測值稱為碰撞趨勢指標，它可應用於碰撞測試、作為選擇避撞運動的參考值和在傳播介面模型中扮演定義波前傳播速度的角色。當使用外接橢圓和外接橢球來近似凸多邊形和凸多面體時，僅需將兩個橢圓或橢球的幾何關係轉換為高斯分布函數，即可求得碰撞趨勢指標。本文裡並探討數種在二維空間中，以傳播介面模型和碰撞趨勢指標為基礎的避撞運動規劃之方法。

An attempt is made to develop systematical approaches for robotic collision-free motion planning. The central idea was inspired by the propagating interface model, which provides a computational way of modeling the evolution of moving wavefronts. From the viewpoint of search problems, a propagating front can be regarded as the scout of a searching team exploring in all directions from the starting point. When the propagating front reaches the target position, the cumulative travel time which elapsed as the front propagated through the workspace can be regarded as the potentials and be used to plan a collision-free path. Besides, a measure called collision-trend index is proposed to perform intersection check, be the penalty function for selecting a collision-free motion in path planning problem, and play a role something like the propagating speed in the interface propagating interface model. By approximating convex polygons/polyhedra using enclosing ellipses/ellipsoids, the collision-trend index is defined by representing the geometrical relationship between ellipses/ ellipsoids as the composed profiles of Gaussian distributions. Based on the propagating interface model and the collision-trend index, several types of two- dimensional motion planning problems are investigated in this dissertation.

Chinese Abstract……………………………………………..……………………..i
English Abstract…………………………………………………….……………..ii
Acknowledgement…………………………………..…………………………….iii
Contents………………………………………………………………...…………..iv
List of Figures……………………………………………………………...…...…vi
Chapter 1.Introduction…………………….……………………….…….......01
1.1.Related Work………………..……………………………………………..02
1.2.Motivation…………………………………………………………………06
1.3.Contribution……………………………………………………………….07
1.4.Organization……………………………………………………………….08
Chapter 2.Object Representation and Collision Detection……...….…11
2.1.Object Representation.…………………...………………………………..11
2.1.1.Best-fit Enclosing Ellipsoid……………………………………….12
2.2.Two-dimensional Gaussian Function……………………………………...14
2.3.Definition of Collision-trend Index………………………………………..16
2.4.Fast Collision Detection Algorithm………………………………………..17
Chapter 3.Propagating Interface Model……………….……………...…..23
3.1.Level Set Formulation……………………………………………………..24
3.2.Fast Marching Method…………………………………………………….27
3.3.Optimal Path Generation………………………………………………..…31
Chapter 4.Global Motion Planning among Static and Moving Obstacles……………………………………………...…………….33
4.1.Propagating Speed Function……………………………………………….33
4.2.Path Planning in Static Environments…………..…………………………35
4.3.Trajectory Planning in Environment with Moving Obstacles….………….39
4.4.Discussion………………………………………………………………....41
Chapter 5.Speed Planning for a Maneuvering Motion……………..….48
5.1.Space/Time Graph………………………………………………………....48
5.1.1.Space/Time Graph Generation for Multiple Controllable Moving Objects……………………………………………………………..51
5.2.Velocity Profile Generation………………………………………………..52
5.2.1.Constraints for Velocity Profile Generation……………………….53
5.2.2.Continuity of Velocity Profile……………………………………..54
5.3.Velocity Profile Generation Based on Propagating Interface Model……...55
5.4.Simulations……………………………………………………………..…57
Chapter 6.A Novel Navigating Method in a Partial Structured Environment Based on Sonar Sensing………..……………..64
6.1.Construction of the Internal Representation……………………………….64
6.1.1.Obstacle Modeling Based on Sensory Information………………..65
6.2.Piecewise Optimal Path Planning…………………………………………67
6.3.Simulations and Discussion…………………………………………….…69
Chapter 7.Conclusion………………………………………………….….…..75
7.1.Summary…………………………………………………………………..75
7.2.Future Researches………………………………………………………....75
Appendix A.Polynomial Form of Transformed Elliptic Equation....…77
Appendix B.Standardization of Elliptic Equation………………………..79
Bibliography…………………………………………………...………………….83

[1]V. J. Lumelsky, “Algorithmic and complexity issues of robot motion in an uncertain environment,” Journal of Complexity, vol.3, pp. 146-182, 1987.
[2]P. M. Hubbard, “Collision detection for interactive graphics applications,” IEEE Transactions on Visualization and Computer Graphics, vol. 13, pp. 218-230, 1995.
[3]B. H. Lee and C. S. G. Lee, “Collision-free motion planning of two robots,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 17, no. 1, pp. 21-32, 1987.
[4]R.A. Basta, R. Mehrotra and M. R. Varanasi, “Collision detection for planning collision-free motion of two robot arms,” Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 638-640, 1988.
[5]J. Tornero, J. Hamlin and R. B. Kelly, “Spherical-object representation and fast distance computation for robotic applications,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 1602-1608, 1991.
[6]S. Bonner and R. B. Kelley, “A novel representation for planning 3-D collision free path,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 20, pp. 1337-1352, 1990.
[7]A. P. Del Pobil, M. A. Serna and J. Llovet, “A new representation for collision avoidance and detection,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 246-251, 1992.
[8]E. Rimon and S. P. Boyd, “Obstacle collision detection using best ellipsoid fit,” Journal of Intelligent and Robotic System, vol. 18, pp. 105—126, 1997.
[9]T. Brychcy and M. Kinder, “ A neural network inspired architecture for robot motion planning,” in Proc. of the Int. Conf. Engineering Applications of Artificial Neural Networks (EANN’95), pp. 103-109, 1995.
[10]D. E. Johnson, and E. Cohen, ” A framework for efficient minimum distance computations,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 3678-3684, 1998.
[11]D. P. Dobkin and D. G. Kirkpatrick, “A linear algorithm for determining the separation of convex polyhedra,” Journal of Algorithm, vol. 6, pp. 381-392, 1985.
[12]S. Quinlan, “Efficient distance computation between non-convex objects,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 3324-3329, 1994.
[13]G. Garcia and J. F. Le Corre, “ A new collision detection algorithm using octree models,” in Proc. of the IEEE/RSJ Int. Workshop on Intelligent Robots and Systems (IROS’89), pp. 93-98, 1989.
[14]D. Jung and K. K. Gupta, “Octree-based hierachical distance maps for collision detection,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 454-459, 1996.
[15]G. Hurteau and N. F. Stewart, ”Distance calculation for imminent collision indication in a robot system simulation,” Robotica, vol. 6, pp. 47-51, 1988.
[16]C. Chang, M. J. Chung and Z. Bien, “Collision-free motion planning for two articulated robot arms using minimum distance function,” Robotica, vol. 8, pp. 137-144, 1990.
[17]B. Cao, G. I. Dodds and G. W. Irwin, ”An approach to time-optimal, smooth and collision-free path planning in a two robot arm environment,” Robotica, vol. 14, pp. 61-70, 1996.
[18]C. J. Wu, “On the representation and collision detection of robots,” Journal of Intelligent and Robotic Systems, vol. 16, pp. 151-168, 1996.
[19]T. Lozano-Pérez and M. A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles,” Communications of the ACM, vol. 22, no. 10, pp. 560-570, 1979.
[20]T. Lozano-Pérez, “Spatial planning: a configuration space approach,” IEEE Transactions on Computers, vol. C-32, no. 2, pp. 108-120, 1983.
[21]J. E. Hopcroft, J. T. Schwartz and M. Sharir, “On the complexity of motion planning for multiple independent objects: PSPACE-hardness of the warehouseman’s problem,” International Journal of Robotics Research, vol. 3, no. 4, pp. 76-88, 1984.
[22]R. A. Brooks, “Solving the find-path problem by good representation of free space,” IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-13, pp. 190-197, 1983.
[23]C. L. Shih, T. Lee and W. A. Gruver, “A unified approach for robot motion planning with moving polyhedral obstacles,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 20, no.4, pp. 903-915, 1990.
[24]K. Fujimura, “Motion planning amidst dynamic obstacles in three dimensions,” in Proc. of the IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp. 1387-1392, 1993.
[25]J. Lu and K. Fujimura, “Shape transformation in space-time,” Visual Computer, vol. 12, pp. 455-473, 1996.
[26]O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” International Journal of Robotics Research, vol. 1, pp. 65-78, 1986.
[27]W. S. Newman, and N. Hogan, “High speed control and obstacle avoidance using dynamic potential functions,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp.131-141, 1987.
[28]R. Volpe, and P. Khosla, “Artificial potential with elliptical isopotential contours for obstacle avoidance,” in Proc. of the 26th IEEE Conf. Decision and Control, pp. 180-185, 1987.
[29]J. O. Kim, and P. K. Khosla, “Real-time obstacle avoidance using harmonic potential functions,” IEEE Transactions on Robotics and Automation, vol. 8, no. 3, pp. 338-349, 1992.
[30]C. I. Connolly, J. B. Burns, and R. Weiss, “Path planning using Laplace’s equation,” in Proc. of the IEEE Int. Conf. Robotics and. Automation, pp. 2102-2106, 1990.
[31]D. E. Koditschek, “Exact robot navigation by means of potential functions: some topological considerations,” in Proc. IEEE Int. Conf. Robotics and Automation, pp. 1-6, 1987.
[32]E. Rimon and D. E. Koditschek, “Exact robot navigation using artificial functions,” IEEE Transactions on Robotics and Automation, vol. 8, no. 5, pp. 501-518, 1992.
[33]K. S. Hwang and M. D. Tsai, “On-line collision-avoidance trajectory planning of two planar robots based on geometric modeling,” Journal of Information Science and Engineering, vol. 15, pp. 131-152, 1999.
[34]M. Lin and J. Canny, “A fast algorithm for incremental distance calculation,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 1008-1014, 1991.
[35]M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, 2nd corrected ed., Springer-Verlag, Berlin, 1993.
[36]E. Rimon, and S. P. Boyd, Efficient distance computation using best ellipsoid fit, Technical report, Information Systems Laboratory, Stanford University, 1992.
[37]B. J. Oommen and I. Reichstein, “On translating ellipses amidst elliptic obstacles,” in Proc. of the IEEE Int. Conf. Robotics and Automation, pp. 1755-1760, 1986.
[38]R. Malladi, J. A. Sethian, and B. C. Vemuri, “Shape modeling with front propagation: a level set approach,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, pp. 158-175, 1995.
[39]R. Malladi, J. A. Sethian, “A unified approach to noise removal, image enhancement, and shape recovery,” IEEE Transactions on Image Processing, vol. 5, pp. 1554-1568, 1996.
[40]J. A. Sethian, Level set methods, evolving interfaces in geometry, fluid mechanics, computer vision, and material science, Cambridge University Press, New York, 1996.
[41]S. J. Osher and J. A. Sethian, “Fronts propagating with curvature dependent speed: algorithm based on Hamilton-Jacobi formulations,” Journal of Computational Physics, vol. 9, pp. 12-49, 1988.
[42]M. Sussman and E. Fatem, “An efficient, interface-preserving level set redistancing algorithm and its application to interfacial incompressible fluid flow,” SIAM Journal on Scientific Computing, vol. 20, no. 4, pp. 1165-1191, 1999.
[43]Schroeder, “The eikonal equation,” The Mathematical Intelligencer, vol. 5, no. 1, pp. 36-37, 1983.
[44]F. Qin, Y. Luo, K.B. Olsen, W. Cai and G. T. Schuster, “Finite-difference solution of the eikonal equation along expanding wavefronts,” Geophysics, no. 57, pp. 478-487, 1992.
[45]J. van Trier and W. W. Symes, ”Upwind finite-difference calculation of travel-times,” Geophysics, vol. 56, pp. 812-821, 1991.
[46]E. Rouy, and A. Tourin, “A viscosity solutions approach to shape-from-shading,” SIAM Journal on Numerical Analysis, vol. 29, no. 3, pp. 867-884, 1992.
[47]D. L. Chopp, "Computing minimal surface via level set curvature flow," J. Computational Physics, vol. 106, pp. 77-91, 1993.
[48]A. P. Veselov, “Huygens'' principle and integrable systems,” Physica, vol. D87, no. 1, pp. 9-13, 1995.
[49]S. A. Wymer, A. Akhlesh, and R. S. Engel, “The Huygens'' principle for flow around an arbitrary body in a viscous incompressible fluid,” Fluid Dynamics Research, vol. 17, no, 4, pp. 213-223, 1996.
[50]T. C. Gard, Introduction to Stochastic Differential Equations, Marcel Dekker, New York, 1987.
[51]R. P. Feynman, R. B. Leighton, and M. Sands, The Feynman Lectures on Physics, Addison Westly, Massachusetts, 1964.
[52]K. Kant and S. W. Zucker, “Toward efficient trajectory planning: the path-velocity decomposition,” International Journal of Robotics Research, vol. 5, no. 3, pp. 72-89, 1986.
[53]Y. H. Liu and S. Arimoto, “Computation of the tangent graph of polygonal obstacles by moving-line processing,” IEEE Transactions on Robotics and Automation, vol. 10, pp. 823-830, 1994.
[54]K. S. Hwang, H. J. Chao, and J. S. Lin, “Collision-avoidance motion planning admit multiple moving objects,” Journal of Information Science and Engineering, vol. 15, pp. 715-736, 1999.
[55]C. De Boor, A practical guide to splines, Springer-Verlag, New York, 1978.
[56]U. Brechtken-Manderscheid, Introduction to calculus of variations, Chapman & Hall, London, 1991.
[57]E. R. Pinch, Optimal control and the calculus of variations, Oxford University Press, New York, 1993.
[58]J. C. Latombe, Robot motion planning, Kluwer, Boston, MA, 1991.
[59]T. Tsubouchi, “Nowdays trends in map generation for mobile robots,” in Proc. of the IEEE/RSJ Int. Conf. Intelligent Robotics and Systems, pp. 828-833, 1996.
[60]Polaroid Corp., Ultrasonic ranging system-Polaroid Corp., Norwood, MA, 1990.
[61]K. S. Hwang and M. Y. Ju, ŗD collision-free motion planning based on collision index," will appear in Journal of Intelligent and Robotic Systems, 2001.
[62]K. S. Hwang and M. Y. Ju, "A propagating interface model strategy for global trajectory planning among moving obstacles," submitted to IEEE Trans. Industrial Electronics. (Revised)
[63]K. S. Hwang and M. Y. Ju, "Speed planning for a maneuvering motion," will appear in Journal of Intelligent and Robotic Systems, 2001.