Path Counting for Grid-Based Navigation

AbstractCounting the number of shortest paths on a grid is a simple procedure with close ties to Pascal’s triangle. We show how path counting can be used to select relatively direct grid paths for AI-related applications involving navigation through spatial environments. Typical implementations of Dijkstra’s algorithm and A* prioritize grid moves in an arbitrary manner, producing paths which stray conspicuously far from line-of-sight trajectories. We find that by counting the number of paths which traverse each vertex, then selecting the vertices with the highest counts, one obtains a path that is reasonably direct in practice and can be improved by refining the grid resolution. Central Dijkstra and Central A* are introduced as the basic methods for computing these central grid paths. Theoretical analysis reveals that the proposed grid-based navigation approach is related to an existing grid-based visibility approach, and establishes that central grid paths converge on clear sightlines as the grid spacing approaches zero. A more general property, that central paths converge on direct paths, is formulated as a conjecture.Citation: Goldstein, R., Walmsley, K., Bibliowicz, J., Tessier, A., Breslav, S., and Khan, A. (2022). Path Counting for Grid-Based Navigation. Journal of Artificial Intelligence Research, Volume 74, pp 917-955. https://doi.org/10.1613/jair.1.13544