Alessandra Russo

TMLR Journal 2026 Journal Article

$\texttt{SEM-CTRL}$: Semantically Controlled Decoding

• Mohammad Albinhassan
• Pranava Madhyastha
• Alessandra Russo

Ensuring both syntactic and semantic correctness in Large Language Model (LLM) outputs remains a significant challenge, despite being critical for real-world deployment. In this paper, we introduce $\texttt{SEM-CTRL}$, a unified approach that allows for enforcing rich context-sensitive constraints, and task and instance specific semantics directly on the LLM decoder. Our approach integrates token-level MCTS which is guided by specific syntactic and semantic constraints. The constraints over desired outputs are expressed using Answer Set Grammars, which is a logic-based formalism that generalizes context sensitive grammars while incorporating background knowledge to represent task-specific semantics. We show that our approach helps guarantee valid completions for any off-the-shelf LLM without the need for fine-tuning. We evaluate $\texttt{SEM-CTRL}$ on a range of tasks, including synthetic grammar synthesis, combinatorial reasoning, JSON parsing, and planning. Our experimental results demonstrate that $\texttt{SEM-CTRL}$ allows even small pre-trained LLMs to efficiently outperform larger variants and state-of-the-art reasoning models (e.g., $\text{\textit{o4-mini}}$) while simultaneously guaranteeing semantic validity.

AAAI Conference 2026 Conference Paper

Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs

• Daniel Furelos-Blanco
• Charles Pert
• Frederik Kelbel
• Alex F. Spies
• Alessandra Russo
• Michael Dennis

Training general agents to follow complex instructions (tasks) in intricate environments (levels) remains a core challenge in reinforcement learning. Random sampling of task-level pairs often produces unsolvable combinations, highlighting the need to co-design tasks and levels. While unsupervised environment design (UED) has proven effective at automatically designing level curricula, prior work has only considered a fixed task. We present ATLAS (Aligning Tasks and Levels for Autocurricula of Specifications), a novel method that generates joint autocurricula over tasks and levels. Our approach builds upon UED to automatically produce solvable yet challenging task-level pairs for policy training. To evaluate ATLAS and drive progress in the field, we introduce an evaluation suite that models tasks as reward machines in Minigrid levels. Experiments demonstrate that ATLAS vastly outperforms random sampling approaches, particularly when sampling solvable pairs is unlikely. We further show that mutations leveraging the structure of both tasks and levels accelerate convergence to performant policies.

NeSy Conference 2025 Conference Paper

Disentangling Neural Disjunctive Normal Form Models

• Kexin Gu Baugh
• Vincent Perreault
• Matthew Baugh
• Luke Dickens
• Katsumi Inoue
• Alessandra Russo

Neural Disjunctive Normal Form (DNF) based models are powerful and interpretable approaches to neuro-symbolic learning and have shown promising results in classification and reinforcement learning settings without prior knowledge of the tasks. However, their performance is degraded by the thresholding of the post-training symbolic translation process. We show here that part of the performance degradation during translation is due to its failure to disentangle the learned knowledge represented in the form of the networks’ weights. We address this issue by proposing a new disentanglement method; by splitting nodes that encode nested rules into smaller independent nodes, we are able to better preserve the models’ performance. Through experiments on binary, multiclass, and multilabel classification tasks (including those requiring predicate invention), we demonstrate that our disentanglement method provides compact and interpretable logical representations for the neural DNF-based models, with performance closer to that of their pre-translation counterparts. Our code is available at https: //github. com/kittykg/disentangling-ndnf-classification.

AAMAS Conference 2025 Conference Paper

FORM: Learning Expressive and Transferable First-Order Logic Reward Machines

• Leo Ardon
• Daniel Furelos-Blanco
• Roko Parac
• Alessandra Russo

Reward machines (RMs) are an effective approach for addressing non-Markovian rewards in reinforcement learning (RL) through finite-state machines. Traditional RMs, which label edges with propositional logic formulae, inherit the limited expressivity of propositional logic. This limitation hinders the learnability and transferability of RMs since complex tasks will require numerous states and edges. To overcome these challenges, we propose First- Order Reward Machines (FORMs), which use first-order logic to label edges, resulting in more compact and transferable RMs. We introduce a novel method for learning FORMs and a multi-agent formulation for exploiting them and facilitate their transferability, where multiple agents collaboratively learn policies for a shared FORM. Our experimental results demonstrate the scalability of FORMs with respect to traditional RMs. Specifically, we show that FORMs can be effectively learnt for tasks where traditional RM learning approaches fail. We also show significant improvements in learning speed and task transferability thanks to the multi-agent learning framework and the abstraction provided by the first-order language.

AAMAS Conference 2025 Conference Paper

Neural DNF-MT: A Neuro-symbolic Approach for Learning Interpretable and Editable Policies

• Kexin Gu Baugh
• Luke Dickens
• Alessandra Russo

Although deep reinforcement learning has been shown to be effective, the model’s black-box nature presents barriers to direct policy interpretation. To address this problem, we propose a neurosymbolic approach called neural DNF-MT for end-to-end policy learning. The differentiable nature of the neural DNF-MT model enables the use of deep actor-critic algorithms for training. At the same time, its architecture is designed so that trained models can be directly translated into interpretable policies expressed as standard (bivalent or probabilistic) logic programs. Moreover, additional layers can be included to extract abstract features from complex observations, acting as a form of predicate invention. The logic representations are highly interpretable, and we show how the bivalent representations of deterministic policies can be edited and incorporated back into a neural model, facilitating manual intervention and adaptation of learned policies. We evaluate our approach on a range of tasks requiring learning deterministic or stochastic behaviours from various forms of observations. Our empirical results show that our neural DNF-MT model performs at the level of competing black-box methods whilst providing interpretable policies.

NeSy Conference 2024 Conference Paper

Embed2Rule Scalable Neuro-Symbolic Learning via Latent Space Weak-Labelling

• Yaniv Aspis
• Mohammad Albinhassan
• Jorge Lobo 0001
• Alessandra Russo

Abstract Neuro-symbolic approaches have garnered much interest recently as a path toward endowing neural systems with robust reasoning capabilities. Most proposed end-to-end methods assume knowledge to be given in advance and do not scale up over many latent concepts. The recently proposed Embed2Sym tackles the scalability limitation by performing end-to-end neural training of a visual perception component from downstream labels to generate clusters in the latent space of symbolic concepts. These are later used to perform downstream symbolic reasoning but symbolic knowledge is still engineered. Taking inspiration from Embed2Sym, this paper introduces a novel method for scalable neuro-symbolic learning of first-order logic programs from raw data. The learned clusters are optimally labelled using sampled predictions of a pre-trained vision-language model. A SOTA symbolic learner, robust to noise, uses these labels to learn an answer set program that solves the reasoning task. Our approach, called Embed2Rule, is shown to achieve better accuracy than SOTA neuro-symbolic systems on existing benchmark tasks in most cases while scaling up to tasks that require far more complex reasoning and a large number of latent concepts.

KR Conference 2024 Conference Paper

Learning Robust Reward Machines from Noisy Labels

• Roko Parać
• Lorenzo Nodari
• Leo Ardon
• Daniel Furelos-Blanco
• Federico Cerutti
• Alessandra Russo

This paper presents PROB-IRM, an approach that learns robust reward machines (RMs) for reinforcement learning (RL) agents from noisy execution traces. The key aspect of RM-driven RL is the exploitation of a finite-state ma- chine that decomposes the agent’s task into different sub- tasks. PROB-IRM uses a state-of-the-art inductive logic pro- gramming framework robust to noisy examples to learn RMs from noisy traces using the Bayesian posterior degree of be- liefs, thus ensuring robustness against inconsistencies. Piv- otal for the results is the interleaving between RM learning and policy learning: a new RM is learned whenever the RL agent generates a trace that is believed not to be accepted by the current RM. To speed up the training of the RL agent, PROB-IRM employs a probabilistic formulation of reward shaping that uses the posterior Bayesian beliefs derived from the traces. Our experimental analysis shows that PROB-IRM can learn (potentially imperfect) RMs from noisy traces and exploit them to train an RL agent to solve its tasks success- fully. Despite the complexity of learning the RM from noisy traces, agents trained with PROB-IRM perform comparably to agents provided with handcrafted RMs.

NeSy Conference 2024 Conference Paper

The Role of Foundation Models in Neuro-Symbolic Learning and Reasoning

• Daniel Cunnington
• Mark Law
• Jorge Lobo 0001
• Alessandra Russo

Abstract Neuro-Symbolic AI (NeSy) holds promise to ensure the safe deployment of AI systems, as interpretable symbolic techniques provide formal behaviour guarantees. The challenge is how to effectively integrate neural and symbolic computation, to enable learning and reasoning from raw data. Existing pipelines that train the neural and symbolic components sequentially require extensive labelling, whereas end-to-end approaches are limited in terms of scalability, due to the combinatorial explosion in the symbol grounding problem. In this paper, we leverage the implicit knowledge within foundation models to enhance the performance in NeSy tasks, whilst reducing the amount of data labelling and manual engineering. We introduce a new architecture, called NeSyGPT, which fine-tunes a vision-language foundation model to extract symbolic features from raw data, before learning a highly expressive answer set program to solve a downstream task. Our comprehensive evaluation demonstrates that NeSyGPT has superior accuracy over various baselines, and can scale to complex NeSy tasks. Finally, we highlight the effective use of a large language model to generate the programmatic interface between the neural and symbolic components, significantly reducing the amount of manual engineering required. The Appendix is presented in the longer version of this paper, which contains additional results and analysis [ 8 ].

ICML Conference 2023 Conference Paper

Hierarchies of Reward Machines

• Daniel Furelos-Blanco
• Mark Law
• Anders Jonsson 0001
• Krysia Broda
• Alessandra Russo

Reward machines (RMs) are a recent formalism for representing the reward function of a reinforcement learning task through a finite-state machine whose edges encode subgoals of the task using high-level events. The structure of RMs enables the decomposition of a task into simpler and independently solvable subtasks that help tackle long-horizon and/or sparse reward tasks. We propose a formalism for further abstracting the subtask structure by endowing an RM with the ability to call other RMs, thus composing a hierarchy of RMs (HRM). We exploit HRMs by treating each call to an RM as an independently solvable subtask using the options framework, and describe a curriculum-based method to learn HRMs from traces observed by the agent. Our experiments reveal that exploiting a handcrafted HRM leads to faster convergence than with a flat HRM, and that learning an HRM is feasible in cases where its equivalent flat representation is not.

IJCAI Conference 2023 Conference Paper

Neuro-Symbolic Learning of Answer Set Programs from Raw Data

• Daniel Cunnington
• Mark Law
• Jorge Lobo
• Alessandra Russo

One of the ultimate goals of Artificial Intelligence is to assist humans in complex decision making. A promising direction for achieving this goal is Neuro-Symbolic AI, which aims to combine the interpretability of symbolic techniques with the ability of deep learning to learn from raw data. However, most current approaches require manually engineered symbolic knowledge, and where end-to-end training is considered, such approaches are either restricted to learning definite programs, or are restricted to training binary neural networks. In this paper, we introduce Neuro-Symbolic Inductive Learner (NSIL), an approach that trains a general neural network to extract latent concepts from raw data, whilst learning symbolic knowledge that maps latent concepts to target labels. The novelty of our approach is a method for biasing the learning of symbolic knowledge, based on the in-training performance of both neural and symbolic components. We evaluate NSIL on three problem domains of different complexity, including an NP-complete problem. Our results demonstrate that NSIL learns expressive knowledge, solves computationally complex problems, and achieves state-of-the-art performance in terms of accuracy and data efficiency. Code and technical appendix: https: //github. com/DanCunnington/NSIL

IJCAI Conference 2022 Conference Paper

Detect, Understand, Act: A Neuro-Symbolic Hierarchical Reinforcement Learning Framework (Extended Abstract)

• Ludovico Mitchener
• David Tuckey
• Matthew Crosby
• Alessandra Russo

We introduce Detect, Understand, Act (DUA), a neuro-symbolic reinforcement learning framework. The Detect component is composed of a traditional computer vision object detector and tracker. The Act component houses a set of options, high-level actions enacted by pre-trained deep reinforcement learning (DRL) policies. The Understand component provides a novel answer set programming (ASP) paradigm for effectively learning symbolic meta-policies over options using inductive logic programming (ILP). We evaluate our framework on the Animal-AI (AAI) competition testbed, a set of physical cognitive reasoning problems. Given a set of pre-trained DRL policies, DUA requires only a few examples to learn a meta-policy that allows it to improve the state-of-the-art on multiple of the most challenging categories from the testbed. DUA constitutes the first holistic hybrid integration of computer vision, ILP and DRL applied to an AAI-like environment and sets the foundations for further use of ILP in complex DRL challenges.

KR Conference 2022 Conference Paper

Embed2Sym - Scalable Neuro-Symbolic Reasoning via Clustered Embeddings

• Yaniv Aspis
• Krysia Broda
• Jorge Lobo
• Alessandra Russo

Neuro-symbolic reasoning approaches proposed in recent years combine a neural perception component with a symbolic reasoning component to solve a downstream task. By doing so, these approaches can provide neural networks with symbolic reasoning capabilities, improve their interpretability and enable generalization beyond the training task. However, this often comes at the cost of poor training time, with potential scalability issues. In this paper, we propose a scalable neuro-symbolic approach, called Embed2Sym. We complement a two-stage (perception and reasoning) neural network architecture designed to solve a downstream task end-to-end with a symbolic optimisation method for extracting learned latent concepts. Specifically, the trained perception network generates clusters in embedding space that are identified and labelled using symbolic knowledge and a symbolic solver. With the latent concepts identified, a neuro-symbolic model is constructed by combining the perception network with the symbolic knowledge of the downstream task, resulting in a model that is interpretable and transferable. Our evaluation shows that Embed2Sym outperforms state-of-the-art neuro-symbolic systems on benchmark tasks in terms of training time by several orders of magnitude while providing similar if not better accuracy.

NeurIPS Conference 2022 Conference Paper

Formalizing Consistency and Coherence of Representation Learning

• Harald Strömfelt
• Luke Dickens
• Artur Garcez
• Alessandra Russo

In the study of reasoning in neural networks, recent efforts have sought to improve consistency and coherence of sequence models, leading to important developments in the area of neuro-symbolic AI. In symbolic AI, the concepts of consistency and coherence can be defined and verified formally, but for neural networks these definitions are lacking. The provision of such formal definitions is crucial to offer a common basis for the quantitative evaluation and systematic comparison of connectionist, neuro-symbolic and transfer learning approaches. In this paper, we introduce formal definitions of consistency and coherence for neural systems. To illustrate the usefulness of our definitions, we propose a new dynamic relation-decoder model built around the principles of consistency and coherence. We compare our results with several existing relation-decoders using a partial transfer learning task based on a novel data set introduced in this paper. Our experiments show that relation-decoders that maintain consistency over unobserved regions of representation space retaincoherence across domains, whilst achieving better transfer learning performance.

IJCAI Conference 2022 Conference Paper

Search Space Expansion for Efficient Incremental Inductive Logic Programming from Streamed Data

• Mark Law
• Krysia Broda
• Alessandra Russo

In the past decade, several systems for learning Answer Set Programs (ASP) have been proposed, including the recent FastLAS system. Compared to other state-of-the-art approaches to learning ASP, FastLAS is more scalable, as rather than computing the hypothesis space in full, it computes a much smaller subset relative to a given set of examples that is nonetheless guaranteed to contain an optimal solution to the task (called an OPT-sufficient subset). On the other hand, like many other Inductive Logic Programming (ILP) systems, FastLAS is designed to be run on a fixed learning task meaning that if new examples are discovered after learning, the whole process must be run again. In many real applications, data arrives in a stream. Rerunning an ILP system from scratch each time new examples arrive is inefficient. In this paper we address this problem by presenting IncrementalLAS, a system that uses a new technique, called hypothesis space expansion, to enable a FastLAS-like OPT-sufficient subset to be expanded each time new examples are discovered. We prove that this preserves FastLAS's guarantee of finding an optimal solution to the full task (including the new examples), while removing the need to repeat previous computations. Through our evaluation, we demonstrate that running IncrementalLAS on tasks updated with sequences of new examples is significantly faster than re-running FastLAS from scratch on each updated task.

NeSy Conference 2021 Conference Paper

Coherent and Consistent Relational Transfer Learning with Auto-encoders

• Harald Strömfelt
• Luke Dickens
• Artur S. d'Avila Garcez
• Alessandra Russo

Human defined concepts are inherently transferable, but it is not clear under what conditions they can be modelled effectively by non-symbolic artificial learners. This paper argues that for a transferable concept to be learned, the system of relations that define it must be coherent across domains and properties. That is, they should be consistent with respect to relational constraints, and this consistency must extend beyond the representations encountered in the source domain. Further, where relations are modelled by differentiable functions, their gradients must conform – the functions must at times move together to preserve consistency. We propose a Partial Relation Transfer (PRT) task which exposes how well relation-decoders model these properties, and exemplify this with ordinality prediction transfer task, including a new data set for the transfer domain. We evaluate this on existing relation-decoder models, as well as a novel model designed around the principles of consistency and gradient conformity. Results show that consistency across broad regions of input space indicates good transfer performance, and that good gradient conformity facilitates consistency.

JAIR Journal 2021 Journal Article

Induction and Exploitation of Subgoal Automata for Reinforcement Learning

• Daniel Furelos-Blanco
• Mark Law
• Anders Jonsson
• Krysia Broda
• Alessandra Russo

In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task’s subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand.

NeSy Conference 2021 Conference Paper

pix2rule: End-to-end Neuro-symbolic Rule Learning

• Nuri Cingillioglu
• Alessandra Russo

Humans have the ability to seamlessly combine low-level visual input with high-level symbolic reasoning often in the form of recognising objects, learning relations between them and applying rules. Neurosymbolic systems aim to bring a unifying approach to connectionist and logic-based principles for visual processing and abstract reasoning respectively. This paper presents a complete neuro-symbolic method for processing images into objects, learning relations and logical rules in an end-to-end fashion. The main contribution is a differentiable layer in a deep learning architecture from which symbolic relations and rules can be extracted by pruning and thresholding. We evaluate our model using two datasets: subgraph isomorphism task for symbolic rule learning and an image classification domain with compound relations for learning objects, relations and rules. We demonstrate that our model scales beyond stateof-the-art symbolic learners and outperforms deep relational neural network architectures.

IJCAI Conference 2021 Conference Paper

Scalable Non-observational Predicate Learning in ASP

• Mark Law
• Alessandra Russo
• Krysia Broda
• Elisa Bertino

Recently, novel ILP systems under the answer set semantics have been proposed, some of which are robust to noise and scalable over large hypothesis spaces. One such system is FastLAS, which is significantly faster than other state-of-the-art ASP-based ILP systems. FastLAS is, however, only capable of Observational Predicate Learning (OPL), where the learned hypothesis defines predicates that are directly observed in the examples. It cannot learn knowledge that is indirectly observable, such as learning causes of observed events. This class of problems, known as non-OPL, is known to be difficult to handle in the context of non-monotonic semantics. Solving non-OPL learning tasks whilst preserving scalability is a challenging open problem. We address this problem with a new abductive method for translating examples of a non-OPL task to a set of examples, called possibilities, such that the original example is covered iff at least one of the possibilities is covered. This new method allows an ILP system capable of performing OPL tasks to be "upgraded" to solve non-OPL tasks. In particular, we present our new FastNonOPL system, which upgrades FastLAS with the new possibility generation. We compare it to other state-of-the-art ASP-based ILP systems capable of solving non-OPL tasks, showing that FastNonOPL is significantly faster, and in many cases more accurate, than these other systems.

AAAI Conference 2020 Conference Paper

FastLAS: Scalable Inductive Logic Programming Incorporating Domain-Specific Optimisation Criteria

• Mark Law
• Alessandra Russo
• Elisa Bertino
• Krysia Broda
• Jorge Lobo

Inductive Logic Programming (ILP) systems aim to find a set of logical rules, called a hypothesis, that explain a set of examples. In cases where many such hypotheses exist, ILP systems often bias towards shorter solutions, leading to highly general rules being learned. In some application domains like security and access control policies, this bias may not be desirable, as when data is sparse more specific rules that guarantee tighter security should be preferred. This paper presents a new general notion of a scoring function over hypotheses that allows a user to express domain-specific optimisation criteria. This is incorporated into a new ILP system, called FastLAS, that takes as input a learning task and a customised scoring function, and computes an optimal solution with respect to the given scoring function. We evaluate the accuracy of Fast- LAS over real-world datasets for access control policies and show that varying the scoring function allows a user to target domain-specific performance metrics. We also compare FastLAS to state-of-the-art ILP systems, using the standard ILP bias for shorter solutions, and demonstrate that FastLAS is significantly faster and more scalable.

AAAI Conference 2020 Conference Paper

Induction of Subgoal Automata for Reinforcement Learning

• Daniel Furelos-Blanco
• Mark Law
• Alessandra Russo
• Krysia Broda
• Anders Jonsson

In this work we present ISA, a novel approach for learning and exploiting subgoals in reinforcement learning (RL). Our method relies on inducing an automaton whose transitions are subgoals expressed as propositional formulas over a set of observable events. A state-of-the-art inductive logic programming system is used to learn the automaton from observation traces perceived by the RL agent. The reinforcement learning and automaton learning processes are interleaved: a new re- fined automaton is learned whenever the RL agent generates a trace not recognized by the current automaton. We evaluate ISA in several gridworld problems and show that it performs similarly to a method for which automata are given in advance. We also show that the learned automata can be exploited to speed up convergence through reward shaping and transfer learning across multiple tasks. Finally, we analyze the running time and the number of traces that ISA needs to learn an automata, and the impact that the number of observable events have on the learner’s performance.

NeurIPS Conference 2020 Conference Paper

Learning Invariants through Soft Unification

• Nuri Cingillioglu
• Alessandra Russo

Human reasoning involves recognising common underlying principles across many examples. The by-products of such reasoning are invariants that capture patterns such as "if someone went somewhere then they are there", expressed using variables "someone" and "somewhere" instead of mentioning specific people or places. Humans learn what variables are and how to use them at a young age. This paper explores whether machines can also learn and use variables solely from examples without requiring human pre-engineering. We propose Unification Networks, an end-to-end differentiable neural network approach capable of lifting examples into invariants and using those invariants to solve a given task. The core characteristic of our architecture is soft unification between examples that enables the network to generalise parts of the input into variables, thereby learning invariants. We evaluate our approach on five datasets to demonstrate that learning invariants captures patterns in the data and can improve performance over baselines.

ICAPS Conference 2020 Conference Paper

Learning Neural Search Policies for Classical Planning

• Pawel Gomoluch
• Dalal Alrajeh
• Alessandra Russo
• Antonio Bucchiarone

Heuristic forward search is currently the dominant paradigm in classical planning. Forward search algorithms typically rely on a single, relatively simple variation of best-first search and remain fixed throughout the process of solving a planning problem. Existing work combining multiple search techniques usually aims at supporting best-first search with an additional exploratory mechanism, triggered using a handcrafted criterion. A notable exception is very recent work which combines various search techniques using a trainable policy. That approach, however, is confined to a discrete action space comprising several fixed subroutines. In this paper, we introduce a parametrized search algorithm template which combines various search techniques within a single routine. The template's parameter space defines an infinite space of search algorithms, including, among others, BFS, local and random search. We then propose a neural architecture for designating the values of the search parameters given the state of the search. This enables expressing neural search policies that change the values of the parameters as the search progresses. The policies can be learned automatically, with the objective of maximizing the planner's performance on a given distribution of planning problems. We consider a training setting based on a stochastic optimization algorithm known as the cross-entropy method (CEM). Experimental evaluation of our approach shows that it is capable of finding effective distribution-specific search policies, outperforming the relevant baselines.

KR Conference 2020 Conference Paper

Stable and Supported Semantics in Continuous Vector Spaces

• Yaniv Aspis
• Krysia Broda
• Alessandra Russo
• Jorge Lobo

We introduce a novel approach for the computation of stable and supported models of normal logic programs in continuous vector spaces by a gradient-based search method. Specifically, the application of the immediate consequence operator of a program reduct can be computed in a vector space. To do this, Herbrand interpretations of a propositional program are embedded as 0-1 vectors in $\mathbb{R}^N$ and program reducts are represented as matrices in $\mathbb{R}^{N \times N}$. Using these representations we prove that the underlying semantics of a normal logic program is captured through matrix multiplication and a differentiable operation. As supported and stable models of a normal logic program can now be seen as fixed points in a continuous space, non-monotonic deduction can be performed using an optimisation process such as Newton's method. We report the results of several experiments using synthetically generated programs that demonstrate the feasibility of the approach and highlight how different parameter values can affect the behaviour of the system.

ICAPS Conference 2019 Conference Paper

Learning Classical Planning Strategies with Policy Gradient

• Pawel Gomoluch
• Dalal Alrajeh
• Alessandra Russo

A common paradigm in classical planning is heuristic forward search. Forward search planners often rely on simple best-first search which remains fixed throughout the search process. In this paper, we introduce a novel search framework capable of alternating between several forward search approaches while solving a particular planning problem. Selection of the approach is performed using a trainable stochastic policy, mapping the state of the search to a probability distribution over the approaches. This enables using policy gradient to learn search strategies tailored to a specific distributions of planning problems and a selected performance metric, e. g. the IPC score. We instantiate the framework by constructing a policy space consisting of five search approaches and a two-dimensional representation of the planner’s state. Then, we train the system on randomly generated problems from five IPC domains using three different performance metrics. Our experimental results show that the learner is able to discover domain-specific search strategies, improving the planner’s performance relative to the baselines of plain bestfirst search and a uniform policy.

AAAI Conference 2019 Conference Paper

Representing and Learning Grammars in Answer Set Programming

• Mark Law
• Alessandra Russo
• Elisa Bertino
• Krysia Broda
• Jorge Lobo

In this paper we introduce an extension of context-free grammars called answer set grammars (ASGs). These grammars allow annotations on production rules, written in the language of Answer Set Programming (ASP), which can express context-sensitive constraints. We investigate the complexity of various classes of ASG with respect to two decision problems: deciding whether a given string belongs to the language of an ASG and deciding whether the language of an ASG is non-empty. Specifically, we show that the complexity of these decision problems can be lowered by restricting the subset of the ASP language used in the annotations. To aid the applicability of these grammars to computational problems that require context-sensitive parsers for partially known languages, we propose a learning task for inducing the annotations of an ASG. We characterise the complexity of this task and present an algorithm for solving it. An evaluation of a (prototype) implementation is also discussed.

AIJ Journal 2018 Journal Article

The complexity and generality of learning answer set programs

• Mark Law
• Alessandra Russo
• Krysia Broda

JELIA Conference 2014 Conference Paper

Inductive Learning of Answer Set Programs

• Mark Law
• Alessandra Russo
• Krysia Broda

Abstract Existing work on Inductive Logic Programming (ILP) has focused mainly on the learning of definite programs or normal logic programs. In this paper, we aim to push the computational boundary to a wider class of programs: Answer Set Programs. We propose a new paradigm for ILP that integrates existing notions of brave and cautious semantics within a unifying learning framework whose inductive solutions are Answer Set Programs and examples are partial interpretations We present an algorithm that is sound and complete with respect to our new notion of inductive solutions. We demonstrate its applicability by discussing a prototype implementation, called ILASP (Inductive Learning of Answer Set Programs), and evaluate its use in the context of planning. In particular, we show how ILASP can be used to learn agent’s knowledge about the environment. Solutions of the learned ASP program provide plans for the agent to travel through the given environment.

LPAR Conference 2013 Conference Paper

On Minimality and Integrity Constraints in Probabilistic Abduction

• Calin-Rares Turliuc
• Nataly Maimari
• Alessandra Russo
• Krysia Broda

Abstract Abduction is a type of logical inference that can be successfully combined with probabilistic reasoning. However, the role of integrity constraints has not received much attention when performing logical-probabilistic inference. The contribution of our paper is a probabilistic abductive framework based on the distribution semantics for normal logic programs that handles negation as failure and integrity constraints in the form of denials. Integrity constraints are treated as evidence from the perspective of probabilistic inference. An implementation is provided that computes alternative (non-minimal) abductive solutions, using an appropriately modified abductive system, and generates the probability of a query, for given solutions. An example application of the framework is given, where gene network topologies are abduced according to biological expert knowledge, to probabilistically explain observed gene expressions. The example shows the practical utility of the proposed framework.

AAMAS Conference 2012 Conference Paper

Handling Change in Normative Specifications

• Duangtida Athakravi
• Domenico Corapi
• Alessandra Russo
• Marina De Vos
• Julian Padget
• Ken Satoh

Normative frameworks provide a means to address the governance of open systems, by offering a mechanism to express responsibilities and permissions of the individual participants with respect to the entire system without compromising their autonomy. Careful design is crucial if it is to meet its requirements. Tools that support the design process can be of great benefit. In this paper, we describe a method for choosing the appropriate change in the normative specification, using impact analysis of the critical consequences being preserved or rejected by the change.

AAMAS Conference 2011 Conference Paper

Multi-Agent Abductive Reasoning with Confidentiality

• Jiefei Ma
• Alessandra Russo
• Krysia Broda
• Emil Lupu

In the context of multi-agent hypothetical reasoning, agents typically have partial knowledge about their environments, and the union of such knowledge is still incomplete to represent the whole world. Thus, given a global query they need to collaborate with each other to make correct inferences and hypothesis, whilst maintaining global constraints. There are many real world applications in which the confidentiality of agent knowledge is of primary concern, and hence the agents may not share or communicate all their information during the collaboration. This extra constraint gives a new challenge to multi-agent reasoning. This paper shows how this dichotomy between "open communication" in collaborative reasoning and protection of confidentiality can be accommodated, by extending a general-purpose distributed abductive logic programming system for multi-agent hypothetical reasoning with confidentiality. Specifically, the system computes consistent conditional answers for a query over a set of distributed normal logic programs with possibly unbound domains and arithmetic constraints, preserving the private information within the logic programs.

AAMAS Conference 2010 Conference Paper

Distributed Abductive Reasoning with Constraints

• Jiefei Ma
• Alessandra Russo
• Krysia Broda
• Emil Lupu

Abductive inference has many known applications in multi-agent systems. However, most abductive frameworks relyon a centrally executed proof procedure whereas many ofthe application problems are distributed by nature. Confidentiality and communication overhead concerns often preclude transmitting all the knowledge required for centralisedreasoning. We present in this paper a novel multi-agent abductive reasoning framework underpinned by a flexible andextensible distributed proof procedure that permits collaborative abductive reasoning with constraints between agentsover decentralised knowledge.

ECAI Conference 2010 Conference Paper

The Dynamics of Multi-Agent Reinforcement Learning

• Luke Dickens
• Krysia Broda
• Alessandra Russo

Infinite-horizon multi-agent control processes with non-determinism and partial state knowledge have particularly interesting properties with respect to adaptive control, such as the non-existence of Nash Equilibria (NE) or non-strict NE which are nonetheless points of convergence. The identification of reinforcement learning (RL) algorithms that are robust, accurate and efficient when applied to these general multi-agent domains is an open, challenging problem. This paper uses learning pressure fields as a means for evaluating RL algorithms in the context of multi-agent processes. Specifically, we show how to model partially observable infinite-horizon stochastic processes (single-agent) and games (multi-agent) within the Finite Analytic Stochastic Process framework. Taking long term average expected returns as utility measures, we show the existence of learning pressure fields: vector fields – similar to the dynamics of evolutionary game theory, which indicate medium and long term learning behaviours of agents independently seeking to maximise this utility. We show empirically that these learning pressure fields are followed closely by policy-gradient RL algorithms.

JAAMAS Journal 2008 Journal Article

DARE: a system for distributed abductive reasoning

• Jiefei Ma
• Alessandra Russo
• Keith Clark

Abstract Abductive reasoning is a well established field of Artificial Intelligence widely applied to different problem domains not least cognitive robotics and planning. It has been used to abduce high-level descriptions of the world from robot sense data, using rules that tell us what sense data would be generated by certain objects and events of the robots world, subject to certain constraints on their co-occurrence. It has also been used to abduce actions that might result in a desired goal state of the world, using descriptions of the normal effects of these actions, subject to constraints on the action combinations. We can generalise these applications to a multi-agent context. Several robots can collaboratively try to abduce an agreed higher-level description of the state of the world from their separate sense data consistent with their collective constraints on the abduced description. Similarly, multi-agent planning can be accomplished by the abduction of the actions of a collective plan where each agent uses its own description of the effect of its actions within the plan, such that the constraints on the actions of all the participating agents are satisfied. To address this class of problems, we need to generalise the single agent abductive reasoning algorithm to a distributed abductive inference algortihm. In addition, if we want to investigate applications in which the set of collaborating robots/agents is open, we need an algorithm that allows agents to join or leave the collaborating group whilst a particular inference is under way, but which still produces sound abductive inferences. This paper describes such a distributed abductive reasoning system, which we call DARE, and its implementation in the multi-threaded Qu-Prolog variant of Prolog. We prove the soundness of the algorithm it uses and we discuss its completeness in relation to non-distributed abductive reasoning. We illustrate the use of the algorithm with a multi-agent meeting scheduling example. The task is open in that the actual agents who need to attend is not determined in advance. Each individual agent has its own constraints on the possible meeting time and concerning which other agents must or must attend the meeting, if it attends. The algorithm selects the agents to attend and ensures that the constraints of each of the attending agents are satisfied.