Presidential Young Investigators Award: Computational Geometry/Optimization

点击翻译按钮获取中文摘要

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.