Collision-free dynamic window approach for moving obstacles

A method of navigation by a robot to a predetermined first static or dynamic target location within a dynamic environment, the dynamic environment having a predefined boundary, comprising:

• obtaining respective obstacle positions of a first set of obstacles within the predefined boundary, respective obstacle velocities of the first set of obstacles at the respective obstacle positions, and respective obstacle accelerations of the first set of obstacles at the respective obstacle positions;
• determining, via one or more computer processors and within a predetermined first time cycle, a predefined quantity of respective obstacle trajectories for each of the obstacles of the first set of obstacles based on the respective obstacle velocities of the first set of obstacles at the respective obstacle positions and the respective obstacle accelerations of the first set of obstacles at the respective obstacle positions;
• selecting, via the one or more computer processors, a first new robot velocity to be implemented for the robot in a subsequent time cycle from a first set of robot velocity candidates for the robot, wherein:
• when there is a reachable position for the robot outside of the first obstacle first inflated boundary at the completion of the second time cycle the first new robot velocity is one at which a first robot position of the robot at the completion of the subsequent time cycle overlaps none of the determined respective obstacle trajectories at the completion of the subsequent time cycle and
• when there is no reachable position for the robot that does not overlap at least one of the determined respective obstacle trajectories at the completion of the subsequent time cycle, the first new robot velocity is a first reduced robot velocity;
• and
• moving the robot at the first new robot velocity during the subsequent time cycle.

A robot configured for navigation to a predetermined first static or dynamic target location, comprising:

• an object detection system configured for obtaining, during a predetermined first time cycle, a first obstacle position of a first obstacle, a first obstacle velocity of the first obstacle at the first obstacle position, and a first obstacle acceleration of the first obstacle at the first obstacle position;
• a computer system in communication with the object detection system and comprising a non-transitory computer-readable storage medium on which computer readable instructions of a program are stored and one or more computer processors, wherein the instructions, when executed by the one or more processors, cause the computer system to perform the following:
• (i) determine, during the first time cycle, a first obstacle first velocity dynamic window for the first obstacle based on the first obstacle velocity and the first obstacle acceleration;
• (ii) determine, during the first time cycle, a first obstacle first mobility boundary defining a first set of subsequent obstacle positions reachable by the first obstacle during or at the completion of a predetermined second time cycle following the first time cycle from the first obstacle position based on the first obstacle first velocity dynamic window, the second time cycle being of equal duration to the first time cycle;
• and
• (iii) select, during the first time cycle, a first new robot velocity to be applied to the robot at the completion of the first time cycle from a set of first new robot velocity candidates for the robot, wherein:
• when there is a reachable position for the robot outside of the first obstacle first inflated boundary at the completion of the second time cycle the first new robot velocity is one at which a first new robot position of the robot at the completion of the second time cycle is outside of a first obstacle first inflated boundary of the first obstacle spaced from the first obstacle first mobility boundary by a predetermined offset and when there is no reachable position for the robot outside of the first obstacle first inflated boundary at the completion of the second time cycle, the first new robot velocity is a first reduced robot velocity;
• and
• a vehicle power system in communication with the computer system and configured for moving the robot at the first new robot velocity during the predetermined second time cycle and immediately following the first time cycle.