Arrow Research search

Author name cluster

Brian Logan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

69 papers
1 author row

Possible papers

69

JAIR Journal 2026 Journal Article

Synthesising Reward Machines for Cooperative Multi-Agent Reinforcement Learning

  • Giovanni Varricchione
  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan

Reward machines have recently been proposed as a means of encoding team tasks in cooperative multi-agent reinforcement learning. The resulting multi-agent reward machine is then decomposed into individual reward machines, one for each member of the team, allowing agents to learn in a decentralised manner while still achieving the team task. In this paper, we show how multi-agent reward machines for team tasks can be synthesised automatically from an abstraction of the environment in which the agents act and a high-level specification of the desired team behaviour expressed in a fragment of Alternating-time Temporal Logic. We present results from a number of benchmarks which suggest that our automated approach performs as well or better than reward machines in the literature.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Probabilistic Strategy Logic with Degrees of Observability

  • Chunyan Mu
  • Nima Motamed
  • Natasha Alechina
  • Brian Logan

There has been considerable work on reasoning about the strategic ability of agents under imperfect information. However, existing logics such as Probabilistic Strategy Logic are unable to express properties relating to information transparency. Information transparency concerns the extent to which agents' behaviours and actions are observable by other agents. Reasoning about information transparency is useful in many domains including security, privacy, and decision-making. In this paper, we present a formal framework for reasoning about information transparency properties in stochastic multi-agent systems. We extend Probabilistic Strategy Logic with new observability operators that capture the degree of observability of temporal properties by agents. We show that the model checking problem for the resulting logic is decidable.

PDF Details DOI

KR Conference 2025 Conference Paper

Pushdown Reward Machines for Reinforcement Learning

  • Giovanni Varricchione
  • Toryn Q. Klassen
  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan
  • Sheila A. McIlraith

Reward machines (RMs) are automata structures that encode (non-Markovian) reward functions for reinforcement learning (RL). RMs can reward any behaviour representable in regular languages and, when paired with RL algorithms that exploit RM structure, have been shown to significantly improve sample efficiency in many domains. In this work, we present pushdown reward machines (pdRMs), an extension of reward machines based on deterministic pushdown automata. pdRMs can recognise and reward temporally extended behaviours representable in deterministic context-free languages, making them more expressive than reward machines. We introduce two variants of pdRM-based policies, one which has access to the entire stack of the pdRM, and one which can only access the top k symbols (for a given constant k) of the stack. We propose a procedure to check when the two kinds of policies (for a given environment, pdRM, and constant k) achieve the same optimal state values. We then provide theoretical results establishing the expressive power of pdRMs, and space complexity results for the proposed learning problems. Lastly, we propose an approach for off-policy RL algorithms that exploits counterfactual experiences with pdRMs. We conclude by providing experimental results showing how agents can be trained to perform tasks representable in deterministic context-free languages using pdRMs.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Temporal Causal Reasoning with (Non-Recursive) Structural Equation Models

  • Maksim Gladyshev
  • Natasha Alechina
  • Mehdi Dastani
  • Dragan Doder
  • Brian Logan

Structural equation models (SEM) are a standard approach to representing causal dependencies between variables. In this paper we propose a new interpretation of existing formalisms in the field of Actual Causality in which SEM's are viewed as mechanisms transforming the dynamics of exogenous variables into the dynamics of endogenous variables. This allows us to combine counterfactual causal reasoning with existing temporal logic formalizms, and to introduce a temporal logic, CPLTL, for causal reasoning about such structures. Then, we demonstrate that the standard restriction to so-called recursive models (with no cycles in the dependency graphs) is not necessary in our approach. This fact provides us extra tools for reasoning about mutually dependent processes and feedback loops. Finally, we introduce the notions of model equivalence for temporal causal models and show that CPLTL has an efficient model-checking procedure.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Intention Progression with Temporally Extended Goals

  • Yuan Yao
  • Natasha Alechina
  • Brian Logan

The Belief-Desire-Intention (BDI) approach to agent development has formed the basis for much of the research on architectures for autonomous agents. A key advantage of the BDI approach is that agents may pursue multiple intentions in parallel. However, previous approaches to managing possible interactions between concurrently executing intentions are limited to interactions between simple achievement goals (and in some cases maintenance goals). In this paper we present a new approach to intention progression for agents with temporally extended goals which allow mixing reachability and invariant properties, e. g. , ``travel to location A while not exceeding a gradient of 5%''. Temporally extended goals may be specified at run-time (top-level goals), and as subgoals in plans. In addition, our approach allows human-authored plans and plans implemented as RL policies to be freely mixed in an agent program, allowing the development of agents with `neuro-symbolic' architectures.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Pure-Past Action Masking

  • Giovanni Varricchione
  • Natasha Alechina
  • Mehdi Dastani
  • Giuseppe De Giacomo
  • Brian Logan
  • Giuseppe Perelli

We present Pure-Past Action Masking (PPAM), a lightweight approach to action masking for safe reinforcement learning. In PPAM, actions are disallowed (“masked”) according to specifications expressed in Pure-Past Linear Temporal Logic (PPLTL). PPAM can enforce non-Markovian constraints, i.e., constraints based on the history of the system, rather than just the current state of the (possibly hidden) MDP. The features used in the safety constraint need not be the same as those used by the learning agent, allowing a clear separation of concerns between the safety constraints and reward specifications of the (learning) agent. We prove formally that an agent trained with PPAM can learn any optimal policy that satisfies the safety constraints, and that they are as expressive as shields, another approach to enforce non-Markovian constraints in RL. Finally, we provide empirical results showing how PPAM can guarantee constraint satisfaction in practice.

PDF Details DOI

JAIR Journal 2023 Journal Article

A Logic of East and West

  • Heshan Du
  • Natasha Alechina
  • Amin Farjudian
  • Brian Logan
  • Can Zhou
  • Anthony G. Cohn

We propose a logic of east and west (LEW ) for points in 1D Euclidean space. It formalises primitive direction relations: east (E), west (W) and indeterminate east/west (Iew). It has a parameter τ ∈ N>1, which is referred to as the level of indeterminacy in directions. For every τ ∈ N>1, we provide a sound and complete axiomatisation of LEW, and prove that its satisfiability problem is NP-complete. In addition, we show that the finite axiomatisability of LEW depends on τ: if τ = 2 or τ = 3, then there exists a finite sound and complete axiomatisation; if τ > 3, then the logic is not finitely axiomatisable. LEW can be easily extended to higher-dimensional Euclidean spaces. Extending LEW to 2D Euclidean space makes it suitable for reasoning about not perfectly aligned representations of the same spatial objects in different datasets, for example, in crowd-sourced digital maps.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Data-Driven Revision of Conditional Norms in Multi-Agent Systems (Extended Abstract)

  • Davide Dell'Anna
  • Natasha Alechina
  • Fabiano Dalpiaz
  • Mehdi Dastani
  • Brian Logan

In multi-agent systems, norm enforcement is a mechanism for steering the behavior of individual agents in order to achieve desired system-level objectives. Due to the dynamics of multi-agent systems, however, it is hard to design norms that guarantee the achievement of the objectives in every operating context. Also, these objectives may change over time, thereby making previously defined norms ineffective. In this paper, we investigate the use of system execution data to automatically synthesise and revise conditional prohibitions with deadlines, a type of norms aimed at preventing agents from exhibiting certain patterns of behaviors. We propose DDNR (Data-Driven Norm Revision), a data-driven approach to norm revision that synthesises revised norms with respect to a data set of traces describing the behavior of the agents in the system. We evaluate DDNR using a state-of-the-art, off-the-shelf urban traffic simulator. The results show that DDNR synthesises revised norms that are significantly more accurate than the original norms in distinguishing adequate and inadequate behaviors for the achievement of the system-level objectives.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Multi-Agent Intention Recognition and Progression

  • Michael Dann
  • Yuan Yao
  • Natasha Alechina
  • Brian Logan
  • Felipe Meneguzzi
  • John Thangarajah

For an agent in a multi-agent environment, it is often beneficial to be able to predict what other agents will do next when deciding how to act. Previous work in multi-agent intention scheduling assumes a priori knowledge of the current goals of other agents. In this paper, we present a new approach to multi-agent intention scheduling in which an agent uses online goal recognition to identify the goals currently being pursued by other agents while acting in pursuit of its own goals. We show how online goal recognition can be incorporated into an MCTS-based intention scheduler, and evaluate our approach in a range of scenarios. The results demonstrate that our approach can rapidly recognise the goals of other agents even when they are pursuing multiple goals concurrently, and has similar performance to agents which know the goals of other agents a priori.

PDF Details DOI

PRL Workshop 2023 Workshop Paper

Preemptive Restraining Bolts

  • Giovanni Varricchione
  • Natasha Alechina
  • Mehdi Dastani
  • Giuseppe De Giacomo
  • Brian Logan
  • Giuseppe Perelli

We present preemptive restraining bolts (PRBs), a new approach to safe reinforcement learning which uses non-Markovian action masking, i.e., actions are masked (disallowed) based on the history of the system, rather than just the current state. PRBs are expressed in Pure Past Linear Temporal Logic and have minimal overhead (linear in the size of the state) compared to Markovian action masking, while having the same expressive power as other non-Markovian approaches such as shields (that can express any safety Linear Temporal Logic property). As with restraining bolts, the language in which safety properties are expressed does not have to be the same as the language specifying the features of the state for the learning agent. Critically, PRBs can be applied in the learning process to learn an optimal safe policy while using only safe actions during learning. As a result, PRBs can be used to provide general safety guarantees, without compromising efficiency.

PDF Details

IJCAI Conference 2023 Conference Paper

Probabilistic Temporal Logic for Reasoning about Bounded Policies

  • Nima Motamed
  • Natasha Alechina
  • Mehdi Dastani
  • Dragan Doder
  • Brian Logan

To build a theory of intention revision for agents operating in stochastic environments, we need a logic in which we can explicitly reason about their decision-making policies and those policies' uncertain outcomes. Towards this end, we propose PLBP, a novel probabilistic temporal logic for Markov Decision Processes that allows us to reason about policies of bounded size. The logic is designed so that its expressive power is sufficient for the intended applications, whilst at the same time possessing strong computational properties. We prove that the satisfiability problem for our logic is decidable, and that its model checking problem is PSPACE-complete. This allows us to e. g. algorithmically verify whether an agent's intentions are coherent, or whether a specific policy satisfies safety and/or liveness properties.

PDF Details DOI

KR Conference 2022 Conference Paper

Automatic Synthesis of Dynamic Norms for Multi-Agent Systems

  • Natasha Alechina
  • Giuseppe De Giacomo
  • Brian Logan
  • Giuseppe Perelli

Norms have been widely proposed to coordinate and regulate multi-agent systems (MAS) behaviour. We consider the problem of synthesising and revising the set of norms in a normative MAS to satisfy a design objective expressed in Alternating Time Temporal Logic (ATL*). ATL* is a well-established language for strategic reasoning, which allows the specification of norms that constrain the strategic behaviour of agents. We focus on dynamic norms, that is, norms corresponding to Mealy machines, that allow us to place different constraints on the agents' behaviour depending on the state of the norm and the state of the underlying MAS. We show that synthesising dynamic norms is (k + 1)-EXPTIME, where k is the alternation depth of quantifiers in the ATL* specification. Note that for typical cases of interest, k is either 1 or 2. We also study the problem of removing existing norms to satisfy a new objective, which we show to be 2EXPTIME-complete.

PDF Details DOI

JAIR Journal 2022 Journal Article

Data-Driven Revision of Conditional Norms in Multi-Agent Systems

  • Davide Dell'Anna
  • Natasha Alechina
  • Fabiano Dalpiaz
  • Mehdi Dastani
  • Brian Logan

In multi-agent systems, norm enforcement is a mechanism for steering the behavior of individual agents in order to achieve desired system-level objectives. Due to the dynamics of multi-agent systems, however, it is hard to design norms that guarantee the achievement of the objectives in every operating context. Also, these objectives may change over time, thereby making previously defined norms ineffective. In this paper, we investigate the use of system execution data to automatically synthesise and revise conditional prohibitions with deadlines, a type of norms aimed at prohibiting agents from exhibiting certain patterns of behaviors. We propose DDNR (Data-Driven Norm Revision), a data-driven approach to norm revision that synthesises revised norms with respect to a data set of traces describing the behavior of the agents in the system. We evaluate DDNR using a state-of-the-art, off-the-shelf urban traffic simulator. The results show that DDNR synthesises revised norms that are significantly more accurate than the original norms in distinguishing adequate and inadequate behaviors for the achievement of the system-level objectives.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Multi-Agent Intention Progression with Reward Machines

  • Michael Dann
  • Yuan Yao
  • Natasha Alechina
  • Brian Logan
  • John Thangarajah

Recent work in multi-agent intention scheduling has shown that enabling agents to predict the actions of other agents when choosing their own actions can be beneficial. However existing approaches to 'intention-aware' scheduling assume that the programs of other agents are known, or are "similar" to that of the agent making the prediction. While this assumption is reasonable in some circumstances, it is less plausible when the agents are not co-designed. In this paper, we present a new approach to multi-agent intention scheduling in which agents predict the actions of other agents based on a high-level specification of the tasks performed by an agent in the form of a reward machine (RM) rather than on its (assumed) program. We show how a reward machine can be used to generate tree and rollout policies for an MCTS-based scheduler. We evaluate our approach in a range of multi-agent environments, and show that RM-based scheduling out-performs previous intention-aware scheduling approaches in settings where agents are not co-designed

PDF Details DOI

IJCAI Conference 2022 Conference Paper

Situation Calculus for Controller Synthesis in Manufacturing Systems with First-Order State Representation (Extended Abstract)

  • Giuseppe De Giacomo
  • Paolo Felli
  • Brian Logan
  • Fabio Patrizi
  • Sebastian Sardiña

Manufacturing is transitioning from a mass production model to a service model in which facilities `bid' for previously unseen products. To decide whether to bid for a previously unseen product, a facility must be able to synthesize, on the fly, a process plan controller that delegates abstract manufacturing tasks in a supplied process recipe to the available manufacturing resources. First-order representations of the state are commonly considered in reasoning about action in AI. Here we show that we can leverage the wide literature on the Situation Calculus automatically synthesize such controllers. We identify two important decidable cases---finite domains and bounded action theories---for which we provide practical synthesis techniques.

PDF Details DOI

AAMAS Conference 2021 Conference Paper

Agent Programming in the Cognitive Era

  • Rafael H. Bordini
  • Amal El Fallah Seghrouchni
  • Koen Hindriks
  • Brian Logan
  • Alessandro Ricci

It is claimed that, in the nascent ‘Cognitive Era’, intelligent systems will be trained using machine learning techniques rather than programmed by software developers [10]. A contrary point of view argues that machine learning has limitations, and, taken in isolation, cannot form the basis of autonomous systems capable of intelligent behaviour in complex environments [14]. In this paper, we argue that the unique strengths of Belief-Desire-Intention (BDI) agent programming languages provide an ideal framework for integrating the wide range of AI capabilities necessary for progress towards the next-generation of intelligent systems.

PDF

AAMAS Conference 2021 Conference Paper

Intention Progression using Quantitative Summary Information

  • Yuan Yao
  • Natasha Alechina
  • Brian Logan
  • John Thangarajah

A key problem for Belief-Desire-Intention (BDI) agents is intention progression, i. e. , which plans should be selected and how the execution of these plans should be interleaved so as to achieve the agent’s goals. Monte-Carlo Tree Search (MCTS) has been shown to be a promising approach to the intention progression problem, out-performing other approaches in the literature. However, MCTS relies on runtime simulation of possible interleavings of the plans in each intention, which may be computationally costly. In this paper, we introduce the notion of quantitative summary information which can be used to estimate the likelihood of conflicts between an agent’s intentions. We show how offline simulation can be used to precompute quantitative summary information prior to execution of the agent’s program, and how the precomputed summary information can be used at runtime to guide the expansion of the MCTS search tree and avoid unnecessary runtime simulation. We compare the performance of our approach with standard MCTS in a range of scenarios of increasing difficulty. The results suggest our approach can significantly improve the efficiency of MCTS in terms of the number of runtime simulations performed.

PDF

IJCAI Conference 2021 Conference Paper

Multi-Agent Intention Progression with Black-Box Agents

  • Michael Dann
  • Yuan Yao
  • Brian Logan
  • John Thangarajah

We propose a new approach to intention progression in multi-agent settings where other agents are effectively black boxes. That is, while their goals are known, the precise programs used to achieve these goals are not known. In our approach, agents use an abstraction of their own program called a partially-ordered goal-plan tree (pGPT) to schedule their intentions and predict the actions of other agents. We show how a pGPT can be derived from the program of a BDI agent, and present an approach based on Monte Carlo Tree Search (MCTS) for scheduling an agent's intentions using pGPTs. We evaluate our pGPT-based approach in cooperative, selfish and adversarial multi-agent settings, and show that it out-performs MCTS-based scheduling where agents assume that other agents have the same program as themselves.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

BDI Agent Architectures: A Survey

  • Lavindra de Silva
  • Felipe Meneguzzi
  • Brian Logan

The BDI model forms the basis of much of the research on symbolic models of agency and agent-oriented software engineering. While many variants of the basic BDI model have been proposed in the literature, there has been no systematic review of research on BDI agent architectures in over 10 years. In this paper, we survey the main approaches to each component of the BDI architecture, how these have been realised in agent programming languages, and discuss the trade-offs inherent in each approach.

PDF Details DOI

IJCAI Conference 2020 Conference Paper

Intention Progression under Uncertainty

  • Yuan Yao
  • Natasha Alechina
  • Brian Logan
  • John Thangarajah

A key problem in Belief-Desire-Intention agents is how an agent progresses its intentions, i. e. , which plans should be selected and how the execution of these plans should be interleaved so as to achieve the agent’s goals. Previous approaches to the intention progression problem assume the agent has perfect information about the state of the environment. However, in many real-world applications, an agent may be uncertain about whether an environment condition holds, and hence whether a particular plan is applicable or an action is executable. In this paper, we propose SAU, a Monte-Carlo Tree Search (MCTS)-based scheduler for intention progression problems where the agent’s beliefs are uncertain. We evaluate the performance of our approach experimentally by varying the degree of uncertainty in the agent’s beliefs. The results suggest that SAU is able to successfully achieve the agent’s goals even in settings where there is significant uncertainty in the agent’s beliefs.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Parameterised Resource-Bounded ATL

  • Natasha Alechina
  • Stéphane Demri
  • Brian Logan

It is often advantageous to be able to extract resource requirements in resource logics of strategic ability, rather than to verify whether a fixed resource requirement is sufficient for achieving a goal. We study Parameterised Resource-Bounded Alternating Time Temporal Logic where parameter extraction is possible. We give a parameter extraction algorithm and prove that the model-checking problem is 2EXPTIMEcomplete.

PDF Details

AAMAS Conference 2019 Conference Paper

Decidable Model Checking with Uniform Strategies

  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan

The logic of strategic ability Resource-Bounded Alternating Time Syntactic Epistemic Logic (RB±ATSEL) has a decidable modelchecking problem for coalition uniform strategies. A strategy is coalition uniform if agents in a coalition select the same joint action in all states where the knowledge of the coalition is the same. However, this presupposes free and unbounded communication between the agents in the coalition before every action selection. In this paper we present a modified version of RB±ATSEL, RB±ATSELc, with explicit (and explicitly costed) communication actions. RB±ATSELc is interpreted on communication models which have an explicit communication step before every action selection. We show that, unlike standard ATL under imperfect information, the model checking problem for RB±ATSELc is decidable under perfect recall uniform strategies. Our decidability result also applies to ATL with imperfect information and perfect recall when interpreted on communication models.

PDF

AAMAS Conference 2019 Conference Paper

Strategic Responsibility Under Imperfect Information

  • Vahid Yazdanpanah
  • Mehdi Dastani
  • Wojciech Jamroga
  • Natasha Alechina
  • Brian Logan

A central issue in the specification and verification of autonomous agents and multiagent systems is the ascription of responsibility to individual agents and groups of agents. When designing a (multi)agent system, we must specify which agents or groups of agents are responsible for bringing about a particular state of affairs. Similarly, when verifying a multiagent system, we may wish to determine the responsibility of agents or groups of agents for a particular state of affairs, and the contribution of each agent to bringing about that state of affairs. In this paper, we discuss several aspects of responsibility, including strategic ability of agents, their epistemic properties, and their relationship to the evolution of the system behavior. We introduce a formal framework for reasoning about the responsibility of individual agents and agent groups in terms of the agents’ strategies and epistemic properties, and state some properties of the framework.

PDF

AAAI Conference 2019 Conference Paper

Unbounded Orchestrations of Transducers for Manufacturing

  • Natasha Alechina
  • Tomáš Brázdil
  • Giuseppe De Giacomo
  • Paolo Felli
  • Brian Logan
  • Moshe Y. Vardi

There has recently been increasing interest in using reactive synthesis techniques to automate the production of manufacturing process plans. Previous work has assumed that the set of manufacturing resources is known and fixed in advance. In this paper, we consider the more general problem of whether a controller can be synthesized given sufficient resources. In the unbounded setting, only the types of available manufacturing resources are given, and we want to know whether it is possible to manufacture a product using only resources of those type(s), and, if so, how many resources of each type are needed. We model manufacturing processes and facilities as transducers (automata with output), and show that the unbounded orchestration problem is decidable and the (Pareto) optimal set of resources necessary to manufacture a product is computable for uni-transducers. However, for multitransducers, the problem is undecidable.

PDF Details

IJCAI Conference 2018 Conference Paper

An Operational Semantics for a Fragment of PRS

  • Lavindra de Silva
  • Felipe Meneguzzi
  • Brian Logan

The Procedural Reasoning System (PRS) is arguably the first implementation of the Belief--Desire--Intention (BDI) approach to agent programming. PRS remains extremely influential, directly or indirectly inspiring the development of subsequent BDI agent programming languages. However, perhaps surprisingly given its centrality in the BDI paradigm, PRS lacks a formal operational semantics, making it difficult to determine its expressive power relative to other agent programming languages. This paper takes a first step towards closing this gap, by giving a formal semantics for a significant fragment of PRS. We prove key properties of the semantics relating to PRS-specific programming constructs, and show that even the fragment of PRS we consider is strictly more expressive than the plan constructs found in typical BDI languages.

PDF Details

JAIR Journal 2018 Journal Article

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems

  • Natasha Alechina
  • Joseph Y. Halpern
  • Ian A. Kash
  • Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). We show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations. The cost of providing the incentives is not borne by the MAS and does not come from fines charged for norm violations (fines may be impossible to levy in a system where agents are free to leave and rejoin again under a different identity). Instead, monitoring incentives come from (scrip) fees for accessing the services provided by the MAS. In some cases, perfect monitoring (and hence enforcement) can be achieved: no norms will be violated in equilibrium. In other cases, we show that, while it is impossible to achieve perfect enforcement, we can get arbitrarily close; we can make the probability of a norm violation in equilibrium arbitrarily small. We show using simulations that our theoretical results, which apply to systems with a large number of agents, hold for multi-agent systems with as few as 1000 agents–the system rapidly converges to the steady-state distribution of scrip tokens necessary to ensure monitoring and then remains close to the steady state.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Incentive-Compatible Mechanisms for Norm Monitoring in Open Multi-Agent Systems (Extended Abstract)

  • Natasha Alechina
  • Joseph Y. Halpern
  • Ian A. Kash
  • Brian Logan

We consider the problem of detecting norm violations in open multi-agent systems (MAS). In this extended abstract, we outline the approach of [Alechina et al. , 2018], and show how, using ideas from scrip systems, we can design mechanisms where the agents comprising the MAS are incentivised to monitor the actions of other agents for norm violations.

PDF Details

AAMAS Conference 2018 Conference Paper

Resource Logics with a Diminishing Resource

  • Natasha Alechina
  • Brian Logan

Model-checking resource logics with production and consumption of resources is a computationally hard and often undecidable problem. We show that it is more feasible under the assumption that there is at least one diminishing resource, that is, a resource which is consumed by every action.

PDF

AAAI Conference 2018 Conference Paper

Synthesis of Orchestrations of Transducers for Manufacturing

  • Giuseppe De Giacomo
  • Moshe Vardi
  • Paolo Felli
  • Natasha Alechina
  • Brian Logan

In this paper, we model manufacturing processes and facilities as transducers (automata with output). The problem of whether a given manufacturing process can be realized by a given set of manufacturing resources can then be stated as an orchestration problem for transducers. We first consider the conceptually simpler case of uni-transducers (transducers with a single input and a single output port), and show that synthesizing orchestrations for uni-transducers is EXPTIMEcomplete. Surprisingly, the complexity remains the same for the more expressive multi-transducer case, where transducers have multiple input and output ports and the orchestration is in charge of dynamically connecting ports during execution.

PDF Details

AAMAS Conference 2017 Conference Paper

Causality, Responsibility and Blame in Team Plans

  • Natasha Alechina
  • Joseph Y. Halpern
  • Brian Logan

Many objectives can be achieved (or may be achieved more effectively) only by a group of agents executing a team plan. If a team plan fails, it is often of interest to determine what caused the failure, the degree of responsibility of each agent for the failure, and the degree of blame attached to each agent. We show how team plans can be represented in terms of structural equations, and then apply the definitions of causality introduced by Halpern [11] and degree of responsibility and blame introduced by Chockler and Halpern [3] to determine the agent(s) who caused the failure and what their degree of responsibility/blame is. We also prove new results on the complexity of computing causality and degree of responsibility and blame, showing that they can be determined in polynomial time for many team plans of interest.

PDF

AAAI Conference 2017 Conference Paper

Incentivising Monitoring in Open Normative Systems

  • Natasha Alechina
  • Joseph Halpern
  • Ian Kash
  • Brian Logan

We present an approach to incentivising monitoring for norm violations in open multi-agent systems such as Wikipedia. In such systems, there is no crisp definition of a norm violation; rather, it is a matter of judgement whether an agent’s behaviour conforms to generally accepted standards of behaviour. Agents may legitimately disagree about borderline cases. Using ideas from scrip systems and peer prediction, we show how to design a mechanism that incentivises agents to monitor each other’s behaviour for norm violations. The mechanism keeps the probability of undetected violations (submissions that the majority of the community would consider not conforming to standards) low, and is robust against collusion by the monitoring agents.

PDF Details

IJCAI Conference 2017 Conference Paper

Process Plan Controllers for Non-Deterministic Manufacturing Systems

  • Paolo Felli
  • Lavindra de Silva
  • Brian Logan
  • Svetan Ratchev

Determining the most appropriate means of producing a given product, i. e. , which manufacturing and assembly tasks need to be performed in which order and how, is termed process planning. In process planning, abstract manufacturing tasks in a process recipe are matched to available manufacturing resources, e. g. , CNC machines and robots, to give an executable process plan. A process plan controller then delegates each operation in the plan to specific manufacturing resources. In this paper we present an approach to the automated computation of process plans and process plan controllers. We extend previous work to support both non-deterministic (i. e. , partially controllable) resources, and to allow operations to be performed in parallel on the same part. We show how implicit fairness assumptions can be captured in this setting, and how this impacts the definition of process plans.

PDF Details

AAMAS Conference 2017 Conference Paper

Progressing Intention Progression: A Call for a Goal-Plan Tree Contest

  • Brian Logan
  • John Thangarajah
  • Neil Yorke-Smith

User-supplied domain control knowledge in the form of hierarchically structured Goal-Plan Trees (GPTs) is at the heart of a number of approaches to reasoning about action. Reasoning with GPTs connects the AAMAS community with other communities such as automated planning, and forms the foundation for important reasoning capabilities, especially intention progression in Belief-Desire-Intention (BDI) agents. Research on GPTs has a long history but suffers from fragmentation and lack of common terminology, data formats, and enabling tools. One way to address this fragmentation is through a competition. Competitions are increasingly being used as a means to foster research and challenge the state of the art. For example, the AAMAS conference has a number of associated competitions, such as the Trading Agent Competition, while agent research is showcased at competitions such as RoboCup. We therefore issue a call for a Goal-Plan Tree Contest, with the ambition of drawing together a community and incentivizing research in intention progression.

PDF

JAAMAS Journal 2016 Journal Article

Integrating BDI Agents with Agent-Based Simulation Platforms

  • Dhirendra Singh
  • Lin Padgham
  • Brian Logan

Abstract Agent-based models (ABMs) are increasingly being used for exploring and supporting decision making about social science scenarios involving modelling of human agents. However existing agent-based simulation platforms (e. g. , SWARM, Repast) provide limited support for the simulation of more complex cognitive agents required by such scenarios. We present a framework that allows Belief-Desire-Intention (BDI) cognitive agents to be embedded in an ABM system. Architecturally, this means that the “brains” of an agent can be modelled in the BDI system in the usual way, while the “body” exists in the ABM system. The architecture is flexible in that the ABM can still have non-BDI agents in the simulation, and the BDI-side can have agents that do not have a physical counterpart (such as an organisation). The framework addresses a key integration challenge of coupling event-based BDI systems, with time-stepped ABM systems. Our framework is modular and supports integration of off-the-shelf BDI systems with off-the-shelf ABM systems. The framework is Open Source, and all integrations and applications are available for use by the modelling community.

Details DOI

IJCAI Conference 2016 Conference Paper

Parallel Behavior Composition for Manufacturing

  • Paolo Felli
  • Brian Logan
  • Sebastian Sardina

A key problem in the manufacture of highly-customized products is the synthesis of controllers able to manufacture any instance of a given product type on a given production or assembly line. In this paper, we extend classical AI behavior composition to manufacturing settings. We first introduce a novel solution concept for manufacturing composition, target production processes, that are able to manufacture multiple instances of a product simultaneously in a given production plant. We then propose a technique for synthesizing the largest target production process, together with an associated controller for the machines in the plant.

PDF Details

AAAI Conference 2016 Conference Paper

Robust Execution of BDI Agent Programs by Exploiting Synergies Between Intentions

  • Yuan Yao
  • Brian Logan
  • John Thangarajah

A key advantage the reactive planning approach adopted by BDI-based agents is the ability to recover from plan execution failures, and almost all BDI agent programming languages and platforms provide some form of failure handling mechanism. In general, these consist of simply choosing an alternative plan for the failed subgoal (e. g. , JACK, Jadex). In this paper, we propose an alternative approach to recovering from execution failures that relies on exploiting positive interactions between an agent’s intentions. A positive interaction occurs when the execution of an action in one intention assists the execution of actions in other intentions (e. g. , by (re)establishing their preconditions). We have implemented our approach in a scheduling algorithm for BDI agents which we call SP. The results of a preliminary empirical evaluation of SP suggest our approach out-performs existing failure handling mechanisms used by state-of-the-art BDI languages. Moreover, the computational overhead of SP is modest.

PDF Details

IJCAI Conference 2016 Conference Paper

Verifying Existence of Resource-Bounded Coalition Uniform Strategies

  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan

We consider the problem of whether a coalition of agents has a knowledge-based strategy to ensure some outcome under a resource bound. We extend previous work on verification of multi-agent systems where actions of agents produce and consume resources, by adding epistemic pre- and postconditions to actions. This allows us to model scenarios where agents perform both actions which change the world, and actions which change their knowledge about the world, such as observation and communication. To avoid logical omniscience and obtain a compact model of the system, our model of agents' knowledge is syntactic. We define a class of coalition-uniform strategies with respect to any (decidable) notion of coalition knowledge. We show that the model-checking problem for the resulting logic is decidable for any notion of coalition-uniform strategies in these classes.

PDF Details

IJCAI Conference 2015 Conference Paper

On the Boundary of (Un)decidability: Decidable Model-Checking for a Fragment of Resource Agent Logic

  • Natasha Alechina
  • Nils Bulling
  • Brian Logan
  • Hoang Nga Nguyen

The model-checking problem for Resource Agent Logic is known to be undecidable. We review existing (un)decidability results and identify a significant fragment of the logic for which model checking is decidable. We discuss aspects which makes model checking decidable and prove undecidability of two open fragments over a class of models in which agents always have a choice of doing nothing.

PDF Details

IJCAI Conference 2015 Conference Paper

Symbolic Model Checking for One-Resource RB+-ATL

  • Natasha Alechina
  • Brian Logan
  • Hoang Nga Nguyen
  • Franco Raimondi

RB±ATL is an extension of ATL where it is possible to model consumption and production of several resources by a set of agents. The modelchecking problem for RB±ATL is known to be decidable. However the only available modelchecking algorithm for RB±ATL uses a forward search of the state space, and hence does not have an efficient symbolic implementation. In this paper, we consider a fragment of RB±ATL, 1RB±ATL, that allows only one resource type. We give a symbolic model-checking algorithm for this fragment of RB±ATL, and evaluate the performance of an MCMAS-based implementation of the algorithm on an example problem that can be scaled to large state spaces.

PDF Details

AAAI Conference 2013 Conference Paper

Multi-Cycle Query Caching in Agent Programming

  • Natasha Alechina
  • Tristan Behrens
  • Mehdi Dastani
  • Koen Hindriks
  • Jomi Hubner
  • Brian Logan
  • Hai Nguyen
  • Marc van Zee

In many logic-based BDI agent programming languages, plan selection involves inferencing over some underlying knowledge representation. While context-sensitive plan selection facilitates the development of flexible, declarative programs, the overhead of evaluating repeated queries to the agent’s beliefs and goals can result in poor run time performance. In this paper we present an approach to multi-cycle query caching for logic-based BDI agent programming languages. We extend the abstract performance model presented in (Alechina et al. 2012) to quantify the costs and benefits of caching query results over multiple deliberation cycles. We also present results of experiments with prototype implementations of both single- and multi-cycle caching in three logic-based BDI agent platforms, which demonstrate that significant performance improvements are achievable in practice.

PDF Details

IJCAI Conference 2013 Conference Paper

Reasoning about Normative Update

  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan

We consider the problem of updating a multi-agent system with a set of conditional norms. A norm comes into effect when its condition becomes true, and imposes either an obligation or a prohibition on an agent which remains in force until a state satisfying a deadline condition is reached. If the norm is violated, a sanction is imposed on the agent. We define a notion of a normative update of a multi-agent system by a set of conditional norms, and study the problem of checking whether the agent(s) can bring about a state satisfying a property without incurring a specified number of sanctions.

PDF Details DOI

AAMAS Conference 2012 Conference Paper

Consensus Games

  • Julian Zappala
  • Natasha Alechina
  • Brian Logan

Consensus Games (CGs) are a novel approach to modelling coalition formation in multi-agent systems inspired by threshold models in sociology. In a CG, each agent’s degree of commitment to the coalitions in which it may participate is expressed as a quorum function. Agents are willing to form a coalition only if a quorum consensus can be achieved amongst all agents of the coalition.

PDF

AAMAS Conference 2012 Conference Paper

Programming Norm-Aware Agents

  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan

Normative organisations provide a means to coordinate the activities of individual agents in multiagent settings. The coordination is realized at run time by creating obligations and prohibitions (norms) for individual agents. If an agent cannot meet an obligation or violates a prohibition, the organisation imposes a sanction on the agent. In this paper, we consider \emph{norm-aware} agents that deliberate on their goals, norms and sanctions before deciding which plan to select and execute. A norm-aware agent is able to violate norms (accepting the resulting sanctions) if it is in the agent's overall interests to do so, e. g. , if meeting an obligation would result in an important goal of the agent becoming unachievable. Programming norm-aware agents in conventional BDI-based agent programming languages is difficult, as they lack support for deliberating about goals, norms and sanctions and deadlines. We present the norm-aware agent programming language N-2APL. N-2APL is based on 2APL and provides support for beliefs, goals, plans, norms, sanctions and deadlines. We give the syntax and semantics of N-2APL, and show that N-2APL agents are rational in the sense of committing to a set of plans that will achieve the agent's most important goals and obligations by their deadlines while respecting its most important prohibitions.

PDF

AAMAS Conference 2011 Conference Paper

Agent Programming with Priorities and Deadlines

  • Konstantin Vikhorev
  • Natasha Alechina
  • Brian Logan

We present AgentSpeak(RT), a real-time BDI agent programming language based on AgentSpeak(L). AgentSpeak(RT) extends AgentSpeak intentions with deadlines which specify the time by which the agent should respond to an event, and priorities which specify the relative importance of responding to a particular event. The AgentSpeak(RT) interpreter commits to a priority-maximal set of intentions: a set of intentions which is maximally feasible while preferring higher priority intentions. We prove some properties of the language, such as guaranteed reactivity delay of the AgentSpeak(RT) interpreter and probabilistic guarantees of successful execution of intentions by their deadlines.

PDF

AAMAS Conference 2010 Conference Paper

Resource-bounded alternating-time temporal logic

  • Natasha Alechina
  • Brian Logan
  • Hoang Nga Nguyen
  • Abdur Rakib

Many problems in AI and multi-agent systems research are mostnaturally formulated in terms of the abilities of a coalition of agents. There exist several excellent logical tools for reasoning about coalitional ability. However, coalitional ability can be affected by theavailability of resources, and there is no straightforward way ofreasoning about resource requirements in logics such as CoalitionLogic (CL) and Alternating-time Temporal Logic (ATL). In thispaper, we propose a logic for reasoning about coalitional abilityunder resource constraints. We extend ATL with costs of actionsand hence of strategies. We give a complete and sound axiomatisation of the resulting logic Resource-Bounded ATL (RB-ATL) andan efficient model-checking algorithm for it.

PDF

IJCAI Conference 2009 Conference Paper

  • Natasha Alechina
  • Brian Logan
  • Nguyen Hoang Nga
  • Abdur Rakib

Recent work on Alternating-Time Temporal Logic and Coalition Logic has allowed the expression of many interesting properties of coalitions and strategies. However there is no natural way of expressing resource requirements in these logics. This paper presents a Resource-Bounded Coalition Logic (RBCL) which has explicit representation of resource bounds in the language, and gives a complete and sound axiomatisation of RBCL.

PDF Details

AAMAS Conference 2008 Conference Paper

Reasoning about agent deliberation

  • Natasha Alechina
  • Mehdi Dastani
  • Brian Logan
  • John-Jules Meyer

We present a logic for reasoning about properties of agent programs under different agent execution strategies. Using the agent programming language SimpleAPL as an example, we show how safety and liveness properties can be expressed by translating agent programs into expressions of the logic. We give sound and complete axiomatizations of two different program execution strategies for SimpleAPL programs, and, for each of those strategies, prove a correspondence between the operational semantics of SimpleAPL and the models of the corresponding logic.

PDF

AAMAS Conference 2008 Conference Paper

Verifying time, memory and communication bounds in systems of reasoning agents

  • Natasha Alechina
  • Brian Logan
  • Hoang Nga Nguyen
  • Abdur Rakib

We present a framework for verifying systems composed of heterogeneous reasoning agents, in which each agent may have differing knowledge and inferential capabilities, and where the resources each agent is prepared to commit to a goal (time, memory and communication bandwidth) are bounded. The framework allows us to investigate, for example, whether a goal can be achieved if a particular agent, perhaps possessing key information or inferential capabilities, is unable (or unwilling) to contribute more than a given portion of its available computational resources or bandwidth to the problem. We present a novel temporal epistemic logic, BMCL, which allows us to describe a set of reasoning agents with bounds on time, memory and the number of messages they can exchange. The bounds on memory and communication are expressed as axioms in the logic. As an example, we show how to axiomatize a system of agents which reason using resolution and prove that the resulting logic is sound and complete. We then show how to encode a simple system of reasoning agents specified in BMCL in the description language of a model checker, and verify that the agents can achieve a goal only if they are prepared to commit certain time, memory and communication resources.

PDF

AAAI Conference 2007 Conference Paper

A Logic of Agent Programs

  • Natasha Alechina
  • Brian Logan

We present a sound and complete logic for reasoning about SimpleAPL programs. SimpleAPL is a fragment of the agent programming language 3APL designed for the implementation of cognitive agents with beliefs, goals and plans. Our logic is a variant of PDL, and allows the specification of safety and liveness properties of agent programs. We prove a correspondence between the operational semantics of SimpleAPL and the models of the logic for two example program execution strategies. We show how to translate agent programs written in SimpleAPL into expressions of the logic, and give an example in which we show how to verify correctness properties for a simple agent program.

PDF Details

AAAI Conference 2006 Conference Paper

Model-Checking Memory Requirements of Resource-Bounded Reasoners

  • Alex Albore
  • Piergiorgio Bertoli
  • Brian Logan

Memory bounds may limit the ability of a reasoner to make inferences and therefore affect the reasoner’s usefulness. In this paper, we propose a framework to automatically verify the reasoning capabilities of propositional memory-bounded reasoners which have a sequential architecture. Our framework explicitly accounts for the use of memory both to store facts and to support backtracking in the course of deductions. We describe an implementation of our framework in which proof existence is recast as a strong planning problem, and present results of experiments using the MBP planner which indicate that memory bounds may not be trivial to infer even for simple problems, and that memory bounds and length of derivations are closely interrelated.

PDF Details

AAAI Conference 1998 Conference Paper

A* with Bounded Costs

  • Brian Logan

A key assumption of all problem-solving approaches based on utility theory, including heuristic search, is that we can assign a utility or cost to each state. This in turn requires that all criteria of interest can be reduced to a common ratio scale. However, many real-world problems are difficult or impossible to formulate in terms of minimising a single criterion, and it is often more natural to express problem requirements in terms of a set of constraints which a solution should satisfy. In this paper, we present a generalisation of the A search algorithm, A with bounded costs (ABC), which searches for a solution which best satisfies a set of prioritised soft constraints, and show that, given certain reasonable assumptions about the constraints, the algorithm is both complete and optimal. We briefly describe a route planner based on ABC and illustrate the advantages of our approach in a simple route planning problem.

PDF Details