Kinodynamic Motion Planning

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] Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning", Robotics: Science and Systems (RSS), 2007.

[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. Cambridge, MA: Cambridge University Press, 2006.

[5] J.-C. Latombe, Robot Motion Planning. Boston, MA: Kluwer, 1991.

[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