Soft subdivision motion planning for complex planar robots
Soft subdivision motion planning for complex planar robots
复制标题
DOI：
10.1016/j.comgeo.2020.101683
复制
发表时间：
2021-01-01
影响因子：
0.6
通讯作者：
Yap, Chee
中科院分区：
文献类型：
--
作者：
Zhou, Bo;Chiang, Yi-Jen;Yap, Chee
理论上的机器人运动计划算法的设计和实施具有挑战性。在分辨率 - 脱离算法的框架内，可以利用软谓词进行碰撞检测。软谓词的设计是它们的可实现性和其准确性/效果之间的平衡行为。在本文中，我们专注于具有任意复杂几何形状的平面多边形刚性机器人的类别。我们利用了此类机器人的软碰撞检测谓词的显着可分解性。我们引入了一种一般技术来产生这种分解。如果机器人是M-GON，则该方法的复杂性在M中线性缩放。这与O（M（3））的复杂性形成鲜明对比。因此，我们现在可以常规地为任何刚性多边形机器人产生软谓词。这导致在一般软细分搜索（SSS）框架中为此类机器人提供解决方案计划者。这是平面机器人的声音理论和完整计划者的重大进步。我们在开源核心库中实施了这种分解的谓词。实验表明，我们的算法是有效的，在非平凡的环境上实时执行，并且可以超越许多基于抽样的方法。 （c）2020 Elsevier B.V.保留所有权利。
The design and implementation of theoretically-sound robot motion planning algorithms is challenging. Within the framework of resolution-exact algorithms, it is possible to exploit soft predicates for collision detection. The design of soft predicates is a balancing act between their implementability and their accuracy/effectivity.In this paper, we focus on the class of planar polygonal rigid robots with arbitrarily complex geometry. We exploit the remarkable decomposability property of soft collision detection predicates of such robots. We introduce a general technique to produce such a decomposition. If the robot is an m-gon, the complexity of this approach scales linearly in m. This contrasts with the O (m(3)) complexity known for exact planners. It follows that we can now routinely produce soft predicates for any rigid polygonal robot. This results in resolution-exact planners for such robots within the general Soft Subdivision Search (SSS) framework. This is a significant advancement in the theory of sound and complete planners for planar robots.We implemented such decomposed predicates in our open-source Core Library. The experiments show that our algorithms are effective, perform in real time on non-trivial environments, and can outperform many sampling-based methods. (c) 2020 Elsevier B.V. All rights reserved.