|
|
Foundations of Robotics Seminar, December 6, 2011
Time
and Place | Seminar Abstract
Probabilistically Complete Motion Planning with for Problems with Discrete
Tasks, Hybrid Dynamivs, and Real-Time Constraints
Kris Hauser
School of Informatics and Computing
Indiana University at Bloomington
Tuesday, December 6, 2011
GHC 2109
Talk 4:30 pm
Motion planning is an essential capability for enabling robots and
virtual characters with many degrees of freedom to perform complex tasks.
Early results in motion planning have shown that exact solution is
computationally intractable, and hence researchers have settled for weaker
notions of completeness. Under various assumptions, modern sample-based
planners are known to achieve probabilistic completeness -- the property
that the probability of finding a path, if one exists, asymptotically
approaches 1 as more time is spent planning. Unfortunately, these
assumptions are violated for problems that involve discrete sequences of
tasks, hybrid dynamics (e.g., making or breaking contact), or when path
computation and execution occur simultaneously in real-time. Hence,
traditional sample-based planners do not work well, if at all. In this talk
I will present three new general-purpose planning algorithms for these new
settings: Multi-Modal-PRM (MMPRM), Random-MMP, and Adaptive Time Stepping
with Exponential Backoff (ATS+EB). I prove that they are not only
probabilistically complete, but exponentially convergent, which implies that
the expectation and variance in running time is finite. Moreover, I present
probabilistically complete methods for incorporating informed sampling
strategies that make planning faster in practice without violating
asymptotic completeness. I demonstrate the application of these algorithms
to legged locomotion in rough terrain with NASA's six-legged ATHLETE robot,
nonprehensile object manipulation with the Honda ASIMO, and assisted
teleoperation of a high speed robot manipulator at IU.
Kris Hauser received his PhD in Computer Science from Stanford
University in 2008, bachelor's degrees in Computer Science and Mathematics
from UC Berkeley in 2003, and worked as a postdoctoral fellow at UC
Berkeley.s Automation Lab. He has held his current position as Assistant
Professor of Computer Science at Indiana University since 2009, where he
directs the Intelligent Motion Lab. Research interests include algorithms
for robot motion planning, integration of planning and perception, and
semiautonomous robots. Applications of his research have included vehicle
collision avoidance, robotic manipulation, robot-assisted medicine, and
legged locomotion in rough terrain.
The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.
Website: http://www.cs.indiana.edu/~hauserk