Improved Optimization Strategy Based on Region Division for Collaborative Multi-Agent Coverage Path Planning

In this paper, we investigate the algorithms for traversal exploration and path coverage of target regions using multiple agents, enabling the efficient deployment of a set of agents to cover a complex region. First, the original multi-agent path planning problem (mCPP) is transformed into several single-agent sub-problems, by dividing the target region into multiple balanced sub-regions, which reduces the explosive combinatorial complexity; subsequently, closed-loop paths are planned in each sub-region by the rapidly exploring random trees (RRT) algorithm to ensure continuous exploration and repeated visits to each node of the target region. On this basis, we also propose two improvements: for the corner case of narrow regions, the use of geodesic distance is proposed to replace the Eulerian distance in Voronoi partitioning, and the iterations for balanced partitioning can be reduced by more than one order of magnitude; the Dijkstra algorithm is introduced to assign a smaller weight to the path cost when the geodesic direction changes, which makes the region division more "cohesive", thus greatly reducing the number of turns in the path and making it more robust. The final optimization algorithm ensures the following characteristics: complete coverage of the target area, wide applicability of multiple area shapes, reasonable distribution of exploration tasks, minimum average waiting time, and sustainable exploration without any preparation phase.

Deep Learning-Based Complete Coverage Path Planning With Re-Joint and Obstacle Fusion Paradigm

With the introduction of autonomy into the precision agriculture process, environmental exploration, disaster response, and other fields, one of the global demands is to navigate autonomous vehicles to completely cover entire unknown environments. In the previous complete coverage path planning (CCPP) research, however, autonomous vehicles need to consider mapping, obstacle avoidance, and route planning simultaneously during operating in the workspace, which results in an extremely complicated and computationally expensive navigation system. In this study, a new framework is developed in light of a hierarchical manner with the obtained environmental information and gradually solving navigation problems layer by layer, consisting of environmental mapping, path generation, CCPP, and dynamic obstacle avoidance. The first layer based on satellite images utilizes a deep learning method to generate the CCPP trajectory through the position of the autonomous vehicle. In the second layer, an obstacle fusion paradigm in the map is developed based on the unmanned aerial vehicle (UAV) onboard sensors. A nature-inspired algorithm is adopted for obstacle avoidance and CCPP re-joint. Equipped with the onboard LIDAR equipment, autonomous vehicles, in the third layer, dynamically avoid moving obstacles. Simulated experiments validate the effectiveness and robustness of the proposed framework.

Coverage Path Planning Methods Focusing on Energy Efficient and Cooperative Strategies for Unmanned Aerial Vehicles

The coverage path planning (CPP) algorithms aim to cover the total area of interest with minimum overlapping. The goal of the CPP algorithms is to minimize the total covering path and execution time. Significant research has been done in robotics, particularly for multi-unmanned unmanned aerial vehicles (UAVs) cooperation and energy efficiency in CPP problems. This paper presents a review of the early-stage CPP methods in the robotics field. Furthermore, we discuss multi-UAV CPP strategies and focus on energy-saving CPP algorithms. Likewise, we aim to present a comparison between energy efficient CPP algorithms and directions for future research.

Multidrone aerial surveys of penguin colonies in Antarctica

Speed is essential in wildlife surveys due to the dynamic movement of animals throughout their environment and potentially extreme changes in weather. In this work, we present a multirobot path-planning method for conducting aerial surveys over large areas designed to make the best use of limited flight time. Unlike current survey path-planning solutions based on geometric patterns or integer programs, we solve a series of satisfiability modulo theory instances of increasing complexity. Each instance yields a set of feasible paths at each iteration and recovers the set of shortest paths after sufficient time. We implemented our planning algorithm with a team of drones to conduct multiple photographic aerial wildlife surveys of Cape Crozier, one of the largest Adélie penguin colonies in the world containing more than 300,000 nesting pairs. Over 2 square kilometers was surveyed in about 3 hours. In contrast, previous human-piloted single-drone surveys of the same colony required over 2 days to complete. Our method reduces survey time by limiting redundant travel while also allowing for safe recall of the drones at any time during the survey. Our approach can be applied to other domains, such as wildfire surveys in high-risk weather conditions or disaster response.

Proposed Smooth-STC Algorithm for Enhanced Coverage Path Planning Performance in Mobile Robot Applications

Robotic path planning is a field of research which is gaining traction given the broad domains of interest to which path planning is an important systemic requirement. The aim of path planning is to optimise the efficacy of robotic movement in a defined operational environment. For example, robots have been employed in many domains including: Cleaning robots (such as vacuum cleaners), automated paint spraying robots, window cleaning robots, forest monitoring robots, and agricultural robots (often driven using satellite and geostationary positional satellite data). Additionally, mobile robotic systems have been utilised in disaster areas and locations hazardous to humans (such as war zones in mine clearance). The coverage path planning problem describes an approach which is designed to determine the path that traverses all points in a defined operational environment while avoiding static and dynamic (moving) obstacles. In this paper we present our proposed Smooth-STC model, the aim of the model being to identify an optimal path, avoid all obstacles, prevent (or at least minimise) backtracking, and maximise the coverage in any defined operational environment. The experimental results in a simulation show that, in uncertain environments, our proposed smooth STC method achieves an almost absolute coverage rate and demonstrates improvement when measured against alternative conventional algorithms.

Modified A-Star Algorithm for Efficient Coverage Path Planning in Tetris Inspired Self-Reconfigurable Robot with Integrated Laser Sensor

Advancing an efficient coverage path planning in robots set up for application such as cleaning, painting and mining are becoming more crucial. Such drive in the coverage path planning field proposes numerous techniques over the past few decades. However, the proposed approaches were only applied and tested with a fixed morphological robot in which the coverage performance was significantly degraded in a complex environment. To this end, an A-star based zigzag global planner for a novel self-reconfigurable Tetris inspired cleaning robot (hTetro) presented in this paper. Unlike the traditional A-star algorithm, the presented approach can generate waypoints in order to cover the narrow spaces while assuming appropriate morphology of the hTtero robot with the objective of maximizing the coverage area. We validated the efficiency of the proposed planning approach in the Robot Operation System (ROS) Based simulated environment and tested with the hTetro robot in real-time under the controlled scenarios. Our experiments demonstrate the efficiency of the proposed coverage path planning approach resulting in superior area coverage performance in all considered experimental scenarios.

Probabilistic cooperative mobile robot area coverage and its application to autonomous seabed mapping

There are many applications that require mobile robots to autonomously cover an entire area with a sensor or end effector. The vast majority of the literature on this subject is focused on addressing path planning for area coverage under the assumption that the robot’s pose is known or that error is bounded. In this work, we remove this assumption and develop a completely probabilistic representation of coverage. We show that coverage is guaranteed as long as the robot pose estimates are consistent, a much milder assumption than zero or bounded error. After formally connecting robot sensor uncertainty with area coverage, we propose an adaptive sliding window filter pose estimator that provides a close approximation to the full maximum a posteriori estimate with a computation cost that is bounded over time. Subsequently, an adaptive planning strategy is presented that automatically exploits conditions of low vehicle uncertainty to more efficiently cover an area. We further extend this approach to the multi-robot case where robots can communicate through a (possibly faulty and low-bandwidth) channel and make relative measurements of one another. In this case, area coverage is achieved more quickly since the uncertainty over the robots’ trajectories is reduced. We apply the framework to the scenario of mapping an area of seabed with an autonomous underwater vehicle. Experimental results support the claim that our method achieves guaranteed complete coverage notwithstanding poor navigational sensors and that resulting path lengths required to cover the entire area are shortest using the proposed cooperative and adaptive approach.

Ergodicity-Based Cooperative Multiagent Area Coverage via a Potential Field

This paper considers a problem of area coverage where the objective is to achieve given coverage density by use of multiple mobile agents. We present an ergodicity-based coverage algorithm which enables a centralized feedback control for multiagent system based on radial basis function (RBF) representation of the ergodicity problem and a solution of an appropriately designed stationary heat equation for the potential field. The heat equation uses a source term that depends on the difference between the given goal density distribution and the current coverage density (time average of RBFs along trajectories). The agent movement is directed using the gradient of that potential field. The heat equation driven area coverage has a built-in cooperative behavior of agents which includes collision avoidance and coverage coordination. The algorithm is robust, scalable, and computationally inexpensive.

Topological Path Planning in GPS Trajectory Data

This paper proposes a novel solution to the problem of computing a set of topologically inequivalent paths between two points in a space given a set of samples drawn from that space. Specifically, these paths are homotopy inequivalent where homotopy is a topological equivalence relation. This is achieved by computing a basis for the group of homology inequivalent loops in the space. An additional distinct element is then computed where this element corresponds to a loop which passes through the points in question. The set of paths is subsequently obtained by taking the orbit of this element acted on by the group of homology inequivalent loops. Using a number of spaces, including a street network where the samples are GPS trajectories, the proposed method is demonstrated to accurately compute a set of homotopy inequivalent paths. The applications of this method include path and coverage planning.

Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic Methods

Demining and unexploded ordnance (UXO) clearance are extremely tedious and dangerous tasks. The use of robots bypasses the hazards and potentially increases the efficiency of both tasks. A first crucial step towards robotic mine/UXO clearance is to locate all the targets. This requires a path planner that generates a path to pass a detector over all points of a mine/UXO field, i.e., a planner that is complete .The current state of the art in path planning for mine/UXO clearance is to move a robot randomly or use simple heuristics . These methods do not possess completeness guarantees which are vital for locating all of the mines/UXOs. Using such random approaches is akin to intentionally using imperfect detectors. In this paper, we first overview our prior complete coverage algorithm and compare it with randomized approaches. In addition to the provable guarantees, we demonstrate that complete coverage achieves coverage in shorter time than random coverage. We also show that the use of complete approaches enables the creation of a filter to reject bad sensor readings, which is necessary for successful deployment of robots. We propose a new approach to handle sensor uncertainty that uses geometrical and topological features rather than sensor uncertainty models. We have verified our results by performing experiments in unstructured indoor environments. Finally, for scenarios where some a priori information about a minefield is available, we expedite the demining process by introducing a probabilistic method so that a demining robot does not have to perform exhaustive coverage.

Morse Decompositions for Coverage Tasks

Exact cellular decompositions represent a robot's free space by dividing it into regions with simple structure such that the sum of the regions fills the free space. These decompositions have been widely used for path planning between two points, but can be used for mapping and coverage of free spaces. In this paper, we define exact cellular decompositions where critical points of Morse functions indicate the location of cell boundaries. Morse functions are those whose critical points are non-degenerate. Between critical points, the structure of a space is effectively the same, so simple control strategies to achieve tasks, such as coverage, are feasible within each cell. This allows us to introduce a general framework for coverage tasks because varying the Morse function has the effect of changing the pattern by which a robot covers its free space. In this paper, we give examples of different Morse functions and comment on their corresponding tasks. In a companion paper, we describe the sensor-based algorithm that constructs the decomposition.

Sensor-driven area coverage for an autonomous fixed-wing unmanned aerial vehicle

Area coverage with an onboard sensor is an important task for an unmanned aerial vehicle (UAV) with many applications. Autonomous fixed-wing UAVs are more appropriate for larger scale area surveying since they can cover ground more quickly. However, their non-holonomic dynamics and susceptibility to disturbances make sensor coverage a challenging task. Most previous approaches to area coverage planning are offline and assume that the UAV can follow the planned trajectory exactly. In this paper, this restriction is removed as the aircraft maintains a coverage map based on its actual pose trajectory and makes control decisions based on that map. The aircraft is able to plan paths in situ based on sensor data and an accurate model of the on-board camera used for coverage. An information theoretic approach is used that selects desired headings that maximize the expected information gain over the coverage map. In addition, the branch entropy concept previously developed for autonomous underwater vehicles is extended to UAVs and ensures that the vehicle is able to achieve its global coverage mission. The coverage map over the workspace uses the projective camera model and compares the expected area of the target on the ground and the actual area covered on the ground by each pixel in the image. The camera is mounted on a two-axis gimbal and can either be stabilized or optimized for maximal coverage. Hardware-in-the-loop simulation results and real hardware implementation on a fixed-wing UAV show the effectiveness of the approach. By including the already developed automatic takeoff and landing capabilities, we now have a fully automated and robust platform for performing aerial imagery surveys.

An Optimized Field Coverage Planning Approach for Navigation of Agricultural Robots in Fields Involving Obstacle Areas

Abstract Technological advances combined with the demand of cost efficiency and environmental considerations has led farmers to review their practices towards the adoption of new managerial approaches, including enhanced automation. The application of field robots is one of the most promising advances among automation technologies. Since the primary goal of an agricultural vehicle is the complete coverage of the cropped area within a field, an essential prerequisite is the capability of the mobile unit to cover the whole field area autonomously. In this paper, the main objective is to develop an approach for coverage planning for agricultural operations involving the presence of obstacle areas within the field area. The developed approach involves a series of stages including the generation of field-work tracks in the field polygon, the clustering of the tracks into blocks taking into account the in-field obstacle areas, the headland paths generation for the field and each obstacle area, the implementation of a genetic algorithm to optimize the sequence that the field robot vehicle will follow to visit the blocks and an algorithmic generation of the task sequences derived from the farmer practices. This approach has proven that it is possible to capture the practices of farmers and embed these practices in an algorithmic description providing a complete field area coverage plan in a form prepared for execution by the navigation system of a field robot.