Workshop on Progress and Open Problems in Motion Planning

IEEE/RSJ International Conference on Intelligent Robots and Systems
San Francisco, CA
September 30, 2011

Scope

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.

Invited Talks

• Pankaj Agarwal, Duke University
  Abstract: Compact Representations for Shortest-Path Queries
• Nancy Amato, Texas A&M University
  Abstract: TBA
• Saugata Basu, Purdue University
  Abstract: An Improved Algorithm for Computing Roadmaps of Algebraic Sets
• Robert Ghrist, University of Pennsylvania
  Abstract: Geometric-Topological Aspects of Motion Planning
• David Hsu, National University of Singapore
  Abstract: Towards a Principled General Approach to Motion Planning under Uncertainty
• Lydia Kavraki, Rice University
  Abstract: Motion Planning with Complex Goals
• 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
  Abstract: 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

Poster Presentations

• "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 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
  

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.

Goals

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?

Organizers

Timothy Bretl
University of Illinois at Urbana-Champaign
Phone: +1-217-244-3126
Email: tbretl@illinois.edu

Dan Halperin
Tel Aviv University
Phone: +972-3-6406478
Email: danha@tau.ac.il

Kostas Bekris
University of Nevada, Reno
Phone: +1-775-784-4257
Email: bekris@cse.unr.edu