To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic ...To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic Algorithm (AGA) to solve multi-agent path planning problems effectively. To enhance the real-time performance and computational efficiency of Multi-Agent Systems (MAS) in path planning, the AGA incorporates an Equal-Size Clustering Algorithm (ESCA) based on the K-means clustering method. The ESCA divides the primary task evenly into a series of subtasks, thereby reducing the gene length in the subsequent GA process. The algorithm then employs GA to solve each subtask sequentially. To evaluate the effectiveness of the proposed method, a simulation program was designed to perform path planning for 100 trajectories, and the results were compared with those of State-Of-The-Art (SOTA) methods. The simulation results demonstrate that, although the solutions provided by AGA are suboptimal, it exhibits significant advantages in terms of execution speed and solution stability compared to other algorithms.展开更多
Adaptive genetic algorithm A SA GA, a novel algorithm, which can dynamically modify the parameters of Genetic Algorithms in terms of simulated annealing mechanism, is proposed for path planning of loosely coordinated ...Adaptive genetic algorithm A SA GA, a novel algorithm, which can dynamically modify the parameters of Genetic Algorithms in terms of simulated annealing mechanism, is proposed for path planning of loosely coordinated multi robot manipulators. Over the task space of a multi robot, a strategy of decoupled planning is also applied to the evolutionary process, which enables a multi robot to avoid falling into deadlock and calculating of composite C space. Finally, two representative tests are given to validate A SA GA and the strategy of decoupled planning.展开更多
A novel approach for collision-free path planning of a multiple degree-of-freedom （DOF） articulated robot in a complex environment is proposed. Firstly, based on visual neighbor point （VNP）, a numerical artificial...A novel approach for collision-free path planning of a multiple degree-of-freedom （DOF） articulated robot in a complex environment is proposed. Firstly, based on visual neighbor point （VNP）, a numerical artificial potential field is constructed in Cartesian space, which provides the heuristic information, effective distance to the goal and the motion direction for the motion of the robot joints. Secondly, a genetic algorithm, combined with the heuristic rules, is used in joint space to determine a series of contiguous configurations piecewise from initial configuration until the goal configuration is attained. A simulation shows that the method can not only handle issues on path planning of the articulated robots in environment with complex obstacles, but also improve the efficiency and quality of path planning.展开更多
Mobile robot global path planning in a static environment is an important problem. The paper proposes a method of global path planning based on neural network and genetic algorithm. We constructed the neural network m...Mobile robot global path planning in a static environment is an important problem. The paper proposes a method of global path planning based on neural network and genetic algorithm. We constructed the neural network model of environmental information in the workspace for a robot and used this model to establish the relationship between a collision avoidance path and the output of the model. Then the two-dimensional coding for the path via-points was converted to one-dimensional one and the fitness of both the collision avoidance path and the shortest distance are integrated into a fitness function. The simulation results showed that the proposed method is correct and effective.展开更多
Presents a strategy for soccer robot path planning using genetic algorithms for which, real number coding method is used, to overcome the defects of binary coding method, and the double crossover operation adopted, to...Presents a strategy for soccer robot path planning using genetic algorithms for which, real number coding method is used, to overcome the defects of binary coding method, and the double crossover operation adopted, to avoid the common defect of early convergence and converge faster than the standard genetic algorithms concludes from simulation results that the method is effective for robot path planning.展开更多
A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK ...A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.展开更多
In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwa...In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwater vehicles were computed using a nnmerical solution of a nonlinear optimal control problem （NOCP）. An energy performance index as a cost function, which should be minimized, was defmed. The resulting problem was a two-point boundary value problem （TPBVP）. A genetic algorithm （GA）, particle swarm optimization （PSO）, and ant colony optimization （ACO） algorithms were applied to solve the resulting TPBVP. Applying an Euler-Lagrange equation to the NOCP, a conjugate gradient penalty method was also adopted to solve the TPBVP. The problem of energetic environments, involving some energy sources, was discussed. Some near-optimal paths were found using a GA, PSO, and ACO algorithms. Finally, the problem of collision avoidance in an energetic environment was also taken into account.展开更多
Based on the modeling of robot working environment, the shortest distance matrix between points is solved by Floyd algorithm. With the objective of minimizing the sum of the fixed cost of robot and the cost of robot o...Based on the modeling of robot working environment, the shortest distance matrix between points is solved by Floyd algorithm. With the objective of minimizing the sum of the fixed cost of robot and the cost of robot operation, an integer programming model is established and a genetic algorithm for solving the model is designed. In order to make coordination to accomplish their respective tasks for each robot with high efficiency, this paper uses natural number encoding way. The objective function is based on penalty term constructed with the total number of collisions in the running path of robots. The fitness function is constructed by using the objective function with penalty term. Based on elitist retention strategy, a genetic algorithm with collision detection is designed. Using this algorithm for task allocation and path planning of multi-robot, it can effectively avoid or reduce the number of collisions in the process of multi-robot performing tasks. Finally, an example is used to validate the method.展开更多
In this paper, a hybrid method based on rough sets and genetic algorithms, is proposed to improve the speed of robot path planning. Decision rules are obtained using rough set theory. A series of available paths are p...In this paper, a hybrid method based on rough sets and genetic algorithms, is proposed to improve the speed of robot path planning. Decision rules are obtained using rough set theory. A series of available paths are produced by training obtained minimal decision rules. Path populations are optimised by using genetic algorithms until the best path is obtained. Experiment results show that this hybrid method is capable of improving robot path planning speed.展开更多
An Approximate Voronoi Boundary Network is constructed as the environmental model by way of enlar-ging the obstacle raster. The connectivity of the path network under complex environment is ensured through build-ing t...An Approximate Voronoi Boundary Network is constructed as the environmental model by way of enlar-ging the obstacle raster. The connectivity of the path network under complex environment is ensured through build-ing the second order Approximate Voronoi Boundary Network after adding virtual obstacles at joint-close grids. Thismethod embodies the network structure of the free area of environment with less nodes, so the complexity of pathplanning problem is reduced largely. An optimized path for mobile robot under complex environment is obtainedthrough the Genetic Algorithm based on the elitist rule and re-optimized by using the path-tightening method. Sincethe elitist one has the only authority of crossover, the management of one group becomes simple, which makes forobtaining the optimized path quickly. The Approximate Voronoi Boundary Network has a good tolerance to the im-precise a priori information and the noises of sensors under complex environment. Especially it is robust in dealingwith the local or partial changes, so a small quantity of dynamic obstacles is difficult to alter the overall character ofits connectivity, which means that it can also be adopted in dynamic environment by fusing the local path planning.展开更多
The idea of dispatching multiple unmanned surface vehicles(USVs)to undertake marine missions has ignited a burgeoning enthusiasm on a global scale.Embarking on a quest to facilitate inland water monitoring,this paper ...The idea of dispatching multiple unmanned surface vehicles(USVs)to undertake marine missions has ignited a burgeoning enthusiasm on a global scale.Embarking on a quest to facilitate inland water monitoring,this paper presents a systematical approach concerning global path planning and path following for heterogeneous USVs.Specifically,by capturing the heterogeneous nature,an extended multiple travelling salesman problem(EMTSP)model,which seamlessly bridges the gap between various disparate constraints and optimization objectives,is formulated for the first time.Then,a novel Greedy Partheno Genetic Algorithm(GPGA)is devised to consistently address the problem from two aspects:(1)Incorporating the greedy randomized initialization and local exploration strategy,GPGA merits strong global and local searching ability,providing high-quality solutions for EMTSP.(2)A novel mutation strategy which not only inherits all advantages of PGA but also maintains the best individual in the offspring is devised,contributing to the local escaping efficiently.Finally,to track the waypoint permutations generated by GPGA,control input is generated by the nonlinear model predictive controller(NMPC),ensuring the USV corresponds with the reference path and smoothen the motion under constrained dynamics.Simulations and comparisons in various scenarios demonstrated the effectiveness and superiority of the proposed scheme.展开更多
Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassem...Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassembly sequence planning problems efficiently, a product disassembly hybrid graph model, which describes the connection, non-connection and precedence relationships between the product parts, is established based on the characteristic of disassembly. Farther, the optimization model is provided to optimize disassembly sequence. And the solution methodology based on the genetic/simulated annealing algorithm with binaxy-tree algorithm is given. Finally, an example is analyzed in detail, and the result shows that the model is correct and efficient.展开更多
In recent years,the crop protection unmanned aerial vehicle(UAV)has been raised great attention around the world due to the advantages of more efficient operation and lower requirement of special landing airport.Howev...In recent years,the crop protection unmanned aerial vehicle(UAV)has been raised great attention around the world due to the advantages of more efficient operation and lower requirement of special landing airport.However,there are few researches on obstacle-avoiding path planning for crop protection UAV.In this study,an improved Dubins curve algorithm was proposed for path planning with multiple obstacle constraints.First,according to the flight parameters of UAV and the types of obstacles in the field,the obstacle circle model and the small obstacle model were established.Second,after selecting the appropriate Dubins curve to generate the obstacle-avoiding path for multiple obstacles,the genetic algorithm(GA)was used to search the optimal obstacle-avoiding path.Third,for turning in the path planning,a strategy considering the size of the spray width and the UAV’s minimum turning radius was presented,which could decrease the speed change times.The results showed that the proposed algorithm can decrease the area of overlap and skip to 205.1%,while the path length increased by only 1.6%in comparison with the traditional Dubins obstacle-avoiding algorithm under the same conditions.With the increase of obstacle radius,the area of overlap and skip reduced effectively with no significant increase in path length.Therefore,the algorithm can efficiently improve the validity of path planning with multiple obstacle constraints and ensure the safety of flight.展开更多
Optimal path planning involves finding a feasible state sequence between a start and a goal that optimizes an objective.This process relies on heuristic functions to guide the search direction.While a robust function ...Optimal path planning involves finding a feasible state sequence between a start and a goal that optimizes an objective.This process relies on heuristic functions to guide the search direction.While a robust function can improve search efficiency and solution quality,current methods often overlook available environmental data and simplify the function structure due to the complexity of information relationships.This study introduces Genetic Informed Trees(GIT^(*)),which improves upon Effort Informed Trees(EIT^(*))by integrating a wider array of environmental data,such as repulsive forces from obstacles and the dynamic importance of vertices,to refine heuristic functions for better guidance.Furthermore,we integrated reinforced genetic programming(RGP),which combines genetic programming with reward system feedback to mutate genotype-generative heuristic functions for GIT^(*).RGP leverages a multitude of data types,thereby improving computational efficiency and solution quality within a set timeframe.Comparative analyses demonstrate that GIT^(*)surpasses existing single-query.sampling-based planners in problems ranging from R^(4)to R^(16)and was tested on a real-world mobile manipulation task.展开更多
文摘To address the shortcomings of traditional Genetic Algorithm (GA) in multi-agent path planning, such as prolonged planning time, slow convergence, and solution instability, this paper proposes an Asynchronous Genetic Algorithm (AGA) to solve multi-agent path planning problems effectively. To enhance the real-time performance and computational efficiency of Multi-Agent Systems (MAS) in path planning, the AGA incorporates an Equal-Size Clustering Algorithm (ESCA) based on the K-means clustering method. The ESCA divides the primary task evenly into a series of subtasks, thereby reducing the gene length in the subsequent GA process. The algorithm then employs GA to solve each subtask sequentially. To evaluate the effectiveness of the proposed method, a simulation program was designed to perform path planning for 100 trajectories, and the results were compared with those of State-Of-The-Art (SOTA) methods. The simulation results demonstrate that, although the solutions provided by AGA are suboptimal, it exhibits significant advantages in terms of execution speed and solution stability compared to other algorithms.
文摘Adaptive genetic algorithm A SA GA, a novel algorithm, which can dynamically modify the parameters of Genetic Algorithms in terms of simulated annealing mechanism, is proposed for path planning of loosely coordinated multi robot manipulators. Over the task space of a multi robot, a strategy of decoupled planning is also applied to the evolutionary process, which enables a multi robot to avoid falling into deadlock and calculating of composite C space. Finally, two representative tests are given to validate A SA GA and the strategy of decoupled planning.
文摘A novel approach for collision-free path planning of a multiple degree-of-freedom （DOF） articulated robot in a complex environment is proposed. Firstly, based on visual neighbor point （VNP）, a numerical artificial potential field is constructed in Cartesian space, which provides the heuristic information, effective distance to the goal and the motion direction for the motion of the robot joints. Secondly, a genetic algorithm, combined with the heuristic rules, is used in joint space to determine a series of contiguous configurations piecewise from initial configuration until the goal configuration is attained. A simulation shows that the method can not only handle issues on path planning of the articulated robots in environment with complex obstacles, but also improve the efficiency and quality of path planning.
基金Project supported by the National Natural Science Foundation of China (No. 60105003) and the Natural Science Foundation of Zhejiang Province (No. 600025), China
文摘Mobile robot global path planning in a static environment is an important problem. The paper proposes a method of global path planning based on neural network and genetic algorithm. We constructed the neural network model of environmental information in the workspace for a robot and used this model to establish the relationship between a collision avoidance path and the output of the model. Then the two-dimensional coding for the path via-points was converted to one-dimensional one and the fitness of both the collision avoidance path and the shortest distance are integrated into a fitness function. The simulation results showed that the proposed method is correct and effective.
文摘Presents a strategy for soccer robot path planning using genetic algorithms for which, real number coding method is used, to overcome the defects of binary coding method, and the double crossover operation adopted, to avoid the common defect of early convergence and converge faster than the standard genetic algorithms concludes from simulation results that the method is effective for robot path planning.
文摘A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.
文摘In this paper, an underwater vehicle was modeled with six dimensional nonlinear equations of motion, controlled by DC motors in all degrees of freedom. Near-optimal trajectories in an energetic environment for underwater vehicles were computed using a nnmerical solution of a nonlinear optimal control problem （NOCP）. An energy performance index as a cost function, which should be minimized, was defmed. The resulting problem was a two-point boundary value problem （TPBVP）. A genetic algorithm （GA）, particle swarm optimization （PSO）, and ant colony optimization （ACO） algorithms were applied to solve the resulting TPBVP. Applying an Euler-Lagrange equation to the NOCP, a conjugate gradient penalty method was also adopted to solve the TPBVP. The problem of energetic environments, involving some energy sources, was discussed. Some near-optimal paths were found using a GA, PSO, and ACO algorithms. Finally, the problem of collision avoidance in an energetic environment was also taken into account.
基金Supported by National Natural Science Foundation of P.R.China(50275150)National Research Foundation for the Doctoral Program of Higher Education of P.R.China(20040533035)
文摘Based on the modeling of robot working environment, the shortest distance matrix between points is solved by Floyd algorithm. With the objective of minimizing the sum of the fixed cost of robot and the cost of robot operation, an integer programming model is established and a genetic algorithm for solving the model is designed. In order to make coordination to accomplish their respective tasks for each robot with high efficiency, this paper uses natural number encoding way. The objective function is based on penalty term constructed with the total number of collisions in the running path of robots. The fitness function is constructed by using the objective function with penalty term. Based on elitist retention strategy, a genetic algorithm with collision detection is designed. Using this algorithm for task allocation and path planning of multi-robot, it can effectively avoid or reduce the number of collisions in the process of multi-robot performing tasks. Finally, an example is used to validate the method.
基金This project is partially supported by Science Research Funding from the Education Department of Liaoning Province, China (No.J9906065).
文摘In this paper, a hybrid method based on rough sets and genetic algorithms, is proposed to improve the speed of robot path planning. Decision rules are obtained using rough set theory. A series of available paths are produced by training obtained minimal decision rules. Path populations are optimised by using genetic algorithms until the best path is obtained. Experiment results show that this hybrid method is capable of improving robot path planning speed.
基金Project (60234030) supported by the National Natural Science Foundation of China
文摘An Approximate Voronoi Boundary Network is constructed as the environmental model by way of enlar-ging the obstacle raster. The connectivity of the path network under complex environment is ensured through build-ing the second order Approximate Voronoi Boundary Network after adding virtual obstacles at joint-close grids. Thismethod embodies the network structure of the free area of environment with less nodes, so the complexity of pathplanning problem is reduced largely. An optimized path for mobile robot under complex environment is obtainedthrough the Genetic Algorithm based on the elitist rule and re-optimized by using the path-tightening method. Sincethe elitist one has the only authority of crossover, the management of one group becomes simple, which makes forobtaining the optimized path quickly. The Approximate Voronoi Boundary Network has a good tolerance to the im-precise a priori information and the noises of sensors under complex environment. Especially it is robust in dealingwith the local or partial changes, so a small quantity of dynamic obstacles is difficult to alter the overall character ofits connectivity, which means that it can also be adopted in dynamic environment by fusing the local path planning.
基金supported by the College of Civil Engineering and Architecture in Zhejiang University.
文摘The idea of dispatching multiple unmanned surface vehicles(USVs)to undertake marine missions has ignited a burgeoning enthusiasm on a global scale.Embarking on a quest to facilitate inland water monitoring,this paper presents a systematical approach concerning global path planning and path following for heterogeneous USVs.Specifically,by capturing the heterogeneous nature,an extended multiple travelling salesman problem(EMTSP)model,which seamlessly bridges the gap between various disparate constraints and optimization objectives,is formulated for the first time.Then,a novel Greedy Partheno Genetic Algorithm(GPGA)is devised to consistently address the problem from two aspects:(1)Incorporating the greedy randomized initialization and local exploration strategy,GPGA merits strong global and local searching ability,providing high-quality solutions for EMTSP.(2)A novel mutation strategy which not only inherits all advantages of PGA but also maintains the best individual in the offspring is devised,contributing to the local escaping efficiently.Finally,to track the waypoint permutations generated by GPGA,control input is generated by the nonlinear model predictive controller(NMPC),ensuring the USV corresponds with the reference path and smoothen the motion under constrained dynamics.Simulations and comparisons in various scenarios demonstrated the effectiveness and superiority of the proposed scheme.
基金supported by the National High Technology Research and Development Program of China(2006AA04Z427).
文摘Disassembly sequence planning （DSP） plays a significant role in maintenance planning of the aircraft. It is used during the design stage for the analysis of maintainability of the aircraft. To solve product disassembly sequence planning problems efficiently, a product disassembly hybrid graph model, which describes the connection, non-connection and precedence relationships between the product parts, is established based on the characteristic of disassembly. Farther, the optimization model is provided to optimize disassembly sequence. And the solution methodology based on the genetic/simulated annealing algorithm with binaxy-tree algorithm is given. Finally, an example is analyzed in detail, and the result shows that the model is correct and efficient.
基金This research was supported by Natural Science Foundation of Heilongjiang Province of China(No.C2018023)China Postdoctoral Science Foundation(No.2015M580254,No.2017T100221)+1 种基金Heilongjiang Postdoctoral Science Foundation(No.LBH-Z15011)The authors would like to thank the anonymous reviewers for their helpful suggestions,which greatly improved the paper.
文摘In recent years,the crop protection unmanned aerial vehicle(UAV)has been raised great attention around the world due to the advantages of more efficient operation and lower requirement of special landing airport.However,there are few researches on obstacle-avoiding path planning for crop protection UAV.In this study,an improved Dubins curve algorithm was proposed for path planning with multiple obstacle constraints.First,according to the flight parameters of UAV and the types of obstacles in the field,the obstacle circle model and the small obstacle model were established.Second,after selecting the appropriate Dubins curve to generate the obstacle-avoiding path for multiple obstacles,the genetic algorithm(GA)was used to search the optimal obstacle-avoiding path.Third,for turning in the path planning,a strategy considering the size of the spray width and the UAV’s minimum turning radius was presented,which could decrease the speed change times.The results showed that the proposed algorithm can decrease the area of overlap and skip to 205.1%,while the path length increased by only 1.6%in comparison with the traditional Dubins obstacle-avoiding algorithm under the same conditions.With the increase of obstacle radius,the area of overlap and skip reduced effectively with no significant increase in path length.Therefore,the algorithm can efficiently improve the validity of path planning with multiple obstacle constraints and ensure the safety of flight.
文摘Optimal path planning involves finding a feasible state sequence between a start and a goal that optimizes an objective.This process relies on heuristic functions to guide the search direction.While a robust function can improve search efficiency and solution quality,current methods often overlook available environmental data and simplify the function structure due to the complexity of information relationships.This study introduces Genetic Informed Trees(GIT^(*)),which improves upon Effort Informed Trees(EIT^(*))by integrating a wider array of environmental data,such as repulsive forces from obstacles and the dynamic importance of vertices,to refine heuristic functions for better guidance.Furthermore,we integrated reinforced genetic programming(RGP),which combines genetic programming with reward system feedback to mutate genotype-generative heuristic functions for GIT^(*).RGP leverages a multitude of data types,thereby improving computational efficiency and solution quality within a set timeframe.Comparative analyses demonstrate that GIT^(*)surpasses existing single-query.sampling-based planners in problems ranging from R^(4)to R^(16)and was tested on a real-world mobile manipulation task.
