# US 2014/0195157 A1 · Applying an indication of a likelihood of a directional transition at a junction in an encoded routability graph description to a positioning function of a mobile device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0195157 A1 - Document ID: US20140195157A1 - Status: Published application - Kind: A1 - Application number: 14/208,872 - Filed: 2014-03-13 - Published: 2014-07-10 - Earliest claimed: 2011-10-17 - Assignees: QUALCOMM Incorporated - Applicants: QUALCOMM Incorporated - Inventors: Rajarshi Gupta - Web page: https://patentgrep.com/patent/US20140195157A1 ## CPC - G01C 21/206: {specially adapted for indoor navigation} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) ## Abstract Techniques are provided for a mobile, which may be implemented in various methods, apparatuses, and/or articles of manufacture to obtain an encoded routability graph representative of feasible paths for an indoor environment, along with values indicative of likelihoods of transition at certain junctions identifiable in the encoded routability graph, and determine one or both of an estimated position or an estimated direction of travel of the mobile device. ## Claims ### Claim 1 A method comprising, at a mobile device: receiving one or more data files comprising: an encoded routability graph corresponding to an indoor environment represented by an encoded map, said encoded routability graph being indicative of a plurality of feasible paths within said indoor environment, said plurality of feasible paths being indicated, at least in part, by junctions selectively interconnected by edges, and a plurality of values indicative of likelihoods of transition for at least one of said junctions, said at least one of said junctions being connected to three or more of said edges, wherein said likelihoods of transition are based, at least in part, on one or more features of said encoded map, one or more predetermined possible origination paths in said encoded routability graph leading to said at least one of said junctions via one of said three or more of said edges, and one or more predetermined possible destination paths that lead away from said at least one of said junctions via at least two of said three or more of said edges; and determining at least one of an estimated position of said mobile device, or an estimated direction of travel of said mobile device based, at least in part, on at least one of said plurality of values indicative of likelihoods of transition and said encoded routability graph. ### Claim 2 (depends on 1) The method of claim 1, wherein said likelihoods of transition are based, at least in part, on, a ratio indicative of: a number of said one or more predetermined possible destination paths leading away from said at least one of said junctions via said at least two of said three or more of said edges; and a number of said one or more predetermined possible origination paths leading toward said at least one of said junctions via said one of said three or more of said edges. ### Claim 3 (depends on 1) The method of claim 1, wherein said one or more predetermined possible origination paths and said one or more predetermined possible destination paths are based, at least in part, on one or more points of interest in said encoded map. ### Claim 4 (depends on 1) The method of claim 1, wherein at least one of said one or more predetermined possible origination paths is based, at least in part, on an all-pairs shortest path (APSP) algorithm applied to said encoded routability graph. ### Claim 5 (depends on 1) The method of claim 1, wherein determining at least one of said estimated position of said mobile device, or said estimated direction of travel of said mobile device, further comprises: affecting a particle filter based, at least in part, on said at least one of said plurality of values indicative of likelihoods of transition. ### Claim 6 (depends on 1) The method of claim 1, wherein at least one of said plurality of values indicative of likelihoods of transition indicates a probability value. ### Claim 7 An apparatus for use in a mobile device, the apparatus comprising: means for receiving one or more data files comprising: an encoded routability graph corresponding to an indoor environment represented by an encoded map, said encoded routability graph being indicative of a plurality of feasible paths within said indoor environment, said plurality of feasible paths being indicated, at least in part, by junctions selectively interconnected by edges, and a plurality of values indicative of likelihoods of transition for at least one of said junctions, said at least one of said junctions being connected to three or more of said edges, wherein said likelihoods of transition are based, at least in part, on one or more features of said encoded map, one or more predetermined possible origination paths in said encoded routability graph leading to said at least one of said junctions via one of said three or more of said edges, and one or more predetermined possible destination paths that lead away from said at least one of said junctions via at least two of said three or more of said edges; and means for determining at least one of an estimated position of said mobile device, or an estimated direction of travel of said mobile device based, at least in part, on at least one of said plurality of values indicative of likelihoods of transition and said encoded routability graph. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein said likelihoods of transition are based, at least in part, on, a ratio indicative of: a number of said one or more predetermined possible destination paths leading away from said at least one of said junctions via said at least two of said three or more of said edges; and a number of said one or more predetermined possible origination paths leading toward said at least one of said junctions via said one of said three or more of said edges. ### Claim 9 (depends on 7) The apparatus of claim 7, wherein said one or more predetermined possible origination paths and said one or more predetermined possible destination paths are based, at least in part, on one or more points of interest in said encoded map. ### Claim 10 (depends on 7) The apparatus of claim 7, wherein at least one of said one or more predetermined possible origination paths is based, at least in part, on an all-pairs shortest path (APSP) algorithm applied to said encoded routability graph. ### Claim 11 A mobile device comprising: a communication interface; and a processing unit to: receive one or more data files via said communication interface, said one or more data files comprising: an encoded routability graph corresponding to an indoor environment represented by an encoded map, said encoded routability graph being indicative of a plurality of feasible paths within said indoor environment, said plurality of feasible paths being indicated, at least in part, by junctions selectively interconnected by edges, and a plurality of values indicative of likelihoods of transition for at least one of said junctions, said at least one of said junctions being connected to three or more of said edges, wherein said likelihoods of transition are based, at least in part, on one or more features of said encoded map, one or more predetermined possible origination paths in said encoded routability graph leading to said at least one of said junctions via one of said three or more of said edges, and one or more predetermined possible destination paths that lead away from said at least one of said junctions via at least two of said three or more of said edges; and determine at least one of an estimated position of said mobile device, or an estimated direction of travel of said mobile device based, at least in part, on at least one of said plurality of values indicative of likelihoods of transition and said encoded routability graph. ### Claim 12 (depends on 11) The mobile device of claim 11, wherein said likelihoods of transition are based, at least in part, on, a ratio indicative of: a number of said one or more predetermined possible destination paths leading away from said at least one of said junctions via said at least two of said three or more of said edges; and a number of said one or more predetermined possible origination paths leading toward said at least one of said junctions via said one of said three or more of said edges. ### Claim 13 (depends on 11) The mobile device of claim 11, wherein said one or more predetermined possible origination paths and said one or more predetermined possible destination paths are based, at least in part, on one or more points of interest in said encoded map. ### Claim 14 (depends on 11) The mobile device of claim 11, wherein at least one of said one or more predetermined possible origination paths is based, at least in part, on an all-pairs shortest path (APSP) algorithm applied to said encoded routability graph. ### Claim 15 (depends on 11) The mobile device of claim 11, said processing unit to further: affect a particle filter based, at least in part, on said at least one of said plurality of values indicative of likelihoods of transition. ### Claim 16 An article for use in a mobile device, the article comprising: a non-transitory computer-readable medium having stored therein computer implementable instructions executable by a processing unit to: receive one or more data files, said one or more data files comprising: an encoded routability graph corresponding to an indoor environment represented by an encoded map, said encoded routability graph being indicative of a plurality of feasible paths within said indoor environment, said plurality of feasible paths being indicated, at least in part, by junctions selectively interconnected by edges, and a plurality of values indicative of likelihoods of transition for at least one of said junctions, said at least one of said junctions being connected to three or more of said edges, wherein said likelihoods of transition are based, at least in part, on one or more features of said encoded map, one or more predetermined possible origination paths in said encoded routability graph leading to said at least one of said junctions via one of said three or more of said edges, and one or more predetermined possible destination paths that lead away from said at least one of said junctions via at least two of said three or more of said edges; and determine at least one of an estimated position of said mobile device, or an estimated direction of travel of said mobile device based, at least in part, on at least one of said plurality of values indicative of likelihoods of transition and said encoded routability graph. ### Claim 17 (depends on 16) The article of claim 16, wherein said likelihoods of transition are based, at least in part, on, a ratio indicative of: a number of said one or more predetermined possible destination paths leading away from said at least one of said junctions via said at least two of said three or more of said edges; and a number of said one or more predetermined possible origination paths leading toward said at least one of said junctions via said one of said three or more of said edges. ### Claim 18 (depends on 16) The article of claim 16, wherein said one or more predetermined possible origination paths and said one or more predetermined possible destination paths are based, at least in part, on one or more points of interest in said encoded map. ### Claim 19 (depends on 16) The article of claim 16, wherein at least one of said one or more predetermined possible origination paths is based, at least in part, on an all-pairs shortest path (APSP) algorithm applied to said encoded routability graph. ### Claim 20 (depends on 16) The article of claim 16, said computer implementable instructions being further executable by said processing unit to: affect a particle filter based, at least in part, on said at least one of said plurality of values indicative of likelihoods of transition.