[發明專利]一種機器人迷宮搜索方法

有效

• 申請號: 201310062309.9
• 申請日: 2013-02-27
• 公開（公告）號: CN103092207A
• 公開（公告）日: 2013-05-08
• 發明（設計）人: 郭長生;裴蕾;龔濤
• 申請（專利權）人: 東華大學
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 上海泰能知識產權代理事務所 31233
• 代理人: 宋纓;孫健

技術領域

本發明屬人工智能技術領域，特別是涉及一種機器人迷宮搜索方法。

背景技術

將智能機器人應用于探索迷宮和未知環境的研究已經非常普及，縱觀已有迷宮搜索算法，絕大部分的做法是當機器人有支路進行選擇時，會根據擬定的路徑選擇算法，選擇其中一條進行繼續探索，直至搜索到終點。而此類算法有個弊端，沒有充分利用機器人已經搜索到的信息對機器人的搜索路徑進行優化。當有支路進行選擇時，則根據擬定的路徑選擇算法，選擇其中一條進行繼續探索，而這條路徑是否可達終點，事先并未根據已有的數據進行分析判斷，只能通過實際搜索來得知。而且也僅僅局限于對已探索到的信息進行選擇，并未對這些信息進行有效擴展，這些都必將帶來一些不必要的搜索，影響做出判斷的準確性，降低搜索效率。

發明內容

本發明所要解決的技術問題是提供一種機器人迷宮搜索方法，從剔除無效搜索路徑和增加有效信息兩方面入手，以高速的微控制器運算速度替代相對低速的機器人機械運行速度，從而提高迷宮搜索效率。

本發明解決其技術問題所采用的技術方案是：提供一種機器人迷宮搜索方法，包括下列步驟：

（1）對已知和機器人探索出的信息進行擴展，當搜索到迷宮格中一格的墻面信息后，利用此墻面信息，對其四周各格的墻面部分或全部信息進行更新。即根據當前迷宮格左方向是否有路，得出其左方的迷宮格右方向是否有路。同理可根據當前迷宮格的下、右、上方向是否有路，得出其下方迷宮格的上方向、右方迷宮格的左方向和上方迷宮格的下方向是否有路。這樣，雖然這四格并未搜索過，卻已得到部分甚至全部墻面信息，為后期的判斷和路徑選擇提供更多有效數據；

（2）當有支路可供選擇時，對路徑選擇算法選擇出的支路利用“洪水推演法”進行預推演，剔除不可行路徑，所述“洪水推演法”即根據路徑選擇法則選擇好最優支路后，在機器人行進前，根據已知信息、機器人探索出和擴展出的信息順著這條支路預推演，若這條支路能夠推演到終點，則這條支路判斷為可行進；若推演不到終點，則判斷為不可行進，并將推演到的所有不可行進迷宮格標記為死路、剔出搜索范圍，再根據路徑選擇法則選擇出的下一優先支路進行預推演，直至找出可行進的支路為止。

所述的步驟（2）中還包括：對路徑選擇算法選擇出的路徑進行一次過濾，排除那些不可達路徑，減小搜索范圍；排除的僅僅是那些沒有可能到達終點的路徑，對其余有可能到達的路徑均予以保留。

所述的步驟（2）中“洪水推演法”在路徑選擇算法選擇好支路之后，根據數組記錄的隔墻信息，順著這條支路模擬“流水”，并將機器人當前位置標記為最高點，即“洪水”流不到的地方，防止其“逆流”；若這條“流水”路徑能夠“流淌”到終點，則這條路判斷為可行進；若“流淌”不到終點，則判斷為不可行進，并將“洪水”所“流過”的所有格子標記為死路、剔出搜索范圍，再根據路徑選擇算法選擇下一優先支路，并進行推演，直至找出可行進支路為止。

所述的步驟（2）中所述的推演的實現方法為基于等高圖法尋找最優路徑的方法進行，根據數組中記錄的信息作從支路點到終點的等高圖，從中找出一條能夠到達終點的路徑；如果已完成所有坐標的等高值更新，依然沒能夠更新終點的等高值，則判斷為此支路不可達；推演過程必須向“前”推演，等高值初始化時，將當前機器人位置的等高值置為最小值0，起點或支路點的等高值置為1，其余點的初始等高值均置為0xff，即可保證向“前”推演。

有益效果

本發明首先對已知和機器人探索出的信息進行擴展，從而得出更多有用信息，不僅能為本發明提出的“洪水推演法”提供有效數據，也能夠為機器人在選擇最優路徑等提供更多數據，從而做出更加準確的選擇或判斷。所提出的“洪水推演法”能夠識別出迷宮中的死路，從而減小搜索范圍，以微控制器高速的運算速度替代機器人緩慢的“奔跑”速度，

有效提高搜索效率。

附圖說明

圖1為本發明數據擴展示意圖。

圖2為本發明路徑選擇算法流程圖。

圖3為本發明機器人搜索路徑示意圖。

具體實施方式

下面結合具體實施例，進一步闡述本發明。應理解，這些實施例僅用于說明本發明而不用于限制本發明的范圍。此外應理解，在閱讀了本發明講授的內容之后，本領域技術人員可以對本發明作各種改動或修改，這些等價形式同樣落于本申請所附權利要求書所限定的范圍。