论文标题
用于分段线性运动计划的随机贪婪算法
A randomized greedy algorithm for piecewise linear motion planning
论文作者
论文摘要
我们描述并实施了一种随机算法，该算法输入了多面体，被认为是某些自动导向车辆$ \ MATHCAL {R} $的状态的空间，并输出了$ \ Mathcal {R} $的分段线性运动计划者的显式系统。该算法的设计方式使输出系统的基数概率关闭（用户选择的参数）以最小化。这是根据简单复杂性（SC）技术的第一个自动化解决方案，用于稳健的机器人运动计划，这是Farber拓扑复杂性TC的离散化。除了它对技术应用的相关性外，我们的工作还引起了与TC的其他离散方法不同的作品，SC模型可以重铸Farber的不变，而不必引入昂贵的细分。我们通过实际离散化Macías-Virgós和Mosquera-Lois对同位距离的概念来开发和实施我们的算法，从而涵盖了其他部分类别不变的计算机估计，例如Lusternik-Schnirelmann类别Polyhedra。
We describe and implement a randomized algorithm that inputs a polyhedron, thought of as the space of states of some automated guided vehicle $\mathcal{R}$, and outputs an explicit system of piecewise linear motion planners for $\mathcal{R}$. The algorithm is designed in such a way that the cardinality of the outputed system is probabilistically close (with parameters chosen by the user) to minimal possible. This yields the first automated solution for robust-to-noise robot motion planning in terms of simplicial complexity (SC) techniques, a discretization of Farber's topological complexity TC. Besides its relevance toward technological applications, our work revels that, unlike other discrete approaches to TC, the SC model can recast Farber's invariant without having to introduce costly subdivisions. We develop and implement our algorithm by actually discretizing Macías-Virgós and Mosquera-Lois' notion of homotopic distance, thus encompassing computer estimations of other sectional category invariants as well, such as the Lusternik-Schnirelmann category of polyhedra.
