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

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

?

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

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

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

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

the application of graph planning in path plannng

0　引言

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

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

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

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

圖1　機器人運輸問題

任務描述：利用機器人將兩個包裹從M地運往N地。初始狀態(tài)機器人和包裹A，包裹B在M地。目標狀態(tài)機器人和包裹A，包裹B在N地。

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

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

1.1 圖的擴展

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

1.2解的提取

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

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

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

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

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

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

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

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

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

時間步1為“pickup A M”和“pickup B M”

時間步2為“move M N”

時間步3為“putdown A N”和“putdown B N”

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

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

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

3　小結

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

參考文獻

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

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

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

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

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

圖2　機器人運輸規(guī)劃圖

2015年海南省高等學校科學研究項目（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

基金項目：2016年海南軟件職業(yè)技術學院科學研究項目（Hr201602）