Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Constant-Factor Approximation Algorithm for Online Coverage Path Planning with Energy Constraint
108
0
0.0
(
0
)
Added by
Ayan Dutta
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study the problem of coverage planning by a mobile robot with a limited energy budget. The objective of the robot is to cover every point in the environment while minimizing the traveled path length. The environment is initially unknown to the robot. Therefore, it needs to avoid the obstacles in the environment on-the-fly during the exploration. As the robot has a specific energy budget, it might not be able to cover the complete environment in one traversal. Instead, it will need to visit a static charging station periodically in order to recharge its energy. To solve the stated problem, we propose a budgeted depth-first search (DFS)-based exploration strategy that helps the robot to cover any unknown planar environment while bounding the maximum path length to a constant-factor of the shortest-possible path length. Our $O(1)$-approximation guarantee advances the state-of-the-art of log-approximation for this problem. Simulation results show that our proposed algorithm outperforms the current state-of-the-art algorithm both in terms of the traveled path length and run time in all the tested environments with concave and convex obstacles.
rate research
Read More
This paper presents a novel algorithm, called $epsilon^*$+, for online coverage path planning of unknown environments using energy-constrained autonomous vehicles. Due to limited battery size, the energy-constrained vehicles have limited duration of operation time. Therefore, while executing a coverage trajectory, the vehicle has to return to the charging station for a recharge before the battery runs out. In this regard, the $epsilon^*$+ algorithm enables the vehicle to retreat back to the charging station based on the remaining energy which is monitored throughout the coverage process. This is followed by an advance trajectory that takes the vehicle to a near by unexplored waypoint to restart the coverage process, instead of taking it back to the previous left over point of the retreat trajectory; thus reducing the overall coverage time. The proposed $epsilon^*$+ algorithm is an extension of the $epsilon^*$ algorithm, which utilizes an Exploratory Turing Machine (ETM) as a supervisor to navigate the vehicle with back and forth trajectory for complete coverage. The performance of the $epsilon^*$+ algorithm is validated on complex scenarios using Player/Stage which is a high-fidelity robotic simulator.
This paper presents a deep-learning based CPP algorithm, called Coverage Path Planning Network (CPPNet). CPPNet is built using a convolutional neural network (CNN) whose input is a graph-based representation of the occupancy grid map while its output is an edge probability heat graph, where the value of each edge is the probability of belonging to the optimal TSP tour. Finally, a greedy search is used to select the final optimized tour. CPPNet is trained and comparatively evaluated against the TSP tour. It is shown that CPPNet provides near-optimal solutions while requiring significantly less computational time, thus enabling real-time coverage path planning in partially unknown and dynamic environments.
The problem of constrained coverage path planning involves a robot trying to cover maximum area of an environment under some constraints that appear as obstacles in the map. Out of the several coverage path planning methods, we consider augmenting the linear sweep-based coverage method to achieve minimum energy/ time optimality along with maximum area coverage. In addition, we also study the effects of variation of different parameters on the performance of the modified method.
This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins vehicle through $n$ points on the plane. By Dubins vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order $n^{2/3}$.
This letter addresses the 3D coverage path planning (CPP) problem for terrain reconstruction of unknown obstacle rich environments. Due to sensing limitations, the proposed method, called CT-CPP, performs layered scanning of the 3D region to collect terrain data, where the traveling sequence is optimized using the concept of a coverage tree (CT). A modified TSP-based tree traversal strategy is proposed. The CT-CPP method is validated on a high-fidelity underwater simulator and the results are evaluated in comparison to an existing terrain following CPP method (TF-CPP). The CT-CPP with TSP optimizer yields significant improvements in trajectory length, energy consumption, and reconstruction error.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
