Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 自動導覽系統中智慧型觀察者的運動計畫
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-Yenen_US
dc.contributor.author (Authors) 游宗翰zh_TW
dc.contributor.author (Authors) Yu, Tzong-Hannen_US
dc.creator (作者) 游宗翰zh_TW
dc.creator (作者) Yu, Tzong-Hannen_US
dc.date (日期) 2001en_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) A2002001571en_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 anden_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/#A2002001571en_US
dc.subject (關鍵詞) 自動導覽系統zh_TW
dc.subject (關鍵詞) 智慧型觀察者zh_TW
dc.subject (關鍵詞) 物體運動計畫zh_TW
dc.subject (關鍵詞) Automatic Tour-Guiding Systemen_US
dc.subject (關鍵詞) Intelligent Observeren_US
dc.subject (關鍵詞) Motion Planningen_US
dc.title (題名) 自動導覽系統中智慧型觀察者的運動計畫zh_TW
dc.title (題名) Motion Planning for an Intelligent Observer in Automatic Tour-Guiding Systemsen_US
dc.type (資料類型) thesisen_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