# US 12,222,205 B2 · Systems and methods for utilizing modeling to automatically generate paths for indoor navigation

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

- Number: US 12,222,205 B2
- Document ID: US12222205B2
- Status: Granted
- Kind: B2
- Application number: 17/663,522
- Filed: 2022-05-16
- Published: 2022-09-01
- Granted: 2025-02-11
- Earliest claimed: 2019-11-22
- Assignees: Verizon Patent and Licensing Inc.
- Applicants: Verizon Patent and Licensing Inc.
- Inventors: Hannah Nicole Aldeborgh; Florin Alexandrescu
- Web page: https://patentgrep.com/patent/US12222205B2

## CPC

- G01C 21/206: {specially adapted for indoor navigation}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)}
- G05D 1/227: Handing over between remote control and on-board control; Handing over between remote control arrangements
- G06N 20/00: Machine learning
- G06N 20/10: using kernel methods, e.g. support vector machines [SVM]
- H04W 4/025: {using location based information parameters}
- H04W 4/33: for indoor environments, e.g. buildings
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- 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)
- G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## Abstract

A device may receive an architectural floor plan of an interior of a building, and may process the architectural floor plan, with a vectorization model, to generate a vectorized floor plan of polygons. The device may process the vectorized floor plan, with a convex hull model, to create convex hull polygons around the polygons of the vectorized floor plan, and may reduce a quantity of vertices associated with the convex hull polygons to generate simplified convex hull polygons. The device may generate, based on the simplified convex hull polygons, one of a visibility graph that identifies potential paths through the interior of the building, or a walking path network through the interior. The device may process the one of the visibility graph or the walking path network, with a pathfinding model, to identify paths through the interior of the building, and may perform actions based on the identified paths.

## Claims

### Claim 1

A method, comprising:
processing, by a device, a vectorized floor plan, with a first model, to create convex hull polygons around polygons of the vectorized floor plan;
generating, by the device and based on the convex hull polygons, one or more of:
a visibility graph that identifies potential paths through an interior of a building associated with the vectorized floor plan,
wherein the visibility graph is based on connecting pairs of points that enable lines to be drawn without touching the convex hull polygons, or
a walking path network through the interior of the building;
processing, by the device, at least one of the one of the visibility graph or the walking path network, with a second model, to identify paths through the interior of the building; and
providing, by the device, (i) the paths to enable one or more navigation actions associated with the paths, the paths for display via a map on a user interface of a client device, and (ii) turn-by-turn directions for one or more of the paths.

### Claim 2 (depends on 1)

The method of claim 1, wherein the vectorized floor plan is processed to remove extraneous features.

### Claim 3 (depends on 1)

The method of claim 1, wherein the first model includes a convex hull model.

### Claim 4 (depends on 1)

The method of claim 1, wherein the convex hull polygons include vertices that correspond to vertices in corresponding polygons included in the vectorized floor plan.

### Claim 5 (depends on 1)

The method of claim 1, wherein processing at least one of the visibility graph or the walking path network comprises:
subtracting areas occupied by the convex hull polygons from a representation of the interior of the building to generate a walkable space,
processing the walkable space with a third model to generate a diagram of walkable space, and
generating the walking path network based on the diagram of walkable space.

### Claim 6 (depends on 1)

The method of claim 1, wherein the second model comprises one or more of:
an A* search model, or
a Dijkstra's shortest path first model.

### Claim 7

A non-transitory computer-readable medium storing a set of instructions, the set of instructions comprising:
one or more instructions that, when executed by one or more processors of a device, cause the device to:
process a vectorized floor plan to create convex hull polygons around polygons of the vectorized floor plan;
generate, based on the convex hull polygons, at least one of:
a visibility graph that identifies potential paths through an interior of a building associated with the vectorized floor plan, or
a walking path network through the interior of the building;
process at least one of the visibility graph or the walking path network to identify paths through the interior of the building,
wherein the one or more instructions, that cause the one or more processors to process the at least one of the visibility graph or the walking path network, cause the device to:
subtract areas occupied by the convex hull polygons from a representation of the interior of the building to generate a walkable space,
process the walkable space with a third model to generate a diagram of walkable space, and
generate the walking path network based on the diagram of walkable space; and
provide, (i) for display via a map on a user interface of a client device, the paths to enable one or more navigation actions associated with the paths and (ii) turn-by-turn directions for one or more of the paths.

### Claim 8 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the vectorized floor plan is based on an architectural floor plan that represents the interior of the building.

### Claim 9 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the one or more instructions, that cause device to process the vectorized floor plan, cause the device to:
process the vectorized floor plan to create the convex hull polygons around polygons of the vectorized floor plan.

### Claim 10 (depends on 7)

The non-transitory computer-readable medium of claim 7, where the one or more instructions, that cause the device to generate the walking path network, cause the device to:
process the walkable space associated with the interior of the building, with a Voronoi diagram model, to generate a Voronoi diagram of the walkable space; and
prune the Voronoi diagram to generate the walking path network.

### Claim 11 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the one or more instructions further cause the device to:
simplify the convex hull polygons to reduce a quantity of vertices associated with the convex hull polygons.

### Claim 12 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the visibility graph represents potential lines of sight within the interior of the building.

### Claim 13 (depends on 7)

The non-transitory computer-readable medium of claim 7, where the one or more instructions, that cause the device to generate the walking path network, cause the device to:
generate the walkable space;
convert edges of the walkable space into evenly-spaced points to be utilized as seeds;
calculate interpolation distances between the seeds;
generate a Voronoi diagram of the walkable space based on calculating the interpolation distances between the seeds; and
prune the Voronoi diagram to generate the walking path network.

### Claim 14

A device, comprising:
one or more processors configured to:
process, using a model, a vectorized floor plan to create convex hull polygons around polygons of the vectorized floor plan;
generate, based on the convex hull polygons, at least one of:
a visibility graph that identifies potential paths through an interior of a building associated with the vectorized floor plan, or
a walking path network through the interior of the building,
wherein the one or more processors, to generate the walking path network, are configured to:
process walkable space associated with the interior of the building, with a Voronoi diagram model, to generate a Voronoi diagram of the walkable space; and
prune the Voronoi diagram to generate the walking path network;
process the at least one of the visibility graph or the walking path network to identify paths through the interior of the building; and
provide, (i) for display via a map on a user interface of a client device, the paths to enable one or more navigation actions associated with the paths and (ii) turn-by-turn directions for one or more of the paths.

### Claim 15 (depends on 14)

The device of claim 14, wherein the one or more processors are further configured to:
reduce a quantity of vertices associated with the convex hull polygons.

### Claim 16 (depends on 14)

The device of claim 14, wherein the one or more processors are further configured to:
receive information indicating a modification to an architectural floor plan of the interior of the building; and
modify at least one of the paths through the interior of the building based on the information indicating the modification.

### Claim 17 (depends on 14)

The device of claim 14, wherein the one or more processors, to generate the visibility graph, are configured to:
connect pairs of points between which lines can be drawn, without touching the convex hull polygons and without going over an outer edge of the building, to generate the visibility graph.

### Claim 18 (depends on 14)

The device of claim 14, wherein the model is trained based on a plurality of architectural floor plans that include a plurality of extraneous features not associated with actual physical features of a plurality of buildings.

### Claim 19 (depends on 14)

The device of claim 14, wherein the one or more processors are further configured to:
perform the one or more navigation actions based on the identified paths.