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.