Method and apparatus for determining location of objects based on range readings from multiple sensors

• US 6,522,288 B1
• Filed: 01/09/2002
• Issued: 02/18/2003
• Est. Priority Date: 01/09/2002
• Status: Expired due to Term

• Current Assignee: Veoneer, Inc. (SSW Partners LP)
• Original Assignee: M/A Com
• Inventors: Paradie, Michael John, Forde, John James, Hunt, Andrew Evan
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): ALSOMIRI, ISAM A
• Application Number:
  US10/042,903
• Time in Patent Office: 405 Days
• Field of Search: 342/71-72, 342/70, 342/145-146, 342/189-192, 342/435-436
• US Class Current: 342/145
• CPC Class Codes: G01S 13/08 Systems for measuring distance only indirect measurement G01S13/46
• CPC Class Codes: G01S 13/46 Indirect determination of position data
• CPC Class Codes: G01S 13/726 Multiple target tracking
• CPC Class Codes: G01S 13/878 Combination of several spaced transmitters or receivers of known location for determining the position of a transponder or a reflector G01S13/874 takes precedence
• CPC Class Codes: G01S 13/931 of land vehicles
• CPC Class Codes: G01S 15/876 Combination of several spaced transmitters or receivers of known location for determining the position of a transponder or a reflector G01S15/872 takes precedence
• CPC Class Codes: G01S 2013/466 by Trilateration, i.e. two antennas or two sensors determine separately the distance to a target, whereby with the knowledge of the baseline length, i.e. the distance between the antennas or sensors, the position data of the target is determined
• CPC Class Codes: G01S 2013/93275 in the bumper area

Abstract

The invention is a method and apparatus for determining the locations of a plurality of actual objects based on the output of a plurality of range sensors. A multiplicity of range measurements are obtained from a plurality of sensors, each sensor capable of providing a multiplicity of range measurements. The range measurements from the plurality of sensors are correlated with each other to generate a list of potential objects and to order that list of potential objects from highest to lowest likelihood of being an actual object. The order may be based upon a cumulative error of the individual sensor measurements upon which the potential object is based. The ordered list of potential objects is then pared down to a smaller list of actual objects by assuming that the potential object highest in the ordered list as an actual object, and then removing from the list all other lower-ordered potential objects that are based on any of the range measurements upon which the selected object is based. The process is repeated for the next highest potential object remaining on the list until all potential objects on the list have either been selected as an actual object or removed from the list.

Claims

1. A method of determining the locations of a plurality of actual objects based on range measurements of a plurality of range sensors, each sensor capable of providing a multiplicity of range measurements, said method comprising the steps of:

(1) obtaining from said sensors a plurality of range measurements;

(2) correlating said range measurements of said plurality of sensors to generate a list of potential objects and their locations, each of said potential objects being based on a plurality of range measurements;

(3) ordering said list of potential objects from highest to lowest likelihood of being an actual object;

(4) selecting a potential object highest on said ordered list as an actual object;

(5) determining the range measurements upon which said potential object selected in step (4) is based;

(6) removing from said ordered list said potential object selected in step (4) as well as any potential objects ordered lower than said potential object selected in step (4) that are based on any of said range measurements upon which said potential object selected in step (4) is based; and

(7) repeating steps (4)-(6) until all potential objects have been removed from said list.

2. The method of claim 1 wherein step (3) comprises the steps of:

(3.1) calculating a cumulative error of said range measurements upon which a potential object is based; and

(3.2) ordering said list in accordance with said cumulative error calculation.

3. The method of claim 2 wherein step (3.1) comprises the steps of:

(3.1.1) for at least one of said range measurements upon which a potential object is based, determining an error between said at least one range measurement and a range of said sensor that generated said at least one range measurement to said determined location of said potential object;

(3.1.2) squaring each of said errors; and

(3.1.3) summing said squared errors.

4. The method of claim 3 wherein said plurality of sensors comprises at least three sensors.

5. The method of claim 4 wherein step (2) comprises the step of excluding from said list any potential objects that are based upon range measurements from less than a predetermined number of sensors.

6. The method of claim 5 wherein step (2) comprises enforcing a rule that no potential object can be based on more than one range measurement from any one sensor.

7. The method of claim 4 wherein said plurality of sensors comprises four sensors.

8. The method of claim 7 wherein step (2) comprises excluding from said list any potential objects that are based upon range measurements from less than three sensors.

9. The method of claim 1 wherein, in step (2), said locations are determined by trilateration.

10. The method of claim 9 wherein step (2) comprises the steps of:

(2.1) for each individual range measurement, determining a locus of points defined by said range measurement;

(2.2) for each said locus of points, determining which of said loci of points corresponding to range measurements from other sensors overlaps said locus of points;

(2.3) putting on said list a potential object corresponding to every locus of points that intersects at least a predetermined number of other loci of points corresponding to range measurements from other sensors.

11. The method of claim 7 wherein step (2) comprises the steps of:

(2.4) for each individual range measurement, determining a locus of points defined by said range measurement;

(2.5) for each said locus of points, determining which of said loci of points corresponding to range measurements from other sensors overlaps said locus of points;

(2.6) putting in said list a potential object corresponding to every locus of points that intersects at least a predetermined number of other loci of points corresponding to range measurements from other sensors.

12. The method of claim 4 wherein step (2) comprises using said range measurements of only the two sensors most distant from each other to generate said locations.

13. The method of claim 12 wherein step (3.1.1) comprises determining said error only for said range measurements upon which said potential object is based other than said two sensors most distant from each other.

14. The method of claim 8 wherein step (2) comprises using said range measurements of only the two sensors most distant from each other to generate said locations.

15. The method of claim 11 further comprising the step of:

(2.7) using said range measurements of only the two sensors most distant from each other to generate said locations.

16. The method of claim 10 wherein said method is performed assuming a two dimensional environment.

17. The method of claim 16 wherein said loci of points comprise circles.

18. The method of claim 8 wherein step (1) comprises limiting a number of range measurements from each sensor to a predetermined number.

19. The method of claim 18 wherein said predetermined number of range measurements from each sensor is ten.

20. A method of determining the locations of a plurality of actual objects based on range measurements from a plurality of range sensors, each sensor capable of outputting a multiplicity of range measurements, said method comprising the steps of:

(1) obtaining from said sensors a plurality of range measurements;

(2) correlating said range measurements of said plurality of sensors to generate a list of potential objects and their locations, each of said potential objects being based on range measurements from a plurality of said sensors;

(3) ordering said list of potential objects from highest to lowest likelihood of being an actual object;

(4) selecting a potential object highest on said ordered list as an actual object;

(5) removing from said ordered list said potential object selected in step (4) as well as any potential objects ordered lower than said potential object selected in step (4) that are based on any of said range measurements upon which said potential object selected in step (4) is based; and

(6) repeating steps (4) and (5) until all potential objects have been removed from said list.

21. An apparatus for determining the locations of a plurality of actual objects based on range measurements said apparatus comprising:

a plurality of range sensors, each sensor capable of providing a multiplicity of range measurements;

a digital processor adapted to (a) obtain from said sensors a plurality of range measurements, (b) correlate said range measurements of said plurality of sensors to generate a list of potential objects and their locations, each of said potential objects being based on a plurality of range measurements, (c) order said list of potential objects from highest to lowest likelihood of being an actual object, (d) select a potential object highest on said ordered list as an actual object, (e) determine the range measurements upon which said selected potential object is based, (f remove from said ordered list said selected potential object as well as any potential objects ordered lower than said selected potential object that are based on any of said range measurements upon which said selected potential object is based, and (g) repeat processes (d)-(f) until all potential objects have been removed from said list.

22. The apparatus of claim 21 wherein, in performing step (c), said digital processor calculates a cumulative error of said range measurements upon which a potential object is based, and orders said list in accordance with said cumulative error calculation.

23. The apparatus of claim 22 wherein said processor calculates said cumulative error by determining for at least one of said range measurements upon which a potential object is based, an error between said at least one range measurement and a range of said sensor that generated said at least one range measurement to said determined location of said potential object, squaring each of said distances, and summing said squared distances.

24. The apparatus of claim 23 wherein said plurality of sensors comprises at least three sensors.

25. The apparatus of claim 24 wherein said digital processor is adapted to include in said list only potential objects that are based upon range measurements from at least a predetermined number of sensors.

26. The apparatus of claim 25 wherein process (b) comprises enforcing a rule that no potential object can be based on more than one range measurement from any one sensor.

27. The apparatus of claim 24 wherein said plurality of sensors comprises four sensors.

28. The apparatus of claim 27 wherein said digital processor is adapted to include in said list only potential objects that are based upon range measurements from it at least three sensors.

29. The apparatus of claim 21 wherein said digital processor determines said locations by trilateration.

30. The apparatus of claim 25 wherein said digital processor uses said range measurements of only the two sensors most distant from each other to generate said locations.

31. The apparatus of claim 30 wherein said process calculates said cumulative error using only said range measurements upon which said potential object is based other than said two sensors most distant from each other.

32. The apparatus of claim 29 wherein said digital processor is adapted to assume a two dimensional environment.

33. The apparatus of claim 28 wherein each of said sensors generate no more than a predetermined number of range measurements.

34. The apparatus of claim 33 wherein said predetermined number of range measurements is ten.

35. The apparatus of claim 27 wherein said sensors are arranged in a line.

36. An automobile comprising said apparatus of claim 21.

37. The automobile of claim 36 further comprising:

a processor adapted to determine tracks of said selected objects based on a plurality of temporally spaced multiplicity of range measurements.

38. The automobile of claim 37 further comprising:

a processor for controlling the velocity of said automobile based on said tracks.