Coverage path planning in a generic known environment is shown to be NP-hard. When the environment is unknown, it becomes more challenging as the robot is required to rely on its online map information built during coverage for planning its path. A significant research effort focuses on designing heuristic or approximate algorithms that achieve reasonable performance. Such algorithms have sub-optimal performance in terms of covering the area or the cost of coverage, e.g., coverage time or energy consumption. In this paper, we provide a systematic analysis of the coverage problem and formulate it as an optimal stopping time problem, where the trade-off between coverage performance and its cost is explicitly accounted for. Next, we demonstrate that reinforcement learning (RL) techniques can be leveraged to solve the problem computationally. To this end, we provide some technical and practical considerations to facilitate the application of the RL algorithms and improve the efficiency of the solutions. Finally, through experiments in grid world environments and Gazebo simulator, we show that reinforcement learning-based algorithms efficiently cover realistic unknown indoor environments, and outperform the current state of the art.

We consider the problem of robot path planning in an initially unknown environment where the robot does not have access to an a priori map of its environment but is aware of some common obstacle patterns along with the paths that enable it to circumnavigate around these obstacles. In order to autonomously improve its navigation performance, the robot should be able to identify significant obstacle patterns and learn corresponding obstacle avoidance maneuvers as it navigates through different environments in order to solve its tasks. To achieve this objective, we propose a novel online algorithm called Incremental State Discovery Via Clustering (ISDC) which enables a robot to dynamically determine important obstacle patterns in its environments and their best representations as combinations of initially available basic obstacle patterns. Our results show that ISDC, when combined with our previously proposed navigation technique, was able to identify significant obstacle patterns in different environments in a time effective manner which accelerated the overall path planning and navigation times for the robots.

We consider the problem of robot path planning in an environment where the location and geometry of obstacles are initially unknown while reusing relevant knowledge about collision avoidance learned from robots’ previous navigational experience. Our main hypothesis in this paper is that the path planning times for a robot can be reduced if it can refer to previous maneuvers it used to avoid collisions with obstacles during earlier missions, and adapt that information to avoid obstacles during its current navigation. To verify this hypothesis,we propose an algorithm called LearnerRRT that first uses a feature matching algorithm called Sample ConsensusInitial Alignment (SAC-IA) to efficiently match currently encountered obstacle features with past obstacle features, and, then uses an experience based learning technique to adapt previously recorded robot obstacle avoidance trajectories corresponding to the matched feature, to the current scenario. The feature matching and machine learning techniques are integrated into the robot’s path planner so that the robot can rapidly and seamlessly update its path to circumvent an obstacle it encounters, in real-time, and continue to move towards its goal. We have conducted several experiments using a simulated Coroware Corobot robot within the Webots simulator to verify the performance of our proposed algorithm,with different start and goal locations, and different obstacle geometries and placements, as well as compared our approach to a state-of-the-art sampling based path planner. Our results show that the proposed algorithm LearnerRRT performs much better than InformedRRT*. When given the same time, our algorithm finished its task successfully whereas Informed RRT* could only achieve 10-20 percent of the optimal distance.