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

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Short Papers

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.

10.1609/socs.v11i1.18541