Fast and optimal branch-and-bound planner for the grid-based coverage path planning problem based on an admissible heuristic function

This paper introduces an optimal algorithm for solving the discrete grid-based coverage path planning (CPP) problem. This problem consists in finding a path that covers a given region completely. First, we propose a CPP-solving baseline algorithm based on the iterative deepening depth-first search (ID-DFS) approach. Then, we introduce two branch-and-bound strategies (Loop detection and an Admissible heuristic function) to improve the results of our baseline algorithm. We evaluate the performance of our planner using six types of benchmark grids considered in this study: Coast-like, Random links, Random walk, Simple-shapes, Labyrinth and Wide-Labyrinth grids. We are first to consider these types of grids in the context of CPP. All of them find their practical applications in real-world CPP problems from a variety of fields. The obtained results suggest that the proposed branch-and-bound algorithm solves the problem optimally (i.e., the exact solution is found in each case) orders of magnitude faster than an exhaustive search CPP planner. To the best of our knowledge, no general CPP-solving exact algorithms, apart from an exhaustive search planner, have been proposed in the literature.

An Improved Complete Coverage Path Planning Method for Intelligent Agricultural Machinery Based on Backtracking Method

The advancement of society and technology has promoted the development of modern agriculture. It has become a trend to replace traditional manpower with intelligent agricultural machinery that operates independently. As the core technology of intelligent agricultural machinery, complete coverage path planning technology has become more important. At present, the complete coverage path planning algorithms still suffer from problems such as sacrificing the coverage rate to obtain the minimum energy consumption, taking a long time to calculate the algorithm, and destroying crops across the covered region. In view of the above problems, an improved complete coverage path planning algorithms based on backtracking is proposed combined with the actual needs of intelligent agricultural machinery for planting seedlings to improve four aspects: repeated coverage, search efficiency, path planning, and sub-regional crossing. Firstly, the Morse decomposition method is used to divide a complex farmland region into simple sub-regions. Then an improved backtracking method based on a greedy algorithm is proposed in order to reduce the computational efficiency of the current region connection algorithms. The priority principle and the strategy of moving along the boundary are used to solve the problems of region crossing and sacrificing the coverage rate, thereby improving the performance of the current complete coverage path planning method. Compared with the traditional backtracking method, the experimental results show that the number of backtracking points is decreased by about 70% and the occurrence of crossing sub-regions has been significantly reduced. This proposed method can improve the coverage and operating efficiency of intelligent agricultural machinery operations and provide technical support for agricultural operations such as sowing, tillage, and harvesting, thus improving the quality and efficiency of agricultural production.

Modelling and Control of a Reconfigurable Robot for Achieving Reconfiguration and Locomotion with Different Shapes

Area coverage is a crucial factor for a robot intended for applications such as floor cleaning, disinfection, and inspection. Robots with fixed shapes could not realize an adequate level of area coverage performance. Reconfigurable robots have been introduced to overcome the limitations of fixed-shape robots, such as accessing narrow spaces and cover obstacles. Although state-of-the-art reconfigurable robots used for coverage applications are capable of shape-changing for improving the area coverage, the reconfiguration is limited to a few predefined shapes. It has been proven that the ability of reconfiguration beyond a few shapes can significantly improve the area coverage performance of a reconfigurable robot. In this regard, this paper proposes a novel robot model and a low-level controller that can facilitate the reconfiguration beyond a small set of predefined shapes and locomotion per instructions while firmly maintaining the shape. A prototype of a robot that facilitates the aim mentioned above has been designed and developed. The proposed robot model and controller have been integrated into the prototype, and experiments have been conducted considering various reconfiguration and locomotion scenarios. Experimental results confirm the validity of the proposed model and controller during reconfiguration and locomotion of the robot. Moreover, the applicability of the proposed model and controller for achieving high-level autonomous capabilities has been proven.

An Autonomous Robot-Aided Auditing Scheme for Floor Cleaning

Cleaning is an important factor in most aspects of our day-to-day life. This research work brings a solution to the fundamental question of “How clean is clean” by introducing a novel framework for auditing the cleanliness of built infrastructure using mobile robots. The proposed system presents a strategy for assessing the quality of cleaning in a given area and a novel exploration strategy that facilitates the auditing in a given location by a mobile robot. An audit sensor that works by the “touch and inspect” analogy that assigns an audit score corresponds to its area of inspection has been developed. A vision-based dirt-probability-driven exploration is proposed to empower a mobile robot with an audit sensor on-board to perform auditing tasks effectively. The quality of cleaning is quantified using a dirt density map representing location-wise audit scores, dirt distribution pattern obtained by kernel density estimation, and cleaning benchmark score representing the extent of cleanliness. The framework is realized in an in-house developed audit robot to perform the cleaning audit in indoor and semi-outdoor environments. The proposed method is validated by experiment trials to estimate the cleanliness in five different locations using the developed audit sensor and dirt-probability-driven exploration.

Neural dynamics based complete grid coverage by single and multiple mobile robots

Navigation of mobile robots in a grid based environment is useful in applications like warehouse automation. The environment comprises of a number of free grid cells for navigation and remaining grid cells are occupied by obstacles and/or other mobile robots. Such obstructions impose situations of collisions and dead-end. In this work, a neural dynamics based algorithm is proposed for complete coverage of a grid based environment while addressing collision avoidance and dead-end situations. The relative heading of the mobile robot with respect to the neighbouring grid cells is considered to calculate the neural activity. Moreover, diagonal movement of the mobile robot through inter grid cells is restricted to ensure safety from the collision with obstacles and other mobile robots. The circumstances where the proposed algorithm will fail to provide completeness are also discussed along with the possible ways to overcome those situations. Simulation results are presented to show the effectiveness of the proposed algorithm for a single and multiple mobile robots. Moreover, comparative studies illustrate improvements over other algorithms on collision free effective path planning of mobile robots within a grid based environment.

Laser Ablation Manipulator Coverage Path Planning Method Based on an Improved Ant Colony Algorithm

Coverage path planning on a complex free-form surface is a representative problem that has been steadily investigated in path planning and automatic control. However, most methods do not consider many optimisation conditions and cannot deal with complex surfaces, closed surfaces, and the intersection of multiple surfaces. In this study, a novel and efficient coverage path-planning method is proposed that considers trajectory optimisation information and uses point cloud data for environmental modelling. First, the point cloud data are denoised and simplified. Then, the path points are converted into the rotation angle of each joint of the manipulator. A mathematical model dedicated to energy consumption, processing time, and path smoothness as optimisation objectives is developed, and an improved ant colony algorithm is used to solve this problem. Two measures are proposed to prevent the algorithm from being trapped in a local optimum, thereby improving the global search ability of the algorithm. The standard test results indicate that the improved algorithm performs better than the ant colony algorithm and the max–min ant system. The numerical simulation results reveal that compared with the point cloud slicing technique, the proposed method can obtain a more efficient path. The laser ablation de-rusting experiment results specify the utility of the proposed approach.

Development of User-Integrated Semi-Autonomous Lawn Mowing Systems: A Systems Engineering Perspective and Proposed Architecture

This concept paper outlines a conceptual framework for the design and development of user-integrated semi-autonomous lawn mowing systems. This is approached from a systems engineering perspective, considering both hardware and software elements and integration with the user. This is an important and emerging field of study within the several engineering communities, including robotics, agricultural engineering, smart city development, and general systems engineering. In several sections of this paper, a review of current progress on this problem is presented (both in general and related to specific aspects of the system), followed by a discussion of the problem from a systems engineering perspective, a general system architecture developed by the authors, a preliminary set of design requirements, and a discussion of some practical implementation strategies. This work is meant to provide a baseline and motivation for the further development and refinement of these systems within the agricultural engineering and robotics communities and is relevant to both academic and commercial research.

GM-VPC: An Algorithm for Multi-robot Coverage of Known Spaces Using Generalized Voronoi Partition

In this paper we address the problem of coverage path planning (CPP) for multiple cooperating mobile robots. We use a ‘partition and cover’ approach using Voronoi partition to achieve natural passive cooperation between robots to avoid task duplicity. We combine two generalizations of Voronoi partition, namely geodesic-distance-based Voronoi partition and Manhattan-distance-based Voronoi partition, to address contiguity of partition in the presence of obstacles and to avoid partition-boundary-induced coverage gap. The region is divided into 2D×2Dgrids, whereDis the size of the robot footprint. Individual robots can use any of the single-robot CPP algorithms. We show that with the proposed Geodesic-Manhattan Voronoi-partition-based coverage (GM-VPC), a complete and non-overlapping coverage can be achieved at grid level provided that the underlying single-robot CPP algorithm has similar property.We demonstrated using two representative single-robot coverage strategies, namely Boustrophedon-decomposition-based coverage and Spanning Tree coverage, first based on so-called exact cellular decomposition and second based on approximate cellular decomposition, that the proposed partitioning scheme completely eliminates coverage gaps and coverage overlaps. Simulation experiments using Matlab and V-rep robot simulator and experiments with Fire Bird V mobile robot are carried out to validate the proposed coverage strategy.