機(jī)器人任務(wù)規(guī)劃

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

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

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

4、前，計(jì)算該程序劃這一詞指的是在執(zhí)行一個(gè)問(wèn)題求解程序中的任何一步之前，計(jì)算該程序幾步的過(guò)程。一個(gè)規(guī)劃是一個(gè)行動(dòng)過(guò)程的描述。缺乏規(guī)劃可能導(dǎo)致不適最幾步的過(guò)程。一個(gè)規(guī)劃是一個(gè)行動(dòng)過(guò)程的描述。缺乏規(guī)劃可能導(dǎo)致不適最佳的問(wèn)題求解。佳的問(wèn)題求解。20142014年年4 4月機(jī)器人足球世界杯在德國(guó)開(kāi)哨月機(jī)器人足球世界杯在德國(guó)開(kāi)哨一 機(jī)器人規(guī)劃綜述 1.3 1.3 規(guī)劃問(wèn)題分解途徑：規(guī)劃問(wèn)題分解途徑： 把某些比較復(fù)雜的問(wèn)題分解為一些比較小的子問(wèn)題，有兩條能夠?qū)嵃涯承┍容^復(fù)雜的問(wèn)題分解為一些比較小的子問(wèn)題，有兩條能夠?qū)崿F(xiàn)這種分解的重要途徑?，F(xiàn)這種分解的重要途徑。 第一條重要途徑是，當(dāng)從一個(gè)問(wèn)題狀態(tài)移動(dòng)到下一個(gè)狀

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

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

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

8、我們超越低地隨著我們超越低地球軌道，這些機(jī)器人對(duì)美國(guó)宇航局的未來(lái)至關(guān)重球軌道，這些機(jī)器人對(duì)美國(guó)宇航局的未來(lái)至關(guān)重要。要?！币?機(jī)器人規(guī)劃綜述 一個(gè)服務(wù)機(jī)器人在接受主人一個(gè)服務(wù)機(jī)器人在接受主人“給我倒一杯開(kāi)水給我倒一杯開(kāi)水”的命令之的命令之后后, ,機(jī)器人如何完成這一任務(wù)機(jī)器人如何完成這一任務(wù)? ?一 機(jī)器人規(guī)劃綜述取取 一一 個(gè)個(gè) 杯杯 子子找找 到到 水水 壺壺打打 開(kāi)開(kāi) 壺壺 塞塞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、斜把把 水水 壺壺 豎豎 直直 把把 水水 壺壺 放放 回回 原原 處處把把 水水 倒倒 入入 杯杯 中中 把把 水水 送送 給給 主主 人人給給 我我 倒倒 杯杯 水水任務(wù)規(guī)劃任務(wù)規(guī)劃運(yùn)動(dòng)規(guī)劃運(yùn)動(dòng)規(guī)劃軌跡規(guī)劃軌跡規(guī)劃總體任務(wù)總體任務(wù)子任務(wù)子任務(wù)動(dòng)作順序動(dòng)作順序關(guān)節(jié)運(yùn)動(dòng)關(guān)節(jié)運(yùn)動(dòng)規(guī)律規(guī)律一 機(jī)器人規(guī)劃綜述一 機(jī)器人規(guī)劃綜述規(guī)規(guī)劃劃控控制制機(jī)機(jī)器器人人本本體體要求的要求的任務(wù)任務(wù)期望的期望的運(yùn)動(dòng)和運(yùn)動(dòng)和力力控制作用控制作用實(shí)際的實(shí)際的運(yùn)動(dòng)和運(yùn)動(dòng)和力力人人機(jī)機(jī)接接口口一 機(jī)器人規(guī)劃綜述 1.4 1.4 規(guī)劃域的預(yù)測(cè)規(guī)劃域的預(yù)測(cè) 對(duì)真實(shí)世界的任何方面進(jìn)行完全預(yù)測(cè)幾乎是做不到的。因此，必須對(duì)真實(shí)世界的任

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、動(dòng)規(guī)劃方法 概率路標(biāo)算法（概率路標(biāo)算法（probabilistic roadmap methodprobabilistic roadmap method）算法的基本思想）算法的基本思想是用一個(gè)隨機(jī)的網(wǎng)絡(luò)來(lái)表示機(jī)器人系統(tǒng)運(yùn)行的自由空間是用一個(gè)隨機(jī)的網(wǎng)絡(luò)來(lái)表示機(jī)器人系統(tǒng)運(yùn)行的自由空間Cfree Cfree ，這一隨機(jī)，這一隨機(jī)網(wǎng)絡(luò)即是為機(jī)器人系統(tǒng)所建立的概率地圖。網(wǎng)絡(luò)即是為機(jī)器人系統(tǒng)所建立的概率地圖。 該算法可通過(guò)該算法可通過(guò)2 2個(gè)階段來(lái)完成：離線(xiàn)學(xué)習(xí)階段個(gè)階段來(lái)完成：離線(xiàn)學(xué)習(xí)階段(1earning phase)(1earning phase)和在和在線(xiàn)查詢(xún)階段線(xiàn)查詢(xún)階段(query phase

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57、年1212月月2525日?qǐng)?bào)道，加拿大日?qǐng)?bào)道，加拿大發(fā)明家宗黎（發(fā)明家宗黎（LeLe TrungTrung）是一名）是一名科學(xué)天才，他創(chuàng)造的機(jī)器人女科學(xué)天才，他創(chuàng)造的機(jī)器人女友友AikoAiko約約2020多歲，具有魔鬼身多歲，具有魔鬼身材，不但能記下宗黎的嗜好，材，不但能記下宗黎的嗜好，更是數(shù)學(xué)高手，也可處理會(huì)計(jì)更是數(shù)學(xué)高手，也可處理會(huì)計(jì)事務(wù)或做一些簡(jiǎn)單家事。事務(wù)或做一些簡(jiǎn)單家事。五 幾種機(jī)器人規(guī)劃的方法 5.1 5.1 積木世界的機(jī)器人問(wèn)題積木世界的機(jī)器人問(wèn)題 對(duì)于堆積木的例子中對(duì)于堆積木的例子中 move move 這個(gè)動(dòng)作可以表示如下：這個(gè)動(dòng)作可以表示如下： 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 動(dòng)作的搜索樹(shù)動(dòng)作的搜索樹(shù)五 幾種機(jī)器人規(guī)劃的方法 5.1 5.1 積木世界的機(jī)器人問(wèn)題積木世界的機(jī)器人問(wèn)題 下面更具體地考慮圖下面更具體地考慮圖2 2中所示的

59、例子，機(jī)器人的中所示的例子，機(jī)器人的 4 4 個(gè)動(dòng)作個(gè)動(dòng)作( (或操作符或操作符) )可用可用 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)五 幾種機(jī)器人規(guī)劃的方法5.1 5.1 積木世界的機(jī)器人問(wèn)題積木世界的機(jī)器人問(wèn)題 (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