[發明專利]一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法

在審

• 申請號: 202010590622.X
• 申請日: 2020-06-24
• 公開（公告）號: CN111857133A
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 詹偉
• 申請（專利權）人: 湖南格蘭博智能科技有限責任公司
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 北京眾合誠成知識產權代理有限公司 11246
• 代理人: 王萌

1.一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于，所述方法包括如下步驟：

步驟1：當機器人周圍區域都被清掃后，或機器人意外碰撞到阻礙物時，搜索全局最近的一個未清掃點；

步驟2：采用的BFS算法是基于雙向鏈表來實現搜索未清掃區域，并輸出到達未清掃區路徑；

步驟3：使用刪除多余節點的方法對路徑進行優化處理，輸出最短路徑；

步驟4：根據輸出的最短路徑，把最短路徑轉換為行動表輸出，控制掃地機器人到達未清掃點清掃。

2.根據權利要求1所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：所述步驟2的具體過程為：

步驟2.1：由初始點坐標生成初始節點，作為雙向鏈表中的首節點；

步驟2.2：由首節點作為父節點生成子節點，并且按順序逐次驗證每個節點在已建地圖的屬性，如果存在地圖柵格的屬性為未清掃的子節點，則退出循環，返回該節點作為行動輸出點，如果不存在未清掃的子節點時，進入下一步；

步驟2.3：由首節點的四個子節點依次生成相應的新的子節點，并且依次判斷新結點在柵格地圖的屬性，如此循環下去，直到存在地圖柵格的屬性為未清掃的子節點退出循環，并且返回該節點和該節點所有的父節點作為行動輸出點，其中，父節點不包括首節點。

3.根據權利要求2所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：所述步驟2.2中，獲取子節點的方法為，

步驟2.2.1：驗證父節點所在柵格是否存在障礙物，如果是則退出循環，該父節點的子節點為空；

步驟2.2.2：父節點所在柵格不存在障礙物，以父節點為中心，從父節點上、左、下、右四個方向創建個子節點；

步驟2.2.3：設置父節點1的坐標為(x，y)，則父節點1的四個子節點的坐標為(x_上，y_上)，(x_左，y_左)，(x_下，y_下)和(x_右，y_右)；

步驟2.2.4：檢查每個子節點的可到達性，若存在可到的子節點，同時在雙向鏈表中反向查詢后不存在重復節點，則將該點坐標以及父節點作為參數創建節點。

4.根據權利要求3所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：所述步驟2.2.3中的四個子節點的坐標表示為：

(x_上，y_上)＝(x+d，y)

(x_左，y_左)＝(x，y+d)

(x_下，y_下)＝(x-d，y)

(x_下，y_下)＝(x，y-d)。

5.根據權利要求1所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：所述步驟3中對路徑優化的具體過程為：

步驟3.1：在步驟2中輸出的路徑中，如果某節點和其不相鄰后面的節點路徑中沒有障礙物，則在最終的行動路徑點集合中刪除其中間點。

6.根據權利要求5所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：刪除其中間點的具體過程為：

步驟3.1.1：設定i＝1，j＝步驟2中輸出的路徑途徑的點數+1，i為路徑中途徑的第i個點，j為路徑中途徑的第j個點；

步驟3.1.2：然后判斷i是否大于等于j，如果不大于或者等于時，判斷第i個點與第j個點之間是否存在障礙物，如果存在時，j--，如果不存在時，刪除第i個點和第j個點之間的點，進入步驟3.1.4；

步驟3.1.3：判斷i+1是否大于或者等于j，如果不大于等于時，返回步驟3.1.1，如果大于或者等于時，進入下一步；

步驟3.1.4：i++，同時j＝路徑途徑的點數數+2，返回步驟3.1.2。

7.根據權利要求6所述的一種用于掃地機器人尋找未清掃區域的寬度優先搜索算法，其特征在于：所述步驟3.1.2中判斷第i個點與第j個點之間是否存在障礙物的具體過程為：首先求解出兩節點之間的直線距離，隨后以單個柵格尺寸為長度劃分區域段，判斷每個區域段是否有障礙物覆蓋，若有則說明兩節點之間有障礙物；若沒有則說明兩節點之間沒有障礙物。