We consider a new type of inverse combinatorial optimization, Inverse Submodular Maximization (ISM), for human-in-the-loop multi-robot coordination. Forward combinatorial optimization, defined as the process of solving a combinatorial problem given the reward (cost)-related parameters, is widely used in multi-robot coordination. In the standard pipeline, the reward (cost)-related parameters are designed offline by domain experts first and then these parameters are utilized for coordinating robots online. What if we need to change these parameters by non-expert human supervisors who watch over the robots during tasks to adapt to some new requirements? We are interested in the case where human supervisors can suggest what actions to take, and the robots need to change the internal parameters based on such suggestions. We study such problems from the perspective of inverse combinatorial optimization, i.e., the process of finding parameters given solutions to the problem. Specifically, we propose a new formulation for ISM, in which we aim to find a new set of parameters that minimally deviate from the current parameters and can make the greedy algorithm output actions the same as those suggested by humans. We show that such problems can be formulated as a Mixed Integer Quadratic Program (MIQP). However, MIQP involves exponentially many binary variables, making it intractable for the existing solver when the problem size is large. We propose a new algorithm under the Branch $\&$ Bound paradigm to solve such problems. In numerical simulations, we demonstrate how to use ISM in multi-robot multi-objective coverage control, and we show that the proposed algorithm achieves significant advantages in running time and peak memory usage compared to directly using an existing solver.
相關內容
Intelligent reflecting surfaces (IRSs) are a promising low-cost solution for achieving high spectral and energy efficiency in future communication systems by enabling the customization of wireless propagation environments. Despite the plethora of research on resource allocation design for IRS-assisted multiuser wireless communication systems, the optimal design and the corresponding performance upper bound are still not fully understood. To bridge this gap in knowledge, in this paper, we investigate the optimal resource allocation design for IRS-assisted multiuser multiple-input single-output systems employing practical discrete IRS phase shifters. In particular, we jointly optimize the beamforming vector at the base station and the discrete IRS phase shifts to minimize the total transmit power for the cases of perfect and imperfect channel state information (CSI) knowledge. To this end, two novel algorithms based on the generalized Benders decomposition (GBD) method are developed to obtain the globally optimal solution for perfect and imperfect CSI, respectively. Moreover, to facilitate practical implementation, we propose two corresponding low-complexity suboptimal algorithms with guaranteed convergence by capitalizing on successive convex approximation (SCA). In particular, for imperfect CSI, we adopt a bounded error model to characterize the CSI uncertainty and propose a new transformation to convexify the robust quality-of-service constraints. Our numerical results confirm the optimality of the proposed GBD-based algorithms for the considered system for both perfect and imperfect CSI. Furthermore, we unveil that both proposed SCA-based algorithms can attain a locally optimal solution within a few iterations. Moreover, compared with the state-of-the-art solution based on alternating optimization, the proposed low-complexity SCA-based schemes achieve a significant performance gain.
In the past few decades, many multiobjective evolutionary optimization algorithms (MOEAs) have been proposed to find a finite set of approximate Pareto solutions for a given problem in a single run, each with its own structure. However, in many real-world applications, it could be desirable to have structure constraints on the entire optimal solution set, which define the patterns shared among all solutions. The current population-based MOEAs cannot properly handle such requirements. In this work, we make the first attempt to incorporate the structure constraints into the whole solution set by a single Pareto set model, which can be efficiently learned by a simple evolutionary stochastic optimization method. With our proposed method, the decision-makers can flexibly trade off the Pareto optimality with preferred structures among all solutions, which is not supported by previous MOEAs. A set of experiments on benchmark test suites and real-world application problems fully demonstrates the efficiency of our proposed method.
Electromagneto-quasistatic (EMQS) field formulations are often dubbed as Darwin-type field formulations which approximate the Maxwell equations by neglecting radiation effects while modelling resistive, capacitive, and inductive effects. A common feature of EMQS field models is the Darwin-Amp\'ere equation formulated with the magnetic vector potential and the electric scalar potential. EMQS field formulations yield different approximations to the Maxwell equations by choice of additional gauge equations. These EMQS formulations are analyzed within the port-Hamiltonian system (PHS) framework. It is shown via the PHS compatibility equation that formulations based on the combination of the Darwin-Amp\'ere equation and the full Maxwell continuity equation yield port-Hamiltonian systems implying numerical stability and specific EMQS energy conservation.
The incorporation of generative models as regularisers within variational formulations for inverse problems has proven effective across numerous image reconstruction tasks. However, the resulting optimisation problem is often non-convex and challenging to solve. In this work, we show that score-based generative models (SGMs) can be used in a graduated optimisation framework to solve inverse problems. We show that the resulting graduated non-convexity flow converge to stationary points of the original problem and provide a numerical convergence analysis of a 2D toy example. We further provide experiments on computed tomography image reconstruction, where we show that this framework is able to recover high-quality images, independent of the initial value. The experiments highlight the potential of using SGMs in graduated optimisation frameworks.
We utilize extreme learning machines for the prediction of partial differential equations (PDEs). Our method splits the state space into multiple windows that are predicted individually using a single model. Despite requiring only few data points (in some cases, our method can learn from a single full-state snapshot), it still achieves high accuracy and can predict the flow of PDEs over long time horizons. Moreover, we show how additional symmetries can be exploited to increase sample efficiency and to enforce equivariance.
Reconfigurable Intelligent Surface (RIS) modeling and optimization are a crucial steps in developing the next generation of wireless communications. To this aim, the availability of accurate electromagnetic (EM) models is of paramount important for the design of RIS-assisted communication links. In this work, we validate a widely-used analytical multiport network for RISs by means of a well-established full-wave numerical method based on the Partial Elements Equivalent Circuit (PEEC) approach. Numerical results show good agreement between the two methods, thus demonstrating i) the considered multiport network model being effective and ii) the PEEC method being appropriate for EM modeling of RIS-assisted wireless links.
Candecomp / PARAFAC (CP) decomposition, a generalization of the matrix singular value decomposition to higher-dimensional tensors, is a popular tool for analyzing multidimensional sparse data. On tensors with billions of nonzero entries, computing a CP decomposition is a computationally intensive task. We propose the first distributed-memory implementations of two randomized CP decomposition algorithms, CP-ARLS-LEV and STS-CP, that offer nearly an order-of-magnitude speedup at high decomposition ranks over well-tuned non-randomized decomposition packages. Both algorithms rely on leverage score sampling and enjoy strong theoretical guarantees, each with varying time and accuracy tradeoffs. We tailor the communication schedule for our random sampling algorithms, eliminating expensive reduction collectives and forcing communication costs to scale with the random sample count. Finally, we optimize the local storage format for our methods, switching between analogues of compressed sparse column and compressed sparse row formats. Experiments show that our methods are fast and scalable, producing 11x speedup over SPLATT by decomposing the billion-scale Reddit tensor on 512 CPU cores in under two minutes.
This research explores the application of Large Language Models (LLMs) for automating the extraction of requirement-related legal content in the food safety domain and checking legal compliance of regulatory artifacts. With Industry 4.0 revolutionizing the food industry and with the General Data Protection Regulation (GDPR) reshaping privacy policies and data processing agreements, there is a growing gap between regulatory analysis and recent technological advancements. This study aims to bridge this gap by leveraging LLMs, namely BERT and GPT models, to accurately classify legal provisions and automate compliance checks. Our findings demonstrate promising results, indicating LLMs' significant potential to enhance legal compliance and regulatory analysis efficiency, notably by reducing manual workload and improving accuracy within reasonable time and financial constraints.
We investigate the role of various demonstration components in the in-context learning (ICL) performance of large language models (LLMs). Specifically, we explore the impacts of ground-truth labels, input distribution, and complementary explanations, particularly when these are altered or perturbed. We build on previous work, which offers mixed findings on how these elements influence ICL. To probe these questions, we employ explainable NLP (XNLP) methods and utilize saliency maps of contrastive demonstrations for both qualitative and quantitative analysis. Our findings reveal that flipping ground-truth labels significantly affects the saliency, though it's more noticeable in larger LLMs. Our analysis of the input distribution at a granular level reveals that changing sentiment-indicative terms in a sentiment analysis task to neutral ones does not have as substantial an impact as altering ground-truth labels. Finally, we find that the effectiveness of complementary explanations in boosting ICL performance is task-dependent, with limited benefits seen in sentiment analysis tasks compared to symbolic reasoning tasks. These insights are critical for understanding the functionality of LLMs and guiding the development of effective demonstrations, which is increasingly relevant in light of the growing use of LLMs in applications such as ChatGPT. Our research code is publicly available at //github.com/paihengxu/XICL.
In this paper we consider the filtering problem associated to partially observed McKean-Vlasov stochastic differential equations (SDEs). The model consists of data that are observed at regular and discrete times and the objective is to compute the conditional expectation of (functionals) of the solutions of the SDE at the current time. This problem, even the ordinary SDE case is challenging and requires numerical approximations. Based upon the ideas in [3, 12] we develop a new particle filter (PF) and multilevel particle filter (MLPF) to approximate the afore-mentioned expectations. We prove under assumptions that, for $\epsilon>0$, to obtain a mean square error of $\mathcal{O}(\epsilon^2)$ the PF has a cost per-observation time of $\mathcal{O}(\epsilon^{-5})$ and the MLPF costs $\mathcal{O}(\epsilon^{-4})$ (best case) or $\mathcal{O}(\epsilon^{-4}\log(\epsilon)^2)$ (worst case). Our theoretical results are supported by numerical experiments.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191