Method and apparatus for controlling high speed vehicles

• US 5,220,497 A
• Filed: 10/29/1990
• Issued: 06/15/1993
• Est. Priority Date: 11/20/1987
• Status: Expired due to Fees

• Current Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Original Assignee: North American Philips Corp. (Koninklijke Philips N.V.)
• Inventors: Mehta, Sandeep, Trovato, Karen I.
• Primary Examiner(s): RUGGIERO, JOSEPH F
• Application Number:
  US07/605,057
• Time in Patent Office: 960 Days
• Field of Search: 364/148, 364/424.02, 364/461, 364/436, 364/437, 364/438, 364/444, 364/167.01, 364/474.2, 395/80, 395/85, 395/88, 395/90, 395/919, 395/89, 395/905
• US Class Current: 700/56
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: B63B 49/00 Arrangements of nautical instruments or navigational aids nautical measuring instruments G01C; radio navigation, analogous arrangements using other waves G01S
• CPC Class Codes: B63G 8/14 Control of attitude or depth of torpedoes F42B19/00
• CPC Class Codes: B63H 25/04 automatic, e.g. reacting to compass
• CPC Class Codes: G05B 19/4061 Avoiding collision or forbidden zones
• CPC Class Codes: G05B 2219/35415 3-D three dimension, space input, spaceball
• CPC Class Codes: G05B 2219/40443 Conditional and iterative planning
• CPC Class Codes: G05B 2219/40448 Preprocess nodes with arm configurations, c-space and planning by connecting nodes
• CPC Class Codes: G05B 2219/40465 Criteria is lowest cost function, minimum work path
• CPC Class Codes: G05B 2219/40471 Using gradient method
• CPC Class Codes: G05B 2219/40476 Collision, planning for collision free path
• CPC Class Codes: G05B 2219/45131 Turret punch press
• CPC Class Codes: G05B 2219/49143 Obstacle, collision avoiding control, move so that no collision occurs
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G06F 30/15 Vehicle, aircraft or watercraft design
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• CPC Class Codes: G08G 1/161 Decentralised systems, e.g. inter-vehicle communication
• CPC Class Codes: G08G 9/00 Traffic control systems for craft where the kind of craft is irrelevant or unspecified

Abstract

Maneuvers of a controlled vehicle, such as a car, traveling at moderate to high speeds are planned by propagating cost waves in a configuration space using two search strategies referred to as budding and differential budding. Control is achieved by monitoring properties of the controlled vehicle and adjusting control parameters to achieve motion relative to a frame of reference. The frame of reference may change before the transformation to configuration space occurs. The method transforms goals, obstacles, and the position of the controlled vehicle in task space to a configuration space based on the position of these objects relative to a moving frame of reference. The method also determines a local neighborhood of possible motions based on the control capabilities of the vehicle. In one embodiment, the controlled parameters are time derivatives of the monitored properties. A variation of the method provides for the parallel computation of the configuration space. In one embodiment of the parallel computation, the case where two processes are used, a first process and configuration space would be used to plan. A second process and configuration space would be used to read the setpoints which are sent as control directives to the vehicle.

Claims

1. A method for controlling the motion of a vehicle in a physical task space comprising the steps of:

generating a data set which represents a configuration space having a frame of reference which is moving relative to the physical space;

propagating cost waves in the configuration space data set to create direction arrows;

using the direction arrows to find a least cost path from a starting point to a goal point in the physical task space; and

controlling one or more parameters affecting the motion of the vehicle after finding the least cost path in a manner that the vehicle follows the path.

2. The method of claim 1 wherein the step of generating the data set comprises monitoring one or more properties of the vehicle.

3. The method of claim 2 wherein the controlled parameters are the time derivatives of the monitored properties.

4. The method of claim 3 wherein the monitored properties are velocity components of the vehicle and wherein the controlled parameters are the acceleration components of the vehicle.

5. The method of claim 1 further comprising the steps of repetitively:

updating the data set to reflect changes in the task space and or properties of the vehicle;

repropagating cost waves in the configuration space data set to update the direction arrows; and

modifying the path on the basis of the updated direction arrows.

6. The method of claim 5 wherein the step of propagating the cost waves comprises budding waves in the configuration space and wherein the step of repropagating the cost waves comprises differentially budding waves in the propagation space.

7. The method of claim 6 wherein the step of repropagating cost waves comprises:

determining if a metric has changed in the configuration space;

budding waves in the configuration space if the metric has changed; and

differentially budding waves in the configuration space if the metric has not changed.

10. The method of any of claims 2, 5, or 8 wherein the least cost path is a path which minimizes fuel use.

11. The method of any of claims 2, 5, or 8 wherein the least cost path is a path which minimizes distance travelled.

12. The method of claim 1 wherein the frame of reference moves with the same velocity as the controlled vehicle.

13. The method of claim 1 wherein the path is determined to avoid collisions with obstacles which are moving relative to the task space and the frame of reference moves with the same velocity as one of the obstacles.

14. The method of claim 1 wherein the vehicle is an automobile or the like moving at higher speed and the task space includes a highway.

15. The method of claim 1 wherein the vehicle is a submarine tracking another ship, while avoiding the ocean bottom and other obstacles.

16. The method of claim 1 wherein the choice of frame of reference changes due to changes in sensory information.

17. The method of claim 12 wherein the controlled vehicle is one of a plurality of vehicles moving in formation.

8. A method for controlling the motion of a vehicle in a physical task space comprising the steps of:

1) generating a first data set which represents a first configuration space having a frame of reference which is moving relative to the physical space;

2) propagating cost waves in the configuration space data set to create first direction arrows;

3) using the first direction arrows to find a least cost first path from starting point to a goal point in the physical task space; and

4) controlling one or more parameters affecting the motion of the vehicle after finding the first least cost path in a manner that the vehicle follows the first path

5) while controlling the parameters in accordance with step

     4);

generating a second data set which represents a second configuration space having a frame of reference which is moving relative to the physical space;

propagating cost waves in the second configuration space data set to create second direction arrows;

using the second direction arrows to find a least cost second path from a starting point to a goal point in the physical task space; and

then

6) controlling one or more parameters affecting the motion of the vehicle so that the vehicle follows the second path; and

then

7) alternatingly repropagating cost waves and finding paths in the first and second data sets while controlling the parameters on the basis of the last most recently determined path.

9. The method of claim 8 wherein the step of generating the second data set includes copying the first data set into the second data set.

18. A system for controlling the motion of a vehicle in a physical task space comprising:

means for generating a data set which represents a configuration space having a frame of reference which is moving relative to the physical space;

means for propagating cost waves in the configuration space data set to create direction arrows;

means for using the direction arrows to find a least cost path from a starting point to a goal point in the physical task space; and

means for controlling one or more parameters affecting the motion of the vehicle in response to the means for using the direction arrows in a manner that the vehicle follows the path.