Robotics/Navigation/Trajectory Planning

From Wikibooks, open books for an open world
Jump to: navigation, search

Trajectory Planning[edit]

Trajectory planning is moving from point A to point B while avoiding collisions over time. This can be computed in both discrete and continuous methods. Trajectory planning is a major area in robotics as it gives way to autonomous vehicles.

Trajectory planning is sometimes referred to as motion planning and erroneously as path planning. Trajectory planning is distinct from path planning in that it is parametrized by time. Essentially trajectory planning encompasses path planning in addition to planning how to move based on velocity, time, and kinematics.

Problem Constraints[edit]

Holonomicity[edit]

Holonomicity is the relationship between the controllable degrees of freedom of the robot and the total degrees of freedom of the robot. If the number of controllable degrees of freedom are greater than or equal to the total degrees of freedom a robot is said to be holonomic. By using a holonomic robot many movements are much easier to make and returning to a past pose is much easier.

A car would be non-holonomic, as it has no way to move laterally. This makes certain movements, such as parallel parking, difficult. An example of a holonomic vehicle would be one using mecanum wheels, such as the new Segway RMP.[1]

Dynamic Environments[edit]

In dynamic environments, such as the real world, many possible collision objects are not stationary. This makes trajectory planning more difficult as time is constantly changing and objects are moving. A robot cannot simply move backwards in time as it might simply back away from a stationary collision. In addition to this many choices are completely irreversible due to terrain, such as moving off of a cliff.

Concepts[edit]

Concepts of Trajectory Planning

Trajectory planning gives a path from a starting configuration S to a goal configuration G avoiding collisions in a 2D or 3D space.

A configuration is the pose of a robot describing its position. Configuration Space C, is the set of all configurations. For instance in two dimensions a robot's configuration would be described by coordinates (x, y) and angle θ. Whereas in three dimensions a robot's configuration would be described by coordinates (x, y, z) and angles (α, β, γ).

Free space Cfree is the set of all configurations that are collision free. Computing the shape of Cfree is not effecient, however computing if a given configuration is collision free is by simply using kinematics and collision detection from sensors.

Planning Algorithms[edit]

Potential Field Planning[edit]

Example of a Potential Field

Potential Field Planning places values over the map with the goal having the lowest value raising the value depending on the distance from the goal. Obstacles are defined to have an incredibly high value. The robot then simply moves to the lowest potential value adjacent to it, which should lead it to the goal. However this technique often gets trapped in local minima. Certain techniques can be used to avoid this, such as wavefront potential field planning.

Sampling Based Planning[edit]

Roadmap method is one sampling based planning method. First a sample of N configurations in C as milestones. Then a line PQ is formed between all milestones as long as the line PQ is completely in Cfree. Then graph search algorithms can be used to find a path from start to the goal. As N grows better solutions are found, however this increases computation time.

Grid Based Planning[edit]

Example of Grid Based Planning

Grid Based planning overlays a grid on the map. Every configuration then corresponds with a grid pixel. The robot can move from one grid pixel to any adjacent grid pixels as long as that grid pixel is in Cfree. Then a search algorithm such as A* can be used to find a path to get from start to the goal. One potential tradeoff with this method is with a lower resolution grid(bigger pixels) the search will be faster, however it may miss paths through narrow spaces of Cfree. In addition as the resolution of the grid increases memory usage increases exponentially, therefore in large areas using another path planning algorithm may be necessary.

[2][3][4][5][6]


References[edit]

  1. Phillip Torrone. "Segway’s new RMP". Make magazine. 2008.
  2. Artificial Intelligence: a Modern Approach. Stuart Russell. Peter Norvig. 2003.
  3. Roadmap Methods. http://parasol.tamu.edu/~amato/Courses/padova04/lectures/L5.roadmaps.ps
  4. ICAPS 2004 Tutorial. http://www-rcf.usc.edu/~skoenig/icaps/icaps04/tutorial4.html
  5. Steven M. LaValle. "Planning Algorithms". 2006. Cambridge University Press. (The book can be read online at )
  6. http://www.contrib.andrew.cmu.edu/~hyunsoop/Project/Random_Motion_Techniques_HSedition.ppt