學術產出-Theses
Article View/Open
Publication Export
-
題名 自動導覽系統中智慧型觀察者的運動計畫
Motion Planning for an Intelligent Observer in Automatic Tour-Guiding Systems作者 游宗翰
Yu, Tzong-Hann貢獻者 李蔡彥
Li, Tsai-Yen
游宗翰
Yu, Tzong-Hann關鍵詞 自動導覽系統
智慧型觀察者
物體運動計畫
Automatic Tour-Guiding System
Intelligent Observer
Motion Planning日期 2001 上傳時間 18-Apr-2016 16:32:04 (UTC+8) 摘要 在本論文中，我們設計了一個以運動計畫演算法為基礎的自動導覽系統，讓使用者能透過計畫程式的輔助輕鬆地瀏覽虛擬場景。這系統包括一個我們稱之為智慧型觀察者的照相機模組，而這個模組便是本論文的研究焦點。其包含了三個主要功能：第一、追蹤導覽員（目標物），在任何時刻都要看到移動中的導覽員；第二、當使用者對照相機（觀察者）的路徑不滿意時，可以線上進行即時修改，而系統能保證其不與障礙物碰撞；第三、允許設定慣用動作(Idiom)，以豐富導覽活動。我們實作了這個自動導覽系統，並且根據二維以及三維空間的特性，提出有效率的搜尋演算法，以解決智慧型觀察者追蹤目標物的問題，並讓搜尋的時間能符合線上計算的需求。另外針對線上即時修改路徑和設定慣用動作的部分，我們也提出了線上累進的搜尋方法以及內插權重參數的方式，並以實驗證明了這些設計的有效性。我們相信此類智慧型觀察者的研究，能有效地應用在自動導覽系統或其他應用中，提供使用者以方便的介面瀏覽虛擬環境。
In this thesis, we have designed an automatic tour-guiding system based on motion planning algorithms to assist users in navigating a virtual environment. This system includes a camera module that was called intelligent observer, which is the focus of this thesis. This module includes three main functions as follows. First, the camera must be able to track the moving tour guide (target) at any time. Second, when a user is not satisfied with the camera’s (observer’s) path, he/she can choose to modify the path on-the-fly without letting the camera collide with the environmental obstacles. Third, it incorporates Cinematographic idioms to enrich tour activities. We have proposed and implemented efficient search algorithms in this system to solve the motion-tracking problem according to the characteristics of the 2D and 3D workspaces. Our experiments show that the performance of this planning system is satisfactory for our on-line application. Moreover, for the parts of modifying paths on-line and
封面頁 證明書 論文摘要 致謝詞 目錄 圖目錄 表目錄 第一章 緒論 1.1 研究動機與目的 1.2 本論文的章節架構 第二章 相關研究 2.1 物體運動計畫相關 2.2 電腦圖學相關 2.3 攝影學相關 第三章 基本追蹤問題 3.1 基本定義 3.2 已知路徑與未知路徑的追蹤 3.3 固定障礙物與移動障礙物的追蹤 3.4 全程追蹤與片段追蹤 3.5 本論文研究的範疇 第四章 二維空間中的智慧型觀察者 4.1 基本追蹤問題 4.1.1 問題描述 4.1.2 我們提出的解決方法 4.1.3 實驗結果 4.1.4 討論 4.2 線上修改路徑 4.2.1 問題描述 4.2.2 我們提出的解決方法 4.2.3 實驗結果 4.2.4 討論 4.3 慣用動作(Idiom) 4.3.1 問題描述 4.3.2 我們提出的解決方法 4.4.3 實驗結果 4.3.4 討論 第五章 三維空間中的智慧型觀察者 5.1 問題描述 5.2 我們提出的解決方法 5.3 實作成果 5.4 實驗結果 第六章 結論 6.1 結論 6.2 未來發展方向 參考文獻參考文獻 [1] Arijon, D. (1976). Grammar of the film Lannguage. Communication Arts Books, Hastings House Publishers, New York. [2] Bares, W. and Lester, J. (1997). Cinematographic User Models for Automated Realtime Camera Control in Dynamic 3D Environments. Proceedings of the 6th International Conference on User Modeling, Sardinia, Italy, 215-226. [3] Becker, C., Gonzalez-Banos, H., Latombe, J. C., and Tomasi, C. (1995). An Intelligent Observer. Proceedings of International Symposium on Experimental Robotics, 94-99. [4] Briggs, A. J. and Donald, B. R. (1996). Robust Geometric Algorithms for Sensor Planning. Proceedings of the 2nd Workshop on Algorithmic Foundations of Robotics. A.K. Peters, Wellesley, 197-212. [5] Brooks, R. A. and Lozano-Perez, T. (1985). A subdivision algorithm in configuration space for find-path with rotation. IEEE Transaction on System, Man, and Cybernetics, 15(2), 224-233. [6] Christianson, D. B., Anderson, S. E., He, L. W., Salesin, D. H., Weld, D. S. and Cohen, M. F. (1996). Declarative Camera Control for Automatic Cinematography. Proceedings of the 13th National Conference on Artificial Intelligent, Portland, 148-155. [7] Donald, B. R. (1987). A search algorithm for motion planning with six degrees of freedom. Artificial Intelligence, 31(3), 295-353. [8] Drucker, S. M. and Zeltzer, D. (1994). Intelligent Camera Control in a Virtual Environment. Graphics Interface’94, 190-199. [9] Drucker, S. M. and Zeltzer, D. (1995). CamDroid: A System for Implementing Intelligent Camera Control. Proceedings of the 1995 Symposium on Interactive 3D Graphics, 28, 139-144. [10] Faverjon, B. (1986). Object level programming of industrial robots. Proceedings of IEEE International Conference on Robotics and Automation, San Francisco, 1406-1412. [11] Gonzalez-Banos, H. H., Guibas, L., Latombe, J. C., LaValle, S. M., Lin, D., Motwani, R. and Tomasi, C. (1997). Motion Planning with Visibility Constraints: Building Autonomous Observers. Proceedings of the 8th International Symposium of Robotics Research, Hayama, Japan, 95-101. [12] Gouzenes, L. (1984). Strategies for solving collision-free trajectories problems for mobile and manipulator robots. The International Journal of Robotics Research, 3(4), 51-65. [13] Guibas, L. J., Latombe, J. C., LeValle, S. M., Lin, D. and Motwani, R. (1997). Visibility-Based Pursuit-Evasion in a Polygonal Environment. Proceedings of the 5th Workshop on Algorithms and Data Structures, Springer Verlag, 17-30. [14] He, L. W., Cohen, M. F. and Salesin, D. H. (1996). The Virtual Cinematographer: a Paradigm for Automatic Real-Time Camera Control and Directing. Proceedings of ACM SIGGRAPH’96, 217-224. [15] Kant, K. and Zucker, S. W. (1986). Toward Efficient Trajectory Planning: The Path-Velocity Decomposition. International Journal of Robotics Research, 5(3), 72-89. [16] Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90-98. [17] Khosla, P. and Volpe, R. (1988). Superquadric artificial potentials for obstacle avoidance and approach. Proceedings of IEEE International Conference on Robotics and Automation, Philadelphia, 1178-1184. [18] Koditschek, D. E. (1989). Robot planning and control via potential functions. The Robotics Review 1, O. Khatib, J. J. Craig, and T. Lozano-Perez, Eds. Cambridge: MIT Press, 349-367. [19] Latombe, J. C. (1991). Robot Motion Planning. Kluwer Academic Publisher, Boston. [20] LaValle, S. M., Gonzalez-Banos, H. H., Becker, C., Latombe, J. C. (1997). Motion Strategies for Maintaining Visibility of a Moving Target. Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 731-736. [21] Li, T. Y. and Latombe, J. C. (1997). Online Manipulation Planning for Two Robot Arms in a Dynamic Environment. International Journal of Robotics Research, 16(2), 144-167. [22] Li, T. Y., Lien, J. M., Chiu, S. Y. and Yu, T. H. (1999). Automatically Generating Virtual Guided Tours. Proceedings of the Computer Animation `99 Conference, Geneva, Switzerland, 99-106. [23] Li, T. Y. and Yu, T. H. (1999). Planning Tracking Motions for an Intelligent Virtual Camera. Proceedings of the 1999 IEEE International Conference on Robotics and Automation, 1353-1358. [24] Li, T. Y., Yu, T. H. and Shie, Y. C. (2000). Incorporating User Interaction in the Planning of Intelligent Tracking Motions. Proceeding of the 6th International Conference on Automation Technology, Taipei, Taiwan, 1185-1192. [25] O`Rourke, J. (1987). Art Gallery Theorems and Algorithms. Oxford University Press, New York. [26] Schwartz, J. T. and Sharir, M. (1983). On the ‘piano movers’ problem – II: General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4, 298-351. [27] Teller, S. J. and Hanrahan, P. M. (1997). Global Visibility Algorithms for Illumination Computations. Proceedings of ACM SIGGRAPH`97, 239-246. [28] Zhu, D. and Latombe, J. C. (1991). New heuristic for efficient hierarchical path planning. IEEE Transaction on Robotics and Automation, 7(1), 9-20. 描述 碩士
國立政治大學
資訊科學學系資料來源 http://thesis.lib.nccu.edu.tw/record/#A2002001571 資料類型 thesis dc.contributor.advisor 李蔡彥 zh_TW dc.contributor.advisor Li, Tsai-Yen en_US dc.contributor.author (Authors) 游宗翰 zh_TW dc.contributor.author (Authors) Yu, Tzong-Hann en_US dc.creator (作者) 游宗翰 zh_TW dc.creator (作者) Yu, Tzong-Hann en_US dc.date (日期) 2001 en_US dc.date.accessioned 18-Apr-2016 16:32:04 (UTC+8) - dc.date.available 18-Apr-2016 16:32:04 (UTC+8) - dc.date.issued (上傳時間) 18-Apr-2016 16:32:04 (UTC+8) - dc.identifier (Other Identifiers) A2002001571 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/85505 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學學系 zh_TW dc.description.abstract (摘要) 在本論文中，我們設計了一個以運動計畫演算法為基礎的自動導覽系統，讓使用者能透過計畫程式的輔助輕鬆地瀏覽虛擬場景。這系統包括一個我們稱之為智慧型觀察者的照相機模組，而這個模組便是本論文的研究焦點。其包含了三個主要功能：第一、追蹤導覽員（目標物），在任何時刻都要看到移動中的導覽員；第二、當使用者對照相機（觀察者）的路徑不滿意時，可以線上進行即時修改，而系統能保證其不與障礙物碰撞；第三、允許設定慣用動作(Idiom)，以豐富導覽活動。我們實作了這個自動導覽系統，並且根據二維以及三維空間的特性，提出有效率的搜尋演算法，以解決智慧型觀察者追蹤目標物的問題，並讓搜尋的時間能符合線上計算的需求。另外針對線上即時修改路徑和設定慣用動作的部分，我們也提出了線上累進的搜尋方法以及內插權重參數的方式，並以實驗證明了這些設計的有效性。我們相信此類智慧型觀察者的研究，能有效地應用在自動導覽系統或其他應用中，提供使用者以方便的介面瀏覽虛擬環境。 zh_TW dc.description.abstract (摘要) In this thesis, we have designed an automatic tour-guiding system based on motion planning algorithms to assist users in navigating a virtual environment. This system includes a camera module that was called intelligent observer, which is the focus of this thesis. This module includes three main functions as follows. First, the camera must be able to track the moving tour guide (target) at any time. Second, when a user is not satisfied with the camera’s (observer’s) path, he/she can choose to modify the path on-the-fly without letting the camera collide with the environmental obstacles. Third, it incorporates Cinematographic idioms to enrich tour activities. We have proposed and implemented efficient search algorithms in this system to solve the motion-tracking problem according to the characteristics of the 2D and 3D workspaces. Our experiments show that the performance of this planning system is satisfactory for our on-line application. Moreover, for the parts of modifying paths on-line and en_US dc.description.abstract (摘要) 封面頁 證明書 論文摘要 致謝詞 目錄 圖目錄 表目錄 第一章 緒論 1.1 研究動機與目的 1.2 本論文的章節架構 第二章 相關研究 2.1 物體運動計畫相關 2.2 電腦圖學相關 2.3 攝影學相關 第三章 基本追蹤問題 3.1 基本定義 3.2 已知路徑與未知路徑的追蹤 3.3 固定障礙物與移動障礙物的追蹤 3.4 全程追蹤與片段追蹤 3.5 本論文研究的範疇 第四章 二維空間中的智慧型觀察者 4.1 基本追蹤問題 4.1.1 問題描述 4.1.2 我們提出的解決方法 4.1.3 實驗結果 4.1.4 討論 4.2 線上修改路徑 4.2.1 問題描述 4.2.2 我們提出的解決方法 4.2.3 實驗結果 4.2.4 討論 4.3 慣用動作(Idiom) 4.3.1 問題描述 4.3.2 我們提出的解決方法 4.4.3 實驗結果 4.3.4 討論 第五章 三維空間中的智慧型觀察者 5.1 問題描述 5.2 我們提出的解決方法 5.3 實作成果 5.4 實驗結果 第六章 結論 6.1 結論 6.2 未來發展方向 參考文獻 - dc.description.tableofcontents 封面頁 證明書 論文摘要 致謝詞 目錄 圖目錄 表目錄 第一章 緒論 1.1 研究動機與目的 1.2 本論文的章節架構 第二章 相關研究 2.1 物體運動計畫相關 2.2 電腦圖學相關 2.3 攝影學相關 第三章 基本追蹤問題 3.1 基本定義 3.2 已知路徑與未知路徑的追蹤 3.3 固定障礙物與移動障礙物的追蹤 3.4 全程追蹤與片段追蹤 3.5 本論文研究的範疇 第四章 二維空間中的智慧型觀察者 4.1 基本追蹤問題 4.1.1 問題描述 4.1.2 我們提出的解決方法 4.1.3 實驗結果 4.1.4 討論 4.2 線上修改路徑 4.2.1 問題描述 4.2.2 我們提出的解決方法 4.2.3 實驗結果 4.2.4 討論 4.3 慣用動作(Idiom) 4.3.1 問題描述 4.3.2 我們提出的解決方法 4.4.3 實驗結果 4.3.4 討論 第五章 三維空間中的智慧型觀察者 5.1 問題描述 5.2 我們提出的解決方法 5.3 實作成果 5.4 實驗結果 第六章 結論 6.1 結論 6.2 未來發展方向 參考文獻 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#A2002001571 en_US dc.subject (關鍵詞) 自動導覽系統 zh_TW dc.subject (關鍵詞) 智慧型觀察者 zh_TW dc.subject (關鍵詞) 物體運動計畫 zh_TW dc.subject (關鍵詞) Automatic Tour-Guiding System en_US dc.subject (關鍵詞) Intelligent Observer en_US dc.subject (關鍵詞) Motion Planning en_US dc.title (題名) 自動導覽系統中智慧型觀察者的運動計畫 zh_TW dc.title (題名) Motion Planning for an Intelligent Observer in Automatic Tour-Guiding Systems en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Arijon, D. (1976). Grammar of the film Lannguage. Communication Arts Books, Hastings House Publishers, New York. [2] Bares, W. and Lester, J. (1997). Cinematographic User Models for Automated Realtime Camera Control in Dynamic 3D Environments. Proceedings of the 6th International Conference on User Modeling, Sardinia, Italy, 215-226. [3] Becker, C., Gonzalez-Banos, H., Latombe, J. C., and Tomasi, C. (1995). An Intelligent Observer. Proceedings of International Symposium on Experimental Robotics, 94-99. [4] Briggs, A. J. and Donald, B. R. (1996). Robust Geometric Algorithms for Sensor Planning. Proceedings of the 2nd Workshop on Algorithmic Foundations of Robotics. A.K. Peters, Wellesley, 197-212. [5] Brooks, R. A. and Lozano-Perez, T. (1985). A subdivision algorithm in configuration space for find-path with rotation. IEEE Transaction on System, Man, and Cybernetics, 15(2), 224-233. [6] Christianson, D. B., Anderson, S. E., He, L. W., Salesin, D. H., Weld, D. S. and Cohen, M. F. (1996). Declarative Camera Control for Automatic Cinematography. Proceedings of the 13th National Conference on Artificial Intelligent, Portland, 148-155. [7] Donald, B. R. (1987). A search algorithm for motion planning with six degrees of freedom. Artificial Intelligence, 31(3), 295-353. [8] Drucker, S. M. and Zeltzer, D. (1994). Intelligent Camera Control in a Virtual Environment. Graphics Interface’94, 190-199. [9] Drucker, S. M. and Zeltzer, D. (1995). CamDroid: A System for Implementing Intelligent Camera Control. Proceedings of the 1995 Symposium on Interactive 3D Graphics, 28, 139-144. [10] Faverjon, B. (1986). Object level programming of industrial robots. Proceedings of IEEE International Conference on Robotics and Automation, San Francisco, 1406-1412. [11] Gonzalez-Banos, H. H., Guibas, L., Latombe, J. C., LaValle, S. M., Lin, D., Motwani, R. and Tomasi, C. (1997). Motion Planning with Visibility Constraints: Building Autonomous Observers. Proceedings of the 8th International Symposium of Robotics Research, Hayama, Japan, 95-101. [12] Gouzenes, L. (1984). Strategies for solving collision-free trajectories problems for mobile and manipulator robots. The International Journal of Robotics Research, 3(4), 51-65. [13] Guibas, L. J., Latombe, J. C., LeValle, S. M., Lin, D. and Motwani, R. (1997). Visibility-Based Pursuit-Evasion in a Polygonal Environment. Proceedings of the 5th Workshop on Algorithms and Data Structures, Springer Verlag, 17-30. [14] He, L. W., Cohen, M. F. and Salesin, D. H. (1996). The Virtual Cinematographer: a Paradigm for Automatic Real-Time Camera Control and Directing. Proceedings of ACM SIGGRAPH’96, 217-224. [15] Kant, K. and Zucker, S. W. (1986). Toward Efficient Trajectory Planning: The Path-Velocity Decomposition. International Journal of Robotics Research, 5(3), 72-89. [16] Khatib, O. (1986). Real-time obstacle avoidance for manipulators and mobile robots. The International Journal of Robotics Research, 5(1), 90-98. [17] Khosla, P. and Volpe, R. (1988). Superquadric artificial potentials for obstacle avoidance and approach. Proceedings of IEEE International Conference on Robotics and Automation, Philadelphia, 1178-1184. [18] Koditschek, D. E. (1989). Robot planning and control via potential functions. The Robotics Review 1, O. Khatib, J. J. Craig, and T. Lozano-Perez, Eds. Cambridge: MIT Press, 349-367. [19] Latombe, J. C. (1991). Robot Motion Planning. Kluwer Academic Publisher, Boston. [20] LaValle, S. M., Gonzalez-Banos, H. H., Becker, C., Latombe, J. C. (1997). Motion Strategies for Maintaining Visibility of a Moving Target. Proceedings of the 1997 IEEE International Conference on Robotics and Automation, 731-736. [21] Li, T. Y. and Latombe, J. C. (1997). Online Manipulation Planning for Two Robot Arms in a Dynamic Environment. International Journal of Robotics Research, 16(2), 144-167. [22] Li, T. Y., Lien, J. M., Chiu, S. Y. and Yu, T. H. (1999). Automatically Generating Virtual Guided Tours. Proceedings of the Computer Animation `99 Conference, Geneva, Switzerland, 99-106. [23] Li, T. Y. and Yu, T. H. (1999). Planning Tracking Motions for an Intelligent Virtual Camera. Proceedings of the 1999 IEEE International Conference on Robotics and Automation, 1353-1358. [24] Li, T. Y., Yu, T. H. and Shie, Y. C. (2000). Incorporating User Interaction in the Planning of Intelligent Tracking Motions. Proceeding of the 6th International Conference on Automation Technology, Taipei, Taiwan, 1185-1192. [25] O`Rourke, J. (1987). Art Gallery Theorems and Algorithms. Oxford University Press, New York. [26] Schwartz, J. T. and Sharir, M. (1983). On the ‘piano movers’ problem – II: General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4, 298-351. [27] Teller, S. J. and Hanrahan, P. M. (1997). Global Visibility Algorithms for Illumination Computations. Proceedings of ACM SIGGRAPH`97, 239-246. [28] Zhu, D. and Latombe, J. C. (1991). New heuristic for efficient hierarchical path planning. IEEE Transaction on Robotics and Automation, 7(1), 9-20. zh_TW
