[發(fā)明專利]一種機(jī)器人迷宮搜索方法

有效

• 申請?zhí)枺?/td>: 201310062309.9
• 申請日: 2013-02-27
• 公開（公告）號: CN103092207A
• 公開（公告）日: 2013-05-08
• 發(fā)明（設(shè)計）人: 郭長生;裴蕾;龔濤
• 申請（專利權(quán)）人: 東華大學(xué)
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 上海泰能知識產(chǎn)權(quán)代理事務(wù)所 31233
• 代理人: 宋纓;孫健

1.一種機(jī)器人迷宮搜索方法，其特征在于，包括下列步驟：

（1）對已知和機(jī)器人探索出的信息進(jìn)行擴(kuò)展，當(dāng)搜索到迷宮格中一格的墻面信息后，利用此墻面信息，對其四周各格的墻面部分或全部信息進(jìn)行更新，這樣，雖然這四格并未搜索過，卻已得到部分甚至全部墻面信息，為后期的判斷和路徑選擇提供更多有效數(shù)據(jù)；

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

2.根據(jù)權(quán)利要求1所述的一種機(jī)器人迷宮搜索方法，其特征在于，所述的步驟（2）中還包括：對路徑選擇算法選擇出的路徑進(jìn)行一次過濾，排除那些不可達(dá)路徑，減小搜索范圍；排除的僅僅是那些沒有可能到達(dá)終點的路徑，對其余有可能到達(dá)的路徑均予以保留。

3.根據(jù)權(quán)利要求1所述的一種機(jī)器人迷宮搜索方法，其特征在于，所述的步驟（2）中“洪水推演法”在路徑選擇算法選擇好支路之后，根據(jù)數(shù)組記錄的隔墻信息，順著這條支路模擬“流水”，并將機(jī)器人當(dāng)前位置標(biāo)記為最高點，即“洪水”流不到的地方，防止其“逆流”；若這條“流水”路徑能夠“流淌”到終點，則這條路判斷為可行進(jìn)；若“流淌”不到終點，則判斷為不可行進(jìn)，并將“洪水”所“流過”的所有格子標(biāo)記為死路、剔出搜索范圍，再根據(jù)路徑選擇算法選擇下一優(yōu)先支路，并進(jìn)行推演，直至找出可行進(jìn)支路為止。

4.根據(jù)權(quán)利要求1所述的一種機(jī)器人迷宮搜索方法，其特征在于，所述的步驟（2）中的推演的實現(xiàn)方法為基于等高圖法尋找最優(yōu)路徑的方法進(jìn)行，根據(jù)數(shù)組中記錄的信息作從支路點到終點的等高圖，從中找出一條能夠到達(dá)終點的路徑；如果已完成所有坐標(biāo)的等高值更新，依然沒能夠更新終點的等高值，則判斷為此支路不可達(dá)；推演過程必須向“前”推演，等高值初始化時，將當(dāng)前機(jī)器人位置的等高值置為最小值0，起點或支路點的等高值置為1，其余點的初始等高值均置為0xff，即可保證向“前”推演。