Jingjin Yu

Litao Liu, Yifan Han, Pengfei Yi et al.

Task-conditioned manipulation requires grounding instructions to task-relevant functional parts rather than object categories. This setting is scene-dependent and often one-to-many in cluttered scenes: the same object may afford different interactions across tasks, while a single task may correspond to either one functional region or multiple valid functional regions, depending on the scene layout. Existing affordance datasets and benchmarks remain misaligned with this setting, as they typically focus on grasping or object-level affordances, rely on synthetic scenes, or assume a single instruction-region correspondence. We present Affordance2Action (A2A), a benchmark-centered learning framework for scene-level, task-conditioned part affordance grounding. At its core is A2A-Bench, a manipulation-oriented benchmark that covers both single-region and multi-region instruction correspondences in everyday scenes, with the latter highlighting the ambiguity and diversity of affordance grounding in realistic multi-object environments. To construct it at scale, we build A2A-AffordGen, an agent-assisted annotation pipeline that combines language-model filtering, interactive part segmentation, instance-level mask-out refinement, task-reasoning instruction generation, and human verification. A2A-Bench's supervision further supports diverse downstream applications, with real-time affordance grounding and affordance-conditioned manipulation policies as two representative examples. Experiments show that A2A exposes substantial gaps in generic segmentation, VLM-based grounding, and affordance distillation baselines, while improving task-level localization and providing useful spatial priors for downstream manipulation. All datasets and code will be publicly released to promote open research.

Rui Wang, Kai Gao, Jingjin Yu et al.

Object rearrangement is important for many applications but remains challenging, especially in confined spaces, such as shelves, where objects cannot be accessed from above and they block reachability to each other. Such constraints require many motion planning and collision checking calls, which are computationally expensive. In addition, the arrangement space grows exponentially with the number of objects. To address these issues, this work introduces a lazy evaluation framework with a local monotone solver and a global planner. Monotone instances are those that can be solved by moving each object at most once. A key insight is that reachability constraints at the grasps for objects' starts and goals can quickly reveal dependencies between objects without having to execute expensive motion planning queries. Given that, the local solver builds lazily a search tree that respects these reachability constraints without verifying that the arm paths are collision free. It only collision checks when a promising solution is found. If a monotone solution is not found, the non-monotone planner loads the lazy search tree and explores ways to move objects to intermediate locations from where monotone solutions to the goal can be found. Results show that the proposed framework can solve difficult instances in confined spaces with up to 16 objects, which state-of-the-art methods fail to solve. It also solves problems faster than alternatives, when the alternatives find a solution. It also achieves high-quality solutions, i.e., only 1.8 additional actions on average are needed for non-monotone instances.

Kai Gao, Zhaxizhuoma, Yan Ding et al.

Effectively performing object rearrangement is an essential skill for mobile manipulators, e.g., setting up a dinner table or organizing a desk. A key challenge in such problems is deciding an appropriate manipulation order for objects to effectively untangle dependencies between objects while considering the necessary motions for realizing the manipulations (e.g., pick and place). To our knowledge, computing time-optimal multi-object rearrangement solutions for mobile manipulators remains a largely untapped research direction. In this research, we propose ORLA*, which leverages delayed (lazy) evaluation in searching for a high-quality object pick and place sequence that considers both end-effector and mobile robot base travel. ORLA* also supports multi-layered rearrangement tasks considering pile stability using machine learning. Employing an optimal solver for finding temporary locations for displacing objects, ORLA* can achieve global optimality. Through extensive simulation and ablation study, we confirm the effectiveness of ORLA* delivering quality solutions for challenging rearrangement instances. Supplementary materials are available at: https://gaokai15.github.io/ORLA-Star/

Xiao Zang, Miao Yin, Lingyi Huang et al.

Neural network (NN)-based methods have emerged as an attractive approach for robot motion planning due to strong learning capabilities of NN models and their inherently high parallelism. Despite the current development in this direction, the efficient capture and processing of important sequential and spatial information, in a direct and simultaneous way, is still relatively under-explored. To overcome the challenge and unlock the potentials of neural networks for motion planning tasks, in this paper, we propose STP-Net, an end-to-end learning framework that can fully extract and leverage important spatio-temporal information to form an efficient neural motion planner. By interpreting the movement of the robot as a video clip, robot motion planning is transformed to a video prediction task that can be performed by STP-Net in both spatially and temporally efficient ways. Empirical evaluations across different seen and unseen environments show that, with nearly 100% accuracy (aka, success rate), STP-Net demonstrates very promising performance with respect to both planning speed and path cost. Compared with existing NN-based motion planners, STP-Net achieves at least 5x, 2.6x and 1.8x faster speed with lower path cost on 2D Random Forest, 2D Maze and 3D Random Forest environments, respectively. Furthermore, STP-Net can quickly and simultaneously compute multiple near-optimal paths in multi-robot motion planning tasks

Kai Gao, Jingjin Yu

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.

Teng Guo, Jingjin Yu

We introduce a robust framework, RGBTrack, for real-time 6D pose estimation and tracking that operates solely on RGB data, thereby eliminating the need for depth input for such dynamic and precise object pose tracking tasks. Building on the FoundationPose architecture, we devise a novel binary search strategy combined with a render-and-compare mechanism to efficiently infer depth and generate robust pose hypotheses from true-scale CAD models. To maintain stable tracking in dynamic scenarios, including rapid movements and occlusions, RGBTrack integrates state-of-the-art 2D object tracking (XMem) with a Kalman filter and a state machine for proactive object pose recovery. In addition, RGBTrack's scale recovery module dynamically adapts CAD models of unknown scale using an initial depth estimate, enabling seamless integration with modern generative reconstruction techniques. Extensive evaluations on benchmark datasets demonstrate that RGBTrack's novel depth-free approach achieves competitive accuracy and real-time performance, making it a promising practical solution candidate for application areas including robotics, augmented reality, and computer vision. The source code for our implementation will be made publicly available at https://github.com/GreatenAnoymous/RGBTrack.git.

Baichuan Huang, Teng Guo, Abdeslam Boularias et al.

In this study, working with the task of object retrieval in clutter, we have 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. Videos and supplementary material can be found at https://github.com/arc-l/more

Kai Gao, Darren Lau, Baichuan Huang et al.

In this paper, 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. source:github.com/arc-l/TRLB

Jingjin Yu

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. The implementation of the algorithms from the paper can be found at github.com/arc-l/lattice-rearrangement.

Baichuan Huang, Shuai D. Han, Jingjin Yu et al.

This paper considers 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 in simulation and using a real robot and objects 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. A video introducing VFT, with robot experiments, is accessible at https://youtu.be/7cL-hmgvyec. The full source code is available at https://github.com/arc-l/vft.

Baichuan Huang, Shuai D. Han, Abdeslam Boularias et al.

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. Videos, code, and experiments log are available at https://github.com/rutgers-arc-lab/dipn.

Rahul Shome, Wei N. Tang, Changkyu Song et al.

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 low-cost, 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 real-world 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.

Jingjin Yu, Shuai D Han, Wei N Tang et al.

microMVP is an affordable, portable, and open source micro-scale mobile robot platform designed for robotics research and education. As a complete and unique multi-vehicle platform enabled by 3D printing and the maker culture, microMVP can be easily reproduced and requires little maintenance: a set of six micro vehicles, each measuring $8\times 5\times 6$ cubic centimeters and weighing under $100$ grams, and the accompanying tracking platform can be fully assembled in under two hours, all from readily available components. In this paper, we describe microMVP's hardware and software architecture, and the design thoughts that go into the making of the platform. The capabilities of microMVP APIs are then demonstrated with several single- and multi-robot path and motion planning algorithms. microMVP supports all common operation systems.

Marcus Gozon, Jingjin Yu

In the $15$-puzzle game, $15$ labeled square tiles are reconfigured on a $4\times 4$ board through an escort, wherein each (time) step, a single tile neighboring it may slide into it, leaving the space previously occupied by the tile as the new escort. We study a generalized sliding-tile puzzle (GSTP) in which (1) there are $1+$ escorts and (2) multiple tiles can move synchronously in a single time step. Compared with popular discrete multi-agent/robot motion models, GSTP provides a more accurate model for a broad array of high-utility applications, including warehouse automation and autonomous garage parking, but is less studied due to the more involved tile interactions. In this work, we analyze optimal GSTP solution structures, establishing that computing makespan-optimal solutions for GSTP is NP-complete and developing polynomial time algorithms yielding makespans approximating the minimum with expected/high probability constant factors, assuming randomized start and goal configurations.

Teng Guo, Baichuan Huang, Jingjin Yu

Accurate 6D object pose estimation is a prerequisite for successfully completing robotic prehensile and non-prehensile manipulation tasks. At present, 6D pose estimation for robotic manipulation generally relies on depth sensors based on, e.g., structured light, time-of-flight, and stereo-vision, which can be expensive, produce noisy output (as compared with RGB cameras), and fail to handle transparent objects. On the other hand, state-of-the-art monocular depth estimation models (MDEMs) provide only affine-invariant depths up to an unknown scale and shift. Metric MDEMs achieve some successful zero-shot results on public datasets, but fail to generalize. We propose a novel framework, Monocular One-shot Metric-depth Alignment (MOMA), to recover metric depth from a single RGB image, through a one-shot adaptation building on MDEM techniques. MOMA performs scale-rotation-shift alignments during camera calibration, guided by sparse ground-truth depth points, enabling accurate depth estimation without additional data collection or model retraining on the testing setup. MOMA supports fine-tuning the MDEM on transparent objects, demonstrating strong generalization capabilities. Real-world experiments on tabletop 2-finger grasping and suction-based bin-picking applications show MOMA achieves high success rates in diverse tasks, confirming its effectiveness.

Marcus Gozon, Jingjin Yu

The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game.

Ewerton R. Vieira, Daniel Nakhimovich, Kai Gao et al.

This work explores the use of topological tools for achieving effective non-prehensile manipulation in cluttered, constrained workspaces. In particular, it proposes the use of persistent homology as a guiding principle in identifying the appropriate non-prehensile actions, such as pushing, to clean a cluttered space with a robotic arm so as to allow the retrieval of a target object. Persistent homology enables the automatic identification of connected components of blocking objects in the space without the need for manual input or tuning of parameters. The proposed algorithm uses this information to push groups of cylindrical objects together and aims to minimize the number of pushing actions needed to reach to the target. Simulated experiments in a physics engine using a model of the Baxter robot show that the proposed topology-driven solution is achieving significantly higher success rate in solving such constrained problems relatively to state-of-the-art alternatives from the literature. It manages to keep the number of pushing actions low, is computationally efficient and the resulting decisions and motion appear natural for effectively solving such tasks.

Yuhan Zhao, Baichuan Huang, Jingjin Yu et al.

In this study, we explore the application of game theory, in particular Stackelberg games, to address the issue of effective coordination strategy generation for heterogeneous robots with one-way communication. To that end, focusing on the task of multi-object rearrangement, we develop a theoretical and algorithmic framework that provides strategic guidance for a pair of robot arms, a leader and a follower where the leader has a model of the follower's decision-making process, through the computation of a feedback Stackelberg equilibrium. With built-in tolerance of model uncertainty, the strategic guidance generated by our planning algorithm not only improves the overall efficiency in solving the rearrangement tasks, but is also robust to common pitfalls in collaboration, e.g., chattering.

Teng Guo, Jingjin Yu

Graph-based multi-robot path planning (MRPP) is NP-hard to optimally solve. In this work, we propose the first low polynomial-time algorithm for MRPP achieving 1--1.5 asymptotic optimality guarantees on makespan for random instances under very high robot density, with high probability. The dual guarantee on computational efficiency and solution optimality suggests our proposed general method is promising in significantly scaling up multi-robot applications for logistics, e.g., at large robotic warehouses. Specifically, on an $m_1\times m_2$ gird, $m_1 \ge m_2$, our RTH (Rubik Table with Highways) algorithm computes solutions for routing up to $\frac{m_1m_2}{3}$ robots with uniformly randomly distributed start and goal configurations with a makespan of $m_1 + 2m_2 + o(m_1)$, with high probability. Because the minimum makespan for such instances is $m_1 + m_2 - o(m_1)$, also with high probability, RTH guarantees $\frac{m_1+2m_2}{m_1+m_2}$ optimality as $m_1 \to \infty$ for random instances with up to $\frac{1}{3}$ robot density, with high probability. $\frac{m_1+2m_2}{m_1+m_2} \in (1, 1.5]$. Alongside this key result, we also establish a series of related results supporting even higher robot densities and environments with regularly distributed obstacles, which directly map to real-world parcel sorting scenarios. Building on the baseline methods with provable guarantees, we have developed effective, principled heuristics that further improve the computed optimality of the RTH algorithms. In extensive numerical evaluations, RTH and its variants demonstrate exceptional scalability as compared with methods including ECBS and DDM, scaling to over $450 \times 300$ grids with $45,000$ robots, and consistently achieves makespan around $1.5$ optimal or better, as predicted by our theoretical analysis.

Si Wei Feng, Jingjin Yu

In this work, we carry out structural and algorithmic studies of a problem of barrier forming: selecting theminimum 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.

Shuai D. Han, Jingjin Yu

We perform a systematic exploration of the principle of Space Utilization Optimization (SUO) as a heuristic for planning better individual paths in a decoupled multi-robot path planner, with applications to both one-shot and life-long multi-robot path planning problems. We show that the decentralized heuristic set, SU-I, preserves single path optimality and significantly reduces congestion that naturally happens when many paths are planned without coordination. Integration of SU-I into complete planners brings dramatic reductions in computation time due to the significantly reduced number of conflicts and leads to sizable solution optimality gains in diverse evaluation scenarios with medium and large maps, for both one-shot and life-long problem settings.

Kai Gao, Jingjin Yu

We investigate the capacitated vehicle routing problem (CVRP) under a robotics context, where a vehicle with limited payload must complete delivery (or pickup) tasks to serve a set of geographically distributed customers with varying demands. In classical CVRP, a customer location is modeled as a point. In many robotics applications, however, it is more appropriate to model such "customer locations" as 2D regions. For example, in aerial delivery, a drone may drop a package anywhere in a customer's lot. This yields the problem of CVRG (Capacitated Vehicle Routing with Target Geometric Constraints). Computationally, CVRP is already strongly NP-hard; CVRG is therefore more challenging. Nevertheless, we develop fast algorithms for CVRG, capable of computing high quality solutions for hundreds of regions. Our algorithmic solution is guaranteed to be optimal when customer regions are convex. Numerical evaluations show that our proposed methods significantly outperform greedy best-first approaches. Comprehensive simulation studies confirm the effectiveness of our methods.

Kai Gao, Si Wei Feng, Jingjin Yu

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.

Teng Guo, Shuai D. Han, Jingjin Yu

In this work, we systematically examine the application of spatio-temporal splitting heuristics to the Multi-Robot Motion Planning (MRMP) problem in a graph-theoretic setting: a problem known to be NP-hard to optimally solve. Following the divide-and-conquer principle, we design multiple spatial and temporal splitting schemes that can be applied to any existing MRMP algorithm, including integer programming solvers and Enhanced Conflict Based Search, in an orthogonal manner. The combination of a good baseline MRMP algorithm with a proper splitting heuristic proves highly effective, allowing the resolution of problems 10+ times than what is possible previously, as corroborated by extensive numerical evaluations. Notably, spatial partition of problem fusing with the temporal splitting heuristic and the enhanced conflict based search (ECBS) algorithm increases the scalability of ECBS on large and challenging DAO maps by 5--15 folds with negligible impact on solution optimality.

Si Wei Feng, Kai Gao, Jie Gong et al.

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-CoV-2). 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.

Rui Wang, Kai Gao, Daniel Nakhimovich et al.

Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a "region graph", which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFSDP performs a recursive depth first search to solve monotone problems quickly, i.e., those instances that do not require objects to be moved first to an intermediate buffer. DFSDP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.

Wei N. Tang, Shuai D. Han, Jingjin Yu

We investigate the task and motion planning problem of clearing clutter from a workspace with limited ingress/egress access for multiple robots. We call the problem multi-robot clutter removal (MRCR). Targeting practical applications where motion planning is non-trivial but is not a bottleneck, we focus on finding high-quality solutions for feasible MRCR instances, which depends on the ability to efficiently compute high-quality object removal sequences. Despite the challenging multi-robot setting, our proposed search algorithms based on A*, dynamic programming, and best-first heuristics all produce solutions for tens of objects that significantly outperform single robot solutions. Realistic simulations with multiple Kuka youBots further confirms the effectiveness of our algorithmic solutions. In contrast, we also show that deciding the optimal object removal sequence for MRCR is computationally intractable.

Si Wei Feng, Jingjin Yu

We investigate the problem of using mobile robots equipped with 2D range sensors to optimally guard perimeters or regions, i.e., 1D or 2D sets. Given such a set of arbitrary shape to be guarded, and $k$ mobile sensors where the $i$-th sensor can guard a circular region with a variable radius $r_i$, we seek the optimal strategy to deploy the $k$ sensors to fully cover the set such that $\max r_i$ 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, 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.

Mario Szegedy, Jingjin Yu

A great number of robotics applications demand the rearrangement of many mobile objects, e.g., organizing products on shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations, e.g., the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to complex inter-dependency between objects, especially in high-density settings. In tackling the aforementioned challenges, we develop a novel algorithmic tool, Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an $n\times n$ table containing $n^2$ items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most $2n$ column/row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional $n$ shuffles are needed. Rubik Tables allow many generalizations, e.g., to higher dimensions. Using Rubik Table, we have designed a first constant-factor optimal algorithm for stack rearrangement problems. We show that, for $nd$ items stored in $n$ stacks of depth $d$ each, using one empty stack as the swap space, $O(nd)$ stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where $d \le n^{\frac{m}{2}}$ for arbitrary fixed $m >0$. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.

Shuai D. Han, Si Wei Feng, Jingjin Yu

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.

Si Wei Feng, Jingjin Yu

We perform structural and algorithmic studies of significantly generalized versions of the optimal perimeter guarding (OPG) problem. 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 (OPG_LR) and the other seeks to minimize the total deployment cost (OPG_MC). In contrast to the original OPG which admits low-polynomial time solutions, both OPG_LR and OPG_MC are computationally intractable with OPG_LR being strongly NP-hard. Nevertheless, we develop fairly scalable pseudo-polynomial time algorithms for practical, fixed-parameter subcase of OPG_LR; we also develop pseudo-polynomial time algorithm for general OPG_MC and polynomial time algorithm for the fixed-parameter OPG_MC case. The applicability and effectiveness of selected algorithms are demonstrated through extensive numerical experiments.

Wei N. Tang, Jingjin Yu

We examine an important combinatorial challenge in clearing clutter using a mobile robot equipped with a manipulator, seeking to compute an optimal object removal sequence for minimizing the task completion time, assuming that each object is grasped once and then subsequently removed. On the structural side, we establish that such an optimal sequence can be NP-hard to compute, even when no two objects to be removed have any overlap. Then, we construct asymptotically optimal and heuristic algorithms for clutter removal. Employing dynamic programming, our optimal algorithm scales to 40 objects. On the other hand, for random clutter, fast greedy algorithms tend to produce solutions comparable to these generated by the optimal algorithm.

Si Wei Feng, Shuai D. Han, Kai Gao et al.

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.

Shuai D. Han, Jingjin Yu

We propose a novel centralized and decoupled algorithm, DDM, for solving multi-robot path planning problems in grid graphs, targeting on-demand and automated warehouse-like settings. Two settings are studied: a traditional one whose objective is to move a set of robots from their respective initial vertices to the goal vertices as quickly as possible, and a dynamic one which requires frequent re-planning to accommodate for goal configuration adjustments. Among other techniques, 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 planner: while path diversification allows the more effective use of the entire workspace for robot travel, optimal sub-problem solution databases facilitate the fast resolution of local path conflicts. Extensive evaluation demonstrates that DDM achieves high levels of scalability and high levels of solution optimality.

Shuai D. Han, Jingjin Yu

Integer programming (IP) has proven to be highly effective in solving many path-based optimization problems in robotics. However, the applications of IP are generally done in an ad-hoc, problem specific manner. In this work, after examined a wide range of path-based optimization problems, we describe an IP solution methodology for these problems that is both easy to apply (in two simple steps) and high-performance in terms of the computation time and the achieved optimality. We demonstrate the generality of our approach through the application to three challenging path-based optimization problems: multi-robot path planning (MPP), minimum constraint removal (MCR), and reward collection problems RCPs). Associated experiments show that the approach can efficiently produce (near-)optimal solutions for problems with large state spaces, complex constraints, and complicated objective functions. In conjunction with the proposition of the IP methodology, we introduce two new and practical robotics problems: multi-robot minimum constraint removal (MMCR) and multi-robot path planning (MPP) with partial solutions, which can be quickly and effectively solved using our proposed IP solution pipeline.

Rahul Shome, Kiril Solovey, Jingjin Yu et al.

Rearranging objects on a planar surface arises in a variety of robotic applications, such as product packaging. Using two arms can improve efficiency but introduces new computational challenges. This paper studies the structure of dual-arm rearrangement for synchronous, monotone tabletop setups and develops an optimal mixed integer model. It then describes an efficient and scalable algorithm, which first minimizes the cost of object transfers and then of moves between objects. This is motivated by the fact that, asymptotically, object transfers dominate the cost of solutions. Moreover, a lazy strategy minimizes the number of motion planning calls and results in significant speedups. Theoretical arguments support the benefits of using two arms and indicate that synchronous execution, in which the two arms perform together either transfers or moves, introduces only a small overhead. Experiments support these points and show that the scalable method can quickly compute solutions close to the optimal for the considered setup.

Rupesh Chinta, Shuai D. Han, Jingjin Yu

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.

Jingjin Yu

Let $G = (V, E)$ be an $m_1 \times \ldots \times m_k$ grid. Assuming that each $v \in V$ is occupied by a robot and a robot may move to a neighboring vertex in a step via synchronized rotations along cycles of $G$, we first establish that the arbitrary reconfiguration of labeled robots on $G$ can be performed in $O(k\sum_i m_i)$ makespan and requires $O(|V|^2)$ running time in the worst case and $o(|V|^2)$ when $G$ is non-degenerate (in the current context, a grid is degenerate if it is nearly one dimensional). The resulting algorithm, iSAG, provides average case $O(1)$-approximate (i.e., constant-factor) time optimality guarantee. When all dimensions are of similar size $O(|V|^{\frac{1}{k}})$, the running time of iSAG approaches a linear $O(|V|)$. Define $d_g(p)$ as the largest distance between individual initial and goal configurations over all robots for a given problem instance $p$, building on iSAG, we develop the PartitionAndFlow (PAF) algorithm that computes $O(d_g(p))$ makespan solutions for arbitrary fixed $k \ge 2$, using mostly $o(|V|^2)$ running time. PAF provides worst case $O(1)$-approximation regarding solution time optimality. We note that the worst case running time for the problem is $Ω(|V|^2)$.

Shuai D Han, Nicholas M Stiffler, Athanasios Krontiris et al.

This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the travel distance of the end-effector. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard in both cases. This is shown through reductions from well-understood, hard combinatorial challenges to these rearrangement problems. The reductions are also shown to hold in the reverse direction, which enables the convenient application on rearrangement of well studied algorithms. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation, including hardware-based trials, shows that the proposed pipeline computes high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setup.

Shuai D. Han, Edgar J. Rodriguez, Jingjin Yu

We study the labeled multi-robot path planning problem in continuous 2D and 3D domains in the absence of obstacles where robots must not collide with each other. For an arbitrary number of robots in arbitrary initial and goal arrangements, we derive a polynomial time, complete algorithm that produces solutions with constant-factor optimality guarantees on both makespan and distance optimality, in expectation, under the assumption that the robot labels are uniformly randomly distributed. Our algorithm only requires a small constant factor expansion of the initial and goal configuration footprints for solving the problem, i.e., the problem can be solved in a fairly small bounded region. Beside theoretical guarantees, we present a thorough computational evaluation of the proposed solution. In addition to the baseline implementation, adapting an effective (but non-polynomial time) routing subroutine, we also provide a highly efficient implementation that quickly computes near-optimal solutions. Hardware experiments on the microMVP platform composed of non-holonomic robots confirms the practical applicability of our algorithmic pipeline.

Shuai D. Han, Nicholas M. Stiffler, Kostas E. Bekris et al.

This work studies rearrangement problems involving the sorting of robots or objects in stack-like containers, which can be accessed only from one side. Two scenarios are considered: one where every robot or object needs to reach a particular stack, and a setting in which each robot has a distinct position within a stack. In both cases, the goal is to minimize the number of stack removals that need to be performed. Stack rearrangement is shown to be intimately connected to pebble motion problems, a useful abstraction in multi-robot path planning. Through this connection, feasibility of stack rearrangement can be readily addressed. The paper continues to establish lower and upper bounds on optimality, which differ only by a logarithmic factor, in terms of stack removals. An algorithmic solution is then developed that produces suboptimal paths much quicker than a pebble motion solver. Furthermore, informed search-based methods are proposed for finding high-quality solutions. The efficiency and desirable scalability of the methods is demonstrated in simulation.

Jingjin Yu

Fast algorithms for optimal multi-robot path planning are sought after in real-world applications. Known methods, however, generally do not simultaneously guarantee good solution optimality and good (e.g., polynomial) running time. In this work, we develop a first low-polynomial running time algorithm, called SplitAngGroup (SaG), that solves the multi-robot path planning problem on grids and grid-like environments, and produces constant factor makespan optimal solutions on average over all problem instances. That is, SaG is an average case O(1)-approximation algorithm and computes solutions with sub-linear makespan. SaG is capable of handling cases when the density of robots is extremely high - in a graph-theoretic setting, the algorithm supports cases where all vertices of the underlying graph are occupied. SaG attains its desirable properties through a careful combination of a novel divide-and-conquer technique, which we denote as global decoupling, and network flow based methods for routing the robots. Solutions from SaG, in a weaker sense, are also a constant factor approximation on total distance optimality.

Shuai D. Han, Nicholas M. Stiffler, Athansios Krontiris et al.

This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, similar-geometry objects placed on a flat, horizontal surface, where a robot can approach them from above and perform pick-and-place operations to rearrange them. The paper considers both the case where the start and goal object poses overlap, and where they do not. For overlapping poses, the primary objective is to minimize the number of pick-and-place actions and then to minimize the distance traveled by the end-effector. For the non-overlapping case, the objective is solely to minimize the end-effector distance. While such problems do not involve all the complexities of general rearrangement, they remain computationally hard challenges in both cases. This is shown through two-way reductions between well-understood, hard combinatorial challenges and these rearrangement problems. The benefit of the reduction is that there are well studied algorithms for solving these well-established combinatorial challenges. These algorithms can be very efficient in practice despite the hardness results. The paper builds on these reduction results to propose an algorithmic pipeline for dealing with the rearrangement problems. Experimental evaluation shows that the proposed pipeline achieves high-quality paths with regards to the optimization objectives. Furthermore, it exhibits highly desirable scalability as the number of objects increases in both the overlapping and non-overlapping setups.

Jingjin Yu, Steven M. LaValle

We study the problem of optimal multi-robot path planning on graphs MPP over four distinct minimization objectives: the makespan (last arrival time), the maximum (single-robot traveled) distance, the total arrival time, and the total distance. In a related paper, we show that these objectives are distinct and NP-hard to optimize. In this work, we focus on efficiently algorithmic solutions for solving these optimal MPP problems. Toward this goal, we first establish a one-to-one solution mapping between MPP and network-flow. Based on this equivalence and integer linear programming (ILP), we design novel and complete algorithms for optimizing over each of the four objectives. In particular, our exact algorithm for computing optimal makespan solutions is a first such that is capable of solving extremely challenging problems with robot-vertex ratio as high as 100%. Then, we further improve the computational performance of these exact algorithms through the introduction of principled heuristics, at the expense of some optimality loss. The combination of ILP model based algorithms and the heuristics proves to be highly effective, allowing the computation of 1.x-optimal solutions for problems containing hundreds of robots, densely populated in the environment, often in just seconds.

Jingjin Yu, Steven M. LaValle

We study the problem of optimal multi-robot path planning on graphs (MPP) over four distinct minimization objectives: the total arrival time, the makespan (last arrival time), the total distance, and the maximum (single-robot traveled) distance. On the structure side, we show that each pair of these four objectives induces a Pareto front and cannot always be optimized simultaneously. Then, through reductions from 3-SAT, we further establish that computation over each objective is an NP-hard task, providing evidence that solving MPP optimally is generally intractable. Nevertheless, in a related paper, we design complete algorithms and efficient heuristics for optimizing all four objectives, capable of solving MPP optimally or near-optimally for hundreds of robots in challenging setups.

Jingjin Yu, Daniela Rus

We present a centralized algorithmic framework for solving multi-robot path planning problems in general, two-dimensional, continuous environments while minimizing globally the task completion time. The framework obtains high levels of effectiveness through the composition of an optimal discretization of the continuous environment and the subsequent fast, near-optimal resolution of the resulting discrete planning problem. This principled approach achieves orders of magnitudes better performance with respect to both speed and the supported robot density. For a wide variety of environments, our method is shown to compute globally near-optimal solutions for fifty robots in seconds with robots packed close to each other. In the extreme, the method can consistently solve problems with hundreds of robots that occupy over 30% of the free space.

Kiril Solovey, Jingjin Yu, Or Zamir et al.

We study the problem of path planning for unlabeled (indistinguishable) unit-disc robots in a planar environment cluttered with polygonal obstacles. We introduce an algorithm which minimizes the total path length, i.e., the sum of lengths of the individual paths. Our algorithm is guaranteed to find a solution if one exists, or report that none exists otherwise. It runs in time $\tilde{O}(m^4+m^2n^2)$, where $m$ is the number of robots and $n$ is the total complexity of the workspace. Moreover, the total length of the returned solution is at most $\text{OPT}+4m$, where OPT is the optimal solution cost. To the best of our knowledge this is the first algorithm for the problem that has such guarantees. The algorithm has been implemented in an exact manner and we present experimental results that attest to its efficiency.

Jingjin Yu

We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.

Jingjin Yu, Javed Aslam, Sertac Karaman et al.

We introduce and study the problem in which a mobile sensing robot (our tourist) is tasked to travel among and gather intelligence at a set of spatially distributed point-of-interests (POIs). The quality of the information collected at each POI is characterized by some non-decreasing reward function over the time spent at the POI. With limited time budget, the robot must balance between spending time traveling to POIs and spending time at POIs for information collection (sensing) so as to maximize the total reward. Alternatively, the robot may be required to acquire a minimum mount of reward and hopes to do so with the least amount of time. We propose a mixed integer programming (MIP) based anytime algorithm for solving these two NP-hard optimization problems to arbitrary precision. The effectiveness of our algorithm is demonstrated using an extensive set of computational experiments including the planning of a realistic itinerary for a first-time tourist in Istanbul.

Jingjin Yu, Mac Schwager, Daniela Rus

We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to model the planning of informative tours for the persistent monitoring of a spatiotemporal field with time-invariant spatial correlations, in which the tours are constrained to have limited length. Our focus in this paper is QCOP a quadratic COP formulation that only looks at correlations between neighboring nodes in a node network. The main feature of QCOP is a quadratic utility function capturing the said spatial correlation. QCOP may be solved using mixed integer quadratic programming (MIQP), with the resulting anytime algorithm capable of planning multiple disjoint tours that maximize the quadratic utility. In particular, our algorithm can quickly plan a near-optimal tour over a network with up to $150$ nodes. Besides performing extensive simulation studies to verify the algorithm's correctness and characterize its performance, we also successfully applied it to two realistic persistent monitoring tasks: (i) estimation over a synthetic spatiotemporal field, and (ii) estimating the temperature distribution in the state of Massachusetts.