TECHNICAL FIELD

The present disclosure generally relates to robot motion planning, and in particular to systems and methods that facilitate motion planning of a robot storing a discretized representation of the environment on one or more processors.

BACKGROUND

Description of the Related Art

Motion planning is a fundamental problem in robot control and robotics. A motion plan completely specifies a path a robot can follow from a starting state to a goal state, typically without colliding with any obstacles in an operational environment or with a reduced possibility of colliding with any obstacles in the operational environment. Challenges to motion planning involve the ability to perform motion planning at a relatively low cost and very fast speeds even as characteristics of the robot itself change. For example, such characteristics may include the volume considered occupied by the robot when the robot is holding objects of various sizes, when changing to a different end effector or when changing to a different appendage. Also, there are also challenges with respect to a limited amount of motion planning information that could be stored on processor chip circuitry.

BRIEF SUMMARY

A method of operation in a robot control system may be summarized as including: for a first robot that will operate in an environment, determining a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states are represented by respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph; for at least two or more of the edges of each of the planning graphs, generating a respective set of edge information that represents a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge; storing the plurality of planning graphs and the sets of edge information in at least one nontransitory processor-readable storage; based on at least a portion of the first robot having a first set of physical dimensions at a first time, providing the sets of edge information for a first one of the planning graphs to at least one processor; and based on at least a portion of the first robot having a second set of physical dimensions at a second time, at least one dimension in the second set of physical dimensions different than a corresponding one of the dimensions of the first set, providing the sets of edge information for a second one of the planning graphs to the at least one processor.

The first robot may have at least a first appendage that is selectively operable for movement with respect to the environment in which the first robot operates, and the first robot may have a first end effector attached to the first appendage, the first end effector selectively operable for movement between at least a first and a second end effector arrangements, and may further include determining that the first end effector attached to the first appendage is in a first end effector arrangement, wherein the first set of physical dimensions represent a set of dimensions of the first end effector in the first end effector arrangement; and wherein providing the sets of edge information for a first one of the planning graphs to at least one processor may be in response to the determination that the first end effector attached to the first appendage is in the first end effector arrangement.

The method of operation in a robot control system may further include: determining that the first end effector attached to the first appendage is in a second end effector arrangement, wherein the second set of physical dimensions represents a set of dimensions of the first end effector in the second end effector arrangement; and wherein providing the sets of edge information for a second one of the planning graphs to at least one processor is in response to the determination that the first end effector attached to the first appendage is in the second end effector arrangement.

The first robot may have at least a first appendage that is selectively operable for movement with respect to the environment in which the first robot operates, and a first end effector may be attached to the first appendage, the first end effector selectively operable for movement between at least an un-grasped arrangement and a grasped arrangement, at least one of a size or shape of a volume occupied by the first end effector in the grasped arrangement being different from at least one of a size or shape of a volume occupied by the first end effector in the un-grasped arrangement, and may further include determining that the first end effector attached to the first appendage is in the un-grasped arrangement; wherein providing the sets of edge information for a first one of the planning graphs to at least one processor may be in response to the determination that the first end effector attached to the first appendage is in the un-grasped arrangement; and determining that the first end effector attached to the first appendage may be in the grasped arrangement; wherein providing the sets of edge information for a second one of the planning graphs to at least one processor may be in response to the determination that the first end effector attached to the first appendage is in grasped arrangement. The first robot may have at least a first appendage that is selectively operable for movement with respect to the environment in which the first robot operates, and, may further include determining that the first robot has a first end effector attached to the first appendage, wherein the first set of physical dimensions may represent a set of dimensions of the first end effector attached to the first appendage; and wherein providing the sets of edge information for a first one of the planning graphs to at least one processor may be in response to the determination that the first robot has a first end effector attached to the first appendage.

The method of operation in a robot control system may further include determining that the first robot has a second end effector attached to the first appendage, the second end effector different from the first end effector in at least one of shape or size, wherein the second set of physical dimensions may represent a set of dimensions of the second end effector attached to the first appendage; and wherein providing the sets of edge information for a second one of the planning graphs to at least one processor may be in response to the determination that the first robot has a second end effector attached to the first appendage.

The first robot may be at least one of an autonomous or semi-autonomous vehicle, at least one of a size or shape of a volume occupied by the at least one of an autonomous or semi-autonomous vehicle in a first physical state may be different from at least one of a size or shape of a volume occupied by the at least one of an autonomous or semi-autonomous vehicle in the second physical state (e.g., weight may change due to consumption of fuel, hence velocity may change and distance traveled changes), and may further include determining that the at least one of an autonomous or semi-autonomous vehicle is in the first physical state; wherein providing the sets of edge information for a first one of the planning graphs to at least one processor may be in response to the determination that the at least one of an autonomous or semi-autonomous vehicle is in the first physical state; and determining that the at least one of an autonomous or semi-autonomous vehicle may be in the second physical state; wherein providing the sets of edge information for a second one of the planning graphs to at least one processor may be in response to the determination that the at least one of an autonomous or semi-autonomous vehicle is in second physical state. Providing the sets of edge information for a first one of the planning graphs to at least one processor may include applying the edge information for one of the edges to each of a plurality of circuits of the at least one processor to determine which edges collide with a unit volume occupied by an obstacle in the environment in which the robot operates. Providing the sets of edge information for a first one of the planning graphs to at least one processor may include applying the edge information for one of the edges to each of a plurality of circuits of the at least one processor in parallel. Generating a respective set of edge information that represents a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge may include generating a respective set of edge information that represents in terms of voxels a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge. Generating a respective set of edge information that represents a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge may include generating a respective set of edge information that represents in terms of units of volume, the units of volume that cover two or more voxels, a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge. Generating a respective set of edge information that represents a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge may include generating a respective set of edge information that represents in terms of rectangular prisms (parallelepiped) a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge. Generating a respective set of edge information that represents in terms of rectangular prisms (parallelepiped) a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge may include, for each of the rectangular prisms, storing a pair of three dimensional coordinates that completely define the volume of the respective rectangular prism. The determining a plurality of planning graphs and the generating a respective set of edge information may be performed during a pre-run time period. The providing the sets of edge information for a second one of the planning graphs to the at least one processor may be performed during a run time period.

A processor-based robot control system may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: for a first robot that will operate in an environment, determine a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states are represented by respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph; for at least two or more of the edges of each of the planning graphs, generate a respective set of edge information that represents a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge; store the plurality of planning graphs and the sets of edge information in at least one nontransitory processor-readable storage; based on at least a portion of the first robot having a first set of physical dimensions at a first time, provide the sets of edge information for a first one of the planning graphs to at least one processor; and based on at least a portion of the first robot having a second set of physical dimensions at a second time, at least one dimension in the second set of physical dimensions different than a corresponding one of the dimensions of the first set, provide the sets of edge information for a second one of the planning graphs to the at least one processor.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

A method of operation in a robot control system may be summarized as including: for a first discretized representation of an environment in which at least a first robot will operate, the environment occupied by one or more obstacles, supplying at least a portion of the first discretized representation of the environment to at least one processor; for each edge of a first planning graph of a plurality of planning graphs stored in memory relative to the at least one processor, wherein each planning graph of the plurality of planning graphs is associated with a different set of physical dimensions of the first robot, providing a respective set of edge information to the at least one processor, the respective set of edge information which represents a volume swept by at least a portion of the first robot in transitioning between a pair of states of the first robot, the pair of states of the first robot represented by respective ones of a pair of nodes of the first planning graph, the respective pair of nodes which are coupled by a respective edge of the first planning graph, the respective edge which represents a transition between the respective pair of states of the first robot; and identifying any of the edges of the first planning graph that the corresponding transition would result in a collision between at least a portion of the robot and at least a portion of at least one of the one or more obstacles in the environment.

Providing a respective set of edge information to the at least one processor may include applying the edge information for one of the edges to each of a plurality of circuits of the at least one processor in parallel. Providing a respective set of edge information to the at least one processor may include, for each edge, applying the edge information for the respective edge to each of a plurality of circuits of the at least one processor in parallel. Providing a respective set of edge information to the at least one processor may include, for each edge, applying to circuits of the at least one processor a respective set of edge information that represents in terms of voxels a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge. Providing a respective set of edge information to the at least one processor may include, for each edge, applying to circuits of the at least one processor a respective set of edge information that represents in terms of units of volume a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge, the units of volume which each cover two or more voxels. Providing a respective set of edge information to the at least one processor t may include, for each edge, applying to circuits of the at least one processor a respective set of edge information that represents, in terms of rectangular prisms, a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge, the units of volume which each cover two or more voxels. Applying to the circuits a respective set of edge information that represents, in terms of rectangular prisms, a volume swept by at least a portion of the first robot in transitioning between the states represented by the respective nodes that are coupled by the respective edge may include, for each of the rectangular prisms, storing a pair of three dimensional coordinates that completely define the volume of the respective rectangular prism.

The method of operation in a robot control system may further include: determining that the first robot will or has changed from a first arrangement to a second arrangement, the second arrangement different from the first arrangement; for each edge of a second planning graph of the plurality of planning graphs, providing a respective set of edge information to the at least one processor, the respective set of edge information which represents a volume swept by at least a portion of the first robot in transitioning between a pair of states of the first robot, the pair of states of the first robot represented by respective ones of a pair of nodes of the second planning graph, the respective pair of nodes which are coupled by a respective edge of the second planning graph, the respective edge which represents a transition between the respective pair of states of the first robot, the second planning graph different from the first planning graph; and identifying any of the edges of the second planning graph that the corresponding transition would result in a collision between at least a portion of the robot and at least a portion of at least one of the one or more obstacles in the environment.

The first robot may include a first appendage that is selectively operable for movement with respect to the environment in which the first robot operates, and determining that the first robot will or has changed from a first arrangement to a second arrangement may include determining that a second end effector is attached or being attached to the first appendage in place of a first end effector. The first robot may include a first appendage that is selectively operable for movement with respect to the environment in which the first robot operates, and a first end effector may be attached to the first appendage, the first end effector selectively operable for movement between at least an un-grasped arrangement and a grasped arrangement, at least one of a size or shape of a volume occupied by the first end effector in the grasped arrangement being different from at least one of a size or shape of a volume occupied by the first end effector in the un-grasped arrangement, and determining that the first robot will or has changed from a first arrangement to a second arrangement may include determining that the first end effector attached to the first appendage is changing or has changed a grasp arrangement. Determining that the first end effector attached to the first appendage is changing or has changed a grasp arrangement may include determining that the first end effector is or has transitioned between an un-grasped arrangement and a grasped arrangement. The first robot may be at least one of an autonomous or semi-autonomous vehicle, at least one of a size or shape of a volume occupied by the at least one of an autonomous or semi-autonomous vehicle in a first arrangement is different from at least one of a size or shape of a volume occupied by the at least one of an autonomous or semi-autonomous vehicle in the second arrangement, and wherein determining that the first robot will or has changed from a first arrangement to a second arrangement may include determining that the at least one of an autonomous or semi-autonomous vehicle is transitioning or has transitioned between in the first and the second arrangements of the at least one of an autonomous or semi-autonomous vehicle. The providing a respective set of edge information for each edge of the first planning graph to the at least one processor may include retrieving the respective set of edge information from a nontransitory storage during a run time period, the respective set of edge information which was stored to the nontransitory storage during a pre-run time period. The at least one processor may be at least one of a field programmable gate array or application specific integrated circuit, and providing the respective set of edge information to at least one processor may include applying the edge information for one of the edges to each of a plurality of circuits of the at least one processor implemented in the at least one of a field programmable gate array or application specific integrated circuit.

The method of operation in a robot control system may further include: storing the first discretized representation of the environment in a memory on the at least one processor; and after storing the first discretized representation of the environment in a memory on the at least one processor, receiving the set of edge information by the at least one processor from a storage that is separate from the at least one processor.

A processor-based robot control system may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: for a first discretized representation of an environment in which at least a first robot will operate, the environment occupied by one or more obstacles, supply at least a portion of the first discretized representation of the environment to at least one processor; for each edge of a first planning graph of a plurality of planning graphs stored in memory relative to the at least one processor, wherein each planning graph of the plurality of planning graphs is associated with a different set of physical dimensions of the first robot, provide a respective set of edge information to the at least one processor, the respective set of edge information which represents a volume swept by at least a portion of the first robot in transitioning between a pair of states of the first robot, the pair of states of the first robot represented by respective ones of a pair of nodes of the first planning graph, the respective pair of nodes which are coupled by a respective edge of the first planning graph, the respective edge which represents a transition between the respective pair of states of the first robot; and identify any of the edges of the first planning graph that the corresponding transition would result in a collision between at least a portion of the robot and at least a portion of at least one of the one or more obstacles in the environment.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

A method of operation in a system to facilitate motion planning may be summarized as including: for at least a first scenario that includes a set of a plurality of pairs of tasks and environments, for each of the pairs of tasks and environments of the at least the first scenario, for each of a plurality of iterations, generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor, at least two of the respective discretizations comprising a respective set of voxels, where the voxels of the at least two of the respective discretizations are non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the at least two of the respective discretizations is different from one another; assessing an effectiveness of the generated respective discretizations of the representation of the environment in which the robot will operate; and storing to at least one nontransitory processor-readable media at least the generated respective discretizations of the representation of the environment in which the robot will operate that is assessed to be the most effective for at least the first scenario.

Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels of at least one region in a front of the robot has a relatively small volume as compared to a respective volume of each of a plurality of the voxels in at least one region behind the robot. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels of a first region in a front of the robot has a first volume, a plurality of the voxels of a second region in a front of the robot has a second volume, the second volume different than the first volume. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels of a first region in a front of the robot has a first volume, a plurality of the voxels of a second region in the front of the robot has a second volume, and a plurality of the voxels of a third region in the front of the robot has a third volume, the third volume different than the second volume. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels of a first region in a front of the robot has a first volume, a plurality of the voxels of a second region in the front of the robot has a second volume, and a plurality of the voxels of a third region in the front of the robot has a third volume, the second volume different than the first volume, and the third volume different than the second volume. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot has a first volume, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot has a second volume, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot has a third volume, the second volume different than the first volume, and the third volume different than the second volume. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which a shape of each of a plurality of the voxels in at least one region in a front of the robot is different than a shape of each of a plurality of the voxels of at least one region behind the robot. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels a first region in a front of the robot has a first shape, a plurality of the voxels a second region in a front of the robot has a second shape, the second shape different then the first shape. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels in a first region in a front of the robot has a first shape, a plurality of the voxels a second region in the front of the robot has a second shape, and a plurality of the voxels in a third region in the front of the robot has a third shape, the third shape different than the second shape. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels in a first region in a front of the robot has a first shape, a plurality of the voxels a second region in the front of the robot has a second shape, and a plurality of the voxels in a third region in the front of the robot has a third shape, the second shape different than the first shape, and the third shape different than the second shape. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot has a first shape, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot has a second shape, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot has a third shape, the second shape different than the first shape, and the third shape different than the second shape. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which both a shape and a volume of each of a plurality of the voxels in at least one region in a front of the robot is different than both a shape and a volume of each of a plurality of the voxels of at least one region behind the robot. Generating a respective discretization of a representation of an environment in which a robot will operate by at least one processor may include generating a first respective discretization in which both a shape and a volume of each of a plurality of the voxels in at least one region in a front of the robot is different than both a shape and a volume of each of a plurality of the voxels of at least one region behind the robot, and at least one of the shapes is non-cubic. Assessing an effectiveness of the generated respective discretizations of the representation of the environment in which the robot will operate may include determining which of generated respective discretizations of the representation of the environment in which the robot will operate is mostly likely to result in a path without collisions. Assessing an effectiveness of the generated respective discretizations of the representation of the environment in which the robot will operate may include determining which of generated respective discretizations of the representation of the environment in which the robot will operate is mostly likely to result in a path with a lowest probability of a collision. Assessing an effectiveness of the generated respective discretizations of the representation of the environment in which the robot will operate may include determining which of generated respective discretizations of the representation of the environment in which the robot will operate is mostly likely to result in a lowest cost collision free path. Storing to at least one nontransitory processor-readable media at least the generated respective discretizations of the representation of the environment in which the robot will operate that are assessed to be the most effective for at least the first scenario may include storing at least one generated respective discretization for each of a plurality of scenarios, along with an indication of which of the generated respective discretizations should be used for each of the plurality of scenarios.

A processor-based system to facilitate motion planning may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: for at least a first scenario that includes a set of a plurality of pairs of tasks and environments, for each of the pairs of tasks and environments of the at least the first scenario, for each of a plurality of iterations, generate a respective discretization of a representation of an environment in which a robot will operate by at least one processor, at least two of the respective discretizations comprising a respective set of voxels, where the voxels of the at least two of the respective discretizations are non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the at least two of the respective discretizations is different from one another; assess an effectiveness of the generated respective discretizations of the representation of the environment in which the robot will operate; and store to at least one nontransitory processor-readable media at least the generated respective discretizations of the representation of the environment in which the robot will operate that is assessed to be the most effective for at least the first scenario.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

A method of operation in a system to facilitate motion planning may be summarized as including: based at least in part on an identified scenario that classifies a pair of a task which a robot will perform and an environment in which the robot will operate, determining which of a number of discretizations to use to generate a number of swept volumes that represent respective regions through which at least a portion of the robot will pass when transitioning between one state of the robot and another state of the robot; for each of a plurality of edges in a planning graph, determining a respective swept volume of the edge using the determined discretization, the planning graph comprising a plurality of nodes and a plurality of edges, each node which represents a respective one of a plurality of states of the robot, each of the edges coupling a respective pair of the nodes and representing a respective transition by the robot between the states represented by the respective nodes coupled by the respective edge; and storing to at least one nontransitory processor-readable media at least one of the determined swept volume's respective discretizations of the representation of the environment in which the robot will operate that is assessed to be the most effective for at least the identified scenario.

Determining which of a number of discretizations to use to generate a number of swept volumes may include selecting between at least two discretizations based on the identified scenario, where the voxels of the at least two of the respective discretizations may be non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the at least two of the respective discretizations may be different from one another. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels of at least one region in a front of the robot may have a relatively small volume as compared to a respective volume of each of a plurality of the voxels in at least one region behind the robot. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, a plurality of the voxels in a second region in a front of the robot may have a second volume, the second volume different then the first volume. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot may have a third volume, the third volume different than the second volume. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot may have a third volume, the second volume different than the first volume, and the third volume different than the second volume. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot may have a third volume, the second volume different than the first volume, and the third volume different than the second volume. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which a shape of each of a plurality of the voxels in at least one region in a front of the robot may be different than a shape of each of a plurality of the voxels of at least one region behind the robot. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, and a plurality of the voxels in a second region in a front of the robot may a second shape, the second shape different then the first shape. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot may have a third shape, the third shape different than the second shape. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot may have a third shape, the second shape different than the first shape, and the third shape different than the second shape. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot may have a third shape, the second shape different than the first shape, and the third shape different than the second shape. Determining a respective swept volume of the edge using the determined discretization may include determining the respective swept volume of the edge using the determined discretization in which both a shape and a volume of each of a plurality of the voxels in at least one region in a front of the robot is different than both a shape and a volume of each of a plurality of the voxels of at least one region behind the robot.

The method of operation in a system to facilitate motion planning may further include receiving the identified scenario.

The method of operation in a system to facilitate motion planning may further include providing a respective set of edge information to at least one processor, the respective set of edge information which represents the respective swept volume swept by at least a portion of the first robot in transitioning between a pair of states of the robot.

The at least one processor may be at least one of a field programmable gate array or application specific integrated circuit, and may further include applying a respective set of edge information to each of a plurality of circuits of the at least one processor implemented in the at least one of a field programmable gate array or application specific integrated circuit, the respective set of edge information which represents the respective swept volume swept by at least a portion of the robot in transitioning between a pair of states of the robot.

A processor-based system to facilitate motion planning may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: based at least in part on an identified scenario that classifies a pair of a task which a robot will perform and an environment in which the robot will operate, determine which of a number of discretizations to use to generate a number of swept volumes that represent respective regions through which at least a portion of the robot will pass when transitioning between one state of the robot and another state of the robot; for each of a plurality of edges in a planning graph, determine a respective swept volume of the edge using the determined discretization, the planning graph comprising a plurality of nodes and a plurality of edges, each node which represents a respective one of a plurality of states of the robot, each of the edges coupling a respective pair of the nodes and representing a respective transition by the robot between the states represented by the respective nodes coupled by the respective edge; and store to at least one nontransitory processor-readable media at least one of the determined swept volume's respective discretizations of the representation of the environment in which the robot will operate that is assessed to be the most effective for at least the identified scenario.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

A method of operation in a system to facilitate motion planning may be summarized as including: based at least in part on an identified scenario that classifies a pair of a task which a robot will perform and an environment in which the robot operates, determining which of a number of discretizations to use to generate a discretized representation of the environment, including obstacles, if any, in the environment; receiving sensor information produced by one or more sensors that sense the environment, the sensor information which represents the environment, including obstacles, if any, in the environment; and generating a discretized representation of the environment, including obstacles, if any, in the environment using the determined discretization, wherein a plurality of voxels of the determined discretization are non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the determined discretization is different from that of another one of the number of discretizations.

The method of operation in a system to facilitate motion planning may further include storing to at least one nontransitory processor-readable media the determined generated discretized representation of the environment, including obstacles, if any, in the environment.

Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using a distribution of voxel size and shape that matches a distribution of voxel size and shape used to generate a discretized representation of a swept volume. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using a distribution of voxel size and shape that matches a distribution of voxel size and shape used to generate a discretized representation of a swept volume swept by at least a portion of a robot. Determining which of a number of discretizations to use to generate a discretized representation of the environment, including obstacles, if any, in the environment, may include selecting between at least two discretizations based on the identified scenario, where the voxels of the at least two of the respective discretizations may be non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the at least two of the respective discretizations may be different from one another. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels of at least one region in a front of the robot may have a relatively small volume as compared to a respective volume of each of a plurality of the voxels in at least one region behind the robot. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, and a plurality of the voxels in a second region in a front of the robot may a second volume, the second volume different then the first volume. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot may have a third volume, the third volume different than the second volume. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot may have a third volume, the second volume different than the first volume, and the third volume different than the second volume. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot may have a first volume, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot may have a second volume, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot may have a third volume, the second volume different than the first volume, and the third volume different than the second volume. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which a shape of each of a plurality of the voxels in at least one region in a front of the robot may be different than a shape of each of a plurality of the voxels of at least one region behind the robot. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, and a plurality of the voxels in a second region in a front of the robot may have a second shape, the second shape different then the first shape. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot may have a third shape, the third shape different than the second shape. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot may have a third shape, the second shape different than the first shape, and the third shape different than the second shape. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which each of a plurality of the voxels in a first region immediately in a front of the robot may have a first shape, a plurality of the voxels in a second region in the front of the robot and spaced relatively outward from the first region with respect to the robot may have a second shape, and a plurality of the voxels in a third region in the front of the robot and spaced relatively outward from the second region with respect to the robot may have a third shape, the second shape different than the first shape, and the third shape different than the second shape. Generating a discretized representation of the environment, including obstacles, if any, in the environment may include generating the discretized representation of the environment using the determined discretization in which both a shape and a volume of each of a plurality of the voxels in at least one region in a front of the robot may be different than both a shape and a volume of each of a plurality of the voxels of at least one region behind the robot.

The method of operation in a system to facilitate motion planning may further include: receiving information that represents the task to be performed by the robot and the environment in which the robot is to operate; identifying the identified scenario based at least in part on received information.

The method of operation in a system to facilitate motion planning may further include providing the discretized representation of the environment to at least one processor.

The at least one processor may be at least one of a field programmable gate array or application specific integrated circuit, and may further include applying the discretized representation of the environment to each of a plurality of circuits implemented in the at least one of a field programmable gate array or application specific integrated circuit.

A processor-based system to facilitate motion planning may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: based at least in part on an identified scenario that classifies a pair of a task which a robot will perform and an environment in which the robot operates, determine which of a number of discretizations to use to generate a discretized representation of the environment, including obstacles, if any, in the environment; receive sensor information produced by one or more sensors that sense the environment, the sensor information which represents the environment, including obstacles, if any, in the environment; and generate a discretized representation of the environment, including obstacles, if any, in the environment using the determined discretization, wherein a plurality of voxels of the determined discretization are non-homogenous in at least one of size and shape within the respective discretization, and a respective distribution of the non-homogeneousness of the voxels of the determined discretization is different from that of another one of the number of discretizations.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

A method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may be summarized as including: for a first planning graph of the plurality of planning graphs, for each of a plurality of edges of the first planning graph performing collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate; updating the first planning graph based on the collision checking; performing an optimization of the updated first planning graph to identify one or more optimized results, if any, from the updated first planning graph; determining whether the one or more optimized results, if any, from the updated first planning graph meets a satisfaction condition; in response to determining that the optimized result does not meet the satisfaction condition: for each of a plurality of edges of the second planning graph performing collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate, updating the second planning graph based on the collision checking; and performing an optimization of the updated second planning graph to identify one or more optimized results, if any, from the updated second planning graph.

The method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may further include determining whether the one or more optimized results, if any, from the updated second planning graph, if any, meets a satisfaction condition.

The method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may, in response to determining that the one or more optimized results, if any, from the updated second planning graph meets the satisfaction condition, apply a transition identified by one of the one or more optimized results from the updated second planning graph to the robot.

The method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may, in response to determining that the one or more optimized results, if any, from the updated second planning graph does not meet the satisfaction condition: for each of a plurality of edges of a third planning graph performing collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate, update the third planning graph based on the collision checking; and perform an optimization of the updated third planning graph to identify one or more optimized results, if any, from the updated third planning graph.

The method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may, in response to determining that the one or more optimized results, if any, from the updated third planning graph meets the satisfaction condition: apply a transition identified by one of the one or more optimized results from the updated third planning graph to the robot.

Determining that the one or more optimized results, if any, from the updated second planning graph meets the satisfaction condition may include determining whether the optimization produces any paths. Determining that the one or more optimized results, if any, from the updated second planning graph meets the satisfaction condition may include determining whether the optimization produces any collision-free paths. Performing collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate may include, for each of the edges in the first planning graph, applying a set of edge information for the edges to each of a plurality of circuits in parallel, the circuits which each represent a respective unit volume occupied by an obstacle in the environment in which the robot operates.

The method of operation in a robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph may further include configuring at least one processor to implement a plurality of circuits that represent respective ones of each of a plurality of unit volumes occupied by one or more obstacles in the environment in which at least the first robot will operate.

A processor-based robot control system that employs a plurality of planning graphs, each planning graph respectively comprising a plurality of nodes connected by a plurality of edges, each node which represents, implicitly or explicitly, variables that characterize a respective state of the first robot, and each edge which represents a transition between a respective pair of the states of the first robot, where the respective pair of states is represented by a respective ones of a pair of nodes that are coupled by a respective edge in the respective planning graph, may be summarized as including: at least one processor; and at least one nontransitory processor-readable medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor, causes the at least one processor to: for a first planning graph of the plurality of planning graphs, for each of a plurality of edges of the first planning graph perform collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate; update the first planning graph based on the collision checking; perform an optimization of the updated first planning graph to identify one or more optimized results, if any, from the updated first planning graph; determine whether the one or more optimized results, if any, from the updated first planning graph meets a satisfaction condition; in response to determining that the optimized result does not meet the satisfaction condition: for each of a plurality of edges of the second planning graph perform collision checking for collisions between a discretized representation of a swept volume associated with the edge and a discretized representation of any obstacles in an environment in which the robot will operate, update the second planning graph based on the collision checking; and perform an optimization of the updated second planning graph to identify one or more optimized results, if any, from the updated second planning graph.

The at least one of processor-executable instructions or data, when executed by the at least one processor, may further cause the at least one processor to perform any of the methods described above.

