EAGER: Provably Efficient Motion Planning After Finite Computation Time
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:
- Describe the properties of modern sampling-based algorithms after finite computation time instead of the typical asymptotic analysis.
- Consider ways to improve the computational efficiency of such methods in terms of space and time requirements, while maintaining desirable properties.
- Apply such solutions to interesting challenges in robotics, especially in the area of manufacturing.
- 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
- 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.
- 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.
- 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.
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.
- Dobson, A, G. V Moustakides, and KE Bekris. 2015. “Geometric Probability Results For Bounding Path Quality In Sampling-Based Roadmaps After Finite Computation”. In IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA.
- Kolchmeyer, R., A Dobson, and KE Bekris. 2015. “Expected Path Degradation When Searching Over A Sparse Grid Hierarchy”. In Symposium on Combinatorial Search (SoCS), Ein Gedi, Dead Sea, Israel.
- Krontiris, A, and KE Bekris. 2015. "Computational Tradeoffs Of Search Methods For Minimum Constraint Removal Paths". In Symposium on Combinatorial Search (SoCS), Dead Sea, Israel.
- Krontiris, A, and KE Bekris. 2015. “Dealing With Difficult Instances Of Object Rearrangement”. In Robotics: Science and Systems (RSS), Rome, Italy: [Best Paper & Best Student Paper Award Finalists].
- Dobson, A, and KE Bekris. 2015. “Planning Representations And Algorithms For Prehensile Multi-Arm Manipulation”. In IEEE/RSJ International Conference on Intelligent Robots and Systems, Hamburg, Germany.
- Littlefield, Z, D. Klimenko, H. Kurniawati, and KE Bekris. 2015. “The Importance Of A Suitable Distance Function In Belief-Space Planning”. In International Symposium on Robotic Research (ISRR), Sestri Levante, Italy.
- Li, Y, Z Littlefield, and KE Bekris. 2016. "Asymptotically Optimal Sampling-Based Kinodynamic Planning". International Journal of Robotics Research.
- Krontiris, A, and KE Bekris. 2016. "Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive For An Incremental Sampling-Based Planner". International Conference on Robotics and Automation (ICRA)
- Littlefield, Z, S. Zhu, C. Kourtev, Z. Psarakis, R. Shome, A Kimmel, A Dobson, Ferreira A. De Souza, and KE Bekris. 2016. "Evaluating End-Effector Modalities For Warehouse Picking: A Vacuum Gripper Vs A 3-Finger Underactuated Hand". 12th IEEE International Conference on Automation Science and Engineering (IEEE CASE)
- Correll, N., KE Bekris, D. Berenson, O. Brock, A. Causo, K. Hauser, K. Okada, A. Rodriguez, J. Romano, and P. Wurman. 2016. "Analysis and Observations From The First Amazon Picking Challenge". IEEE Transactions on Automation Science and Engineering.
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.