Method for object avoidance during autonomous navigation

Abstract

A method for autonomous navigation of an autonomous vehicle includes: estimating a stopping duration, for the autonomous vehicle to reach a full stop, based on a current speed of the autonomous vehicle; calculating a critical time from the current time by the stopping duration; detecting an object in a scan image, of a field proximal the autonomous vehicle, captured by a sensor on the autonomous vehicle at the current time; based on the scan image, deriving a current location and motion of the object; calculating a future state boundary that represents a ground area accessible to the object up to the critical time based on the current location and motion of the object and a set of predefined motion limit assumptions for generic objects proximal public roads; and electing a navigational action to avoid entry into the future state boundary prior to the critical time.

I claim: 
     
         1 . A method for autonomous navigation of an autonomous vehicle comprising:
 accessing a set of predefined motion limit assumptions for generic objects proximal public roads;   for a first scan cycle:
 accessing a first scan image containing data captured by a sensor on the autonomous vehicle at a first time; 
 identifying a first group of points in the first scan image representing a first object in a field proximal the autonomous vehicle, each point in the first group of points comprising:
 a first range value from the sensor to a surface on the first object; 
 a first azimuthal position of the surface on the first object relative to the sensor; and 
 a first radial velocity of the surface of the first object relative to the sensor; 
 
 calculating a first correlation between first radial velocities and first azimuthal positions of points in the first group of points; 
 based on the first correlation, calculating a first function that relates possible tangential velocities of the first object and possible angular velocities of the first object at the first time; and 
 calculating a first radial velocity of the first object at the first time based on first radial velocities of points in the first group of points; 
   estimating a first stopping duration, for the autonomous vehicle to reach a full stop, based on a first speed of the autonomous vehicle at the first time;   calculating a first critical time offset from the first time by the stopping duration;   calculating a first future state boundary that represents a first ground area accessible to the first object at the first critical time based on:
 possible tangential velocities of the first object and possible angular velocities of the first object, at the first time, defined by the first function; 
 the first radial velocity; and 
 the set of predefined motion limit assumptions; and 
   electing a first navigational action to avoid entry into the first future state boundary prior to the first critical time.   
     
     
         2 . The method of  claim 1 :
 further comprising calculating an access zone, around the autonomous vehicle, excluding the first future state boundary of the first object; and   wherein electing the first navigational action comprises, in response to a first location of the autonomous vehicle at the first time falling within a threshold distance of a perimeter of the first future state boundary, executing the first navigational action to navigate toward the access zone.   
     
     
         3 . The method of  claim 1 , wherein electing the first navigational action comprises, in response to a first location of the autonomous vehicle at the first time falling within the first future state boundary, executing a braking action to slow the autonomous vehicle. 
     
     
         4 . The method of  claim 1 , wherein electing the first navigational action comprises, in response to a first location of the autonomous vehicle at the first time falling outside of the first future state boundary, maintaining a velocity of the autonomous vehicle. 
     
     
         5 . The method of  claim 1 , further comprising:
 for a second scan cycle succeeding the first scan cycle:
 accessing a second scan image containing data captured by the sensor at a second time; 
 identifying a second group of points in the second scan image representing the first object in the field; 
 calculating a second correlation between second radial velocities and second azimuthal positions of points in the second group of points; 
 based on the second correlation, calculating a second function that relates possible tangential velocities of the first object and possible angular velocities of the first object at the second time; and 
 calculating a second radial velocity of the first object at the second time based on second radial velocities of points in the second group of points; 
   estimating a second tangential velocity of the first object and a second angular velocity of the first object at the second time based on an intersection of the first function and the second function;   estimating a second stopping duration, for the autonomous vehicle to reach a full stop, based on a second speed of the autonomous vehicle at the second time;   calculating a second critical time offset from the second time by the stopping duration;   calculating a second future state boundary that represents a second ground area accessible to the first object at the second critical time based on:
 second tangential velocity of the first object; 
 the second angular velocity of the first object; 
 the first radial velocity; and 
 the set of predefined motion limit assumptions; and 
   electing a second navigational action to avoid entry into the second future state boundary prior to the first critical time.   
     
     
         6 . The method of  claim 5 :
 wherein calculating the first future state boundary comprises calculating the first future state boundary:
 within a plane approximately parallel to a road surface; and 
 characterized by a first area dimension; and 
   wherein calculating the second future state boundary comprises calculating the second future state boundary:
 within the plane; and 
 characterized by a second area dimension less than the first area dimension. 
   
     
     
         7 . The method of  claim 1 , wherein calculating the first correlation comprises:
 calculating a first linear trend line through first radial velocities versus first azimuthal positions of points in the first group of points; and   calculating the first correlation based on a first slope of the first linear trend line, the slope representing a relationship between a first tangential velocity of the first object and a first angular velocity of the first object at the first time.   
     
     
         8 . The method of  claim 7 :
 further comprising characterizing a first error of the first linear trend line based on deviation of first radial velocities of points in the first group of points from the first linear trend line;   wherein calculating the first function comprises:
 calculating a first line that relates possible tangential velocities of the first object and possible angular velocities of the first object at the first time based on the first correlation; and 
 calculating a first width of the first line based on the first error; and 
   wherein calculating the first future state boundary comprises calculating the first future state boundary based on possible tangential velocities of the first object and possible angular velocities of the first object, at the first time, represented by the first line of the first width.   
     
     
         9 . The method of  claim 1 , wherein accessing the first scan image comprises accessing the first scan image containing data captured by the sensor comprising a four-dimensional light detection and ranging sensor:
 mounted on the autonomous vehicle; and   configured to generate scan images representing positions and speeds of surfaces within the field relative to the sensor.   
     
     
         10 . A method for autonomous navigation of an autonomous vehicle comprising:
 at a first time at the autonomous vehicle, estimating a stopping duration, for the autonomous vehicle to reach a full stop, based on a speed of the autonomous vehicle at the first time;   calculating a critical time offset from the first time by the stopping duration;   detecting an object in a first scan image, of a field proximal the autonomous vehicle, captured by a sensor on the autonomous vehicle at approximately the first time;   based on the first scan image, deriving a first location and a first motion of the first object;   calculating a first future state boundary that represents a first ground area accessible to the first object from the first time to the first critical time based on:
 the first location of the first object at the first time; 
 the first motion of the first object; and 
 a set of predefined motion limit assumptions for generic objects proximal public roads; and 
   electing a first navigational action to avoid entry into the first future state boundary prior to the first critical time.   
     
     
         11 . The method of  claim 10 :
 further comprising accessing the set of predefined motion limit assumptions comprising:
 a maximum linear acceleration of the generic ground-based vehicle; 
 a maximum linear velocity of a generic ground-based vehicle; and 
 a maximum angular velocity of the generic ground-based vehicle; and 
   wherein calculating the first future state boundary comprises:
 integrating the first motion of the first object, moving at up to the maximum angular velocity and accelerating up to the maximum linear velocity according to the maximum linear acceleration, from the first location of the first object over the stopping duration to calculate the first ground area accessible to the first object from the first time to the first critical time; and 
 storing the first ground area as the first future state boundary. 
   
     
     
         12 . The method of  claim 11 :
 further comprising:
 detecting a second object in the first scan image; 
 based on the first scan image, deriving a second location and a second motion of the second object; 
 integrating the second motion of the second object, moving at up to the maximum angular velocity and accelerating up to the maximum linear velocity according to the maximum linear acceleration, from the second location of the second object over the stopping duration to calculate a second ground area accessible to the second object from the first time to the first critical time; and 
 storing the second ground area as a second future state boundary; and 
   wherein electing the first navigational action comprises electing the first navigational action to avoid entry into the first future state boundary and the second future state boundary prior to the first critical time.   
     
     
         13 . The method of  claim 12 :
 further comprising calculating an access zone, around the autonomous vehicle, excluding the first future state boundary of the first object and the second future state boundary of the second object; and   wherein electing the first navigational action comprises executing the first navigational action to navigate toward the access zone.   
     
     
         14 . The method of  claim 10 :
 further comprising calculating an access zone, around the autonomous vehicle, excluding the first future state boundary of the first object; and   wherein electing the first navigational action comprises, in response to a first location of the autonomous vehicle at the first time falling within a threshold distance of a perimeter of the first future state boundary, executing the first navigational action to navigate toward the access zone.   
     
     
         15 . The method of  claim 10 :
 wherein detecting the object in the first scan image comprises identifying a first group of points in the first scan image representing a first object in a field proximal the autonomous vehicle, each point in the first group of points comprising:
 a first range value from the sensor to a surface on the first object; 
 a first azimuthal position of the surface on the first object relative to the autonomous vehicle; and 
 a first radial velocity of the surface of the first object relative to the autonomous vehicle; 
   wherein deriving the first location and the first motion of the first object comprises:
 calculating a first correlation between first radial velocities and first azimuthal positions of points in the first group of points; 
 based on the first correlation, calculating a first function that relates possible tangential velocities of the first object and possible angular velocities of the first object at the first time; 
 calculating a first radial velocity of the first object at the first time based on first radial velocities of points in the first group of points; and 
 deriving the first location of the first object based on first range values and first azimuthal positions of points in the first group of points; and 
   wherein calculating the first future state boundary comprises calculating the first future state boundary based on:
 possible tangential velocities of the first object and possible angular velocities of the first object, at the first time, defined by the first function; 
 the first radial velocity; 
 the first location, and 
 the set of predefined motion limit assumptions. 
   
     
     
         16 . The method of  claim 15 , further comprising:
 for a second scan cycle succeeding the first scan cycle:
 accessing a second scan image containing data captured by the sensor at a second time; 
 identifying a second group of points in the second scan image representing the first object in the field; 
 calculating a second correlation between second radial velocities and second azimuthal positions of points in the second group of points; 
 based on the second correlation, calculating a second function that relates possible tangential velocities of the first object and possible angular velocities of the first object at the second time; and 
 calculating a second radial velocity of the first object at the second time based on second radial velocities of points in the second group of points; 
   estimating a second tangential velocity of the first object and a second angular velocity of the first object at the second time based on an intersection of the first function and the second function;   estimating a second stopping duration, for the autonomous vehicle to reach a full stop, based on a second speed of the autonomous vehicle at the second time;   calculating a second critical time offset from the second time by the stopping duration;   calculating a second future state boundary that represents a second ground area accessible to the first object at the second critical time based on:
 the second tangential velocity of the first object; 
 the second angular velocity of the first object; 
 the second radial velocity; and 
 the set of predefined motion limit assumptions; and 
   electing a second navigational action to avoid entry into the second future state boundary prior to the first critical time.   
     
     
         17 . The method of  claim 16 , wherein calculating the second future state boundary comprises calculating the second future state boundary that represents the second ground area less than the first ground area. 
     
     
         18 . The method of  claim 10 :
 further comprising:
 detecting a second object in the first scan image; 
 based on the first scan image, deriving a second location and a second motion of the second object; 
 calculating a second future state boundary that represents a second ground area accessible to the second object from the first time to the first critical time based on:
 the second location of the second object at the first time; 
 the second motion of the second object; and 
 the set of predefined motion limit assumptions for generic objects proximal public roads; and 
 
 in response to a second distance from the autonomous vehicle to a second perimeter of the second future state boundary at the first time exceeding a threshold distance, muting the second object from a next path planning consideration at the autonomous vehicle; and 
   wherein electing the first navigational action comprises, in response to a first distance from the autonomous vehicle to a first perimeter of the first future state boundary at the first time falling within the threshold distance, activating the first object in the next path planning consideration at the autonomous vehicle.   
     
     
         19 . The method of  claim 10 , wherein estimating the stopping duration comprises:
 accessing a second image of the field captured by a second sensor, arranged on the autonomous vehicle, at approximately the first time;   interpreting a type of a road surface occupied by the autonomous vehicle at the first time based on a set of features extracted from the second image;   predicting a quality of the road surface based on the set of features;   estimating a friction coefficient for tires of the autonomous vehicle acting on the road surface based on the type of the road surface and the quality of the road surface; and   estimating the stopping duration based on:
 a vehicle speed of the autonomous vehicle at the first time; 
 the friction coefficient; and 
 a braking model for the autonomous vehicle. 
   
     
     
         20 . A method for autonomous navigation of an autonomous vehicle comprising:
 accessing a set of predefined motion limit assumptions for generic objects proximal public roads;   accessing a scan image containing data captured by a sensor on the autonomous vehicle at a first time;   identifying a group of points in the scan image representing an object in a field proximal the autonomous vehicle, each point in the group of points comprising:
 a position of a surface on the object relative to the autonomous vehicle; 
 a radial velocity of the surface of the object relative to the autonomous vehicle; 
   calculating a correlation between radial velocities and positions of points in the group of points;   based on the correlation, calculating a function that relates possible tangential velocities of the object and possible angular velocities of the object at the first time;   calculating a radial velocity of the object at the first time based on radial velocities of points in the group of points;   calculating a future state boundary that represents a ground area accessible to the object at a future time based on:
 possible tangential velocities of the object and possible angular velocities of the object, at the first time, defined by the function; 
 the radial velocity of the object; and 
 the set of predefined motion limit assumptions; and 
   electing a navigational action to avoid the future state boundary prior to the future critical time.