Geometric Packing, Covering and Path Planning

几何填充、覆盖和路径规划

• 批准号: 8908901
• 负责人: David Mount
• 金额: $ 3.29万
• 依托单位: University of Maryland, College Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1989
• 资助国家: 美国
• 起止时间: 1989-07-15 至 1991-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8908901&HistoricalAwards=false
• 关键词: Geometric; Packing; Covering; Path; Planning

The problems of packing a set of objects into a finite container and of covering some space by a set of objects are known to be hard (NP- complete) computational problems. Geometric versions of these problems have many applications in areas such a stock cutting in computer-aided manufacturing and object recognition by templates in computer vision. The research is directed towards tractable, yet interesting formulations of these problems by considering the internal density of the packing or covering, that is by determining the best way of arranging objects in an infinite space, ignoring boundaries. In the area of path planning it will be investigated how the configuration of a set of obstacles in the plane affects the structure of shortest paths that avoid the obstacles. The research is particularly concerned with the conditions under which the shortest path between two points is monotonic, that is, it does not reverse direction relative to the line segment joining its start and goal points. Monotonic shortest paths are of interest, because (1) shortest paths can be found efficiently if they are known to be monotonic, and (2) many applications of path planning involve shortest path queries that are monotonic.

将一组对象装入一个有限容器， 一组物体覆盖某个空间的概率是困难的（NP- 完整的）计算问题。 这些问题的几何版本 在计算机辅助下料等领域有许多应用 计算机视觉中的模板制造和物体识别。 这项研究是针对易于处理，但有趣的 这些问题的公式通过考虑内部密度 包装或覆盖，即通过确定最佳方式 在无限的空间中排列物体，忽略边界。 在路径规划领域，将研究如何 一组障碍物在平面上的配置影响结构 避开障碍物的最短路径 这项研究是 特别关注的是， 两点之间的路径是单调的，也就是说，它不反向 相对于连接起点和终点的线段的方向 点 单调最短路径是有趣的，因为（1）最短路径 如果已知路径是单调的，则可以有效地找到路径，并且 (2)路径规划的许多应用涉及最短路径查询 是单调的