COMP 790-058: Motion Planning in Real and Virtual Worlds
Course Project
by Xin
Huang
Project Update(10/31/2007)
So
far I have:
1 Investigated
the state space in Kinodynamic motion planning and state-of-art
research in this field.
2 Read
papers in RRT based Kinodynamic planning, run the Motion
Strategy Library, get familiar with its
implementation.
3 Read
papers in complete motion planning using approximate cell decomposition, and
the hybrid approach with PRM.
4
Built the rendering infrastructure for animating the robot motion planning
along the path using POV-RAY.
Next Milestone:
The general idea is to explore
the space with kinodynamic constraints, guided by an initial collision-free path
in configuration space computed using approximate
cell decomposition. This is to combine the
complete motion planning in configuration space with robot’s motion obeying
the dynamic constraints. So the method can not only report the
no-path existence, but also improve the exploration speed using the guiding path
in C-space. In addition, I plan to further explore the space using the multiple
RRTs, whose initial state is generated by sampling points
in the free cell of the guiding path, then expanding and merging subtrees to construct a whole free path obeying dynamic
constraints. This is also valuable for planning in narrow passage. The to-do-list
is:
1 Build the
infrastructure for Kinodynamic motion planner. Either based on the starshaped roadmap
motion planner or Motion Strategy Library, or both.
2 Use approximate
cell decomposition method to generate an initial collision free path (also the
free cells along the path) in C-space for guiding further exploration.
3 Sample
multiple points on the free cells along the initial path, use these points as
initial states to expand and merge RRT subtrees.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Proposal Presentation(9/26/2007) | PPT | PDF | Video
Introduction
My aim is to propose an
efficient and stable trajectory planning algorithm in robot motion planning
with kinodynamic constraints. Kinodynamic motion planning
attempts to drive a robot from an initial configuration and velocity to a goal
configuration and velocity while avoiding obstacles and obeying dynamic
constraints. It is useful in a wide area of applications such as virtual
prototyping, spacecraft exploration, virtual environment, etc. In state-time
space, a robot whose motion is governed by an equation of the form 
, where 
is the robot’s state, 
is its derivative relative to time, and 
is the control input. The sets 
and 
are the robot’s state
space and control space,
respectively.
Motivation
The state space plays the
same role as configuration space for kinematic motion planning,
however, standard randomized motion planning methods do not directly apply to
trajectories planning in the state space. The primary limitation in current
space exploration is the sensitivity of the performance on the choice of the
metric. To find appropriate metric to guide the space exploration remains
challenging and desirable in Kinodynamic motion
planning. Moreover, the interaction between workspace decomposition and
continuous exploration is also valuable to be investigated.
Previous Work
Recent
research in kinodynamic motion planning is to
randomly create or merge a tree trajectory from the initial state to the goal
state, such as Rapidly-exploring Random Tree (RRT), Expansive Space Tree (EST),
Discrete Search continuous eXploration (DSLX). These sampling-based tree
planners typically explore the state space using a single or a bidirectional
tree, or multiple trees. RRT and EST rely on simple heuristics or distance
metrics to guide the space exploration. Discrete
Search continuous eXploration (DSLX) method utilizes
the information gathered during previous explorations steps to lead
future explorations toward increasingly promising directions.
Goal
Firstly
a suitable method to decompose the workspace is to be proposed, such as
approximate cell decomposition method. Then I will introduce an appropriate and
stable metric to guide the space exploration, and investigate the interaction
between cell decomposition and continuous exploration. I also wish to employ
the method in multi-robot environments or realtime
application if I can finish it before the due day.
Reference
[1]
[2] S. M. LaValle
and J. J. Kuffner, “Randomized kinodynamic planning,” in IEEE International
Conference on Robotics and Automation, 1999, pp. 473–479.
[3] D. Hsu, R. Kindel, J.-C. Latombe, and S.
Rock, “Randomized kinodynamic motion planning
with moving obstacles,” International Journal of Robotics Research, vol.
21, pp. 233–255, 2002.
[4] S. M. LaValle,
Planning Algorithms.
[5] J.-C. Latombe, Robot
Motion Planning.
[6] B. Donald, P. Xaier, J.
Canny, and J. Reif.
Kinodynamic Motion Planning. Journal of the ACM, 50(5):1048-1066, November
1993.
[7] J. Canny, A. Rege, and J. Reif. An Exact Algorithm for Kinodynamic
Planning in the Plane. Discrete
Computational Geometry, 6:461-484, 1991.
[8] Piotr Indyk, Rajeev Motwani. Approximate Nearest Neighbors: Towards
Removing the Curse of Dimensionality.
ACM Symposium on Theory of Computing.
[9] Jur van den Berg, Mark Overmars; Kinodynamic Motion
Planning on Roadmaps in Dynamic Environments. Proc. IEEE/RSJ Int. Conf. on
Intelligent Robots and Systems - IROS'07, 2007