Arrow Research search

Author name cluster

Jingjin Yu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

52 papers
2 author rows

Possible papers

52

AAAI Conference 2026 Conference Paper

Robust Out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity

  • Tzvika Geft
  • William Zhang
  • Jingjin Yu
  • Kostas Bekris

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 loads (e.g., containers, pallets, or totes), which are moved by a robot (or other manipulator) along a collision-free path in the grid. The loads are labeled (i.e., unique) and must be stored in a given sequence, and later be retrieved in a different sequence---an operational pattern that arises in logistics applications, such as last-mile distribution centers and shipyards. The objective is to minimize the load relocations to ensure efficient retrieval. A previous result guarantees a zero-relocation solution for known storage and retrieval sequences, even for storage at full capacity, provided that the side of the grid through which loads are stored/retrieved is at least 3 cells wide. However, in practice, the retrieval sequence can change after the storage phase. To address such uncertainty, this work investigates k-bounded perturbations during retrieval, under which any two loads may depart out of order if they are originally at most k positions apart. We prove that a Theta(k) grid width is necessary and sufficient for eliminating relocations at maximum capacity. We also provide an efficient solver for computing a storage arrangement that is robust to such perturbations. To address the higher-uncertainty case where perturbations exceed k, a strategy is introduced to effectively minimize relocations. Extensive experiments show that, for k up to half the grid width, the proposed storage-retrieval framework essentially eliminates relocations. For k values up to the full grid width, relocations are reduced by 50%+.

PDF Details DOI

IROS Conference 2025 Conference Paper

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’ capabilities in challenging, realistic environments. In comparison to the previous state-of-the-art, KARL (1) incorporates a novel six-stage RL curriculum that doubles the system’s motion range, thereby greatly enhancing the system’s grasping performance, (2) integrates a robust Kalman filter layer between the perception and reinforcement learning (RL) control modules, enabling the system to maintain an uncertain but continuous 6D pose estimate even when the target object temporarily exits the camera’s field-of-view or undergoes rapid, unpredictable motion, and (3) introduces mechanisms to allow retries to gracefully recover from unavoidable policy execution failures. Extensive evaluations conducted in both simulation and real-world experiments qualitatively and quantitatively corroborate KARL’s advantage over earlier systems, achieving higher grasp success rates and faster robot execution speed. Source code and supplementary materials for KARL will be made available at: https://github.com/arc-l/karl.

Details

IROS Conference 2025 Conference Paper

Monocular One-Shot Metric-Depth Alignment for RGB-Based Robot Grasping

  • Teng Guo 0006
  • 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.

Details

ICRA Conference 2025 Conference Paper

ORLA*: Mobile Manipulator-Based Object Rearrangement with Lazy A

  • Kai Gao
  • Zhaxizhuoma
  • Yan Ding 0002
  • Shiqi Zhang 0001
  • Jingjin Yu

Effectively performing object rearrangement is an essential skill for mobile manipulators, e. g. , setting up a dinner table. A key challenge in such problems is deciding an appropriate ordering to effectively untangle object-object dependencies while considering the necessary motions for realizing manipulation tasks (e. g. , pick and place). Computing time-optimal multi-object rearrangement solutions for mobile manipulators remains a largely untapped research direction. In this work, we propose ORLA*, which leverages delayed/lazy evaluation in searching for a high-quality object pick-n-place sequence that considers both end-effector and mobile robot base travel. ORLA* readily handles multi-layered rearrangement tasks powered by learning-based stability predictions. 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: gaokai15.github.io/ORLA-Star/

Details

ICRA Conference 2025 Conference Paper

PROBE: Proprioceptive Obstacle Detection and Estimation while Navigating in Clutter

  • Dhruv Metha Ramesh
  • Aravind Sivaramakrishnan
  • Shreesh Keskar
  • Kostas E. Bekris
  • Jingjin Yu
  • Abdeslam Boularias

In critical applications, including search-and-rescue in degraded environments, blockages can be prevalent and prevent the effective deployment of certain sensing modalities, particularly vision, due to occlusion and the constrained range of view of onboard camera sensors. To enable robots to tackle these challenges, we propose a new approach, Proprioceptive Obstacle Detection and Estimation while navigating in clutter (PROBE), which instead relies only on the robot's proprioception to infer the presence or absence of occluded rectangular obstacles while predicting their dimensions and poses in SE (2). The proposed approach is a Transformer neural network that receives as input a history of applied torques and sensed whole-body movements of the robot and returns a parameterized representation of the obstacles in the environment. The effectiveness of PROBE is evaluated on simulated environments in Isaac Gym and with a real Unitree Go1 quadruped robot. The project webpage can be found at https://dhruvmetha.github.io/legged-probe/.

Details

IROS Conference 2025 Conference Paper

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 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 applications areas including robotics, augmented reality, computer vision. The source code for our implementation will be made publicly available at https://github.com/GreatenAnoymous/RGBTrack.git.

Details

ICRA Conference 2025 Conference Paper

Targeted Parallelization of Conflict-Based Search for Multi-Robot Path Planning

  • Teng Guo 0006
  • Jingjin Yu

Multi-Robot Path Planning (MRPP) on graphs, also known as Multi-Agent PathFinding (MAPF), is a well-established NP-hard problem with critically important applications. In (near)-optimally solving MRPP, as serial computation approaches its efficiency limits, parallelization offers a promising route to extend that limit further. As a single solution is unlikely to be successful in addressing all settings, e. g. , in handling small/hard or large/sparse MRPP instances, in this study, we explore a targeted parallelization effort to boost the performance of conflict-based search for MRPP. Specifically, when instances are relatively small but robots are densely packed with strong interactions, we devise a decen-tralized parallel algorithm that concurrently explores multiple branches that leads to markedly enhanced solution discovery. On the other hand, for large problems with sparse robot-robot interactions, we find that prioritizing node expansion and conflict resolution more promising. Our innovative multi-threaded approach to parallelizing bounded-suboptimal conflict search-based algorithms demonstrates significant improvements over baseline serial methods in success rate or runtime. Our work furthers the understanding of MRPP and charts a promising path for elevating solution quality and computational efficiency through parallel algorithmic strategies.

Details

ICRA Conference 2024 Conference Paper

Decentralized Lifelong Path Planning for Multiple Ackerman Car-Like Robots

  • Teng Guo 0006
  • 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 topic, computationally efficient and high-quality solutions are lacking, especially in lifelong settings where robots must continuously take on new tasks. In this work, we make it possible to extend key ideas enabling state-of-the-art (SOTA) methods for multi-robot planning in discrete domains to the motion planning of multiple Ackerman (car-like) robots in lifelong settings, yielding high-performance centralized and decentralized planners. Our planners compute trajectories that allow the robots to reach precise SE(2) goal poses. The effectiveness of our methods is thoroughly evaluated and confirmed using both simulation and real-world experiments.

Details

JAIR Journal 2024 Journal Article

Expected 1.x Makespan-Optimal Multi-Agent Path Finding on Grid Graphs in Low Polynomial 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 natural question: How optimal can polynomial-time algorithms reach? Whereas algorithms for computing constant-factor optimal solutions have been developed, the constant factor is generally very large, limiting their application potential. In this work, among other breakthroughs, we propose the first low-polynomial-time MAPF 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 agent density, with high probability. Moreover, when regularly distributed obstacles are introduced, our methods experience no performance degradation. These methods generalize to support 100% agent density. Regardless of the dimensionality and density, our high-quality methods are enabled by a unique hierarchical integration of two key building blocks. At the higher level, we apply the labeled Grid Rearrangement Algorithm (GRA), capable of performing efficient reconfiguration on grids through row/column shuffles. At the lower level, we devise novel methods that efficiently simulate row/column shuffles returned by GRA. Our implementations of GRA-based algorithms are highly effective in extensive numerical evaluations, demonstrating excellent scalability compared to other SOTA methods. For example, in 3D settings, GRA-based algorithms readily scale to grids with over 370,000 vertices and over 120,000 agents and consistently achieve conservative makespan optimality approaching 1.5, as predicted by our theoretical analysis.

PDF Details DOI

IROS Conference 2024 Conference Paper

LGMCTS: Language-Guided Monte-Carlo Tree Search for Executable Semantic Object Rearrangement

  • Haonan Chang
  • Kai Gao
  • Kowndinya Boyalakuntla
  • Alex Lee
  • Baichuan Huang
  • Jingjin Yu
  • Abdeslam Boularias

We present LGMCTS, a framework that uniquely combines language guidance with geometrically informed sampling distributions to effectively rearrange objects according to geometric patterns dictated by natural language descriptions. LGMCTS uses Monte Carlo Tree Search (MCTS) to create feasible action plans that ensure executable semantic object rearrangement. We present a comprehensive comparison with leading approaches that use language to generate goal rearrangements independently of actionable planning, including Structformer, StructDiffusion, and Code as policies. We also present a new benchmark, the Executable Language Guided Rearrangement (ELGR) Bench, containing tasks involving intricate geometry. With the ELGR bench, we show limitations of task and motion planning (TAMP) solutions that are purely based on Large Language Models (LLM) such as Code as Policies and Progprompt on such tasks. Our findings advocate for using LLMs to generate intermediary representations rather than direct action planning in geometrically complex rearrangement scenarios, aligning with perspectives from recent literature. Our code and supplementary materials are accessible at https://lgmcts.github.io/.

Details

AAAI Conference 2024 Conference Paper

On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles

  • Marcus Gozon
  • Jingjin Yu

In the 15-puzzle game, 15 labeled square tiles are reconfigured on a 4 × 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.

PDF Details DOI

ICRA Conference 2024 Conference Paper

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 synergistic integration of different manipulation actions for optimally solving long-horizon task-and-motion planning problems. In this study, we propose and investigate planning high-quality action sequences for solving long-horizon tabletop rearrangement tasks in which multiple manipulation primitives are required. Denoting the problem rearrangement with multiple manipulation primitives (REMP), we develop two algorithms, hierarchical best-first search (HBFS) and parallel Monte Carlo tree search for multi-primitive rearrangement (PMMR) toward optimally resolving the challenge. Extensive simulation and real robot experiments demonstrate that both methods effectively tackle REMP, with HBFS excelling in planning speed and P M MR producing human-like, high-quality solutions with a nearly 100% success rate. Source code and supplementary materials will be available at https://github.com/arc-l/remp.

Details

ICRA Conference 2024 Conference Paper

Well-Connected Set and Its Application to Multi-Robot Path Planning

  • Teng Guo 0006
  • Jingjin Yu

Parking lots and autonomous warehouses for accommodating many vehicles/robots adopt designs in which the underlying graphs are well-connected to simplify planning and reduce congestion. In this study, we formulate and delve into the largest well-connected set (LWCS) problem and explore its applications in layout design for multi-robot path planning. Roughly speaking, a well-connected set over a connected graph is a set of vertices such that there is a path on the graph connecting any pair of vertices in the set without passing through any additional vertices of the set. Identifying an LWCS has many potential high-utility applications, e. g. , for determining parking garage layout and capacity, as prioritized planning can be shown to be complete when start/goal configurations belong to an LWCS. In this work, we establish that computing an LWCS is NP-complete. We further develop optimal and near-optimal LWCS algorithms, with the near-optimal algorithm targeting large maps. A complete prioritized planning method is given for planning paths for multiple robots residing on an LWCS.

Details

IROS Conference 2023 Conference Paper

DynGMP: Graph Neural Network-Based Motion Planning in Unpredictable Dynamic Environments

  • Wenjin Zhang
  • Xiao Zang
  • Lingyi Huang
  • Yang Sui 0001
  • Jingjin Yu
  • Yingying Chen 0001
  • Bo Yuan 0001

Neural networks have already demonstrated attractive performance for solving motion planning problems, especially in static and predictable environments. However, efficient neural planners that can adapt to unpredictable dynamic environments, a highly demanded scenario in many practical applications, are still under-explored. To fill this research gap and enrich the existing motion planning approaches, in this pa-per, we propose DynGMP, a graph neural network (GNN)-based planner that provides high-performance planning solutions in unpredictable dynamic environments. By fully leveraging the prior exploration experience and minimizing the replanning cost incurred by environmental change, DynGMP achieves high planning performance and efficiency simultaneously. Empirical evaluations across different environments show that DynGMP can achieve close to 100% success rate with fast planning speed and short path cost. Compared with existing non-learning and learning-based counterparts, DynGMP shows very significant planning performance improvement, e. g. , at least 2. 7×, 2. 2×, $2. 4\times$ and $2\times$ faster planning speed with low path distance in four environments, respectively.

Details

IROS Conference 2023 Conference Paper

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-based robotic grasping methods implicitly assume target objects are stationary or moving predictably. Performing grasping of unpredictably moving objects presents a unique set of challenges. For example, a pre-computed robust grasp can become unreachable or unstable as the target object moves, and motion planning must also be adaptive. In this work, we present a new approach, Eye-on-hAnd Reinforcement Learner (EARL), for enabling coupled Eye-on-Hand (EoH) robotic manipulation systems to perform real-time active pose tracking and dynamic grasping of novel objects without explicit motion prediction. EARL readily addresses many thorny issues in automated hand-eye coordination, including fast-tracking of 6D object pose from vision, learning control policy for a robotic arm to track a moving object while keeping the object in the camera's field of view, and performing dynamic grasping. We demonstrate the effectiveness of our approach in extensive experiments validated on multiple commercial robotic arms in both simulations and complex real-world tasks.

Details

IROS Conference 2023 Conference Paper

Effectively Rearranging Heterogeneous Objects on Cluttered Tabletops

  • Kai Gao
  • Justin Yu
  • Tanay Sandeep Punjabi
  • Jingjin Yu

Effectively rearranging heterogeneous objects constitutes a high-utility skill that an intelligent robot should master. Whereas significant work has been devoted to the grasp synthesis of heterogeneous objects, little attention has been given to the planning for sequentially manipulating such objects. In this work, we examine the long-horizon sequential rearrangement of heterogeneous objects in a tabletop setting, addressing not just generating feasible plans but near-optimal ones. Toward that end, and building on previous methods, including combinatorial algorithms and Monte Carlo tree search-based solutions, we develop state-of-the-art solvers for optimizing two practical objective functions considering key object properties such as size and weight. Thorough simulation studies show that our methods provide significant advantages in handling challenging heterogeneous object rearrangement problems, especially in cluttered settings. Real robot experiments further demonstrate and confirm these advantages. Source code and evaluation data associated with this research will be available at https//github.com/arc-l/TRLB upon the publication of this manuscript

Details

IROS Conference 2023 Conference Paper

Efficient Heuristics for Multi-Robot Path Planning in Crowded Environments

  • Teng Guo 0006
  • 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 robotics. Current MRPP solvers can be divided into reduction-based, search-based, and rule-based categories, each with their strengths and limitations. Regardless of the methodology, however, the issue of handling dense MRPP instances remains a significant challenge, where existing approaches generally demonstrate a dichotomy regarding solution optimality and efficiency. This study seeks to bridge the gap in optimal MRPP resolution for dense, highly-entangled scenarios, with potential applications to high-density storage systems and traffic congestion control. Toward that goal, we analyze the behaviors of SOTA MRPP algorithms in dense settings and develop two hybrid algorithms leveraging the strengths of existing SOTA algorithms: DCBS (database-accelerated enhanced conflict-based search) and SCBS (sparsified enhanced conflict-based search). Experimental validations demonstrate that DCBS and SCBS deliver a significant reduction in computational time compared to existing bounded-suboptimal methods and improve solution quality compared to existing rule-based methods, achieving a desirable balance between computational efficiency and solution optimality. As a result, DCBS and SCBS are particularly suitable for quickly computing good-quality solutions for multi-robot routing in dense settings. Simulation video https://youtu.be/dZxMPUr7Bqg Upon the publication of the manuscript source code and data will be released at https://github.com/arc-l/dcbs

Details

ICRA Conference 2023 Conference Paper

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 randomly in a lattice are to be sorted using a robot arm with k 1 swap spaces or buffers, capable of holding up to $k$ objects on its end-effector simultaneously. On the structural side, we show that the addition of each new buffer brings diminishing returns in saving the end-effector travel distance while holding the total number of pick-n-swap operations at a minimum. This is due to an interesting recursive cycle structure in random m-permutation, where the largest cycle covers over 60% of objects. On the algorithmic side, we propose fast algorithms for 1D and 2D lattice rearrangement problems that can effectively use multiple buffers to boost solution optimality. Numerical experiments demonstrate the efficiency and scalability of our methods, as well as confirm the diminishing return structure as more buffers are employed. Introduction video: https://youtu.be/KtBxoARGaVQ

Details

ICRA Conference 2023 Conference Paper

Optimal Allocation of Many Robot Guards for Sweep-Line Coverage

  • Si Wei Feng
  • Teng Guo 0006
  • 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 rescue, coverage, surveillance, monitoring, pursuit-evasion, and so on. The mobile robots (or agents) are assumed to have one-dimensional sensing capability with probabilistic guarantees that deteriorate as the sensing distance increases. In solving such tasks, a time-parameterized distribution of robots along the sweep frontier must be computed, to minimize the number of robots used to achieve some desired coverage quality guarantee or to maximize the probabilistic guarantee for a given the number of robots. We propose a max-flow-based algorithm for solving the allocation task, which builds on a decomposition technique of the workspace as a generalization of the well-known boustrophedon decomposition. Our proposed algorithm has a very low polynomial running time and completes in under two seconds for polygonal environments with over 10 5 vertices. Simulation experiments are carried out on three realistic use cases with randomly generated obstacles of varying shapes, sizes, and spatial distributions, demonstrating our proposed method's applicability and scalability. Introduction video: https://youtu.be/8taX92rzC5k.

Details

IROS Conference 2023 Conference Paper

Optimal and Stable Multi-Layer Object Rearrangement on a Tabletop

  • Andy Xu
  • Kai Gao
  • Si Wei Feng
  • Jingjin Yu

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 robots to master. In this study, we conduct the first algorithmic study on optimally solving the problem of Multi-layer Object Rearrangement on a Tabletop (MORT), in which one object may be relocated at a time, and an object can only be moved if other objects do not block its top surface. In addition, any intermediate structure during the reconfiguration process must be physically stable, i. e. , it should stand without external support. To tackle the dual challenges of untangling the dependencies between objects and ensuring structural stability, we develop an algorithm that interleaves the computation of the optimal rearrangement plan and structural stability checking. Using a carefully constructed integer linear programming (ILP) model, our algorithm, Stability-Aware Rearrangement Programming (SARP), readily scales to optimally solve complex rearrangement problems of 3D structures with over 60 building blocks, with solution quality significantly outperforming natural greedy best-first approaches. Upon the publication of the manuscript source code and data will be available at https//github.com/arc-1/mort/.

Details

ICRA Conference 2023 Conference Paper

Toward Efficient Physical and Algorithmic Design of Automated Garages

  • Teng Guo 0006
  • Jingjin Yu

Parking in large metropolitan areas is often a time-consuming task with further implications for traffic patterns that affect urban landscaping. Reducing the premium space needed for parking has led to the development of automated mechanical parking systems. Compared to regular garages having one or two rows of vehicles on each island, automated garages can have multiple rows of vehicles stacked together to support higher parking demands. Although this multi-row layout reduces parking space, it makes parking and retrieval more complicated. In this work, we propose an automated garage design that supports nearly 100% parking density. Modeling the problem of parking and retrieving multiple vehicles as a special class of multi-robot path planning problem, we propose associated algorithms for handling all common operations of the automated garage, including (1) optimal algorithm and near-optimal methods that find feasible and efficient solutions for simultaneous parking/retrieval and (2) a novel shuffling mechanism to rearrange vehicles to facilitate scheduled retrieval at rush hours. We conduct thorough simulation studies showing the proposed methods are promising for large and high-density real-world parking applications.

Details

ICRA Conference 2022 Conference Paper

Barrier Forming: Separating Polygonal Sets with Minimum Number of Lines

  • Si Wei Feng
  • Jingjin Yu

In this work, we carry out structural and al-gorithmic 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.

Details

ICRA Conference 2022 Conference Paper

Fast High-Quality Tabletop Rearrangement in Bounded Workspace

  • Kai Gao
  • Darren Lau
  • Baichuan Huang
  • Kostas E. Bekris
  • Jingjin Yu

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

Details

ICRA Conference 2022 Conference Paper

Interleaving Monte Carlo Tree Search and Self-Supervised Learning for Object Retrieval in Clutter

  • Baichuan Huang
  • Teng Guo 0006
  • Abdeslam Boularias
  • Jingjin Yu

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 → 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.

Details

ICAPS Conference 2022 Conference Paper

Lazy Rearrangement Planning in Confined Spaces

  • Rui Wang 0087
  • Kai Gao
  • Jingjin Yu
  • Kostas E. Bekris

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.

Details

ICRA Conference 2022 Conference Paper

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 planner, with applications to both one-shot and life-long multi-robot path planning problems. We show that the 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 over medium and large maps, for both one-shot and life-long problem settings.

Details

IROS Conference 2022 Conference Paper

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 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 30× with an improved solution quality, in comparison to a serial MCTS implementation. We show that PMBS can be directly applied to real robot hardware with negligible sim-to-real differences. Supplementary material, including video, can be found at https://github.com/arc-l/pmbs.

Details

ICRA Conference 2022 Conference Paper

Persistent Homology for Effective Non-Prehensile Manipulation

  • Ewerton R. Vieira
  • Daniel Nakhimovich
  • Kai Gao
  • Rui Wang 0087
  • Jingjin Yu
  • Kostas E. Bekris

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.

Details

IROS Conference 2022 Conference Paper

Polynomial Time Near-Time-Optimal Multi-Robot Path Planning in Three Dimensions with Applications to Large-Scale UAV Coordination

  • Teng Guo 0006
  • Si Wei Feng
  • Jingjin Yu

For enabling efficient, large-scale coordination of unmanned aerial vehicles (UAV s) under the labeled setting, in this work, we develop the first polynomial time algorithm for the reconfiguration of many moving bodies in three-dimensional spaces, with provable 1. $x$ asymptotic makespan optimality guarantee under high robot density. More precisely, on an $m_{1} \times m_{2} \times m_{3}$ grid, $m_{1}\geq m_{2}\geq m_{3}$, our method computes solutions for routing up to $\displaystyle \frac{m_{1}m_{2}m_{3}}{3}$ uniquely labeled robots with uniformly randomly distributed start and goal configurations within a makespan of $m_{1}+2m_{2}+2m_{3}+o(m_{1})$, with high probability. Because the makespan lower bound for such instances is $m_{1}+m_{2}+m_{3}-o(m_{1})$, also with high probability, as $m_{1}\displaystyle \rightarrow\infty, \frac{m_{1}+2m_{2}+2m_{3}}{m_{1}+m_{2}+m_{3}}$ optimality guarantee is achieved. $\displaystyle \frac{m_{1}+2 m_{2}+2m_{3}}{m_{1}+m_{2}+m_{3}}\in\left(1, \displaystyle \frac{5}{3}\right]$, yielding 1. $x$ optimality. In contrast, it is well-known that multi-robot path planning is NP-hard to optimally solve. In numerical evaluations, our method readily scales to support the motion planning of over 100, 000 robots in 3D while simultaneously achieving 1. $x$ optimality. We demonstrate the application of our method in coordinating many quadcopters in both simulation and hardware experiments.

Details

IROS Conference 2022 Conference Paper

Robot Motion Planning as Video Prediction: A Spatio-Temporal Neural Network-based Motion Planner

  • Xiao Zang
  • Miao Yin
  • Lingyi Huang
  • Jingjin Yu
  • Saman A. Zonouz
  • Bo Yuan 0001

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 5×, 2. 6× and 1. 8× 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.

Details

ICRA Conference 2022 Conference Paper

Stackelberg Strategic Guidance for Heterogeneous Robots Collaboration

  • Yuhan Zhao
  • Baichuan Huang
  • Jingjin Yu
  • Quanyan Zhu

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.

Details

IROS Conference 2022 Conference Paper

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 re- arrangement 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.

Details

IROS Conference 2021 Conference Paper

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 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 NPhard; 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.

Details

ICRA Conference 2021 Conference Paper

DIPN: Deep Interaction Prediction Network with Application to Clutter Removal

  • Baichuan Huang
  • Shuai D. Han
  • Abdeslam Boularias
  • Jingjin Yu

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.

Details

ICRA Conference 2021 Conference Paper

Sensor Placement for Globally Optimal Coverage of 3D-Embedded Surfaces

  • Si Wei Feng
  • Kai Gao
  • Jie Gong
  • Jingjin Yu

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 net- work 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.

Details

ICRA Conference 2021 Conference Paper

Spatial and Temporal Splitting Heuristics for Multi-Robot Motion Planning

  • Teng Guo 0006
  • 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.

Details

ICRA Conference 2021 Conference Paper

Uniform Object Rearrangement: From Complete Monotone Primitives to Efficient Non-Monotone Informed Search

  • Rui Wang 0087
  • Kai Gao
  • Daniel Nakhimovich
  • Jingjin Yu
  • Kostas E. Bekris

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 DFS DP 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. DFS DP 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.

Details

IROS Conference 2020 Conference Paper

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 clutter removal (MRCR). Targeting practical applications where motion planning is non-trivial but is not a bottle-neck, 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.

Details

IROS Conference 2019 Conference Paper

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-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.

Details

ICRA Conference 2019 Conference Paper

Towards Robust Product Packing with a Minimalistic End-Effector

  • Rahul Shome
  • Wei N. Tang
  • Changkyu Song
  • Chaitanya Mitash
  • Hristiyan Kourtev
  • Jingjin Yu
  • Abdeslam Boularias
  • Kostas E. Bekris

Advances in sensor technologies, object detection algorithms, planning frameworks and hardware designs have motivated the deployment of robots in warehouse automation. A variety of such applications, like order fulfillment or packing tasks, require picking objects from unstructured piles and carefully arranging them in bins or containers. Desirable solutions need to be low-cost, easily deployable and controllable, making minimalistic hardware choices desirable. The challenge in designing an effective solution to this problem relates to appropriately integrating multiple components, so as to achieve a robust pipeline that minimizes failure conditions. The current work proposes a complete pipeline for solving such packing tasks, 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 finger. To achieve the desired level of robustness, three key manipulation primitives are identified, which take advantage of the environment and simple operations to successfully pack multiple cubic objects. The overall approach is demonstrated to be robust to execution and perception errors. The impact of each manipulation primitive is evaluated by considering different versions of the proposed pipeline, which incrementally introduce reasoning about object poses and corrective manipulation actions.

Details

IROS Conference 2018 Conference Paper

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 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.

Details

ICRA Conference 2017 Conference Paper

A portable, 3D-printing enabled multi-vehicle platform for robotics research and education

  • Jingjin Yu
  • Shuai D. Han
  • Wei N. Tang
  • Daniela Rus

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 × 5 × 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.

Details

IROS Conference 2015 Conference Paper

Anytime planning of optimal schedules for a mobile sensing robot

  • Jingjin Yu
  • Javed A. Aslam
  • Sertac Karaman
  • Daniela Rus

We study the problem in which a mobile sensing robot is tasked to travel among and gather intelligence at a set of spatially distributed points-of-interest (POIs). The quality of the information collected at a POI is characterized by some sensory (reward) function of time. With limited fuel, the robot must balance between spending time traveling to more POIs and performing time-consuming sensing activities at POIs to maximize the overall reward. In a dual formulation, the robot is required to acquire a minimum amount of reward with the least amount of time. We propose an anytime planning algorithm for solving these two NP-hard problems to arbitrary precision for arbitrary reward functions. The algorithm is effective on large instances with tens to hundreds of POIs, as demonstrated with an extensive set of computational experiments. Besides mobile sensor scheduling, our algorithm also applies to automation scenarios such as intelligent and optimal itinerary planning.

Details

IROS Conference 2014 Conference Paper

Correlated Orienteering Problem and its application to informative path planning for 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 plan informative tours (cyclic paths) for persistent monitoring of an environment with spatial correlations, where the tours are constrained to a fixed length or time budget. The main feature of COP is a quadratic utility function that captures spatial correlations among points of interest that are close to each other. COP may be solved using mixed integer quadratic programming (MIQP) that can plan multiple disjoint tours that maximize the quadratic utility function. We perform extensive characterization of our method to verify its correctness, as well as its applicability to the estimation of a realistic, time-varying, and spatially correlated scalar field.

Details

ICRA Conference 2014 Conference Paper

Distance optimal target assignment in robotic networks under communication and sensing constraints

  • Jingjin Yu
  • Soon-Jo Chung
  • Petros G. Voulgaris

We study the problem of minimizing the total distance incurred in assigning a group of mobile robots to an equal number of static targets. Assuming that the robots have limited, range-based communication and target-sensing capabilities, we present a necessary and sufficient condition for ensuring distance optimality when robots and targets are uniformly randomly distributed. We then provide an explicit, non-asymptotic formula for computing the number of robots needed for guaranteeing optimality in terms of the robots' sensing and communication capabilities with arbitrarily high probabilities. The bound given in the formula is also asymptotically tight. Due to the large number of robots needed for high-probability optimality guarantee, we continue to investigate strategies for cases in which the number of robots cannot be freely chosen. We show that a properly designed strategy can be asymptotically optimal or suboptimal with constant approximation ratios.

Details

ICRA Conference 2014 Conference Paper

Persistent monitoring of events with stochastic arrivals at multiple stations

  • Jingjin Yu
  • Sertac Karaman
  • Daniela Rus

This paper is concerned with a novel mobile sensor scheduling problem, involving a single robot tasked with monitoring several events of interest that occur at different locations. Of particular interest is the monitoring of events that can not be easily forecast. Prominent examples range from natural phenomena (e. g. , monitoring abnormal seismic activity around a volcano using a ground robot) to urban activities (e. g. , monitoring early formations of traffic congestion in the Boston area using an aerial robot). Motivated by these examples, this paper focuses on problems where the precise occurrence time of the events is not known a priori, but some statistics for their inter-arrival times are available from past observations. The robot's task is to monitor the events to optimize the following two objectives: (i) maximize the number of events observed and (ii) minimize the delay between two consecutive observations of events occurring at the same location. Provided with only one robot, it is crucial to optimize these objectives in a balanced way, so that they are optimized at each station simultaneously. Our main theoretical result is that this complex mobile sensor scheduling problem can be reduced to a quasi-convex program, which can be solved in polynomial time. In other words, a globally optimal solution can be computed in time that is polynomial in the number of locations. We also provide computational experiments that validate our theoretical results.

Details

ICRA Conference 2013 Conference Paper

Efficient formation path planning on large graphs

  • Max Katsev
  • Jingjin Yu
  • Steven M. LaValle

For the task of transferring a group of robots from one formation to another on a connected graph with unit edge lengths, we provide an efficient hierarchical algorithm that can complete goal assignment and path planning for 10, 000 robots on a 250, 000 vertex grid in under one second. In the extreme, our algorithm can handle up to one million robots on a grid with one billion vertices in approximately 30 minutes. Perhaps more importantly, we prove that with high probability, the algorithm supplies paths with total distance within a constant multiple of the optimal total distance. Furthermore, our hierarchical method also allows these paths to be scheduled with a tight completion time guarantee. In practice, our implementation yields a total path distance less than two times of the true optimum and a much shorter completion time.

Details

ICRA Conference 2013 Conference Paper

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 compute minimum last arrival time and minimum total distance solutions for our MPP formulation, respectively. The resulting algorithms from these ILP models are complete and guaranteed to yield true optimal solutions. In addition, our flexible framework can easily accommodate other variants of the MPP problem. Focusing on the time optimal algorithm, we evaluate its performance, both as a stand alone algorithm and as a generic heuristic for quickly solving large problem instances. Computational results confirm the effectiveness of our method.

Details

AAAI Conference 2013 Conference Paper

Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs

  • Jingjin Yu
  • Steven LaValle

In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate. Our optimality objectives are to minimize the total arrival time, the makespan (last arrival time), and the total distance. On the structure side, we show that, in general, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a minimal and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i. e. robots within each group are interchangeable).

PDF Details

ICRA Conference 2011 Conference Paper

Story validation and approximate path inference with a sparse network of heterogeneous sensors

  • Jingjin Yu
  • Steven M. LaValle

Given a story from an agent (sensor outputs from a robot or a tale told by a human) and recordings from a spare network of heterogeneous sensors, this paper provides efficient algorithms that validate whether it is possible to reconstruct a path compatible with the sensor recordings that is also "close" to the agent's story. In solving the proposed problems, we show that effective exploitation of a unique finite automaton structure yields time complexity linear in both the length of the story and the length of the sensor observation history. Besides immediate applicability towards security and forensics problems, the idea of behavior validation using external sensors also appears promising in complementing design time model verification.

Details

ICRA Conference 2010 Conference Paper

Probabilistic shadow information spaces

  • Jingjin Yu
  • Steven M. LaValle

This paper introduces a Bayesian filter that is specifically designed for counting targets that move outside of the field of view while performing a sensor sweep. Information space concepts are used to dramatically reduce the filter complexity so that information is processed only when the shadow region (all points invisible to the sensors) changes combinatorially or targets pass in and out of view. Previous work assumed perfect observations; however, this paper extends the approach to enable probabilistic disturbances. Practical algorithms are introduced, implemented, and demonstrated for computing the filter outputs based on realistic data.

Details

ICRA Conference 2008 Conference Paper

Tracking hidden agents through shadow information spaces

  • Jingjin Yu
  • Steven M. LaValle

This paper addresses problems of inferring the locations of moving agents from combinatorial data extracted by robots that carry sensors. The agents move unpredictably and may be fully distinguishable, partially distinguishable, or completely indistinguishable. The key is to introduce information spaces that extract and maintain combinatorial sensing information. This leads to monitoring the changes in connected components of the shadow region, which is the set of points not visible to any sensors at a given time. When used in combination with a path generator for the robots, the approach solves problems such as counting the number of agents, determining movements of teams of agents, and solving pursuit-evasion problems. An implementation with examples is presented.

Details
v2026.09.13