In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking....In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking.While Multi-Degree-of-Freedom(MDOF)manipulators offer kinematic redundancy,aiding in the derivation of optimal inverse kinematic solutions to meet position and posture requisites,their path planning entails intricate multiobjective optimization,encompassing path,posture,and joint motion optimization.Achieving satisfactory results in practical scenarios remains challenging.In response,this study introduces a novel Reverse Path Planning(RPP)methodology tailored for industrial manipulators.The approach commences by conceptualizing the manipulator’s end-effector as an agent within a reinforcement learning(RL)framework,wherein the state space,action set,and reward function are precisely defined to expedite the search for an initial collision-free path.To enhance convergence speed,the Q-learning algorithm in RL is augmented with Dyna-Q.Additionally,we formulate the cylindrical bounding box of the manipulator based on its Denavit-Hartenberg(DH)parameters and propose a swift collision detection technique.Furthermore,the motion performance of the end-effector is refined through a bidirectional search,and joint weighting coefficients are introduced to mitigate motion in high-power joints.The efficacy of the proposed RPP methodology is rigorously examined through extensive simulations conducted on a six-degree-of-freedom(6-DOF)manipulator encountering two distinct obstacle configurations and target positions.Experimental results substantiate that the RPP method adeptly orchestrates the computation of the shortest collision-free path while adhering to specific posture constraints at the target point.Moreover,itminimizes both posture angle deviations and joint motion,showcasing its prowess in enhancing the operational performance of MDOF industrial manipulators.展开更多
A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in t...A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.展开更多
Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effecti...Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.展开更多
Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travell...Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost,and not the path simplicity.To balance these factors,this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy.The proposed algorithm started searching from a starting point,and expanded layer by layer through searching zero-level reachable points until the endpoint is found,and then deleted unnecessary points in the reverse direction.The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points,and form a fewestturn-path graph(G^(*)).After that,a classic Dijkstra shortest path algorithm was executed on the G^(*) to obtain a fewestturn-and-shortest path.Comparing with the shortest path in Baidu map,the algorithm in this work has less than half of the turns but the nearly same length.The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.62001199Fujian Province Nature Science Foundation under Grant No.2023J01925.
文摘In the domain of autonomous industrial manipulators,precise positioning and appropriate posture selection in path planning are pivotal for tasks involving obstacle avoidance,such as handling,heat sealing,and stacking.While Multi-Degree-of-Freedom(MDOF)manipulators offer kinematic redundancy,aiding in the derivation of optimal inverse kinematic solutions to meet position and posture requisites,their path planning entails intricate multiobjective optimization,encompassing path,posture,and joint motion optimization.Achieving satisfactory results in practical scenarios remains challenging.In response,this study introduces a novel Reverse Path Planning(RPP)methodology tailored for industrial manipulators.The approach commences by conceptualizing the manipulator’s end-effector as an agent within a reinforcement learning(RL)framework,wherein the state space,action set,and reward function are precisely defined to expedite the search for an initial collision-free path.To enhance convergence speed,the Q-learning algorithm in RL is augmented with Dyna-Q.Additionally,we formulate the cylindrical bounding box of the manipulator based on its Denavit-Hartenberg(DH)parameters and propose a swift collision detection technique.Furthermore,the motion performance of the end-effector is refined through a bidirectional search,and joint weighting coefficients are introduced to mitigate motion in high-power joints.The efficacy of the proposed RPP methodology is rigorously examined through extensive simulations conducted on a six-degree-of-freedom(6-DOF)manipulator encountering two distinct obstacle configurations and target positions.Experimental results substantiate that the RPP method adeptly orchestrates the computation of the shortest collision-free path while adhering to specific posture constraints at the target point.Moreover,itminimizes both posture angle deviations and joint motion,showcasing its prowess in enhancing the operational performance of MDOF industrial manipulators.
基金The National Natural Science Foundation of China(No.70772059)Youth Science and Technology Innovation Foundation of Nanjing Agriculture University(No.KJ06029)
文摘A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.
基金Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of ChinaProject supported by the Program for New Century Excellent Talents in University of ChinaProjects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China
文摘Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.
基金This research was supported by the National Natural Science Foundation of China(Nos.41471332 and 41101354)the National High Technology Research and Development Program of China(863 Program)(No.2013AA12A302)+1 种基金the Fundamental Research Funds for the Central Universities(No.ZYGX2011J077)the Fund of China Scholarship Council.
文摘Many cognitive studies have indicated that the path simplicity may be as important as its distance travelled.However,the optimality of paths for current navigation system is often judged purely on the distance travelled or time cost,and not the path simplicity.To balance these factors,this paper presented an algorithm to compute a path that not only possesses fewest turns but also is as short as possible by utilizing the breadth-first-search strategy.The proposed algorithm started searching from a starting point,and expanded layer by layer through searching zero-level reachable points until the endpoint is found,and then deleted unnecessary points in the reverse direction.The forward searching and backward cleaning strategies were presented to build a hierarchical graph of zero-level reachable points,and form a fewestturn-path graph(G^(*)).After that,a classic Dijkstra shortest path algorithm was executed on the G^(*) to obtain a fewestturn-and-shortest path.Comparing with the shortest path in Baidu map,the algorithm in this work has less than half of the turns but the nearly same length.The proposed fewest-turn-and-shortest path algorithm is proved to be more suitable for human beings according to human cognition research.
