Path Planning

Path planning is the ability of a robot to search feasible and efficient path to the goal. The path has to satisfy some constraints based on the robot’s motion model and obstacle positions, and optimize some objective functions such as time to goal and distance to obstacle. In path planning, dynamic programming based approaches and sampling based approaches are widely used[22]. Fig.5 shows simulation results of potential field path planning and LQRRRT* path planning[27].

Contents

• Dynamic Window Approach
• Bug planner
• Grid based search
  • Breadth First Search
  • Depth First Search
  • Dijkstra algorithm
  • A* algorithm
  • Bidirectional A* algorithm
  • D* algorithm
  • D* lite algorithm
  • Potential Field algorithm
• Time based grid search
  • Space-time astar
  • Safe Interval Path Planning
  • References
• Model Predictive Trajectory Generator
  • Path optimization sample
  • Lookup table generation sample
• State Lattice Planning
  • Uniform polar sampling
  • Biased polar sampling
  • Lane sampling
• Probabilistic Road-Map (PRM) planning
• Visibility Road-Map planner
  • Algorithms
• Voronoi Road-Map planning
• Rapidly-Exploring Random Trees (RRT)
  • Basic RRT
  • RRT*
  • RRT with dubins path
  • RRT* with dubins path
  • RRT* with reeds-sheep path
  • Informed RRT*
  • Batch Informed RRT*
  • Closed Loop RRT*
  • LQR-RRT*
• Cubic spline planning
  • Spline curve continuity
  • 1D cubic spline
  • 2D cubic spline
  • References
• B-Spline planning
  • Bspline basics
  • Bspline interpolation planning
  • Bspline approximation planning
  • References
• Catmull-Rom Spline Planning
  • Catmull-Rom Spline Fundamentals
  • Types of Catmull-Rom Splines
  • Blending Functions
  • Catmull-Rom Spline API
  • References
• Clothoid path planning
  • Step1: Solve g function
  • Step2: Calculate path parameters
  • Step3: Construct a path with Fresnel integral
  • References
• Eta^3 Spline path planning
• Bezier path planning
• Quintic polynomials planning
  • Quintic polynomials for one dimensional robot motion
  • Quintic polynomials for two dimensional robot motion (x-y)
  • References:
• Dubins path planning
  • Dubins path
  • API
  • Reference
• Reeds Shepp planning
  • Mathematical Description of Individual Path Types
• LQR based path planning
• Hybrid a star
• Optimal Trajectory in a Frenet Frame
  • High Speed and Velocity Keeping Scenario
  • High Speed and Merging and Stopping Scenario
  • Low Speed and Velocity Keeping Scenario
  • Low Speed and Merging and Stopping Scenario
• Coverage path planner
  • Grid based sweep
  • Spiral Spanning Tree
  • Wavefront path
• Elastic Bands
  • Core Concept
  • Bubble Representation
  • Force-Based Deformation
  • Dynamic Path Maintenance
  • References