《要给机器人(robot)下个明确定义并不容易》由会员分享，可在线阅读，更多相关《要给机器人(robot)下个明确定义并不容易（7页珍藏版）》请在金锄头文库上搜索。
1、 第一章第一章 序論序論 1.1 簡介簡介 要給機器人(robot)下個明確的定義並不容易，一個原因是隨著機器人的發展，會一直出現新的解釋；另一個原因是從不同的角度來看機器人，會得到不同的定義。例如：功能、外型、構造，這些特徵都曾被用來說明什麼是機器人。無論如何，29為機器人下了一個簡單的定義：機器人是一種真實世界中人造的東西，能夠感知環境並且行動。由此定義可區別機器人與電腦上的代理人軟體(software agent)；前者存在於現實世界，後者則是虛擬世界。另外這也說明了機器人與動物的不同，因為動物不是人類製造的。如果進一步限制由人類操作或遙控的機器不算是機器人的話，那麼由電腦控制的自動機器
2、人(autonomous robot)出現在世界上已有五十年左右的時間了。今天我們已經可以在市面上買到吸塵器機器人與寵物機器狗，但理想中的機器人應能做到大部分人類能做的事。雖然目前實用的機器人只能做幾個特定的工作，距離當初的理想還太遙遠，但是至少現在的機器人在某些工作上能夠做得比人還好，甚至還能超過人類的能力範圍，像是極為精細的工作、或是在危險的環境下執行任務。 研究機器人很重要的一個方向是機器人該如何行動，而此行動又可分為機器人本身的移動與機器人去移動環境中其他的物體；後者最常見的例子就是機器手臂(manipulator)1利用關節的轉動來操作物體 。 這些行動都可以用運動計劃(motion
3、 planning)的方法來決定機器人該如何動作。例如，有一個機器人要從它目前的位置移動到某個目標地點，或是有個機器手臂要把某個物體搬到別處去，經由運動計劃之後可以得到一連串運動的軌跡，也就是路徑(path)，讓機器人知道如何動作來完成工作。一般而言，我們稱機器人在空間中狀態的一組參數為組態(configuration) 。對於可自由移動(free-flying)的機器人來說，在空間中的位置與方向就是它的組態；如果機器人的形狀會改變，像是有關節的機器人，則它的組態就包含這些關節的角度。相對而言，工作空間(workspace)則是機器人在真實世界中的活動範圍所在的空間。在工作空間中決定了機器人的
4、起始及終止狀態，也就是在這些描述機器人狀態的參數所構成的組態空間(configuration space)中，指定了起始與終止的組態點。運動計劃的目標就是在組態空間中尋找一條避免碰撞障礙物(obstacle)的路徑，連接起點與終點組態。構成組態的參數數目又稱為自由度(DOF, degree of freedom)；當機器人的組態越複雜，自由度越大，搜尋空間的維度也越高。 機器人不是只能單獨作業，機器人與機器人之間可以互相幫助。在9中提到了多個機器人合作的好處：有些工作對單一機器人來說很困難或是需要很長的時間才能完成，因此使用多個機器人可以提高效率。而且多個機器人的系統中，每個機器人的功能可以設
5、計的比較簡單，減少發生錯誤的機會。即使有部分機器人故障，還能靠其他機器人繼續完成任務。多個機器人在運動時最大的問題就是空間上的衝突，因為在計劃這些路徑時只有考慮到環境中的障礙物，而沒有考慮到其他的機器人，按照這樣的路徑運動，有可能會互相碰撞。需要有些協調的方法來解決這個問題，例如使用類似交通規則的限制來控制機器人，或是給每個機器人不同的優先權來決定衝突時誰先行動。但是這些方法通常並無法保證能解決困難的空間衝突問題。 在計劃多個機器人的運動時，如果考慮時間這個參數，注意到每個時刻其他機器人的位置，可以確保機器人在運動時不會互相碰撞。在文獻上，群體機器人的運動計劃通2常有兩類做法：分離式(deco
6、upled approach)與集中式(centralized approach)。分離式的方法是把問題分割，讓每個機器人分別計劃運動路徑；但是這種方法並不表示它們不考慮其他機器人的路徑，而是按照一個計劃順序，後來計劃的機器人必須避開之前計劃的機器人。集中式則是把所有機器人視為一個整體，當作是一個自由度很高、可改變形狀的機器人來計劃路徑。分離式的優點是把問題分割成多個子問題，再分別去解決，比較簡單；但是，每一個機器人計劃出路徑時，都會限制到後面計劃的機器人，所以可能會出現計劃失敗的情形，也沒有好的方法可以做倒退搜尋(backtrack)的處理。集中式的優點就是能在完整的組態空間裡作自由的搜尋，
7、因此只要答案存在，理論上就可以找得到；缺點是當機器人數量很多時，組態空間的維度高，計劃的計算複雜度高，搜尋的時間也較長。 圖 1.1 群體運動計劃應用在電腦動畫的例子 群體機器人運動的自動產生，可以應用在可移動式機器人群的路徑規劃或電腦動畫(computer animation)中虛擬人群的模擬上，而電腦動畫是我們主要的應用。在製作動畫的過程中，要產生群體的運動，傳統的方法是以人工設定關鍵格(key frame)，然後用動畫製作軟體以內插(interpolation)的方式算出每個畫格(frame)的狀態。但是人數很多的時3候，要設定每個人的運動軌跡非常辛苦，最好是用更高階的方式來控制。像是圖
8、 1.1 中行走的人群，如果用人工去調整每個畫格每個動畫人物的位置，會花費相當多的時間。運動計劃便是一種解決的方法，只需要指定起始與終止的組態，中間的運動過程就交由程式自動產生。 1.2 問題定義問題定義 在這一節裡，我們會根據上述電腦動畫的應用，明確定義所要解決的問題，並且說明我們的假設與簡化問題的方法。機器人的群體運動計劃，最廣泛的定義，就是兩個以上的機器人運動計劃。我們要解決的問題，簡單而言便是：指定一個終點，讓一群機器人從目前的位置，自動計劃出避免碰撞的運動路徑，讓所有的機器人都能夠移動到終點附近的區域內。 圖 1.2 以障礙物描述的平面場景 我們假設環境中的障礙物可以被投影在一個 2
9、D 的平面工作空間中，因此障礙物以多邊形來表示，如圖 1.2 中灰色的區域。我們並假設障礙物在計劃過程中是不會移動的。另外，我們假設機器人的幾何形狀能合理的以其外包圓(enclosing circle)來表示，並且每個機器人都表示為相同半徑的圓形。如圖 1.3 的機器人群體，我們用一樣大的灰色圓形來表示它們。使用圓形有兩個好處：機器人互相偵測碰撞時，只要比較兩個圓心的距離4與兩圓的半徑和，就可以判斷；另外，因為圓形的對稱性，在計劃搜尋時可降低組態空間的維度。如圖 1.4，原本在平面上組態為(x, y, )的機器人，用圓形取代之後，可以忽略它的方向角度 。因為改變圓形的方向，並不會影響它在平面空
10、間上所佔的區域；只有在圓形移動時，平面上的狀態才會改變。所以搜尋的時候，每個機器人可以降低一維的組態空間。在機器人的運動方面，我們考慮平面上自由運動的機器人，速度限制是每單位時間在 X、Y 方向最多各移動一個單位距離，其中的單位時間與單位距離是我們定義的。 圖 1.3 用同樣大小的圓來表示所有的機器人 圖 1.4 以圓表示的機器人可以忽略方向的角度 在本論文中我們要探討的問題，如圖 1.5 所示，是為 N 個機器人 R1、R2RN由起始的狀態 S，找出一段連接的組態 CS、C1、C2CG形成一條路徑 P，讓所有的機器人能夠順利移動到共同的目的地 G。在路徑 P 中任何一個組態 Ck，機器人都不
11、能發生碰5撞，也就是任意兩個機器人 Ri與 Rj不能相交，如圖 1.6(a)；且任意一個機器人 Ri，也不能與障礙物相交，如圖 1.6(b)。我們不指定每個機器人固定的終點座標，因此終點 G 是一塊圓形的區域，計劃完成的條件是每個機器人都進入終點區域 G 內。 圖 1.5 我們定義的群體運動計劃問題 圖 1.6 碰撞的定義 1.3 研究方向與論文貢獻研究方向與論文貢獻 群體運動計劃在文獻中的探討很多，但在觀察傳統的分離式與集中式計劃之後，我們認為集中式的計劃具備搜尋的完整性，但是搜尋的時間通常較久。特別是當機器人的數量很多時，發生碰撞的機會很高，不容易找到合法的、避免碰撞的下一步組態，因此計劃
12、所花費的時間更長。我們希望能夠減少搜尋過程中碰撞的機會，讓集中式計劃更有效率，並保留其完整性。因此，針對群體運動的特性，我們提出一個階層式動態編隊的方法，來改善集中式的群體運動計劃。編隊的目的是讓鄰近的機器人每次都往同一個方向移動相同的距離，也就是說同一隊伍中的機器人走到下一步之後，互相的相對位置都不會改變，因此可以確保同一隊伍中的機器人不會隨意移動而產生碰撞。 6具體而言，本論文的貢獻包括： 1. 我們設計了分離式與集中式的群體運動計劃器 ， 並以實驗方式分析比較集中式與分離式兩種方法在不同環境與不同群體數目下的效率。 2. 我們提出了階層式動態編隊的方法，來改善集中式的群體運動計劃。使用球
13、形樹(sphere tree)的結構組織群體，有效降低機器人之間的碰撞機會，兼顧效率與完整性。 3. 將群體運動計劃的結果，應用於電腦動畫中人群運動的產生。 1.4 本論文的章節架構本論文的章節架構 在第二章裡，我們整理出一些相關研究，包括了幾種運動計劃的方法、多個機器人的運動計劃、群體運動的模擬、及球形樹結構。在第三章，介紹分離式的群體運動計劃與一些簡單的改進方法。第四章是介紹集中式的群體運動計劃。第五章則是用階層式動態編隊的方法來改善集中式的群體運動計劃。在第六章裡，我們以實驗比較各種方法在不同場景與不同人數下的效率。第七章是應用在電腦動畫上的例子，並說明實用上的考量。最後則是結論與未來發展。 7
