Algorithmic Robotics & Control Lab @ Rutgers


For a more comprehensive set of videos, please check our YouTube channel.

Application Domains

Manipulation in Clutter ●  Multi-Object Rearrangement ●  Multi-Robot Path and Motion Planning ●  Surveillance and Monitoring ●  Industrial Collaboration: End-to-End Systems

Manipulation in Clutter

Parallel MCTS for Object Retrieval in Clutter (IROS 22) ●  Self-Supervised Learning-Guided MCTS (ICRA 22) ●  Visual Foresight Trees for Object Retrieval (RA-L 22) ●  Declutter with Deep Interaction Prediction Network (ICRA 21) ●  Back to Top

Parallel MCTS for Object Retrieval in Clutter

We propose a novel Parallel Monte Carlo tree search with Batched Simulations (PMBS) algorithm for accelerating long-horizon, episodic robotic planning tasks. Monte Carlo tree search (MCTS) is an effective heuristic search algorithm for solving episodic decision-making problems whose underlying search spaces are expansive. Leveraging a GPU-based large-scale simulator, PMBS introduces massive parallelism into MCTS for solving planning tasks through the batched execution of a large number of concurrent simulations, which allows for more efficient and accurate evaluations of the expected cost-to-go over large action spaces. When applied to the challenging manipulation tasks of object retrieval from clutter, PMBS achieves a speedup of over 30x with an improved solution quality, in comparison to a serial MCTS implementation. We show that PMBS can be directly applied to a real robot hardware with negligible sim-to-real differences.

Self-Supervised Learning-Guided MCTS

Working with the task of object retrieval in clutter, we developed a robot learning framework in which Monte Carlo Tree Search (MCTS) is first applied to enable a Deep Neural Network (DNN) to learn the intricate interactions between a robot arm and a complex scene containing many objects, allowing the DNN to partially clone the behavior of MCTS. In turn, the trained DNN is integrated into MCTS to help guide its search effort. We call this approach learning-guided Monte Carlo tree search for Object REtrieval (MORE), which delivers significant computational efficiency gains and added solution optimality. MORE is a self-supervised robotics framework/pipeline capable of working in the real world that successfully embodies the System 2 to System 1 learning philosophy proposed by Kahneman, where learned knowledge, used properly, can help greatly speed up a time-consuming decision process over time.

Visual Foresight Trees for Object Retrieval

We consider the problem of retrieving an object from many tightly packed objects using a combination of robotic pushing and grasping actions. Object retrieval in dense clutter is an important skill for robots to operate in households and everyday environments effectively. The proposed solution, Visual Foresight Trees (VFT), intelligently rearranges the clutter surrounding a target object so that it can be grasped easily. Rearrangement with nested nonprehensile actions is challenging as it requires predicting complex object interactions in a combinatorially large configuration space of multiple objects. We first show that a deep neural network can be trained to accurately predict the poses of the packed objects when the robot pushes one of them. The predictive network provides visual foresight and is used in a tree search as a state transition function in the space of scene images. The tree search returns a sequence of consecutive push actions yielding the best arrangement of the clutter for grasping the target object. Experiments show that the proposed approach outperforms model-free techniques as well as model-based myopic methods both in terms of success rates and the number of executed actions, on several challenging tasks.

Declutter with Deep Interaction Prediction Network

We propose a Deep Interaction Prediction Network (DIPN) for learning to predict complex interactions that ensue as a robot end-effector pushes multiple objects, whose physical properties, including size, shape, mass, and friction coefficients may be unknown a priori. DIPN "imagines" the effect of a push action and generates an accurate synthetic image of the predicted outcome. DIPN is shown to be sample efficient when trained in simulation or with a real robotic system. The high accuracy of DIPN allows direct integration with a grasp network, yielding a robotic manipulation system capable of executing challenging clutter removal tasks while being trained in a fully self-supervised manner. The overall network demonstrates intelligent behavior in selecting proper actions between push and grasp for completing clutter removal tasks and significantly outperforms the previous state-of-the-art. Remarkably, DIPN achieves even better performance on the real robotic hardware system than in simulation.

Multi-Object Rearrangement

Optimal Dual-Arm Tabletop Object Rearrangement (IROS 22) ●  Tabletop Rearrangement in Bounded Workspace (ICRA 21) ●  Rearrangement on Lattices with Pick-n-Swaps (RSS 21) ●  Running Buffer Minimization for Tabletop Rearrangement (RSS 21) ●  Optimal Robotic Pick-and-Place on a Moving Conveyor (RA-L 20) ●  Efficient High Quality Stack Rearrangement (ICRA 18) ●  Tabletop Object Rearrangement with Overhand Grasps (RSS 17, IJRR 18) ●  Back to Top

Toward Optimal Dual-Arm Tabletop Object Rearrangement

We investigate the problem of coordinating two robot arms to solve non-monotone tabletop multi-object rearrangement tasks. In a non-monotone rearrangement task, complex object-object dependencies exist that require moving some objects multiple times to solve an instance. In working with two arms in a large workspace, some objects must be handed off between the robots, which further complicates the planning process. For the challenging dual-arm tabletop rearrangement problem, we develop effective task planning algorithms for scheduling the pick-n-place sequence that can be properly distributed between the two arms. We show that, even without using a sophisticated motion planner, our method achieves significant time savings in comparison to greedy approaches and naive parallelization of single-robot plans.

Tabletop Rearrangement in Bounded Workspace

We examine the problem of rearranging many objects on a tabletop in a cluttered setting using overhand grasps. Efficient solutions for the problem, which capture a common task that we solve on a daily basis, are essential in enabling truly intelligent robotic manipulation. In a given instance, objects may need to be placed at temporary positions (“buffers”) to complete the rearrangement, but allocating these buffer locations can be highly challenging in a cluttered environment. To tackle the challenge, a two-step baseline planner is first developed, which generates a primitive plan based on inherent combinatorial constraints induced by start and goal poses of the objects and then selects buffer locations assisted by the primitive plan. We then employ the “lazy” planner in a tree search framework which is further sped up by adapting a novel preprocessing routine. Simulation experiments show our methods can quickly generate high-quality solutions and are more robust in solving large-scale instances than existing state-of-the-art approaches.

Rearrangement on Lattices with Pick-n-Swaps

We study a class of rearrangement problems under a novel pick-n-swap prehensile manipulation model, in which a robotic manipulator, capable of carrying an item and making item swaps, is tasked to sort items stored in lattices of variable dimensions in a time-optimal manner. We systematically analyze the intrinsic optimality structure, which is fairly rich and intriguing, under different levels of item distinguishability (fully labeled, where each item has a unique label, or partially labeled, where multiple items may be of the same type) and different lattice dimensions. Focusing on the most practical setting of one and two dimensions, we develop low polynomial time cycle-following-based algorithms that optimally perform rearrangements on 1D lattices under both fully- and partially-labeled settings. On the other hand, we show that rearrangement on 2D and higher-dimensional lattices become computationally intractable to optimally solve. Despite their NP-hardness, we prove that efficient cycle-following-based algorithms remain optimal in the asymptotic sense for 2D fully- and partially-labeled settings, in expectation, using the interesting fact that random permutations induce only a small number of cycles. We further improve these algorithms to provide 1.x-optimality when the number of items is small. Simulation studies corroborate the effectiveness of our algorithms.

Running Buffer Minimization for Tabletop Rearrangement

For tabletop rearrangement problems with overhand grasps, storage space outside the tabletop workspace, or buffers, can temporarily hold objects which greatly facilitates the resolution of a given rearrangement task. This brings forth the natural question of how many running buffers are required so that certain classes of tabletop rearrangement problems are feasible. In this work, we examine the problem for both the labeled (where each object has a specific goal pose) and the unlabeled (where goal poses of objects are interchangeable) settings. On the structural side, we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance, and show that computing MRB on dependency graphs is NP-hard. We then prove that under both labeled and unlabeled settings, even for uniform cylindrical objects, the number of required running buffers may grow unbounded as the number of objects to be rearranged increases; we further show that the bound for the unlabeled case is tight. On the algorithmic side, we develop highly effective algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems, scalable to over a hundred objects under very high object density. Employing these algorithms, empirical evaluations show that random labeled and unlabeled instances, which more closely mimics real-world setups, have much smaller MRBs.

Optimal Robotic Pick-and-Place on a Moving Conveyor

Robotic pick-and-place (PnP) operations on moving conveyors find a wide range of industrial applications. In practice, simple greedy heuristics (e.g., prioritization based on the time to process a single object) are applied that achieve reasonable efficiency. We show analytically that, under a simplified telescoping robot model, these greedy approaches do not ensure time optimality of PnP operations. To address the shortcomings of classical solutions, we develop algorithms that compute optimal object picking sequences for a predetermined finite horizon. Employing dynamic programming techniques and additional heuristics, our methods scale to up to tens to hundreds of objects. In particular, the fast algorithms we develop come with running time guarantees, making them suitable for real-time PnP applications demanding high throughput. Extensive evaluation of our algorithmic solution over dominant industrial PnP robots used in real-world applications, i.e., Delta robots and Selective Compliance Assembly Robot Arm (SCARA) robots, shows that a typical efficiency gain of around 10-40% over greedy approaches can be realized.

Efficient High Quality Stack Rearrangement

Efficient High Quality Stack Rearrangement - Video highlight of our RA-L/ICRA 2018 work with the same name. Abstract: We study a variant of rearrangement problems that appear frequently in applications, which involves sorting objects or robots in stack-like containers that can be accessed only from one side. We provide efficient algorithms that could generate high quality rearrangement sequence.

Tabletop Object Rearrangement with Overhand Grasps

Optimal Tabletop Object Rearrangement with Overhand Grasps - Video highlight of our RSS 2017 work on optimal tabletop object rearrangement and subsequent extended version. Our hardware experiments confirm our hypothesis that (1) grasping/releasing is generally much more time consuming and (2) our proposed algorithm provide significant benefit when compared with a greedy algorithm.

Multi-Robot Path and Motion Planning

1.x Time-Optimal Multi-Robot Path Planning in 2D and 3D (RSS 22, IROS 22) ●  Path-Diversification and Database-Driven Multi-Robot Path Planning (RA-L 20) ●  Multi-Robot Motion Planning in Continuous Domain under Extreme Density (WAFR 2018) ●  Open-Source micro-Multi-Vehicle Platform (ICRA 2017) ●  Fast Near-Optimal Multi-Robot Path Planning in Continuous Domain (ISRR 15) ●  Optimal Formation Reconfiguration (CDC 12, CDC 13) ●  Rendezvous without Coordinates (CDC 08, TAC 12) ●  Back to Top

1.x Time-Optimal Multi-Robot Path Planning in 2D and 3D

Multi-robot path planning (MRPP) is NP-hard to optimally solve on graphs, suggesting no polynomial-time algorithms can compute exact optimal solutions for them. This raises a natural question: How optimal can polynomial-time algorithms reach? In this work, among other breakthroughs, we propose the first low-polynomial-time MRPP algorithms delivering 1-1.5 (resp., 1-1.67) asymptotic makespan optimality guarantees for 2D (resp., 3D) grids for random instances at a very high 1/3 robot density, with high probability. Moreover, our methods experience no performance degradation when regularly distributed obstacles are introduced. These methods generalize to support 100% robot density. Simple Python-based implementations of our RTA-based algorithms are shown to be highly effective in extensive numerical evaluations, demonstrating unprecedented scalability as compared with methods including ECBS and DDM. For example, in 3D settings, RTA-based algorithms readily scale to grids with over $370,000$ vertices and over $120,000$ robots and consistently achieves conservative makespan optimality approaching $1.5$, as predicted by our theoretical analysis.

Path-Diversification and Database-Driven Multi-Robot Path Planning

DDM - DDM solves one-shot and dynamic optimal multi-robot path planning problems in a graph-based setting. DDM is mainly enabled through exploiting two innovative heuristics: path diversification and optimal sub-problem solution databases. The two heuristics attack two distinct phases of a decoupling-based planning planner: while path diversification allows more effective use of the entire workspace for robot travel, optimal sub-problem solution databases facilitate the fast resolution of local path conflicts.

Open-Source micro-Multi-Vehicle Platform

<We push the limit in planning collision-free motions for routing uniform labeled discs in two dimensions. First, from a theoretical perspective, we show that the constant-factor time-optimal routing of labeled discs can be achieved using a polynomial-time algorithm with robot density over 50% in the limit (i.e., over half of the workspace may be occupied by the discs). Second, from a more practical standpoint, we provide a high performance algorithm that computes near-optimal (e.g., 1.x) solutions under the same density setting.

Open-Source micro-Multi-Vehicle Platform

A Portable, 3D-Printing Enabled Multi-Vehicle Platform for Robotics Research and Education - Video highlight of our microMVP platform for all! See for more details or read more here.

Fast Near-Optimal Multi-Robot Path Planning in Continuous Domain

Near-Optimal Multi-Robot Path Planning in Continuous Domain - Video highlights accompanying our ISRR work. You may also [download the video].

Optimal Formation Reconfiguration

Optimal Reconfiguration of Multi-Robot Formations - In two (CDC'12, CDC'13) recent works, we developed efficient algorithm for the distance optimal reconfiguration of multi-robot formations. The video below demonstrates effectiveness of the algorithm. We note that the examples in the video take less than 0.1 second to solve when implemented in Java and running on a MacBook Air (2013). [download the video].

Rendezvous without Coordinates

Rendezvous Without Coordinates - This research establishes a sufficient condition for an arbitrary (known) number of Dubins-car vehicles to rendezvous in finite time. The sensing model of the vehicle is extremely coarse with only three quantized values. The feedback control law is similarly quantized with three total control input. In particular, the vehicles do not perform any state estimation, i.e., no coordinate data is needed. Our result generalizes to distributed systems without central coordination as well as in-homogeneous vehicles.
The video below demonstrates the sufficient condition for rendezvous, which depends solely on the sensor quantization (windshield size). We show two cases of rendezvous and two cases of divergence. Time evolutions of both the system and the Lyapunov certificate are shown. The simulation program is fully accessible here. [download the video].

Surveillance and Monitoring

Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines (ICRA 22) ●  Globally Optimal Coverage of 3D-Embedded Surfaces (ICRA 21) ●  Optimal Perimeter and Region Guarding with Range Sensors (RSS 20) ●  Optimal Perimeter Guarding w Heterogeneous Robots (RA-L 20) ●  Optimal Perimeter Guarding (RSS 19) ●  Back to Top

Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines

In this work, we carry out structural and algorithmic studies of a problem of barrier forming: selecting the minimum number of straight line segments (barriers) that separate several sets of mutually disjoint objects in the plane. The problem models the optimal placement of line sensors (e.g., infrared laser beams) for isolating many types of regions in a pair-wise manner for practical purposes (e.g., guarding against intrusions). The problem is NP-hard even if we want to find the minimum number of lines to separate two sets of points in the plane. Under the umbrella problem of barrier forming with minimum number of line segments, three settings are examined: barrier forming for point sets, point sets with polygonal obstacles, polygonal sets with polygonal obstacles. We describe methods for computing the optimal solution for the first two settings with the assistance of mathematical programming, and provide a 2-OPT solution for the third. We demonstrate the effectiveness of our methods through extensive simulations.

Globally Optimal Coverage of 3D-Embedded Surfaces

We carry out a structural and algorithmic study of a mobile sensor coverage optimization problem targeting 2D surfaces embedded in a 3D workspace. The investigated settings model multiple important applications including camera network deployment for surveillance, geological monitoring/survey of 3D terrains, and UVC-based surface disinfection for the prevention of the spread of disease agents (e.g., SARS-CoV2). Under a unified general “sensor coverage” problem, three concrete formulations are examined, focusing on optimizing visibility, single-best coverage quality, and cumulative quality, respectively. After demonstrating the computational intractability of all these formulations, we describe approximation schemes and mathematical programming models for near-optimally solving them. The effectiveness of our methods is thoroughly evaluated under realistic and practical scenarios.

Optimal Perimeter and Region Guarding with Range Sensors

We investigate the problem of using mobile robots equipped with 2D range sensors to optimally guard perimeters or regions. Given a bounded set in R^2 to be guarded, and k mobile sensors where the i-th sensor can cover a circular region with a variable radius ri, we seek the optimal strategy to deploy the k sensors to fully cover the set such that max ri is minimized. On the side of computational complexity, we show that computing a 1.152-optimal solution for guarding a perimeter or a region is NP-hard even when the set is a simple polygon or the boundary of a simple polygon, i.e., the problem is hard to approximate. The hardness result on perimeter guarding holds when each sensor may guard at most two disjoint perimeter segments. On the side of computational methods, for the guarding perimeters, we develop a fully polynomial time approximation scheme (FPTAS) for the special setting where each sensor may only guard a single continuous perimeter segment, suggesting that the aforementioned hard-to-approximate result on the two-disjoint-segment sensing model is tight. For the general problem, we first describe a polynomial-time (2 + ε)-approximation algorithm as an upper bound, applicable to both perimeter guarding and region guarding. This is followed by a high-performance integer linear programming (ILP) based method that computes near-optimal solutions. Thorough computational benchmarks as well as evaluation on potential application scenarios demonstrate the effectiveness of these algorithmic solutions.

Optimal Perimeter Guarding w Heterogeneous Robots

We perform structural and algorithmic studies of significantly generalized versions of the optimal perimeter guarding (OPG) problem [1]. As compared with the original OPG where robots are uniform, in this paper, many mobile robots with heterogeneous sensing capabilities are to be deployed to optimally guard a set of one-dimensional segments. Two complimentary formulations are investigated where one limits the number of available robots (OPGLR) and the other seeks to minimize the total deployment cost (OPGMC). In contrast to the original OPG which admits low-polynomial time solutions, both OPGLR and OPGMC are computationally intractable with OPGLR being strongly NP-hard. Nevertheless, we develop fairly scalable pseudo-polynomial time algorithms for practical, fixed-parameter subcase of OPGLR; we also develop pseudo-polynomial time algorithm for general OPGMC and polynomial time algorithm for the fixed-parameter OPGMC case. The applicability and effectiveness of selected algorithms are demonstrated through extensive numerical experiments.

Optimal Perimeter Guarding

We investigate the problem of optimally assigning a large number of robots (or other types of autonomous agents) to guard the perimeters of closed 2D regions, where the perimeter of each region to be guarded may contain multiple disjoint polygonal chains. Each robot is responsible for guarding a subset of a perimeter and any point on a perimeter must be guarded by some robot. In allocating the robots, the main objective is to minimize the maximum 1D distance to be covered by any robot along the boundary of the regions. For this optimization problem which we call optimal perimeter guarding (OPG), thorough structural analysis is performed, which is then exploited to develop fast exact algorithms that run in guaranteed low polynomial time. In addition to formal analysis and proofs, experimental evaluations and simulations are performed that further validate the correctness and effectiveness of our algorithmic results.

Industrial Collaboration: End-to-End Systems

Automated ML-Enabled Scrap Al-Cu Recycling ●  Tight Robot Packing in the Real World ●  Back to Top

Automated ML-Enabled Scrap Al-Cu Recycling

Computer Vision and Robotic System for Recycling Automation - We are working with a large recycling company to help it modernizing its product lines to increase levels of automation as an early prototype, we build a demo system for the separation of scrap metals based on color that is robust to lighting condition changes. The video shows a real-time demo of a run that separates pure copper pieces from mixed aluminum-copper pieces. We expect to report more exciting results as the project progresses.

Tight Robot Packing in the Real World

Many order fulfillment applications in logistics, such as packing, involve picking objects from unstructured piles before tightly arranging them in bins or shipping containers. Desirable robotic solutions in this space need to be lowcost, robust, easily deployable and simple to control. The current work proposes a complete pipeline for solving packing tasks for cuboid objects, given access only to RGB-D data and a single robot arm with a vacuum-based end-effector, which is also used as a pushing or dragging finger. The pipeline integrates perception for detecting the objects and planning so as to properly pick and place objects. The key challenges correspond to sensing noise and failures in execution, which appear at multiple steps of the process. To achieve robustness, three uncertainty-reducing manipulation primitives are proposed, which take advantage of the end-effector’s and the workspace’s compliance, to successfully and tightly pack multiple cuboid objects. The overall solution is demonstrated to be robust to execution and perception errors. The impact of each manipulation primitive is evaluated in extensive realworld experiments by considering different versions of the pipeline. Furthermore, an open-source simulation framework is provided for modeling such packing operations. Ablation studies are performed within this simulation environment to evaluate features of the proposed primitives.