EAGER: Provably Efficient Motion Planning After Finite Computation Time

Award Abstract on the NSF page.

Major Goals of the Project

This project aims to advance the understanding of state-of-the-art methods for robot motion planning by analyzing their properties and develop increasingly more capable and practical solutions, which are relevant to important applications, such as automated manufacturing. Four individual goals are identified:

  1. Describe the properties of modern sampling-based algorithms after finite computation time instead of the typical asymptotic analysis.
  2. Consider ways to improve the computational efficiency of such methods in terms of space and time requirements, while maintaining desirable properties.
  3. Apply such solutions to interesting challenges in robotics, especially in the area of manufacturing.
  4. Independently study the case of planning for systems with significant dynamics where it is harder to apply existing solutions with near-optimality guarantees and consider ramifications in the area of planning under uncertainty.


2014 - 2015
  1. A publication on the finite-time properties of the popular Probabilistic Roadmap Method (PRM) has been generated [Dobson, Bekris, ICRA 2015]. The accompanying analysis is able to describe the error after finite computation path between the path found PRM and the optimum path in the same homotopic class.
  2. A study on the average case of the path degradation that arises when one plans over sparse graphical representations has been performed [Kolchmeyer, Dobson, Bekris, SoCS 2015]. The average degradation is significantly smaller than the worst-case performance but there has been limited analysis of the average case.

    Furthermore, we have studied the case that there is no solution to a path planning problem and one needs to consider the minimum-constraint removal problem [Krontiris, Bekris SoCS 2015]. The focus has been on developing computationally efficient approximate solutions to this problem.

  3. We have applied the developed sampling-based motion planners in two cases related to manufacturing applications:
    • One involved the rearrangement of multiple objects using an industrial manipulator [Krontiris, Bekris RSS 2015]
    • The other involved the transfer of an individual object by multiple robotic arms [Dobson, Bekris IROS 2015]

2015 - 2016

The PI's research group further extended the analysis of sampling-based algorithms for systems with significant dynamics, which has led into a journal publication at IJRR that appeared during the reporting period. The corresponding article describes a state-of-the-art algorithm, which achieves asymptotic optimality for the most general set of conditions. Furthermore, this line of work was also applied in the context of planning in belief spaces, which exhibits similar properties with planning for systems with significant dynamics (i.e.., lack of a steering function). It was shown that given an appropriate distance function, sampling-based algorithms can be effectively used for exploring belief spaces and returning robust trajectories.

Furthermore, the project continued the study of sampling-based algorithms in the context of higher-level manipulation tasks, such as object rearrangement and multi-arm manipulation. In particular: (a) building on top of previous work that achieved asymptotic optimality for object rearrangement, new algorithms were proposed that maintained these desirable properties but achieved improved computational performance, (b) sampling-based algorithms were also evaluated in the context of multi-arm manipulation, where it was shown that it is possible to both represent and efficiently search a graphical representation that explicitly states the set of modes of the problem.

Finally, the practical application of these methods was studied in the context of warehouse picking challenges, such as those studied in the context of the popular Amazon Picking Challenge. The studied methods were used in conjunction with appropriate hardware platforms and perception solutions towards integrated systems in this domain.

Significant Results

To the best of the PI's knowledge, some of the results developed as part of this project manage to address long-standing issues in the motion planning community and significantly extend the capabilities of modern planners. In particular, significant results are:

  • the finite computation time properties, which have been argued for the popular PRM algorithm for the first time
  • the general type of optimality guarantees when planning for dynamical systems and the application of asymptotically (near-)optimal sampling-based planners in belief space for relatively high-dimensional systems.

Relevant Publications

Related Software

You can access public software repositories on the PRACSYS directory on BitBucket.

Please contact us if you would like to access any implementations of algorithms not publicly available on the above directory.