Indoor positioning system for a mobile electronic device

A system, comprising:

• a processor;
• and
• a memory device containing programming instructions that, when executed, cause the processor to:
• determine a starting location and a destination location, wherein one or both of the locations is located in an environment,
• receive a graph representation of a map of the environment, wherein the graph representation of the map includes instances of objects represented as nodes of the graph, and open area paths between objects represented as edges of the graph,
• determine a plurality of candidate paths from the starting location to the destination location, wherein each of the plurality of candidate paths comprises a set of node-edge combinations that extend from the starting location to the destination location,
• identify which of the plurality of candidate paths is a shortest path from the starting point location to the destination object location,
• select the shortest path as a path to navigate from the starting location to the destination location,
• generate a token comprising one or more instructions for navigating the shortest path,
• cause the token to be displayed on a display device of an interactive kiosk, and
• cause a mobile electronic device to display a navigation guide for directing a user from the starting location to the destination location when read by the mobile electronic device.

A method, comprising:

• by a mobile electronic device:
• reading a token that is displayed on a display device of an electronic device to determine an initial position of the mobile electronic device in an indoor environment, wherein the token comprises information pertaining to the initial position of the mobile electronic device,
• determining an initial heading of the mobile electronic device,
• determining a relative location associated with the mobile electronic device based on the initial position,
• initializing a set of particles within a threshold distance from the relative location and within a threshold angle from the initial heading,
• detecting a move associated with the mobile electronic device,
• creating a subset of the set of particles based on the move,
• identifying a path that extends from the relative location away from the mobile electronic device at an angle,
• determining a first distance between the relative location and a nearest obstacle that is encountered along the path,
• filtering the particles in the subset by, for each of the particles in the subset:
• using a map to determine a second distance between a location of the particle and an obstacle nearest to the particle at the angle,
• determining a difference between the first distance and the second distance, and
• assigning a probability value to the particle based on the difference,
• determining whether a deviation of the probability values does not exceed a threshold probability value,
• in response to determining that the deviation does not exceed the threshold probability value, estimating an actual location of the mobile electronic device, and
• causing a visual indication of the actual location to be displayed to a user via a display of the mobile electronic device.