Obstacle-avoiding navigation system
First Claim
1. A method of operating a vehicle to avoid an obstacle in a field of operation, the method comprising the steps of:
- installing in a first memory first data defining a first array of first grid cells, each for holding data corresponding to a respective value, said first grid cells in said first array corresponding to respective predetermined subfields in the field of operation;
scanning one of said subfields in the field of operation for determining the presence of an obstacle therein;
incrementing said value in a first grid cell in said first array corresponding to said scanned one of said subfields in response to a signal responsive to said step of scanning indicating a likelihood that an obstacle is present in said scanned one of said subfields;
defining a region of operation in the vicinity of the vehicle; and
computing a plurality of vectorial values, each vectorial value being responsive to the location of each first grid cell in said first array within said defined region of operation, with respect to the location of the vehicle, and said values in said first grid cells.
1 Assignment
0 Petitions
Accused Products
Abstract
A system for guiding an autonomous or semi-autonomous vehicle through a field of operation having obstacles thereon to be avoided employs a memory for containing data which defines an array of grid cells which correspond to respective subfields in the field of operation of the vehicle. Each grid cell in the memory contains a value which is indicative of the likelihood, or probability, that an obstacle is present in the respectively associated subfield. The values in the grid cells are incremented individually in response to each scan of the subfields, and precomputation and use of a look-up table avoids complex trigonometric functions. A further array of grid cells is fixed with respect to the vehicle form a conceptual active window which overlies the incremented grid cells. Thus, when the cells in the active window overly grid cell having values which are indicative of the presence of obstacles, the value therein is used as a multiplier of the precomputed vectorial values. The resulting plurality of vectorial values are summed vectorially in one embodiment of the invention to produce a virtual composite repulsive vector which is then summed vectorially with a target-directed vector for producing a resultant vector for guiding the vehicle. In an alternative embodiment, a plurality of vectors surrounding the vehicle are computed, each having a value corresponding to obstacle density. In such an embodiment, target location information is used to select between alternative directions of travel having low associated obstacle densities.
222 Citations
32 Claims
-
1. A method of operating a vehicle to avoid an obstacle in a field of operation, the method comprising the steps of:
-
installing in a first memory first data defining a first array of first grid cells, each for holding data corresponding to a respective value, said first grid cells in said first array corresponding to respective predetermined subfields in the field of operation; scanning one of said subfields in the field of operation for determining the presence of an obstacle therein; incrementing said value in a first grid cell in said first array corresponding to said scanned one of said subfields in response to a signal responsive to said step of scanning indicating a likelihood that an obstacle is present in said scanned one of said subfields; defining a region of operation in the vicinity of the vehicle; and computing a plurality of vectorial values, each vectorial value being responsive to the location of each first grid cell in said first array within said defined region of operation, with respect to the location of the vehicle, and said values in said first grid cells. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. A method of operating a vehicle to avoid an obstacle in a field of operation, the method comprising the steps of:
-
installing in a first memory first data for defining an array of first grid cells, each for holding data corresponding to a respective value, said first grid cells in said first array corresponding to respective predetermined subfields in the field of operation; installing in a second memory data corresponding to a desired direction of travel of the vehicle; scanning said subfields sequentially for determining the presence of an obstacle therein; incrementing said values in said first grid cells in response to said step scanning of said subfields, said values being responsive to the likelihood of an obstacle being present in said subfields; defining an active region of operation in the vicinity of the vehicle; computing a plurality of vectorial values, each vectorial value having a direction component responsive to the location of each first grid cell in said array within said defined region of operation, with respect to the location of the vehicle in said active region of operation, and a magnitude component responsive to said likelihood of an obstacle being encountered in said direction within said region of operation; and steering the vehicle in a direction responsive to said data in said second memory and said vectorial values. - View Dependent Claims (19, 20)
-
-
21. A method of guiding a vehicle on a field of operation having obstacles to be avoided thereon, the method comprising the steps of:
-
dividing the field of operation into a plurality of subfields; assigning a predetermined certainty value associated with each of said subfields; scanning selected ones of said subfields for establishing the possible presence of an obstacle thereon; incrementing said certainty value associated each of said subfields for which it is established in said step of scanning that an obstacle possibly is present thereon; and computing a vector value responsive to the location of at least one of said subfields with respect to the location of the vehicle, and said certainty value associated therewith. - View Dependent Claims (22, 23, 24, 25, 26, 27)
-
-
28. A vehicle for traveling in a region of operation having obstacles to be avoided, the vehicle comprising:
-
first memory means for containing first data defining a first array of first grid cells, each for holding data corresponding to a respective value, said first grid cells in said first array corresponding to respective predetermined subfields in the region of operation; scanning means for scanning one of said subfields in the field of operation for determining the presence of an obstacle therein; processor means for incrementing a value in said first memory means associated with said scanned one of said subfields in response to a signal responsive to said scanning means indicating a likelihood that an obstacle is present in said scanned one of said subfields; and input means coupled to said processor means, said input means being responsive to an operator of the vehicle for producing data responsive to a desired direction of travel selected by the operator, subject to the presence of an obstacle in said desired direction of travel. - View Dependent Claims (29, 30, 31, 32)
-
Specification