使用曼哈頓模型於平面上正方形重構問題之探討

Abstract

在機器人領域中，動作規劃(Motion planning)是一個很重要的議題。最基本的問題就是探討物體如何從一個點移動到另一個點。從單一物體的動作規劃，到多重物體的動作規劃，都是要避開障礙物。而多重物體動作規劃則著重在如何避開物體之間的碰撞。多重物體動作規劃可被視為多物體的重構問題，探討一群物體如何從一組位置逐一移動到另一組位置而不發生碰撞。 這篇論文探討的即是一個平面上的方形重構問題。試想在一個平面上有n個方形，沒有其他障礙物，每個方形皆為與軸對齊且全等。n個方形在平面上的一組位置被稱為一個組態，在任一組態中，方形彼此不互相重疊。我們定義了一個新的移動模型；此模型中，每次方形的移動稱為一個曼哈頓步(Manhattan Move)，是由一個水平移動與一個垂直移動組合而成。問題如下：若給予任意兩個組態，S與T，至少需要多少曼哈頓步能將n個方形從S移動到T，且過程中每個方形的移動皆無碰撞發生？ 這篇論文中，我們介紹了這個新的移動模型以及針對這個重構問題給了一個所需的步數上限。

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.