林爾敏，張逢春蔡莉莎（.海南軟件職業(yè)技術(shù)學(xué)院，海南瓊海，57400；.?？谑懈呒壖脊W(xué)校，海南?？冢?700）

?

圖規(guī)劃在路徑規(guī)劃中的應(yīng)用

林爾敏1，張逢春2蔡莉莎1
（1.海南軟件職業(yè)技術(shù)學(xué)院，海南瓊海，571400；2.海口市高級技工學(xué)校，海南海口，570102）

摘要：隨著科學(xué)技術(shù)的不斷發(fā)展，機(jī)器人研究成為當(dāng)今的熱門話題，人們趨向于用機(jī)器人替代人類去完成一些危險(xiǎn)的工作。而路徑規(guī)劃是機(jī)器人研究的難點(diǎn)之一。本文以機(jī)器人的運(yùn)輸問題為例，介紹了圖規(guī)劃的算法，以及如何利用圖規(guī)劃技術(shù)對路徑規(guī)劃問題進(jìn)行求解。

關(guān)鍵詞：圖規(guī)劃；路徑規(guī)劃

the application of graph planning in path plannng

0　引言

隨著科技的發(fā)展，智能能規(guī)劃已經(jīng)成為當(dāng)今的熱門學(xué)科，基于規(guī)劃圖的規(guī)劃算法—圖規(guī)劃（Graphplan）深受規(guī)劃界的廣泛關(guān)注，像Blackbox、FF等著名的規(guī)劃器都采用了圖規(guī)劃的算法。使用圖規(guī)劃可以將問題空間規(guī)劃化，能夠減少重復(fù)搜索，縮短時(shí)間。利用圖規(guī)劃的技術(shù)來解決規(guī)劃問題，就可以將尋跡問題轉(zhuǎn)變?yōu)橛幸?guī)整的狀態(tài)空間的寬度優(yōu)先搜索算法，很好的縮短了規(guī)劃時(shí)間。本文將圖規(guī)劃技術(shù)應(yīng)用在機(jī)器人的路徑規(guī)劃系統(tǒng)中，以求達(dá)到縮短規(guī)劃時(shí)間的目的。

1　圖規(guī)劃算法的研究

圖規(guī)劃的主要思想是利用圖的方法來解決規(guī)劃問題。將規(guī)劃問題轉(zhuǎn)化成規(guī)劃圖，這個(gè)規(guī)劃圖在時(shí)間上滿足規(guī)劃存在的條件，即滿足同層命題節(jié)點(diǎn)，動(dòng)作節(jié)點(diǎn)之間的互斥關(guān)系。然后進(jìn)行規(guī)劃解的提取，對已經(jīng)生成的規(guī)劃圖實(shí)施一個(gè)向后的鏈?zhǔn)剿阉?，試圖尋得所求的規(guī)劃解，如果無法找到所需要的解，我們將對前面生成的規(guī)劃圖進(jìn)行進(jìn)一步的擴(kuò)展，再次循環(huán)執(zhí)行圖擴(kuò)展與規(guī)劃解的提取，直到找到所需要的解或是無解返回。

本文以機(jī)器人運(yùn)輸問題為例如圖1所示介紹基于圖規(guī)劃路徑規(guī)劃算法。

圖1　機(jī)器人運(yùn)輸問題

任務(wù)描述：利用機(jī)器人將兩個(gè)包裹從M地運(yùn)往N地。初始狀態(tài)機(jī)器人和包裹A，包裹B在M地。目標(biāo)狀態(tài)機(jī)器人和包裹A，包裹B在N地。

圖規(guī)劃問題的問題描述：采用STRIPS問題域描述方法。

圖規(guī)劃的算法表示：圖規(guī)劃主要由兩個(gè)階段組成：圖擴(kuò)展與規(guī)劃解的提取。

1.1 圖的擴(kuò)展

機(jī)器人運(yùn)輸完整規(guī)劃圖如圖2所示，第一列由運(yùn)輸問題的初始狀態(tài)組成，成為命題列。第二列為動(dòng)作列，若在操作集合中能夠找到它的前提在上一步命題列中的操作，則表示這個(gè)操作可以實(shí)例化，實(shí)例化后得到一個(gè)動(dòng)作節(jié)點(diǎn)，這些動(dòng)作節(jié)點(diǎn)組成動(dòng)作列。第三列為命題列，由上一步的所有動(dòng)作例添加效果后構(gòu)成，其中也包括no-op動(dòng)作，命題列生成后要對該命題列進(jìn)行搜索看是否存在目標(biāo)命題，若出現(xiàn)目標(biāo)命題并且任意兩個(gè)命題都不互斥，則規(guī)劃圖的擴(kuò)展結(jié)束。若無則繼續(xù)擴(kuò)展規(guī)劃圖。將相連的命題列與動(dòng)作列用實(shí)現(xiàn)和虛線連接起來，其中實(shí)線表示添加效果，用虛線表示刪除效果。

1.2解的提取

如圖2所示時(shí)間步4的命題列中機(jī)器人運(yùn)輸問題的目標(biāo)狀態(tài)全部出現(xiàn)，并且任意兩個(gè)命題都不互斥。規(guī)劃圖的擴(kuò)展結(jié)束，進(jìn)行有效解的搜索。對于“at A N”，我們選擇在時(shí)間步3動(dòng)作列中支持它的動(dòng)作“pickup A N”；同樣對于“at B N”，我們選擇在時(shí)間步3動(dòng)作列中支持它的動(dòng)作“putdown B N”。 “putdown A N”與“putdown B N”不相沖突。

接著執(zhí)行目標(biāo)集合創(chuàng)建的步：在時(shí)間步3的命題列中將“putdown A N”的前提“in A P”、“at P N”與“putdown B N”的前提放在一個(gè)集合中即得到次目標(biāo)集合：｛“in A P”、“in B P”、“atP N”｝. （1.1）

對上面得到的次目標(biāo)集合繼續(xù)搜索支持動(dòng)作。

選法1：從圖2中可以看到對于次目標(biāo)“in A P”，可以有兩種不同的選擇，如果選擇支持動(dòng)作no-op支持；同樣對于次目標(biāo)“in B P”和“in P N”，都選擇支持動(dòng)作no-op支持；這三個(gè)選定的動(dòng)作互不沖突，得到次目標(biāo)集合：

｛“in A P”、“in B P”、“at P N”｝（1.2）

對比式1.1與式1.2中，這兩個(gè)次目標(biāo)集是相同的，但是他們又處于不同的時(shí)間步，所以接下來在尋找支持工作時(shí)就會(huì)碰到不同的情況。支持“in A P”的動(dòng)作“pickup A M”與支持“in B P”的動(dòng)作“pickup B M”不沖突，但是支持“at P N”的動(dòng)作“move M N”卻與“pickup A M”、“pickup B M”沖突，所以此選擇無解退回。

選法2：對次次目標(biāo)“in A P”，可以有兩種不同的選擇，如果選擇支持動(dòng)作no-op支持；對于次目標(biāo)“in B P”，在他的兩個(gè)兩種不同的選擇中選擇支持動(dòng)作no-op支持；這次對于次目標(biāo)“in P N”，在他的兩個(gè)兩種不同的選擇中選擇支持動(dòng)作“move M N”支持。這次選擇的這三個(gè)動(dòng)作不相沖突，所以我們可以在此選擇上執(zhí)行目標(biāo)集合創(chuàng)建步，得到次目標(biāo)集合

｛“in A P”、“in B P”、“at P N”、“fuel P”｝（1.3）

繼續(xù)用以上方法搜索直至出現(xiàn)初始狀態(tài)搜索結(jié)束，得出有效規(guī)劃解：

時(shí)間步1為“pickup A M”和“pickup B M”

時(shí)間步2為“move M N”

時(shí)間步3為“putdown A N”和“putdown B N”

2　基于圖規(guī)劃的路徑規(guī)劃系統(tǒng)的設(shè)計(jì)

基于圖規(guī)劃的智能小車路徑規(guī)劃系統(tǒng)主要由電機(jī)驅(qū)動(dòng)、尋跡、避障、單片機(jī)、火源傳感器、風(fēng)扇、電源七個(gè)模塊組成。

本系統(tǒng)的主要設(shè)計(jì)思路：分為硬件方面的設(shè)計(jì)與軟件方面的設(shè)計(jì)。硬件方面：利用紅外對地圖上的路面情況進(jìn)行探測，確定前走的區(qū)域，利用火源傳感器檢測火源信號(hào)。然后將檢測到的兩種信號(hào)進(jìn)行處理，送給單片機(jī)控制模塊進(jìn)行運(yùn)算，再將輸出的信號(hào)提供給驅(qū)動(dòng)電機(jī)模塊以驅(qū)動(dòng)電機(jī)轉(zhuǎn)動(dòng)，達(dá)到控制小車運(yùn)動(dòng)的目的。軟件方面：將路徑規(guī)劃問題抽象出來，利用STRIPS規(guī)則將規(guī)劃問題轉(zhuǎn)化為規(guī)劃圖的形式，然后在規(guī)劃圖中實(shí)施一個(gè)由后向前的鏈?zhǔn)剿阉魈崛∫?guī)劃解，最后將得到的規(guī)劃解傳送給STC89C52，從而控制小車能夠按照求得的規(guī)劃解行走以達(dá)到提高路徑搜索的目的。

3　小結(jié)

測試環(huán)境：設(shè)計(jì)行駛地圖，在地圖上任意設(shè)置障礙物和火源的位置，讓小車從起始點(diǎn)出發(fā)，避開障礙物到達(dá)火源位置。經(jīng)過實(shí)驗(yàn)證明利用圖規(guī)劃系統(tǒng)進(jìn)行的路徑規(guī)劃速度明顯高于傳統(tǒng)的基于傳感器路徑規(guī)劃的速度，由此可見基于圖規(guī)劃系統(tǒng)可以很好的提高路徑搜索的效率。

參考文獻(xiàn)

［1］ 李和香，董少英.圖規(guī)劃在排課系統(tǒng)中的應(yīng)用［J］. 自動(dòng)化與信息工程，2007，02：26-28.

［2］谷文祥，殷明治，徐麗等.智能規(guī)劃與規(guī)劃識(shí)別［M］.北京：科學(xué)出版社，2010.

［3］劉吉穎，方思行. AI規(guī)劃的回顧與展望［J］. 中山大學(xué)學(xué)報(bào)論叢，2000，05：78-81.

［4］ 李天際，姜云飛. 圖規(guī)劃及其擴(kuò)展的分析和研究［J］. 計(jì)算機(jī)科學(xué)，2001，07：69-73.

［5］姜云飛［J］.譯.自動(dòng)規(guī)劃：理論和實(shí)踐［M］.北京：清華大學(xué)出版社，2008.

圖2　機(jī)器人運(yùn)輸規(guī)劃圖

2015年海南省高等學(xué)?？茖W(xué)研究項(xiàng)目（Hnky2015-76）

Lin Ermin1，Zhang Fengchun2，Cai Lisha1
（1.Hainan Software Profession Institute QionghaiHainan 571400China；2.Haikou advanced technical school Haikou 570102China）

Abstract：With the development of science and technology，Robotics research is a hot topic，people tend to use robots to do some dangerous work instead of people.The path planning is one of the difficulties of robotics research，in this paper，by the example of the robot's transportation problem，introduced the algorithm of Graphplan，and how to use the technology of Graphplan to solve the problem of Path planning.

Keywords：Graphplan；Path planning

基金項(xiàng)目：2016年海南軟件職業(yè)技術(shù)學(xué)院科學(xué)研究項(xiàng)目（Hr201602）