Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63958Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 李德財(Der-Tsai Lee) | |
| dc.contributor.author | Pei-Hsun Kao | en |
| dc.contributor.author | 高培勛 | zh_TW |
| dc.date.accessioned | 2021-06-16T17:24:25Z | - |
| dc.date.available | 2013-08-18 | |
| dc.date.copyright | 2012-08-18 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-08-16 | |
| dc.identifier.citation | [1] M. Abellanas, S. Bereg, F. Hurtado, A. G. Olaverri, D. Rappaport, and J. Tejel, Moving coins, Computational Geometry: Theory and Applications, 34(1) (2006), 35–48.
[2] S. Bereg and A. Dumitrescu, The lifting model for reconfiguration, Discrete & Computational Geometry, 35(4) (2006), 653–669. [3] S. Bereg, A. Dumitrescu, and J. Pach, Sliding disks in the plane, International Journal of Computational Geometry & Applications, 15(8) (2008), 373–387. [4] Casal and M. Yim, Self-reconfiguration planning for a class of modular robots, Proceedings of the Symposium on Intelligent Systems and Advanced Manufacturing, (SPIE’99), 246–256. [5] G. C˘alinescu, A. Dumitrescu, and J. Pach: Reconfigurations in graphs and grids, SIAM Journal on Discrete Mathematics, 22(1) (2008), 124–138. [6] G. Chirikjian, A. Pamecha, and I. Ebert-Uphoff, Evaluating efficiency of self-reconfiguration in a class of modular robots, Journal of Robotic Systems, 13(5) (1996), 317–338. [7] H. T. Croft, K. J. Falconer, and R. K. Guy, Unsolved Problems in Geometry, Springer, New York, 1991. [8] E. D. Demaine and R. A. Hearn, Playing games with algorithms: algorithmic combinatorial game theory, preprint, 2008. [9] K. Kedem and M. Sharir, An efficient motion-planning algorithm for a convex polygonal object, Discrete & Computational Geometry, 5 (1990), 43–75. [10] L. Moser, Problem 66-11, SIAM Rev., 8 (1966), 381. [11] S. Murata, H. Kurokawa, and S. Kokaji, Self-assembling machine, Proceedings of IEEE International Conference on Robotics and Automation, (1994), 441–448. [12] Nguyen, L. J. Guibas, and M. Yim, Controlled module density helps reconfiguration planning, Proceedings of IEEE International Workshop on Algorithmic Foundations of Robotics, 2000. [13] J. Pach and M. Sharir, Combinatorial Geometry and Its Algorithmic Applications — The Alcal’a Lectures, American Mathematical Society, Providence, 2009. [14] Pamecha, I. Ebert-Uphoff, and G. Chirikjian, Useful metrics for modular robot motion planning, IEEE Transactions on Robotics and Automation, 13(4) (1997), 531–545. [15] D. Ratner and M. Warmuth, Finding a shortest solution for the (N × N)-extension of the 15-puzzle is intractable, Journal of Symbolic Computation, 10 (1990), 111–137. [16] J. O’Rourke, Computational Geometry in C, Cambridge University Press, second edition, 1998. [17] D. Rus and M. Vona, Crystalline robots: self-reconfiguration with compressible unit modules, Autonomous Robots, 10 (2001), 107–124. [18] J. T. Schwartz and M. Sharir, On the “piano mover’s” problem, I, Commun. Pure Appl. Math., 36 (1983), 345–398; II, Adv. Appl. Math., 4 (1983), 298–351; III, Intl. J. Robotics Res., 2 (1983), 46–75; V, Commun. Pure Appl. Math., 37 (1984), 815–848. [19] W. E. Story, Notes on the 15 puzzle. II., American Journal of Mathematics, 2 (1879), 399–404. [20] J.E. Walter, J.L. Welch, and N.M. Amato, Distributed reconfiguration of metamorphic robot chains, Proceedings of the 19th ACM Symposium on Principles of Distributed Computing (PODC’00), July 2000, 171–180. [21] J.E. Walter, J.L. Welch, and N.M. Amato, Reconfiguration of hexagonal metamorphic robots in two dimensions, in Sensor Fusion and Decentralized Control in Robotic Systems III (G. T. McKee, P. S. Schenker, editors), Proceedings of the Society of Photo-Optical Instrumentation Engineers, Vol. 4196, 2000, 441–453. [22] X. Wei, W. Shi-gang, J. Huai-wei, Z. Zhi-zhou, and H. Lin, Strategies and methods of constructing self-organizing metamorphic robots, in Mobile Robots: New Research, edited by J. X. Liu, pp. 1–38, Nova Science, 2005. [23] R. M. Wilson, Graph puzzles, homotopy, and the alternating group, Journal of Combinatorial Theory, Series B, 16 (1974), 86–96. [24] M. Yim, Y. Zhang, J. Lamping, and E. Mao, Distributed control for 3D metamorphosis, Autonomous Robots, 10 (2001), 41–56. [25] E. Yoshida, S. Murata, A. Kamimura, K. Tomita, H. Kurokawa, and S. Kokaji, A motion planning method for a self-reconfigurable modular robot, in Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2001. [26] Adrian Dumitrescu. Mover Problems. 2011 [27] M. Erdmann and T. Lozano-P’erez, On multiple moving objects, Algorithmica, 2(1-4) (1987), 477–521. [28] Dumitrescu and M. Jiang, On reconfiguration of disks in the plane and other related problems, Proceedings of the 23rd International Symposium on Algorithms and Data Structures, (WADS 2009), Banff, August 2009, Vol. 5664 of LNCS, Springer, pp. 254–265. [29] Garc’ıa, C. Huemer, F. Hurtado, and J. Tejel, Moving rectangles, Proc. VII Jornadas de Matem’atica Discreta y Algor’ıtmica, Santander, 2010. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/63958 | - |
| dc.description.abstract | 在機器人領域中，動作規劃(Motion planning)是一個很重要的議題。最基本的問題就是探討物體如何從一個點移動到另一個點。從單一物體的動作規劃，到多重物體的動作規劃，都是要避開障礙物。而多重物體動作規劃則著重在如何避開物體之間的碰撞。多重物體動作規劃可被視為多物體的重構問題，探討一群物體如何從一組位置逐一移動到另一組位置而不發生碰撞。
這篇論文探討的即是一個平面上的方形重構問題。試想在一個平面上有n個方形，沒有其他障礙物，每個方形皆為與軸對齊且全等。n個方形在平面上的一組位置被稱為一個組態，在任一組態中，方形彼此不互相重疊。我們定義了一個新的移動模型；此模型中，每次方形的移動稱為一個曼哈頓步(Manhattan Move)，是由一個水平移動與一個垂直移動組合而成。問題如下：若給予任意兩個組態，S與T，至少需要多少曼哈頓步能將n個方形從S移動到T，且過程中每個方形的移動皆無碰撞發生？ 這篇論文中，我們介紹了這個新的移動模型以及針對這個重構問題給了一個所需的步數上限。 | zh_TW |
| dc.description.abstract | Motion planning is an important issue in robotics. The aim is to move a single object from one position to another position avoiding obstacles. Multiple object motion planning problem is focus on how to rearrange objects to their target positions while objects are not colliding to each other. Reconfiguration of objects in the plane is such a problem in two-dimensional space. In this thesis, we introduce a new model for the reconfiguration of objects in the plane.
Consider a set of n axis-parallel congruent squares in the plane and two configurations, S and T, each consisting of n pairwise disjoint square positions. We define a motion called Manhattan move, which is consisting of one horizontal translation and one vertical translation for a square. What is the minimum number of Manhattan moves that suffice for transforming S into T? Collisions are not allowed. In this thesis, we introduce this new model and give an upper bound for the number of the needed Manhattan moves. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T17:24:25Z (GMT). No. of bitstreams: 1 ntu-101-R98922085-1.pdf: 438839 bytes, checksum: ec819dca501132890cf94b9c12b38243 (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | 口試委員會審定書 #
誌謝 i ABSTRACT ii 中文摘要 iii CONTENTS iv LIST OF FIGURES vi Chapter 1 Introduction 1 1.1 Related Works 3 1.2 Our Contribution 4 1.3 Organization 5 Chapter 2 Preliminaries 6 2.1 Problem Definition 6 2.2 Terms Definition 8 2.3 Universal Method 12 Chapter 3 The Upper Bound 15 3.1 Axis-Parallel Procedure 15 3.1.1 Move Schedule for Line-separated Configurations 15 3.1.2 Procedure Steps 17 3.2 Diagonal Procedure 21 3.2.1 Procedure Steps 21 3.2.2 Move Schedule for Strip-separated Configurations 24 3.3 Method and Analysis 33 Chapter 4 Conclusion 36 REFERENCE 38 | |
| dc.language.iso | en | |
| dc.subject | 多重物體 | zh_TW |
| dc.subject | 重構 | zh_TW |
| dc.subject | reconfiguration | en |
| dc.subject | motion planning | en |
| dc.title | 使用曼哈頓模型於平面上正方形重構問題之探討 | zh_TW |
| dc.title | On Reconfiguration of Squares in the plane using Manhattan Model | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 廖崇碩(Chung-Shou Liao),林清池(Ching-Chi Lin) | |
| dc.subject.keyword | 重構,多重物體, | zh_TW |
| dc.subject.keyword | reconfiguration,motion planning, | en |
| dc.relation.page | 40 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-08-16 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| Appears in Collections: | 資訊工程學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-101-1.pdf Restricted Access | 428.55 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.