智能扫地机器人的路径规划方法外文翻译资料

Proceedings of 2019 IEEE

International Conference on Mechatronics and Automation August 4 - 7, Tianjin, China

A Path Planning Strategy for Intelligent Sweeping Robots

Hongmei Zhang 1, Wei Hong 2, Mingjie Chen 1

1. College of Automation, Harbin Engineering University, Harbin 150001
2. School of Control Science and Engineering, Dalian University of Technology, Dalian 116024

E-mail: zhang_hm@yeah.net

Abstract - The path planning strategy and optimized algorithm of intelligent sweeping robot are researched in this paper. In order to achieve traversal cleaning indoor environment, a raster map is established firstly, and the inward spiral traversal method is designed for the sweeper. Then a scheme of the shortest path for out of the dead zone is proposed based on A* algorithm, due to the inward spiral traversal may fall into dead zone. Finally, the global traversal problem is considered, and the traversal cleaning task is realized by simulation. The results show that the proposed scheme and algorithm are effective.

Index Terms - sweeping robot, path planning, traversal cleaning, inward spiral, A* algorithm

• 1. INTRODUCTION

Since the worlds first fully automatic sweeper 'trilobite' was product by Electrolux in 2001, sweeping robot [1,2] or called intelligent sweeper developed rapidly. In the follow, it is called sweeper for short. Up to now, the research direction has aimed to the multi-sensor fusion, positioning and navigation, path planning and other intelligent technologies. Among these technologies, path planning [2-5] is a very important research direction, by which, the sweeper builds the environment model, then carries out global and local path planning based on its own positioning, so as to complete the cleaning work. The path planning strategy for sweepers includes map construction, path traversal, path optimization and escape dead zone, etc. The path planning problem of sweeper is different from that of general sweeper or vehicle. A reasonable and efficient path planning strategy needs to traverse the whole sweeping area as possible as to repeat the sweeping route, and automatically avoid obstacles meanwhile. In this paper, some strategies of path planning to realize the above requirements will be studied for sweepers.

The content and structure of this paper are arranged as follows. Firstly, the basic theory of path planning are introduced which involved the traversing method of sweepers indoors and A* algorithm, the optimization algorithm will be used to optimize the path of the sweepers. Secondly, a inward spiral path planning strategy is designed to realize ergodic

The main idea of the forward and backward method is that the sweeper starts from a certain corner and goes straight until it meets an obstacle or wall, and then turns around to continue straight in the opposite direction. Repeat like this until it reaches the last corner of the room.

Take counter-clockwise direction for example, the idea of the inward spiral method is: first of all, the sweeper take a certain corner as the starting point (For example, the point can be set to the sweepers charging place), then go straight along the wall by counter-clockwise. At the same time, it detects by external sensors if there is the area for cleaning. If yes, then the sweeper turn right and go straight for cleaning. In the process of going straight, if an obstacle or an area has been cleared is detected in front, turn left.

For the two traversal modes, the forma is easy to realize, but when there are many obstacles, it is easy to fall into dead zone or realize environment traversal with high repetition rate. So this strategy is applicable to the environment with a large area and few obstacles, such as outdoor environment, indoor stadium, basketball court, etc. For the latter mode, when the environment is open and there are few obstacles, the path traversal repetition rate is low and the efficiency is high. When there are more obstacles, the sweeper may fall into the dead zone also, but it is easy to get out by jumping operation through programming. Therefore, in this paper, the inward spiral strategy is used for the ergodic strategy of sweeper.

B. Path Optimization Algorithm: A* Algorithm

In 1968, P.E.Hart [6] proposed A* algorithm, which combined the advantages of Dijkstra algorithm [8] and the best priority search algorithm. In heuristic searching algorithm, A* algorithm has the least search states and has many advantages in static map for path searching. Compared with Dijkstra algorithm, it has certain rapidity. At the same time, it overcomes the disadvantage of the optimal priority searching in complex environment map. For this reason, A* algorithm was taken as the path optimization algorithm of the sweeper in this paper.

The idea of A* algorithm is constructing a cost function for the path and minimizing it:

cleaning. Thirdly, aiming at the dead zone problem, a escape

f (n)  g(n)  h(n)

(1)

algorithm is proposed based on A* algorithm [6,7]. At last, some conclusions are made.

• 1. THEORETICAL BASIS OF PATH PLANNING

1. Traversal Modes of Sweepers for Path Planning

There are two main traversal modes for path planning: forward and backward planning and inward spiral planning.

Where, f (n) is the cost function of current node n, which

represents the estimated value of cost sum of the path that have walked and the path to the destination node will be taken, g(n) represents the estimated value of the shorted path from initial node s lt;

剩余内容已隐藏，支付完成后下载完整资料

智能扫地机器人的路径规划方法

摘要

本文研究了智能扫地机器人的路径规划策略和优化算法。为了实现室内环境的横向清洁，首先建立了栅格地图，并设计了清扫器的向内螺旋横向清洁方法。然后基于A*算法，提出了一种走出死角的最短路径方案，由于向内的螺旋，横穿可能会进入死角。最后，考虑了全局遍历问题，并给出了算法通过仿真实现了横向清扫任务。结果表明，本文提出的方案和算法是有效的。

关键词 扫地机器人；路径规划；横向清扫；向内螺旋；A*算法

1 简介

自从世界上第一个智能扫地机器人' 三叶虫' 被Electrolux 在2001 年生产出来，扫地机器人[1,2] 或称为智能扫地机器人发展迅速。在下文中，它简称为扫地机。到目前为止，研究方向旨在实现多传感器融合，定位和导航，路径规划和其他智能技术。在这些技术中，路径规划[2-5] 是一个非常重要的研究方向，扫地机建立环境模型，然后根据自己的定位进行全局和局部路径规划，以完成清洁工作。扫地机的路径规划策略包括地图构建，路径遍历，路径优化和走出死区等。扫地机的路径规划问题与一般扫描器或车辆的路径规划问题不同。合理有效的路径规划策略需要尽可能遍历整个扫描区域以重复扫描路线，同时自动避开障碍物。在本文中，将研究一些路径规划策略以实现上述要求。本文的内容和结构安排如下。第一，介绍了路径规划的基本理论，包括室内扫地机的路径规划方法和A*算法，并用该优化算法对清扫车的路径进行优化。第二，设计了一种向内螺旋的路径规划策略，实现遍历清扫。第三，针对死区问题，基于A*算法[6,7]提出了一种逃逸算法。最后得出了一些结论。

2 路径规划的理论基础

A . 用于路径规划的单向内螺旋清扫器横向模式

用于路径规划的扫地机的遍历模式路径规划有两种主要的遍历模式：前向和后向规划以及内向螺旋规划。前向和后向方法的主要思想是扫描器从某个角落开始直接前进，直到遇到障碍物或墙壁，然后转身向相反方向直接前进。重复这样，直到它到达房间的最后一个角落。以逆时针方向为例，向内螺旋方法的思想是：首先，扫描器以某个角为起点（例如，该点可以设置为扫描器的充电位置），然后沿逆时针方向沿着墙壁。同时，如果存在清洁区域，它将由外部传感器检测。如果是，则扫描器向右转并直接进行清洁。在直行的过程中，如果在前面检测到障碍物或区域已被清除，则向左转。对于两种遍历模式，前者更易于实现，但是当存在许多障碍时，很容易陷入死区或实现具有高重复率的环境遍历。因此，该策略适用于面积较大且障碍较少的环境，例如室外环境，室内体育场，篮球场等。对于后一种模式，当环境打开且障碍物很少时，路径遍历重复率低且效率高。当存在更多障碍时，扫描器也可能落入死区，但是通过编程跳跃操作很容易退出。因此，在本文中，内向螺旋策略用于sweeper 的遍历策略。

B . 路径优化算法：A * 算法

1968 年，p.e.Hart [6] 提出了A* 算法，结合了Dijkstra 算法[8] 和最佳优先级搜索算法的优点。( b )。与Dijkstra 算法相比，它具有一定的快速度。同时，它克服了复杂环境图中最佳优先级搜索的缺点。因此，本文将A * 算法作为扫地机的路径优化算法。A*算法的思想是为路径构造一个代价函数并最小化它：f（n）=g（n） h（n）（1）。其中，f（n）是当前节点n的代价函数，它表示已走的路径和将要走到目的地节点的路径的代价和的估计值，g（n）表示从初始节点s到当前节点n的短路径的估计值，h（n）是从节点n到目的地的最短路径的代价函数。假设它们的实际值为g*（n）和h*（n）。一般来说，g（n）le; g*（n），h（n）le; h*（n）。

A*算法考虑了从源节点s到当前节点n的最短路径成本，以及从节点n到目标节点的最短路径成本。该算法的具体实现是动态更新开放列表中所有节点的估计值以获得最优路径，指针连接所有节点以形成最终路径。该算法的具体过程如下：（1）创建开放列表以存储要扩展的地图节点及其估计值。创建一个紧密列表以存储扩展节点，并初始化为空。（2）将源节点S 放入打开列表中。（3）如果打开列表为空，则不存在有效路径。（4）根据其估计值对打开列表中的节点进行排序，顶部为小节点，底部为大节点。（5）删除打开列表中的第一个节点n 并将其放在关闭列表中。确定节点n 是否是目标节点，如果是这样，则表示已找到最短路径并退出搜索。（6）如果节点n 不是目标节点，则可以计算其所有子节点的估计值，表示为（inf）。如果in 中的子节点不在上述两个列表中，则将其放置在打开列表中，并且将同时生成指向父节点n 的指针。如果in 中的子节点已存储在打开列表中，则将通过父节点n 的子节点的估计值与先前存储在打开列表中的节点的估计值进行比较。如果in 中的子节点已经在近距离列表中，则已对其进行扩展，然后跳过该点。（7）返回步骤3 并重复直到找到最短路径或终止而没有解决方案。

3 扫地机向内螺旋路径规划方法

A . 基于向内螺旋清扫方式的路径规划方案

当扫描器通过向内螺旋样式执行清洁任务时，其状态可以分为五种：向上，向下，向左，向右和死区。扫描器以向内螺旋方式的清洁过程可以简洁地描述如下：（1）首先，扫描器需要构建环境栅格图以确定其自身的姿势。为方便起见，网格单元的大小通常设置为与扫描器直径相同的正方形。栅格图初始化如下：障碍物占据的网格值设置为0 ，扫描器通过的网格被视为清理，其值设置为2 ，网格未被障碍物占据而未通过将其设置为1 ，将进行清理。（2）然后，扫描器按照向内螺旋方式的策略进行清洁工作。如果未找到死区，则继续向内螺旋清洁。如果找到死区，则将从内到外逐层搜索要清理的最近光栅。清洁任务完成，退出清洁。（3）如果找到最接近清洁的栅格，则使用A * 算法搜索从死区到要清洁的最近栅格的最短路径，然后沿最短路径分离死区，返回步骤2 继续清洁。

B . 单向内螺旋清洁过程

扫描器以向内螺旋方式穿越的过程可描述如下：（1）首先，构造22 times; 18 的网格图，如图1所示.假设当前位置坐标为（m ，n ），则扫描器的前网格为（m 1 ，n ），左右网格分别为（m ，n-1 ）和。扫描器的初始位置，即光栅图的左下角是（2,2 ）。（2）然后扫描器以向内螺旋模式遍历。以扫描器的当前位置和运行方向为参考，当要清理的网格右侧出现时，它将右转，例如，从右线运行状态到下侧。当障碍物出现在前侧或网格被扫描时，例如，从右运行状态向上转动。（3）一旦扫描器移动网格，它就会检测到是否存在要在其周围清洁的网格。如果存在，则返回步骤2 以继续清洁。如果不存在，它将落入死区并继续进行步骤4 . （4）如果扫描器落入死区，它将检测全局栅格图中是否仍有要清理的点，网格值为。如果不是，则意味着清洁已完成并退出。如果是这样，请沿原始路径退一步并返回步骤。图1 是通过向内螺旋方式穿越的第一个死区之前的路径的示意图，其中黑色网格是障碍物和墙壁，白色网格是要清洁的区域。为了方便地显示，已清理的网格与线连接，未连接的网格是死点。当环境中存在单个障碍物时，扫描器可以通过撤退从死区取出最短路径，并且清洁的重复率不会很高，因此清洁工作可以快速完成。但是，当环境中没有更多的障碍时，如图1所示，死区点可能远离要清理的最近的点。在这种情况下，如果清扫机按照原来的遍历路径一步一步地退出死区，则清扫重复率高，清扫效率低。在现实生活中，室内往往存在许多障碍。这种逃离死区的方法是不可行的，应该采取更有效的措施。

图一，多障碍内向螺旋

4 基于A*算法的扫地机最短走出死角路径规划

从上面可以看出，在遍历过程中，扫描器可能落入死区，并且如果扫描器采取撤退方式以传统上逃逸死区，则会降低清洁效率。下面设计了一种逃避死区的新规划方法。

A .搜索要清理的最近点

在使用A*算法搜索出死区外的最短路径之前，必须事先知道起始点和结束点，其中起始点是当前死区点，通过逐层向外延伸的方式搜索得到结束点。具体流程如下：（1）根据搜索层的数量，可以将要搜索的栅格确定为形状为' 嘴' 的方形环，分别对应于顶部，底部，左侧和右侧方向。( 2 )如果某个方向的搜索范围超过地图边界，则将对应于该方向的标记变量设置为1 ，否则为0 . （3）判断对应于四个方向的符号值是否全部为。如果是这样，则表示扫描完成，跳出当前搜索子循环，结束。( 4 )如果是这样，则上侧已到达地图边界。跳过搜索并转到步骤3 . 如果不是，则根据步骤2中确定的范围搜索要从'嘴' 上方从左到右清理的网格。如果建立，则记下当前网格并退出搜索。（5）如果未建立，则根据步骤4 中的规则在底侧，左侧和右侧执行搜索。如果未找到要清理的网格，则扩展搜索层数h = h 1 并返回步骤2. b . 基于a * 算法的路径查找方法构建初始映射，如图2 所示。

B .基于A*算法的路径搜索方法

接着，最短路径找到以下步骤.初始地图的构建如图2所示。其中，点A是死区点，点B是要跳出的点，它们之间有一堵墙。然后按照以下步骤寻找最短路径：（1） 将起始网格A放入开放列表，该列表用于存储要搜索的网格的信息，即F、G和H值的大小。（2） 搜索栅格A的相邻栅格，未被障碍物占用的栅格将添加到打开列表中，并将栅格A设置为相邻栅格的父栅格，以生成后续路径。在图3中，指针指向的网格是父网格。（3） 将网格A移出“打开”列表，然后移到“关闭”列表中，关闭列表用于保存检索到的和未考虑的网格。（4） 在“打开”列表中，选择估计值最低的网格作为下一次搜索的新父网格。

图2 清扫初始地图

这里，估计值F = G H 。其中，G 是从起始网格a 移动到任何其他网格的距离成本。( b )。为了便于计算，采用了曼哈顿方法。也就是说，通过当前网格的网格数量通过横向和纵向运动到达目标网格，然后将其乘以10 以获得。由于在h 的计算中忽略了占据网格的障碍物的影响，因此它只是对剩余距离成本的估计，而不是实际值（仅在生成路径后才能知道），因此它也称为启发式方法。通过上述计算，可以方便地获得网格a 的相邻网格的f ，g 和h 的值，并在左上角，左下角和下角进行标记网格的右角。然后按顺序执行以下步骤：（1）继续搜索，具有最低f 值的网格将从打开列表中取出并放置在关闭列表中。检索相邻网格并将不在打开列表中的无障碍网格放入其中。当前网格是新添加的父网格。（2）如果当前网格的相邻网格之一已经在开放列表中并且不是新添加的网格，则检测通过相邻网格的路径是否更好。如果是这样，请将网格的父级设置为当前网格并重新计算其f 和g 值。( 3 ) 计算完成后，四个网格的所有f 值都大于当前父网格，因此不进行更改。基于此，选择要处理的下一个网格。重复上述步骤直到到达目标网格。结果如图3 所示。

图3路径生成过程

C.基于A*算法的最佳路径搜索图4 A*算法C的最短路径搜索

以上介绍了基于A*算法的栅格地图路径搜索方法的原理和步骤。接下来，将通过仿真验证基于A*算法的路径发现理论。图4是初始栅格地图任意两栅格间最短路径的模拟结果。

图4 A*算法的最短路径搜索

D.全局遍历策略

上面已经讨论了全局遍历原理的详细流程和每个子步骤的实现。接下来，结合内螺旋遍历模式和基于A*算法的逃离死区方法，给出了全局路径规划方案的设计思想和仿真结果。

首先，初始化清理的标志变量以控制向内螺旋遍历的主循环。可以通过在要清理的最近点中搜索四个方向来控制标志变量。当扫描未完成时，主循环中的遍历扫描将继续。否则，通过控制标志变量来结束主循环。

其次，在主回路内，switch 语句控制扫描器的五个运动状态，即向内螺旋遍历的四个运动方向和跳出死区的状态。因此，每次主回路运行时，清扫器要么在当前运动状态下向前移动一步，要么转弯，要么跳出死区。重复此操作，直到光栅地图上要清除的区域完全穿过。

以一个障碍物的情况为例，模拟全局穿越，结果如图5所示。从上图可以看出，清扫器在清扫过程中两次落入死区并脱离死区，最终完成了全球清扫。为了避免路径重叠，给出了两次从死区中分离出来的路径规划图（图中圈出了两个位置），最后给出了全局遍历路径规划图。通过用另一个模拟改变栅格图中的障碍物分布，可以获得相同的结果。

图5清扫器的全局遍历示意图

5 结论

设计了基于向内螺旋遍历和a * 算法的智能扫描器路径规划策略。首先，通过向内螺旋方式执行遍历清理，然后当遇到死区时，将使用a * 算法从中找到最佳路径。仿真结果表明，本文提出的路径规划及其在智能扫描器实用最优路径策略设计中的应用。

致谢

本文由“哈尔滨工程大学自动化学院学科建设综合试点特别基金”资助。笔者非常感谢基金提供者和匿名审稿人的建设性意见，这些意见大大改善了本文。

参考文献

[1] 赵浩，刘玉梅，卞志刚.“中国的发展现状和前景。”《信息与计算机》（理论版）

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[591657]，资料为PDF文档或Word文档，PDF文档可免费转换为Word