System for relative vehicle navigation

• US 6,694,233 B1
• Filed: 06/03/2002
• Issued: 02/17/2004
• Est. Priority Date: 07/23/1999
• Status: Expired due to Term

• Current Assignee: Commonwealth Scientific & Industrial Research Organisation (Commonwealth Of Australia As Represented By Department Of Industry, Innovation, Climate Change, Science, Research And Tertiary Education)
• Original Assignee: Commonwealth Scientific & Industrial Research Organisation (Commonwealth Of Australia As Represented By Department Of Industry, Innovation, Climate Change, Science, Research And Tertiary Education)
• Inventors: Duff, Elliot Stanley, Cunningham, Jock Bernard, Roberts, Jonathan Michael, Corke, Peter Ian
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US10/031,775
• Time in Patent Office: 624 Days
• Field of Search: 701/23, 701/25, 701/200, 701/202, 701/205, 701/207, 701/217, 731/78.R, 340/988
• US Class Current: 701/23
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means

Abstract

A navigation system for navigating an autonomous vehicle along a path that is confined by walls that are within range of on-board sensors is described. The system determines the relative location and orientation of the walls with respect to the vehicle. The system controls the steering angle and the ground speed of the vehicle by employing: (a) range data to establish free space in front of vehicle; (b) active contours to generate a desired path; (c) driving hints to guide the active contours along arcs and open areas; (d) steering hints to confine the active contours to a specific domain of free space, at, for instance, intersections; and (e) a desired path to generate steering demand or velocity.

Claims

1. A means of localizing a vehicle without localization infrastructure comprising:

(a) a means of establishing a starting position,

(b) using dead-reckoning to estimate the vehicle position, wherein the dead reckoning is such that;

(1) the vehicle position is defined as a distance to a next landmark,

(2) the vehicle position is reset once the next landmark has been passed,

(c) using range data to find topology of free space in front of the vehicle,

(d) identifying changes in the topology as the next landmark,

(e) matching said next landmark to a nodal-map to update the vehicle position,

(f) using knowledge of position and the nodal-map to pass driving hints to vehicle control, and

(g) using knowledge of the position and the nodal-path to pass steering hints to the vehicle control.

2. The means of claim 1, wherein the range data to find the topology of free space in front of the vehicle is such to:

(a) offset and re-scale data to front centre of vehicle,

(b) smooth and resample the range data,

(c) generate a contour of equally spaced points.

3. The means of claim 2, wherein the identification of changes in topology as landmarks comprises:

(a) skeletonizing free space,

(b) pruning branches that are insignificant,

(c) label remaining intersections as landmarks.

4. The means of claim 3, wherein the matching of the landmarks to the nodal-map to update the vehicle position comprises:

(a) ignoring the landmarks that are not expected (from nodal-map &

position), and

(b) matching based upon minimum radius, energy, and connectivity.

5. The means of claim 4, wherein the use of knowledge of the position and the nodal-map to pass driving hints to the vehicle control includes, max-speed, gradient, curvature and wall profile.

6. The means of claim 5, wherein the use of knowledge of the position and a nodal-path to pass steering hints to vehicle control includes:

(a) the nodal-path containing a list of the landmarks that the vehicle must pass through; and

(b) the steering hints of including turn-left, turn-right, and stop.

7. A means of navigating without localization infrastructure or external control, an autonomous vehicle along a path that is confined by walls that are within range of on-board sensors by determining the relative location and orientation of the walls with respect to the vehicle, the means comprising means of controlling the vehicle, including setting steer angle and ground speed, without localization comprising hardware and means to:

(a) use range data to establish free space in front of vehicle,

(b) use active contours to generate a desired path,

(c) use driving hints to guide said active contours, for instance along arcs and open areas, and/or to

(d) use steering hints to confine the snake active contours to a specific domain of free space, for instance at intersections, and

(e) use the desired path to generate steering demand and velocity, wherein the active contours to generate the desired path are such that;

(1) the desired path must avoid walls and preferably minimize curvature,

(2) the length and stiffness of the active contour is a function of the vehicle and the state of the vehicle;

(3) the “

energy”

of the active contours is a defined function of the proximity to the walls and the curvature of the active contours, and

(4) if the “

energy”

exceeds a predefined limit, the velocity of the vehicle is reduced and if the “

energy”

continues to exceed the limit for a predetermined time/distance, the vehicle is stopped.

8. The means of claim 7, wherein the range data is in the form of on-board sensors which emit and receive electro-magnetic/ultra-sonic radiation to determine the range and bearing of the walls.

9. The means of claim 7, wherein the driving hints to guide the active contours along the arcs and the open areas are adapted to:

(a) modify the ground speed according to local curvature and recommended speed limits, and

(b) add a “

potential gradient energy”

term to bias the position of the active contours snake.

10. The means of claim 7, wherein the steering hints to guide the active contours are such that:

(a) radial rails are generated in front of the vehicle,

(b) the rails are segmented into bands by the topology of the free space,

(c) appropriate bands are selected by steering hints, and

(d) points on the active contours are fitted to selected bands.

11. The means of claim 7, wherein the desired path to generate the steering demand, and the velocity compares a radius of curvature of the vehicle, with a radius of curvature of the path.

12. A nodal-map for use with means of localizing a vehicle without localization infrastructure, the nodal map comprising:

(a) a position of landmarks,

(b) topological relationship between the landmarks,

(c) the nature of an arc that connects the landmarks, wherein the nature of the arc that connects the landmarks is such to;

(1) account for physical limitations,

(2) improve the performance of the vehicle, and

(3) account for unusual/dangerous conditions, and

(d) a means where the nodal-map of an intended path and features is determined by driving the vehicle along the intended path, logging and processing data obtained from at least one sensor and storing the nodal-map along with identifying characteristics of the landmarks in a memory.

13. The nodal-map of claim 12, wherein the means where a nodal-map of the intended path and features is determined comprises:

(a) a means where the dead reckoning method is used to estimate the relative position of the landmarks along the intended track in either the forward or reverse direction with respect to the vehicle, and

(b) a means where the range finding data is used generate a polyline.