Path Counting for Grid-Based Navigation

Journal of Artificial Intelligence Research
2022

Abstract

Counting 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.

Related Publications

Loading...

Related Projects

  • Building simulation

    Buildings are the largest consumers of energy responsible for 48% of all Green House Gas (GHG) emissions. Due to the complexity and multidisciplinary aspects of architectural design, construction, urban design, and building occupant behavior, simulation has gained attention as a means of addressing.

  • Item headline

    Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

  • Item headline

    Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.

Welcome ${RESELLERNAME} Customers

Please opt-in to receive reseller support

I agree that Autodesk may share my name and email address with ${RESELLERNAME} so that ${RESELLERNAME} may provide installation support and send me marketing communications.  I understand that the Reseller will be the party responsible for how this data will be used and managed.

Email is required Entered email is invalid.

${RESELLERNAME}