With the rapid progress in Multi-Agent Path Finding (MAPF), researchers have studied how MAPF algorithms can be deployed to coordinate hundreds of robots in large automated warehouses. While most works try to improve the throughput of such warehouses by developing better MAPF algorithms, we focus on improving the throughput by optimizing the warehouse layout. We show that, even with state-of-the-art MAPF algorithms, commonly used human-designed layouts can lead to congestion for warehouses with large numbers of robots and thus have limited scalability. We extend existing automatic scenario generation methods to optimize warehouse layouts. Results show that our optimized warehouse layouts (1) reduce traffic congestion and thus improve throughput, (2) improve the scalability of the automated warehouses by doubling the number of robots in some cases, and (3) are capable of generating layouts with user-specified diversity measures. We include the source code at: //github.com/lunjohnzhang/warehouse_env_gen_public
We present Adaptive Skill Coordination (ASC) -- an approach for accomplishing long-horizon tasks like mobile pick-and-place (i.e., navigating to an object, picking it, navigating to another location, and placing it). ASC consists of three components -- (1) a library of basic visuomotor skills (navigation, pick, place), (2) a skill coordination policy that chooses which skill to use when, and (3) a corrective policy that adapts pre-trained skills in out-of-distribution states. All components of ASC rely only on onboard visual and proprioceptive sensing, without requiring information like detailed maps with obstacle layouts or precise object locations, easing real-world deployment. We train ASC in simulated indoor environments, and deploy it zero-shot (without any real-world experience or fine-tuning) on the Boston Dynamics Spot robot in 8 novel real-world environments (1 apartment, 1 lab, 2 microkitchens, 2 lounges, 1 office space, 1 outdoor courtyard). In rigorous quantitative comparisons in 2 environments, ASC achieves near-perfect performance (59/60 episodes, or 98%), while sequentially executing skills succeeds in only 44/60 (73%) episodes. Extensive perturbation experiments show that ASC is robust to hand-off errors, changes in the environment layout, dynamic obstacles (e.g., people), and unexpected disturbances. Supplementary videos at adaptiveskillcoordination.github.io.
Integrating coded caching (CC) techniques into multi-input multi-output (MIMO) setups provides a substantial performance boost in terms of the achievable degrees of freedom (DoF). In this paper, we study cache-aided MIMO setups where a single server with $L$ transmit antennas communicates with a number of users each with $G$ receive antennas. We extend a baseline CC scheme, originally designed for multi-input single-output (MISO) systems, to the considered MIMO setup. However, in a proposed MIMO approach, instead of merely replicating the transmit strategy from the baseline MISO scheme, we adjust the number of users served in each transmission to maximize the achievable DoF. This approach not only makes the extension more flexible in terms of supported network parameters but also results in an improved DoF of $\max_{\beta \le G} \beta \lfloor \frac{L-1}{\beta} \rfloor + \beta (t+1)$, where $t$ is the coded caching gain. In addition, we also propose a high-performance multicast transmission design for the considered MIMO-CC setup by formulating a symmetric rate maximization problem in terms of the transmit covariance matrices for the multicast signals and solving the resulting non-convex problem using successive convex approximation. Finally, we use numerical simulations to verify both improved DoF results and enhanced MIMO multicasting performance.
The multiple-choice knapsack problem (MCKP) is a classic NP-hard combinatorial optimization problem. Motivated by several significant practical applications, this work investigates a novel variant of MCKP called data-driven chance-constrained multiple-choice knapsack problem (DDCCMCKP), where the item weight is a random variable with unknown probability distribution. We first present the problem formulation of DDCCMCKP, and then establish two benchmark sets. The first set contains synthetic instances, and the second set is devised to simulate a real-world application scenario of a certain telecommunication company. To solve DDCCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm. The main merit of DDALS lies in evaluating solutions with chance constraints by data-driven methods, under the condition of unknown distributions and only historical sample data being available. The experimental results demonstrate the effectiveness of the proposed algorithm and show that it is superior to other baselines. Additionally, ablation experiments confirm the necessity of each component in the algorithm. Our proposed algorithm can serve as the baseline for future research, and the code and benchmark sets will be open-sourced to further promote research on this challenging problem.
Frequency range 2 (FR2) has become an integral part of 5G networks to fulfill the ever-increasing demand for data hungry-applications. However, radio signals in FR2 experience high path and diffraction loss, which also pronounces the problem of inter and intra-cell interference. As a result, both the serving and target links are affected, leading to radio link failures (RLFs) and handover failures (HOFs), respectively. To address this issue, multi-panel user equipment (MPUE) is proposed for 5G-Advanced whereby multiple spatially distinct antenna panels are integrated into the UE to leverage gains from antenna directivity. It also opens the possibility of using UE-side Rx-beamforming for each panel. In this paper, three different Rx-beamforming approaches are proposed to improve the serving link, the target link, and the handover process for an MPUE equipped with three directional panels. Thereafter, the mobility performance is analyzed in a system-level simulation for a multi-beam FR2 network. Results have shown that the proposed schemes can help reduce RLFs by 53\% and HOFs by 90\%.
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
In this paper, we use Prior-data Fitted Networks (PFNs) as a flexible surrogate for Bayesian Optimization (BO). PFNs are neural processes that are trained to approximate the posterior predictive distribution (PPD) through in-context learning on any prior distribution that can be efficiently sampled from. We describe how this flexibility can be exploited for surrogate modeling in BO. We use PFNs to mimic a naive Gaussian process (GP), an advanced GP, and a Bayesian Neural Network (BNN). In addition, we show how to incorporate further information into the prior, such as allowing hints about the position of optima (user priors), ignoring irrelevant dimensions, and performing non-myopic BO by learning the acquisition function. The flexibility underlying these extensions opens up vast possibilities for using PFNs for BO. We demonstrate the usefulness of PFNs for BO in a large-scale evaluation on artificial GP samples and three different hyperparameter optimization testbeds: HPO-B, Bayesmark, and PD1. We publish code alongside trained models at //github.com/automl/PFNs4BO.
In conventional joint communications and sensing (JCAS) designs for multi-carrier multiple-input multiple-output (MIMO) systems, the dual-functional waveforms are often optimized for the whole frequency band, resulting in limited communications--sensing performance tradeoff. To overcome the limitation, we propose employing a subset of subcarriers for JCAS, while the communications function is performed over all the subcarriers. This offers more degrees of freedom to enhance the communications performance under a given sensing accuracy. We first formulate the rate maximization under the sensing accuracy constraint to optimize the beamformers and JCAS subcarriers. The problem is solved via Riemannian manifold optimization and closed-form solutions. Numerical results for an 8x4 MIMO system with 64 subcarriers show that compared to the conventional subcarrier sharing scheme, the proposed scheme employing 16 JCAS subcarriers offers 60% improvement in the achievable communications rate at the signal-to-noise ratio of 10 dB. Meanwhile, this scheme generates the sensing beampattern with the same quality as the conventional JCAS design.
We study the problem of imputing missing values in a dataset, which has important applications in many domains. The key to missing value imputation is to capture the data distribution with incomplete samples and impute the missing values accordingly. In this paper, by leveraging the fact that any two batches of data with missing values come from the same data distribution, we propose to impute the missing values of two batches of samples by transforming them into a latent space through deep invertible functions and matching them distributionally. To learn the transformations and impute the missing values simultaneously, a simple and well-motivated algorithm is proposed. Our algorithm has fewer hyperparameters to fine-tune and generates high-quality imputations regardless of how missing values are generated. Extensive experiments over a large number of datasets and competing benchmark algorithms show that our method achieves state-of-the-art performance.
This paper aims to mitigate straggler effects in synchronous distributed learning for multi-agent reinforcement learning (MARL) problems. Stragglers arise frequently in a distributed learning system, due to the existence of various system disturbances such as slow-downs or failures of compute nodes and communication bottlenecks. To resolve this issue, we propose a coded distributed learning framework, which speeds up the training of MARL algorithms in the presence of stragglers, while maintaining the same accuracy as the centralized approach. As an illustration, a coded distributed version of the multi-agent deep deterministic policy gradient(MADDPG) algorithm is developed and evaluated. Different coding schemes, including maximum distance separable (MDS)code, random sparse code, replication-based code, and regular low density parity check (LDPC) code are also investigated. Simulations in several multi-robot problems demonstrate the promising performance of the proposed framework.
Retrieving object instances among cluttered scenes efficiently requires compact yet comprehensive regional image representations. Intuitively, object semantics can help build the index that focuses on the most relevant regions. However, due to the lack of bounding-box datasets for objects of interest among retrieval benchmarks, most recent work on regional representations has focused on either uniform or class-agnostic region selection. In this paper, we first fill the void by providing a new dataset of landmark bounding boxes, based on the Google Landmarks dataset, that includes $94k$ images with manually curated boxes from $15k$ unique landmarks. Then, we demonstrate how a trained landmark detector, using our new dataset, can be leveraged to index image regions and improve retrieval accuracy while being much more efficient than existing regional methods. In addition, we further introduce a novel regional aggregated selective match kernel (R-ASMK) to effectively combine information from detected regions into an improved holistic image representation. R-ASMK boosts image retrieval accuracy substantially at no additional memory cost, while even outperforming systems that index image regions independently. Our complete image retrieval system improves upon the previous state-of-the-art by significant margins on the Revisited Oxford and Paris datasets. Code and data will be released.