Patent ID: 7765499

Claim:
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.