Energy-Based Approach for Obstacle Avoidance

This invention relates generally to a method for avoiding obstacles and, more particularly, to a method for determining avoidance paths around obstacles using energy-based techniques.

Mobile machines, for example earthworking machines at a mine or construction site, are being developed to be capable of autonomous operation. As an example, a frequent use of autonomous mobile machines involves fleets of autonomous mining trucks for hauling material at a mining site.

One of the principle challenges in the development of autonomous mobile machines is obstacle detection and avoidance. Obstacle avoidance, in particular, offers unique problems in its development. Early versions of obstacle avoidance systems generally consisted of stopping the movement of a mobile machine when an obstacle was detected, only resuming motion when the obstacle was cleared. More advanced versions of obstacle avoidance provided methods for an autonomous mobile machine to determine alternate routes around detected obstacles.

However, as autonomous fleets of mobile machines become more widely used and complex, the task of planning alternate routes to avoid multiple, and often moving, obstacles requires the development of unique and inventive methods to be successful.

The present invention is directed to overcoming one or more of the problems as set forth above.

In one aspect of the present invention a method for determining an alternate path by a mobile machine to avoid at least one obstacle is disclosed. The method includes the steps of assigning an initial value of charge to the mobile machine, assigning a value of charge to a desired destination, determining the presence and the locations of at least one obstacle, and assigning a value of charge to each determined obstacle. The method further includes the steps of determining a force vector equation for each of the desired destination and each obstacle with respect to the mobile machine, determining a resultant force vector as a function of the force vector equations, and controlling the steering and movement of the mobile machine in response to the resultant force vector.

FIG. 1 is a flow diagram illustrating a preferred method of the present invention;

FIG. 2 is a diagrammatic illustration of force vector relationships of a mobile machine, a desired destination, and a plurality of obstacles; and

FIG. 3 is a diagrammatic illustration of a control system as embodied in a preferred aspect of the present invention.

Referring to FIGS. 1, 2, and 3, a method for determining an alternate path by a mobile machine 202 to avoid at least one obstacle is shown. An exemplary mobile machine 202 for use with the present invention is an off-road mining truck for hauling material at a mining site. However, many types of mobile machines, e.g., loaders, scrapers, graders, on-highway trucks, and the like, may benefit from use of the invention.

The present invention is particularly well suited for use in an autonomous mobile machine 202. However, the invention may be equally used in a manual mobile machine situation, perhaps providing a visual output to an operator of a preferred path to traverse to avoid obstacles.

The obstacle avoidance system of the present invention is modeled on a theory of charged particles, and the forces they exert on each other. For example, the theory of charged particles includes two opposite charges, which attract each other in force. Two like charges, on the other hand, oppose each other in force. The charges of attraction and repulsion may be expressed in vector force equations. When multiple charges are present and affected by each other, a resultant force vector of the sum of all charges is easily determined.

As illustrated in FIG. 2, this charge model is easily extended to a mobile machine 202 attempting to reach a desired destination 204. The mobile machine 202 is given a charge (+) and the desired destination 204 is given an opposite charge (-). The resultant force of attraction causes the mobile machine 202 to move toward the desired destination 204. In addition, a plurality of obstacles; for example, a first determined obstacle 206, a second determined obstacle 208, and a third determined obstacle 210, are each given a charge of the same polarity (+) as the charge given to the mobile machine 202. The like charges of the obstacles 206,208,210 create forces of repulsion between the obstacles 206,208,210 and the mobile machine 202.

It is to be understood that the assignment of (+) and (-) charges is purely arbitrary. The designation of polarities is used to help clarify that some charges have forces of attraction and other charges have forces of repulsion.

In FIG. 2, the mobile machine 202 is depicted as an off-road mining truck, the first determined obstacle 206 is depicted as another off-road mining truck, the second determined obstacle 208 is shown as a rock, and the third determined obstacle 210 is shown as a foreman's truck.

Referring to FIG. 1, a flow diagram of a preferred embodiment of the present invention is shown.

In a first control block 102, an initial value of charge is assigned to the mobile machine 202. In a second control block 104, a value of charge is assigned to the desired destination 204, which is of opposite polarity to the initial charge of the mobile machine 202. The two opposite charges therefore create a force of attraction between the mobile machine 202 and the desired destination 204. Hence, the mobile machine 202 attempts to move to the desired destination 204, preferably by a straight line path if no obstacles are detected.

In a third control block 106, the mobile machine 202 determines the presence and locations of any obstacles 206,208,210 which may prevent the mobile machine 202 from moving to the desired destination 204 by the originally intended path. The determination of the presence and the locations of obstacles is well known in the art and will not be discussed further.

Control proceeds to a fourth control block 108, where a value of charge is assigned to each of the obstacles 206,208,210. Each obstacle charge is of the same polarity as the charge of the mobile machine 202. Therefore, each obstacle 206,208,210 has a force of repulsion against the mobile machine 202.

In the preferred embodiment, the charge on each obstacle 206,208,210 may be given a magnitude value that is a function of certain desired parameters, thus resulting in various levels of force between each obstacle 206,208,210 and the mobile machine 202. For example, the second determined obstacle 208, i.e., the rock, may be assigned with a charge of less magnitude than the charge assigned to the first determined obstacle 206, i.e., the off-road mining truck. This is due to the rock being stationary and predictable, while the off-road mining truck may be moving, thus requiring a larger avoidance distance by the mobile machine 202. Additionally, the first determined obstacle 206 may be assigned a charge of greater magnitude than the third determined obstacle 210, i.e., the foreman's truck, due to the significant difference in the mass of the two machines. Other criteria that may be used to assign a magnitude of charge may be the heading and velocity of a moving obstacle, the level of predictability of the movement of the obstacle, the distance of the obstacle from the mobile machine 202, and the like.

In a fifth control block 110, a force vector equation for each obstacle 206,208,210 with respect to the mobile machine 202, and for the desired destination 204 with respect to the mobile machine 202 is determined. Preferably, each force vector equation is determined as: ##EQU1## where: F.sub.i is the force vector between the mobile machine 202 and one of an obstacle 206,208,210 and the desired destination 204;

K.sub.i is a constant;

m.sub.i is the magnitude of charge of an obstacle 206,208,210 or the desired destination 204;

m.sub.mobilemachine is the magnitude of charge of the mobile machine 202; and

r.sub.i is the vector distance from the mobile machine 202 to the obstacle 206,208,210 or the desired destination 204.

In the preferred embodiment, the force vector F.sub.i may be correlated with coordinates in the x and y direction and with a steering angle .THETA., where the x and y coordinates are two dimensional Cartesian coordinates. However, the force vector F.sub.i may correlate to other coordinate systems as well; e.g., site reference systems, polar coordinates, and the like.

Therefore, as is shown in FIG. 2, from the mobile machine 202 to the desired destination 204 is a respective force vector and distance vector F.sub.D,r.sub.D ; from the mobile machine 202 to the first determined obstacle 206 is a respective force vector and distance vector F.sub.1,r.sub.1 ; from the mobile machine 202 to the second determined obstacle 208 is a respective force vector and distance vector F.sub.2,r.sub.2 ; and from the mobile machine 202 to the third determined obstacle 210 is a respective force vector and distance vector F.sub.3,r.sub.3.

With continued reference to FIG. 3, control proceeds to a sixth control block 112, where a resultant force vector is determined as a function of the force vector equations. In the preferred embodiment, the resultant force vector is determined by: ##EQU2##

In a seventh control block 114, the steering and movement of the mobile machine 202 is controlled as a function of the resultant force vector. The determination of the resultant force vector is a continual process. That is, the fifth, sixth, and seventh control blocks 110,112,114 are repeated continually during movement of the mobile machine 202. In this manner, the resultant force vector continually changes as the conditions between the mobile machine 202, the obstacles 206,208,210, and the desired destination 204 change. From this continual change of the resultant force vector, the path from the mobile machine 202 to the desired destination 204 continually changes to avoid the obstacles 206,208,210 that have been detected.

As an example of an application of the present invention, reference is made to FIG. 3, where a diagrammatic illustration of a preferred embodiment of a control diagram for the present invention is shown.

A command for the mobile machine 202 to traverse a desired path is input to a first summer 302. The first summer 302 also accepts feedback information on the position, velocity, and orientation of the mobile machine 202, thus providing a standard, well known feedback control system. The combined signal is delivered to control gains 304 for further signal processing. A second summer 306 accepts the command signal from the control gains 304, and also accepts the resultant force vector equation from an obstacle avoidance system 314. The obstacle avoidance system 314 receives information about the presence and locations of obstacles from an obstacle detection system 312. The obstacle avoidance system 314 assigns charge magnitudes to the mobile machine 202, the desired destination 204, and each of the obstacles 206,208,210. The obstacle avoidance system 314 then determines force vector equations, determines the resultant force vector, and scales the value of the resultant force vector to be compatible with the signal from the control gains 304.

The signal from the second summer 306, which compensates the original desired path signal to establish a modified path to avoid obstacles, is delivered to an actuator 308 for actuating machine control 310, thus controlling the steering and movement of the mobile machine 202.

Other aspects, objects, and features of the present invention can be obtained from a study of the drawings, the disclosure, and the appended claims.