Real-time motion and path planner for robots

An apparatus comprising:

• an environment mapping circuit configured to generate occupancy information about an environment around a robot, wherein the occupancy information represents defined volumes of space of the environment, wherein each defined volume of space is associated with a corresponding probability of whether the defined volume of space is occupied, wherein the defined volumes of space comprise a linear octree of axes-aligned bounding boxes with multiple levels, wherein each bounding box is associated with a corresponding level of the multiple levels and associated with a unique key for identifying the bounding box, wherein the unique key encodes the corresponding level, a radius of the bounding box at the corresponding level, and a center coordinate of the bounding box at the corresponding level;
• a path planning circuit configured to determine a sequence of robot configurations between a starting configuration and a target configuration based on the occupancy information, wherein the sequence of robot configurations defines poses of the robot that occupy selected ones of the defined volumes of space in which the corresponding probability satisfies a predefined criterion;
• a trajectory planning circuit configured to generate an instruction for the robot based on the sequence of robot configurations, wherein the instruction comprises trajectory information to control the robot to move from the starting configuration to the target configuration through the sequence of robot configurations;
• and
• a control circuit configured to control movements of the robot according to the instruction.

A non-transitory computer readable medium that comprises instructions which, if executed, cause one or more processors to:

• generate occupancy information about an environment around a robot, wherein the occupancy information represents defined volumes of space of the environment, wherein each defined volume of space is associated with a corresponding probability of whether the defined volume of space is occupied, wherein the defined volumes of space comprise a linear octree of axes-aligned bounding boxes with multiple levels, wherein each bounding box is associated with a corresponding level of the multiple levels and associated with a unique key for identifying the bounding box, wherein the unique key encodes the corresponding level, a radius of the bounding box at the corresponding level, and a center coordinate of the bounding box at the corresponding level;
• determine a sequence of robot configurations between a starting configuration and a target configuration based on the occupancy information, wherein the sequence of robot configurations defines poses of the robot that occupy selected ones of the defined volumes of space in which the corresponding probability satisfies a predefined criterion;
• and
• generate an instruction for the robot based on the sequence of robot configurations, wherein the instruction comprises trajectory information to control the robot to move from the starting configuration to the target configuration through the sequence of robot configurations;
• and
• control movements of the robot according to the instruction.

A device comprising:

• a means for generating occupancy information about an environment around a robot, wherein the occupancy information represents defined volumes of space of the environment, wherein each defined volume of space is associated with a corresponding probability of whether the defined volume of space is occupied, wherein the defined volumes of space comprise a linear octree of axes-aligned bounding boxes with multiple levels, wherein each bounding box is associated with a corresponding level of the multiple levels and associated with a unique key for identifying the bounding box, wherein the unique key encodes the corresponding level, a radius of the bounding box at the corresponding level, and a center coordinate of the bounding box at the corresponding level;
• a means for determining a sequence of robot configurations between a starting configuration and a target configuration based on the occupancy information, wherein the sequence of robot configurations defines poses of the robot that occupy selected ones of the defined volumes of space in which the corresponding probability satisfies a predefined criterion;
• and
• a means for generating an instruction for the robot based on the sequence of robot configurations, wherein the instruction comprises trajectory information to control the robot to move from the starting configuration to the target configuration through the sequence of robot configurations;
• and
• a means for controlling movements of the robot according to the instruction.