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.Phillip Torrone. "Segway’s new RMP". Make magazine. 2008. 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 thumb|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 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.10.1016/j.jart.2016.06.006 Humanoid robot path planning with fuzzy Markov decision processes Journal of Applied Research and Technology 14 5 300–10 2016 Fakoor Mahdi Kosari Amirreza Jafarzadeh Mohsen Planning Algorithms Artificial Potential Field thumb|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.10.1504/IJAMECHS.2015.072707 Revision on fuzzy artificial potential field for humanoid robot path planning in unknown environment International Journal of Advanced Mechatronic Systems 6 4 174–83 2015 Fakoor Mahdi Kosari Amirreza Jafarzadeh Mohsen 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 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 thumb|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. 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. Artificial Intelligence: a Modern Approach. Stuart Russell. Peter Norvig. 2003.Roadmap Methods. http://parasol.tamu.edu/~amato/Courses/padova04/lectures/L5.roadmaps.psICAPS 2004 Tutorial. http://www-rcf.usc.edu/~skoenig/icaps/icaps04/tutorial4.html Steven M. LaValle. "Planning Algorithms". 2006. Cambridge University Press. (The book can be read online at http://planning.cs.uiuc.edu/ )http://www.contrib.andrew.cmu.edu/~hyunsoop/Project/Random_Motion_Techniques_HSedition.ppt References