Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm ...Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment.Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with patternbased genetic algorithm(PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.展开更多
Unmanned aerial vehicles(UAVs),commonly known as drones,have drawn significant consideration thanks to their agility,mobility,and flexibility features.They play a crucial role in modern reconnaissance,inspection,intel...Unmanned aerial vehicles(UAVs),commonly known as drones,have drawn significant consideration thanks to their agility,mobility,and flexibility features.They play a crucial role in modern reconnaissance,inspection,intelligence,and surveillance missions.Coverage path planning(CPP)which is one of the crucial aspects that determines an intelligent system’s quality seeks an optimal trajectory to fully cover the region of interest(ROI).However,the flight time of the UAV is limited due to a battery limitation and may not cover the whole region,especially in large region.Therefore,energy consumption is one of the most challenging issues that need to be optimized.In this paper,we propose an energy-efficient coverage path planning algorithm to solve the CPP problem.The objective is to generate a collision-free coverage path that minimizes the overall energy consumption and guarantees covering the whole region.To do so,the flight path is optimized and the number of turns is reduced to minimize the energy consumption.The proposed approach first decomposes the ROI into a set of cells depending on a UAV camera footprint.Then,the coverage path planning problem is formulated,where the exact solution is determined using the CPLEX solver.For small-scale problems,the CPLEX shows a better solution in a reasonable time.However,the CPLEX solver fails to generate the solution within a reasonable time for large-scale problems.Thus,to solve the model for large-scale problems,simulated annealing forCPP is developed.The results show that heuristic approaches yield a better solution for large-scale problems within amuch shorter execution time than the CPLEX solver.Finally,we compare the simulated annealing against the greedy algorithm.The results show that simulated annealing outperforms the greedy algorithm in generating better solution quality.展开更多
It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the bous...It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .展开更多
We propose a novel parameter value selection strategy for the Lüsystem to construct a chaotic robot to accomplish the complete coverage path planning(CCPP)task.The algorithm can meet the requirements of high rand...We propose a novel parameter value selection strategy for the Lüsystem to construct a chaotic robot to accomplish the complete coverage path planning(CCPP)task.The algorithm can meet the requirements of high randomness and coverage rate to perform specific types of missions.First,we roughly determine the value range of the parameter of the Lüsystem to meet the requirement of being a dissipative system.Second,we calculate the Lyapunov exponents to narrow the value range further.Next,we draw the phase planes of the system to approximately judge the topological distribution characteristics of its trajectories.Furthermore,we calculate the Pearson correlation coefficient of the variable for those good ones to judge its random characteristics.Finally,we construct a chaotic robot using variables with the determined parameter values and simulate and test the coverage rate to study the relationship between the coverage rate and the random characteristics of the variables.The above selection strategy gradually narrows the value range of the system parameter according to the randomness requirement of the coverage trajectory.Using the proposed strategy,proper variables can be chosen with a larger Lyapunov exponent to construct a chaotic robot with a higher coverage rate.Another chaotic system,the Lorenz system,is used to verify the feasibility and effectiveness of the designed strategy.The proposed strategy for enhancing the coverage rate of the mobile robot can improve the efficiency of accomplishing CCPP tasks under specific types of missions.展开更多
A coverage path planning algorithm is proposed for discrete harvesting in cashew orchards.The main challenge in such an orchard is the collection of fruits and nuts lying on the floor.The manual collection of fruits a...A coverage path planning algorithm is proposed for discrete harvesting in cashew orchards.The main challenge in such an orchard is the collection of fruits and nuts lying on the floor.The manual collection of fruits and nuts is both time consuming and labour intensive.The scenario begs for automated collection of fruits and nuts.There are methods developed in research for continuous crop fields,but none for discrete coverage.The problem is visualized as a graph traversal problem and paths for autonomous maneuvering are generated.A novel Mahalanobis distance based partitioning approach for performing coverage is introduced.The proposed path planner was able to achieve a mean coverage of 52.78 percentage with a deviation of 18.95 percentage between the best and worst solutions.Optimization of the generated paths is achieved through a combination of local and global search techniques.This was implemented by combining a discrete invasive weed optimization technique with an improved 2-Opt operator.A case study is formulated for the fruit picking operations in the orchards of Puducherry.The performance of the proposed algorithm is benchmarked against existing methods and also with performance metrics such as convergence rate,convergence diversity and deviation ratio.The convergence rate was observed to be 99.97 percent and 97.83 percent for a dataset with 48 and 442 nodes respectively.The deviation ratio was 0.02 percent and 2.16 percent,with a convergence diversity of 1.18 percent and 30.14 percent for datasets with 48 and 442 nodes.The achieved solutions was on par with the global best solutions achieved so far for the test datasets.展开更多
We propose a contraction transformation algorithm to plan a complete coverage trajectory for a mobile robot to ac-complish specific types of missions based on the Arnold dynamical system. First, we construct a chaotic...We propose a contraction transformation algorithm to plan a complete coverage trajectory for a mobile robot to ac-complish specific types of missions based on the Arnold dynamical system. First, we construct a chaotic mobile robot by com-bining the variable z of the Arnold equation and the kinematic equation of the robot. Second, we construct the candidate sets including the initial points with a relatively high coverage rate of the constructed mobile robot. Then the trajectory is contracted to the current position of the robot based on the designed contraction transformation strategy, to form a continuous complete cov-erage trajectory to execute the specific types of missions. Compared with the traditional method, the designed algorithm requires no obstacle avoidance to the boundary of the given workplace, possesses a high coverage rate, and keeps the chaotic characteristics of the produced coverage trajectory relatively unchanged, which enables the robot to accomplish special missions with features of completeness, randomness, or unpredictability.展开更多
基金supported by the National Natural Science Foundation of China (61903036, 61822304)Shanghai Municipal Science and Technology Major Project (2021SHZDZX0100)。
文摘Collaborative coverage path planning(CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle(UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment.Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with patternbased genetic algorithm(PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.
基金funded by Project Number INML2104 under the Interdisci-Plinary Center of Smart Mobility and Logistics,KFUPM.
文摘Unmanned aerial vehicles(UAVs),commonly known as drones,have drawn significant consideration thanks to their agility,mobility,and flexibility features.They play a crucial role in modern reconnaissance,inspection,intelligence,and surveillance missions.Coverage path planning(CPP)which is one of the crucial aspects that determines an intelligent system’s quality seeks an optimal trajectory to fully cover the region of interest(ROI).However,the flight time of the UAV is limited due to a battery limitation and may not cover the whole region,especially in large region.Therefore,energy consumption is one of the most challenging issues that need to be optimized.In this paper,we propose an energy-efficient coverage path planning algorithm to solve the CPP problem.The objective is to generate a collision-free coverage path that minimizes the overall energy consumption and guarantees covering the whole region.To do so,the flight path is optimized and the number of turns is reduced to minimize the energy consumption.The proposed approach first decomposes the ROI into a set of cells depending on a UAV camera footprint.Then,the coverage path planning problem is formulated,where the exact solution is determined using the CPLEX solver.For small-scale problems,the CPLEX shows a better solution in a reasonable time.However,the CPLEX solver fails to generate the solution within a reasonable time for large-scale problems.Thus,to solve the model for large-scale problems,simulated annealing forCPP is developed.The results show that heuristic approaches yield a better solution for large-scale problems within amuch shorter execution time than the CPLEX solver.Finally,we compare the simulated annealing against the greedy algorithm.The results show that simulated annealing outperforms the greedy algorithm in generating better solution quality.
文摘It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments. .
基金Project supported by the National Natural Science Foundation of China(Nos.61973184 and 61473179)the Natural Science Foundation of Shandong Province,China(No.ZR2021MF072)。
文摘We propose a novel parameter value selection strategy for the Lüsystem to construct a chaotic robot to accomplish the complete coverage path planning(CCPP)task.The algorithm can meet the requirements of high randomness and coverage rate to perform specific types of missions.First,we roughly determine the value range of the parameter of the Lüsystem to meet the requirement of being a dissipative system.Second,we calculate the Lyapunov exponents to narrow the value range further.Next,we draw the phase planes of the system to approximately judge the topological distribution characteristics of its trajectories.Furthermore,we calculate the Pearson correlation coefficient of the variable for those good ones to judge its random characteristics.Finally,we construct a chaotic robot using variables with the determined parameter values and simulate and test the coverage rate to study the relationship between the coverage rate and the random characteristics of the variables.The above selection strategy gradually narrows the value range of the system parameter according to the randomness requirement of the coverage trajectory.Using the proposed strategy,proper variables can be chosen with a larger Lyapunov exponent to construct a chaotic robot with a higher coverage rate.Another chaotic system,the Lorenz system,is used to verify the feasibility and effectiveness of the designed strategy.The proposed strategy for enhancing the coverage rate of the mobile robot can improve the efficiency of accomplishing CCPP tasks under specific types of missions.
基金The work was supported by University Grants Commission,India under the scheme NFOBC with grant no.F./201718/NF O201718OBCPON51035.The authors would like to thank the people of Namalavar Cashew Farmers Association,Puducherry for their inputs.
文摘A coverage path planning algorithm is proposed for discrete harvesting in cashew orchards.The main challenge in such an orchard is the collection of fruits and nuts lying on the floor.The manual collection of fruits and nuts is both time consuming and labour intensive.The scenario begs for automated collection of fruits and nuts.There are methods developed in research for continuous crop fields,but none for discrete coverage.The problem is visualized as a graph traversal problem and paths for autonomous maneuvering are generated.A novel Mahalanobis distance based partitioning approach for performing coverage is introduced.The proposed path planner was able to achieve a mean coverage of 52.78 percentage with a deviation of 18.95 percentage between the best and worst solutions.Optimization of the generated paths is achieved through a combination of local and global search techniques.This was implemented by combining a discrete invasive weed optimization technique with an improved 2-Opt operator.A case study is formulated for the fruit picking operations in the orchards of Puducherry.The performance of the proposed algorithm is benchmarked against existing methods and also with performance metrics such as convergence rate,convergence diversity and deviation ratio.The convergence rate was observed to be 99.97 percent and 97.83 percent for a dataset with 48 and 442 nodes respectively.The deviation ratio was 0.02 percent and 2.16 percent,with a convergence diversity of 1.18 percent and 30.14 percent for datasets with 48 and 442 nodes.The achieved solutions was on par with the global best solutions achieved so far for the test datasets.
基金Project supported by the National Natural Science Foundation of China(Nos.61473179,61602280,and 61573213)the Natural Science Foundation of Shandong Province,China(Nos.ZR2017MF047,ZR2015CM016,and ZR2014FM007)the Shandong University of Technology&Zibo City Integration Development Project,China(No.2018ZBXC295)。
文摘We propose a contraction transformation algorithm to plan a complete coverage trajectory for a mobile robot to ac-complish specific types of missions based on the Arnold dynamical system. First, we construct a chaotic mobile robot by com-bining the variable z of the Arnold equation and the kinematic equation of the robot. Second, we construct the candidate sets including the initial points with a relatively high coverage rate of the constructed mobile robot. Then the trajectory is contracted to the current position of the robot based on the designed contraction transformation strategy, to form a continuous complete cov-erage trajectory to execute the specific types of missions. Compared with the traditional method, the designed algorithm requires no obstacle avoidance to the boundary of the given workplace, possesses a high coverage rate, and keeps the chaotic characteristics of the produced coverage trajectory relatively unchanged, which enables the robot to accomplish special missions with features of completeness, randomness, or unpredictability.