Method, system, and computer product for forming a graph structure that describes free and occupied areas
First Claim
Patent Images
1. A method implemented in a computer for forming a graph to describe a location having a free area and an occupied area, comprising:
- determining a topological graph structure for the free area;
selecting a point in the topological graph structure;
for the selected point of the topological graph structure, determining an adjacent occupied area;
selecting an occupied point for the adjacent occupied area, the occupied point being at a shortest distance to the selected point of the topological graph structure;
determining associated location information for the occupied point;
forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point;
determining a local grid map for a portion of the location;
comparing the local grid map with the graph;
determining a position of the local grid map with respect to the graph based on the comparison; and
using information from the local grid map to supplement the graph, at the position, whereinthe location has a plurality of sub-areas and the graph is formed by combining graphs for the plurality of sub-areas.
1 Assignment
0 Petitions
Accused Products
Abstract
A graph structure is generated to describe an area with a free area and an occupied area. In this case a topological graph structure for the free area is determined. A point of the topological graph structure is selected and for this a nearest adjacent occupied area point is determined. For this nearest adjacent occupied area point location information is determined. The graph structure is formed from at least the selected point of the topological graph structure and from the associated location information of the nearest adjacent occupied area point.
40 Citations
16 Claims
-
1. A method implemented in a computer for forming a graph to describe a location having a free area and an occupied area, comprising:
-
determining a topological graph structure for the free area; selecting a point in the topological graph structure; for the selected point of the topological graph structure, determining an adjacent occupied area; selecting an occupied point for the adjacent occupied area, the occupied point being at a shortest distance to the selected point of the topological graph structure; determining associated location information for the occupied point; forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point; determining a local grid map for a portion of the location; comparing the local grid map with the graph; determining a position of the local grid map with respect to the graph based on the comparison; and using information from the local grid map to supplement the graph, at the position, wherein the location has a plurality of sub-areas and the graph is formed by combining graphs for the plurality of sub-areas. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method implemented in a computer for forming a graph to describe a location having a free area and an occupied area, comprising:
-
determining a topological graph structure for the free area; selecting a point in the topological graph structure; for the selected point of the topological graph structure, determining an adjacent occupied area; selecting an occupied point for the adjacent occupied area, the occupied point being at a shortest distance to the selected point of the topological graph structure; determining associated location information for the occupied point; forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point; determining a local grid map for a portion of the location, at an unknown position within the location; comparing the local grid map with the graph; and determining the position of the local grid map with respect to the graph based on the comparison. - View Dependent Claims (15, 16)
-
Specification