Robotics/Navigation/Trajectory Planning

Trajectory Planning

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

Holonomicity

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 return 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.

Dynamic Environments

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 backward 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

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 C_free is the set of all configurations that are collision-free. Computing the shape of C_free is not efficient, however, computing if a given configuration is a collision free is by simply using kinematics and collision detection from sensors.

Target space is a linear subspace of free space which we want robot go there. In global motion planning, target space is observable by robot's sensors. However, in local motion planning, robot cannot observe the target space in some states. To solve problem, robot assume several virtual target space which is located in observable area (around robot). The virtual target space is called sub-goal.

Planning Algorithms

Artificial Potential Field

Example of a Potential Field

Artificial Potential Field Planning places values over the map with the goal having the lowest(Highest) value raising(falling) the value depending on the distance from the goal. Obstacles are defined to have an incredibly high(low) value. The robot then simply moves to the lowest(highest) 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. Artificial potential fields can be achieved by direct equation similar to electrostatic potential fields or can be drive by set of linguistic rules.

Sampling Based Planning

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 C_free. 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

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 C_free. 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 C_free. 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.

Reward-Based Planning

Reward-Based Algorithms assume that robot in each state (position and internal state include direction) can choose between different action (motion). However, the result of each action is not definite. In the other word, outcomes (displacement) are partly random and partly under the control of the robot. Robot gets positive reward when it reach to the target and get negative reward if collide with obstacle. These Algorithms try to find a path which maximized cumulative future rewards. Markov decision processes (MDPs) is a popular mathematical framework which is used in many of Reward-Based Algorithms. Advantage of MDPs over other Reward-Based Algorithms is that it generate optimal path. Disadvantage of MDPs is that it limit robot to choose from a finite set of action; Therefore, the path is not smooth (similar to Grid-based approaches). Fuzzy Markov decision processes (FDMPs)is an extension of MDPs which generate smooth path with using an fuzzy inference system.