Generation of map data

• US 10,288,425 B2
• Filed: 06/22/2012
• Issued: 05/14/2019
• Est. Priority Date: 06/24/2011
• Status: Active Grant

• Current Assignee: Universite D'Angers
• Original Assignee: Universite D'Angers
• Inventors: Lucidarme, Philippe, Lagrange, Sebastien
• Primary Examiner(s): Schechter, Andrew
• Assistant Examiner(s): Knox, Kaleria
• Application Number:
  US14/128,948
• Publication Number:
  US 20140142891A1
• Time in Patent Office: 2,517 Days
• Field of Search: 702181, 700251, 701 28
• CPC Class Codes: G01C 15/002 Active optical surveying means optical plumbing G01C15/105
• 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

Abstract

A measurement instrument, i.e. a mobile body, measures distances between a current position of the mobile body and obstacles in the environment of the mobile body by: a) taking at least N measurements of distances between the mobile body and the obstacles, by consecutive angular steps of A/N (A is a predetermined angular sector), and combining the distances with the respective angular steps in order to establish map data; b) moving the mobile body and repeating step a) for a new current position of the mobile body; and c) simultaneously determining, according to the distances measured for each angular step of the current position of step b) and the preceding position of step a), the current position of the mobile body in step b) on the map relative to the initial position thereof in step a), and new data of the map.

Claims

1. A method for generating cartographic data, in which at least one mobile device has a processor, means of displacement, and a measurement instrument designed to measure distances between a current position of the mobile device and obstacles in an environment of the mobile device, the method comprising the steps:

a) performing, by the measurement instrument, at least N measurements of distances between the mobile device and obstacles in said environment, by successive angular intervals of A/N each, where A is a predetermined angular sector that defines at least partially said environment of the mobile device, and associating said distances with the respective angular intervals in a work memory of the mobile device by the processor, to establish map data of a map,

b) displacing the mobile device using the means of displacement and repeating step a) for a new current position of the mobile device, and

c) simultaneously i) determining, by the processor, as a function of the distances measured for each angular interval of the current position of step b) and of the previous position of step a), the current position of the mobile device in step b), on said map, with respect to its initial position in step a), and ii) generating, by the processor, new map data of said map as a function of the distances measured for each angular interval of the current position of step b) and of the previous position of step a),

wherein step c) includes;

estimating, by the processor, a function of global distance between the mobile device and the obstacles with respect to the map determined in step a) by a sum of Euclidian distances between each obstacle point determined in step a) and a neighboring point detected as an obstacle in step b), and

determining, by the processor, a local minimum of said global distance function that corresponds to the current position of the mobile device in step b).

2. The method as claimed in claim 1, comprising a step d) of successive reiterations of steps b) and c) to establish a map of at least one object or building.

3. The method as claimed in claim 1, wherein, in step a), said map data are established as a function of an indication of the current position of the mobile device in step a), the method comprising an initial step a₀) of determining the absolute position of the mobile device in space.

4. The method as claimed in claim 1, wherein a plurality of measurement instruments suitable for communicating, each to at least one other measurement instrument, its map data, is provided, the method furthermore comprising a step of cross-checking by the processor of map data arising from various measurement instruments.

5. The method as claimed in claim 1, wherein the global distance function exhibits a single local minimum, corresponding, for the establishment of a two-dimensional map, to two cartesian coordinates X, Y, and an angle θ

defining an orientation of the mobile device in a plane in step b).

6. The method as claimed in claim 1, wherein the global distance function exhibits a single local minimum, corresponding, for the establishment of a map in three-dimensional space, to three cartesian coordinates X, Y, Z, and three angles θ

, ψ

, φ

together defining an orientation of the mobile device in space in step b).

7. The method as claimed in claim 1, wherein:

a look-up table is established beforehand for the correspondence between neighboring points of a central point and estimated euclidian distances between this central point and its neighbors,

for the estimation of the global distance function, after detection of obstacles in step b), for each obstacle, a distance with the closest obstacle point, determined in step a), is determined and said look-up table is referred to in order to determine a euclidian distance between the obstacle and a closer neighbor,

said sum of the euclidian distances, for all the obstacle points, is estimated thereafter.

8. The method as claimed in claim 1, wherein the minimum of said sum of distances corresponds to an orientation and a distance of displacement of the mobile device, and, after determination of said minimum, a new position of the mobile device is determined and new map data is generated.

9. A non-transitory computer readable medium comprising computer program instructions for the implementation of the method as claimed in claim 1, when the instructions are executed by the processor.

10. A mobile device for generating cartographic data for the implementation of the method as claimed in claim 1, the mobile device comprising at least one measurement instrument, for measurements of distances, comprising:

a unit for measurements of distances for the implementation of step a),

means of displacement of the mobile device for the implementation of step b),

means for communicating the measured data to a calculation unit for calculating map data and current position of the robot in said map, and

said calculation unit,

wherein said calculation unit comprises the processor and the work memory for;

associating the measured distances with the respective angular measurement intervals in the work memory, and

for the implementation of step c), simultaneously i) determining, as a function of the distances measured for each angular interval of successive current positions, the last current position of the measurement instrument, on said map, and ii) generating new map data of said map as a function of the distances measured for each angular interval of successive current positions,

by estimating a function of global distance between the mobile device and the obstacles, with respect to the map determined in step a) by a sum of Euclidian distances between each obstacle point determined in step a) and a neighboring point detected as an obstacle in step b), and

by determining a local minimum of said global distance function that corresponds to the current position of the mobile device in step b).