Workflow for using tree search-based approach for placing boxes on pallet with limited knowledge of future sequence

Patent metadata

Field	Value
Publication number	US-12390928-B2
Application number	US-202217838039-A
Country	US
Kind code	B2
Filing date	Jun 10, 2022
Priority date	Jun 16, 2021
Publication date	Aug 19, 2025
Grant date	Aug 19, 2025

Abstract

A robotic system is disclosed. The system includes a communication interface that receives, from one or more sensors deployed in a workspace, sensor data indicative of a current state of the workspace. The system includes one or more processors that use the sensor data to estimate a state of one or both of the pallet or other receptacle and the set of zero or more items stacked on or in the receptacle, and use the estimated state to generate or update a plan to control a robotic arm to place a next set of items on or in, or remove the next set of items from, the pallet or other receptacle, the plan comprising an ordered sequence of item placements or removals. The plan is generated or updated based at least in part by performing a bounded tree search in which a subset of possible ordered sequences is explored.

First claim

The invention claimed is:

1. A robotic system, comprising:
a communication interface configured to receive, from one or more sensors deployed in a workspace, sensor data indicative of a current state of the workspace, the workspace comprising a pallet or other receptacle and a set of zero or more items stacked on or in the receptacle; and
one or more processors coupled to the communication interface and configured to:
use the sensor data to estimate a state of one or both of the pallet or other receptacle and the set of zero or more items stacked on or in the receptacle; and
use the estimated state to generate or update a plan to control a robotic arm to place a next set of items on or in, or remove the next set of items from, the pallet or other receptacle, the plan comprising an ordered sequence of item placements or removals;
wherein:
the one or more processors are configured to generate or update the plan at least in part by performing a bounded tree search in which a subset of possible ordered sequences is explored; and
the subset is determined by one or both of selecting for exploration tree branches that satisfy one or more selection criteria or omitting from consideration one or more branches that satisfy a pruning criteria, wherein the pruning criteria is associated with a determination that a branch does not comprise a node corresponding to a favorable scenario.

2. The robotic system of claim 1 , wherein an item placement comprises a placement of the item in a particular location.

3. The robotic system of claim 1 , wherein an item placement comprises a placement of the item in a particular orientation.

4. The robotic system of claim 3 , wherein:
the item is a box; and
the item placement is one of six orientations.

5. The robotic system of claim 1 , wherein the pruning criteria is associated with instability of one or more items stacked on or in the receptacle.

6. The robotic system of claim 5 , wherein the instability is determined based at least in part on one or more historical observations.

7. The robotic system of claim 5 , wherein the instability is determined based at least in part on a simulation of stacking or removing at least one of the zero or more items stacked on or in the receptacle.

8. The robotic system of claim 5 , wherein the instability is determined based at least in part on one or more predefined heuristics.

9. The robotic system of claim 8 , wherein at least one heuristic includes an indication of stacking an item having a weight exceeding a predefined weight threshold on top of an item having a packaging that is deformable.

10. The robotic system of claim 1 , wherein the pruning criteria is associated with a packing density less than a predefined packing density threshold.

11. The robotic system of claim 1 , wherein the pruning criteria is associated with a determination that stacking items according to a particular sequence of the subset of possible ordered sequences is expected to result in a collision.

12. The robotic system of claim 1 , wherein the pruning criteria is associated with a determination that stacking items according to a particular sequence of the subset of possible ordered sequences is expected to result in the robotic arm to move more than a predefined movement threshold to avoid a collision.

13. The robotic system of claim 1 , wherein the pruning criteria is associated with a determination that a particular sequence of the subset of possible ordered sequences includes placements that are not along an edge or vertex of an item already placed on the pallet.

14. The robotic system of claim 1 , wherein the favorable scenario is determined to be a placement for which a corresponding value for a value function exceeds a predefined favorability threshold.

15. The robotic system of claim 14 , wherein the value function is based at least in part on one or more of a packing density, an expected stability, and an expected efficiency of item placement.

16. The robotic system of claim 1 , wherein the one or more selection criteria are associated with an expected packing density exceeding a predefined density threshold.

17. The robotic system of claim 1 , wherein the one or more selection criteria are associated with one or more predefined heuristics.

18. The robotic system of claim 17 , wherein the one or more predefined heuristics include a bias for placing heavy or large items at a bottom of a stack.

19. The robotic system of claim 1 , wherein the one or more selection criteria are associated with an expected stability.

20. The robotic system of claim 19 , wherein the expected stability pertains to a layer in a stack or a top layer topography.

21. The robotic system of claim 1 , wherein the one or more selection criteria are associated with first exploring branches involving a placement of a first subset of one or more items on a far side away from a robot first, and subsequent placement of a second subset of one or more items at a location closer to the robot.

22. The robotic system of claim 21 , wherein the first subset is determined based at least in part on performing a beam search of the tree branches, the beam search being limited to N possible placements, and N is a positive integer.

23. The robotic system of claim 1 , wherein:
each node of the tree of possible ordered sequences corresponds to a scenario of a placement of items up to that point in the ordered sequence; and
each branch of the tree of possible ordered sequences corresponds to a decision to place a next item at a particular location or in a particular orientation.

24. A method to control a robot, comprising:
receiving, from one or more sensors deployed in a workspace, sensor data indicative of a current state of the workspace, the workspace comprising a pallet or other receptacle and a set of zero or more items stacked on or in the receptacle;
using the sensor data to estimate a state of one or both of the pallet or other receptacle and the set of zero or more items stacked on or in the receptacle; and
using the estimated state to generate or update a plan to control a robotic arm to place a next set of items on or in, or remove the next set of items from, the pallet or other receptacle, the plan comprising an ordered sequence of item placements or removals;
wherein:
generating or updating the plan includes performing a bounded tree search in which a subset of possible ordered sequences is explored; and
the subset is determined by one or both of selecting for exploration tree branches that satisfy one or more selection criteria or omitting from consideration one or more branches that satisfy a pruning criteria, wherein the pruning criteria is associated with a determination that a branch does not comprise a node corresponding to a favorable scenario.

25. A computer program product to control a robot, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
receiving, from one or more sensors deployed in a workspace, sensor data indicative of a current state of the workspace, the workspace comprising a pallet or other receptacle and a set of zero or more items stacked on or in the receptacle;
using the sensor data to estimate a state of one or both of the pallet or other receptacle and the set of zero or more items stacked on or in the receptacle; and
using the estimated state to generate or update a plan to contr

Assignees

• Dexterity Inc

Inventors

• Pidaparthi Rohit Arka
• Clary William Arthur
• Abhyankar Neeraja
• Kuck Jonathan
• Pottayil Ben Varkey Benjamin
• Chavez Kevin Jose
• Kumar Shitij

Classifications

• B25J9/1694

  characterised by use of sensors other than normal servo-feedback from position, speed or acceleration sensors, perception control, multi-sensor controlled systems, sensor fusion · CPC title

• B25J9/1697

  Vision controlled systems · CPC title

• B25J9/1671

  characterised by simulation, either to verify existing program or to create and verify new program, CAD/CAM oriented, graphic oriented programming systems · CPC title

• B25J9/1661

  characterised by task planning, object-oriented languages · CPC title

• G05B2219/40067

  Stack irregular packages · CPC title