I’m very happy to share the news that a paper authored by current and former members of Autodesk Research has been published in JAIR, the Journal of Artificial Intelligence Research. The paper is entitled “Path Counting for Grid-Based Navigation” and talks in depth about the algorithm developed to power the Space Analysis package for Dynamo.
Here’s the paper’s abstract, to tickle your fancy:
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…