Award Abstract on the NSF page.

Major Goals of the Project

This project is funded as part of the United States-Israel Collaboration in Computer Science (USICCS) program. The objective of this project is to allow interactions between the US PI's research group (Dr. Kostas Bekris' group at Rutgers University) with the research group of Prof. Dan Halperin at Tel Aviv University. Dr. Bekris's research expertise is on sampling-based robot motion planning methods, while Prof. Halperin's group is one of the globally leading research labs in the areas of computational geometry and combinatorial methods for motion planning.

Given the expertise of the two teams, this travel award can help the definition of proper frameworks 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.

Project Activities


The collaboration of the two groups is based on contributions from both:

- Kiril Solovey and Dan Halperin from TAU have shown that it is possible to implicitly search the space of a multi-robot planning problem (which involves the Cartesian product of the configuration space of each robot) without explicitly building a data structure in the joint space. The prior method could only achieve probabilistic completeness.

- Andrew Dobson and Kostas Bekris from Rutgers have described in recent work the space that corresponds to multi-arm manipulation problems, where potentially pairs of arms need to perform handoff of objects. Multi-robot planning arises as a subproblem in this domain. The prior method again could only achieve probabilistic completeness.

Given recent results on the asymptotic optimality of sampling-based planners, the two groups are collaborating towards a method that can search implicitly the joint space but also achieves asymptotic optimality in a way that helps challenges in the multi-arm manipulation domains.

Prior to 2015

The PI's graduate student, Mr. Andrew Dobson, visited Tel Aviv University during the month of December 2013 with the support of this research grant. Mr. Dobson's thesis focuses on the completeness and optimality properties of sampling-based motion planners after finite computation time.

During this period, he had the opportunity to interact with Prof. Dan Halperin, his research team - especially Mr. Kiril Solovey working in the area of multi-robot motion planning and Mr. Oren Salzman working in efficient representations for motion planning - as well as get exposed to the latest contributions of Prof. Halperin's group to the Computational Geometry Algorithms Library (CGAL). He also had the opportunity to present his own work in sparse data structures for motion planning and finite-time guarantees.

The coordination between the two groups continued beyond the visit and there were frequent video conferencing meetings in an effort to investigate further opportunities for interaction.Given the availability of funds from Israel, Prof. Halperin's graduate student, Mr. Kiril Solovey, had the opportunity to visit the PI's research group at Rutgers on September of 2014.

Specific Objectives

The PI aims towards the development of increasingly capable motion planning algorithms through the integration of existing contributions from the Rutgers and Tel Aviv group and as a result of the supported interactions. It is expected that this objective will be achieved through common publications between the two research groups.

Beyond algorithms, this project should also assist in the development of open source software tools given the prior experience and existing contributions of the research groups in this area.

Key Outcomes

Andrew Dobson, Oren Salzman and Kiril Solovey developed a report that summarized their investigations during the visit of Mr. Andrew Dobson at Tel Aviv University. It focuses on the properties of Unit Disk Graphs and how these properties affect the performance of a popular sampling-based algorithm, known as the Probabilistic Roadmap Method (PRM*). Please contact Kostas Bekris (kostas.bekris\AT\cs.rutgers.edu) if you are interested in this report.

The PI's group developed an algorithm for rearrangement of multiple objects (paper accepted to appear in the IEEE Humanoids 2014 conference in Madrid, Spain - November 2014) that builds on top of contributions from the Tel Aviv University research group on multi-robot motion planning.

Opportunities for Training and Professional Development

This project is directly providing training and professional development opportunities to the PI's graduate students that have the opportunity to interact with the research group from Tel Aviv University (TAU). This includes Mr. Andrew Dobson, who had the opportunity to visit TAU but also other graduate students in the group, such as Athanasios Krontiris, Rahul Shome and Andrew Kimmel, who participated in the development of the rearrangement algorithm given the prior work by the Prof. Halperin's lab.

Furthermore, an undergraduate student, Mr. Robert Kolchmeyer, who is supported by Rutgers University's Aresty program for undergraduate research, started working on a project that relates to the outcome of the visit of Mr. Andrew Dobson at Tel Aviv University. His focus is on better understanding the average or expected properties of sparse data structures for motion planning.