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.
