本文選題：清潔機器人 + 邊緣膨脹�。� 參考：《南京郵電大學》2017年碩士論文

【摘要】：智能清潔機器人是目前比較受歡迎的服務型機器人,它融合了機器人、傳感器和人工智能等技術。路徑規(guī)劃是智能清潔機器人的關鍵技術之一,其好壞是評價智能清潔機器人優(yōu)劣的重要指標。全局路徑規(guī)劃要求清潔機器人,以最小的代價(如路徑最短、時間最少、能耗最低等)規(guī)劃覆蓋全局且不與障礙物發(fā)生碰撞的最優(yōu)或較優(yōu)路徑。針對目前智能清潔機器人路徑規(guī)劃存在的低覆蓋率,高重復率,整體遍歷效率不高的問題,本文研究了已知環(huán)境清掃任務下的環(huán)境模型及分區(qū)方法,給出了提高矩形分區(qū)遍歷效率及區(qū)域銜接路徑效率的解決方法和優(yōu)化模型。主要工作如下:首先將工作環(huán)境用柵格法進行建模,針對柵格中不規(guī)則障礙物容易使算法陷入局部最優(yōu)及機器人陷入死角等問題,用柵格單元作為膨脹算子對不規(guī)則障礙物的邊緣進行膨脹處理,使不規(guī)則障礙物邊緣占據整個柵格單元,將不規(guī)則障礙物矩形化,便于下一步的矩形分區(qū),提高機器人的全局路徑規(guī)劃效率。針對傳統(tǒng)的矩形分區(qū)法分區(qū)之后,分區(qū)內結構不夠簡化的問題,本文運用改進的矩形分區(qū)算法,進行分解分區(qū),分區(qū)內則為自由柵格,這樣便于機器人在分區(qū)內的遍歷路徑規(guī)劃。為了提高矩形分區(qū)遍歷效率,提出了進化算法的解決方法及其優(yōu)化模型。針對傳統(tǒng)遺傳算法在解決此類問題時收斂速度慢和優(yōu)化結果不滿足節(jié)點相鄰的問題,初始化種群后用鄰接表對相鄰節(jié)點進行相鄰性判斷,搜索結果中相鄰節(jié)點為相鄰矩形分區(qū)。新的解決方法和傳統(tǒng)的深度優(yōu)先和廣度優(yōu)先搜索方法相比,能減少對分區(qū)的重復遍歷;相比于一般解決這類問題的蟻群算法,減少了迭代次數,縮短了收斂時間,且能搜索到滿足優(yōu)化條件的遍歷順序。針對相鄰分區(qū)間為不規(guī)則障礙物的區(qū)域銜接路徑規(guī)劃,結合傳感器對不規(guī)則障礙物沿邊清掃,使膨脹區(qū)域也能被覆蓋清掃,提高整體清掃覆蓋率。為了降低規(guī)則障礙物間的區(qū)域銜接路徑的重復率,對傳統(tǒng)A*算法估值函數進行改進。首先給出矩形分區(qū)內往返式遍歷起點、方向、終點的規(guī)則,對無障礙物矩形分區(qū)內運用往返式仿人工清掃模式。引入曼哈頓距離和對角線距離的組合,在傳統(tǒng)A*算法基礎上改進了啟發(fā)式函數,并在估值函數中引入轉角代價,有效降低了區(qū)域銜接路徑重復率。最后運用RobotBASIC進行綜合實驗仿真,實驗結果表明本文提出的方法使清潔機器人能夠找到全覆蓋、低重復率、高效地遍歷清潔路徑。
[Abstract]:Intelligent cleaning robot is a popular service robot, which combines robot, sensor and artificial intelligence technology. Path planning is one of the key technologies of intelligent cleaning robot, which is an important index to evaluate the advantages and disadvantages of intelligent cleaning robot. Global path planning requires a clean robot to plan the optimal or optimal path that covers the whole world and does not collide with obstacles at the minimum cost (such as the shortest path, the least time, the lowest energy consumption, etc.). Aiming at the problems of low coverage, high repetition rate and low overall traversal efficiency in path planning of intelligent cleaning robot, this paper studies the environment model and partition method under known environmental cleaning task. The solution and optimization model for improving the efficiency of rectangular partition traversal and regional convergence path are presented. The main work is as follows: firstly, the working environment is modeled by grid method, aiming at the problem that irregular obstacles in grid make the algorithm fall into local optimum and robot fall into dead angle, etc. The edge of irregular obstacle is expanded by using grid element as expansion operator, so that the edge of irregular obstacle occupies the whole grid element, and the irregular obstacle is rectangular, which is convenient for the next rectangular partition. The global path planning efficiency of robot is improved. In order to solve the problem that the structure of the partition is not simplified enough after the traditional rectangular partition method, this paper uses the improved rectangular partition algorithm to decompose the partition, and the free grid is used in the partition. In this way, it is convenient for robot to traverse path planning in the partition. In order to improve the efficiency of rectangular partition traversal, an evolutionary algorithm and its optimization model are proposed. In view of the slow convergence speed of traditional genetic algorithm in solving this kind of problem and the problem that the optimization results do not satisfy the problem of adjacent nodes, the adjacent nodes are judged by the adjacent table after the population initialization, and the adjacent nodes in the search results are adjacent rectangular partitions. Compared with the traditional depth first and breadth first search methods, the new method can reduce the repeated traversal of the partition, reduce the number of iterations and shorten the convergence time compared with the general ant colony algorithm. And the traversal order satisfying the optimization condition can be found. According to the path planning of the adjacent regions which are irregular obstacles, combined with the sensor to sweep the irregular obstacles, the expansion area can also be covered and the overall cleaning coverage can be improved. In order to reduce the repetition rate of regional convergence paths between regular obstacles, the estimation function of the traditional A * algorithm is improved. First, the rules of starting point, direction and end point of round-trip traversal in rectangular partition are given, and the round-trip artificial cleaning mode is applied to rectangular partition without obstacles. By introducing the combination of Manhattan distance and diagonal distance, the heuristic function is improved based on the traditional A * algorithm, and the corner cost is introduced into the estimation function, which effectively reduces the repetition rate of the regional convergence path. Finally, RobotBASIC is used to carry out comprehensive experimental simulation. The experimental results show that the proposed method can find full coverage, low repetition rate and efficiently traverse clean path.
【學位授予單位】：南京郵電大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP242

【參考文獻】

相關期刊論文 前10條

1 李成進;王芳;;智能移動機器人導航控制技術綜述[J];導航定位與授時;2016年05期

2 朱哲;;自移動清潔機器人專利技術分支的發(fā)展趨勢[J];科技經濟導刊;2016年24期

3 徐雪松;楊勝杰;陳榮元;;復雜環(huán)境移動群機器人最優(yōu)路徑規(guī)劃方法[J];電子測量與儀器學報;2016年02期

4 劉春;馬穎;;遺傳算法和神經網絡結合的PSD非線性校正[J];電子測量與儀器學報;2015年08期

5 呂金秋;游曉明;劉升;;機器人全局路徑規(guī)劃的混合蟻群系統(tǒng)算法[J];計算機工程與應用;2016年11期

6 馬飛;楊v瀄~;顧青;孟宇;;基于改進A*算法的地下無人鏟運機導航路徑規(guī)劃[J];農業(yè)機械學報;2015年07期

7 占偉偉;王偉;陳能成;王超;;一種利用改進A*算法的無人機航跡規(guī)劃[J];武漢大學學報(信息科學版);2015年03期

8 張屹;劉錚;胡方軍;詹騰;丁昌鵬;;基于元胞遺傳算法的移動機器人路徑規(guī)劃[J];機床與液壓;2014年09期

9 陳鵬;李彩虹;;移動機器人混合式全遍歷覆蓋路徑規(guī)劃算法[J];山東理工大學學報(自然科學版);2013年05期

10 張殿富;劉福;;基于人工勢場法的路徑規(guī)劃方法研究及展望[J];計算機工程與科學;2013年06期

相關碩士學位論文 前5條

1 郭良;自主移動機器人完全遍歷和多任務分配的研究[D];東北大學;2010年

2 邢敏;清潔機器人系統(tǒng)開發(fā)及路徑規(guī)劃研究[D];北京交通大學;2007年

3 周學益;清潔機器人全區(qū)域覆蓋路徑算法與避障控制研究[D];重慶大學;2007年

4 劉奎;移動機器人完全遍歷系統(tǒng)研究[D];東南大學;2006年

5 張永華;基于灰值腐蝕—膨脹形態(tài)學和中值二值化的車牌定位及DSP硬件實現[D];浙江工業(yè)大學;2004年

，

本文編號：1915778