圖規劃在路徑規劃中的應用

林爾敏，張逢春蔡莉莎（.海南軟件職業技術學院，海南瓊海，57400；.海口市高級技工學校，海南海口，5700）

?

圖規劃在路徑規劃中的應用

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

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

關鍵詞：圖規劃；路徑規劃

the application of graph planning in path plannng

0　引言

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

1　圖規劃算法的研究

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

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

圖1　機器人運輸問題

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

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

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

1.1 圖的擴展

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

1.2解的提取

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

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

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

選法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”支持。這次選擇的這三個動作不相沖突，所以我們可以在此選擇上執行目標集合創建步，得到次目標集合

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

繼續用以上方法搜索直至出現初始狀態搜索結束，得出有效規劃解：

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

時間步2為“move M N”

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

2　基于圖規劃的路徑規劃系統的設計

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

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

3　小結

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

參考文獻

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

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

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

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

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

圖2　機器人運輸規劃圖

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年海南軟件職業技術學院科學研究項目（Hr201602）