Complete coverage path planning of mobile robots for humanitarian demining
Marija Dakulovic[1], Ivan Petrovic1
Dimensions
Prime Mover Prime Mover With Flail (Clearing arm pulled in) Prime Mover With Flail (Clearing arm extended)
Abstract—The paper presents a path planning algorithm for a non-circular shaped mobile robot to autonomously navigate in an unknown area for humanitarian demining. For that purpose the path planning problem comes down to planning a path from some starting location to a final location in an area so that the robot covers all the reachable positions in the area while following the planned path. Based on our previous complete coverage algorithm of known areas we have developed a complete coverage algorithm capable of operating in unknown areas with known border dimensions. The proposed algorithm uses occupancy grid map representation of the area. Every free cell represents a node in the graph being searched to find the complete coverage path. The proposed algorithm finds the complete coverage path in the graph accounting for the dimensions of the mobile robot, where non-circular shaped robots can be easily included. The algorithm is implemented under the ROS (robot operating system) and tested in the stage 3D simulator for mobile robots.
Index Terms — autonomous mobile robots, path planning, coverage path planning, exploration
- INTRODUCTION
The path planning problem of a mobile robot for humanitarian demining application comes down to planning a path from a start position to a final position in an area so that the robot inspects all the reachable positions (nodes in a graph) while following the planned path. The problem of finding the path that visits all nodes in a graph is called the complete coverage path planning [7]. Finding an optimal path that visits every node in a graph exactly once is NP-hard problem known as the traveling salesman problem. Therefore, approximate or even heuristic solutions are used for the complete coverage path planning task.
A common approach to complete coverage planning is decomposing the environment into subregions [6], selecting a sequence of those subregions, and then generating a path that covers each subregion in turn. Most methods assume convex polygonal environments and perform exact cell decomposition [5], [1], [11], which can be very time consuming in changing environments. Methods based on the approximate cell decomposition (i.e. grid maps) are less time consuming, but suppose that the mobile robot has the dimensions of exactly one cell within the grid map [4], [12].
Most complete coverage planning algorithms assume circular shaped mobile robot, and there is little work reported for complex non-circular shaped mobile robots. This paper presents a new complete coverage path planning algorithm for complex shaped mobile robot and is capable of operating in unknown areas of known border dimensions for the application of humanitarian demining. The algorithm is an extension of our previous complete coverage D* algorithm (CCD*) developed for circular shaped robots operating in known indoor environments with moving obstacles [2]. The proposed algorithm uses decomposition of the unknown area into squared cells of equal size and finds the complete coverage path that covers all reachable cells. The complete coverage path is integrated with the dynamic window obstacle avoidance algorithm [3] to produce smooth robot trajectory considering robots kinematic and dynamic constraints.
The rest of the paper is organized as follows. Section II describes robot and environment representation for the humanitarian demining. Section III presents the proposed complete coverage planning algorithm. Test results are given in Section IV and conclusion in Section V.
- ROBOT AND ENVIRONMENT REPRESENTATION A. The robot
In this paper, we assume usage of the humanitarian demining mobile robot MV-4 of DOK-ING company (Fig. 1), although developed algorithm is generally applicable to other robots. The dimensions of the prime mover together with the attached flail tool for activating mines are given in Table I (taken from www.dok-ing.hr). The simulation setup with
TABLE I
Technical data for the MV-4 mine clearance system.
(Length x Width x Height) mm 3005 x 1530 x 1470 mm 4455 x 2015 x 1470 mm
5145 x 2015 x 1470 mm
the robot model is shown in Fig. 2. The simulated robot has on-board laser range sensor with 360o field of view. The maximal range used for mapping of unknown obstacles are set to 8 m, although outdoor laser range sensors provides much higher ranges (e.g. 30 m). The limitation of only 8 m ranges data assure more reliable map update especially in an uneven terrains (detecting of the ground). The robot has differential drive, i.e., it can rotate in place, and can move in forward and backward direction.
Fig. 1. The MV-4 mine clearance system. Courtesy of DOK-ING company www.dok-ing.hr.
Fig. 2. The simulation setup in the Stage simulator - 3D view of the robot model and the part of the random environment.
B. The occupancy grid map
Two-dimensional (2D) occupancy grid maps are usually used to represent a continuous environment by an equally-spaced grid of discrete points [10]. The whole unknown area with known borders is divided into squared cells of equal size. Each cell contains occupancy information of the part of the environment that it covers, which is continuously updated as the robot detects obstacles within the corresponding cells.
The real shape of the robot represented in the grid map is shown in Fig. 3. It is usually assumed that the robot shape can be approximated by
剩余内容已隐藏，支付完成后下载完整资料
完全覆盖的的人道主义排雷移动机器人路径规划
Marija Dakulovic[1], Ivan Petrovic
原动机的原动力和连枷(拉动臂)原动机连枷(清算机构扩展)。
摘要：本文提出了一种非圆形状的移动机器人设计方法。这种方法是在未知领域自主导航的人道主义排雷的路径规划算法。为此目的的路径规划问题归结为规划路径从开始位置到最终位置的地方,这样机器人能覆盖所有在该地区可得到的规划的路径。基于我们之前了解的完全覆盖算法的已知领域,我们已经开发出一种能够完全覆盖在未知的领域与已知边界的维度的算法。该算法使用面积占用网格地图来表示。图中每一个自由单元代表一个被搜索找到完整的覆盖路径的节点。该算法可发现完全覆盖路径图中移动机器人的尺寸,非圆形状的机器人可以很容易地包括在内。这种的算法实现依靠S(机器人操作系统)和测试阶段的3 d模拟器为移动机器人提供帮助。
关键词:自主移动机器人路径规划,覆盖路径规划,探索
I．介绍
移动机器人人道主义排雷的路径规划问题的应用可以归结为规划在一个区域一条从起始位置到最终位置的路径规划问题,这样机器人检查所有可访问的位置(图中的节点),来计划好之后的道路。完全覆盖路径规划是访问所有节点的路径所发现的问题[7]。找到在一次运动中一条访问每个节点的最优路径称为货郎担问题，是一个比较难解决的问题。因此,近似甚至启发式的解决方案较为适合用于完成覆盖路径规划任务。
完全覆盖规划的一种常见方法是将环境分解为条件[6],选择序列的条件,然后生成一个路径覆盖每一个亚区。大多数假设方法突出多边形环境和执行精确单元分解[5],[1],[11],在s变化的环境中,可能非常耗时。基于近似单元分解的方法 (即网格地图)更耗费时间,但假设移动机器人的尺寸是跟一个单元内的网格地图相似[4],[12]。最完整的覆盖规划算法是使用圆形形状的移动机器人。没有工作报告的复杂形状的移动机器人并不是圆的。本文提出了一种对于复杂形状的移动机器人新的完全覆盖路径规划算法,能够在未知领域操作拥有人道主义排雷算法的应用程序的已知边界尺寸的机器人。该算法是我们为之前的完全覆盖的扩展D *算法(CCD)为圆形形状的机器人所开发在已知的室内环境与移动障碍的操作应用[2]。未知区域的算法是使用分解成平方单元的大小和发现完全覆盖路径覆盖所有可获得的单元。完全覆盖路径结合动态窗口避障算法来产生光滑的机器人轨迹，其中考虑了机器人的运动学和动力学的约束条件。
剩下的部分如下: 第三部分介绍提出了完全覆盖规划算法。在第四节给出了测试结果，第五部分是结论部分。
II．机器人和环境表示为A号机器
在本文中,我们使用的是人道主义排雷移动机器人是MV-4 DOK-ING公司的产品(图1),尽管发展算法通常也是适用于其他机器人。原型机的尺寸附连枷工具表一起给出(来自www.dok-ing.hr)。仿真设置：
技术数据MV-4扫雷系统
3005 x 1530 x 1470毫米
(长度x宽度x高度) 4455 x 2015 x 1470毫米
5145 x 2015 x 1470毫米
表1
图2所示的是机器人模型。模拟机器人车载激光测距传感器360度的视野。未知障碍的最大范围映射设置为8米,虽然室外激光测距传感器能提供更高的范围(例如30米)。但只有8米范围的限制数据能保证更可靠的地图更新，特别是在一个凹凸不平的地形(检测地面)。机器人可以旋转到位,也可以向前或向后的方向移动。
图2
图3
图2所表示的是仿真设置阶段模拟器- 3 d视图的机器人模型和随机环境的一部分。
B.占用的网格地图
二维(2 d)占用网格地图通常用来表示一个连续的环境被一条平行的网格分成离散点[10]。整个未知与已知的边界区域分为平方单元。每个单元包含环境一部分的入住率信息, 机器人它的表面相应的单元内检测到障碍是不断更新的。真正的机器人在网格地图的形状图3所示。通常认为,机器人在每个计划位置的坐标是近似的圆形状。为了避免机器人定位规划出现问题,在本文中,我们假定的真实形状机器人可以用两个圆来近似。一个圆覆盖机器人的车辆部分(原动力),和另一个圆覆盖排雷机器人的连枷工具。通过引入两个圆和避障模块的某些实施条件足以满足计划。图3的大圆(Ri)用于障碍扩大。机器人中心的位置被认为是原点。机器人的路径规划假设需要检查整个区域的工具而不是它的表面。此外,它假定访问节点在图3的近似平方形状。注意占用网格地图的机器人真正的形状。单元的大小eceii = 0.25 m的工具,跟真正的工具尺寸相比有点小。另一方面,在计划出路径后,节点访问要适当地确定,即要满足那些真实的机器人的形状。
图3
III．完整的覆盖计划
人道主义扫雷：
人道主义排雷完全覆盖规划算法实际上是一个原始完全覆盖的修改版本D *算法[2]。而原始CCD *算法是让有限的圆形形状的机器人在已知区域完美运行的路径规划的算法,它介绍了修改非圆形状的机器人在未知领域的路径规划算法。
CCD *算法的修改：
CCD *算法的修改,这使路径规划对于复杂的机器人的形状,包括第一次的覆盖路径规划工具的中心的计算更加简洁方便,即依靠节点中心的工具的平方形状(见图3),然后推导出机器人的位置。当机器人在开始位置即覆盖工具中的第一个节点的路径工具中心点时,和第一个节点覆盖机器人的路径开始节点重合。工具的中心点是失去位置的机器人的中心点。工具的CCD *算法叫做T和路径VT，对于它们的使用是必须的。接下来,可以通过执行某些坐标变换的路径点来虚拟化现实以决定机器人的中心。
当车载范围传感器检测到障碍物,相应单元就被占领。此外,机器人和被发现的障碍物之间将变得自由。之后,启动包含或删除的路的重新规划流程和特定地区的区域径。跟踪访问机器人在哪些单元完成完全覆盖路径,记录函数visitedR(n)= { 0,1 }和overlapped ^(n)= { 0,1 }。每次执行前访问完全覆盖路径的计算值的函数visitedR (n)和overlapped (n) 分别由新的visitedR(n)和overlapped ^(n)代替。新的规划路径是一道重新计算的过程。
B. 算法迭代的说明
首先,D *搜索执行[9]从开始节点计算g每个可及节点的成本值。覆盖工具中的第一个节点的路径工具的中心点,和第一个节点覆盖机器人的路径开始节点重合。这个工具的中心点与机器人的位置固定长度lT沿着x轴的机器人的局部坐标系(机器人的前进方向)移动。在路径规划步骤中,小方形状的部分(中心真正的形状)中的一部分是用于确定访问节点(见图3),而不是路径跟踪,所有的单元都由机器人的实际形状来确定。只将算法的第一步访问和重叠值确定为机器人完成的覆盖部分。在所有步骤完成后使用确定这些值的工具。覆盖工具中的下一个节点的路径选择候选节点利用相同的方式在使用原始的CCD *算法时对机器人的路径进行规划。候选节点定义为non-overlapped节点，可以和前面的节点覆盖工具以及路径扫描工具对连续4个方向的网格相对应。下一个节点是用一个最小的成本价值g产生的第一次迭代的例子覆盖路径来算出，如图4所示。
-24 -23 -22 -21 -20 -19 -18 -17 -16 -15 x [m]
图4
图4表示出了第一次迭代路径——分配覆盖和重叠节点来确定出的范围。
当确定了路径中的每个节点时,例如工具的第i个节点的路径,机器人的i - th节点的路径，要计算机器人的位置之间的位移和工具的位置。工具的路径转换向后lT沿长度之间的连接(i – 1)是在机器人的路径,i点工具的路径。如果连接线路的长度小于位移长度lT,然后第i个机器人的路径点重复使用先前(i - 1)点。通过这个过程机器人的路径平滑会变得更合适的路径跟踪模块。这个过程的一个例子是第三个迭代算法，如图5所示。
扫描迭代算法持续到周围没有候选节点时为止。在CCD *算法中,接下来的过程就是从最后一个节点执行另一个搜索工具的路径找到最接近non-visited节点。没有non-visited节点时,算法停止。
图5
测试结果
该算法是为了实现ROS(机器人操作系统和舞台模拟器www.ros.org)与MV4机器人模型II中所描述的部分。AMCL算法(自适应蒙特卡罗定位)是用于机器人定位。基于路径跟踪动态窗口算法,描述出在我们以前的工作中应该如何使用[8]某些适应性相符合机器人。机器人被允许在一些死锁场景中任意行动。这里会使用一个随机生成尺寸为50m x 50m地图的模拟图,见图2。仿真中使用的激光测距数据已经可以依靠完整的视野(360度)和仅限于8米范围内只应对障碍时依靠在附近的机器人来完成。机器人移动的时候,它在发现未知的障碍时会重新规划完全覆盖路径。
图6
图6显示了三个由于许多交错规划而产生的未知的区域。第一个(左边)是最初的规划。结束节点的工具的路径和机器人的路径分别由GT和GR指出。每个重新规划的步骤和路径方向是改变障碍检测路径的方法。由于编码器提示出未覆盖部分的路径跟踪的部分区域，这些部分被包含在新的完全覆盖路径来重新规划的下一步。然而, 由于复杂的机器人的形状和旋转当场某些障碍附近配置动态窗口算法是不容许的，所以一些单元很难访问。3图中绿色区域总时间访问花了80分钟,最后花了110分钟。机器人以平均135毫米/秒的速度运动。前进运动最大允许速度是500 mm / s和向后运动100 mm / s。最大方向速度仅限于100mm/ s。3图机器人试图访问单元边界附近的障碍,这在所有情况下是不成功的，因为机器人也需要旋转来达到未覆盖到的单元,没有计划在算法内。最后,机器人覆盖30712个单元总数(1919.5平方米)其中 30718个是可获得的单元,即只剩下6个单元未覆盖到。机器人的驱动轨迹的总长度是938.4米。
V．结论
本文介绍提出了一种新的人道主义排雷完全覆盖路径规划算法。实验表明,它可以有效地计划并确保机器人的路径连枷工具访问到所有可获得的区域(单元)以检查区域。该算法的测试结果令人满意。应用于环境中的算法可以填补未知领域的空白。一些单元一直未覆盖到是由于编码器路径跟踪还有些许不足。在我们未来的工作中，发达国家和额外的约束条件会将更好的路径跟踪算法纳入到规划中。算法最小化等路径方向变化的数量和计划也取决于对某些点附近的障碍的解决。
感谢
这项工作在一直支持科学、教育的体育克罗地亚共和国（批准号036-0363078-3018）帮助下完成,由欧盟第七框架计划285939号协议拨款。作者非常感谢DOK-ING公司提供排雷机器人技术数据。
引用
- H. Choset. Coverage of known spaces: the boustrophedon cellular decomposition. Autonomous Robots, 9(3):247-253, 2000.
- M. Dakulovic, S. Horvatic, and I. Petrovic. Complete Coverage D* Algorithm for Path Planning of a Floor-Cleaning Mobile Robot. In Proceedings of the 18th IFAC World Congress, pages 5950-5955, 2011.
- D. Fox, W. Burgard, and S. Thrun. The dynamic window approach to collision avoidance. Robotics amp; Automation Magazine, IEEE, 4(1):23-33, 1997.
- Y. Gabriely and E. Rimon. Competitive on-line coverage of grid environments by a mobile robot. Computational Geometry, 24(3):197-224, 2003.
- W.H. Huang. Optimal line-sweep-based decompositions for coverage algorithms. In IEEE International Conference on Robotics and Automation (ICRA 2001), pages 27-32, 2001.
- J.C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Dodrecht, Netherlands, 1991.
- S.M. LaValle. Planning algorithms. Cambridge Univ. Pr., 2006.
-
M. Seder, K. Macek, and I. Petrovic. An integrated approach to real-time mobile robot control in partially known in
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[146995]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
