機器人任務規(guī)劃

1、機器人任務規(guī)劃主要內容 一一 機器人的任務規(guī)劃機器人的任務規(guī)劃 二二 任務規(guī)劃的基本要素任務規(guī)劃的基本要素 三三 運動規(guī)劃運動規(guī)劃 四四 軌跡規(guī)劃軌跡規(guī)劃 五五 幾種機器人規(guī)劃的方法幾種機器人規(guī)劃的方法一一 機器人的任務規(guī)劃機器人的任務規(guī)劃 1.1 1.1 規(guī)劃的概念規(guī)劃的概念 1.2 1.2 規(guī)劃的作用規(guī)劃的作用 1.3 1.3 規(guī)劃問題分解途徑規(guī)劃問題分解途徑 1.4 1.4 規(guī)劃域的預測規(guī)劃域的預測 1.5 1.5 規(guī)劃的修正規(guī)劃的修正 1.6 1.6 規(guī)劃系統(tǒng)所要執(zhí)行的任務規(guī)劃系統(tǒng)所要執(zhí)行的任務一 機器人規(guī)劃綜述 1.1 1.1 規(guī)劃的概念：規(guī)劃的概念： 自動規(guī)劃是一種重要的問題求解技

2、術，它從某個特定的問題狀態(tài)出自動規(guī)劃是一種重要的問題求解技術，它從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態(tài)為止。發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標狀態(tài)為止。機器人規(guī)劃（機器人規(guī)劃（Robot planningRobot planning）是機器人學的一個重要研究領域。）是機器人學的一個重要研究領域。工工 作作 日日 規(guī)規(guī) 劃劃上午子規(guī)劃上午子規(guī)劃中午子規(guī)劃中午子規(guī)劃下午子規(guī)劃下午子規(guī)劃吃夾心面包吃夾心面包閱讀閱讀寫作寫作回家回家去上班去上班閱讀文章閱讀文章子規(guī)劃的分層結構例子子規(guī)劃的分層結構例子 一 機器人規(guī)劃綜述 1.1 1.1

3、規(guī)劃的概念：規(guī)劃的概念：Automatic planning Problem-solving technique belong to Robot planning typical example Roboticsresearch area of一 機器人規(guī)劃綜述雙足雙足( (輪輪) )自走機器人零號機登場自走機器人零號機登場 我會和人類一樣跑步啦！我會和人類一樣跑步啦！一 機器人規(guī)劃綜述 1.2 1.2 規(guī)劃的作用：規(guī)劃的作用： 在日常生活中，規(guī)劃意味著在行動之前決定行動的進程，或者說規(guī)在日常生活中，規(guī)劃意味著在行動之前決定行動的進程，或者說規(guī)劃這一詞指的是在執(zhí)行一個問題求解程序中的任何一步之

4、前，計算該程序劃這一詞指的是在執(zhí)行一個問題求解程序中的任何一步之前，計算該程序幾步的過程。一個規(guī)劃是一個行動過程的描述。缺乏規(guī)劃可能導致不適最幾步的過程。一個規(guī)劃是一個行動過程的描述。缺乏規(guī)劃可能導致不適最佳的問題求解。佳的問題求解。20142014年年4 4月機器人足球世界杯在德國開哨月機器人足球世界杯在德國開哨一 機器人規(guī)劃綜述 1.3 1.3 規(guī)劃問題分解途徑：規(guī)劃問題分解途徑： 把某些比較復雜的問題分解為一些比較小的子問題，有兩條能夠實把某些比較復雜的問題分解為一些比較小的子問題，有兩條能夠實現(xiàn)這種分解的重要途徑。現(xiàn)這種分解的重要途徑。 第一條重要途徑是，當從一個問題狀態(tài)移動到下一個狀

5、態(tài)時，無需第一條重要途徑是，當從一個問題狀態(tài)移動到下一個狀態(tài)時，無需計算整個新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。例如，一計算整個新的狀態(tài)，而只要考慮狀態(tài)中可能變化了的那些部分。例如，一個機器人從一個房間走動到另外一個房間，這并不改變兩個房間內門窗的個機器人從一個房間走動到另外一個房間，這并不改變兩個房間內門窗的位置。當問題狀態(tài)的復雜程度提高時，研究如何決定哪些事物是變化的以位置。當問題狀態(tài)的復雜程度提高時，研究如何決定哪些事物是變化的以及哪些是不變的問題（框架問題）就變得越來越重要。及哪些是不變的問題（框架問題）就變得越來越重要。 俄機器人宇航員俄機器人宇航員SAR-SAR-401

6、401。據(jù)英國。據(jù)英國每日郵每日郵報報1111月月2727日報道，俄日報道，俄羅斯最早將于羅斯最早將于20142014年派年派遣遣“機器人宇航員機器人宇航員”前前往國際空間站工作。往國際空間站工作。一 機器人規(guī)劃綜述 1.3 1.3 規(guī)劃問題分解途徑：規(guī)劃問題分解途徑： 第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易解決的子問題，這種分解能夠使困難問題的求解變得容易些。雖然這樣做解決的子問題，這種分解能夠使困難問題的求解變得容易些。雖然這樣做有時是可能的，但往往是不可能的。替代的辦法是，可以把許多問題看做有時是可能的，但往往

7、是不可能的。替代的辦法是，可以把許多問題看做待可分解問題，即意味著它們可以被分割為只有少量相互作用的子問題。待可分解問題，即意味著它們可以被分割為只有少量相互作用的子問題。 “ “發(fā)現(xiàn)號發(fā)現(xiàn)號”航天飛機（航天飛機（DiscoveryDiscovery）的最后一項）的最后一項太空任務是將首臺人形機器人送入國際空間站。這太空任務是將首臺人形機器人送入國際空間站。這位機器宇航員被命名為位機器宇航員被命名為“R2”R2”，它的活動范圍接，它的活動范圍接 近近于人類，并可以執(zhí)行那些對人類宇航員來說太過危于人類，并可以執(zhí)行那些對人類宇航員來說太過危險的任務。美國宇航局表示，險的任務。美國宇航局表示，“隨著

8、我們超越低地隨著我們超越低地球軌道，這些機器人對美國宇航局的未來至關重球軌道，這些機器人對美國宇航局的未來至關重要。要?！币?機器人規(guī)劃綜述 一個服務機器人在接受主人一個服務機器人在接受主人“給我倒一杯開水給我倒一杯開水”的命令之的命令之后后, ,機器人如何完成這一任務機器人如何完成這一任務? ?一 機器人規(guī)劃綜述取取 一一 個個 杯杯 子子找找 到到 水水 壺壺打打 開開 壺壺 塞塞J O IN T P O S IT IO N A T O BM O V E H A N D F R O M A T O B提提 起起 水水 壺壺 到到 杯杯 口口 上上 方方慢慢 慢慢 把把 水水 壺壺 傾傾 斜

9、斜把把 水水 壺壺 豎豎 直直 把把 水水 壺壺 放放 回回 原原 處處把把 水水 倒倒 入入 杯杯 中中 把把 水水 送送 給給 主主 人人給給 我我 倒倒 杯杯 水水任務規(guī)劃任務規(guī)劃運動規(guī)劃運動規(guī)劃軌跡規(guī)劃軌跡規(guī)劃總體任務總體任務子任務子任務動作順序動作順序關節(jié)運動關節(jié)運動規(guī)律規(guī)律一 機器人規(guī)劃綜述一 機器人規(guī)劃綜述規(guī)規(guī)劃劃控控制制機機器器人人本本體體要求的要求的任務任務期望的期望的運動和運動和力力控制作用控制作用實際的實際的運動和運動和力力人人機機接接口口一 機器人規(guī)劃綜述 1.4 1.4 規(guī)劃域的預測規(guī)劃域的預測 對真實世界的任何方面進行完全預測幾乎是做不到的。因此，必須對真實世界的任

10、何方面進行完全預測幾乎是做不到的。因此，必須隨時準備面對規(guī)劃的失敗。但是，如果在進行規(guī)劃時把問題分解為盡可能隨時準備面對規(guī)劃的失敗。但是，如果在進行規(guī)劃時把問題分解為盡可能多的獨立的（或近乎獨立的）子問題，那么某一規(guī)劃步驟的失敗對規(guī)劃的多的獨立的（或近乎獨立的）子問題，那么某一規(guī)劃步驟的失敗對規(guī)劃的影響是十分局部的。影響是十分局部的。 如果通過在實際上執(zhí)行某個操作序列來尋找問題的解答，那么在這如果通過在實際上執(zhí)行某個操作序列來尋找問題的解答，那么在這個過程的任何一步都能確信該步的結果。但對于不可預測的論域，最好能個過程的任何一步都能確信該步的結果。但對于不可預測的論域，最好能考慮可能的結果的集

11、合，這些結果很可能按照它們出現(xiàn)的可能性以某個次考慮可能的結果的集合，這些結果很可能按照它們出現(xiàn)的可能性以某個次序排列。然后，產(chǎn)生一個規(guī)劃，并試圖去執(zhí)行這個規(guī)劃。序排列。然后，產(chǎn)生一個規(guī)劃，并試圖去執(zhí)行這個規(guī)劃。 一 機器人規(guī)劃綜述 1.5 1.5 規(guī)劃的修正規(guī)劃的修正 如果規(guī)劃在執(zhí)行中失敗了，那么久需要對它進行修訂，為了便于修如果規(guī)劃在執(zhí)行中失敗了，那么久需要對它進行修訂，為了便于修訂，在規(guī)劃中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須執(zhí)訂，在規(guī)劃中不僅要記下規(guī)劃的執(zhí)行步驟，而且也要記下每一步驟必須執(zhí)行的理由。這樣，如果規(guī)劃中某一步失敗了，就能夠容易地應用相關定向行的理由。這樣，如果規(guī)

12、劃中某一步失敗了，就能夠容易地應用相關定向回溯技術來確定規(guī)劃的哪一部分與這一步有關而且可能需要修改。另一方回溯技術來確定規(guī)劃的哪一部分與這一步有關而且可能需要修改。另一方面，如果它是從初始狀態(tài)正向進行的，那么要決定需要的相關性可能是困面，如果它是從初始狀態(tài)正向進行的，那么要決定需要的相關性可能是困難的。大多數(shù)規(guī)劃系統(tǒng)主要是按目標定向模式工作的。難的。大多數(shù)規(guī)劃系統(tǒng)主要是按目標定向模式工作的。機器人制造公司機器人制造公司W(wǎng)owWeeWowWee公司在公司在CESCES大展上推出了可編程玩具機器人大展上推出了可編程玩具機器人MiPMiP一 機器人規(guī)劃綜述 1.6 1.6 在規(guī)劃系統(tǒng)中，必須執(zhí)行下列

13、各項任務：在規(guī)劃系統(tǒng)中，必須執(zhí)行下列各項任務： 根據(jù)最有效的啟發(fā)信息，選擇應用于下一步的最好規(guī)則。根據(jù)最有效的啟發(fā)信息，選擇應用于下一步的最好規(guī)則。 應用所選取的規(guī)則來計算由于應用該規(guī)則而生成的新狀態(tài)。應用所選取的規(guī)則來計算由于應用該規(guī)則而生成的新狀態(tài)。 對所求得的解答進行檢驗。對所求得的解答進行檢驗。 檢驗空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。檢驗空端，以便舍棄它們，使系統(tǒng)的求解工作向著更有效的方向進行。 檢驗殆正確的解答，并應用具體的技術使之完全正確。檢驗殆正確的解答，并應用具體的技術使之完全正確。Bluetooth Fighting Mini RobotBluetoo

14、th Fighting Mini Robot藍牙戰(zhàn)斗小型玩具機器人藍牙戰(zhàn)斗小型玩具機器人一 機器人規(guī)劃綜述 智能化程度越高智能化程度越高, , 規(guī)劃的層數(shù)越多規(guī)劃的層數(shù)越多, ,用戶操作越簡單。一般的工業(yè)機器人用戶操作越簡單。一般的工業(yè)機器人, , 以軌跡規(guī)劃為主以軌跡規(guī)劃為主, ,高層的規(guī)劃由人工完成。關于機器人規(guī)劃的幾點理解：高層的規(guī)劃由人工完成。關于機器人規(guī)劃的幾點理解： 機器人的規(guī)劃是分層次的：機器人的規(guī)劃是分層次的： 任務規(guī)劃任務規(guī)劃 動作規(guī)劃動作規(guī)劃 軌跡規(guī)劃軌跡規(guī)劃20142014年年5 5月月5 5日，北京，日，北京，20142014全球移動互聯(lián)網(wǎng)大會召開，在全球移動互聯(lián)網(wǎng)大會

15、召開，在大會現(xiàn)場，來自大阪大學的智能機器人研究所所長石黑浩大會現(xiàn)場，來自大阪大學的智能機器人研究所所長石黑浩展示了新款智能機器人。該機器人外形機器極其逼真，能展示了新款智能機器人。該機器人外形機器極其逼真，能夠完成點頭、眨眼等動作，并可以進行簡單的交談。夠完成點頭、眨眼等動作，并可以進行簡單的交談。一 機器人規(guī)劃綜述奧巴馬與日本人踢足球奧巴馬與日本人踢足球二 任務規(guī)劃的基本要素 2.1 2.1 狀態(tài)空間（狀態(tài)空間（StateState） 2.2 2.2 時間（時間（TimeTime） 2.3 2.3 操作狀態(tài)的動作序列（操作狀態(tài)的動作序列（ActionsActions） 2.4 2.4 初始和

16、目標狀態(tài)（初始和目標狀態(tài)（Initial and goal states)Initial and goal states) 2.5 2.5 標準（標準（A criterionA criterion） 2.6 2.6 運動計劃（運動計劃（A planA plan）二 任務規(guī)劃的基本要素 2.1 2.1 狀態(tài)空間（狀態(tài)空間（StateState） 1. 1.設計問題包括所有可能發(fā)生的狀態(tài)空間。比如機器人的位置和方向、直升設計問題包括所有可能發(fā)生的狀態(tài)空間。比如機器人的位置和方向、直升機的位置和速度等。機的位置和速度等。 2. 2.離散的和連續(xù)的狀態(tài)空間都是允許的；應該可以被簡潔的用一個計劃算法離散

17、的和連續(xù)的狀態(tài)空間都是允許的；應該可以被簡潔的用一個計劃算法描述。在大多數(shù)應用里，狀態(tài)空間的大?。〝?shù)目和復雜度）應該盡可能的被簡潔描述。在大多數(shù)應用里，狀態(tài)空間的大?。〝?shù)目和復雜度）應該盡可能的被簡潔描述。描述。 3. 3.狀態(tài)空間是設計問題中最基本的也是最重要的，應該仔細設計及分析。狀態(tài)空間是設計問題中最基本的也是最重要的，應該仔細設計及分析?！矮C豹獵豹”機器人機器人二 任務規(guī)劃的基本要素 2.2 2.2 時間（時間（TimeTime） 1. 1.所有的設計問題都包括在時間范圍內的一系列決策。所有的設計問題都包括在時間范圍內的一系列決策。 2. 2.時間模型一定要設計的簡潔，能簡單的反應事實

18、，以便動作執(zhí)行。時間模型一定要設計的簡潔，能簡單的反應事實，以便動作執(zhí)行。 3. 3.特殊的時間設計是不必要的，但簡潔的時間序列也要保證正確的特殊的時間設計是不必要的，但簡潔的時間序列也要保證正確的動作序列。動作序列。 4. 4.一個簡潔的時間設計的例子是一個簡潔的時間設計的例子是Piano Movers ProblemPiano Movers Problem：解決方：解決方案是移動鋼琴使其到另一個模擬狀態(tài)，但是特殊的速度在方案中不被專屬案是移動鋼琴使其到另一個模擬狀態(tài)，但是特殊的速度在方案中不被專屬對待。對待。機器人演奏機器人演奏二 任務規(guī)劃的基本要素 2.3 2.3 操作狀態(tài)的動作序列（操

19、作狀態(tài)的動作序列（ActionsActions） 1. 1.一個計劃產(chǎn)生一系列可以改變狀態(tài)的動作。動作這個術語在這里一個計劃產(chǎn)生一系列可以改變狀態(tài)的動作。動作這個術語在這里可以理解為人工智能中通用的可以理解為人工智能中通用的operatorsoperators。在控制理論和機器人理論中的。在控制理論和機器人理論中的對應術語為對應術語為inputsinputs和和controlscontrols。 2. 2.在設計規(guī)范中，當動作序列執(zhí)行時，狀態(tài)如何改變時必須要細致在設計規(guī)范中，當動作序列執(zhí)行時，狀態(tài)如何改變時必須要細致描述的。這就需要一個狀態(tài)返回函數(shù)，來處理離散的時間變化或者可微分描述的。這就需

20、要一個狀態(tài)返回函數(shù)，來處理離散的時間變化或者可微分的連續(xù)時間上的變化。的連續(xù)時間上的變化。 3. 3.對應絕大多數(shù)動作設計問題，關于時間的函數(shù)設計要避免直接在對應絕大多數(shù)動作設計問題，關于時間的函數(shù)設計要避免直接在狀態(tài)空間相鄰位置連續(xù)變換。狀態(tài)空間相鄰位置連續(xù)變換。二 任務規(guī)劃的基本要素 2.4 2.4 初始和目標狀態(tài)（初始和目標狀態(tài)（Initial and goal statesInitial and goal states） 1.1.一個計劃問題通常包含初始化的狀態(tài)和目標狀態(tài)，過程通過一系列設計的一個計劃問題通常包含初始化的狀態(tài)和目標狀態(tài)，過程通過一系列設計的中間狀態(tài)及動作序列組成。中間狀

21、態(tài)及動作序列組成。 2. 2.初始狀態(tài)是狀態(tài)空間的一個特殊點，也是動作序列未發(fā)生時的全局狀態(tài)。初始狀態(tài)是狀態(tài)空間的一個特殊點，也是動作序列未發(fā)生時的全局狀態(tài)。 3. 3.目標狀態(tài)時設計的一系列動作執(zhí)行后，決策者期待經(jīng)過一系列狀態(tài)變化后目標狀態(tài)時設計的一系列動作執(zhí)行后，決策者期待經(jīng)過一系列狀態(tài)變化后的最終狀態(tài)。的最終狀態(tài)。2525毫米大的毫米大的OzobotOzobot智能機器人，陪你玩游戲智能機器人，陪你玩游戲二 任務規(guī)劃的基本要素 2.5 2.5 準據(jù)（準據(jù)（A criterionA criterion） 1. 1.準據(jù)將一個關于狀態(tài)和動作的計劃的輸出結果進行編碼成可執(zhí)行準據(jù)將一個關于狀態(tài)和

22、動作的計劃的輸出結果進行編碼成可執(zhí)行格式。根據(jù)準據(jù)的類型，大致有兩類方法。格式。根據(jù)準據(jù)的類型，大致有兩類方法。 2. 2.可行性：不考慮其效率，只考慮可行性?？尚行裕翰豢紤]其效率，只考慮可行性。 3. 3.最佳性：可行的并最優(yōu)效能，在一些特定條件下，可達到目標狀最佳性：可行的并最優(yōu)效能，在一些特定條件下，可達到目標狀態(tài)。態(tài)。NaoNao智能機器人智能機器人二 任務規(guī)劃的基本要素 2.6 2.6 運動計劃（運動計劃（A planA plan） 1. 1.大體來說，一個計劃利用一個特殊的策略或者行為來施加于決策者。大體來說，一個計劃利用一個特殊的策略或者行為來施加于決策者。 2. 2.計劃應該使

23、得動作序列容易被執(zhí)行。然而，這使得設計更復雜。計劃應該使得動作序列容易被執(zhí)行。然而，這使得設計更復雜。 3. 3.預測未來的狀態(tài)是困難的，因此關注被放在狀態(tài)轉移的實現(xiàn)上。預測未來的狀態(tài)是困難的，因此關注被放在狀態(tài)轉移的實現(xiàn)上。 4. 4.若不考慮未來的狀態(tài)，當前的狀態(tài)的最優(yōu)方案是可以被設計出的，這若不考慮未來的狀態(tài)，當前的狀態(tài)的最優(yōu)方案是可以被設計出的，這和貪心策略是相似的。和貪心策略是相似的。 5. 5.當前的方法中，利用反饋和活動計劃是有效且廣泛被采納的。但是這當前的方法中，利用反饋和活動計劃是有效且廣泛被采納的。但是這樣的情況下有些狀態(tài)不發(fā)被精確測量。這將被定義成為信息狀態(tài)，在此之上計樣

24、的情況下有些狀態(tài)不發(fā)被精確測量。這將被定義成為信息狀態(tài)，在此之上計劃的動作有條件被執(zhí)行。劃的動作有條件被執(zhí)行。二 任務規(guī)劃的基本要素日本開發(fā)出會跳舞唱歌美女機器人日本開發(fā)出會跳舞唱歌美女機器人三 運動規(guī)劃 3.1 3.1 運動規(guī)劃概念運動規(guī)劃概念 3.2 3.2 運動規(guī)劃方法分類及常用算法運動規(guī)劃方法分類及常用算法 3.3 3.3 路徑規(guī)劃路徑規(guī)劃三 運動規(guī)劃 3.1 3.1 運動規(guī)劃概念運動規(guī)劃概念 運動規(guī)劃就是對一系列動作所做的規(guī)劃，它是綜合機器人的動作序運動規(guī)劃就是對一系列動作所做的規(guī)劃，它是綜合機器人的動作序列，即在某個給定初始情況下，經(jīng)過某個動作序列而達到指定的目標。列，即在某個給定

25、初始情況下，經(jīng)過某個動作序列而達到指定的目標。 動作序列的規(guī)劃是一種智能行為，如果是簡單的動作，我們可以采動作序列的規(guī)劃是一種智能行為，如果是簡單的動作，我們可以采用單關節(jié)動作規(guī)劃，然后將單個關節(jié)動作規(guī)劃得到的數(shù)據(jù)分別存儲，用于用單關節(jié)動作規(guī)劃，然后將單個關節(jié)動作規(guī)劃得到的數(shù)據(jù)分別存儲，用于組成后續(xù)過程中的復雜動作。組成后續(xù)過程中的復雜動作。該機器人是由日本川田該機器人是由日本川田工業(yè)株式會社生產(chǎn)的，工業(yè)株式會社生產(chǎn)的，首臺機器人已運至空客首臺機器人已運至空客PuertoRealPuertoReal工廠，并將工廠，并將被集成在被集成在A380A380方向舵裝方向舵裝配臺上。在那里，該機配臺上。

26、在那里，該機器人將和普通人類員工器人將和普通人類員工一起進行鉚接工作一起進行鉚接工作。三 運動規(guī)劃 3.1 3.1 運動規(guī)劃概念運動規(guī)劃概念 機器人運動規(guī)劃要完成的功能一般包括兩層：機器人運動規(guī)劃要完成的功能一般包括兩層： 第一層即所謂的路徑規(guī)劃，移動機器人在具有障礙物環(huán)境中按照一第一層即所謂的路徑規(guī)劃，移動機器人在具有障礙物環(huán)境中按照一定的評價標準，尋找一條從起始狀態(tài)（包括位置和姿態(tài)）到目標狀態(tài)（包定的評價標準，尋找一條從起始狀態(tài)（包括位置和姿態(tài)）到目標狀態(tài)（包括位置和姿態(tài)）的無碰路徑。括位置和姿態(tài)）的無碰路徑。 第二層即跟蹤控制，要求移動機器人依據(jù)路徑規(guī)劃得到路徑解，設第二層即跟蹤控制，要

27、求移動機器人依據(jù)路徑規(guī)劃得到路徑解，設計控制量序列驅動機器人安全快速地移動到目標點。計控制量序列驅動機器人安全快速地移動到目標點。20102010年年1010月月1616日，日本東京，日，日本東京，美女機器人美女機器人“HRP-4C”(HRP-4C”(中中) )在數(shù)位產(chǎn)品博覽會上唱歌跳在數(shù)位產(chǎn)品博覽會上唱歌跳舞。這個機器人身高舞。這個機器人身高1.581.58米，米，重重4343公斤，能說話，會做出公斤，能說話，會做出多種表情。多種表情。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 按照環(huán)境建模方式和搜索策略的異同，可將規(guī)劃方法大致上分成三類，按照環(huán)境建模方式

28、和搜索策略的異同，可將規(guī)劃方法大致上分成三類，分別是基于自由空間幾何構造的規(guī)劃，前向圖搜索算法和基于隨機采樣的運動分別是基于自由空間幾何構造的規(guī)劃，前向圖搜索算法和基于隨機采樣的運動規(guī)劃。規(guī)劃。 1. 1.基于自由空間幾何構造的規(guī)劃方法有可視圖、切線圖、基于自由空間幾何構造的規(guī)劃方法有可視圖、切線圖、VoronoiVoronoi圖以及圖以及精確（近似）柵格分解等方法。精確（近似）柵格分解等方法。 2. 2.前向搜索算法是從起始點出發(fā)向目標點搜索的算法，常用的包括貪心前向搜索算法是從起始點出發(fā)向目標點搜索的算法，常用的包括貪心算法、算法、DijkstraDijkstra算法、算法、A A* *算

29、法以及人工勢場法等等。算法以及人工勢場法等等。 3. 3.基于隨機采樣的規(guī)劃始于基于隨機采樣的規(guī)劃始于19901990年年BarraquandBarraquand和和LatombcLatombc提出的提出的RPPRPP（randomized potential plannerrandomized potential planner）規(guī)劃算法，用于克服人工勢場法存在的局）規(guī)劃算法，用于克服人工勢場法存在的局部極小和高維姿態(tài)空間中規(guī)劃時存在的效率問題。部極小和高維姿態(tài)空間中規(guī)劃時存在的效率問題。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 1.1.基于自由空間幾何

30、構造的規(guī)劃方法基于自由空間幾何構造的規(guī)劃方法 其基本思想就是構造某種圖來描述環(huán)境的自由空間，從圖上找到滿其基本思想就是構造某種圖來描述環(huán)境的自由空間，從圖上找到滿足某種準則的最優(yōu)路徑。此法一般包括兩個階段：第一階段構造一個描述足某種準則的最優(yōu)路徑。此法一般包括兩個階段：第一階段構造一個描述自由空間關系圖，第二階段按照一定的準則則自由空間關系圖，第二階段按照一定的準則則( (最短距離、最少時間等最短距離、最少時間等) )尋尋找一條最優(yōu)路徑。找一條最優(yōu)路徑。 可視圖法：在空間中，以多邊形障礙物模型為基礎可視圖法：在空間中，以多邊形障礙物模型為基礎, , 任意形狀障礙任意形狀障礙物用近似多邊形代替物

31、用近似多邊形代替, , 用直線將機器人運動的起始點和所有空間障礙物的用直線將機器人運動的起始點和所有空間障礙物的頂點以及目標點連接頂點以及目標點連接, , 并保證這些直線段不與空間障礙物相交并保證這些直線段不與空間障礙物相交, , 形成了一形成了一張圖張圖, , 稱為可視圖。稱為可視圖。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 1.1.基于自由空間幾何構造的規(guī)劃方法基于自由空間幾何構造的規(guī)劃方法 柵格分解法：是目前研究最廣泛的路徑規(guī)劃方法之一。該方法柵格分解法：是目前研究最廣泛的路徑規(guī)劃方法之一。該方法將機器人的工作空間分解為多個簡單的區(qū)域將機器人的工作空

32、間分解為多個簡單的區(qū)域, , 一般稱為柵格。由這些柵格一般稱為柵格。由這些柵格構成一個顯式的連通圖構成一個顯式的連通圖, , 或在搜索過程中形成隱式的連通圖或在搜索過程中形成隱式的連通圖, , 然后在圖上然后在圖上搜索一條從起始柵格到目標柵格的路徑。一般搜索一條從起始柵格到目標柵格的路徑。一般, , 路徑只需用柵格的序號表路徑只需用柵格的序號表示。按照柵格劃分的方式又分為確切的和不確切的兩種。示。按照柵格劃分的方式又分為確切的和不確切的兩種。 切線圖法：以多邊形障礙物模型為基礎切線圖法：以多邊形障礙物模型為基礎, , 任意形狀障礙物用近似多任意形狀障礙物用近似多邊形替代邊形替代, , 在自由空

33、間中構造切線圖。在自由空間中構造切線圖。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 2.2.前向圖搜索算法前向圖搜索算法 貪心算法：是最簡單的圖搜索算法。是一種典型的集中考慮局部費用最貪心算法：是最簡單的圖搜索算法。是一種典型的集中考慮局部費用最小化小化, , 而忽略全局最優(yōu)的搜索算法而忽略全局最優(yōu)的搜索算法, , 該算法不能保證一定收斂到目標節(jié)點該算法不能保證一定收斂到目標節(jié)點, , 就就是說是說, , 該算法不完備。該算法不完備。 Dijkstra Dijkstra算法：是最短路徑搜索的經(jīng)典算法算法：是最短路徑搜索的經(jīng)典算法, , 首次出現(xiàn)在首次出現(xiàn)在1

34、959 1959 年年, , 隨后隨后廣泛應用在最短路徑搜索問題中。該算法可以在顯式圖中找到從源節(jié)點到任意廣泛應用在最短路徑搜索問題中。該算法可以在顯式圖中找到從源節(jié)點到任意節(jié)點的最短路徑節(jié)點的最短路徑, , 或者從目標節(jié)點到圖中任意節(jié)點的最短路徑。如果該算法在或者從目標節(jié)點到圖中任意節(jié)點的最短路徑。如果該算法在到達目標節(jié)點時結束到達目標節(jié)點時結束, , 那么一定可以找一條從源節(jié)點到目標節(jié)點的最短路徑。那么一定可以找一條從源節(jié)點到目標節(jié)點的最短路徑。 三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 2.2.前向圖搜索算法前向圖搜索算法 A A* *算法：該算法是

35、應用極廣的隱式圖啟發(fā)式搜索算法算法：該算法是應用極廣的隱式圖啟發(fā)式搜索算法, , 其距離函數(shù)其距離函數(shù)的定義具有啟發(fā)性的定義具有啟發(fā)性, , 在柵格結構的數(shù)據(jù)集上性能相當好。在柵格結構的數(shù)據(jù)集上性能相當好。 人工勢場法：其基本思想是引入一個稱為勢場的數(shù)值函數(shù)來描述機人工勢場法：其基本思想是引入一個稱為勢場的數(shù)值函數(shù)來描述機器人空間的幾何結構器人空間的幾何結構, , 通過搜索勢場的下降方向來完成運動規(guī)劃。勢場分通過搜索勢場的下降方向來完成運動規(guī)劃。勢場分為兩部分為兩部分, , 即目標位姿產(chǎn)生的吸引勢和障礙物產(chǎn)生的排斥勢。即目標位姿產(chǎn)生的吸引勢和障礙物產(chǎn)生的排斥勢。20112011年年6 6月月2

36、929日，日本東京，昭和花子日，日本東京，昭和花子2 2號機器人向號機器人向媒體演示在醫(yī)治過程中的反應。這是位女性機器人，媒體演示在醫(yī)治過程中的反應。這是位女性機器人，由昭和大學同由昭和大學同tmsuktmsuk有限公司共同開發(fā)，被用來幫有限公司共同開發(fā)，被用來幫助牙科實習醫(yī)生在臨床培訓中更好地了解病人的疼助牙科實習醫(yī)生在臨床培訓中更好地了解病人的疼痛。這個機器人能提供逼真的治療情景，會張口、痛。這個機器人能提供逼真的治療情景，會張口、閉口，轉頭，并發(fā)出閉口，轉頭，并發(fā)出“唉喲，太疼了！唉喲，太疼了！”的聲音的聲音三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法：

37、3.3.基于隨機采樣的運動規(guī)劃方法基于隨機采樣的運動規(guī)劃方法 前面介紹的規(guī)劃算法基本上屬于相對確定的方法前面介紹的規(guī)劃算法基本上屬于相對確定的方法, , 就是說對于同一就是說對于同一環(huán)境任意兩次不同規(guī)通常環(huán)境任意兩次不同規(guī)通常, , 規(guī)劃問題的復雜度與機器人的自由度成指數(shù)關規(guī)劃問題的復雜度與機器人的自由度成指數(shù)關系系, , 與環(huán)境中障礙物的規(guī)模成多項式關系與環(huán)境中障礙物的規(guī)模成多項式關系, , 規(guī)劃問題隨著機器人自由度增規(guī)劃問題隨著機器人自由度增多會出現(xiàn)多會出現(xiàn)“維數(shù)災難維數(shù)災難( dimension curse)( dimension curse)”問題問題, , 因而以上確定性算法不因而以

38、上確定性算法不適合解決高自由度機器人在復雜環(huán)境中的實時規(guī)劃劃適合解決高自由度機器人在復雜環(huán)境中的實時規(guī)劃劃, , 結果都相同。結果都相同。 為了解決存在的問題為了解決存在的問題, , 科學家們采用基于在規(guī)劃空間科學家們采用基于在規(guī)劃空間( (如位置空間、如位置空間、姿態(tài)空間、狀態(tài)空間等姿態(tài)空間、狀態(tài)空間等) ) 中隨機采樣的方法中隨機采樣的方法, , 以損失完備性為代價提高算以損失完備性為代價提高算法的執(zhí)行效率，下面介紹法的執(zhí)行效率，下面介紹PRMPRM算法。算法。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 3.3.基于隨機采樣的運動規(guī)劃方法基于隨機采樣的運

39、動規(guī)劃方法 概率路標算法（概率路標算法（probabilistic roadmap methodprobabilistic roadmap method）算法的基本思想）算法的基本思想是用一個隨機的網(wǎng)絡來表示機器人系統(tǒng)運行的自由空間是用一個隨機的網(wǎng)絡來表示機器人系統(tǒng)運行的自由空間Cfree Cfree ，這一隨機，這一隨機網(wǎng)絡即是為機器人系統(tǒng)所建立的概率地圖。網(wǎng)絡即是為機器人系統(tǒng)所建立的概率地圖。 該算法可通過該算法可通過2 2個階段來完成：離線學習階段個階段來完成：離線學習階段(1earning phase)(1earning phase)和在和在線查詢階段線查詢階段(query phase

40、)(query phase)。電空客公司位于西班牙加電空客公司位于西班牙加迪斯的迪斯的PuertoRealPuertoReal工廠正工廠正在進行一項旨在提高工廠在進行一項旨在提高工廠裝配自動化的項目，使用裝配自動化的項目，使用日本制造的雙臂仿人機器日本制造的雙臂仿人機器人來承擔飛機裝配過程中人來承擔飛機裝配過程中的重復性工作。的重復性工作。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 4.4.其他智能化規(guī)劃方法其他智能化規(guī)劃方法 路徑規(guī)劃是環(huán)境模型和搜索算法相結合的一種技術路徑規(guī)劃是環(huán)境模型和搜索算法相結合的一種技術, , 規(guī)劃過程既是規(guī)劃過程既是搜索的過程搜

41、索的過程, , 也是推理的過程。人工智能中的很多優(yōu)化、推理技術也被運也是推理的過程。人工智能中的很多優(yōu)化、推理技術也被運用到移動機器人運動規(guī)劃中來用到移動機器人運動規(guī)劃中來, , 如遺傳算法、模糊推理以及神經(jīng)網(wǎng)絡等在如遺傳算法、模糊推理以及神經(jīng)網(wǎng)絡等在移動機器人運動規(guī)劃中起到很大的作用。移動機器人運動規(guī)劃中起到很大的作用。 遺傳算法規(guī)劃器：首先初始化路徑群體遺傳算法規(guī)劃器：首先初始化路徑群體, , 然后進行遺傳操作然后進行遺傳操作, , 如選如選擇、交叉、復制、變異。經(jīng)過若干代的進化以后擇、交叉、復制、變異。經(jīng)過若干代的進化以后, , 停止進化停止進化, , 輸出當前最輸出當前最優(yōu)個體作為路徑

42、下一個節(jié)點。優(yōu)個體作為路徑下一個節(jié)點。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 4.4.其他智能化規(guī)劃方法其他智能化規(guī)劃方法 模糊規(guī)劃器：模糊規(guī)劃器利用反射式導航機制，將當前環(huán)境障礙信模糊規(guī)劃器：模糊規(guī)劃器利用反射式導航機制，將當前環(huán)境障礙信息作為模糊推理機的輸入息作為模糊推理機的輸入, , 推理機輸出機器人期望的轉向角和速度等。該推理機輸出機器人期望的轉向角和速度等。該方法在環(huán)境未知或發(fā)生變化的情況下方法在環(huán)境未知或發(fā)生變化的情況下, , 能夠快速而準確地規(guī)劃機器人局部能夠快速而準確地規(guī)劃機器人局部路徑路徑, , 對于要求有較少路徑規(guī)劃時間的機器人是一種

43、很好的導航方法。但對于要求有較少路徑規(guī)劃時間的機器人是一種很好的導航方法。但是是, , 其缺點是當障礙物數(shù)目增加時其缺點是當障礙物數(shù)目增加時, , 該方法的計算量較大該方法的計算量較大, , 影響規(guī)劃結果影響規(guī)劃結果, , 而且該規(guī)劃器只利用局部信息作出快速反應而且該規(guī)劃器只利用局部信息作出快速反應, , 較容易陷入局部極小。較容易陷入局部極小。三 運動規(guī)劃 3.2 3.2 運動規(guī)劃分類及常用算法：運動規(guī)劃分類及常用算法： 4.4.其他智能化規(guī)劃方法其他智能化規(guī)劃方法 神經(jīng)網(wǎng)絡規(guī)劃器：近年來神經(jīng)網(wǎng)絡規(guī)劃器：近年來, , 科學家一直致力將機器學習的技術運用科學家一直致力將機器學習的技術運用到機器

44、人中來，或者說致力于依靠智能機器人技術來推動機器學習的發(fā)展到機器人中來，或者說致力于依靠智能機器人技術來推動機器學習的發(fā)展, , 事實上事實上, , 它們是密不可分的。其基本原理是將環(huán)境障礙等作為神經(jīng)網(wǎng)絡的它們是密不可分的。其基本原理是將環(huán)境障礙等作為神經(jīng)網(wǎng)絡的輸入層信息輸入層信息, , 經(jīng)由神經(jīng)網(wǎng)絡并行處理經(jīng)由神經(jīng)網(wǎng)絡并行處理, , 神經(jīng)網(wǎng)絡輸出層輸出期望的轉向角神經(jīng)網(wǎng)絡輸出層輸出期望的轉向角和速度等和速度等, , 引導機器人避障行駛引導機器人避障行駛, , 直至到達目的地。直至到達目的地。20072007年年9 9月月2828日，在西班日，在西班牙的巴塞羅那，第二代牙的巴塞羅那，第二代“阿

45、西莫阿西莫”雙腳步行機雙腳步行機器人亮相并表演上樓梯。器人亮相并表演上樓梯。三 運動規(guī)劃關節(jié)非常靈活的充氣機器人關節(jié)非常靈活的充氣機器人四 軌跡規(guī)劃 4.1 4.1 路徑和軌跡路徑和軌跡 4.2 4.2 軌跡規(guī)劃軌跡規(guī)劃四 軌跡規(guī)劃 4.14.1路徑和軌跡路徑和軌跡 機器人的軌跡指操作臂在運動過程中的位移、速度和加速度。機器人的軌跡指操作臂在運動過程中的位移、速度和加速度。 路徑路徑是機器人位姿的一定序列是機器人位姿的一定序列, ,而不考慮機器人位姿參數(shù)隨時間變化的因素。如而不考慮機器人位姿參數(shù)隨時間變化的因素。如下張下張PPTPPT圖所示圖所示, ,如果有關機器人從如果有關機器人從A A點運

46、動到點運動到B B點點, , 再到再到C C點點, , 那么這中間那么這中間位姿序列就構成了一條路徑。而軌跡則與何時到達路徑中的每個部分有關位姿序列就構成了一條路徑。而軌跡則與何時到達路徑中的每個部分有關, , 強調的是時間。強調的是時間。機器人在路徑上的依次運動機器人在路徑上的依次運動 四 軌跡規(guī)劃 4.2 4.2 軌跡規(guī)劃軌跡規(guī)劃 軌跡規(guī)劃是指根據(jù)作業(yè)任務要求確定軌跡參數(shù)并實時計算和生成運軌跡規(guī)劃是指根據(jù)作業(yè)任務要求確定軌跡參數(shù)并實時計算和生成運動軌跡。軌跡規(guī)劃的一般問題有三個動軌跡。軌跡規(guī)劃的一般問題有三個: : (1) (1) 對機器人的任務進行描述對機器人的任務進行描述, , 即運動

47、軌跡的描述。即運動軌跡的描述。 (2) (2) 根據(jù)已經(jīng)確定的軌跡參數(shù)根據(jù)已經(jīng)確定的軌跡參數(shù), , 在計算機上模擬所要求的軌跡。在計算機上模擬所要求的軌跡。 (3) (3) 對軌跡進行實際計算對軌跡進行實際計算, ,即在運行時間內按一定的速率計算出位置、即在運行時間內按一定的速率計算出位置、速度和加速度速度和加速度, ,從而生成運動軌跡。從而生成運動軌跡。 在規(guī)劃中在規(guī)劃中, ,不僅要規(guī)定機器人的起始點和終止點不僅要規(guī)定機器人的起始點和終止點, , 而且要給出中間而且要給出中間點點( (路徑點路徑點) )的位姿及路徑點之間的時間分配的位姿及路徑點之間的時間分配, , 即給出兩個路徑點之間的運即

48、給出兩個路徑點之間的運動時間。動時間。 四 軌跡規(guī)劃 以二自由度平面關節(jié)機器人為例。以二自由度平面關節(jié)機器人為例。 如下圖所示如下圖所示, ,要求機器人從要求機器人從A A點運點運動到動到B B點。機器人在點。機器人在A A點時形位角為點時形位角為=20=20,=30,=30; ;達到達到B B點時的形位角點時的形位角是是=40=40,=80,=80。兩關節(jié)運動的最大速率均為。兩關節(jié)運動的最大速率均為1010/s/s。當機器人的所。當機器人的所有關節(jié)均以最大速度運動時有關節(jié)均以最大速度運動時, ,下方的連桿將用下方的連桿將用2s2s到達到達, , 而上方的連桿還需再而上方的連桿還需再運動運動3

49、s,3s,可見路徑是不規(guī)則的可見路徑是不規(guī)則的, ,手部掠過的距離點也是不均勻的。手部掠過的距離點也是不均勻的。二自由度機器人關節(jié)空間的非歸一化運動二自由度機器人關節(jié)空間的非歸一化運動 四 軌跡規(guī)劃 設機器人手臂兩個關節(jié)的運動用有關公共因子做歸一化處理設機器人手臂兩個關節(jié)的運動用有關公共因子做歸一化處理, ,使手臂使手臂運動范圍較小的關節(jié)運動成比例的減慢運動范圍較小的關節(jié)運動成比例的減慢, ,這樣這樣, ,兩個關節(jié)就能夠同步開始和兩個關節(jié)就能夠同步開始和結束運動結束運動, , 即兩個關節(jié)以不同速度一起連續(xù)運動即兩個關節(jié)以不同速度一起連續(xù)運動, , 速率分別為速率分別為4 4/s/s和和1010

50、/s/s。如下圖所示為該機器人兩關節(jié)運動軌跡。如下圖所示為該機器人兩關節(jié)運動軌跡, , 與前面的不同與前面的不同, , 其運動其運動更加均衡更加均衡, , 且實現(xiàn)了關節(jié)速率歸一化。且實現(xiàn)了關節(jié)速率歸一化。 二自由度機器人關節(jié)空間的歸一化運動二自由度機器人關節(jié)空間的歸一化運動 四 軌跡規(guī)劃 如果希望機器人的手部可以沿如果希望機器人的手部可以沿ABAB這條直線運動這條直線運動, , 最簡單的方法是將最簡單的方法是將該直線等分為幾部分該直線等分為幾部分( (圖中分成圖中分成5 5份份), ), 然后計算出各個點所需的形位角然后計算出各個點所需的形位角和和的值的值, , 這一過程稱為兩點間的插值。這時

51、路徑是一條直線這一過程稱為兩點間的插值。這時路徑是一條直線, , 而形位角變而形位角變化并不均勻。如果路徑點過少化并不均勻。如果路徑點過少, , 將不能保證機器人在每一小段內的嚴格直將不能保證機器人在每一小段內的嚴格直線軌跡。因此線軌跡。因此, ,為獲得良好的沿循精度為獲得良好的沿循精度, , 應對路徑進行更加細致的分割。由應對路徑進行更加細致的分割。由于對機器人軌跡的所有運動段的計算均基于直角坐標系于對機器人軌跡的所有運動段的計算均基于直角坐標系, , 因此該法屬直角因此該法屬直角坐標空間的軌跡規(guī)劃。坐標空間的軌跡規(guī)劃。二自由度機器人直角坐標空間的運動二自由度機器人直角坐標空間的運動 四 軌

52、跡規(guī)劃日本研究出能在石頭剪刀布游戲中百戰(zhàn)百勝的機器人日本研究出能在石頭剪刀布游戲中百戰(zhàn)百勝的機器人五 幾種機器人規(guī)劃的方法 5.1 5.1 積木世界的機器人規(guī)劃積木世界的機器人規(guī)劃 5.2 STRIPS 5.2 STRIPS 規(guī)劃系統(tǒng)規(guī)劃系統(tǒng) 5.3 5.3 分層規(guī)劃分層規(guī)劃 5.4 5.4 基于專家系統(tǒng)的機器人規(guī)劃基于專家系統(tǒng)的機器人規(guī)劃 5.5 5.5 本章小結本章小結五 幾種機器人規(guī)劃的方法5.1 5.1 積木世界的機器人問題積木世界的機器人問題 機器人問題既比較簡單，又很直觀。在機器人問題的典型表示中，機器人能夠執(zhí)行機器人問題既比較簡單，又很直觀。在機器人問題的典型表示中，機器人能夠執(zhí)

53、行一套動作。一套動作。 在這個例子中機器人能夠執(zhí)行的動作舉例如下：在這個例子中機器人能夠執(zhí)行的動作舉例如下： unstackunstack( (a,ba,b) )：把堆放在積木：把堆放在積木 b b 上的積木上的積木 a a 拾起。在進行這個動作之前，要求機拾起。在進行這個動作之前，要求機器人的手為空手，而且積木器人的手為空手，而且積木 a a 的頂上是空的。的頂上是空的。 stack( stack(a,ba,b) )：把積木：把積木a a堆放在積木堆放在積木b b上。動作之前要求機械手必須已抓住積木上。動作之前要求機械手必須已抓住積木a a，而且，而且積木積木b b頂上必須是空的。頂上必須是

54、空的。 pickup(a) pickup(a)：從桌面上拾起積木：從桌面上拾起積木a a，并抓住它不放。在動作之前要求機械手為空手，并抓住它不放。在動作之前要求機械手為空手，而且積木而且積木a a頂上沒有任何東西。頂上沒有任何東西。 putdown(a) putdown(a)：把積木：把積木a a放置到桌面上。要求動作之前機械手已抓住積木放置到桌面上。要求動作之前機械手已抓住積木a a。五 幾種機器人規(guī)劃的方法 5.1 5.1 積木世界的機器人問題積木世界的機器人問題 舉例：積木世界由一些有標記的立方形積木，互相堆迭在一起構成；舉例：積木世界由一些有標記的立方形積木，互相堆迭在一起構成；機器人

55、有個可移動的機械手，它可以抓起積木塊并移動積木從一處至另一機器人有個可移動的機械手，它可以抓起積木塊并移動積木從一處至另一處。處。 提問：請同學就積木世界的機器人問題應用謂詞公式的合取描述此提問：請同學就積木世界的機器人問題應用謂詞公式的合取描述此目標為：目標為： ON(BON(B，C)ON(AC)ON(A，B)B)。初始狀態(tài)的描述。初始狀態(tài)的描述: :圖圖1 1 積木世界的機器人問題積木世界的機器人問題五 幾種機器人規(guī)劃的方法 5.1 5.1 積木世界的機器人問題積木世界的機器人問題 F F規(guī)則求解規(guī)劃序列規(guī)則求解規(guī)劃序列 采用采用 F F 規(guī)則表示機器人的動作，這是一個叫做規(guī)則表示機器人的

56、動作，這是一個叫做 STRIPS STRIPS 規(guī)劃系統(tǒng)的規(guī)劃系統(tǒng)的規(guī)則，它由規(guī)則，它由 3 3 部分組成。部分組成。 1.1.先決條件。為了使先決條件。為了使 F F 規(guī)則能夠應用到狀態(tài)描述中去。規(guī)則能夠應用到狀態(tài)描述中去。 2.2.一個叫做刪除表的謂詞。當一條規(guī)則被應用于某個狀態(tài)描述或數(shù)一個叫做刪除表的謂詞。當一條規(guī)則被應用于某個狀態(tài)描述或數(shù)據(jù)庫時，就從該數(shù)據(jù)庫刪去刪除表的內容。據(jù)庫時，就從該數(shù)據(jù)庫刪去刪除表的內容。 3.3.叫做添加表。當把某條規(guī)則應用于某數(shù)據(jù)庫時，就把該添加表的叫做添加表。當把某條規(guī)則應用于某數(shù)據(jù)庫時，就把該添加表的內容添進該數(shù)據(jù)庫。內容添進該數(shù)據(jù)庫。20092009年

57、年1212月月2525日報道，加拿大日報道，加拿大發(fā)明家宗黎（發(fā)明家宗黎（LeLe TrungTrung）是一名）是一名科學天才，他創(chuàng)造的機器人女科學天才，他創(chuàng)造的機器人女友友AikoAiko約約2020多歲，具有魔鬼身多歲，具有魔鬼身材，不但能記下宗黎的嗜好，材，不但能記下宗黎的嗜好，更是數(shù)學高手，也可處理會計更是數(shù)學高手，也可處理會計事務或做一些簡單家事。事務或做一些簡單家事。五 幾種機器人規(guī)劃的方法 5.1 5.1 積木世界的機器人問題積木世界的機器人問題 對于堆積木的例子中對于堆積木的例子中 move move 這個動作可以表示如下：這個動作可以表示如下： move(x,y,z)mov

58、e(x,y,z)：把物體：把物體 x x 從物體從物體 y y 上面移到物體上面移到物體 z z 上上面面 先決條件：先決條件： CLEAR(x), CLEAR(z)CLEAR(x), CLEAR(z)，ON(x,y)ON(x,y) 刪除表：刪除表： ON(x,y)ON(x,y)，CLEAR(z)CLEAR(z) 添加表：添加表： ON(x,z)ON(x,z)，CLEAR(y) CLEAR(y) 圖圖2 2 表示表示 move move 動作的搜索樹動作的搜索樹五 幾種機器人規(guī)劃的方法 5.1 5.1 積木世界的機器人問題積木世界的機器人問題 下面更具體地考慮圖下面更具體地考慮圖2 2中所示的

59、例子，機器人的中所示的例子，機器人的 4 4 個動作個動作( (或操作符或操作符) )可用可用 STRIPS STRIPS 形式表示如下：形式表示如下： (1) stack(X,Y)(1) stack(X,Y) 先決條件和刪除表：先決條件和刪除表：HOLDING(X)CLEAR(Y)HOLDING(X)CLEAR(Y) 添加表：添加表：HANDEMPTYHANDEMPTY，ON(XON(X，Y)Y) (2) (2) unstackunstack(X,Y)(X,Y) 先決條件：先決條件：HANDEMPTYON(XHANDEMPTYON(X，Y)CLEAR(X)Y)CLEAR(X) 刪除表：刪除表

60、：ON(XON(X，Y)Y)，HANDEMPTYHANDEMPTY 添加表：添加表：HOLDING(X)HOLDING(X)，CLEAR(Y)CLEAR(Y)五 幾種機器人規(guī)劃的方法5.1 5.1 積木世界的機器人問題積木世界的機器人問題 (3) pickup(X) (3) pickup(X) 先決條件：先決條件：ONTABLE(X)CLEAR(X)HANDEMPTY ONTABLE(X)CLEAR(X)HANDEMPTY 刪除表：刪除表：ONTABLE(X)HANDENPTYONTABLE(X)HANDENPTY 添加表：添加表：HOLDING(X)HOLDING(X) (4) putdow