skip to main content

Search for: All records

Creators/Authors contains: "Gao, Kai"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Free, publicly-accessible full text available March 1, 2023
  2. Free, publicly-accessible full text available January 1, 2023
  3. For tabletop object rearrangement problems with overhand grasps, storage space which may be inside or outside the tabletop workspace, or running buffers, can temporarily hold objects which greatly facilitates the resolution of a given rearrangement task. This brings forth the natural question of how many running buffers are required so that certain classes of tabletop rearrangement problems are feasible. In this work, we examine the problem for both the labeled (where each object has a specific goal pose) and the unlabeled (where goal poses of objects are interchangeable) settings. On the structural side, we observe that finding the minimum number of running buffers (MRB) can be carried out on a dependency graph abstracted from a problem instance, and show that computing MRB on dependency graphs is NP-hard. We then prove that under both labeled and unlabeled settings, even for uniform cylindrical objects, the number of required running buffers may grow unbounded as the number of objects to be rearranged increases; we further show that the bound for the unlabeled case is tight. On the algorithmic side, we develop highly effective, exact algorithms for finding MRB for both labeled and unlabeled tabletop rearrangement problems, scalable to over a hundred objects undermore »very high object density. More importantly, our algorithms also compute a sequence witnessing the computed MRB that can be used for solving object rearrangement tasks. Employing these algorithms, empirical evaluations reveal that random labeled and unlabeled instances, which more closely mimics real-world setups, generally have fairly small MRBs.« less
  4. Object rearrangement is a widely-applicable and challenging task for robots. Geometric constraints must be carefully examined to avoid collisions and combinatorial issues arise as the number of objects increases. This work studies the algorithmic structure of rearranging uniform objects, where robot-object collisions do not occur but object-object collisions have to be avoided. The objective is minimizing the number of object transfers under the assumption that the robot can manipulate one object at a time. An efficiently computable decomposition of the configuration space is used to create a ``region graph'', which classifies all continuous paths of equivalent collision possibilities. Based on this compact but rich representation, a complete dynamic programming primitive DFSDP performs a recursive depth first search to solve monotone problems quickly, i.e., those instances that do not require objects to be moved first to an intermediate buffer. DFSDP is extended to solve single-buffer, non-monotone instances, given a choice of an object and a buffer. This work utilizes these primitives as local planners in an informed search framework for more general, non-monotone instances. The search utilizes partial solutions from the primitives to identify the most promising choice of objects and buffers. Experiments demonstrate that the proposed solution returns near-optimal pathsmore »with higher success rate, even for challenging non-monotone instances, than other leading alternatives.« less
  5. Here, we report the high-temperature superlubricity phenomenon accomplished in coatings produced by burnishing powders of antimony trioxide (Sb 2 O 3 ) and magnesium silicate hydroxide coated with carbon (MSH/C) onto the nickel superalloy substrate. The tribological analysis performed in an open-air experimental setup revealed that with the increase of testing temperature, the coefficient of friction (COF) of the coating gradually decreases, finally reaching the superlubricity regime (the COF of 0.008) at 300°C. The analysis of worn surfaces using in-situ Raman spectroscopy suggested the synergistic effect of the inner Sb 2 O 3 adhesion layer and the top MSH/C layer, which do not only isolate the substrate from the direct exposure to sliding but also protect it from oxidation. The cross-sectional transmission electron microscopy (TEM) and X-ray photoelectron spectroscopy (XPS) results indicated the tribochemically-activated formation of an amorphous carbon layer on the surface of the coating during sliding. Formation of the film enables the high-temperature macroscale superlubricity behavior of the material system.
  6. 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 intractabil- ity 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.
  7. 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 returnsmore »near-optimal paths with higher success rate, even for challenging non-monotone instances, than other leading alternatives.« less