[转载]【计算机科学】【2019.05】高维空间中的路径规划算法

1.一种在任意维n中利用多尺度信息的路径规划算法（MSPP算法），它将以前仅限于2D问题的公式扩展到任意维。该算法被证明是完整的，并且该算法所使用的底层多尺度数据结构可以直接与感知算法协同工作，以实现实时应用。理论分析表明，该算法的复杂度从指数级降低到线性。

2.MSPP算法（MSPP-S算法）的概率实现。此变体允许使用MSPP算法，而无需先验的多尺度数据结构。用抽样方法估计障碍物概率，并给出了完备概率的界。无需构建多尺度数据结构，算法的运行时间减少了多个数量级。

3.展示了基于抽样的规划算法收敛性的数值实验（超立方体对角实验）。实验结果表明这些算法的收敛极限是搜索空间维数的函数，与理论分析相吻合：收敛所需的样本数随搜索空间的维数呈指数增长。

4.通过一种优化设置在搜索空间中重新定位样本来减少函数值的误差。结果表明，该优化算法易于计算，特定样本的梯度只需要局部信息。优化结果良好，特别是恢复了多边形障碍物最短路径的可见性图。

5.一种基于采样的算法（DRRT算法），它在快速探索随机树的框架内集成了函数值误差的优化。DRRT算法保持了对RRT族搜索空间的快速探索，以快速找到第一个解，同时增加了优化步骤，提高了算法的收敛速度。

Path-planningcovers a wide range of applications, from fifinding the trajectory of an agentin a video game, to understanding how protein folds, to driving autonomousrobots in a warehouse, or fifinding a trajectory that avoids cars andpedestrians for a self-driving car. Three main characteristics are often lookedfor in the solution of a path-planning algorithm: (1) the solution should avoidcollisions with obstacles, (2) the solution should be dynamically feasible, and(3) the solution should be optimal (with the optimality criterion depending onthe application: shortest length, fastest time, lowest energy consumption,passenger comfort, passenger safety,...).

Many formulationsexist depending on the type of system involved. One major distinction isbetween systems acting on a continuous search space versus systems acting on adiscrete search space. In both cases, the size of the search space affects howfast a solution can be found. For continuous spaces, the dimensionality of thespace is a major variable in how fast the solution converges. For discretespaces, the cardinality of the space is of prime importance: the worst-caseruntime increases linearly with the cardinality of the space, in the best case,or even faster, in the general case.

In this thesis, wepropose novel algorithms that take advantage of a multi-scale data structurerepresentation of the search-space in order to accelerate path-planning ondiscrete search spaces. We also make use of more conventional optimizationtechniques within sampling-based path-planning algorithms to increase theconvergence rate of these algorithms.

The maincontributions of this thesis are:

1. A path-planning algorithm (the MSPP algorithm) that exploitsmulti-scale information in any dimension n. This extends previous formulations, which were limited to 2D problems,to any dimension. The algorithm is proven to be complete and the underlyingmulti-scale data structure used by the algorithm is shown to work directly withperception algorithms for real-time applications. A theoretical analysis demonstratesthe reduction of the complexity from exponential to linear.

2. A probabilisticimplementation of the MSPP algorithm (the MSPP-S algorithm). This variantallows the use of the MSPP algorithm without an a priori multi-scale datastructure. Sampling is used to estimate the obstacle probabilities, and boundson the probability of losing completeness are derived. Removing the need tobuild the multi-scale data structure reduces the runtime of the algorithm bymultiple orders of magnitude.

3. A numericalexperiment to exhibit convergence properties of sampling-based planningalgorithms (the Hypercube Diagonal Experiment). This experiment shows theconvergence limits of these algorithms as a function of the dimension of thesearch space, and matches the theoretical analysis: the number of samplesrequired for convergence increases exponentially with the dimension of thesearch space.

4. An optimizationsetup to reduce the error of the value function by repositioning the samples inthe search space. The optimization is shown to be easily computable,specififically, the gradient for a specifific sample only requires localinformation. The optimization exhibits good results, in particular, it recoversthe visibility graph for a shortest path with polygonal obstacles.

5. Asampling-based algorithm (the DRRT algorithm) that integrates the optimizationof the error of the value function within the framework of Rapidly-exploringRandom Trees. The DRRT algorithm keeps the quick exploration of the searchspace from the RRT family in order to fifind a fifirst solution rapidly, whilethe added optimization step improves the convergence rate of the algorithm.

更多精彩文章请关注公众号：

http://wap.sciencenet.cn/blog-69686-1251786.html

全部精选博文导读

GMT+8, 2020-10-21 18:39