面向荒漠复杂地形的机器人在线全覆盖路径规划方法

对于地形复杂、范围广阔的荒漠环境,当前的地图模型存在占用存储空间过大的问题;同时在复杂地形下,当前的全覆盖路径规划算法能量消耗大,无法适用于在线条件.对此,提出一种在线的全覆盖路径规划算法及相应的地图模型.首先,介绍一种变分辨率的三维栅格地图模型.其次,分析机器人在非平面环境下进行全覆盖任务的能量消耗问题,得出最节约能量的覆盖方式.在对平坦地形的覆盖中,基于优先级覆盖的思想,对传统的牛耕法覆盖做出改进,拓展为8个方向.然后,针对非平坦地形提出一种在线的面向地形的区域分解方法,在全覆盖过程中根据高度将特殊地形区域分解出来单独覆盖.在子区域内部,对特殊地形抽象得到斜面模型,引入地形变化函数,形成新的优先级遍历方法,并设计一种针对性的避障策略以进一步减少能量消耗.最后,对所提出的算法进行仿真验证以及机器人实验.仿真验证和实验结果表明,相比于其他算法,所提出算法能显著减少全覆盖过程中的重复率以及机器人总能量消耗.     

多简单机器人协作覆盖规划研究

研究了多简单机器人协作覆盖的问题．针对简单机器人只能用接触传感器感知外部环境的局限性，提出了基于栅格地图表示法的多机器人内螺旋覆盖算法进行在线覆盖规划．该方法通过对部分区域的重复覆盖和设置GATE栅格实现了对环境的完全覆盖，同时该方法保证了只要有一个机器人不出现故障就可以完成覆盖，提高了系统稳定性．最后用仿真试验验证了该方法的可行性．     

一种改进的粒子滤波SLAM算法*

提出一种改进的粒子滤波SLAM（simultaneous localization and map building）同时定位和地图创建实现方法。改进方法让机器人大约行进10步完成基于局部已创建地图下的粒子滤波定位后,再利用激光传感器探测环境并更新创建的地图;同时在利用粒子滤波定位时,使粒子只分布在由航位推算法得出的机器人位姿附近,从而可有效地减少粒子的数量。实验结果表明,与标准的粒子滤波SLAM 算法比较,改进算法提高了机器人SLAM过程中定位和地图创建的精度和实时性,并为移动机器人在室外未知环境同时定位和地图创建提供了新方法。     

基于栅格地图的机器人覆盖路径规划研究*

研究了基于接触传感器的机器人覆盖问题,提出了基于栅格地图的内螺旋覆盖(ISC)算法.ISC算法通过边界探索获得环境边界地图之后,在线规划覆盖路径,用距离转变的搜索方法保证了完全覆盖,通过设置gate栅格降低了重复覆盖率.通过对三个房间组成的室内环境的覆盖仿真试验验证了该方法的可行性.     

多机器人地图融合方法研究

多机器人建图是实现机器人自主导航,完成复杂智能任务的关键.其中如何将不同机器人采集的数据融合到全局地图中,成了多机器人建图中的一个核心问题.文中采用独立探索、集中建图的探索策略,提出一种基于改进差异进化算法的多机器人概率栅格地图的融合.该算法在地图相似度的概念基础上,建立相异度函数,利用改进的进化算法搜索策略快速地搜索各局部地图之间的最大重叠部分,实现了多机器人系统栅格地图的融合,有效的解决了相对位置未知情况下的地图创建问题.通过实验验证了该方法正确、可行.     

消毒机器人全覆盖路径算法设计

针对消毒机器人全覆盖消毒的算法,传统的消毒机器人重复率高、消耗大,容易进入死区,导致机器人无法进行工作,机器人利用二维的激光雷达旋转扫描到室内的三维立体空间,建立格栅地图,通过SPDF算法与改善A*算法得到的Theta*算法相结合的算法,使得消毒机人能够正常地完成室内的消毒工作,并且保证消毒面积尽可能的重复率在较低的情况下,完成全面消毒。     

基于环境信息实时感知的图书存取机器人移动轨迹检测

为保证机器人在图书存取时,按照设定轨迹完成图书存取,研究基于环境信息实时感知的图书存取机器人移动轨迹检测方法。通过在机器人上搭载激光雷达设备,采集机器人移动环境三维点云数据;采用贝叶斯估计方法融合该数据后,基于图优化算法构建机器人移动地图;采用平滑接近图算法,检测机器人在地图中的移动方向角,结合机器人所有的方向角结果实现机器人移动轨迹检测。测试结果显示：该方法能可靠获取机器人移动环境的三维点云数据,清晰生成机器人移动地图,并呈现障碍物情况;机器人最大方向角度检测误差结果为1.23°;机器人的移动轨迹位置和指定位置结果吻合程度较高。     

基于ROS的无人配送车导航系统的设计与实现

针对无人配送车在自主导航过程中存在的寻路效率低、避障能力弱、转折幅度过大等问题,该文采用搭载机器人操作系统(ROS)的Turtlebot3机器人作为无人配送车,设计并实现了高效稳定的无人配送车自主导航系统。ROS是专门用于编写机器人软件的灵活框架,对其集成的SLAM算法进行改进,以完成无人配送车在封闭园区环境中的即时定位与地图构建,同时对ROS导航功能包集成的路径规划算法进行改进,使无人配送车在已知环境地图中规划生成出适合无人配送车工作的路径和有效避开障碍物。最后在Gazebo仿真环境中对无人配送车自主导航系统进行测试与验证。仿真试验结果表明,设计实现的无人配送车导航系统能够很好地满足无人配送车在封闭园区中的自主导航功能。     

基于激光雷达的移动机器人定位和地图创建

针对未知环境下移动机器人定位和地图创建问题,提出了创建局部地图-机器人定位-更新全局地图的方法和步骤.利用激光雷达数据,采用"聚合-分割-聚合"的方法并运用动态阈值获得精确的局部地图.通过匹配局部地图和全局地图的线段关系,实现了机器人的定位,更新了机器人的位姿,减少了机器人的系统误差和环境误差,进而完成了全局地图的创建与更新.实验证明,此算法可以在实现机器人定位的同时获得精确的环境地图,并且有效的缩短了地图生成时间,可靠性高、实时性好.     

多机器人同步定位与地图构建的地图融合算法的改进

本文主要研究了多机器人同步定位与地图构建(SLAM)的地图实时融合问题.在本文中提出一种混合的SLAM算法(HybridSLAM)算法,可以同时观测和更新多个路标,并根据FastSLAM2.0思想利用选取的最准确的路标观测值来修正机器人位姿.然后,在改进HybridSLAM算法基础上,进一步提出一种改进的多机器人HybridSLAM算法(MR–IHybridSLAM).每个机器人在不同初始位置运行IHybridSLAM算法构建子地图,并将子地图信息实时发送到同一工作站中.根据卡尔曼滤波(KF)原理将每个机器人构建的子地图融合成全局地图.最后,通过仿真实验构建多机器人融合的特征地图并与单一机器人快速的SLAM算法(FastSLAM)和HybridSLAM算法构建的地图进行误差对比,进一步来验证该算法的准确性、快速性和可行性.     

The giving tree: constructing trees for efficient offline and online multi-robot coverage

This paper discusses the problem of building efficient coverage paths for a team of robots. An efficient multi-robot coverage algorithm should result in a coverage path for every robot, such that the union of all paths generates a full coverage of the terrain and the total coverage time is minimized. A method underlying several coverage algorithms, suggests the use of spanning trees as base for creating coverage paths. However, overall performance of the coverage is heavily dependent on the given spanning tree. This paper focuses on the challenge of constructing a coverage spanning tree for both online and offline coverage that minimizes the time to complete coverage. Our general approach involves building a spanning tree by growing sub-trees from the initial location of the robots. This paper first describes a polynomial time tree-construction algorithm for offline coverage. The use of this algorithm is shown by extensive simulations to significantly improve the coverage time of the terrain even when used as a basis for a simple, inefficient, coverage algorithm. Second, this paper provides an algorithm for online coverage of a finite terrain based on spanning-trees, that is complete and guarantees linear time coverage with no redundancy in the coverage. In addition, the solutions proposed by this paper guarantee robustness to failing robots: the offline trees are used as base for robust multi-robot coverage algorithms, and the online algorithm is proven to be robust.     

Spanning-tree based coverage of continuous areas by a mobile robot

This paper considers the problem of covering a continuous planar area by a square-shaped tool attached to a mobile robot. Using a tool-based approximation of the work-area, we present an algorithm that covers every point of the approximate area for tasks such as floor cleaning, lawn mowing, and field demining. The algorithm, called Spanning Tree Covering (STC), subdivides the work-area into disjoint cells corresponding to the square-shaped tool, then follows a spanning tree of the graph induced by the cells, while covering every point precisely once. We present and analyze three versions of the STC algorithm. The first version is off-line, where the robot has perfect apriori knowledge of its environment. The off-line STC algorithm computes an optimal covering path in linear time O(N), where N is the number of cells comprising the approximate area. The second version of STC is on-line, where the robot uses its sensors to detect obstacles and construct a spanning tree of the environment while covering the work-area. The on-line STC algorithm completes an optimal covering path in time O(N), but requires O(N) memory for its implementation. The third version of STC is “ant”-like. In this version, too, the robot has no apriori knowledge of the environment, but it may leave pheromone-like markers during the coverage process. The ant-like STC algorithm runs in time O(N), and requires only O(1) memory. Finally we present simulation results of the three STC algorithms, demonstrating their effectiveness in cases where the tool size is significantly smaller than the work-area characteristic dimension. This revised version was published online in August 2006 with corrections to the Cover Date.     

Efficient terrain coverage for deploying wireless sensor nodes on multi-robot system

Coverage and connectivity are the two main functionalities of wireless sensor network. Stochastic node deployment or random deployment almost always cause hole in sensing coverage and cause redundant nodes in area. In the other hand precise deployment of nodes in large area is very time consuming and even impossible in hazardous environment. One of solution for this problem is using mobile robots with concern on exploration algorithm for mobile robot. In this work an autonomous deployment method for wireless sensor nodes is proposed via multi-robot system which robots are considered as node carrier. Developing an exploration algorithm based on spanning tree is the main contribution and this exploration algorithm is performing fast localization of sensor nodes in energy efficient manner. Employing multi-robot system and path planning with spanning tree algorithm is a strategy for speeding up sensor nodes deployment. A novel improvement of this technique in deployment of nodes is having obstacle avoidance mechanism without concern on shape and size of obstacle. The results show using spanning tree exploration along with multi-robot system helps to have fast deployment behind efficiency in energy.     

BA*: an online complete coverage algorithm for cleaning robots

This paper presents a novel approach to solve the online complete coverage task of autonomous cleaning robots in unknown workspaces based on the boustrophedon motions and the A* search algorithm (BA*). In this approach, the robot performs a single boustrophedon motion to cover an unvisited region until it reaches a critical point. To continue covering the next unvisited region, the robot wisely detects backtracking points based on its accumulated knowledge, determines the best backtracking point as the starting point of the next boustrophedon motion, and applies an intelligent backtracking mechanism based on the proposed A* search with smoothed path on tiling so as to reach the starting point with the shortest collision-free path. The robot achieves complete coverage when no backtracking point is detected. Computer simulations and experiments in real workspaces prove that our proposed BA* is efficient for the complete coverage task of cleaning robots.     

FAST

We propose Frontier Allocation Synchronized by Token passing (FAST), a distributed algorithm for online terrain coverage using multiple mobile robots, ensuring mutually exclusive selection of frontier cells. Many existing approaches cover the terrain in an irregular fashion, without considering the usability of the already covered region. For instance, in the task of floor cleaning in an office building, these approaches do not guarantee the cleanliness of large unbroken areas until a majority of the task is complete. FAST on the other hand, incrementally traverses the terrain generating structured trajectories for each robot. Following a structured trajectory for coverage path planning is proven to be a very powerful approach in literature. This renders large portions of the terrain usable even before the completion of the coverage task. The novel map representation techniques used in FAST render it scalable to large terrains, without affecting the volume of communication among robots. Moreover, the distributed nature of FAST allows incorporation of fault-tolerance mechanisms. Empirical investigations on maps of varied complexities and sizes both in simulation and on an experimental test-bed demonstrate that the proposed algorithm performs better than some of the benchmark approaches in terms of coverage completion time and less redundant coverage.     

GSST: anytime guaranteed search

We present Guaranteed Search with Spanning Trees (GSST), an anytime algorithm for multi-robot search. The problem is as follows: clear the environment of any adversarial target using the fewest number of searchers. This problem is NP-hard on arbitrary graphs but can be solved in linear-time on trees. Our algorithm generates spanning trees of a graphical representation of the environment to guide the search. At any time, spanning tree generation can be stopped yielding the best strategy so far. The resulting strategy can be modified online if additional information becomes available. Though GSST does not have performance guarantees after its first iteration, we prove that several variations will find an optimal solution given sufficient runtime. We test GSST in simulation and on a human-robot search team using a distributed implementation. GSST quickly generates clearing schedules with as few as 50% of the searchers used by competing algorithms.     

Using spanning sets for coverage testing

A test coverage criterion defines a set E/sub r/ of entities of the program flowgraph and requires that every entity in this set is covered under some test Case. Coverage criteria are also used to measure the adequacy of the executed test cases. In this paper, we introduce the notion of spanning sets of entities for coverage testing. A spanning set is a minimum subset of E/sub r/, such that a test suite covering the entities in this subset is guaranteed to cover every entity in E/sub r/. When the coverage of an entity always guarantees the coverage of another entity, the former is said to subsume the latter. Based on the subsumption relation between entities, we provide a generic algorithm to find spanning sets for control flow and data flow-based test coverage criteria. We suggest several useful applications of spanning sets: They help reduce and estimate the number of test cases needed to satisfy coverage criteria. We also empirically investigate how the use of spanning sets affects the fault detection effectiveness.