Anyone who has ever tried to pack a family-sized amount of bags right into a sedan-sized trunk knows this can be a hard problem. Robots struggle with dense packing tasks, too.

For the robot, solving the packing problem involves satisfying many constraints, resembling stacking luggage so suitcases don’t topple out of the trunk, heavy objects aren’t placed on top of lighter ones, and collisions between the robotic arm and the automotive’s bumper are avoided.

Some traditional methods tackle this problem sequentially, guessing a partial solution that meets one constraint at a time after which checking to see if another constraints were violated. With an extended sequence of actions to take, and a pile of bags to pack, this process could be impractically time consuming.   

MIT researchers used a type of generative AI, called a diffusion model, to resolve this problem more efficiently. Their method uses a set of machine-learning models, each of which is trained to represent one specific kind of constraint. These models are combined to generate global solutions to the packing problem, taking into consideration all constraints without delay.

Their method was in a position to generate effective solutions faster than other techniques, and it produced a greater variety of successful solutions in the identical period of time. Importantly, their technique was also in a position to solve problems with novel mixtures of constraints and bigger numbers of objects, that the models didn’t see during training.

Attributable to this generalizability, their technique could be used to show robots tips on how to understand and meet the general constraints of packing problems, resembling the importance of avoiding collisions or a desire for one object to be next to a different object. Robots trained in this manner could possibly be applied to a big selection of complex tasks in diverse environments, from order achievement in a warehouse to organizing a bookshelf in someone’s home.

“My vision is to push robots to do more complicated tasks which have many geometric constraints and more continuous decisions that must be made — these are the sorts of problems service robots face in our unstructured and diverse human environments. With the powerful tool of compositional diffusion models, we will now solve these more complex problems and get great generalization results,” says Zhutian Yang, an electrical engineering and computer science graduate student and lead writer of a paper on this latest machine-learning technique.

Her co-authors include MIT graduate students Jiayuan Mao and Yilun Du; Jiajun Wu, an assistant professor of computer science at Stanford University; Joshua B. Tenenbaum, a professor in MIT’s Department of Brain and Cognitive Sciences and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL); Tomás Lozano-Pérez, an MIT professor of computer science and engineering and a member of CSAIL; and senior writer Leslie Kaelbling, the Panasonic Professor of Computer Science and Engineering at MIT and a member of CSAIL. The research will probably be presented on the Conference on Robot Learning.

Constraint complications

Continuous constraint satisfaction problems are particularly difficult for robots. These problems appear in multistep robot manipulation tasks, like packing items right into a box or setting a dinner table. They often involve achieving quite a few constraints, including geometric constraints, resembling avoiding collisions between the robot arm and the environment; physical constraints, resembling stacking objects in order that they are stable; and qualitative constraints, resembling placing a spoon to the suitable of a knife.

There could also be many constraints, and so they vary across problems and environments depending on the geometry of objects and human-specified requirements.

To resolve these problems efficiently, the MIT researchers developed a machine-learning technique called Diffusion-CCSP. Diffusion models learn to generate latest data samples that resemble samples in a training dataset by iteratively refining their output.

To do that, diffusion models learn a procedure for making small improvements to a possible solution. Then, to resolve an issue, they begin with a random, very bad solution after which step by step improve it.

For instance, imagine randomly placing plates and utensils on a simulated table, allowing them to physically overlap. The collision-free constraints between objects will end in them nudging one another away, while qualitative constraints will drag the plate to the middle, align the salad fork and dinner fork, etc.

Diffusion models are well-suited for this type of continuous constraint-satisfaction problem since the influences from multiple models on the pose of 1 object could be composed to encourage the satisfaction of all constraints, Yang explains. By ranging from a random initial guess every time, the models can obtain a various set of excellent solutions.

Working together

For Diffusion-CCSP, the researchers desired to capture the interconnectedness of the constraints. In packing for example, one constraint might require a certain object to be next to a different object, while a second constraint might specify where certainly one of those objects should be positioned.

Diffusion-CCSP learns a family of diffusion models, with one for every kind of constraint. The models are trained together, in order that they share some knowledge, just like the geometry of the objects to be packed.

The models then work together to seek out solutions, on this case locations for the objects to be placed, that jointly satisfy the constraints.

“We don’t all the time get to an answer at the primary guess. But while you keep refining the answer and a few violation happens, it should lead you to a greater solution. You get guidance from getting something improper,” she says.

Training individual models for every constraint type after which combining them to make predictions greatly reduces the quantity of coaching data required, in comparison with other approaches.

Nonetheless, training these models still requires a considerable amount of data that exhibit solved problems. Humans would wish to resolve each problem with traditional slow methods, making the fee to generate such data prohibitive, Yang says.

As an alternative, the researchers reversed the method by coming up with solutions first. They used fast algorithms to generate segmented boxes and fit a various set of 3D objects into each segment, ensuring tight packing, stable poses, and collision-free solutions.

“With this process, data generation is nearly instantaneous in simulation. We are able to generate tens of 1000’s of environments where we all know the issues are solvable,” she says.

Trained using these data, the diffusion models work together to find out locations objects must be placed by the robotic gripper that achieve the packing task while meeting the entire constraints.

They conducted feasibility studies, after which demonstrated Diffusion-CCSP with an actual robot solving quite a few difficult problems, including fitting 2D triangles right into a box, packing 2D shapes with spatial relationship constraints, stacking 3D objects with stability constraints, and packing 3D objects with a robotic arm.

Their method outperformed other techniques in lots of experiments, generating a greater variety of effective solutions that were each stable and collision-free.

In the longer term, Yang and her collaborators wish to test Diffusion-CCSP in additional complicated situations, resembling with robots that may move around a room. In addition they wish to enable Diffusion-CCSP to tackle problems in numerous domains without the must be retrained on latest data.

“Diffusion-CCSP is a machine-learning solution that builds on existing powerful generative models,” says Danfei Xu, an assistant professor within the School of Interactive Computing on the Georgia Institute of Technology and a Research Scientist at NVIDIA AI, who was not involved with this work. “It may quickly generate solutions that concurrently satisfy multiple constraints by composing known individual constraint models. Even though it’s still within the early phases of development, the continued advancements on this approach hold the promise of enabling more efficient, secure, and reliable autonomous systems in various applications.”

This research was funded, partially, by the National Science Foundation, the Air Force Office of Scientific Research, the Office of Naval Research, the MIT-IBM Watson AI Lab, the MIT Quest for Intelligence, the Center for Brains, Minds, and Machines, Boston Dynamics Artificial Intelligence Institute, the Stanford Institute for Human-Centered Artificial Intelligence, Analog Devices, JPMorgan Chase and Co., and Salesforce.