The Role of Data and Combinatorics in Scaling Intelligent, Interactive Systems

To deal with the strict timelines and scale to many machines that coordinate (potentially with people) to solve tasks in increasingly complex and unstructured environments: We will explore statistical assumptions about the distribution of problem instances and mathematical characterizations of the space of possible solutions to find practical ways to overcome combinatorial challenges and utilize big data to improve performance and scaling.

Research Highlights

1. A Novel Depth-first Dynamic Programming Algorithm for Optimal Task Planning for Object Rearrangement

In nearly all aspects of our everyday lives, be it work related, at home, or for play, objects are to be manipulated and rearranged with precision, e.g., tidying up a messy desk, cleaning the table after dinner, or solving a jigsaw puzzle. Similarly, many industrial and logistics applications require repetitive rearrangements of many objects, e.g., the sorting and packaging of products on conveyors with robots or rearranging products on store shelves, and doing so efficiently is of critical importance in response to greater consumer demand and the labor shortage caused by the COVID-19 pandemic. However, planning and deciding the sequence of objects for optimizing a rearrangement task is non-trivial; we have shown that these tasks often embed with them provably hard combinatorial challenges including well-known Feedback Vertex Set, Vertex Separation, and Traveling Salesperson problems.

Toward addressing the above-mentioned hard challenges, thorough theoretical analysis was performed to understand the intricate dependencies among many objects in the same scene. Consider the task of switching the locations of two objects using a single robot manipulator, which requires one of the two objects to be temporarily relocated to complete, creating a mutual dependency between the objects. As the number of objects in the scene increases, the complexity of the dependency structure also grows, which is directly related to the number of atomic manipulations required to solve a task. As a result, minimizing the number of atomic manipulations, which embeds within it a Feedback Vertex Set problem, is NP-hard to even approximate. The issue is further complicated when space for holding temporarily displaced objects is limited, giving rise to a variant of the Vertex Separator minimization problem. In both cases, the core challenge boils down to figure out the minimum number of objects that must be displaced to untangle all dependencies.

Due to the inherent computation complexity, optimal task planning for rearrangement is intractable in general. However, adapting a data-driven approach, after analyzing a large number of actual instances, we discovered that for the super majority of practical setups, the number of objects that must be displaced is small. Furthermore, these instances often admit many solution sequences yielding comparable time optimality. Based on the insight, we developed dynamic programming methods for searching through all 2^n possible rearrangement sequences over n objects for an optimal sequence. With the introduction of a novel depth-first heuristics, we obtain a new algorithm we call depth-first dynamic programming (DFDP). In extensive simulation and real robot experiments, DFDP is shown to be both highly scalable and highly optimal; it applies to addressing both tabletop rearrangement tasks as well as in-shelf product ordering tasks.

2. A Novel Strategy for Retrieving a Target Object from a Cluttered and Confined Space Using Persistent Homology

Retrieving a target object from a cluttered and confined space, such as extracting a product from a shelf, requires addressing the uncertainty and clutter. While conventional pick-and-place manipulations are commonly employed, they can be computationally demanding in highly cluttered scenarios and inefficient during execution. To overcome these challenges, roboticists have turned to non-prehensile actions, such as pushing actions, introducing additional complexities, as robot arms are typically not designed to push object with its arm. A novel strategy developed to address this problem involves applying Persistent Homology (PH) to automatically identify clusters of blocking objects within the workspace, eliminating the need for manual input or tuning parameters. Furthermore, the robustness inherent in PH improves the effectiveness of pushing actions to relocate these clusters, reducing the number of pushes required to solve the retrieval problem compared to existing approaches. This new approach represents a significant advancement in robotic manipulation for retrieval problems in cluttered environments, introducing a new skill set for automation in real-world applications.

Papers

  • Socially responsible facial recognition of animals by Fred S. Roberts in AI and Ethics, 2023, https://doi.org/10.1007/s43681-023-00344-y
  • On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles by Marcus Gozon, and Jingjin Yu in Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24).
  • Effective Non-Prehensile Manipulation via Persistent Homology & Monte-Carlo Tree Search by Ewerton Vieira*, Kai Gao, Daniel Nakhimovich, Kostas E. Bekris, and Jingjin Yu in 18th International Symposium of Experimental Robotics, 2023 (ISER 2023).
  • Minimizing Running Buffers for Tabletop Object Rearrangement: Complexity, Fast Algorithms, and Applications by K. Gao, S. W. Feng, B. Huang and J. Yu in The International Journal of Robotics Research, in press and online (2023).
  • Rearrangement on Lattices with Pick-n-Swaps: Optimality Structures and Efficient Algorithms, by Jingjin Yu in IEEE The International Journal of Robotics Research, in press and online (2023).
  • Sub-1.5 Time-Optimal Multi-Robot Path Planning on Grids in Polynomial Time by T. Guo and J. Yu in 2022 Robotics: Science and Systems (RSS 2022).
  • Lazy Rearrangement Planning in Confined Spaces by Rui Wang, Kai Gao, Jingjin Yu, Kostas E. Bekris, to appear in AAAI International Conference on Automated Planning and Scheduling, ICAPS (2022).
  • Self-Supervised Monte Carlo Tree Search Learning for Object Retrieval in Clutter
    by Baichuan Huang, Teng Guo, Abdeslam Boularias, Jingjin Yu in IEEE International Conference on Robotics and Automation, ICRA (2022).
  • Persistent Homology for Effective Non-Prehensile Manipulation by Ewerton Vieira, Daniel Nakhimovich, Kai Gao, Rui Wang, Jingjin Yu, and Kostas E. Bekris in IEEE International Conference on Robotics and Automation, ICRA (2022).
  • Fast High-Quality Tabletop Rearrangement in Bounded Workspace by Kai Gao, Darren Lau, Baichuan Huang, Kostas E. Bekris, and Jingjin Yu in IEEE International Conference on Robotics and Automation, ICRA (2022).

  • Efficient and High-quality Prehensile Rearrangement in Cluttered and Confined Spaces by Rui Wang, Yinglong Miao, and Kostas E. Bekris in IEEE International Conference on Robotics and Automation, ICRA (2022).

  • Robotics as an Enabler of Resiliency to Disasters: Promises and Pitfalls by R. Wang, D. Nakhimovitch, K. Bekris, and F.S. Roberts in Resilience in the Digital Age, Springer, (2021), 75-101.

  • Rubik Tables and Object Rearrangement, by M. Szegedy and J. Yu, in The International Journal of Robotics Research, 2022, to appear.
  • Visual Foresight Trees for Object Retrieval From Clutter With Nonprehensile Rearrangement, by B. Huang, S. D. Han, J. Yu and A. Boularias, in IEEE Robotics and Automation Letters, vol. 7, no. 1, pp. 231-238, Jan. 2022, doi: 10.1109/LRA.2021.3123373.
  • Capacitated Vehicle Routing with Target Geometric Constraints, by K. Gao and J. Yu, in 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2021, pp. 7925-7930, doi: 10.1109/IROS51168.2021.9636123.
  • Rearrangement on Lattices with Pick-n-Swaps: Optimality Structures and Efficient Algorithms, by Yu, Jingjin, in Robotics: Sciences and Systems, 2021.
  • On Running Buffer Minimization for Tabletop Rearrangement, by Gao, Kai, Si Wei Feng, and Jingjin Yu, in Robotics: Sciences and Systems, 2021.
  • DIPN: Deep Interaction Prediction Network with Application to Clutter Removal, by B. Huang, S. D. Han, A. Boularias and J. Yu, in 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 4694-4701, doi: 10.1109/ICRA48506.2021.9561073.
  • On Rearrangement of Items Stored in Stacks, by Mario Szegedy and Jingjin Yu, in The 14th International Workshop on the Algorithmic Foundations of Robotics (Wafr), 2020, [pdf] [bib]

  • Analysis of the Ball-Majumdar potential in the Landau-de Gennes theory: An elementary approach, by X. Lu, X. Xu, and W. Zhang, submitted, 2020, [bib]

  • Adversarial robustness via robust low rank representations, by Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, and Aravindan Vijayaraghavan, submitted to NeurIPS, 2020, [pdf] [bib]

  • Adaptive Sampling to Reduce Disparate Performance, by Jacob Abernethy, Pranjal Awasthi, Matthäus Kleindessner, Jamie Morgenstern, and Jie Zhang, submitted to NeurIPS, 2020, [pdf] [bib]

  • A Notion of Individual Fairness for Clustering, by Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern, submitted to NeurIPS, 2020, [pdf] [bib]

  • Limit distribution theory for block estimators in multiple isotonic regression, by Qiyang Han and Cun-Hui Zhang, in Annals of Statistics, 2020, [pdf] [bib]

  • Isotonic regression in multi-dimensional spaces and graphs, by Hang Deng and Cun-Hui Zhang, in Annals of Statistics, 2020, [pdf] [bib]

  • Factor Models for High-Dimensional Tensor Time Series, by Rong Chen, Dan Yang, and Cun-Hui Zhang, submitted to Journal of American Statistical Association, 2020, [pdf] [bib]

  • Beyond Gaussian approximation: Bootstrap for maxima of sums of independent random vectors, by Hang Deng, and Cun-Hui Zhang, to appear in Annals of Statistics, 2017, [pdf] [bib]

  • Factor Models for High-Dimensional Tensor Time Series, by Rong Chen, Dan Yang, and Cun-hui Zhang, arXiv preprint, 2020, [pdf] [bib]

  • Tensor Factor Model Estimation by Iterative Projection, by Yuefeng Han, Rong Chen, Dan Yang, and Cun-Hui Zhang, arXiv preprint, 2020, [pdf] [bib]

  • Data Science and Resilience, by Fred Roberts, in Resilience in the Digital Age, Springer, 2021, [pdf] [bib]

  • Resilience Algorithms in Complex Networks, by Fred Roberts, in Resilience in the Digital Age, Springer, 2021, [pdf] [bib]

Presentations

  • Digital Twins and their Applications – invited talk by Fred Roberts at CBP-ADEPT workshop, Northeastern University, August 2022 [virtual].
  • Graph-theoretical Models of the Spread and Control of Disease and of Fighting Fires – Plenary talk by Fred Roberts at International Conference on Matrix Theory with Applications to Combinatorics, Optimization and Data Science, Cheju Island, Korea, December 2022 [virtual].
  • Graph-theoretical Models of the Spread and Control of Disease and of Fighting Fires – Invited talk by Fred Roberts at International Conference on Data Analysis, Optimization and their Applications, Moscow, January 2023 [virtual].
  • AI and Homeland Security – talk by Fred Roberts at Colloquium on AI4IA: Artificial Intelligence for Intelligence Analysis, City College of New York, October 2021. [virtual]
  • AI and Disasters – talk by Fred Roberts at Conference on Transformative Disaster Risk Governance, York University, Toronto, Canada, April 2021. [virtual]
  • New Mathematically-based Tools of Systems Analysis and Related Decision Support Applications – talk by Fred Roberts at Conference on Systems Analysis in Eurasia, National University of Science and Technology, Moscow, Russia, April 2021. [virtual]
  • Toward scalable and optimal autonomy – seminar talk by Jingjin Yu at Rutgers, October 25, 2019
  • Rate of convergence of optimal transport problem – seminar talk by Wujun Zhang at Finite Element Circus, Virginia Tech, November 1-2, 2019
  • A Finite element method for nematic liquid crystals with variable degree of orientation – paper presentation by Wujun Zhang at SIAM Conference on Analysis of Partial Differential Equations, December 11 – 14, 2019
  • Adversarial robustness via low dimensional representations – paper presentation by Pranjal Awasthi at Google ML Seminar, March 2020
  • Meaningless Statements About Performance of Intelligent Machines in Emergency Management – seminar talk by Fred Roberts at Missouri University of Science and Technology, November 2020 [pdf]
  • Meaningless Statements in Performance Measurement for Intelligent Machines – seminar talk by Fred Roberts at Tufts, May 2020 [pdf]

Selected Team Presentations