Motion Planning: From Theory to Practice

A Workshop at "Robotics: Science and Systems" 2010
June 27, 2010, Zaragoza, Spain

Jump to Speakers, Important Dates and Abstracts

You can download the digest for the Motion Planning Workshop.

Approximately a decade ago, the motion planning community saw new theoretical breakthroughs in sample-based planning algorithms that held the promise of breaking down the barriers of the "curse of dimensionality." The ensuing revolution has led to dramatic progress in real-world applications of motion planning to industrial manufacturing, mobile robots, household and assistive robots, surgical robotics, and computational biology. This workshop will bring together motion planning researchers to discuss:

  • What new or recent developments in algorithms and formal theories will enable exciting robotics applications in 2020?
  • What compelling, topical applications call upon the motion planning community to make new theoretical breakthroughs?

Call for Contributions

We are soliciting extended abstracts relevant to the workshop. Accepted abstracts will be included in the conference flash drive distributed to all RSS conference participants. The authors will also be invited to present a poster at the workshop. Innovative and thought-provoking contributions are preferred, even if preliminary. Student submissions are encouraged. Potential subjects include, but are not limited to:

  • Motion Planning under uncertainty
  • Integration of sensing and planning
  • Multi-robot coordination
  • Reconfigurable robots
  • Application to household robots, medicine, healthcare, CAD/CAM, biology, transportation, games, and new domains

Extended Abstracts should be submitted by e-mail as pdf attachments to Kris Hauser at hauserk at cs.indiana.edu by May 20, 2010. The extended abstract should be no more than 800 words and can include figures and references. Please use the RSS conference final submission template.

Tentative Schedule

The workshop will consist of invited talks, a poster session, and a round-table discussion forum. Talks will be approximately 25 minutes with 5 minutes for questions.

  • Session 1: Algorithmic and Theoretical Developments
  • Session 2: Success Stories
  • Session 3: Grand Challenge Problems
  • Session 4: Poster Session / Round Table Discussion

Invited Speakers

  • Tim Bretl, UIUC
  • Oliver Brock, TU Berlin
  • Etienne Ferre, Kineo CAM
  • Roland Geraerts, Utrecht University
  • Jean-Paul Laumond, LAAS-CNRS, Toulouse
  • Sylvain Martel, Ecole Polytechnique Montreal
  • Rob Platt, MIT

Organizers

Organized by the Co-Chairs of the IEEE/RAS Technical Committee on Algorithms for Planning and Control of Robot Motion:

  • Ron Alterovitz, UNC-Chapel Hill, USA
  • Kostas Bekris, University of Nevada, Reno, USA
  • Juan Cortes, LAAS-CNRS, Toulouse, France
  • Kris Hauser, Indiana University at Bloomington, USA

Important Dates

  • May 20, 2010 Deadline for extended abstracts
  • May 27, 2010 Notification of extended abstract acceptance
  • May 31, 2010 Workshop early registration deadline
  • June 27, 2010 Workshop in Zaragoza, Spain


Abstracts

Kineo CAM, the path planning company.
Etienne Ferre, Kineo CAM

Kineo CAM, created nearly ten years ago, was founded in 2001 by Pr. Jean-Paul Laumond and his colleagues from LAAS-CNRS. Kineo CAM is the worldwide leader in path planning software components with more than 120 customers in 30 countries. Since its birth, what were the different steps of its evolution? What were the successful -and unsuccessful- applicative domains (robotics, video games, CAD/CAM...)? 10 years of challenges: always being at the cutting edge of path planning algorithms, developing powerful SDK framework for research laboratories and meanwhile offering our end-users the easiest-to-use technology focused in making things move.



Motion Planning for Navigating Untethered Microrobots in the Vascular Network Using Magnetic Resonance Imaging (MRI)
Sylvain Martel, Ecole Polytechnique Montreal

There are many reasons to justify the use of medical microrobots and nanorobots in the human body and include the rapid elimination of diseases, repair of biological structures, corrections of genetic defects, and augmentation of human capabilities, to name but a few examples. But in the shorter term, it is most probable that the medical application of choice for untethered entities that could be considered as precursors or simplified versions of the more complex medical micro- and/or nanorobots, would be tumor targeting.

Tumor targeting in this respect aims at delivering therapeutic agents to a tumoral lesion using the most direct route through the vascular network. Hence, the use of navigable untethered micro-nanorobots for such targeted medical interventions could have major benefits compared to traditional methods by providing less invasive approaches with potential for shorter recovery periods for the patients by reducing substantially secondary toxicity.

But the real challenge in the development of medical micro- nanorobots designed to operate in the human blood vessels goes behind the aspect of propulsion alone. Among several challenges, motion planning is a critical aspect. Indeed, not only the characteristics of the micro/nanorobots must be taken into account during the motion planning phase prior to the injection process, but to be successful, it must be done within known technological and physiological constraints that will differ in various regions of the vascular network during the navigation phase.

Here, an overview of the MRI-based nanorobotic platform and the main challenges will be presented with emphasis on the motion planning and its importance for the success of such targeted medical interventions.



A Sampling-based Approach to Compute Biologically-active Protein Conformations
Amarda Shehu, George Mason University

Analogies between articulated mechanisms and protein chains regularly attract applications of the motion-planning framework to the study of protein conformations. The dimensionality challenge when dealing with dozens of dofs in articulated mechanisms is further accentuated by the hundreds of dofs in protein chains. There is a growing need, however, to complement wet-lab efforts in revealing biologically-active conformations of millions of protein sequences obtained from organismal genomes. Knowledge of these conformations promises to improve our understanding and treatment of disease.

This talk presents our recent efforts to enhance the sampling of biologically active conformations. Only sequence is known for a protein at hand. Novel strategies are introduced to enable a tree-based search to deal with the high-dimensionality of the protein conformational space and the continuous and rugged energy surface associated with this space. Energy- and geometry-based discretization layers are employed to gather information about explored regions of the conformational space and the underlying energy landscape in order to further guide the search towards energetically-relevant under-explored regions.

Applications on diverse proteins suggest the proposed efforts greatly enhance the sampling of the protein conformational space and efficiently recover the known native conformations. The usage of reduced protein models and short fragments to efficiently sample valid conformations of the protein chain, the combination of tree-based search with local optimization techniques like Monte Carlo, and the discretization guided search of a continuous space offer interesting insights on how to tackle the dimensionality challenge both in protein chains and articulated mechanisms.



Motion Planning: What Theory is Telling Us for Practice
Oliver Brock, TU Berlin

True, motion planning has made tremendous progress over the last decade. New frameworks have been developed and new application domains have been tackled. But what are the reasons behind these successes? In my talk I would like to give some (possibly controversial?) answers to this question. If my answers are correct then there seems to be a mismatch between the reasons for success in motion planning and the emphasis of ongoing research in the field. I will argue that our community needs to change this. And I will present work that leverages the alleged reasons for success in motion planning.



Some trends in motion planning.
Jean-Paul Laumond, LAAS-CNRS, Toulouse

After pinpointing quickly some effective successes of motion planning I will overview recent researches motivated by the study of the anthropomorphic systems [1,2,3,4,5]. An anthropomorphic system is both a redundant system and an underactuated one. How to apply motion planning algorithms in that context? The question opens algorithmic issues which are more generic than it appears. The talk will mainly emphasize on:

  • the control of random diffusion processes, and
  • the coupling with numerical optimization algorithms.

Then we will see what challenges remain open for effective applications to robotics, including the links with perception and control.

Related References:

  1. S. Dalibard, A. Nakhaei, F. Lamiraux, J.P. Laumond, Whole-Body Task Planning for a Humanoid Robot : a Way to Integrate Collision Avoidance, IEEE-RAS International Conference on Humanoid Robots, 2009.
  2. S. Dalibard, J.P. Laumond, Control of probabilistic diffusion in motion planning, WAFR 2008.
  3. O. Kanoun, J.P. Laumond, E. Yoshida, An optimization formulation for footsteps planning, Int.. Journal of Robotics Research, to appear.
  4. K. Mombaur, A. Truong, J.P. Laumond, From human to humanoid locomotion : an inverse optimal control approach, Autonomous Robots, (to appear) 2010.
  5. O. Kanoun, F. Lamiraux, F. Kanehiro, E. Yoshida, J.-P. Laumond, P.-B. Wieber, Prioritizing Linear Equality and Inequality Systems: Application to Local Motion Planning for Redundant Robots, IEEE International Conference on Robotics and Automation, 2009.



Motion Planning and Infinite-Dimensional Spaces
Tim Bretl, UIUC

The space of all possible paths through a finite-dimensional configuration space is infinite-dimensional. Nevertheless, paths taken by "real" systems often cluster on what is again a finite-dimensional manifold embedded in this infinite-dimensional space. How might we identify this manifold? Why does it exist? What are the implications? We will consider these questions, and try to make them more precise, in the context of several motivational examples: manipulation of deformable objects, inference of human intent, and design of direct brain interfaces for the control of prosthetic devices.



Challenges of Path Planning in Games and Virtual Worlds
Roland Geraerts, Utrecht University

One of the main challenges in applications dealing with virtual environments is planning a path for a character. Traditionally, algorithms were devised which computed the character’s positions from a start to a goal location without colliding with obstacles and other characters. While these algorithms were successfully applied in fields such as mobile robots, manipulation planning and human robot planning, current virtual environment applications, such as games and crowd simulations, pose many new challenges to the algorithms.

In our talk, we will review key differences between path planning in robotics and path planning in virtual environment applications, including real-time constraints, requirements of the paths, complexity of the world and algorithms, and the number of (dynamic) entities. These differences make it clear that we cannot just use path planning algorithms developed in the field of robotics such as sampling-based methods, visibility graphs, and the A*-algorithm. This leads to new problems and the development of new algorithms.

We tackle these problems by introducing a new data structure for efficiently representing the walkable space. Next, we provide algorithms for efficiently computing a visually convincing path, i.e. a path that is smooth, short, keeps some clearance to obstacles and avoids other characters like humans do. We will also address related problems such as planning coherent groups, camera planning, and planning stealthy paths.



Planning and Safe Replanning for Systems with Dynamics
Kostas Bekris, University of Nevada, Reno

There has been great progress in solving high-dimensional motion planning problems but there are still many issues that limit the capabilities of existing solutions. In particular, it is important to effectively model and plan for systems with complex dynamics and signficant drift (kinodynamic planning). An additional requirement is that realistic systems must safely operate in a real-time fashion (replanning) with partial knowledge of their surroundings and despite the presence or in collaboration with other moving agents (distributed planning).

This talk will describe directions for improving the efficiency of planners for systems with dynamics, including an approach that incorporates statistical tools to learn quickly the effects of the constraints in the algorithm's state-space exploration. Then the presentation will progress to replanning challenges with dynamics, where safety issues arise in the form of Inevitable Collision States (ICS). The discussion will focus on the computational tradeoffs between safety and computational efficiency, the level of safety that can be provided in different scenarios and algorithms that provide safety in problems that involve partial-observability. The final discussion point corresponds to an extension of these safe replanning approaches to multi-robot problems, where the robots communicate to safely avoid collisions and ICS despite their dynamic constraints.



Elegant Planning and Control Solutions for Interesting Dynamical Systems
Russ Tedrake, MIT

The research objective of the Robot Locomotion Group at MIT is to build machines which exploit their natural dynamics to achieve extraordinary agility and efficiency. We believe that this challenge involves a tight coupling between mechanical design and underactuated nonlinear control, and that tools from machine learning and optimal control can be used to produce this coupling when classical control techniques fail. Our projects include minimally actuated dynamic walking on moderate terrain, quadrupedal locomotion on extreme terrain, fixed-wing acrobatics, flapping-winged flight, and feedback control for fluid dynamics.