BSF:2012166:A Framework for Composite Techniques in Motion Planning

该项目是美国-以色列计算机科学合作(USICCS)计划的一部分。通过这一计划，NSF和美国-以色列双国科学基金会(BSF)共同支持美国研究人员和以色列研究人员之间的合作。本项目旨在设计一个框架，将计算几何中的先进基本方法与运动规划中基于采样的有效方法相结合。这将允许在重要的应用中实际使用这些技术，并发展有用的教育经验。运动规划的基本形式对应于在充满静态障碍物的工作空间中为机器人找到一条无碰撞路径的问题。它对于制造和仓库管理、产品装配、外科手术规划、建筑设计、图形动画、计算机游戏和计算生物学等许多应用领域都很重要。美国和以色列研究人员的合作将通过开发基于健全理论的新型高效工具来影响复杂系统的运动规划，从而影响应用领域。此外，这些工具的可用性可能会对算法、计算几何和机器人领域的教育工作产生影响。为了实现这些目标，研究人员将实施和评估运动规划的复合方法，这些方法位于计算几何和基于采样的规划的交叉点。特别是，研究人员将利用基本方法来计算紧凑的运动规划表示，提供最佳保证，部分基于其他领域大数据总结的最新进展。这种协作还可以通过利用组合求解器的最新进展并将这些结果转移到连续运动规划领域来促进多机器人运动规划领域的进步。总体而言，集成框架将允许运动规划社区随时获得基于几何的算法的进步，特别是在对配置空间的整个低维流形而不是单个配置、碰撞检测和空间分解进行采样方面。

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. Through this program, NSF and the United States - Israel Binational Science Foundation (BSF) jointly support collaborations among US-based researchers and Israel-based researchers. This project aims to design a framework for the integration of advanced foundational methods from computational geometry with effective sampling-based methods from motion planning. This will allow the practical use of these techniques in important applications and the development of useful educational experiences. Motion planning, in its basic form, corresponds to the problem of finding a collision-free path for a robot in a workspace cluttered with static obstacles. It is important for many application domains, such as manufacturing and warehouse management, product assembly, surgical planning, architectural design, graphical animation, computer games, and computational biology. The collaboration of the US and Israeli researchers will impact the application areas through the development of novel efficient tools based on sound theory for motion planning of complex systems. Furthermore, the availability of these tools can have an impact in educational efforts in the areas of algorithms, computational geometry and robotics.Towards achieving these objectives, the investigators will implement and evaluate composite methods for motion planning, that lie at the intersection of computational geometry and sampling-based planning. In particular, the investigators will utilize foundational methods to compute compact motion planning representations that provide optimality guarantees, based in part on recent advances in summary of big data in other fields. The collaboration can also lead to advances in the area of multi-robot motion planning, by taking advantage of recent progress in combinatorial solvers and transferring these results in the continuous motion planning domain. Overall, the integrated framework will allow advances in geometry-based algorithms to be readily available to the motion planning community, especially in sampling entire low-dimensional manifolds of the configuration space instead of individual configurations, collision detection and space decomposition.