University of Illinois Urbana-Champaign

Navigating the metaverse: Optimization of multi-layer grid transversal using graph algorithms and deep nets

Svenson, Pieter

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/113502

Description

Title
Navigating the metaverse: Optimization of multi-layer grid transversal using graph algorithms and deep nets
Author(s)
Svenson, Pieter
Contributor(s)
  • Varney, Lav R.
  • Lane, H. Chad
Issue Date
2021-12
Keyword(s)
  • navigating the metaverse
  • optimization of grid traversal
  • graph algorithms
  • deeps nets
Abstract
The goal of this project was to assist in the navigation of virtual grid-like spaces. Among other video games, Minecraft is increasingly being used as both a recreational and an educational platform, so our team used this as the target of our implementation. We used a combination of graph-solving algorithms to find a path across a multi-layer network in which the layers are grids. The most difficult and titular task of this project was to explore and develop methods of effectively combining two sub-algorithms — A* and Dijkstra’s — by reducing path distance, execution time, and memory consumption. We developed and explored two options: top-down and bottom-up. Ultimately, top-down does not result in optimal results but instead gives near-optimal results at a much faster rate. Additionally, to improve the runtime of the A* sub-algorithm, we developed a deep neural network whose forward pass replaces its standard approximation function. The inclusion of the neural network yielded roughly 50% longer execution times and 1% larger memory consumption for scenarios with conditions very similar to those in testing. The worsened performance is likely due to the more extensive calculations required in the forward pass of the deep neural network, therefore rendering this solution unfeasible. With more research, maybe neural networks can replace the approximations of grid-solving algorithms, but we found the greatest improvements by altering the overall algorithm structure.
Type of Resource
text
Permalink
http://hdl.handle.net/2142/113502

Owning Collections

Senior Theses - Electrical and Computer Engineering PRIMARY
The best of ECE undergraduate research