Metric path planing

On metric path planning, the idea is to obtain a path to a specified goal using techniques that find and optimal path. This is usually obtained by decomposing the path into subgoals named waypoints.

Metric path planning have two components: the representation of the space ad the algorithm.

CSpace

The representation of the world is usually called configuration space, or Cspace for short. This is a data structure used to represent the position and orientation of the robot in the world. There are many ways to represent the world, some of the more popular are:

  • Meadow map. Transform free space in convex polygons, and use this polygons to travel the world safety.
  • Generalized Voronoi Graphs. Generate lines equidistant from all points, and use this lines to create vortex where the lines meet.
  • Regular grids. Create a grid, 2D or 3D, and map the world to the coordinates of the grid.
  • Quadtrees. Recursive grids that use more smaller grids on cells where more detail is needed.

Graph based algorithms

Graph based algorithm are commonly used, as a graph representation of the world is generated by many different representations. However, in order to reduce complexity and decrease the amount of resources/computation needed, some optimizations have to be implemented. A classic example of a graph based algorithm is A, commonly used in computer science. However, A is very limited when other factors, rather than the distance, have to be addressed to compute the optimal path.

Wavefront based planners

Suitable for grid representations of the world. We consider the CSpace as a material where we have to propagate heat, like a wave, from the initial point to the goal, where different places will have different resistance. These are also called region coloring algorithms.

Path planning and reactive execution

Most path planning algorithms plan once and then execute the movement on a reactive style, breaking the path into subgoals. This is ell suited for hybrid style architecture, but has some problems:

  • Subgoal obsession: the robot may use much more time and effort than needed to achieve a specific subgoal, when unrealistic tolerance measures are not addressed.
  • Lack of opportunistic improvements. If the world changes, there is a possibility that a better plan, removing some subgoals for example, may arise from this change.However, the robot may continue with the previos plan. There are two solutions for this, which are the use of coninious replanning or the use of event-driven replanning.

Drawbacks planing

The two mayor drawbacks that metric path planning technique have are:

  • Terrain types are usually not considered.
  • Many are only applicable to holonomic vehicles (can turn in place)

Notes References

20210714190242 Robotics Basics - Navigation

20210514183815 INDEX - Robotics

References

(Murphy 2000)

Murphy, Robin. 2000. Introduction to AI Robotics. Intelligent Robotics and Autonomous Agents. Cambridge, Mass: MIT Press.