Presidential Young Investigators Award: Computational Geometry/Optimization

米切尔博士一直在研究各种问题的计算 机器人、计算机辅助设计和计算机 视野 一个普遍感兴趣的问题是， 构造最短路径图和Voronoi图的有效算法 二维和三维障碍空间中的图表。 他 用许多不同的距离测量方法来研究这个问题 （欧几里德，链接距离，“加权区域”等）， 目前正在实现其中的一些算法。另一个主要问题 计算机视觉领域是一个最适合的领域， 已知对象模型和给定噪声图像之间的关系。 这导致 问题是如何计算两个任意 形状，其中距离可以有许多不同的含义，形状可以 以各种方式描述（从点集到任意 多连通区域）。 他的许多研究问题都有非常简单的可视化。想象 一个小型移动的机器人试图从A点（在客厅） 到点B（在厨房里）。 在这条路上有很多障碍， 其中一些是预先知道的（例如，如果机器人配备了 而其他人，则是一个未知数，如： 地板）。 目标是找到一条从A到B的好路径。这 “最短路径问题”是机器人学的基础，因为如果一个机器人 要实现自动化，以便能够自行计划任务，它必须找到 可行路径（这是“运动规划”问题），理想地， 是最短的，根据某种意义上的最优。

Dr. Mitchell has been studying a variety of problems in computational geometry that arise in robotics, computer-aided design, and computer vision. One problem of general interest is that of finding very efficient algorithms for building shortest path maps and Voronoi diagrams in two and three-dimensional obstacle spaces. He has examined this problem with many different distance measures (Euclidean, link distance, "weighted regions", and others) and is currently implementing some of these algorithms. Another major problem area is that of computer vision, in which one desires a best fit between a known object model and a given noisy image. This leads to questions of how to compute the "distance" between two arbitrary shapes, where distance can have many different meanings and shapes can be described in various ways (from point sets to arbitrary multiply-connected regions). Many of his research problems have very simple visualizations. Imagine a small mobile robot trying to get from point A (in the living room) to point B (in the kitchen). There are many obstacles in the way, some of them known in advance (if, for instance, the robot is equipped with a floorplan) and others unknown (such as the pet dog on the floor). The objective is to find a good path from A to B. This "shortest path problem" is fundamental in robotics, for if a robot is to be automated to be able to plan tasks on its own, it must find feasible paths (this is the "motion planning" problem) which, ideally, are shortest according to some sense of optimality.