# Motion planning from a given path

Many articles reference algorithms such as A*, PRM or RRT based planners to motion planning algorithms which seems unreasonable since it is still necessary to parametrize found path with time.I wonder, why? However it is not the main problem.

The issue is that of generating motion profile based on a given path. If there were small number of points, maybe 3 or 4, it would be relatively easy to generate some type of speed profile to follow it. Unfortunately output of A* or any of the mentioned algorithms can have large number of points. Therefore it is not clear how to built motion profile based on given points. Could anyone explain to me please how it should be done?

• Do you have a start and goal pose for the robot in the task space? Should the robot should pass through a given set of points while going towards the goal? Also, are there any static or dynamic obstacle in the workspace of the robot? – bluebird Jan 14 '18 at 7:14
• @bluebird it should pass through a set of points and there are only static obstacles in the workspace. – Long Smith Jan 14 '18 at 9:18
• Maybe dynamic programming would be a good option. – fibonatic Jan 14 '18 at 11:34
• As per my understanding, you have a robot which has to go from start to goal passing through some via-points avoiding static obstacles. Please provide the robot's description (mobile robot or a manipulator?). Also, are the via-points in the task space or the joint space? You may update your question with these and the above-provided details. – bluebird Jan 14 '18 at 11:58

Many articles reference algorithms such as A*, PRM or RRT based planners to motion planning algorithms which seems unreasonable since it is still necessary to parametrize found path with time.I wonder, why?

First of all, RRT, for example, can be used to plan trajectories directly. When the robot in question has $n$ DOFs, such a planning problem happens in a space of dimension $2n$ called state-space (each point in the state-space is a pair of configuration and velocity $(q, \dot{q})$). But since the complexity of a motion planning problem grows exponentially with the dimension of the planning space, it is usually pretty difficult to solve the problem.

Instead, a more practical approach is to decouple a trajectory planning problem into two subproblems: (geometric) path planning and time-parameterization. The thing is that each subproblem can be solved really fast that solving these two subproblems is much, much faster than solving the trajectory planning problem in one shot.

Therefore it is not clear how to built motion profile based on given points.

Actually geometric motion planners (i.e. planners that plan paths in the robot configuration space) do not produce only waypoints, they output also a path between each consecutive pair of waypoints (such paths are usually linear).

To produce a trajectory, the geometric path generated by a planner is given to a time-parameterization algorithm to generate a velocity-profile. A geometric path and a velocity profile together make a complete trajectory.

If the generated path is piecewise linear (that is, each pair of consecutive waypoints are connected by a straight-line path), then a velocity profile that makes the robot follows this path exactly must start and stop at each waypoint (it might not be straightforward to see why, but it is not too difficult to derive this either). Then after a velocity profile has been computed, now you get a complete trajectory. (Such a trajectory is slow due to its start-stop behavior. This can be improved by using a trajectory shortcutting method.)

When the generated path is $C^2$-continuous, you can use fancier time-parameterization algorithms. There are quite a few approaches to solving a time-parameterization problem (convex optimization, numerical integration, etc.). They can give you not just any time-parameterization but time-optimal parameterization (i.e. they compute the fastest way for the robot to traverse the given path without violating any constraints).

Note: There are quite a number of names that people use to refer to the second subproblem (time-parameterization). Such terms include (but not limited to) path parameterization, path tracking, etc.

I have used A* for motion planning in a highway simulation with moving obstacles (other cars). The README includes a thorough description of my approach. I recommend reviewing this project to understand how A* can be used effectively for robotic motion planning. Let me know if you have any questions about how the project works, or if there are additional challenges in your project that don't seem to be covered.

https://youtu.be/ouSjnpnRL7w

https://github.com/ericlavigne/CarND-Path-Planning