Publications (85)
Effective and Robust Non-Prehensile Manipulation via Persistent Homology Guided Monte-Carlo Tree Search
Ewerton R. Vieira, Kai Gao, Daniel Nakhimovich +2
Performing object retrieval in real-world workspaces must tackle challenges including \emph{uncertainty} and \emph{clutter}. One option is to apply prehensile operations, which can…
Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies
Jingjin Yu, Soon-Jo Chung, Petros G. Voulgaris
We study the problem of multi-robot target assignment to minimize the total distance traveled by the robots until they all reach an equal number of static targets. In the first hal…
Optimal Perimeter Guarding with Heterogeneous Robot Teams: Complexity Analysis and Effective Algorithms
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…
Rearrangement on Lattices with Pick-n-Swaps: Optimality Structures and Efficient Algorithms
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 swap…
Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds
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 nei…
Well-Connected Set and Its Application to Multi-Robot Path Planning
Teng Guo, Jingjin Yu
Parking lots and autonomous warehouses for accommodating many vehicles/robots adopt designs in which the underlying graphs are \emph{well-connected} to simplify planning and reduce…
Budgeted Steiner Networks: Three Terminals with Equal Path Weights
Mario Szegedy, Jingjin Yu
Given a set of terminals in 2D/3D, the network with the shortest total length that connects all terminals is a Steiner tree. On the other hand, with enough budget, every terminal c…
Fast High-Quality Tabletop Rearrangement in Bounded Workspace
Kai Gao, Darren Lau, Baichuan Huang +2
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 c…
High-Quality Tabletop Rearrangement with Overhand Grasps: Hardness Results and Fast Methods
Shuai D. Han, Nicholas M. Stiffler, Athansios Krontiris +2
This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, simil…
On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles
Marcus Gozon, Jingjin Yu
In the -puzzle game, labeled square tiles are reconfigured on a board through an escort, wherein each (time) step, a single tile neighboring it may slide into…
Efficient Heuristics for Multi-Robot Path Planning in Crowded Environments
Teng Guo, Jingjin Yu
Optimal Multi-Robot Path Planning (MRPP) has garnered significant attention due to its many applications in domains including warehouse automation, transportation, and swarm roboti…
An Effective Algorithmic Framework for Near Optimal Multi-Robot Path Planning
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 tas…
PROBE: Proprioceptive Obstacle Detection and Estimation while Navigating in Clutter
Dhruv Metha Ramesh, Aravind Sivaramakrishnan, Shreesh Keskar +3
In critical applications, including search-and-rescue in degraded environments, blockages can be prevalent and prevent the effective deployment of certain sensing modalities, parti…
EARL: Eye-on-Hand Reinforcement Learner for Dynamic Grasping with Active Pose Estimation
Baichuan Huang, Jingjin Yu, Siddarth Jain
In this paper, we explore the dynamic grasping of moving objects through active pose tracking and reinforcement learning for hand-eye coordination systems. Most existing vision-bas…
Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination
Teng Guo, Siwei Feng, Jingjin Yu
For enabling efficient, large-scale coordination of unmanned aerial vehicles (UAVs) under the labeled setting, in this work, we develop the first polynomial time algorithm for the…
Intractability of Optimal Multi-Robot Path Planning on Planar Graphs
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 th…
A Linear Time Algorithm for the Feasibility of Pebble Motion on Graphs
Jingjin Yu
Given a connected, undirected, simple graph and pebbles labeled , a configuration of these pebbles is an injective map assigning the pebbles…
Uniform Object Rearrangement: From Complete Monotone Primitives to Efficient Non-Monotone Informed Search
Rui Wang, Kai Gao, Daniel Nakhimovich +2
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…
Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines
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 severa…
DIPN: Deep Interaction Prediction Network with Application to Clutter Removal
Baichuan Huang, Shuai D. Han, Abdeslam Boularias +1
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 prop…
Toward Efficient Task Planning for Dual-Arm Tabletop Object Rearrangement
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-obje…
Effectively Rearranging Heterogeneous Objects on Cluttered Tabletops
Kai Gao, Justin Yu, Tanay Sandeep Punjabi +1
Effectively rearranging heterogeneous objects constitutes a high-utility skill that an intelligent robot should master. Whereas significant work has been devoted to the grasp synth…
Multi-agent Path Planning and Network Flow
Jingjin Yu, Steven M. LaValle
This paper connects multi-agent path planning on graphs (roadmaps) to network flow problems, showing that the former can be reduced to the latter, therefore enabling the applicatio…
RGBTrack: Fast, Robust Depth-Free 6D Pose Estimation and Tracking
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 dyn…
Efficient Algorithms for Optimal Perimeter Guarding
Si Wei Feng, Shuai D. Han, Kai Gao +1
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 o…
Optimizing Space Utilization for More Effective Multi-Robot Path Planning
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 pla…
Computing High-Quality Clutter Removal Solutions for Multiple Robots
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 clu…
Efficient, High-Quality Stack Rearrangement
Shuai D. Han, Nicholas M. Stiffler, Kostas E. Bekris +1
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…
Efficient Algorithms for Boundary Defense with Heterogeneous Defenders
Si Wei Feng, Jingjin Yu
This paper studies the problem of defending (1D and 2D) boundaries against a large number of continuous attacks with a heterogeneous group of defenders. The defender team has perfe…
Bin Assignment and Decentralized Path Planning for Multi-Robot Parcel Sorting
Teng Guo, Jingjin Yu
At modern warehouses, mobile robots transport packages and drop them into collection bins/chutes based on shipping destinations grouped by, e.g., the ZIP code. System throughput, m…
Persistent Homology for Effective Non-Prehensile Manipulation
Ewerton R. Vieira, Daniel Nakhimovich, Kai Gao +3
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 pers…
Affordance2Action: Task-Conditioned Scene-level Affordance Grounding for Real-Time Manipulation
Litao Liu, Yifan Han, Pengfei Yi +9
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…
Minimizing Running Buffers for Tabletop Object Rearrangement: Complexity, Fast Algorithms, and Applications
Kai Gao, Si Wei Feng, Baichuan Huang +1
For rearranging objects on tabletops with overhand grasps, temporarily relocating objects to some buffer space may be necessary. This raises the natural question of how many simult…
Stackelberg Strategic Guidance for Heterogeneous Robots Collaboration
Yuhan Zhao, Baichuan Huang, Jingjin Yu +1
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 robo…
Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity
William Zhang, Tzvika Geft, Jingjin Yu +1
Automated warehouses face a fundamental trade-off between maximizing storage density and achieving high retrieval throughput. While puzzle-based storage (PBS) architectures increas…
KARL: Kalman-Filter Assisted Reinforcement Learner for Dynamic Object Tracking and Grasping
Kowndinya Boyalakuntla, Abdeslam Boularias, Jingjin Yu
We present Kalman-filter Assisted Reinforcement Learner (KARL) for dynamic object tracking and grasping over eye-on-hand (EoH) systems, significantly expanding such systems capabil…
Parallel Monte Carlo Tree Search with Batched Rigid-body Simulations for Speeding up Long-Horizon Episodic Robot Planning
Baichuan Huang, Abdeslam Boularias, Jingjin Yu
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 searc…
A Portable, 3D-Printing Enabled Multi-Vehicle Platform for Robotics Research and Education
Jingjin Yu, Shuai D Han, Wei N Tang +1
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…
Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms
Jingjin Yu, Daniela Rus
We study the problem of planning paths for distinguishable pebbles (robots) residing on the vertices of an -vertex connected graph with . A pebble may move from a v…
Toward Holistic Planning and Control Optimization for Dual-Arm Rearrangement
Kai Gao, Zihe Ye, Duo Zhang +2
Long-horizon task and motion planning (TAMP) is notoriously difficult to solve, let alone optimally, due to the tight coupling between the interleaved (discrete) task and (continuo…
Sensor Placement for Globally Optimal Coverage of 3D-Embedded Surfaces
Si Wei Feng, Kai Gao, Jie Gong +1
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 m…
On Minimizing the Number of Running Buffers for Tabletop Rearrangement
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 resol…
Visual Foresight Trees for Object Retrieval from Clutter with Nonprehensile Rearrangement
Baichuan Huang, Shuai D. Han, Jingjin Yu +1
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 clu…
Expected -Makespan-Optimal MAPF on Grids in Low-Poly Time
Teng Guo, Jingjin Yu
Multi-Agent Path Finding (MAPF) is NP-hard to solve optimally, even on graphs, suggesting no polynomial-time algorithms can compute exact optimal solutions for them. This raises a…
On the Utility of Buffers in Pick-n-Swap Based Lattice Rearrangement
Kai Gao, Jingjin Yu
We investigate the utility of employing multiple buffers in solving a class of rearrangement problems with pick-n-swap manipulation primitives. In this problem, objects stored rand…
Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee
Jingjin Yu, Steven M. LaValle
For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast di…
Lazy Rearrangement Planning in Confined Spaces
Rui Wang, Kai Gao, Jingjin Yu +1
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 the…
Robot Motion Planning as Video Prediction: A Spatio-Temporal Neural Network-based Motion Planner
Xiao Zang, Miao Yin, Lingyi Huang +3
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 parall…
Fully Packed and Ready to Go: High-Density, Rearrangement-Free, Grid-Based Storage and Retrieval
Tzvika Geft, Kostas Bekris, Jingjin Yu
Grid-based storage systems with uniformly shaped loads (e.g., containers, pallets, totes) are commonplace in logistics, industrial, and transportation domains. A key performance me…
Toward Fast and Optimal Robotic Pick-and-Place on a Moving Conveyor
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 t…
Tight Robot Packing in the Real World: A Complete Manipulation Pipeline with Robust Primitives
Rahul Shome, Wei N. Tang, Changkyu Song +5
Many order fulfillment applications in logistics, such as packing, involve picking objects from unstructured piles before tightly arranging them in bins or shipping containers. Des…
Integer Programming as a General Solution Methodology for Path-Based Optimization in Robotics: Principles, Best Practices, and Applications
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…
Motion Planning for Unlabeled Discs with Optimality Guarantees
Kiril Solovey, Jingjin Yu, Or Zamir +1
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…
Decentralized Lifelong Path Planning for Multiple Ackerman Car-Like Robots
Teng Guo, Jingjin Yu
Path planning for multiple non-holonomic robots in continuous domains constitutes a difficult robotics challenge with many applications. Despite significant recent progress on the…
Robust Out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity
Tzvika Geft, William Zhang, Jingjin Yu +1
This paper proposes a framework for improving the operational efficiency of automated storage systems under uncertainty. It considers a 2D grid-based storage for uniform-sized load…
Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning
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 pr…
DDM: Fast Near-Optimal Multi-Robot Path Planning using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics
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 setting…
Asymptotically-Optimal Multi-Query Path Planning for a Polygonal Robot
Duo Zhang, Zihe Ye, Jingjin Yu
Shortest-path roadmaps, also known as reduced visibility graphs, provides a highly efficient multi-query method for computing optimal paths in two-dimensional environments. Combine…
Planning Optimal Paths for Multiple Robots on Graphs
Jingjin Yu, Steven M. LaValle
In this paper, we study the problem of optimal multi-robot path planning (MPP) on graphs. We propose two multiflow based integer linear programming (ILP) models that computes minim…
Monocular One-Shot Metric-Depth Alignment for RGB-Based Robot Grasping
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 roboti…
Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time
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 op…
Interleaving Monte Carlo Tree Search and Self-Supervised Learning for Object Retrieval in Clutter
Baichuan Huang, Teng Guo, Abdeslam Boularias +1
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…
Correlated Orienteering Problem and it Application to Persistent Monitoring Tasks
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 fo…
Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density
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 ti…
High-Performance Dual-Arm Task and Motion Planning for Tabletop Rearrangement
Duo Zhang, Junshan Huang, Jingjin Yu
We propose Synchronous Dual-Arm Rearrangement Planner (SDAR), a task and motion planning (TAMP) framework for tabletop rearrangement, where two robot arms equipped with 2-finger gr…
Optimal Multi-Robot Path Planning on Graphs: Structure and Computational Complexity
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…
Average Case Constant Factor Time and Distance Optimal Multi-Robot Path Planning in Well-Connected Environments
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 o…
Optimal Tourist Problem and Anytime Planning of Trip Itineraries
Jingjin Yu, Javed Aslam, Sertac Karaman +1
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-intere…
SEAR: A Polynomial-Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee
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 n…
Complexity Results and Fast Methods for Optimal Tabletop Rearrangement with Overhand Grasps
Shuai D Han, Nicholas M Stiffler, Athanasios Krontiris +2
This paper studies the underlying combinatorial structure of a class of object rearrangement problems, which appear frequently in applications. The problems involve multiple, simil…
Capacitated Vehicle Routing with Target Geometric Constraints
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…
Optimally Guarding Perimeters and Regions with Mobile Range Sensors
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…
Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics
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 trav…
Toward Optimal Tabletop Rearrangement with Multiple Manipulation Primitives
Baichuan Huang, Xujia Zhang, Jingjin Yu
In practice, many types of manipulation actions (e.g., pick-n-place and push) are needed to accomplish real-world manipulation tasks. Yet, limited research exists that explores the…
Rubik Tables and Object Rearrangement
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…
Toward Efficient Physical and Algorithmic Design of Automated Garages
Teng Guo, Jingjin Yu
Parking in large metropolitan areas is often a time-consuming task with further implications toward traffic patterns that affect urban landscaping. Reducing the premium space neede…
Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time
Jingjin Yu
Let be an grid. Assuming that each is occupied by a robot and a robot may move to a neighboring vertex in a step via synchroni…
Persistent Monitoring of Events with Stochastic Arrivals at Multiple Stations
Jingjin Yu, Sertac Karaman, Daniela Rus
This paper introduces a new mobile sensor scheduling problem, involving a single robot tasked with monitoring several events of interest that occur at different locations. Of parti…
Shortest Path Set Induced Vertex Ordering and its Application to Distributed Distance Optimal Multi-agent Formation Path Planning
Jingjin Yu
For the task of moving a group of indistinguishable agents on a connected graph with unit edge lengths into an arbitrary goal formation, it was previously shown that distance optim…
ORLA*: Mobile Manipulator-Based Object Rearrangement with Lazy A Star
Kai Gao, Zhaxizhuoma, Yan Ding +2
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…
Targeted Parallelization of Conflict-Based Search for Multi-Robot Path Planning
Teng Guo, Jingjin Yu
Multi-Robot Path Planning (MRPP) on graphs, equivalently known as Multi-Agent Path Finding (MAPF), is a well-established NP-hard problem with critically important applications. As…
Optimal Allocation of Many Robot Guards for Sweep-Line Coverage
Si Wei Feng, Teng Guo, Jingjin Yu
We study the problem of allocating many mobile robots for the execution of a pre-defined sweep schedule in a known two-dimensional environment, with applications toward search and…
Optimal and Stable Multi-Layer Object Rearrangement on a Tabletop
Andy Xu, Kai Gao, Si Wei Feng +1
Object rearrangement is a fundamental sub-task in accomplishing a great many physical tasks. As such, effectively executing rearrangement is an important skill for intelligent robo…
Taming Combinatorial Challenges in Optimal Clutter Removal Tasks
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 mini…
Fast, High-Quality Dual-Arm Rearrangement in Synchronous, Monotone Tabletop Setups
Rahul Shome, Kiril Solovey, Jingjin Yu +2
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 computation…