Distributed collaborative complete coverage path planning based on hybrid strategy

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.

Search-Based Software Test Data Generation for Path Coverage Based on a Feedback-Directed Mechanism

Automatically generating test cases by evolutionary algorithms to satisfy the path coverage criterion has attracted much research attention in software testing.In the context of generating test cases to cover many target paths,the efficiency of existing methods needs to be further improved when infeasible or difficult paths exist in the program under test.This is because a significant amount of the search budget(i.e.,time allocated for the search to run)is consumed when computing fitness evaluations of individuals on infeasible or difficult paths.In this work,we present a feedback-directed mechanism that temporarily removes groups of paths from the target paths when no improvement is observed for these paths in subsequent generations.To fulfill this task,our strategy first organizes paths into groups.Then,in each generation,the objective scores of each individual for all paths in each group are summed up.For each group,the lowest value of the summed up objective scores among all individuals is assigned as the best aggregated score for a group.A group is removed when no improvement is observed in its best aggregated score over the last two generations.The experimental results show that the proposed approach can significantly improve path coverage rates for programs under test with infeasible or difficult paths in case of a limited search budget.In particular,the feedback-directed mechanism reduces wasting the search budget on infeasible paths or on difficult target paths that require many fitness evaluations before getting an improvement.

Energy-Efficient UAVs Coverage Path Planning Approach

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.

Complete Coverage Path Planning Based on Improved Area Division

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. .

Generating test data for both path coverage and fault detection using genetic algorithms

The aim of software testing is to find faults in a program under test, so generating test data that can expose the faults of a program is very important. To date, current stud- ies on generating test data for path coverage do not perform well in detecting low probability faults on the covered path. The automatic generation of test data for both path coverage and fault detection using genetic algorithms is the focus of this study. To this end, the problem is first formulated as a bi-objective optimization problem with one constraint whose objectives are the number of faults detected in the traversed path and the risk level of these faults, and whose constraint is that the traversed path must be the target path. An evolution- ary algorithm is employed to solve the formulated model, and several types of fault detection methods are given. Finally, the proposed method is applied to several real-world programs, and compared with a random method and evolutionary opti- mization method in the following three aspects： the number of generations and the time consumption needed to generate desired test data, and the success rate of detecting faults. The experimental results confirm that the proposed method can effectively generate test data that not only traverse the target path but also detect faults lying in it.

Parameter value selection strategy for complete coverage path planning based on the Lüsystem to perform specific types of missions

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.

Generating test data for both paths coverage and faults detection using genetic algorithms： multi-path case

Generating test data that can expose the faults of the program is an important issue in software testing. Al- though previous methods of covering path can generate test data to traverse target path, the test data generated by these methods are difficult in detecting some low-probabilistic faults that lie on the covered paths. We present a method of generating test data for covering multiple paths to detect faults in this study. First, we transform the problem of cover- ing multiple paths and detecting faults into a multi-objective optimization problem with constraint, and construct a mathe- matical model for it. Then, we give a strategy of solving the model based on a weighted genetic algorithm. Finally, we ap- ply our method to several real-world programs, and compare it with several methods. The experimental results confirm that the proposed method can more efficiently generate test data that not only traverse the target paths but also detect faults lying in them than other methods.

Complete coverage path planning for an Arnold system based mobile robot to perform specific types of missions

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.

A hybrid weed optimized coverage path planning technique for autonomous harvesting in cashew orchards

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.

A hierarchical multi-UAV cooperative framework for infrastructure inspection and reconstruction

Unmanned aerial vehicles(UAVs)are emerging as a powerful tool for inspections and repair works in large-scale and unstructured 3D infrastructures,but current approaches take a long time to cover the entire area.Planning using UAVs for inspections and repair works puts forward a requirement of improving time efficiency in large-scale and cluster environments.This paper presents a hierarchical multi-UAV cooperative framework for infrastructure inspection and reconstruction to balance the workload and reduce the overall task completion time.The proposed framework consists of two stages,the exploration stage and the exploitation stage,resolving the task in a sequential manner.At the exploration stage,the density map is developed to update global and local information for dynamic load-balanced area partition based on reconstructability and relative positions of UAVs,and the Voronoi-based planner is used to enable the UAVs to reach their best region.After obtaining the global map,viewpoints are generated and divided while taking into account the battery capacity of each UAV.Finally,a shortest path planning method is used to minimize the total traveling cost of these viewpoints for obtaining a high-quality reconstruction.Several experiments are conducted in both a simulated and real environment to show the time efficiency,robustness,and effectiveness of the proposed method.Furthermore,the whole system is implemented in real applications.