Reactive collision avoidance for autonomous vehicles considering physical constraints

1 . A method of navigation by a first robot to a predetermined first location, comprising:

detecting a first set of velocity obstacles within a preset distance from the first robot by a first obstacle detection sensor of the first robot;

generating, via a first computer processor of the first robot and based on the first set of velocity obstacles detected, a first set of velocity candidates for the first robot based on detection of a first set of one or more velocity obstacles;

determining, via the first computer processor of the first robot, whether each of the first set of velocity candidates is a safe velocity for the first robot or an unsafe velocity for the first robot;

selecting, via the first computer processor, a first new velocity from the first set of velocity candidates; and

moving the first robot at a first velocity corresponding to the first new velocity,

wherein the first new velocity is a velocity candidate of the first set of velocity candidates corresponding to a first desired velocity when the first new velocity corresponds to a determined safe velocity for the first robot, and

determining one or more of the first set of velocity candidates are unsafe velocities for the first robot and, based on determining that each one of the first set of velocity candidates are unsafe velocities for the first robot, selecting the first new velocity as a minimum velocity associated with the first robot.

2 . The method according to claim 1 , wherein the first set of velocity candidates for the first robot is generated only when the first set of velocity obstacles detected includes more than one velocity obstacle.

3 . The method according to claim 1 , further comprising generating, via the first computer processor, a first set of reachable velocities for the first robot when each one of the first set of velocity candidates corresponds to a respective safe but unreachable velocity for the first robot, wherein the first new velocity is a velocity corresponding to a velocity candidate of the first set of velocity candidates, the corresponding velocity candidate being determined, via the first computer processor using a preset algorithm, to correspond to a velocity closest to the first desired velocity.

4 . The method according to claim 1 , further comprising:

detecting a location of the first set of velocity obstacles; and

determining, via the first computer processor, collision cones based on the location of the first set of velocity obstacles to ascertain the first set of velocity candidates.

5 . The method according to claim 1 , wherein the determination of whether each one of the first set of velocity candidates is safe and reachable by the first robot includes calculating, via the computer processor of the first robot, safety and reachability indices using preset algorithms.

6 . The method according to claim 1 , wherein the minimum velocity possible by the first robot is greater than zero.

7 . The method according to claim 1 , wherein at least one velocity obstacle of the first set of velocity obstacles of the velocity obstacles is a second robot identical or substantially identical to the first robot.

8 . The method according to claim 1 , wherein the first robot is an autonomous vehicle.

9 . The method according to claim 8 , wherein the autonomous vehicle is intended for travel on either one or both of roadways and other terrain.

10 . The method according to claim 8 , wherein the autonomous vehicle is intended for either one or both of air travel and sea travel.

11 . The method according to claim 1 , wherein the first robot is a first non-holonomic agent, and wherein the generating of the first set of velocity candidates comprises:

determining candidate sets of kinematic values each comprising a respective candidate translational velocity value, a respective candidate rotational velocity value, and a respective candidate angular value providing a possible directional heading for the first robot, each of the sets of kinematic values being based on a kinematics model for the non-holonomic agent; and

reducing the candidate sets of kinematic values to only such candidate sets of kinematic values reachable for the first robot if the first robot were a holonomic agent.

12 . A robot collision avoidance system, the collision avoidance system comprising:

a first robot; and

a second robot configured to navigate to a predetermined second location, the second robot being a velocity obstacle from a first set of velocity obstacles and wherein the second robot is further configured, using a second computer processor, to:

generate a second set of velocity candidates for the second robot based on the detection of a second set of one or more velocity obstacles, the second set of velocity obstacles including the first robot and being within a preset distance from the second robot;

select a second new velocity from the second set of velocity candidates; and

move the second robot at a velocity corresponding to the second new velocity,

wherein the second new velocity is a second desired velocity when at least one velocity candidate of the second set of velocity candidates corresponds to a safe velocity for the second robot, and

wherein the second new velocity is a minimum velocity associated with the second robot when each one of the second set of velocity candidates corresponds to a respective unsafe velocity for the second robot.

13 . The robot collision avoidance system according to claim 12 , wherein the first robot is a first non-holonomic agent, and the first robot is configured to generate a first set of velocity candidates using a first processor that is configured to:

determine candidate sets of kinematic values each comprising a respective candidate translational velocity value, a respective candidate rotational velocity value, and a respective candidate angular value providing a directional heading for the first robot, each of the sets of kinematic values being based on a kinematics model for the non-holonomic agent; and

reduce the candidate sets of kinematic values to only such candidate sets of kinematic values reachable for the first robot if the first robot were a holonomic agent.

14 . A method of navigation by a first robot to a predetermined first location, comprising:

detecting a first set of velocity obstacles from the first robot by a first obstacle detection sensor of the first robot, wherein the first set of velocity obstacles includes a plurality of velocity obstacles;

generating, via a first computer processor of the first robot and based on the first set of velocity obstacles detected, a first set of velocity candidates for the first robot based on detection of a first set of one or more velocity obstacles;

determining, via the first computer processor of the first robot, whether each of the first set of velocity candidates is a safe velocity for the first robot or an unsafe velocity for the first robot;

selecting, via the first computer processor, a first new velocity from the first set of velocity candidates; and

moving the first robot at a first velocity corresponding to the first new velocity, wherein the first new velocity is a velocity candidate of the first set of velocity candidates corresponding to a first desired velocity when the first new velocity corresponds to a determined safe velocity for the first robot, and

determining each of the first set of velocity candidates are unsafe velocities for the first robot and, based on determining that each one of the first set of velocity candidates are unsafe velocities for the first robot, associating the first new velocity with a minimum velocity associated with the first robot.

15 . The method according to claim 14 , wherein the first set of velocity candidates for the first robot is generated only when at least one velocity obstacle of the first set of velocity obstacles is detected to be within a preset distance from the first robot.

16 . The method according to claim 14 , wherein the determination of whether each one of the first set of velocity candidates is safe and reachable by the first robot includes calculating, via the computer processor of the first robot, safety and reachability indices using preset algorithms.

17 . The method according to claim 14 , wherein the first robot is an autonomous vehicle for land travel, an autonomous vehicle for air travel, or an autonomous vehicle for sea travel.

18 . The method according to claim 14 , wherein the first robot is a first non-holonomic agent, and wherein the generating of the first set of velocity candidates comprises:

determining candidate sets of kinematic values each comprising a respective candidate translational velocity value, a respective candidate rotational velocity value, and a respective candidate angular value providing a possible directional heading for the first robot, each of the sets of kinematic values being based on a kinematics model for the non-holonomic agent; and

reducing the candidate sets of kinematic values to only such candidate sets of kinematic values reachable for the first robot if the first robot were a holonomic agent.

19 . The method according to claim 14 , wherein at least one velocity obstacle of the first set of velocity obstacles of the velocity obstacles is a second robot.

20 . The method according to claim 19 , wherein the second robot and first robot comprise autonomous vehicles.