Computational Geometry Problems in Robotics (Computer and Information Science)

计算几何已经作为理论计算机科学的一个极其重要的领域出现，并在许多其他领域得到应用，如机器人学、计算机辅助设计、力学、计算机图形学、运筹学和超大规模集成电路设计。虽然计算几何领域还很年轻，但最近的许多突破已经导致了一系列活动，特别是在机器人应用方面。该项目旨在确定可以应用计算几何技术的机器人的重要领域。它将首先专注于机器人几何算法的设计和分析，特别是那些与运动规划和最短路径规划有关的问题。这项研究建立在现有的最短路径算法的基础上，该算法用于在存在障碍物和“加权区域”的情况下在平面内运动。进一步的研究应该改善各种基本问题的计算复杂性的界限。更好地理解基本几何算法将导致高效和有效的启发式算法来解决机器人中的重要问题。

Computational geometry has arisen as an extremely important field of theoretical computer science and is finding applications in many other fields, such as robotics, computer-aided design, mechanics, computer graphics, operations research, and VLSI design. While the field of computational geometry is still young, many recent breakthroughs have resulted in a flurry of activity, particularly in applications to robotics. This project is designed to identify important areas of robotics to which techniques of computational geometry may be applied. It will initially focus on the design and analysis of geometric algorithms for robotics, particularly those problems related to motion planning and shortest path planning. The research builds on an existing body of work in shortest path algorithms for motion in the plane in the presence of obstacles and "weighted regions." Further research should improve the bounds on the computational complexity of a variety of fundamental problems. A better understanding of basic geometric algorithms will lead to efficient and effective heuristics for solving important problems in robotics.