A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on th...A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on the parent/child relationships among the tool-path loops （TPLs） is presented. The direction, tool-path loop, leaf/branch, layer number, and the corresponding points of the TPL-tree are introduced. By defining TPL as a vector, and by traveling throughout the tree, a CPO tool-path without tool-retractions can be derived.展开更多
A new genetic algorithm named niche pseudo-parallel genetic algorithm （NPPGA） is presented for path evolution and genetic optimization of autonomous mobile robot. The NPPGA is an effective improvement to maintain th...A new genetic algorithm named niche pseudo-parallel genetic algorithm （NPPGA） is presented for path evolution and genetic optimization of autonomous mobile robot. The NPPGA is an effective improvement to maintain the population diversity as well for the sake of avoiding premature and strengthen parallelism of the population to accelerate the search process combined with niche genetic algorithms and pseudo-parallel genetic algorithms. The proposed approach is evaluated by robotic path optimization, which is a specific application of traveler salesman problem （TSP）. Experimental results indicated that a shortest path could be obtained in the practical traveling salesman problem named ＂Robot tour around Pekin＂, and the performance conducted by NPPGA is better than simple genetic algorithm （SGA） and distributed paralell genetic algorithms （DPGA）.展开更多
A novel path tracking controller for parallel parking based on active disturbance rejection control （ADRC） was presented in this paper. A second order ADRC controller was used to solve the path tracking robustness, ...A novel path tracking controller for parallel parking based on active disturbance rejection control （ADRC） was presented in this paper. A second order ADRC controller was used to solve the path tracking robustness, which can estimate and compensate model uncertainty caused by steering kinematics and disturbances caused by parking speed and steering system delay. Collision-free path planning technology was adopted to generate the reference path. The simulation results validate that the performance of the proposed path tracking controller is better than the conventional PID controller. The actual vehicle tests show that the proposed path tracking controller is effective and robust to model uncertainty and disturbances.展开更多
Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With p...Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.展开更多
On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP ...On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.展开更多
The similarity search is one of the fundamental components in time series data mining,e.g.clustering,classification,association rules mining.Many methods have been proposed to measure the similarity between time serie...The similarity search is one of the fundamental components in time series data mining,e.g.clustering,classification,association rules mining.Many methods have been proposed to measure the similarity between time series,including Euclidean distance,Manhattan distance,and dynamic time warping(DTW).In contrast,DTW has been suggested to allow more robust similarity measure and be able to find the optimal alignment in time series.However,due to its quadratic time and space complexity,DTW is not suitable for large time series datasets.Many improving algorithms have been proposed for DTW search in large databases,such as approximate search or exact indexed search.Unlike the previous modified algorithm,this paper presents a novel parallel scheme for fast similarity search based on DTW,which is called MRDTW(MapRedcuebased DTW).The experimental results show that our approach not only retained the original accuracy as DTW,but also greatly improved the efficiency of similarity measure in large time series.展开更多
Pathfinding is a kind of problem widely used in daily life. It is widely used in network games, map navigation and other fields. However, the traditional A* algorithm has some shortcomings, such as heuristic function ...Pathfinding is a kind of problem widely used in daily life. It is widely used in network games, map navigation and other fields. However, the traditional A* algorithm has some shortcomings, such as heuristic function needs to be designed according to different problems, path has many inflection points, and algorithm stability is poor. B* algorithm also has the shortcoming of inaccurate pathfinding. In order to solve the problems existing in A* and B* algorithms, obstacle avoidance regeneration mechanism, pre-exploration mechanism and equivalent waiting strategy are proposed. It adds a bidirectional parallel search mechanism to form an IBP-B* algorithm (Intelligent bi-directional parallel B* routing algorithm). The simulation results show that the speed of IBP-B* algorithm is 182% higher than that of A* algorithm and 366% higher than that of BFS algorithm. Meanwhile, compared with B* algorithm, IBP-B* algorithm improves the pathfinding accuracy of the algorithm.展开更多
在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境...在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境进行栅格化建模,使用改进的跳点搜索算法生成双向搜索的初始次优路径,为双向蚁群搜索提供初始搜索方向参考.其次,在双向并行蚁群搜索过程中采用改进的转移概率启发函数,该函数在确定下一个转移节点时考虑了避免AGV与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.展开更多
文摘A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on the parent/child relationships among the tool-path loops （TPLs） is presented. The direction, tool-path loop, leaf/branch, layer number, and the corresponding points of the TPL-tree are introduced. By defining TPL as a vector, and by traveling throughout the tree, a CPO tool-path without tool-retractions can be derived.
文摘A new genetic algorithm named niche pseudo-parallel genetic algorithm （NPPGA） is presented for path evolution and genetic optimization of autonomous mobile robot. The NPPGA is an effective improvement to maintain the population diversity as well for the sake of avoiding premature and strengthen parallelism of the population to accelerate the search process combined with niche genetic algorithms and pseudo-parallel genetic algorithms. The proposed approach is evaluated by robotic path optimization, which is a specific application of traveler salesman problem （TSP）. Experimental results indicated that a shortest path could be obtained in the practical traveling salesman problem named ＂Robot tour around Pekin＂, and the performance conducted by NPPGA is better than simple genetic algorithm （SGA） and distributed paralell genetic algorithms （DPGA）.
基金Supported by the National Natural Science Foundation of China(11072106,51005133,51375009)
文摘A novel path tracking controller for parallel parking based on active disturbance rejection control （ADRC） was presented in this paper. A second order ADRC controller was used to solve the path tracking robustness, which can estimate and compensate model uncertainty caused by steering kinematics and disturbances caused by parking speed and steering system delay. Collision-free path planning technology was adopted to generate the reference path. The simulation results validate that the performance of the proposed path tracking controller is better than the conventional PID controller. The actual vehicle tests show that the proposed path tracking controller is effective and robust to model uncertainty and disturbances.
文摘Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.
基金the National Natural Science Foundation of China under Grant No. 60671033.
文摘On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.
基金supported in part by National High-tech R&D Program of China under Grants No.2012AA012600,2011AA010702,2012AA01A401,2012AA01A402National Natural Science Foundation of China under Grant No.60933005+1 种基金National Science and Technology Ministry of China under Grant No.2012BAH38B04National 242 Information Security of China under Grant No.2011A010
文摘The similarity search is one of the fundamental components in time series data mining,e.g.clustering,classification,association rules mining.Many methods have been proposed to measure the similarity between time series,including Euclidean distance,Manhattan distance,and dynamic time warping(DTW).In contrast,DTW has been suggested to allow more robust similarity measure and be able to find the optimal alignment in time series.However,due to its quadratic time and space complexity,DTW is not suitable for large time series datasets.Many improving algorithms have been proposed for DTW search in large databases,such as approximate search or exact indexed search.Unlike the previous modified algorithm,this paper presents a novel parallel scheme for fast similarity search based on DTW,which is called MRDTW(MapRedcuebased DTW).The experimental results show that our approach not only retained the original accuracy as DTW,but also greatly improved the efficiency of similarity measure in large time series.
文摘Pathfinding is a kind of problem widely used in daily life. It is widely used in network games, map navigation and other fields. However, the traditional A* algorithm has some shortcomings, such as heuristic function needs to be designed according to different problems, path has many inflection points, and algorithm stability is poor. B* algorithm also has the shortcoming of inaccurate pathfinding. In order to solve the problems existing in A* and B* algorithms, obstacle avoidance regeneration mechanism, pre-exploration mechanism and equivalent waiting strategy are proposed. It adds a bidirectional parallel search mechanism to form an IBP-B* algorithm (Intelligent bi-directional parallel B* routing algorithm). The simulation results show that the speed of IBP-B* algorithm is 182% higher than that of A* algorithm and 366% higher than that of BFS algorithm. Meanwhile, compared with B* algorithm, IBP-B* algorithm improves the pathfinding accuracy of the algorithm.
文摘在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境进行栅格化建模,使用改进的跳点搜索算法生成双向搜索的初始次优路径,为双向蚁群搜索提供初始搜索方向参考.其次,在双向并行蚁群搜索过程中采用改进的转移概率启发函数,该函数在确定下一个转移节点时考虑了避免AGV与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.
