I recently completed a comprehensive demo setup for our Digital Kiosk Solutions at REALFUSION. While reviewing each module we offer, I integrated quick samples and listed available options, including external solutions.
Indoor navigation represents a significant market opportunity, with 6-10 viable solution providers currently available. However, most face a critical challenge: their pricing models and feature sets are often too advanced for typical customer needs.
Most customers simply want to enhance a basic floor plan image—whether single or multi-floor layouts. They don’t require AI, AR, or sensor-based solutions; they need something straightforward and functional.
This led me to explore open-source alternatives rather than reinventing existing solutions. My research uncovered numerous concepts, though most were abandoned projects dating back a decade or more. I’ll detail these findings in Part 2. While I did identify one promising project, it remains in early development stages.
Finding no solid foundation to build upon, I decided to create our own solution. Simple enough, right? The reality proved more complex—developing a working navigation prototype took 3-4 days, followed by another 2 days building an overlay editor. I’ll explore this development process in my next article.
Here a short introduction to the editor and demo…
Today’s focus: Dijkstra’s Algorithm and its role in our solution…
Indoor Navigation and Dijkstra’s Algorithm
Introduction: When GPS Fails Us
Picture yourself standing in the sprawling corridors of a massive shopping mall, hospital, or airport terminal. Your smartphone’s GPS signal flickers weakly, unable to penetrate the concrete and steel that surrounds you. The familiar blue dot that guides you through outdoor journeys becomes unreliable, leaving you to navigate by memory, intuition, or the kindness of strangers. This scenario highlights one of modern technology’s most intriguing challenges: how do we navigate indoor spaces where traditional satellite-based positioning systems fall short?
The answer lies in a fascinating convergence of cutting-edge hardware technologies and classical computer science algorithms. At the heart of many indoor navigation systems beats the pulse of an algorithm conceived nearly seven decades ago by Dutch computer scientist Edsger Dijkstra. His elegant solution to the shortest path problem has found new life in guiding people through the complex indoor environments of our increasingly connected world.
The Indoor Navigation Challenge
Indoor navigation represents a unique technological frontier. Unlike outdoor environments where GPS satellites provide reliable positioning with accuracies of a few meters, indoor spaces present a hostile environment for radio signals. Walls, floors, and ceilings create signal shadows and multipath interference, where radio waves bounce off surfaces multiple times before reaching receivers, distorting distance measurements and location estimates.
The challenges extend beyond mere signal propagation. Indoor environments are dynamic and heterogeneous – they change constantly as people move about, furniture is rearranged, and temporary obstacles appear. A navigation system that works perfectly during quiet morning hours might struggle during busy afternoon periods when crowds of people alter the radio frequency landscape.
Moreover, indoor spaces often feature complex three-dimensional layouts with multiple floors, mezzanines, and vertical circulation paths that traditional two-dimensional mapping approaches struggle to represent accurately. Emergency stairwells, elevators, and restricted access areas add layers of complexity that outdoor navigation rarely encounters.
Enter Dijkstra’s Algorithm: A Timeless Solution
Edsger Dijkstra published his shortest path algorithm in 1959, initially conceiving it as a solution for finding the shortest route between two cities. The algorithm’s elegance lies in its systematic approach to exploring a graph of interconnected nodes, guaranteed to find the optimal path in any network with non-negative edge weights.
How Dijkstra’s Algorithm Works
The algorithm operates on a fundamental principle: always expand the closest unvisited node first. Starting from a source node, it maintains a priority queue of nodes to visit, along with the shortest known distance to each node. The process unfolds as follows:
- Initialization: Set the distance to the starting node as zero and all other nodes as infinity
- Selection: Choose the unvisited node with the smallest known distance
- Relaxation: For each neighbor of the current node, calculate the distance through the current node and update if shorter
- Iteration: Mark the current node as visited and repeat until the destination is reached
This methodical approach ensures that when a node is finally visited, the shortest path to that node has been definitively found.
Graph Representation in Indoor Spaces
In indoor navigation contexts, the abstract mathematical concept of a graph takes on tangible meaning. Nodes represent significant locations within a building – hallway intersections, room entrances, elevator lobbies, and decision points where a person might change direction. Edges represent walkable paths between these locations, weighted by factors such as physical distance, estimated travel time, accessibility considerations, or even user preferences.
Consider a university building where nodes might include:
- Classroom doorways
- Stairwell entrances and exits
- Elevator lobbies on each floor
- Main corridor intersections
- Emergency exits
- Restroom locations
The edges connecting these nodes carry weights that reflect not just geometric distance, but practical navigation considerations. A path through a crowded cafeteria might be weighted more heavily than an equivalent distance through a quiet administrative corridor. Stairs might carry different weights than level pathways, particularly for accessibility-conscious routing.
For my solution I decided to concentrate on distance for now, might extend it with weight options in the future. I know myself, I will have weights working next LOL
I will share more of my findings and list some of the commercial solutions in Part 2.
Technical Resources:
