Foundations and Future Prospects of Sampling-Based Motion Planning
A Special Session at the IEEE/RSJ International Conference on Intelligent Robots and Systems
Date: Wednesday, September 28, 2011
Time: 10:00am - 11:30am
Location: Continental Ballroom 5, Hilton at Union Square, San Francisco
Schedule of Presentations:
- 10:00 - 10:30:
Sampling-Based Algorithms for General Motion Control Problems: Recent Advances and New Challenges
Keynote presentation by Prof. Emilio Frazzoli - MIT
- 10:30 - 10:45:
An Obstacle-Responsive Technique for the Management and Distribution of Local Rapidly-Exploring Random Trees
Wedge, N., Branicky, M. - Case Western Res. Univ.
- 10:45 - 10:50
Finding Critical Changes in Dynamic Configuration Spaces
Lu, Y., Lien, J.-M. - George Mason Univ.
- 10:50 - 10:55
Toggle PRM: Simultaneous Mapping of C-Free and C-Obstacle - a Study in 2D
Denny, J., Amato, N. -Texas A&M Univ.
- 10:55 - 11:00
Sampling Heuristics for Optimal Motion Planning in High Dimensions
Akgun, B., Stilman, M. - Georgia Tech.
- 11:00 - 11:15
EG-RRT: Environment-Guided Random Trees for Kinodynamic Motion Planning with Uncertainty and Obstacles
Jaillet, L. (CSIC-UPC), Hoffman, J. (UC Berkeley), van den Berg, J. (UNC Chapel Hill), Abbeel, P. (UC Berkeley), Porta, J. M. (CSIC-UPC), Goldberg, K. (UC Berkeley)
Planning Humanlike Actions in Blending Spaces
Huang, Y., Mahmudi, M., Kallmann, M. - Univ. of California, Merced
- Kostas Bekris
Computer Science and Engineering Department
University of Nevada, Reno
- Steven M. LaValle
Department of Computer Science
University of Illinois, Urbana-Champaign
Sampling-based motion planners have become popular over the last two decades as general solutions that can solve many challenges that cannot be addressed by more traditional, combinatorial and complete algorithms. The main idea is to avoid the explicit construction of the underlying configura- tion space (C-space) and instead search the space through a sampling process. Probing the C-space is achieved through a collision checking module that allows the planner to identify free configurations while ignoring the complexity of C-space obstacles. These algorithms provide weak guarantees that a motion planning problem can be solved, either in the form of probabilistic completeness, when the sampling process samples densely in a random fashion, or resolution completeness, when the sampling is deterministic. Despite these weaker guarantees, sampling-based motion planners are considered today sufficient solutions even for high-dimensional geometric planning problems and have found applications in robotics, manufacturing and biology.
Building on top of the success of sampling-based algorithms, motion planning research remains active, as multiple issues are currently investigated or remain to be addressed. For instance, there are new results regarding the asymptotic optimality of sampling-based algorithms that provide new insights regarding the properties of these algorithms. Furthermore, there are still many challenges regarding the use of sampling-based algorithms to extensions of the basic motion planning problem and in innovative applications. In particular, the following areas provide important examples of challenges that need to be addressed:
- dealing with increasingly more complex systems, such as those with complex differential con- straints or even hybrid systems that involve both discrete and continuous state parameters,
- providing feedback-based solutions that provide stability in the case that the future configura- tions are not predictable,
- addressing problems that involve sensing information and uncertainty, where the robot needs to reason about an underlying information space.
Other challenges include time varying problems, multi-robot coordination, manipulation planning and grasping, dealing with closed kinematic chains and specific challenges that might arise in innovative application areas, such as structural biology.
This symposium will aim to highlight some of the recent developments regarding the foundations of sampling-based motion planners, as well as their use in increasingly more realistic instances of motion planning challenges and applications. It will specifically focus to contributions by young researchers active in the field and give them an opportunity to describe their interests and articulate their vision for the future of sampling-based motion planning.