Determining the position of a mobile device in a geographical area

Patent metadata

Field	Value
Publication number	US-10281282-B2
Application number	US-201515119556-A
Country	US
Kind code	B2
Filing date	Feb 16, 2015
Priority date	Feb 17, 2014
Publication date	May 7, 2019
Grant date	May 7, 2019

Abstract

A method of determining the position of a mobile device uses a model. The model is constructed by obtaining a map of a geographical area, constructing the graph using the map, wherein vertices of the graph correspond to areas of the map, and two vertices are joined by an edge when the areas corresponding to the vertices are adjacent and can be travelled between by a device, and building the one or more feature functions using the graph, wherein a feature value of the one or more feature functions indicates the extent to which the observations support the device being positioned in the areas corresponding to one or more vertices of the graph.

First claim

The invention claimed is:

1. A computer-implemented method for determining the position of a mobile device, the method comprising:
constructing a model for determining position of a mobile device in a geographical area, wherein the model comprises:
a graph comprising a set of vertices and a set of edges between the vertices;
one or more feature functions that take as input one or more vertices of the graph and a set of observations for the device, and return a feature value;
the method comprising constructing the model via executing the steps of:
obtaining a map of the geographical area;
constructing the graph using the map, wherein the vertices of the graph correspond to areas of the map, and two vertices are joined by an edge when the areas corresponding to the vertices are adjacent and can be travelled between by a device;
building the one or more feature functions using the graph, wherein the feature value of the one or more feature functions indicates the extent to which the observations support the device being positioned in the areas corresponding to the one or more vertices of the graph;
obtaining a set of observations from sensors of the device;
determining trajectory for the device that optimizes the values given by the feature functions given for the set of observations; and
determining the position of the device to be an end point of the trajectory.

2. The computer-implemented method as claimed in claim 1 , wherein the model comprises a feature function that takes as input a first and a second vertex of the graph, and a set of observations indicating the movement of the device from the area corresponding to the first vertex to the area corresponding to the second vertex.

3. The computer-implemented method as claimed in claim 1 , wherein the model comprises a feature function that takes as input a first and a second vertex of the graph, and a set of observations indicating the movement of the device from the area corresponding to the first vertex to the area corresponding to the second vertex corrected by a determined rotation angle.

4. The computer-implemented method as claimed in claim 1 , wherein the model comprises a feature function that takes as input a vertex of the graph and a set of observations indicating radio signal strength measurements taken by the device in the area corresponding to the vertex.

5. The computer-implemented method as claimed claim 1 , wherein the step of constructing the graph includes the step of removing any vertex which corresponds to an area which could not be reached by a device.

6. The computer-implemented method as claimed in claim 1 , wherein each feature function has a corresponding weight value.

7. The computer-implemented method as claimed in claim 6 , further comprising the step of determining the weight values for the feature functions by training the model using at least one known device trajectories and corresponding set of observations.

8. The computer implemented method as claimed in claim 1 , further comprising the step of determining a heading for the device, and using the determined heading to correct a heading bias in the set of observations.

9. The computer-implemented method as claimed in claim 1 , further comprising the step of determining at least one parameter used for determining the observations for the device.

10. The computer-implemented method as claimed in claim 9 , wherein the at least one parameter includes a step parameter.

11. The computer-implemented method as claimed in claim 9 , wherein the at least one parameter includes a heading bias parameter.

12. A computing device arranged to perform the method of claim 1 .

13. The computing device as claimed in claim 12 , further arranged to send the constructed model to a mobile device.

14. The computing device as claimed in claim 12 , wherein the computing device is a mobile device.

15. The computing device of claim 14 , wherein the mobile device is further arranged to receive the constructed model from a computer device.

16. A system comprising a computing device as claimed in claim 12 .

17. A non-transitory computer program product arranged, when executed on a computing device, to perform the method of claim 1 .

18. The non-transitory computer program product as claimed in claim 17 , wherein the computing device is a mobile device.

19. A non-transitory computer program product arranged, when executed on a computing device, to provide the computing device of claim 12 .

Assignees

• Univ Oxford Innovation Ltd

Inventors

• Trigoni Niki
• Xiao Zhuoling

Classifications

• G06F18/2323

  based on graph theory, e.g. minimum spanning trees [MST] or graph cuts · CPC title

• G01C21/206 Primary

  specially adapted for indoor navigation · CPC title

• G01C21/3667

  Display of a road map (G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635) · CPC title

• G06K9/52

  Physics · mapped topic

• G06K9/469

  Physics · mapped topic