Award Abstract # 1718478
RI: Small: Robot Motion Planning with an Experience Database

NSF Org: IIS
Division of Information & Intelligent Systems
Recipient: WILLIAM MARSH RICE UNIVERSITY
Initial Amendment Date: July 25, 2017
Latest Amendment Date: March 19, 2019
Award Number: 1718478
Award Instrument: Standard Grant
Program Manager: Juan Wachs
IIS
 Division of Information & Intelligent Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: August 15, 2017
End Date: July 31, 2022 (Estimated)
Total Intended Award Amount: $500,000.00
Total Awarded Amount to Date: $508,000.00
Funds Obligated to Date: FY 2017 = $500,000.00
FY 2019 = $8,000.00
History of Investigator:
  • Lydia Kavraki (Principal Investigator)
    kavraki@cs.rice.edu
  • Anshumali Shrivastava (Co-Principal Investigator)
Recipient Sponsored Research Office: William Marsh Rice University
6100 MAIN ST
Houston
TX  US  77005-1827
(713)348-4820
Sponsor Congressional District: 09
Primary Place of Performance: William Marsh Rice University
6100 Main St
Houston
TX  US  77005-1827
Primary Place of Performance
Congressional District:
09
Unique Entity Identifier (UEI): K51LECU1G8N3
Parent UEI:
NSF Program(s): Robust Intelligence
Primary Program Source: 01001718DB NSF RESEARCH & RELATED ACTIVIT
01001920DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7923, 7495, 9251
Program Element Code(s): 749500
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

Motion planning is the problem of determining how to get the robot from one point to another. Ideally, robots should have past experiences, of their own and others, inform future actions to operate more robustly and improve their performance over time. Motion planning, as it is largely practiced today, focuses on solving one problem at a time and makes limited use of past history. The goal of this project is to transform the way robots plan their motions by learning to exploit similarities between different experiences and by creating strategies that can adapt to wide range of scenarios. The work will create a bridge between the motion planning community and the information retrieval community, potentially transforming both fields. Training opportunities for diverse students will be offered. All developed software is disseminated under an open source license and infrastructure will enable other researchers to use the experience databases and contribute to them.

This project provides a two-pronged approach to transform motion planning using an experience database. First, hashing will be used on an environment to fetch roadmaps for similar environments from a database. A roadmap is a graph representing feasible motions for a robot. These fetched roadmaps will be then lazily composed and refined to allow the robot to plan efficiently in the current environment. The use of prior experience will be done in tandem with planning from scratch; the latter, if successful, can provide a path and add to the experience database. The second prong in the planned approach will be to maintain various performance characteristics of a library of motion planning algorithms. These characteristics will be then used to optimize algorithm performance and construct a portfolio of algorithms that is competitive across various problems. The overall framework will be implemented in the cloud.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Beidi Chen, Anshumali Shrivastava "Densified Winner Take All (WTA) Hashing for Sparse Datasets" Uncertainty in artificial intelligence , 2018 Citation Details
Chamzas, Constantinos and Cullen, Aedan and Shrivastava, Anshumali and Kavraki, Lydia E. "Learning to Retrieve Relevant Experiences for Motion Planning" 2022 International Conference on Robotics and Automation , 2022 https://doi.org/10.1109/ICRA46639.2022.9812076 Citation Details
Chamzas, Constantinos and Kingston, Zachary and Quintero-Pena, Carlos and Shrivastava, Anshumali and Kavraki, Lydia E. "Learning Sampling Distributions Using Local 3D Workspace Decompositions for Motion Planning in High Dimensions" Proceedings of the International Conference on Robotics and Automation 2021 , 2022 Citation Details
Chamzas, Constantinos and Quintero-Pena, Carlos and Kingston, Zachary and Orthey, Andreas and Rakita, Daniel and Gleicher, Michael and Toussaint, Marc and Kavraki, Lydia E. "MotionBenchMaker: A Tool to Generate and Benchmark Motion Planning Datasets" IEEE Robotics and Automation Letters , v.7 , 2022 https://doi.org/10.1109/LRA.2021.3133603 Citation Details
Chamzas, Constantinos and Shrivastava, Anshumali and Kavraki, Lydia E "Using Local Experiences for Global Motion Planning" 2019 IEEE International Conference on Robotics and Automation , 2019 Citation Details
Kingston, Zachary and Wells, Andrew M. and Moll, Mark and Kavraki, Lydia E. "Informing Multi-Modal Planning with Synergistic Discrete Leads" 2020 IEEE International Conference on Robotics and Automation , 2020 https://doi.org/10.1109/ICRA40945.2020.9197545 Citation Details
Moll, Mark and Chamzas, Constantinos and Kingston, Zachary and Kavraki, Lydia E. "HyperPlan: A Framework for Motion Planning Algorithm Selection and Parameter Optimization" IEEE/RSJ International Conference on Intelligent Robots and Systems , 2021 https://doi.org/10.1109/IROS51168.2021.9636651 Citation Details
Pairet, Eric and Chamzas, Constantinos and Petillot, Yvan R. and Kavraki, Lydia "Path Planning for Manipulation Using Experience-Driven Random Trees" IEEE Robotics and Automation Letters , v.6 , 2021 https://doi.org/10.1109/lra.2021.3063063 Citation Details
uddin, Muhayy and Moll, Mark and Kavraki, Lydia and Rosell, Jan "Randomized Physics-Based Motion Planning for Grasping in Cluttered and Uncertain Environments" IEEE Robotics and Automation Letters , v.3 , 2018 10.1109/LRA.2017.2783445 Citation Details
Wang, Yiqiu and Shrivastava, Anshumali and Wang, Jonathan and Ryu, Junghee "Randomized Algorithms Accelerated over CPU-GPU for Ultra-High Dimensional Similarity Search" Proceedings of the 2018 International Conference on Management of Data , 2018 10.1145/3183713.3196925 Citation Details

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

As robots enter our daily lives, they need to become multi-purpose and multi-functional and improve their motion planning capabilities in diverse scenarios, while, at the same time, allowing their specialization and robust operation in a certain type of environment. A service robot for example, may specialize in operating efficiently in an apartment computing and executing reliable and optimized motion, while another robot of the same type may become an efficient sorter of small mechanical parts that arrive in boxes. Ideally, robots should have past experiences inform future actions to operate more robustly and improve their performance over time. Motion planning, as it is often understood and practiced, focuses on solving one problem at a time and makes limited use of history. This proposal transforms the way robots plan their motions by learning to exploit similarities between motion planning problems and by creating adaptive algorithmic strategies that are robust across a wide range of scenarios. The intellectual merit lies in new framework for learning sampling distributions that guide the most successful category of today’s motion planners, namely sampling-based motion planners. By combining non-parametric learning methods (based on information retrieval) and local geometric decompositions, the resulting framework successfully uses earlier experiences stored in a database resulting in an order of magnitude improvement over competing learning methods. The developed methodology also shows how to learn retrieval functions, specific for motion planning problems, utilizing contrastive learning and a self-supervised training scheme. The approach has been successful with modern manipulators operating in realistic environments obtained through sensing. While investigating the challenges of integrating planning algorithms with modern machine learning methods, this proposal has also developed a path deformation method which can generalize to several scenarios from a single demonstration, a method that uses past experiences for constrained motion planning, differential surrogates for (nondifferential) planners to optimize the respective learned sampling distributions, and a methodology for tuning hyper-parameters of planners. It has also contributed tools for planner evaluation. Evaluating new planners remains a challenge, as researchers often create their own ad-hoc benchmarking problems, a process which is time consuming and bias prone. The advent of learning-based planners has exacerbated this problem as such planners rely on datasets both for learning and evaluation. Towards creating community accepted datasets and benchmarks, a benchmarking dataset generator was proposed along with several challenging motion planning problems. The broader impact of this proposal has been realized by tight collaborations between a machine learning and a robotics group, by training both undergraduate and graduate students, by distributing open-source software, and by introducing the developed concepts in an undergraduate class at Rice University.

 


Last Modified: 11/13/2022
Modified by: Lydia Kavraki

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page