# US 2023/0408681 A1 · Method for determining a graph modelling a geographical zone, system for navigating within the zone using said graph

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0408681 A1
- Document ID: US20230408681A1
- Status: Published application
- Kind: A1
- Application number: 18/251,685
- Filed: 2021-10-27
- Published: 2023-12-21
- Earliest claimed: 2020-11-04
- Assignees: Orange
- Applicants: Orange
- Inventors: Dinh Thuy Phan Huy; Rita Ibrahim
- Web page: https://patentgrep.com/patent/US20230408681A1

## CPC

- G01S 13/89: for mapping or imaging
- G01C 21/206: {specially adapted for indoor navigation}
- G01C 21/383: {Indoor data}
- G01S 13/876: {Combination of several spaced transponders or reflectors of known location for determining the position of a receiver (G01S13/874 takes precedence)}
- G01S 13/878: {Combination of several spaced transmitters or receivers of known location for determining the position of a transponder or a reflector (G01S13/874 takes precedence)}
- G01S 13/765: {with exchange of information between interrogator and responder}
- G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
- 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

A method is described for determining a graph modelling a zone comprising at least one transmitting device for backscattering an ambient signal, emitted by a transmitting device, towards a receiving device (for detection by said receiving device. The method includes obtaining at least one coverage area of said zone, said at least one coverage area having been determined for a location of said zone and corresponding to a datum identifying the transmitting device or devices detected by the receiving device when the transmitting device occupies said location. The method also includes determining a graph of which at least one vertex consists of said at least one coverage area, two vertices of said graph being connected by an edge if the coverage areas relating to said two vertices comprise at least one transmitting device detected in common.

## Claims

### Claim 1

A method for determining a graph modeling a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said method comprising:
obtaining at least one footprint of said geographical area, said at least one footprint having been determined for a location of said geographical area and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when the emitter device emits the ambient signal from the location associated with said footprint, and
determining a graph having at least one vertex, each vertex of said graph formed of a respective footprint of said at least one footprint, two vertices of said graph being connected by an edge if footprints relating to said two vertices include at least one transmitter device detected in common.

### Claim 2

A method for emitting an ambient signal in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device the ambient signal emitted by an emitter device for detection by said receiver device, said method including steps of:
moving the emitter device so as to reach at least one location of said geographical area,
emitting said ambient signal when said at least one location is reached.

### Claim 3 (depends on 1)

A method for determining an intermediate path in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said intermediate path being configured to connect a starting location to a neighborhood of a target transmitter device among said at least one transmitter device, said method comprising:
obtaining a current footprint determined for said starting location and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when said receiver device occupies said starting location,
determining whether the current footprint forms a vertex of a graph determined according to the method of claim 1,
upon determining that said current footprint forms a vertex of the graph determined according to the method of claim 1, determining a sequence of footprints of the graph, said sequence forming an intermediate path of minimum length to connect the starting location to a footprint of the graph identifying said target transmitter device, and
upon determining that said current footprint does not form a vertex of the graph determined according to the method of claim 1;
updating the graph so that the current footprint forms a vertex of the updated graph, two vertices of said updated graph being connected by an edge if the footprints relating to said two vertices include at least one transmitter device detected in common,
determining a sequence of footprints of the updated graph, said sequence forming an intermediate path of minimum length to connect the starting location to a footprint of the updated graph identifying said target transmitter device.

### Claim 4 (depends on 3)

The method of claim 3, wherein the intermediate path is determined by means of the Dijkstra algorithm.

### Claim 5 (depends on 3)

A method for moving in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said intermediate path being configured to connect a starting location to a neighborhood of a target transmitter device among said at least one transmitter device, said method comprising:
emitting the ambient signal at said starting location,
obtaining a locating set of transmitter devices formed of any transmitter devices identified by the first footprint of an intermediate path determined according to the method of claim 3 and not identified by a current footprint determined for said starting location during the determination of said intermediate path,
obtaining at least one sensory data making it possible to identify in a sensory manner, in the environment of said geographical area, the locating set of transmitter devices,
moving the emitter device in the area so as to reach an intermediate location satisfying a neighborhood criterion with at least one transmitter device belonging to said locating set, said movement being performed by using said sensory data.

### Claim 6 (depends on 3)

A method for determining an intermediate location in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said receiver device being intended to connect a starting location to a neighborhood of a given transmitter device among said at least one transmitter device, said method including steps of:
obtaining a locating set of transmitter devices formed of any transmitter devices identified by a first footprint of an intermediate path determined according to the method of claim 3 and not identified by a current footprint determined for said starting location during the determination of said intermediate path, and
during movement of the emitter device in the geographical area to reach an intermediate location, said movement being performed by using sensory data making it possible to identify in a sensory manner, in the environment of said geographical area, the locating set of transmitter devices, the emitter device emitting the ambient signal during its movement:
detecting, by said receiver device, a transmitter device,
determining an intermediate location satisfying a neighborhood criterion making it possible to verify whether the emitter device has reached a location for which the receiver device detects, from the ambient signal emitted by said transmitter device, a number of transmitter devices at least equal to a given fraction of the number of transmitter devices belonging to said locating set, and
transmitting to the emitter device an information data able to indicate that the intermediate location is reached.

### Claim 7 (depends on 2)

A method for navigating in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said method including a set of steps of comprising:
moving in said geographical area by performing at least one iteration of the following set of steps:
determining an intermediate path using the method of claim 2;
emitting, at said starting location, the ambient signal,
obtaining a locating set of transmitter devices formed of any transmitter devices identified by a first footprint of the intermediate path and not identified by the current footprint determined for said starting location during the determination of said intermediate path,
obtaining at least one sensory data making it possible to identify in a sensory manner, in the environment of said geographical area, the locating set of transmitter devices, and
moving the emitter device in the geographical area to reach an intermediate location satisfying a neighborhood criterion with at least one transmitter device belonging to said locating set, said movement being performed by using said sensory data,
said set of steps being iterated as long as the first footprint of the intermediate path does not identify said target transmitter device, the starting location considered in a second or subsequent iteration of said set of steps corresponding to the intermediate location considered in the previous iteration, and the graph considered in a second or subsequent iteration of said set of steps for a possible update corresponding to the graph to which the intermediate path determined during the previous iteration belongs.

### Claim 8 (depends on 5)

The method of claim 5, wherein said neighborhood criterion is satisfied if the emitter device reaches a location at which is situated a given or any transmitter device among the transmitter devices of said locating set.

### Claim 9 (depends on 7)

The method according to claim 7, wherein said set of steps for which at least one iteration is performed also includes a step of determining an intermediate location satisfying a neighborhood criterion making it possible to verify whether the emitter device has reached a location for which the receiver device detects, from the ambient signal emitted by said transmitter device, a number of transmitter devices at least equal to a given fraction of the number of transmitter devices belonging to said locating set.

### Claim 10

A device for determining a graph modeling a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said determination device including:
an obtaining module configured to obtain at least one footprint of said geographical area, said at least one footprint having been determined for a location of said geographical area and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when the emitter device emits the ambient signal from the location associated with said footprint, and
a determination module configured to determine a graph having at least one vertex, each vertex of said graph formed of a respective footprint of said at least one footprint, two vertices of said graph being connected by an edge if the footprints relating to said two vertices include at least one transmitter device detected in common.

### Claim 11

A device for emitting an ambient signal in a geographical area, said area including at least one transmitter device configured to backscatter towards a receiver device the ambient signal emitted by said emitter device so as to be detected by said receiver device, said emitter device including an emission module configured to emit said ambient signal when, following a movement of said emitter device to reach at least one location of said geographical area, said at least one location has been reached.

### Claim 12 (depends on 10)

A device for determining an intermediate path in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said intermediate path being configured to connect a starting location to a neighborhood of a given target transmitter device, among said at least one transmitter device, said determination device including:
a first obtaining module configured to obtain a graph determined by the device of claim 10,
a second obtaining module configured to obtain a current footprint determined for said starting location and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when said receiver device occupies said starting location,
a test module configured to verify whether said current footprint forms or does not form a vertex of the obtained graph,
an update module configured to, if said current footprint does not form a vertex of the obtained graph, update the obtained graph so that the current footprint forms a vertex of the updated graph, two vertices of said updated graph being connected by an edge if the footprints relating to said two vertices include at least one transmitter device detected in common,
a determination module configured to determine a sequence of footprints of the obtained graph or, if the graph was updated by the update module, the updated graph, said sequence forming an intermediate path of minimum length to connect the starting location to a footprint of the obtained graph or the updated graph identifying said target transmitter device.

### Claim 13 (depends on 12)

A device for emitting an ambient signal in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by said emitter device for detection by said receiver device, said emitter device being intended to connect a starting location to a neighborhood of a given transmitter device among said at least one transmitter device, and including:
an emission module configured to emit the ambient signal at said starting location,
an obtaining module configured to obtain a locating set of transmitter devices formed of any transmitter devices identified by a first footprint of an intermediate path determined by the device of claim 12 and not identified by a current footprint determined for said starting location during the determination of said intermediate path,
an obtaining module configured to obtain at least one sensory data, making it possible to identify in a sensory manner, in the environment of said geographical area, the locating set of transmitter devices.

### Claim 14 (depends on 12)

A device for determining an intermediate location location in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said emitter device being intended to connect a starting location to a neighborhood of a given transmitter device among said at least one transmitter device, said determination device including:
an obtaining module configured to obtain a locating set of transmitter devices formed of any transmitter devices identified by the first footprint of an intermediate path determined by the device of claim 12 and not identified by a current footprint determined for said starting location during the determination of said intermediate path,
a detection module configured to detect, when the emitter device moves in the area by emitting the ambient signal, one or several transmitter devices,
a determination module configured to determine, when the emitter device moves in the area by emitting the ambient signal, an intermediate location called satisfying a neighborhood criterion making it possible to verify whether the emitter device has reached a location for which the receiver device detects, from the ambient signal emitted by said emitter device, a number of transmitter devices at least equal to a given fraction of the number of transmitter devices belonging to said locating set, and
a transmission module configured to transmit to the emitter device an information data able to indicate that the intermediate location is reached.

### Claim 15 (depends on 14)

A system for navigating in a geographical area, said geographical area including at least one transmitter device configured to backscatter towards a receiver device an ambient signal emitted by an emitter device for detection by said receiver device, said system including:
an emitter device including an emission module configured to emit said ambient signal when, following a movement of said emitter device to reach at least one location of said area, said at least one location has been reached;
a graph determining device for determining a graph modeling the geographical area, the graph determining device comprising:
an obtaining module configured to obtain at least one footprint of said geographical area, said at least one footprint having been determined for a location of said geographical area and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when the emitter device emits the ambient signal from the location associated with said footprint, and
a determination module configured to determine a graph having a vertex formed of said at least one footprint, two vertices of said graph being connected by an edge if footprints relating to said two vertices include at least one transmitter device detected in common;
an intermediate path determination device including:
a first obtaining module configured to obtain a graph determined by the graph determining device,
a second obtaining module configured to obtain a current footprint determined for said starting location and corresponding to a data identifying, among said at least one transmitter device, any transmitter devices detected by the receiver device when said receiver device occupies said starting location,
a test module configured to verify whether said current footprint forms or does not form a vertex of the obtained graph,
an update module configured to, if said current footprint does not form a vertex of the obtained graph, update the obtained graph so that the current footprint forms a vertex of the updated graph, two vertices of said updated graph being connected by an edge if the footprints relating to said two vertices include at least one transmitter device detected in common,
a determination module configured to determine a sequence of footprints of the obtained graph or, if the graph was updated by the update module, the updated graph, said sequence forming an intermediate path of minimum length to connect the starting location to a footprint of the obtained graph or the updated graph identifying said target transmitter device; and
the intermediate location determining device of claim 14;
wherein the emitter device further comprises:
an obtaining module configured to obtain a locating set of transmitter devices formed of any transmitter devices identified by a first footprint the intermediate path determined by the intermediate path determining device and not identified by a current footprint determined for said starting location during the determination of said intermediate path, and
an obtaining module configured to obtain at least one sensory data making it possible to identify in a sensory manner, in the environment of said geographical area, the locating set of transmitter devices.
