平移式运动规划：计算几何在机器人避障中的应用

"陶文全的《计算流体力学与传热学》中涉及了平移式运动规划的问题，主要关注机器人在平面上的移动路径规划，特别是与计算几何相关的概念，如Minkowski和、多边形复杂度等。书中提到了Minkowski和的复杂度与多边形的关系，包括凸多边形和非凸多边形的组合情况。此外，还介绍了平移式运动规划中机器人的自由空间复杂度是线性的这一重要结论。该书引用了计算几何的经典著作《计算几何：算法与应用》的作者，包括Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars的工作，以及邓俊辉的翻译。" 在计算几何领域，平移式运动规划是解决机器人如何在充满障碍物的环境中有效移动的问题。本章重点关注的是机器人只能进行平移运动的情况，其中障碍物被表示为互不相交的多边形。Minkowski和是解决这个问题的关键工具，它是两个形状的几何操作，能够生成一个新的形状。定理13.11阐述了Minkowski和的复杂度与多边形顶点数量之间的关系，分为凸多边形、一个凸一个多边形非凸以及两个非凸多边形的组合情况。 对于平移式运动规划，每个障碍物Pi对应的C-障碍物是Minkowski和Pi ⊕ (-R)，其中-R表示机器人的相反位置。由于凸多边形的Minkowski和形成伪圆盘，这有助于简化问题并证明自由空间的复杂度是线性的，这意味着机器人可以找到一条穿越自由空间到达目标的简单路径，而无需处理过于复杂的几何结构。 书中还提及了其他计算几何的主题，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图和排列对偶等，这些都是解决机器人运动规划和其他相关问题的基础算法和技术。这些技术广泛应用于路径规划、数据库查询、图形渲染和几何优化等领域。 通过这些理论和方法，工程师和研究人员能够设计出更高效、更智能的机器人运动策略，确保它们在复杂环境中的自主导航能力。同时，这些计算几何的原理也为其他领域的应用提供了强大的数学工具。