Efficient Wayfinding System Testing Using Set Cover Problem Optimization

Testing wayfinding systems is always a significant challenge. It is very difficult to establish a feedback loop where you receive feedback from users on the wayfinding performance and experience of the entire system, whether it is digital (mobile wayfinding) or analog (signage).

This is also true for Eyedog. Post-deployment testing is always a time-consuming task. The number of routes we model in hospitals quickly reaches around 25,000, and this doesn't even include routes for people with physical disabilities.

If the average route is 200 meters, this means you have 500,000 meters to test, in other words: 500 km (200 miles). Clearly, you cannot do this on foot. One person would need 50 days to test, walking 10 km per day. And if something is incorrect and needs to be adjusted, you would have to walk many kilometers again.

Using blue dot navigation, you can only check whether the planned path is correct by looking at the map, but that does not tell you anything about whether following this path in real life will give you the correct navigation prompts required for at least acceptable wayfinding performance and experience. To know this, you need to walk all the specific routes to understand whether the navigation prompts are correct. An impossible task.

Photo Landmark Navigation though, allows you to test virtually, making it possible to conduct the testing of the whole system, but it still requires testing tons of routes from your laptop or desktop.

We have been working for almost a year on finding a solution for this. Thanks to modeling this as a Set Cover Problem (a classic optimization problem in computer science and mathematics), we managed to reduce the number of routes to be tested by 90%! By testing just 10% of the routes, we can test the whole network, which is a huge time saver for our clients.

After setup, you not only know that everything is correct, but it also takes just a few hours to be sure of it!