An Evolution of Wayfinding Technology with Pointr

• Indoor wayfinding is hard to solve - it took us 6 years of R&D development and most of our competitors have given up 
• In this article, we review the main challenges of common pathfinding algorithms and how we solved these over the years to enable dynamic, simple, and efficient wayfinding.

When thinking of pathfinding, most people imagine a straight line from A to B. It is true when you're driving in a car on the highway: your GPS shows you a line, and you just need to follow it to arrive at your destination. However, it's never that straightforward when it comes to human behavior. 

Indoor wayfinding is another matter entirely. When you're in a large venue, such as an airport or a hospital, there are multiple paths you could take to arrive at your destination, and your itinerary has to be accurate, dynamic, and provide smooth transitions as you walk around. 

While you can easily find basic pathfinding algorithms on the internet that can plot a route, real-time wayfinding is difficult to achieve. It requires highly accurate indoor positioning, interactive path planning and a smooth user experience. 

Many of our competitors have given up on trying to improve their pathfinding algorithms as they still face the same struggles we met in our earlier technologies. They have decided instead to continue providing a less accurate and less intuitive product to their customers. That’s why many companies simply plot a route and don’t do any real-time updates.

Two examples of poor wayfinding technology

Since 2014, Pointr has specialized in high-accuracy indoor positioning and pathfinding technology. As one of the first players in the indoor location market, we have perfected our proprietary pathfinding algorithms to provide the best user experience to visitors, customers, and employees in large venues. 

How did we do it? 

In this technical overview, we describe the pathfinding challenges that our R&D team faced and solved along the way. We provide an overview of our algorithms throughout the years and how we overcame each algorithm’s limitations thanks to customer feedback and hard work.

Introducing the Pointr Mobile SDK v6

The latest pathfinding technology of Pointr is the Mobile SDK v6. Powered by a brand new algorithm, v6 solves all the key wayfinding challenges, providing the most seamless and accurate pathfinding experience available today. This version of the algorithm is currently the leader in pathfinding solutions. We have had many clients who used a different pathfinding vendor initially, and after switching to our product, were amazed by the level of enhancement.

With the Mobile SDK v6, Pointr redefines the expectations in the indoor location market. Here’s how.

The Pointr Mobile SDK v6 solves all the challenges from previous versions 

Here’s an overview of the common pathfinding challenges that are solved in the Pointr Mobile SDK v6: 

• Indoor - Outdoor Transitions - The path gives latitude, longitude information along with Pointr coordinates, which allows for a smooth transition between outdoor and indoor sites. This is a critical feature for venues such as campuses, which encompass multiple buildings.
• Smooth Path Edges - This enables a user-friendly path visualization. It means no more rough path turns and edges.
• Smart Re-Routing - When a user is walking, the smart algorithm can detect whether there is a shorter path available. If that’s the case, it calculates the new path and automatically re-routes the user.
• High Accuracy Path Directions - Directions are calculated on simplified path nodes to give an improved walking path rather than just the shortest path. Directions are more stable due to the mechanism that checks time and orientation changes between successive path updates. Features include live turn, rotate directions, better portal usage directions.
• Augmenting Reality - View live directions as real-world overlays with AR navigation.
• Zig-Zag Paths - Better dynamic graph connectivity prevents sporadic path calculation failures and occasional path jumpiness bugs.
• Level Transitions - Combined with our beautiful multi-layer indoor maps, users can be effectively directed to locations on different floors. Portal travel times are now considered while computing the shortest path, walking distance, and total travel time. This ensures smooth transitions between floors. 
• Node Content Management - Fewer nodes are necessary to enable pathfinding. Only major graph paths have to be entered, and the minor connections are made dynamically.
• Dynamic Pathfinding - Improved shortest path heuristic and inter-facility pathfinding 
• On-Demand Path Calculation - On-demand path calculation can be performed for any venue. Previously this was limited to the venue the user is currently in.

From v3 to v6: strengths and weaknesses of the Pointr pathfinding algorithms

How did we get there? Over the years, our R&D team has worked hard to perfect the Pointr Pathfinding Technology to provide a seamless and efficient navigation journey to our customers. 

In this table, we provide a detailed overview of the strengths and weaknesses of the Pointr Mobile SDK, from version 3 to version 6.

Version	Description	Strengths	Weaknesses	Screenshots
v3	Node-based A* algorithm Automatic Node assignment	Accurate and efficient path calculation Dynamic paths were calculated and updated as the user moved All the nodes were automatically connected, so there was no island structure (unconnected mini-graphs) that was not reachable, which eliminated the path calculation failures	Due to automatic node assignment, the graph data of large venues were getting cumbersome No advanced smart reroute mechanism Sharp Path Edges Excess Nodes Zig-zag paths Paths not centered in the walkway Inaccurate path directions

Version	Description	Strengths	Weaknesses	Screenshots
v5	Metro-line algorithm Major-minor path updates introduced Graph nodes with different speeds Path node conversion to 3-D planes for AR (alpha version)	Simplified Graph Nodes, faster load time and path calculation Path updates made seamless by introducing minor/major updates Ported to c++ for seamless cross-platform experience Added speed feature to graph nodes which allowed clients to customize paths  Path centered on walkable areas Interfacility pathfinding Dynamic path updates, smart reroute algorithm to update the shortest path as the user changes position	The path does not connect directly to the node lines, so zigzag paths and sharp edges occur on some edge cases Path directions give unexpected results on some edge cases Interfacility pathfinding is limited; it needs certain preconditions to work On-demand path calculation can only be done within the bounds of the Site Jumpy path in some cases

Comparison of Graph Node Content management between Pre v5 and v5 algorithm

A major update of the v5 algorithm was metro-line-based path calculations, which decreased the nodes necessary to do pathfinding. With this, only major graph paths have to be entered, and minor connections such as portals and Points of Interest are made dynamically using dynamic graph connectivity capability.

Version	Description	Strengths	Screenshots
v6	Metro-line algorithm Portal travel times Full conversion of path nodes to 3-D planes  Conversion of path nodes to world coordinates Dynamic graph connectivity to prevent sporadic path calculation failures	Improved Shortest Path Heuristics Smooth path edges Zig-zag paths eliminated Improved Dynamic Graph Connectivity Content Error Resilience Algorithmic updates to resolve jumpy paths on edge cases Live path directions, accurately guiding the user Added portal travel times to differentiate between portals while calculating paths Inter-facility pathfinding is now available in full scope without limitations Indoor-outdoor pathfinding, seamless dynamic transition to outdoor Calculated path directions include latitude, longitude Concept of path sessions to facilitate path management Augmented Reality, path directions suited for 3D planes On-demand path calculation between any Site, Building

Is it possible to enable pathfinding without an app?

In addition to the Mobile SDK, Pointr also provides REST API technology for static wayfinding. This technology is multi-platform but it is used primarily for digital screens such as kiosks and for web apps where it is not possible to integrate a Mobile SDK. 

How does the REST API work?

When a user requests directions to a destination, the REST API creates a static request to the server, on the cloud. The REST API provides Location A and Location B and asks the server to calculate the path to the destination. The server then sends a response to the phone or to the digital screen with a path. 

The limitations of REST API for pathfinding 

At Pointr, we recommend wherever possible to work with a Mobile SDK instead of a REST API. Here are the reasons why:

• No automatic path update - with the REST API, the path is only calculated once, when the user picks a destination and when the REST API calls the server. There is no automatic system available for path updates. This means that updates to the path will only be available at specific intervals. This interval cannot be too frequent as that would require a lot of network operations, creating a poor user experience. 
• No optimized path re-route - on the Mobile SDK, when a user is walking, the smart algorithm can detect whether there is a shorter path available. If that’s the case, it calculates the new path and automatically re-routes the user. This is not available on the REST API. 
• No efficient path calculation - The REST API has to re-calculate the path from scratch every time it calls the server. In contrast, the Mobile SDK only re-calculates the path from scratch when there is a significant position update. It makes the journey smoother for the user with better performance & efficiency. 
• No offline capability - when the server is offline, the REST API can still request pathfinding but won’t be able to reach the server to get a reply, which means the user won’t get wayfinding. This is a significant limitation to the user experience. In contrast, the Mobile SDK has the capability to work without network connectivity. 

The limitations of REST API for Pathfinding 

Request a live demo and see for yourself

With the Pointr Mobile SDK v6, our customers get the most advanced pathfinding technology available today. This new technology has already received overwhelmingly positive feedback from customers thanks to its high accuracy and performance. But developing and improving our pathfinding algorithms and solving new challenges. 

If you’re interested to find out more about the Pointr Mobile SDK v6 and get a live demo of our pathfinding technology, please get in touch with our team.