Progress and Open Problems in Motion Planning

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.

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.

Tentative Schedule

  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:

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:

A poster session, with submissions reviewed by the workshop organizers, will provide a forum for contributions from the broader research community.

Poster Abstracts

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:

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.

Important Dates

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?

 

Organizers

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

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

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