[發明專利]移動機器人及其基于自適應遺傳算法的路徑規劃方法

有效

• 申請號: 202011486397.1
• 申請日: 2020-12-16
• 公開（公告）號: CN112686429B
• 公開（公告）日: 2022-07-29
• 發明（設計）人: 郝琨;趙家樂;趙璐;于凱丞
• 申請（專利權）人: 天津城建大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12;G01C21/20
• 代理公司: 石家莊知住優創知識產權代理事務所(普通合伙) 13131
• 代理人: 林艷艷

一種基于自適應遺傳算法的移動機器人路徑規劃方法，其包括地圖建模方法和地圖預處理過程；采用自適應遺傳算法生成優質的可行路徑；規劃路徑碰撞檢測算法；采用優化算子對優質的可行路徑進行第二次優化等步驟。本發明提供的基于自適應遺傳算法的移動機器人路徑規劃方法是將自適應遺傳算法和移動機器人結合起來，通過地圖建模方法和地圖預處理過程生成一個包含障礙物的柵格地圖，利用自適應遺傳算法在該柵格地圖上生成優質的可行路徑，然后借助碰撞檢測算法提出優化算子，采用優化算子對優質的可行路徑進行第二次優化。本方法能夠顯著提升規劃路徑的質量，同時由于對標準遺傳算法的種群初始化過程進行了改進，算法的程序運行時間也大幅度減少。

技術領域

本發明屬于移動機器人路徑規劃領域，特別是涉及一種基于自適應遺傳算法的移動機器人路徑規劃方法及移動機器人。

背景技術

隨著現代社會的不斷發展，移動機器人在各行業已經得到廣泛的應用。家庭、工廠、醫院等公共場所對移動機器人的需求正在急劇增加。移動機器人也已經引起了人們極大的興趣，因為它們能夠極大的提高生產力并且給人們提供高效便捷的服務。移動機器人除了具備強大的實用性外，還具備極高的市場商業價值。據估計，移動清潔機器人的市場價值將會在2023年達到43.4億美元，其中移動掃地板機器人將會占據龐大的市場份額。由于社會的快速發展，人們對生產生活的方式發生了根本性的轉變，對移動機器人的要求也從原來的單一化、機械化向智能化、人性化的需求轉變。其中，路徑規劃技術是實現移動機器人智能化的關鍵技術之一，也是移動機器人領域的研究熱點。路徑規劃是指移動機器人按照某一性能指標搜索一條從起始狀態到目標狀態的最優或次最優的無碰撞路徑。

過去幾十年，路徑規劃技術得到了很好的發展。基本形成了以Floyd算法、Dijkstra算法、人工勢場法、A*算法為代表的傳統搜索算法。以神經網絡算法、免疫克隆算法、遺傳算法、蟻群算法為代表的智能進化算法。傳統搜索算法適用于小規模少障礙物地圖。對于大規模多障礙物地圖，傳統搜索算法會十分吃力，不但搜索時間長而且還容易陷入局部最優解。與傳統搜索算法相比，智能進化算法既適用于小規模少障礙物地圖，也適用于大規模多障礙物地圖。智能進化算法也在一定程度上擁有打破局部最優解的能力。然而，智能進化算法也存在著程序運行時間長，收斂迭代次數多，收斂路徑質量低等缺陷。

發明內容

為了解決上述問題，本發明的目的在于提供一種基于自適應遺傳算法的移動機器人路徑規劃方法，采用柵格法建立地圖模型并進行預處理得到柵格地圖，運用自適應遺傳算法，得到一條優質可行路徑，大幅縮減算法的程序運行時間，提出了一種新的碰撞檢測算法，用以檢測規劃路徑是否與障礙物柵格發生碰撞；提出了優化算子，進一步改善規劃路徑的質量，克服了現有的智能進化算法存在的程序運行時間長、收斂迭代次數多、收斂路徑質量低等缺陷。

為了達到上述目的，本發明是采用下述技術方案實現的：

一種基于自適應遺傳算法的移動機器人路徑規劃方法，包括按順序進行的下列步驟：

步驟一：進行地圖建模和地圖預處理；采用柵格法建立地圖模型，將移動機器人所處的二維工作空間劃分為若干個大小相等的柵格，然后對每一個柵格進行編號，將可行區域標記為白色，將不可行區域標記為黑色，形成柵格模型；對所述柵格模型進行預處理，將移動機器人等效為質量點同時對障礙物做膨脹化處理，若障礙物為不規則障礙物，則將障礙物所處的柵格全部標記為黑色；若一個白色柵格的八個方向全部為黑色柵格，則此白色柵格也標記為黑色柵格，生成柵格地圖；

步驟二：在步驟一生成的柵格地圖上，運用自適應遺傳算法，得到一條優質可行路徑；

步驟三：設計碰撞檢測算法，檢測步驟二中生成的路徑是否與障礙物發生碰撞，若一條路徑由若干個路徑點所組成，檢測該路徑中所有相鄰路徑點的連線是否與障礙物柵格發生碰撞，如果所有相鄰路徑點連線均不與障礙物柵格發生碰撞，則認為該路徑不與障礙物柵格發生碰撞；若有任何一個相鄰路徑點連線與障礙物柵格發生了碰撞，則認為該路徑與障礙物柵格發生了碰撞；