Method and system, computer program comprising program code means, and computer program product for forming a graph structure in order to describe an area with a free area and an occupied area

• US 20050159879A1
• Filed: 09/19/2003
• Published: 07/21/2005
• Est. Priority Date: 10/23/2002
• Status: Active Grant

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: De Graeve, Charles-Marie, Fiegert, Michael
• Granted Patent: US 7,765,499 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 16/29 Geographical information databases

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.

Claims

1-20. -20. (canceled)

21. A method 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; and

forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.

22. The method according to claim 21, wherein

the topological graph structure is determined using a Shock graph, a “

medial axis”

or a Voronoi graph.

23. The method in accordance with claim 21, wherein

the location information for the adjacent occupied area is relative location information with regard to the selected point, including displacement information and direction information, the direction information comprising an angle specification.

24. The method in accordance with claim 21, wherein the location information for the adjacent occupied area is absolute location information comprising coordinates of the adjacent occupied area.

25. The method in accordance with claim 21, wherein

a plurality of points are selected in the topological graph structure,

for each selected point an occupied point is selected and location information is determined, and

the graph structure is formed from all selected points and the associated location information.

26. The method according to claim 24, wherein

the selected points are selected depending on a regularity of the topological graph structure, and

fewer points are selected for a more regular topological graph structure.

27. The method in accordance with claim 21, further comprising:

for the selected point of the topological graph structure, determining at least one additional adjacent occupied area;

selecting an occupied point for each additional occupied area; and

determining associated location information for each additional occupied area.

28. The method according to claim 27, wherein

a node point is selected in the topological graph structure, and

for the node point, at least two adjacent occupied areas are determined, occupied points are selected and associated location information is determined.

29. The method in accordance with claim 21, wherein

the topological graph structure is determined using sensor measurements generating distance information, the sensor measurements being selected from the group consisting of laser measurements, ultrasound measurements and measurements of video systems.

30. The method in accordance with claim 21, wherein

the topological graph structure is determined using a local geometrical map of the area.

31. The method in accordance with claim 21, wherein

the location has a plurality of sub-areas, and

the graph is formed by combining graphs for the plurality of sub-areas.

32. The method according to claim 31, further comprising:

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.

33. The method according to claim 32, wherein the local grid map is compared with the graph by overlaying the local grid map and the graph.

34. The method according to claim 32, wherein

the location has a plurality of sub-areas,

the graph is formed by combining graphs for the plurality of sub-areas, and

the local grid map is compared with the graph by individually comparing the local grid map with the graphs for the sub-areas.

35. The method according to claim 32, wherein

the local grid map is determined using information from a mobile unit,

the mobile unit continually generates local grid maps as the mobile unit moves, and

the graph is continually updated.

36. The method according to claim 21, further comprising:

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.

37. The method according to claim 36 wherein

the location has a plurality of sub-areas,

the graph is formed by combining graphs for the plurality of sub-areas,

the local grid map is compared with the graph by individually comparing the local grid map with the graphs for the sub-areas.

38. The method in accordance with claim 36, wherein

the local grid map is determined using information from a mobile unit, and

the mobile unit is navigated through the location using the graph.

39. A system to form a graph a location having a free area and an occupied area, comprising:

a structure determination unit to determine a topological graph structure for the free area;

a selection unit to select a point in the topological graph structure;

an obstacle identification unit to identify an obstacle and to select an occupied point for the obstacle, the occupied point being at a shortest distance to the selected point of the topological graph structure;

a location determination unit to determine associated location information for the occupied point; and

a graph generation unit, to form the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.

40. A computer-readable medium storing program to control a computer to perform a method for forming a graph structure to describe a location having a free area and an occupied area, the method 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; and

forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.