The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms o...The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms of configuration spaces. In this paper, we survey some of our recent work on solving two important challenges related to configuration spaces： ~ how to efficiently compute an approximate representation of high-dimensional configuration spaces; and how to efficiently perform geometric proximity and motion planning queries （n high-dimensional configuration spaces. We present new configuration space construction algorithms based on machine learning and geometric approximation techniques. These algorithms perform collision queries on many configuration samples. The collision query results are used to compute an approximate representation for the configuration space, which quickly converges to the exact configuration space. We also present parallel GPU-based algorithms to accelerate the performance of optimization and search computations in configuration spaces. In particular, we design efficient GPU-based parallel k-nearest neighbor and parallel collision detection algorithms and use these algorithms to accelerate motion planning.展开更多
This paper studies the multi-objective optimization of space station short-term mission planning(STMP), which aims to obtain a mission-execution plan satisfying multiple planning demands. The planning needs to allocat...This paper studies the multi-objective optimization of space station short-term mission planning(STMP), which aims to obtain a mission-execution plan satisfying multiple planning demands. The planning needs to allocate the execution time effectively, schedule the on-board astronauts properly, and arrange the devices reasonably. The STMP concept models for problem definitions and descriptions are presented, and then an STMP multi-objective planning model is developed. To optimize the STMP problem, a Non-dominated Sorting Genetic Algorithm II(NSGA-II) is adopted and then improved by incorporating an iterative conflict-repair strategy based on domain knowledge. The proposed approach is demonstrated by using a test case with thirty-five missions, eighteen devices and three astronauts. The results show that the established STMP model is effective, and the improved NSGA-II can successfully obtain the multi-objective optimal plans satisfying all constraints considered. Moreover, through contrast tests on solving the STMP problem, the NSGA-II shows a very competitive performance with respect to the Strength Pareto Evolutionary Algorithm II(SPEA-II) and the Multi-objective Particle Swarm Optimization(MOPSO).展开更多
基金partially supported by the Army Research Office,the National Science Foundation,Willow Garagethe Seed Funding Programme for Basic Research at the University of Hong Kong
文摘The configuration space is a fundamental concept that is widely used in algorithmic robotics. Many applications in robotics, computer-aided design, and related areas can be reduced to computational problems in terms of configuration spaces. In this paper, we survey some of our recent work on solving two important challenges related to configuration spaces： ~ how to efficiently compute an approximate representation of high-dimensional configuration spaces; and how to efficiently perform geometric proximity and motion planning queries （n high-dimensional configuration spaces. We present new configuration space construction algorithms based on machine learning and geometric approximation techniques. These algorithms perform collision queries on many configuration samples. The collision query results are used to compute an approximate representation for the configuration space, which quickly converges to the exact configuration space. We also present parallel GPU-based algorithms to accelerate the performance of optimization and search computations in configuration spaces. In particular, we design efficient GPU-based parallel k-nearest neighbor and parallel collision detection algorithms and use these algorithms to accelerate motion planning.
基金supported by the National Natural Science Foundation of China(Grant No.11402295)the Science Project of National University of Defense Technology(Grant No.JC14-01-05)the Hunan Provincial Natural Science Foundation of China(Grant No.2015JJ3020)
文摘This paper studies the multi-objective optimization of space station short-term mission planning(STMP), which aims to obtain a mission-execution plan satisfying multiple planning demands. The planning needs to allocate the execution time effectively, schedule the on-board astronauts properly, and arrange the devices reasonably. The STMP concept models for problem definitions and descriptions are presented, and then an STMP multi-objective planning model is developed. To optimize the STMP problem, a Non-dominated Sorting Genetic Algorithm II(NSGA-II) is adopted and then improved by incorporating an iterative conflict-repair strategy based on domain knowledge. The proposed approach is demonstrated by using a test case with thirty-five missions, eighteen devices and three astronauts. The results show that the established STMP model is effective, and the improved NSGA-II can successfully obtain the multi-objective optimal plans satisfying all constraints considered. Moreover, through contrast tests on solving the STMP problem, the NSGA-II shows a very competitive performance with respect to the Strength Pareto Evolutionary Algorithm II(SPEA-II) and the Multi-objective Particle Swarm Optimization(MOPSO).
