Path Planning Principles - Do You Know The Way?

July 25, 2018 by Dan Titov
Read in 8 Minutes




For just over a decade, outdoor navigation has been dominated by Google Maps and other similar mapping applications. The indoor space, however, does not have a similar universal standard for navigation, making it much more difficult to create an algorithm that will work for every building and every user. The intricacies of indoor spaces, such as malls, hospitals, corporate offices, hotels and other complex buildings, can make navigating within them very difficult. Each building is unique and should be treated as such.

If we want to address and solution navigating indoors, we must begin by noting that there is a fundamental difference between implementing an indoor navigation system and implementing an indoor navigation system that can be effectively utilized. Path planning, the way a navigational route is determined, is one such consideration.

Path planning contributes to navigating users from an initial location to their desired destination. Before this is ready for general consumption, the paths must first be translated into clear and concise instructions that users can understand and follow. This is done using a variety of landmarks and text directions.

This is where some indoor navigation systems differ. As a user follows the instructions provided by the system, the user’s location is automatically updated. To add more detail, once the user completes an instruction, the next instruction is generated. When properly implemented, it will also take into account a user’s actual movement and be able to detect when the provided path is not being followed. Say a user is walking in a different direction, the system should be able to recalculate and re-route the user back to the identified path or find the next best route. There are a variety of path planning techniques that can be implemented to help enhance the user’s navigation experience.

According to a survey conducted by the University of Nevada and Rutgers University, path planning is an important part of navigation which can impact the system's overall performance. Two such path planning techniques that have a significant impact on the usability of an indoor navigation system are:

  • Shortest Path - The most direct path from A to B, avoiding any obstacles
  • Safest PathThe least confusing path, typically containing many landmarks
Figure 1: Path Planning - Indoor Human Navigation Systems - A Survey
Figure 1 - Shortest and Safest Path
Source: Indoor Human Navigation Systems - A Survey

The path planning techniques represented in Figure 1 are showing both the shortest and safest path. Each of these have strengths and weaknesses, and are often used interchangeably when mapping out a venue. Safest paths are longer, involve more instructions, and have more landmarks, but ensure that users don't get lost. Shortest paths are the most direct and easy to follow, however, large open spaces and a lack of landmarks can lead to a higher uncertainty.

So why are we still talking about it? Simply put, there is no definitive way of achieving “ideal” results. At the end of the day, defining the "ideal" navigation experience is highly subjective. When looking for a doctor’s office or following a route provided by Waze, I always appreciate a good landmark. Whether a receptionist directs me to turn “at the end of the hall” or my phone instructs me to “make a left at Dovercourt Road”, this information is crucial to help me orient myself. Issues arise when you have a large open space where none of these descriptive instructions are possible - so what now?

This is why I propose another option – why not meet in the middle?

Figure 1: Path Planning -Jibestream Combination Technique
Figure 2 - Proposed Path (in orange)

In Figure 2, we have a concept similar to what was shown in Figure 1, however, this time we are introducing a third route option. One that is both direct and still contains visual or descriptive landmarks.

The real achievement here wasn’t combining the two path planning strategies, instead, it was to demonstrate the power and importance of various path options and the control its administrators have over a user’s experience when navigating indoors. It’s essential to understand how the slightest adjustment to a path can impact and hopefully alleviate a user’s frustration when navigating in unfamiliar indoor spaces.

Will there ever be a universally perfect way to provide indoor directions? Only time will tell, but for now, having the power to adjust routes based on user feedback, personal experience, or even for traffic control, is just as important today as it will be 10 years from now.



Dan Titov is a Senior Support Technician at Jibestream. He loves working with people, all things technical, and is always up for a challenge. Outside of work, Dan enjoys table tennis, video games (Epic username ughhmnster, let's play!), and hanging out with co-workers and friends.