Efficient object manipulation planning with Monte Carlo Tree Search

This paper was a finalist for the Best Paper Award on Mobile Manipulation at IROS 2023. It is one of 5 finalists out of 2760 submitted papers at one of the largest robotics conferences in the world.

In the field of robotics, the intricate dance of planning how machines touch and maneuver objects is a linchpin for granting them the autonomy to execute intricate tasks. However, this endeavor remains a challenge. The pursuit of identifying dynamically viable sequences of contacts between robotic manipulators and objects often unravels into a web of formidable combinatorial and nonlinear complications.

Consider the ostensibly simple act of reorienting an object nestled on a table using a two-fingered robotic hand. The strategic planning of contacts necessitates a thoughtful consideration of interaction forces. For instance, a cube succumbs to rotation through forces applied from its sides. In stark contrast, when faced with a slender plate, the robotic fingers must exert a downward pressure — initiating a frictional interplay — to achieve a comparable outcome.

The crux of the challenge lies in the nuanced orchestration of interaction forces and judicious contact switches. As the robotic fingers approach their kinematic limits, a process of breaking and re-establishing contacts becomes imperative to propel the object into further rotation. These twin challenges, encapsulated in interaction forces and contact switches, underscore the complexity inherent in planning the manipulation of objects.

Over the past decade, trajectory optimization has emerged as the favored approach for orchestrating multi-contact motion planning. This methodology holds sway due to its capacity to construct efficient formulations for navigating the intricate terrain of interaction forces. Yet, a lingering problem persists—the effective integration of planning for contact modes remains elusive, primarily attributed to its discrete nature, injecting a disruptive discontinuity into the dynamics at the crucial juncture of contact switches.

Now, a team of NYU researchers led by Ludovic Righetti, Associate Professor of Electrical and Computer Engineering Department and Mechanical and Aerospace Engineering, as well as a member of the Center for Urban Science + Progress, have developed a strategy for planning object manipulation, leveraging the power of Monte Carlo Tree Search (MCTS) to discern optimal contact sequences. Complementing this, an adept trajectory optimization algorithm, rooted in Alternating Direction Method of Multipliers (ADMM), evaluates the dynamic feasibility of potential contact sequences. The algorithm was previously developed by Righetti’s group, The Machines in Motion Laboratory.

The team, including Ph.D. students Huaijiang Zhu and Avadesh Meduri, made a key innovation in expediting MCTS involving the development of a goal-conditioned policy-value network, guiding the search toward promising nodes. Additionally, manipulation-specific heuristics prove instrumental in markedly shrinking the search space.

The efficacy of the approach is underscored through a series of meticulous object manipulation experiments conducted both in a physics simulator and on tangible hardware. The methodology exhibits a favorable scalability for protracted manipulation sequences, a testament to the learned policy-value network. 

This advancement substantially elevates the planning success rate, marking a significant stride in the realm of object manipulation planning.

Zhu, H., Meduri, A., & Righetti, L. (2023, March 19). Efficient object manipulation planning with Monte Carlo Tree Search. arXiv.org. https://arxiv.org/abs/2206.09023