A full-day workshop on Friday, September 30th, 2011 taking place in conjunction with the IEEE/RSJ International Conference on Intelligent Robots and Systems 2011 in San Francisco, CA.
The goal of this full-day workshop is to highlight current progress and identify challenging open problems in robot motion planning, in order to provoke further theoretical advancement and accelerate the translation of this research into practice. As a starting point, participants will be invited to reconcile the complexity of robot motion planning with the empirical success of sampling-based algorithms (such as the PRM and its variants). In particular, it is known that motion planning, typified by the classical "Piano-Mover's Problem," is PSPACE-complete. Nonetheless, sampling-based algorithms can solve many problem instances very fast, even in high-dimensional configuration spaces. The success of these algorithms suggests that certain geometric properties, for example expansiveness, are encountered widely in real-world problems. Can we take advantage of these properties to design better planners? Can we take advantage of them to design planners that achieve what sampling-based algorithms traditionally cannot, e.g., prove that paths do not exist or produce optimal (or high quality) paths? Invited talks and poster presentations will investigate challenges in the field, which will be refined in a panel discussion and disseminated, with attribution, to the community.
8:15 - 8:30 Welcoming presentation
8:30 - 9:05 Talk: Jean-Claude Latombe
9:05 - 9:40 Talk: Pankaj Agarwal
9:40 - 10:00 Poster Highlights
10:00 - 10:15 Coffee break
10:15 - 10:45 Talk: Nancy Amato
10:50- 11:25 Talk: Saugata Basu
11:25 - 11:45 Poster highlights
11:45 - 1:15 Lunch
1:15- 1:50 Talk: Jean-Paul Laumond
1:50 - 2:25 Talk: David Hsu
2:25 - 3:25 Poster session
3:25 - 4:00 Talk: Steve LaValle
4:00 - 4:30 Brief message from the organizers
4:30 - 4:45 Coffee break
4:45 - 5:45 Panel
Speakers and Panelists
The following speakers participated at the meeting:
- Pankaj Agarwal, Duke University
Abstract: Compact Representations for Shortest-Path Queries
- Nancy Amato, Texas A&M University
Abstract: Toggle PRM:Improved Planning by Simultaneously Mapping C-free and C-obstacle
- Saugata Basu, Purdue University
Abstract: An Improved Algorithm for Computing Roadmaps of Algebraic Sets
- David Hsu, National University of Singapore
Abstract: Towards a Principled General Approach to Motion Planning under Uncertainty
- Jean-Claude Latombe, Stanford University
Abstract: A PRM Approach to Handle Huge Numbers of Path Planning Queries in Different Configuration Spaces
- Jean-Paul Laumond, LAAS-CNRS
The Notion of Small-Space Controllability: A Way to Address Dynamics in Motion Planning for Physical Humanoid Robots.
- Steve LaValle, University of Illinois, Urbana-Champaign
Abstract: Beyond Basic Path Planning in C-Spaces
The following panel participants appeared at the meeting:
- Michael Branicky, Case Western Reserve University
- Roland Geraerts, Utrecht University
- Nancy Amato, Texas A&M University
- Chee Yap, New York University
There were also short presentations by the organizers:
- Kostas Bekris, University of Nevada, Reno
Presentation: PRACSYS group's research interests
- Tim Bretl, University of Illinois, Urbana-Champaign
- Dan Halperin, Tel-Aviv University
Presentation: Improving Path Quality
A poster session, with submissions reviewed by the workshop organizers, will provide a forum for contributions from the broader research community.
The organizers would like to thank all the members of the community who have submitted an abstract for the workshop. We received a large number of submissions, out of which the following 17 posters will appear at the meeting:
"Motion Planning for Robots with Active Mechanical Compensation"
Gustavo Arechavaleta, Felipe A. Machorro-Fernandez and Vicente Parra-Vega - Centro de Investigacion y de Estudios Avanzados del IPN, Saltillo, Coah. Mexico
"Real-time Walking Path Planning with 3D Collision Avoidance"
Leo Baudouin, Nicolas Perrin, Olivier Stasse, Thomas Moulard, Florent Lamiraux, and Eiichi Yoshida - LAAS-CNRS, France and CNRS-AIST, JRL, Japan
"Robust Sensorless Part Orientation of Variable Diameter Spheres"
Aaron Becker and Tim Bretl - University of Illinois Urbana-Champaign
"Toward a Lifelong Motion Planning System that Learns from Experience"
Dmitri Berenson, Pieter Abbeel and Ken Goldberg - University of California, Berkeley
"Numerical Subdivision Methods in Motion Planning"
Yi-Jen Chiang and Chee Yap - Polytechnic Institute of New York University and New York University
"Medial Zones in Motion Planning Applications"
Ata Eftekharian and Horea Ilies - University of Connecticut
"Look Before You Leap: Predictive Sensing and Opportunistic Navigation"
D. K. Grady, M. Moll, C. Hegde, A. C. Sankaranarayanan, R. G. Baraniuk, and L. E. Kavraki - Rice University, TX
"Design of Optimal Robot User Interfaces"
Kris Hauser - Indiana University at Bloomington, USA
"Humanlike Motion Planning"
Marcelo Kallmann, Yazhou Huang, and Mentar Mahmudi - University of California, Merced
"Asymptotic Optimality in Sampling-based Motion Planning"
Sertac Karaman and Emilio Frazzoli - Massachusetts Institute of Technology
"Cross-Entropy Probabilistic Motion Planning"
Marin Kobilarov - California Institute of Technology
"Risk Averse Motion Planning for a Mobile Robot"
Neil MacMillan, River Allen, Dimitri Marinakis, Sue Whitesides - University of Victoria
"Asymptotically Near-Optimal Planning with Probabilistic Roadmap Spanners"
James Marble and Kostas Bekris - University of Nevada, Reno
"Sampling-based Motion Planning with High-Level Discrete Specifications"
Erion Plaku - Catholic University of America, Washington DC
"Robust Sampling-Based Planning for Vision-Based Control in Unstructured Environments"
Azad Shademan and Martin Jagersand - University of Alberta
"Adaptive Motion Planning for Complex Planning Problems"
Lydia Tapia - University of New Mexico
"Reusable Sampling-Based Techniques for Manipulation via Pushing"
Christopher Vo, Jyh-Ming Lien - George Mason University, Virginia
The final version of the abstract is due by 29 August 2011. In addition to a poster session, authors will be given time to speak briefly about their poster to all participants at the workshop.
25 July 2011: Abstract Submissions
10 August 2011: Notification of Acceptance
30 September 2011: Workshop
Primary and Secondary Audience
The primary audience includes researchers active in motion planning or related areas, particular those interested in questions of computational complexity, completeness, and optimality properties of motion planning solutions. The secondary audience includes practitioners and industry representatives who want to steer future research toward real-world challenges and who want to find out about and use the latest results in the field of motion planning.
Motivation and Objectives
The broad goal of this workshop is to provoke new breakthroughs in robot motion planning that are relevant to real-world applications. These breakthroughs will come from a refined understanding of the progress that has been made by the research community over the past decades and of the key challenges that impede future progress. To reach this long-term goal, the workshop will begin by opening a discussion on how insight from the success of sampling-based planners can be used to design new planners that have improved performance in terms of computational cost, completeness properties, and path quality guarantees. Specific questions to be addressed include the following:
- What algorithmic properties are shared by state-of-the-art motion planners, sampling-based or otherwise?
- What problem structure is important to the success of sampling-based planners, and what alternative approaches could use this structure in an even more effective way?
- What are the consequences of sampling-based planners not being able to detect that no solution exists and how can this shortcoming be addressed?
- When is it possible to generate high-quality paths with a sampling-based planner—e.g., by asymptotic optimality or by a post-processing optimization phase—and when would an alternative approach be more efficient?
- When does the cost of pre-computation—e.g., to build data structures for fast collision checking—become a critical problem for sampling-based planners, and how can this problem be addressed?
- What additional requirements for motion planners are arising from new applications?
- What software infrastructure and benchmarks should be used for evaluation of motion planners?
University of Illinois at Urbana-Champaign
Tel Aviv University
University of Nevada, Reno