Toward a String-Pulling Approach to Path Smoothing on Grid Graphs


  • Jihee Han University of Southern California
  • Tansel Uras University of Southern California
  • Sven Koenig University of Southern California


Paths found on grid graphs are often unrealistic looking in the continuous environment that the grid graph represents and often need to be smoothed after a search. The well-known algorithm for path smoothing is greedy in nature and does not necessarily eliminate all heading changes in freespace. We present a new path-smoothing algorithm based on “string pulling” and show experimentally that it consistently finds shorter paths than the greedy algorithm and produces paths with no heading changes in freespace.