The grid representation of the world introduces the discretization of the robot's action space into individual cells. These cells carry the information on whether they are free or occupied and possibly further information such as traversability or suitability of the area for foot placement. An example of a terrain map and its underlying representation as a traversability map is visualized in the following figure.
A typical pipeline of grid-based path planning consists of the following steps:
Obstacle growing - The robot has non-zero dimensions representing its embodiment, which must be considered when planning. Moreover, the plan execution in real experiments has limited precision, which further enlarges demands on the clearance to the obstacles for the robot to navigate the environment safely. Planning with a large robot in a grid environment is complex; therefore, the trick is to grow the borders of the obstacles by the diameter of the robot and plan in the resulting map that ensures sufficient clearance to the obstacles.
Path planning - Proper selection of the grid path planning algorithm depends on the performance metrics and usage of the plan. Among others, the following grid-based planning algorithms are worth mentioning:
Breadth First Search (BFS), Depth First Search (DFS)
Dijkstra
A*
Jump Point Search (JPS)
Theta* (any-angle path planning - returns the shortest path)
ARA* (Any-time repairing A*)
D* lite
Floyd-Warshall
Trajectory smoothing - The grid-based planners usually return the path as a list of neighboring cells. The trajectory smoothing simplifies the path representation, possible shortening of the path, and considers the path following approach deployed on the particular mobile robot. A trajectory smoothing approach can connect the neighboring segments one by one using straight-line segments up to the point where the straight-line segment collides with an obstacle (grown obstacles) and then follows with another straight-line segment.
Typical steps of planning algorithm evaluation in robotics consist of the following steps
Software testing of the planning algorithm without execution
Simulation of execution with perfect information and perfect execution
Simulation in a realistic simulator with perfect information and imperfect execution given by simulated physics
Deployment on a real robot with imperfect information and imperfect execution
For the evaluation of the path, different metrics can be used as follows.
Feasibility - whether the path is feasible for a particular robot given its embodiment
Length - the overall path length
Planning time - in real-time applications and multi-goal path planning, the overall planning time is a crucial parameter
Clearance - how far from the obstacles the robot navigates. Low distance may result in robot damage in case of inaccurate path execution