己知环境下智能清洁机器人路径规划研究

发布时间：2018-05-20 18:34

本文选题：清洁机器人 + 边缘膨胀　；参考：《南京邮电大学》2017年硕士论文

【摘要】：智能清洁机器人是目前比较受欢迎的服务型机器人,它融合了机器人、传感器和人工智能等技术。路径规划是智能清洁机器人的关键技术之一,其好坏是评价智能清洁机器人优劣的重要指标。全局路径规划要求清洁机器人,以最小的代价(如路径最短、时间最少、能耗最低等)规划覆盖全局且不与障碍物发生碰撞的最优或较优路径。针对目前智能清洁机器人路径规划存在的低覆盖率,高重复率,整体遍历效率不高的问题,本文研究了已知环境清扫任务下的环境模型及分区方法,给出了提高矩形分区遍历效率及区域衔接路径效率的解决方法和优化模型。主要工作如下:首先将工作环境用栅格法进行建模,针对栅格中不规则障碍物容易使算法陷入局部最优及机器人陷入死角等问题,用栅格单元作为膨胀算子对不规则障碍物的边缘进行膨胀处理,使不规则障碍物边缘占据整个栅格单元,将不规则障碍物矩形化,便于下一步的矩形分区,提高机器人的全局路径规划效率。针对传统的矩形分区法分区之后,分区内结构不够简化的问题,本文运用改进的矩形分区算法,进行分解分区,分区内则为自由栅格,这样便于机器人在分区内的遍历路径规划。为了提高矩形分区遍历效率,提出了进化算法的解决方法及其优化模型。针对传统遗传算法在解决此类问题时收敛速度慢和优化结果不满足节点相邻的问题,初始化种群后用邻接表对相邻节点进行相邻性判断,搜索结果中相邻节点为相邻矩形分区。新的解决方法和传统的深度优先和广度优先搜索方法相比,能减少对分区的重复遍历;相比于一般解决这类问题的蚁群算法,减少了迭代次数,缩短了收敛时间,且能搜索到满足优化条件的遍历顺序。针对相邻分区间为不规则障碍物的区域衔接路径规划,结合传感器对不规则障碍物沿边清扫,使膨胀区域也能被覆盖清扫,提高整体清扫覆盖率。为了降低规则障碍物间的区域衔接路径的重复率,对传统A*算法估值函数进行改进。首先给出矩形分区内往返式遍历起点、方向、终点的规则,对无障碍物矩形分区内运用往返式仿人工清扫模式。引入曼哈顿距离和对角线距离的组合,在传统A*算法基础上改进了启发式函数,并在估值函数中引入转角代价,有效降低了区域衔接路径重复率。最后运用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

【参考文献】