Goal Recognition is the task by which an observer aims to discern the goals that correspond to plans that comply with the perceived behavior of subject agents given as a sequence of observations. Research on Goal Recognition as Planning encompasses reasoning about the model of a planning task, the observations, and the goals using planning techniques, resulting in very efficient recognition approaches. In this article, we design novel recognition approaches that rely on the Operator-Counting framework, proposing new constraints, and analyze their constraints' properties both theoretically and empirically. The Operator-Counting framework is a technique that efficiently computes heuristic estimates of cost-to-goal using Integer/Linear Programming (IP/LP). In the realm of theory, we prove that the new constraints provide lower bounds on the cost of plans that comply with observations. We also provide an extensive empirical evaluation to assess how the new constraints improve the quality of the solution, and we found that they are especially informed in deciding which goals are unlikely to be part of the solution. Our novel recognition approaches have two pivotal advantages: first, they employ new IP/LP constraints for efficiently recognizing goals; second, we show how the new IP/LP constraints can improve the recognition of goals under both partial and noisy observability.

Complex multi-objective missions require the coordination of heterogeneous robots at multiple inter-connected levels, such as coalition formation, scheduling, and motion planning. The associated challenges are exacerbated when solutions to these interconnected problems need to both maximize task performance and respect practical constraints on time and resources. In this work, we formulate a new class of spatio-temporal heterogeneous task allocation problems that consider these complexities. We contribute a novel framework, named Quality-Optimized Incremental Task Allocation Graph Search (Q-ITAGS), to solve such problems. Q-ITAGS builds upon our prior work in trait-based coordination and offers a flexible interleaved framework that i) explicitly models and optimizes the effect of collective capabilities on task performance via learnable trait-quality maps, and ii) respects both resource constraints and spatio-temporal constraints, including a user-specified time budget (i.e., maximum makespan). In addition to algorithmic contributions, we derive theoretical suboptimality bounds in terms of task performance that varies as a function of a single hyperparameter. Our detailed experiments involving a simulated emergency response task and a real-world video game dataset reveal that i) Q-ITAGS results in superior team performance compared to a state-of-the-art method, while also respecting complex spatio-temporal and resource constraints, ii) Q-ITAGS efficiently learns trait-quality maps to enable effective trade-off between task performance and resource constraints, and iii) Q-ITAGS' suboptimality bounds consistently hold in practice.

In their work Resource Democratization: Is Compute the Binding Constraint on AI Research?, presented at AAAI 2024, Rebecca Gelles, Veronica Kinoshita, Micah Musser and James Dunham investigate researchers' access to compute and the impact this has on their work. In this interview, Rebecca and Ronnie tell us about what inspired their study, their methodology and some of their main findings. We wanted to engage directly with AI researchers to understand their resource constraints when deciding what types of research to dedicate their time to. We also wanted to dig deeper and try to understand how resource constraints play out across the AI research community – particularly looking at divides between industry and academia, a popular topic of discussions about AI resource constraints. The reason we were interested in this question is that there's a lot of discourse, particularly from the policy community, about the democratization of AI, addressing inequities in the field, and the fear that progress in AI may be held back by resource constraints.

We study the algorithmic task of finding large independent sets in Erdos-Renyi $r$-uniform hypergraphs on $n$ vertices having average degree $d$. Krivelevich and Sudakov showed that the maximum independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$. We show that the class of low-degree polynomial algorithms can find independent sets of density $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$ but no larger. This extends and generalizes earlier results of Gamarnik and Sudan, Rahman and Virag, and Wein on graphs, and answers a question of Bal and Bennett. We conjecture that this statistical-computational gap holds for this problem. Additionally, we explore the universality of this gap by examining $r$-partite hypergraphs. A hypergraph $H=(V,E)$ is $r$-partite if there is a partition $V=V_1\cup\cdots\cup V_r$ such that each edge contains exactly one vertex from each set $V_i$. We consider the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random $r$-partite hypergraphs with $n$ vertices in each partition and average degree $d$. We prove that the maximum balanced independent set has density $\left(\frac{r\log d}{(r-1)d}\right)^{1/(r-1)}$ asymptotically. Furthermore, we prove an analogous low-degree computational threshold of $\left(\frac{\log d}{(r-1)d}\right)^{1/(r-1)}$. Our results recover and generalize recent work of Perkins and the second author on bipartite graphs. While the graph case has been extensively studied, this work is the first to consider statistical-computational gaps of optimization problems on random hypergraphs. Our results suggest that these gaps persist for larger uniformities as well as across many models. A somewhat surprising aspect of the gap for balanced independent sets is that the algorithm achieving the lower bound is a simple degree-1 polynomial.

This study investigates learning from demonstration (LfD) for contact-rich tasks. The procedure for choosing a task frame to express the learned signals for the motion and interaction wrench is often omitted or using expert insight. This article presents a procedure to derive the optimal task frame from motion and wrench data recorded during the demonstration. The procedure is based on two principles that are hypothesized to underpin the control configuration targeted by an expert, and assumes task frame origins and orientations that are fixed to either the world or the robot tool. It is rooted in screw theory, is entirely probabilistic and does not involve any hyperparameters. The procedure was validated by demonstrating several tasks, including surface following and manipulation of articulated objects, showing good agreement between the obtained and the assumed expert task frames. To validate the performance of the learned tasks by a UR10e robot, a constraint-based controller was designed based on the derived task frames and the learned data expressed therein. These experiments showed the effectiveness and versatility of the proposed approach. The task frame derivation approach fills a gap in the state of the art of LfD, bringing LfD for contact-rich tasks closer to practical application.

Integer Linear Programming (ILP) has been proposed as a formalism for encoding precise structural and semantic constraints for Natural Language Inference (NLI). However, traditional ILP frameworks are non-differentiable, posing critical challenges for the integration of continuous language representations based on deep learning. In this paper, we introduce a novel approach, named Diff-Comb Explainer, a neuro-symbolic architecture for explanation-based NLI based on Differentiable BlackBox Combinatorial Solvers (DBCS). Differently from existing neuro-symbolic solvers, Diff-Comb Explainer does not necessitate a continuous relaxation of the semantic constraints, enabling a direct, more precise, and efficient incorporation of neural representations into the ILP formulation. Our experiments demonstrate that Diff-Comb Explainer achieves superior performance when compared to conventional ILP solvers, neuro-symbolic black-box solvers, and Transformer-based encoders. Moreover, a deeper analysis reveals that Diff-Comb Explainer can significantly improve the precision, consistency, and faithfulness of the constructed explanations, opening new opportunities for research on neuro-symbolic architectures for explainable and transparent NLI in complex domains.

This paper addresses the challenge of object-centric layout generation under spatial constraints, seen in multiple domains including floorplan design process. The design process typically involves specifying a set of spatial constraints that include object attributes like size and inter-object relations such as relative positioning. Existing works, which typically represent objects as single nodes, lack the granularity to accurately model complex interactions between objects. F or instance, often only certain parts of an object, like a room's right wall, interact with adjacent objects. T o address this gap, we introduce a factor graph based approach with four latent variable nodes for each room, and a factor node for each constraint. The factor nodes represent dependencies among the variables to which they are connected, effectively capturing constraints that are potentially of a higher order . W e then develop message-passing on the bipartite graph, forming a factor graph neural network that is trained to produce a floorplan that aligns with the desired requirements. Our approach is simple and generates layouts faithful to the user requirements, demonstrated by a large improvement in IOU scores over existing methods. Additionally, our approach, being inferential and accurate, is well-suited to the practical human-in-the-loop design process where specifications evolve iteratively, offering a practical and powerful tool for AI-guided design.

In the field of control engineering, the connection between Signal Temporal Logic (STL) and time-varying Control Barrier Functions (CBF) has attracted considerable attention. CBFs have demonstrated notable success in ensuring the safety of critical applications by imposing constraints on system states, while STL allows for precisely specifying spatio-temporal constraints on the behavior of robotic systems. Leveraging these methodologies, this paper addresses the safety-critical navigation problem, in Socially Responsible Navigation (SRN) context, presenting a CBF-based STL motion planning methodology. This methodology enables task completion at any time within a specified time interval considering a dynamic system subject to velocity constraints. The proposed approach involves real-time computation of a smooth CBF, with the computation of a dynamically adjusted parameter based on the available path space and the maximum allowable velocity. A simulation study is conducted to validate the methodology, ensuring safety in the presence of static and dynamic obstacles and demonstrating its compliance with spatio-temporal constraints under non-linear velocity constraints.

Assembly processes involving humans and robots are challenging scenarios because the individual activities and access to shared workspace have to be coordinated. Fixed robot programs leave no room to diverge from a fixed protocol. Working on such a process can be stressful for the user and lead to ineffective behavior or failure. We propose a novel approach of online constraint-based scheduling in a reactive execution control framework facilitating behavior trees called CoBOS. This allows the robot to adapt to uncertain events such as delayed activity completions and activity selection (by the human). The user will experience less stress as the robotic coworkers adapt their behavior to best complement the human-selected activities to complete the common task. In addition to the improved working conditions, our algorithm leads to increased efficiency, even in highly uncertain scenarios. We evaluate our algorithm using a probabilistic simulation study with 56000 experiments. We outperform all baselines by a margin of 4-10%. Initial real robot experiments using a Franka Emika Panda robot and human tracking based on HTC Vive VR gloves look promising.

The domain of explainable AI is of interest in all Machine Learning fields, and it is all the more important in clustering, an unsupervised task whose result must be validated by a domain expert. We aim at finding a clustering that has high quality in terms of classic clustering criteria and that is explainable, and we argue that these two dimensions must be considered when building the clustering. We consider that a good global explanation of a clustering should give the characteristics of each cluster taking into account their abilities to describe its objects (coverage) while distinguishing it from the other clusters (discrimination). Furthermore, we aim at leveraging expert knowledge, at different levels, on the structure of the expected clustering or on its explanations. In our framework an explanation of a cluster is a set of patterns, and we propose a novel interpretable constrained clustering method called ECS for declarative clustering with Explainabilty-driven Cluster Selection that integrates structural or domain expert knowledge expressed by means of constraints. It is based on the notion of coverage and discrimination that are formalized at different levels (cluster / clustering), each allowing for exceptions through parameterized thresholds. Our method relies on four steps: generation of a set of partitions, computation of frequent patterns for each cluster, pruning clusters that violates some constraints, and selection of clusters and associated patterns to build an interpretable clustering. This last step is combinatorial and we have developed a Constraint-Programming (CP) model to solve it. The method can integrate prior knowledge in the form of user constraints, both before or in the CP model.