Method and system for fingerprinting survey

Patent metadata

Field	Value
Publication number	US-12487091-B2
Application number	US-201816118970-A
Country	US
Kind code	B2
Filing date	Aug 31, 2018
Priority date	Dec 5, 2017
Publication date	Dec 2, 2025
Grant date	Dec 2, 2025

Abstract

A survey for building fingerprint maps for an area may be achieved using map information to generate a grid of nodes and links, then transforming the grid to a directed graph, generating an improved tour that entirely traverses the directed graph and providing at least one survey route based at least in part on the tour to a surveyor that will perform the survey route. The provided survey route may be traversed with at least one device having an integrated sensor assembly that outputs data representing motion of the device and recording signal measurements with each device at a plurality of positions to generate a fingerprint map. The traversal of the provided survey route may be assessed through in-route assessment and/or post-route assessment. Depending on the assessment, the provided survey route may be re-traversed or a next survey route may be scheduled.

First claim

What is claimed is:

1 . A method for providing an improved survey process through automatically providing an improved survey route, wherein the survey is for building fingerprint maps for an area and comprises traversing at least one provided improved survey route with at least one device, wherein each device comprises recording signal measurements at a plurality of positions along the at least one provided survey route, and wherein the survey comprises constructing a fingerprint map of the area based at least in part on the positions and the recorded signal measurements, the method comprising:
a) obtaining digitized map information for an area, wherein the map information comprises a grid of nodes and links and wherein the area comprises an indoor venue; b) transforming the grid to a directed graph comprising vertices and edges, wherein the directed graph is a data structure; c) generating an improved tour that entirely traverses the directed graph by traversing each edge, wherein the improvement to the tour further comprises at least one of optimality and usability; d) wherein generating the improved tour further comprises identifying an edge as a bridge if traversing that edge breaks the directed graph into two unconnected graphs so that the improved tour does not traverse the identified edge; e) generating at least one improved survey route based at least in part on the improved tour; and f) improving a survey process for building fingerprint maps for the area by conducting the survey using the at least one improved survey route.

2 . The method of claim 1 , wherein transforming the grid to the directed graph comprises providing a path from every vertex to any other vertex.

3 . The method of claim 2 , wherein transforming the grid to the directed graph comprises representing each link of the grid with one inward edge and one outward edge.

4 . The method of claim 1 , wherein generating the tour comprises deactivating each edge after the generated tour traverses it.

5 . The method of claim 4 , wherein generating the tour further comprises sequentially adding edges to the tour that are one of;
(i) edges that are not identified as bridges; and (ii) edges that are identified as the only active edge of a vertex.

6 . The method of claim 5 , wherein generating the tour further comprises selecting an edge to be sequentially added to the tour from among a straight edge and a turn edge for a given vertex based at least in part on a distance to a previous turn.

7 . The method of claim 6 , wherein the straight edge is selected when the distance to the previous turn is below a threshold.

8 . The method of claim 6 , wherein the turn edge is selected when the distance to the previous turn is above a threshold.

9 . The method of claim 6 , further comprising randomly selecting among the straight edge and the turn edge when the distance to the previous turn is between two thresholds.

10 . The method of claim 1 , wherein generating the tour entirely traverses the directed graph by traversing each edge only once.

11 . The method of claim 1 , wherein providing the at least one survey route based at least in part on the tour comprises providing a plurality of routes wherein each route has a route length within a predetermined range.

12 . The method of claim 1 , further comprising traversing the provided survey route with the at least one device, wherein each device comprises an integrated sensor assembly configured to output data representing motion of the device.

13 . The method of claim 12 , further comprising recording signal measurements with each device at the plurality of positions along the provided survey route, the plurality of positions determined based at least in part on the motion data, wherein the signal measurements are at least one of wireless networking signals, radio frequency signals and magnetic field signals.

14 . The method of claim 13 , further comprising constructing a fingerprint map of the area based at least in part on the determined positions and the recorded signal measurements.

15 . The method of claim 12 , wherein the device is one of:
i) configured to be conveyed automatically; and ii) configured to be conveyed by a human.

16 . The method of claim 12 , further comprising assessing traversal of the provided survey route by comparing characterizations of the traversed route to a reference, wherein the traversed route characterizations are based at least in part on the motion data and the reference is based at least in part on the provided survey route and wherein the assessment is at least one of: i) an in-route assessment; and ii) a post-route assessment.

17 . The method of claim 16 , further comprising scheduling another traversal of the provided survey route based on the assessment.

18 . The method of claim 16 , further comprising scheduling a traversal of a next survey route, wherein the next survey route is selected from a pool of survey routes based at least in part on current proximity.

19 . The method of claim 18 , wherein the pool of survey routes comprises the provided survey route if a traversal of the provided survey route fails the assessment.

20 . The method of claim 16 , wherein the assessment is an in-route assessment and wherein the traversed route characterizations comprise a distance traveled since a previous benchmark point, a difference between corresponding turn angles, and a difference between corresponding segment lengths.

21 . The method of claim 20 , further comprising directing a discontinuation of a traversal of the provided survey route before completion based at least in part on the assessment.

22 . The method of claim 21 , further comprising scheduling traversal of a next survey route in sequence after the discontinuation, wherein the next survey route is selected from the provided survey route and another survey route based on proximity to a start of the next survey route when the discontinuation occurs.

23 . The method of claim 16 , wherein the assessment is an in-route assessment, further comprising providing feedback during traversal of the provided survey route based at least in part on the assessment.

24 . The method of claim 16 , wherein the assessment is a post-route assessment and wherein the post-route assessment comprises a scoring routine performed after traversal of the provided survey route is complete.

25 . The method of claim 24 , wherein the traversed route characterizations are turn-based and segment-based.

26 . The method of claim 25 , wherein the segment-based traversed route characterizations comprise any one or any combination of: i) a difference between reference segment length and corresponding trajectory segment length; and ii) a determined straightness factor for at least one segment.

27 . The method of claim 25 , wherein the turn-based traversed route characterizations comprise any one or any combination of: i) a difference between reference turn angles and corresponding trajectory turn angles; ii) identification of missed turns; and iii) identification of extra turns.

28 . The method of claim 24 , further comprising scheduling a traversal of a next survey route based on the assessment, wherein the next survey route is selected from a pool of survey routes that comprises the provided survey route if a traversal of the provided survey

Assignees

• Invensense Inc

Inventors

• Elhoushi Mostafa
• Al-Hamad Amr
• Ali Abdelrahman
• Georgy Jacques
• Goodall Chris
• Mahmoud Anas

Classifications

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/34

  Route searching; Route guidance · CPC title

• G01C21/3641

  Personalized guidance, e.g. limited guidance on previously travelled routes · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G05D1/02

  Control of position or course in two dimensions · CPC title