Media Lab Intern Spotlight: Yuliya Parshina-Kottas's Accessible Wayfinding

«Yuliya Parshina-Kottas is a recent graduate of the ITP program at New York University's Tisch School of the Arts. After a decade of working as an animator and designer for children's television, advertising, and multimedia museum exhibits, she is venturing bravely into the world of user experience, interaction design, and creative coding. I am thrilled to have Yuliya introduce her recent Media Lab project, Accessible Wayfinding, here on Digital Underground.»

From Yuliya:

I came to The Metropolitan Museum of Art's Media Lab with a keen interest in creating accessible experiences in a museum environment. The topic combines my passion for assistive technology and universal design—discovered while at ITP—and my awareness of accessibility issues in museums, honed through my professional work on educational multimedia exhibits. I was particularly curious to explore the challenge of finding one's way through the beautiful and confounding maze of the Met's galleries. Having been a loyal visitor of the Museum for over twenty years, I still manage to get hopelessly lost. While this can sometimes lead to a welcome adventure, having control over one's navigation is an important part of a satisfying museum experience—especially for anyone with specific accessibility needs.

Inspired by conversations with staff members and fellow interns, I decided to work on a tool to help visitors craft custom paths through the Museum, based on their individual interests and environmental preferences. My goal was to create a back-end framework for calculating and communicating the best navigational path based on user input, which would drive future explorations of user experience, interface, and storytelling potential.

Coming from a visual background of motion-graphics animation, I had limited programming experience. However, with generous help and encouragement from Don Undeen and Jonathan Dahan, I took a three-month dive into the unknown depths of algorithm design, JavaScript development, and Node.js. Having recently resurfaced, I am very excited to share my adventure with you!

Project Background

The Accessible Wayfinding tool takes root in the work begun by a team of MFA students from the Design and Technology program at Parsons The New School for Design during the Fall 2013 semester. The group collected environmental data about lighting, crowd levels, acoustics, and floor quality in the Met's first-floor galleries, explored user experience and interface design for a mobile wayfinding app, and conducted user tests with a paper prototype. More information about this team's work and findings are available on their project's website.

The Parsons DT exploration culminated in three map visualizations of the light, crowd, and acoustic data of the Museum's first floor.

Light Map
Light Shading = bright spaces
Dark Shading = Dim spaces

Crowd Map
Light Shading = uncrowded
Dark Shading = crowded

Noise Map
Light Shading = quiet
Dark Shading = loud

Visualizations by Joori Lee

The Process

My role in the project was to create a working prototype with a simple user interface that accepts user input of desired destinations and accessibility preferences, calculates a multiple-points-of-interest path based on the user's environmental needs, and draws the path over the Met's floor map. Following the Media Lab's Minimum Viable Product (MVP) approach, the prototype was developed in three phases, with each iteration followed by review and feedback from interested members of the Met's various departments. In addition to the Accessible Wayfinding prototype, a data-entry app was developed to feed the Wayfinder navigational and access information.

Data Entry

Don Undeen created a system for data entry—appropriately named the MapMaker—using Raphael.js, a JavaScript library that helps implement vector graphics on the web. MapMaker gave us an easy and visual way to represent the Met's floor plan as a network of nodes and edges, and indicated every possible path a visitor can traverse without walking through walls.

The MapMaker nodes (representing galleries, hallways, and doorways) store the accessibility data collected in the Fall 2013 semester, which I entered using the app's simple interface.

All information about the nodes, edges, and their relationships is automatically exported into a JSON file when a "Save" button is selected, making all updates easy to manage.

The Algorithm

Prototype 1: Getting from A to B

My first task was to find an algorithm that calculates the most efficient path between two points. I began by looking at the Dijkstra's weighted graphs.

Some of the resources I found helpful in understanding how Dijkstra's algorithm works include a YouTube video describing the algorithm and a Node Packaged Modules page outlining how to implement the algorithm. I explored a few other options, such as the Ant Colony Optimization algorithm, but research conducted by the Maritime University of Szczecin uncovered that Dijkstra performs faster and with more consistent results.

In the first prototype of the Accessible Wayfinder, the Dijkstra algorithm evaluated the nodes and edges stored in our JSON data file and calculated the shortest path between two user-specified points, saving a list of the path nodes and edges in an array.

I used Raphael.js to draw the final path on top of the map UI.

Prototype 2: Multiple Selections

Once I was able to get from A to B, I began to work on including multiple selections.

My approach was to use the Dijkstra algorithm from Prototype 1 to calculate paths between all possible point-of-interest (POI) permutations.

I then looked at each path as a single edge by adding up the length of all the path edges.

This allowed me to create a subgraph of points of interest and their edges, which I could then use to find the best path among all possible paths.

I needed to find an algorithm to calculate a Hamiltonian Path within my subgraph. Unlike Dijkstra, which requires a start and an end point to work, an ideal algorithm for this step would take a start point and find the most optimal route among the remaining nodes, regardless of what node it ends on.

I looked at various approaches to what is essentially a Traveling Salesman Problem, and decided to try the Nearest Neighbor algorithm—a heuristic approach which sacrifices some precision to achieve faster results. The Nearest Neighbor traverses the graph, node by node, examining the length of each node's edges and choosing the shortest among them.

Prototype 3: Accessibility

The final step was to add accessibility preferences to the algorithm. I converted the collected light, crowd, and noise data into a 0–2 (low, medium, high) score, and added it to the main JSON data file by assigning the numbers to the MapMaker app graph nodes. In the Wayfinder prototype, simple drop-down menus allow users to define their ideal navigational environment.

In the algorithm, the user-defined preferences convert each node's accessibility score into a preference-based value. This value is then assigned to the graph edges by deriving the average of each edge's nodes. The edge's length is then multiplied by its accessibility value, so that an edge whose accessibility matches user preferences becomes "shorter" (hence, more likely to be part of the final path), while edges with undesirable accessibility become "longer" (less likely to be chosen).

Here is an example of how the path is affected by light preferences (drawn over the Light Map).

Light Preference: "Don't care"

Light Preference: "Bright"

Light Preference: "Dark and subdued"

Final Thoughts

Working on the Accessible Wayfinding project was a wonderful introduction to the world of computer science, which I am now eager to explore and conquer. I walked away with a better understanding of, and immense admiration for, the creative process involved in designing an algorithm. Through conversations with various members of the Met staff, I learned a lot about the issues of wayfinding and accessibility in a world-class museum like the Met.

I am truly grateful for the opportunity to be immersed in a topic of great personal meaning, and develop it from a concept to a functional prototype. I can't wait to see this project evolve in the hands of the next generation of interns and volunteers, and I hope my work will serve as fertile ground for more conversation, experimentation, and innovation to take root in the future.

Related Link
GitHub: Accessible Wayfinding code