[paper-review] Fast-Replanning Motion Control for Non-Holonomic Vehicles with Aborting A*

IROS, 2022. [Paper] [Video]

Marcell Missura¹, Arindam Roychoudhury¹, Maren Bennewitz^{1 1}All authors are with the Humanoid Robots Lab, University of Bonn, Germany. Contact: missura@cs.uni-bonn.de

Jul. 21.

Fig. 1: Overview of ShortTerm Aborting A* (STAA*).

Fig. 2: Comparison between RTR and PathRTR.

Fig. 3: Simulation setup.

Summary

• They present ShortTerm Aborting A* (STAA): operates in locally bounded map (seems like dwa algorithm) and avoiding dynamic obstacles using short-term aborting a algorithm.
  • They find a global path via Minimal Construct algorithm. Due to the superior performance of the Minimal Construct algorithm, they can afford to recompute the global path in every control cycle; 4.34ms on average.
  • The STAA* motion planner operates in a bounded local map; (8m X 8m square), additionally, they define intermediate global goal pose within the local map.
  • Finally, they locally plan a collision-avoidance path using short-term aborting a*.

Contributions

• Local map representation
• They propose local map representation by inflating convex polygons to avoid planning through too narrow passages the agent would not fit through.
  • Using Minimal Construct algorithm
  • They set the local goal path as $\tilde{G}$ to plan in the local map.
• Short-Term Aborting A*: The centerpiece of this paper is specifically tailored for early abortion.
  • Like DWA, they sample actions in discrete ranges (in the paper they sample 7x7 actions) based on velocity specs: $(v_{\text{max}}, ~ w_{\text{max}})$
• Then they predict the successor state using their dynamic model of the robot.
  • The radius of the arc is obtained by only using $(v_{\text{max}}, ~ w_{\text{max}})$.
• They use SAT algorithm to check collisions.
  • Separating Axis Theorem: Collision Detection Using the Separating Axis Theorem
• They evaluate heuristic functions leveraging RTR and PathRTR.
  • rotate-translate-rotate (RTR) time function: estimate the time needed to drive along a path to the intermediate goal and to attain the goal direction.

Experiments

• Baselines
  • PD controller, DWA, STAA* (ours)
• Evaluation of different heuristic functions
  • Path RTR (ours)
  • Path Euclidean
  • Dijkstra
    • when all agents are using STAA* as a planner, almost all collisions can be avoided no matter which heuristic is being used.

Thoughts

• The demo video shows powerful collision-free navigation and the visualization in the simulation is great.
• I think the main contribution of this paper is tailored for early abortion.
  • They also mentioned that one of the parameters is a trade-off between precision and computation time.
• And the second-most contribution is a novel time evaluation in goal navigation: Path RTR. They officially released the code, but the implementation is in C++. So I have to study the code and hope to reimplement this algorithm in the mujoco environment.