Simple Summary of Mobile Robot Motion Planning Methods

Author: KangchanRoh

Research Field: Mobile Robot Planning
Date: 2023/03/07

---

Reference Review Paper

A review of mobile robot motion planning methods_ from classical motion planning workflows to reinforcement learning-based architectures.pdf

1.60MB

Reference Link

https://github.com/AtsushiSakai/PythonRobotics#a-algorithm

GitHub - AtsushiSakai/PythonRobotics: Python sample codes for robotics algorithms.

+ Wikipedia

---

Path Planning

Graph-search-based Algorithms (Grid-search-based)

---

Basically, there are two or three typical concepts.

• Depth-first Search (DFS)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking.

• Breadth-first Search (BFS)

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.

 

• Jump point Search (JPS)

Jump point search (JPS) is another type of graph-search-based algorithms with different search principles. JPS only adds the jump points that are searched according to the specific rules into the open list. This operation excludes a large number of meaningless nodes. Therefore, JPS occupies less memory and can search faster than A*. However, JPS is only applicable to the uniform grid map.

---

Dijkstra’s algorithm

Algorithm for finding the shortest between nodes in a graph.

1. Create a set of all the unvisited nodes called the unvisited set.
2. Assign to every node a tentative distance **value : set it to zero for our initial node and to infinity.
   • Tentative Distance : length of the shortest path discovered so far between the node and the initial node.
3. When we are done considering all of the unvisited neighbors of the current node, mark the current node as visited and remove it from the unvisited set.
4. If the destination node has been marked visited, then stop. The algorithm has finished.

This algorithm is greedy, complete, and optimal. However, Dijkstra lacks directionality in the process of path search.

A* Algorithm

Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree from a specified source to all possible goals. For Dijkstra's algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no specific-goal-directed heuristic.

A* introduce the heuristic function to measure the distance between the real-time search position and the target position. This function makes the search more oriented and improves the search speed. Specifically, A* selects the path that minimizes

$f(n)=g(n)+h(n)$

where $n$ is the next node on the path, $g(n)$ is the cost of the path from the start node to $n$, and $h(n)$ is a heuristic function that estimates the cost of the cheapest path from $n$ to the goal. A* terminates when the path it chooses to extend is a path from start to goal or if there are no paths eligible to be extended.

D* Algorithm

 

D*, by Anthony Stentz, is an informed incremental search algorithm. They replace the heuristic rule in A* with an incremental reverse rule.

D Lite* is an incremental heuristic search algorithm by Sven Koenig and Maxim Likhachev that builds on LPA*, an incremental heuristic search algorithm that combines ideas of A* and Dynamic SWSF-FP. This method incorporate the reverse searching trick with the heuristic mechanism. D* Lite is a path planning algorithm with the variable start point and the fixed target point. The difference between D* Lite and LPA* is the search direction.

---

Sampling-based Algorithms

---

Graph-search-based algorithms depend on the entire modeling process of the environment. In a higher-dimensional space, such methods would be suffering from the curse of dimensionality. Sampling-based algorithm (SBA) are more suitable for high-dimensional path searching scenarios.

Probabilistic Road-Map (PRM) Planning

This PRM planner uses Dijkstra method for graph search. In the animation, blue points are sampled points, Cyan crosses means searched points with Dijkstra method. The red line is the final path of PRM.

The probabilistic roadmap planner consists of two phases: a construction and a query phase. In the construction phase, a roadmap (graph) is built, approximating the motions that can be made in the environment. First, a random configuration is created. Then, it is connected to some neighbors, typically either the k nearest neighbors or all neighbors less than some predetermined distance. Configurations and connections are added to the graph until the roadmap is dense enough. In the query phase, the start and goal configurations are connected to the graph, and the path is obtained by a Dijkstra's shortest path query. It is simple with few parameters but lacks optimality.

Rapidly-Exploring Random Trees (RRT)

RRT is more goal-oriented than PRM. It generates an extended tree by selecting leaf nodes with random sampling. When the leaf node expands to the target region, the discrete path from the root node to the goal is obtained. RRT is not sufficient because of the whole-space-sampling process. And, RRT is not an optimal or asymptotically optimal algorithm. Limited by these restrictions, RRT cannot plan a feasible path quickly in the narrow passage environment. And it used only geometric relationships without considering the kino-dynamics of the robot.