completecoverage, which is integral to many robotic applications, aims to cover an area as quickly as possible. In such tasks, employing multiple robots can reduce the overall coverage time by appropriate task alloca...
详细信息
completecoverage, which is integral to many robotic applications, aims to cover an area as quickly as possible. In such tasks, employing multiple robots can reduce the overall coverage time by appropriate task allocation. Several multi-robot coverage approaches divide the environment into balanced subareas and minimize the maximum subarea of all robots. However, balanced coverage in many situations, such as in the cases of robots with different velocities and heterogeneous multi-robot systems, may have inefficient results. This study addresses the unbalanced complete coverage problem of multiple robots with different velocities for a known environment. First, we propose a novel credit model to transform the unbalanced coverageproblem into a set of single-objective optimization problems, which can find a combinational optimal solution by optimizing each separate objective function of the single-objective optimization problem to alleviate the computational complexity. Then, we propose a credit-based algorithm composed of a cyclic region growth algorithm and a region fine-tuning algorithm. The cyclic region growth algorithm finds an initial solution to the single-objective optimization problems set by a regional growth strategy with multiple restricts, whereas the region fine-tuning algorithm reallocates the tasks of the partitions with too many tasks to the partitions with too few tasks by constructing a search tree, thereby converging the initial solution to the optimal solution. Simulation results indicate that compared with conventional multi-robot complete coverage problem algorithms, the credit-based algorithm can obtain the optimal solution with the increased number of robots and enlarged size of the mission environment.
Algorithms using swarming collective motion can solve coverageproblems in unknown environments by reacting to unknown obstacles in real-time when they are encountered. However, these algorithms face two key challenge...
详细信息
Algorithms using swarming collective motion can solve coverageproblems in unknown environments by reacting to unknown obstacles in real-time when they are encountered. However, these algorithms face two key challenges when deployed on real robots. First, hand-tuning efficient collective motion parameters is both time-consuming and difficult. Second, predicting the time required fora swarm to solve a particular problem is not straightforward. This paper introduces a novel evolutionary framework to address both problems by proposing a methodology that autonomously tunes collective motion parameters for coverageproblems while predicting the time required for real robots to complete the task. Our approach utilizes a simulation- optimization framework that employs a genetic algorithm to optimize the parameters of a frontier-led swarming algorithm. Results indicate that the optimized parameters are transferable to real robots, achieving 100% coverage while maintaining 84% connectivity between them. Compared to state-of-the-art swarm methods, our system reduced turnaround time by 50% and 57% indifferent environments while maintaining collective motion. It also achieved a 55% reduction in turnaround time on average across five scenarios compared to budget-constrained path planning, with a 10% increase in coverage. Furthermore, our framework outperformed both hand-tuned and learned collective motion approaches, reducing turnaround time by 73% in non-collective motion scenarios and by 63% while maintaining 85% connectivity in collective motion scenarios. This approach effectively combines the adaptability of swarm behavior with the predictive reliability of planning methods.
coverage path planning (CPP) is the foundation of multiple robotic applications. The efficiency of CPP is affected by the local extremum, which describes a situation with the robot surrounded by obstacles and explored...
详细信息
coverage path planning (CPP) is the foundation of multiple robotic applications. The efficiency of CPP is affected by the local extremum, which describes a situation with the robot surrounded by obstacles and explored areas, even if unexplored areas remain in the environment. Most online CPP methods reactively deal with the local extremum after the mobile robot is trapped within it. However, repeated coverage is generated since the path of escaping the local extremum revisits the covered areas. This paper presents an online spiral coverage framework with proactive prevention of extremum (SP2E) to address the CPP problem in an unknown environment. Unlike other CPP methods, the SP2E approach prevents the local extremum through a cut vertex detection algorithm and a direction adaptation algorithm. The cut vertex detection algorithm predicts the local extremum by detecting cut vertexes, and the direction adaptation algorithm prevents it by adjusting the spiral path's direction. The SP2E approach was validated by simulations and real-world experiments, and its performance was compared with other CPP algorithms. The results of simulations and real-world experiments demonstrate that the SP2E approach provides the minimum coverage time and computation time while avoiding the local extremum.
In robot planning problems, the completecoverage path planning refers to the problem of determining a path that a robot must take in order to pass over each point in an environment and avoid obstacles. Applications i...
详细信息
ISBN:
(纸本)9781424402588
In robot planning problems, the completecoverage path planning refers to the problem of determining a path that a robot must take in order to pass over each point in an environment and avoid obstacles. Applications include demining, sweeping, cleaning, vacuuming, inspection robots. For this kind of problem, not only the completecoverage should be performed, but an efficient path is highly desired. Using traditional sweeping line strategy often requires several relocation moves, leading to poor efficiency. In this paper we describe a geometric algorithm for generating paths by using a modified sweeping line strategy that attempts to minimize extra relocation moves. Several examples are used in the paper to show the advantage of our algorithm over traditional approaches.
暂无评论