I’m very happy to share the news that a paper authored by current and former members of Autodesk Research has been published in the open access Journal of Artificial Intelligence Research (JAIR). 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 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.
If you’re curious about the techniques used to implement Space Analysis, or if you’re interested in pathfinding in general, then I do recommend taking a look at the paper. It explores how adding “path counting” to more traditional pathfinding algorithms such as Dijkstra’s and A* produces straighter, more direct grid paths.
This approach was inspired by Pascal’s triangle, and is an efficient way to get higher quality paths out of the classic pathfinding algorithms.
Image: By Hersfold on the English Wikipedia
Without going deep into the theory, here’s an animation made from figures in the paper that shows how path counting can be used to find more direct paths.
This technique also deals with obstacles.
While the paper focuses primarily on navigation (or pathfinding), it does touch on the work we’ve done around visibility analysis, mainly as this helps describe how central grid paths will converge on direct sightlines as the resolution of the grid becomes finer.
In case you’re not familiar with the historical context of this work, it was originally started to enable the generative design of the Autodesk office in the MaRS district of Toronto. (It wasn’t used for the original Project Discover but rather for Project Rediscover, where we published a similar workflow using readily available Autodesk tools.)
We needed pathfinding and visibility analysis to implement a number of the metrics that would be used to score individual designs. For instance:
- When calculating adjacency we had to measure the average distance between people’s desks and key features such as amenities and elevators.
- For buzz we had to measure possible congestion by aggregating the adjacency paths and looking for areas with heavy traffic (and whether this is a good or a bad thing has clearly shifted over the last three years).
- For distraction we used visibility analysis to check whether people would have any colleagues in their field of view when sat at their desks.
Here’s a visualization of these and other metrics from a generative run using the MaRS graph.
Why was path counting important for this project? With traditional grid-based pathfinding methods, the resulting paths can stray significantly from the obvious line-of-sight headings, which we worried might bias the results of some of our analyses. We found that adding a counting step makes these paths go straight, or at least relatively straight, making us much more confident in the quality of the metrics we were computing for generative design.
Since creating and publishing this package, we’ve realized that this new method could be used for other applications, such as for video games or path planning in robotics. For instance, here’s a site that talks about the problem of ugly paths in the context of video game development. That realization led to the team running a number of experiments and developing the theory, and ultimately publishing the concept in a general artificial intelligence journal.
We hope you find the paper an interesting read.
Finally, congratulations to my co-authors – Rhys, Jacky, Alex, Simon and Azam – for this publication. It was quite the journey getting it out there, but very much worth the effort: this is a really interesting contribution to the field and I’m looking forward to seeing how it gets adopted.
