William Yeoh

AAAI Conference 2026 Conference Paper

On Generating Monolithic and Model Reconciling Explanations in Probabilistic Scenarios (Abstract Reprint)

• Stylianos Loukas Vasileiou
• William Yeoh
• Alessandro Previti
• Tran Cao Son

Explanation generation frameworks aim to make AI systems’ decisions transparent and understandable to human users. However, generating explanations in uncertain environments characterized by incomplete information and probabilistic models remains a significant challenge. In this paper, we propose a novel framework for generating probabilistic monolithic explanations and model reconciling explanations. Monolithic explanations provide self-contained reasons for an explanandum without considering the agent receiving the explanation, while model reconciling explanations account for the knowledge of the agent receiving the explanation. For monolithic explanations, our approach integrates uncertainty by utilizing probabilistic logic to increase the probability of the explanandum. For model reconciling explanations, we propose a framework that extends the logic-based variant of the model reconciliation problem to account for probabilistic human models, where the goal is to find explanations that increase the probability of the explanandum while minimizing conflicts between the explanation and the probabilistic human model. We introduce explanatory gain and explanatory power as quantitative metrics to assess the quality of these explanations. Further, we present algorithms that exploit the duality between minimal correction sets and minimal unsatisfiable sets to efficiently compute both types of explanations in probabilistic contexts. Extensive experimental evaluations on various benchmarks demonstrate the effectiveness and scalability of our approach in generating explanations under uncertainty.

KR Conference 2025 Conference Paper

A Methodology for Incompleteness-Tolerant and Modular Gradual Semantics for Argumentative Statement Graphs

• Antonio Rago
• Stylianos Loukas Vasileiou
• Son Tran
• Francesca Toni
• William Yeoh

Gradual semantics (GS) have demonstrated great potential in argumentation, in particular for deploying quantitative bipolar argumentation frameworks (QBAFs) in a number of real-world settings, from judgmental forecasting to explainable AI. In this paper, we provide a novel methodology for obtaining GS for statement graphs, a form of structured argumentation framework, where arguments and relations between them are built from logical statements. Our methodology differs from existing approaches in the literature in two main ways. First, it naturally accommodates incomplete information, so that arguments with partially specified premises can play a meaningful role in the evaluation. Second, it is modularly defined to leverage on any GS for QBAFs. We also define a set of novel properties for our GS and study their suitability alongside a set of existing properties (adapted to our setting) for two instantiations of our GS, demonstrating their advantages over existing approaches.

AAMAS Conference 2025 Conference Paper

DECAF: Learning to be Fair in Multi-agent Resource Allocation

• Ashwin Kumar
• William Yeoh

A wide variety of resource allocation problems operate under resource constraints that are managed by a central arbitrator, with agents who evaluate and communicate preferences over these resources. We formulate this broad class of problems as Distributed Evaluation, Centralized Allocation (DECA) problems and propose methods to learn fair and efficient policies in centralized resource allocation. Our methods are applied to learning long-term fairness in a novel and general framework for fairness in multi-agent systems. Our methods outperform existing fair MARL approaches on multiple resource allocation domains, even when evaluated using diverse fairness functions, and allow for flexible online trade-offs between utility and fairness.

AAAI Conference 2025 Conference Paper

Does Your AI Agent Get You? A Personalizable Framework for Approximating Human Models from Argumentation-based Dialogue Traces

• Yinxu Tang
• Stylianos Loukas Vasileiou
• William Yeoh

Explainable AI is increasingly employing argumentation methods to facilitate interactive explanations between AI agents and human users. While existing approaches typically rely on predetermined human user models, there remains a critical gap in dynamically learning and updating these models during interactions. In this paper, we present a framework that enables AI agents to adapt their understanding of human users through argumentation-based dialogues. Our approach, called Persona, draws on prospect theory and integrates a probability weighting function with a Bayesian belief update mechanism that refines a probability distribution over possible human models based on exchanged arguments. Through empirical evaluations with human users in an applied argumentation setting, we demonstrate that Persona effectively captures evolving human beliefs, facilitates personalized interactions, and outperforms state-of-the-art methods.

TMLR Journal 2025 Journal Article

Goal Recognition Design for General Behavioral Agents using Machine Learning

• Robert Kasumba
• Guanghui Yu
• Chien-Ju Ho
• Sarah Keren
• William Yeoh

Goal recognition design (GRD) aims to make limited modifications to decision-making environments to make it easier to infer the goals of agents acting within those environments. Although various research efforts have been made in goal recognition design, existing approaches are computationally demanding and often assume that agents are (near-)optimal in their decision-making. To address these limitations, we leverage machine learning methods for goal recognition design that can both improve run-time efficiency and account for agents with general behavioral models. Following existing literature, we use worst-case distinctiveness (wcd) as a measure of the difficulty in inferring the goal of an agent in a decision-making environment. Our approach begins by training a machine learning model to predict the wcd for a given environment and the agent behavior model. We then propose a gradient-based optimization framework that accommodates various constraints to optimize decision-making environments for enhanced goal recognition. Through extensive simulations, we demonstrate that our approach outperforms existing methods in reducing wcd and enhances runtime efficiency. Moreover, our approach also adapts to settings in which existing approaches do not apply, such as those involving flexible budget constraints, more complex environments, and suboptimal agent behavior. Finally, we conducted human-subject experiments that demonstrate that our method creates environments that facilitate efficient goal recognition from human decision-makers.

NeurIPS Conference 2025 Conference Paper

Model Reconciliation via Cost-Optimal Explanations in Probabilistic Logic Programming

• Yinxu Tang
• Stylianos Loukas Vasileiou
• Vincent Derkinderen
• William Yeoh

In human-AI interaction, effective communication relies on aligning the AI agent’s model with the human user’s mental model, a process known as model reconciliation. However, existing model reconciliation approaches predominantly assume deterministic models, overlooking the fact that human knowledge is often uncertain or probabilistic. To bridge this gap, we present a probabilistic model reconciliation framework that resolves inconsistencies in MPE outcome probabilities between an agent’s and a user’s models. Our approach is built on probabilistic logic programming (PLP) using ProbLog, where explanations are generated as cost-optimal model updates that reconcile these probabilistic differences. We develop two search algorithms -- a generic baseline and an optimized version. The latter is guided by theoretical insights and further extended with greedy and weighted variants to enhance scalability and efficiency. Our approach is validated through a user study on explanation types and computational experiments showing that the optimized version consistently outperforms the generic baseline.

JAIR Journal 2025 Journal Article

On Generating Monolithic and Model Reconciling Explanations in Probabilistic Scenarios

• Stylianos Loukas Vasileiou
• William Yeoh
• Alessandro Previti
• Tran Cao Son

Explanation generation frameworks aim to make AI systems’ decisions transparent and understandable to human users. However, generating explanations in uncertain environments characterized by incomplete information and probabilistic models remains a significant challenge. In this paper, we propose a novel framework for generating probabilistic monolithic explanations and model reconciling explanations. Monolithic explanations provide self-contained reasons for an explanandum without considering the agent receiving the explanation, while model reconciling explanations account for the knowledge of the agent receiving the explanation. For monolithic explanations, our approach integrates uncertainty by utilizing probabilistic logic to increase the probability of the explanandum. For model reconciling explanations, we propose a framework that extends the logic-based variant of the model reconciliation problem to account for probabilistic human models, where the goal is to find explanations that increase the probability of the explanandum while minimizing conflicts between the explanation and the probabilistic human model. We introduce explanatory gain and explanatory power as quantitative metrics to assess the quality of these explanations. Further, we present algorithms that exploit the duality between minimal correction sets and minimal unsatisfiable sets to efficiently compute both types of explanations in probabilistic contexts. Extensive experimental evaluations on various benchmarks demonstrate the effectiveness and scalability of our approach in generating explanations under uncertainty.

KR Conference 2025 System Paper

TRACE-CS: A Hybrid Logic–LLM System for Explainable Course Scheduling

• Stylianos Loukas Vasileiou
• William Yeoh

We present TRACE-cs, a novel hybrid system that combines logical reasoning with large language models (LLMs) to address contrastive queries in course scheduling problems. TRACE-cs leverages logic-based techniques to encode scheduling constraints and generate provably correct explanations, while utilizing an LLM to process natural language queries and refine logical explanations into user-friendly responses. This system showcases how combining symbolic KR methods with LLMs creates explainable AI agents that balance logical correctness with natural language accessibility, addressing a fundamental challenge in deployed scheduling systems.

AAAI Conference 2025 System Paper

TRACE-CS: A Synergistic Approach to Explainable Course Scheduling Using LLMs and Logic

• Stylianos Loukas Vasileiou
• William Yeoh

We present TRACE-cs, a novel hybrid system that combines symbolic reasoning with large language models (LLMs) to address contrastive queries in scheduling problems. TRACE-cs leverages SAT solving techniques to encode scheduling constraints and generate explanations for user queries, while utilizing an LLM to process the user queries into logical clauses as well as refine the explanations generated by the symbolic solver to natural language sentences. By integrating these components, our approach demonstrates the potential of combining symbolic methods with LLMs to create explainable AI agents with correctness guarantees.

HAXP Workshop 2025 Workshop Paper

When Humans Revise Their Beliefs, Explanations Matter: Evidence from User Studies and What It Means for AI Alignment

• Stylianos Loukas Vasileiou
• Antonio Rago
• Maria Vanina Martinez
• William Yeoh

Understanding how humans revise their beliefs in light of new information is crucial for developing AI agents which can effectively model, and thus align with, human reasoning and decision-making. Motivated by empirical evidence from cognitive psychology, in this paper we first present three comprehensive human-subject studies showing that people consistently prefer explanation-based revisions, i. e. , those which are guided by explanations, that result in changes to their belief agents that are more extensive than necessary. Our experiments systematically investigate how people revise their beliefs with explanations for inconsistencies, whether they are provided with them or left to formulate them themselves, demonstrating a robust preference for what may seem non-minimal revisions across different types of scenarios. Moreover, we evaluate to what extent large language models can simulate human belief revision patterns by testing state-of- the-art models on parallel tasks, analyzing their revision choices and alignment with human preferences. These findings have implications for AI agents designed to model and interact with humans, suggesting that such agents should accommodate explanation-based, potentially non-minimal belief revision operators to better align with human cognitive processes.

AAMAS Conference 2024 Conference Paper

Algorithmic Filtering, Out-Group Stereotype, and Polarization on Social Media

• Jean Springsteen
• William Yeoh
• Dino Christenson

The introduction of social media websites touted the idea of global communication — exposing users to a worldwide audience and a diverse range of experiences, opinions, and debates. Unfortunately, studies have shown that social networks have instead contributed to growing levels of polarization in society across a wide variety of issues. Social media websites employ algorithmic filtering strategies to drive engagement, which can lead to the formation of filter bubbles and increased levels of polarization. In this paper, we introduce features of affective polarization — feelings towards one’s in-group and out-group — into an opinion dynamics model. Specifically, we show that incorporating a negative out-group stereotype into the opinion dynamics model (1) affects the level of polarization present among agents in the network; (2) changes the effectiveness of algorithmic filtering strategies; and (3) is exacerbated by the presence of extremists in the network. Hence, the inclusion of an affective group mechanism in opinion dynamics modeling provides novel insights into the effects of algorithmic filtering strategies on the extremity of opinions in social networks.

HAXP Workshop 2024 Workshop Paper

Approximating Human Models During Argumentation-based Dialogues

• Yinxu Tang
• Stylianos Loukas Vasileiou
• William Yeoh

Explainable AI Planning (XAIP) aims to develop AI agents that can effectively explain their decisions and actions to human users, fostering trust and facilitating human-AI collaboration. A key challenge in XAIP is model reconciliation, which seeks to align the mental models of AI agents and humans. While existing approaches often assume a known and deterministic human model, this simplification may not capture the complexities and uncertainties of real-world interactions. In this paper, we propose a novel framework that enables AI agents to learn and update a probabilistic human model through argumentation-based dialogues. Our approach incorporates trust-based and certainty-based update mechanisms, allowing the agent to refine its understanding of the human's mental state based on the human's expressed trust in the agent's arguments and certainty in their own arguments. We employ a probability weighting function inspired by prospect theory to capture the relationship between trust and perceived probability, and use a Bayesian approach to update the agent's probability distribution over possible human models. We conduct a human-subject study to empirically evaluate the effectiveness of our approach in an argumentation scenario, demonstrating its ability to capture the dynamics of human belief formation and adaptation.

KR Conference 2024 System Paper

Dialectical Reconciliation via Structured Argumentative Dialogues

• Stylianos Loukas Vasileiou
• Ashwin Kumar
• William Yeoh
• Tran Cao Son
• Francesca Toni

We present a novel framework designed to extend model reconciliation approaches, commonly used in human-aware planning, for enhanced human-AI interaction. By adopting a structured argumentation-based dialogue paradigm, our framework enables dialectical reconciliation to address knowledge discrepancies between an explainer (AI agent) and an explainee (human user), where the goal is for the explainee to understand the explainer's decision. We formally describe the operational semantics of our proposed framework, providing theoretical guarantees. We then evaluate the framework's efficacy ``in the wild'' via computational and human-subject experiments. Our findings suggest that our framework offers a promising direction for fostering effective human-AI interactions in domains where explainability is important.

IJCAI Conference 2024 Conference Paper

Theoretical Study on Multi-objective Heuristic Search

• Shawn Skyler
• Shahaf Shperberg
• Dor Atzmon
• Ariel Felner
• Oren Salzman
• Shao-Hung Chan
• Han Zhang
• Sven Koenig

This paper provides a theoretical study on Multi-Objective Heuristic Search. We first classify states in the state space into must-expand, maybe-expand, and never-expand states and then transfer these definitions to nodes in the search tree. We then formalize a framework that generalizes A* to Multi-Objective Search. We study different ways to order nodes under this framework and their relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions.

IJCAI Conference 2023 Conference Paper

A Logic-based Explanation Generation Framework for Classical and Hybrid Planning Problems (Extended Abstract)

• Stylianos Loukas Vasileiou
• William Yeoh
• Son Tran
• Ashwin Kumar
• Michael Cashmore
• Daniele Magazzeni

In human-aware planning systems, a planning agent might need to explain its plan to a human user when that plan appears to be non-feasible or sub-optimal. A popular approach, called model reconciliation, has been proposed as a way to bring the model of the human user closer to the agent's model. In this paper, we approach the model reconciliation problem from a different perspective, that of knowledge representation and reasoning, and demonstrate that our approach can be applied not only to classical planning problems but also hybrid systems planning problems with durative actions and events/processes.

EAAI Journal 2023 Journal Article

A particle swarm inspired approach for continuous distributed constraint optimization problems

• Moumita Choudhury
• Amit Sarker
• Samin Yaser
• Md. Maruf Al Alif Khan
• William Yeoh
• Md. Mosaddek Khan

HAXP Workshop 2023 Workshop Paper

DR-HAI: Argumentation-based Dialectical Reconciliation in Human-AI Interactions

• Stylianos Loukas Vasileiou
• Ashwin Kumar
• William Yeoh

In this paper, we introduce DR-HAI (Dialectical Reconciliation in Human-AI Interactions), a novel game-theoretic framework designed to extend model reconciliation approaches for enhanced human-AI interaction. By adopting a multi-shot reconciliation paradigm and not assuming a-priori knowledge of the human user's model, DR-HAI enables interactive dialogues to address knowledge discrepancies between explainee and explainer agents. We provide formal operational semantics for DR-HAI using logic-based argumentation and offer theoretical guarantees regarding the framework's termination and success. Furthermore, we conduct a human-user study that compares DR-HAI to single-shot reconciliation approaches, demonstrating the efficacy of our framework in improving users' understanding of AI decisions in tasks characterized by substantial knowledge asymmetry. Our findings suggest that DR-HAI offers a promising direction for fostering effective human-AI interactions.

JAAMAS Journal 2023 Journal Article

Effect of asynchronous execution and imperfect communication on max-sum belief propagation

• Roie Zivan
• Ben Rachmut
• William Yeoh

Abstract Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems. It has been studied theoretically and empirically, extended to versions that improve solution quality and converge rapidly, and is applicable to multiple distributed applications. The algorithm was presented both as synchronous and asynchronous algorithms. However, neither the differences in the performance of the two execution versions nor the implications of imperfect communication (i. e. , massage delay and message loss) on the two versions have been investigated to the best of our knowledge. We contribute to the body of knowledge on Max-sum by: (1) Establishing the theoretical differences between the two execution versions of the algorithm, focusing on the construction of beliefs; (2) Empirically evaluating the differences between the solutions generated by the two versions of the algorithm, with and without message delay or loss; and (3) Establishing both theoretically and empirically the positive effect of damping on reducing the differences between the two versions. Our results indicate that, in contrast to recent published results indicating that message latency has a drastic (positive) effect on the performance of distributed local search algorithms, the effect of imperfect communication on Damped Max-sum (DMS) is minor. The version of Max-sum that includes both damping and splitting of function nodes converges to high quality solutions very fast, even when a large percentage of the messages sent by agents do not arrive at their destinations. Moreover, the quality of solutions in the different versions of DMS is dependent of the number of messages that were received by the agents, regardless of the amount of time they were delayed or if these messages are only a portion of the total number of messages that was sent by the agents.

IJCAI Conference 2023 Conference Paper

Multi-objective Search via Lazy and Efficient Dominance Checks

• Carlos Hernández
• William Yeoh
• Jorge A. Baier
• Ariel Felner
• Oren Salzman
• Han Zhang
• Shao-Hung Chan
• Sven Koenig

Multi-objective search can be used to model many real-world problems that require finding Pareto optimal paths from a specified start state to a specified goal state, while considering different costmetrics such as distance, time, and fuel. The performance of multi-objective search can be improved by making dominance checking—an operation necessary to determine whether or not a path dominates another—more efficient. This was shown in practice by BOA*, a state-of-the-art bi-objective search algorithm, which outperforms previously existing bi-objective search algorithms in part because it adopts a lazy approach towards dominance checking. EMOA*, a recent multi-objective search algorithm, generalizes BOA* to more-than-two objectives using AVL trees for dominance checking. In this paper, we first propose Linear-Time Multi-Objective A* (LTMOA*), an multi-objective search algorithm that implements a more efficient dominance checking than EMOA* using simple data structures like arrays. We then propose an even lazier approach towards dominance checking, and the resulting algorithm, LazyLTMOA*, distinguishes from EMOA* and LTMOA* by removing the dominance checking during node generation. Our experimental results show that LazyLTMOA* outperforms EMOA* by up to an order of magnitude in terms of runtime.

AIJ Journal 2023 Journal Article

Simple and efficient bi-objective search algorithms via fast dominance checks

• Carlos Hernández
• William Yeoh
• Jorge A. Baier
• Han Zhang
• Luis Suazo
• Sven Koenig
• Oren Salzman

JAIR Journal 2022 Journal Article

A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems

• Stylianos Loukas Vasileiou
• William Yeoh
• Tran Cao Son
• Ashwin Kumar
• Michael Cashmore
• Dianele Magazzeni

In human-aware planning systems, a planning agent might need to explain its plan to a human user when that plan appears to be non-feasible or sub-optimal. A popular approach, called model reconciliation, has been proposed as a way to bring the model of the human user closer to the agent’s model. To do so, the agent provides an explanation that can be used to update the model of human such that the agent’s plan is feasible or optimal to the human user. Existing approaches to solve this problem have been based on automated planning methods and have been limited to classical planning problems only. In this paper, we approach the model reconciliation problem from a different perspective, that of knowledge representation and reasoning, and demonstrate that our approach can be applied not only to classical planning problems but also hybrid systems planning problems with durative actions and events/processes. In particular, we propose a logic-based framework for explanation generation, where given a knowledge base KB a (of an agent) and a knowledge base KB h (of a human user), each encoding their knowledge of a planning problem, and that KB a entails a query q (e.g., that a proposed plan of the agent is valid), the goal is to identify an explanation ε ⊆ KB a such that when it is used to update KB h, then the updated KB h also entails q. More specifically, we make the following contributions in this paper: (1) We formally define the notion of logic-based explanations in the context of model reconciliation problems; (2) We introduce a number of cost functions that can be used to reflect preferences between explanations; (3) We present algorithms to compute explanations for both classical planning and hybrid systems planning problems; and (4) We empirically evaluate their performance on such problems. Our empirical results demonstrate that, on classical planning problems, our approach is faster than the state of the art when the explanations are long or when the size of the knowledge base is small (e.g., the plans to be explained are short). They also demonstrate that our approach is efficient for hybrid systems planning problems. Finally, we evaluate the real-world efficacy of explanations generated by our algorithms through a controlled human user study, where we develop a proof-of-concept visualization system and use it as a medium for explanation communication.

JAIR Journal 2022 Journal Article

Communication-Aware Local Search for Distributed Constraint Optimization

• Ben Rachmut
• Roie Zivan
• William Yeoh

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume that messages arrive instantaneously and are never lost. Specifically, distributed local search DCOP algorithms, have been designed as synchronous algorithms (i.e., they perform in synchronous iterations in which each agent exchanges messages with all its neighbors), despite running in asynchronous environments. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumption of perfect communication is relaxed, the properties that were established for the state-of-the-art local search algorithms and the anytime mechanism may not necessarily apply. In this work, we address this limitation by: (1) Proposing a Communication-Aware DCOP model (CA-DCOP) that can represent scenarios with different communication disturbances; (2) Investigating the performance of existing local search DCOP algorithms, specifically Distributed Stochastic Algorithm (DSA) and Maximum Gain Messages (MGM), in the presence of message latency and message loss; (3) Proposing a latency-aware monotonic distributed local search DCOP algorithm; and (4) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that imperfect communication has a positive effect on distributed local search algorithms due to increased exploration. Furthermore, the asynchronous anytime framework we proposed allows one to benefit from algorithms with inherent explorative heuristics.

JAIR Journal 2022 Journal Article

Proactive Dynamic Distributed Constraint Optimization Problems

• Khoi D. Hoang
• Ferdinando Fioretto
• Ping Hou
• William Yeoh
• Makoto Yokoo
• Roie Zivan

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. To solve DCOPs in a dynamic environment, Dynamic DCOPs (D-DCOPs) have been proposed to model the inherent dynamism present in many coordination problems. D-DCOPs solve a sequence of static problems by reacting to changes in the environment as the agents observe them. Such reactive approaches ignore knowledge about future changes of the problem. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model D-DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model possible changes of the problem and take such information into account when solving the dynamically changing problem in a proactive manner. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) We introduce Proactive Dynamic DCOPs (PD-DCOPs), which explicitly model how the DCOP will change over time; (ii) We develop exact and heuristic algorithms to solve PD-DCOPs in a proactive manner; (iii) We provide theoretical results about the complexity of this new class of DCOPs; and (iv) We empirically evaluate both proactive and reactive algorithms to determine the trade-offs between the two classes. The final contribution is important as our results are the first that identify the characteristics of the problems that the two classes of algorithms excel in.

AAAI Conference 2022 Conference Paper

Stochastic Goal Recognition Design Problems with Suboptimal Agents

• Christabel Wayllace
• William Yeoh

Goal Recognition Design (GRD) problems identify the minimum number of environmental modifications aiming to force an interacting agent to reveal its goal as early as possible. Researchers proposed several extensions to the original model, some of them handling stochastic agent action outcomes. While this generalization is useful, it assumes optimal acting agents, which limits its applicability. This paper presents the Suboptimal Stochastic GRD model, where we consider boundedly rational agents that, due to limited resources, might follow a suboptimal policy. Inspired by theories on human behavior asserting that humans are (close to) optimal when making perceptual decisions, we assume the chosen policy has at most u suboptimal actions. Our contribution includes (i) Extending the stochastic goal recognition design framework by supporting suboptimal agents in cases where an observer has either full or partial observability; (ii) Presenting methods to evaluate the ambiguity of the model under these assumptions; and (iii) Evaluating our approach on a range of benchmark applications.

AAMAS Conference 2021 Conference Paper

Branch-and-Bound Heuristics for Incomplete DCOPs

• Atena M. Tabakhi
• Yuanming Xiao
• William Yeoh
• Roie Zivan

The Incomplete Distributed Constraint Optimization Problem (I- DCOP) extends the distributed constraint optimization problem, where constraint costs are allowed to be unspeci�ed. A distributed variant of the Synchronous Branch-and-Bound (SyncBB) search algorithm has been proposed to solve I-DCOPs, where unspeci�ed constraint costs are elicited during its execution. In this paper, we propose two heuristics that can be used in conjunction with SyncBB to solve I-DCOPs. Our proposed heuristics speed up the algorithm by pruning those parts of the search space whose solution quality is sub-optimal. Thus, our model and heuristics extend the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.

AAMAS Conference 2021 Conference Paper

Latency-Aware Local Search for Distributed Constraint Optimization

• Ben Rachmut
• Roie Zivan
• William Yeoh

Most studies investigating models and algorithms for distributed constraint optimization problems (DCOPs) assume messages arrive instantaneously or within a (short) bounded delay. Specifically, distributed local search DCOP algorithms have been designed as synchronous algorithms, performing in an asynchronous environment, i. e. , algorithms that perform in synchronous iterations in which each agent exchanges messages with all its neighbors. This is true also for an anytime mechanism that reports the best solution explored during the run of synchronous distributed local search algorithms. Thus, when the assumptions on instantaneous message arrival are relaxed, the state of the art local search algorithms and mechanism do not apply. In this work, we address this limitation by: (1) Investigating the performance of existing local search DCOP algorithms in the presence of message latency; (2) Proposing an asynchronous monotonic distributed local search DCOP algorithm; and (3) Proposing an asynchronous anytime framework for reporting the best solution explored by non-monotonic asynchronous local search DCOP algorithms. Our empirical results demonstrate that, up to some extent, message delays have a positive effect on distributed local search algorithms due to increased exploration. The asynchronous anytime framework proposed, allows a maximal benefit from such latency based explorative heuristics.

AAAI Conference 2021 Conference Paper

On Exploiting Hitting Sets for Model Reconciliation

• Stylianos Loukas Vasileiou
• Alessandro Previti
• William Yeoh

In human-aware planning, a planning agent may need to provide an explanation to a human user on why its plan is optimal. A popular approach to do this is called model reconciliation, where the agent tries to reconcile the differences in its model and the human’s model such that the plan is also optimal in the human’s model. In this paper, we present a logicbased framework for model reconciliation that extends beyond the realm of planning. More specifically, given a knowledge base KB1 entailing a formula ϕ and a second knowledge base KB2 not entailing it, model reconciliation seeks an explanation, in the form of a cardinality-minimal subset of KB1, whose integration into KB2 makes the entailment possible. Our approach, based on ideas originating in the context of analysis of inconsistencies, exploits the existing hitting set duality between minimal correction sets (MCSes) and minimal unsatisfiable sets (MUSes) in order to identify an appropriate explanation. However, differently from those works targeting inconsistent formulas, which assume a single knowledge base, MCSes and MUSes are computed over two distinct knowledge bases. We conclude our paper with an empirical evaluation of the newly introduced approach on planning instances, where we show how it outperforms an existing stateof-the-art solver, and generic non-planning instances from recent SAT competitions, for which no other solver exists.

AAAI Conference 2020 System Paper

DRAGON-V: Detection and Recognition of Airplane Goals with Navigational Visualization

• Christabel Wayllace
• Sunwoo Ha
• Yuchen Han
• Jiaming Hu
• Shayan Monadjemi
• William Yeoh
• Alvitta Ottley

We introduce Detection and Recognition of Airplane GOals with Navigational Visualization (DRAGON-V), a visualization system that uses probabilistic goal recognition to infer and display the most probable airport runway that a pilot is approaching. DRAGON-V is especially useful in cases of miscommunication, low visibility, or lack of airport familiarity which may result in a pilot deviating from the assigned taxiing route. The visualization system conveys relevant information, and updates according to the airplane's current geolocation. DRAGON-V aims to assist air traffic controllers in reducing incidents of runway incursions at airports.

KR Conference 2020 Conference Paper

Explainable Planning Using Answer Set Programming

• Van Nguyen
• Stylianos Loukas Vasileiou
• Tran Cao Son
• William Yeoh

In human-aware planning problems, the planning agent may need to explain its plan to a human user, especially when the plan appears infeasible or suboptimal for the user. A popular approach to do so is called model reconciliation, where the planning agent tries to reconcile the differences between its model and the model of the user such that its plan is also feasible and optimal to the user. This problem can be viewed as an optimization problem, where the goal is to find a subset-minimal explanation that one can use to modify the model of the user such that the plan of the agent is also feasible and optimal to the user. This paper presents an algorithm for solving such problems using answer set programming.

JAIR Journal 2019 Journal Article

Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm

• Duc Thien Nguyen
• William Yeoh
• Hoong Chuin Lau
• Roie Zivan

Researchers have used distributed constraint optimization problems (DCOPs) to model various multi-agent coordination and resource allocation problems. Very recently, Ottens et al. proposed a promising new approach to solve DCOPs that is based on confidence bounds via their Distributed UCT (DUCT) sampling-based algorithm. Unfortunately, its memory requirement per agent is exponential in the number of agents in the problem, which prohibits it from scaling up to large problems. Thus, in this article, we introduce two new sampling-based DCOP algorithms called Sequential Distributed Gibbs (SD-Gibbs) and Parallel Distributed Gibbs (PD-Gibbs). Both algorithms have memory requirements per agent that is linear in the number of agents in the problem. Our empirical results show that our algorithms can find solutions that are better than DUCT, run faster than DUCT, and solve some large problems that DUCT failed to solve due to memory limitations.

AAMAS Conference 2019 Conference Paper

Parameterized Heuristics for Incomplete Weighted CSPs with Elicitation Costs

• Atena M. Tabakhi
• William Yeoh
• Makoto Yokoo

Weighted Constraint Satisfaction Problems (WCSPs) are an elegant paradigm for modeling combinatorial optimization problems. A key assumption in this model is that all constraints are specified or known a priori, which does not hold in some applications where constraints may encode preferences of human users. Incomplete WCSPs (IWCSPs) extend WCSPs by allowing some constraints to be partially specified, and they can be elicited from human users during the execution of IWCSP algorithms. Unfortunately, existing approaches assume that the elicitation of preferences does not incur any additional cost. This assumption is unrealistic as human users are likely bothered by repeated elicitations and will refuse to provide an unbounded number of preferences. Therefore, we propose the IWCSP with Elicitation Cost (IWCSP+EC) model, which extends IWCSPs to include elicitation costs, as well as three parameterized heuristics that allow users to trade off solution quality for fewer elicited preferences and faster computation times. They provide theoretical quality guarantees for problems where elicitations are free. Our model and heuristics thus extend the state of the art in constraint reasoning to better model and solve agent-based applications with user preferences.

AAMAS Conference 2018 Conference Paper

A Near-Optimal Node-to-Agent Mapping Heuristic for GDL-Based DCOP Algorithms in Multi-Agent Systems

• Md. Mosaddek Khan
• Long Tran-Thanh
• William Yeoh
• Nicholas R. Jennings

Distributed Constraint Optimization Problems (DCOPs) can be used to model a number of multi-agent coordination problems. The conventional DCOP model assumes that the subproblem that each agent is responsible for (i. e. the mapping of nodes in the constraint graph to agents) is part of the model description. While this assumption is often reasonable, there are many applications where there is some flexibility in making this assignment. In this paper, we focus on this gap and make the following contributions: (1) We formulate this problem as an optimization problem, where the goal is to find an assignment that minimizes the completion time of the DCOP algorithm (e. g. Action-GDL or Max-Sum) that operates on this mapping. (2) We propose a novel heuristic, called MNA, that can be executed in a centralized or decentralized manner. (3) Our empirical evaluation illustrates a substantial reduction in completion time, ranging from 16% to 40%, without affecting the solution quality of the algorithms, compared to the current state of the art. In addition, we observe empirically that the completion time obtained from our approach is near-optimal; it never exceeds more than 10% of what can be achieved from the optimal node-to-agent mapping.

IJCAI Conference 2018 Conference Paper

Bidding in Periodic Double Auctions Using Heuristics and Dynamic Monte Carlo Tree Search

• Moinul Morshed Porag Chowdhury
• Christopher Kiekintveld
• Son Tran
• William Yeoh

In a Periodic Double Auction (PDA), there are multiple discrete trading periods for a single type of good. PDAs are commonly used in real-world energy markets to trade energy in specific time slots to balance demand on the power grid. Strategically, bidding in a PDA is complicated because the bidder must predict and plan for future auctions that may influence the bidding strategy for the current auction. We present a general bidding strategy for PDAs based on forecasting clearing prices and using Monte Carlo Tree Search (MCTS) to plan a bidding strategy across multiple time periods. In addition, we present a fast heuristic strategy that can be used either as a standalone method or as an initial set of bids to seed the MCTS policy. We evaluate our bidding strategies using a PDA simulator based on the wholesale market implemented in the Power Trading Agent Competition (PowerTAC) competition. We demonstrate that our strategies outperform state-of-the-art bidding strategies designed for that competition.

AAMAS Conference 2018 Conference Paper

Bidding Strategy for Periodic Double Auctions Using Monte Carlo Tree Search

• Moinul Morshed Porag Chowdhury
• Christopher Kiekintveld
• Tran Cao Son
• William Yeoh

Bidding strategies for Periodic Double Auctions (PDAs) are complicated because they need to predict and plan for future auctions, which may affect the bidding strategy in the current auction. We present a general bidding strategy for PDAs based on forecasting clearing prices and using Monte Carlos Tree Search (MCTS) to plan a bidding strategy across multiple time periods. We developed a controlled simulator by isolating Power Trading Agent Competition’s wholesale market to evaluate bidding strategies in a realistic PDA energy market. We show that our MCTS bidding strategy is cost effective in buying energy compared to other baseline and state-ofthe-art strategies and it’s performance improves with increasing number of MCTS simulations.

JAIR Journal 2018 Journal Article

Distributed Constraint Optimization Problems and Applications: A Survey

• Ferdinando Fioretto
• Enrico Pontelli
• William Yeoh

The field of multi-agent system (MAS) is an active area of research within artificial intelligence, with an increasingly important impact in industrial and other real-world applications. In a MAS, autonomous agents interact to pursue personal interests and/or to achieve common objectives. Distributed Constraint Optimization Problems (DCOPs) have emerged as a prominent agent model to govern the agents' autonomous behavior, where both algorithms and communication models are driven by the structure of the specific problem. During the last decade, several extensions to the DCOP model have been proposed to enable support of MAS in complex, real-time, and uncertain environments. This survey provides an overview of the DCOP model, offering a classification of its multiple extensions and addressing both resolution methods and applications that find a natural mapping within each class of DCOPs. The proposed classification suggests several future perspectives for DCOP extensions and identifies challenges in the design of efficient resolution algorithms, possibly through the adaptation of strategies from different areas.

AAMAS Conference 2018 Conference Paper

Preference Elicitation with Interdependency and User Bother Cost

• Tiep Le
• Atena M. Tabakhi
• Long Tran-Thanh
• William Yeoh
• Tran Cao Son

Agent-based scheduling systems, such as automated systems that schedule meetings for users and systems that schedule smart devices in smart homes, require the elicitation of user preferences in oder to operate in a manner that is consistent with user expectations. Unfortunately, interactions between such systems and users can be limited as human users prefer to not be overly bothered by such systems. As such, a key challenge is for the system to efficiently elicit key preferences without bothering the users too much. To tackle this problem, we propose a cost model that captures the cognitive or bother cost associated with asking a question. We incorporate this model into our iPLEASE system, an interactive preference elicitation approach. iPLEASE represents a user’s preferences as a matrix, called preference matrix, and uses heuristics to select, from a given set of questions, an efficient sequence of questions to ask the user such that the total bother cost incurred to the user does not exceed a given bother cost budget. The user’s response to those questions will partially populate the preference matrix. It then performs an exact matrix completion via convex optimization to approximate the remaining preferences that are not directly elicited. We empirically apply iPLEASE on randomly-generated problems as well as on a real-world dataset for the smart device scheduling problem to demonstrate that our approach outperforms other non-trivial benchmarks in eliciting user preferences.

TIST Journal 2018 Journal Article

Risk-Sensitive Stochastic Orienteering Problems for Trip Optimization in Urban Environments

• Pradeep Varakantham
• Akshat Kumar
• Hoong Chuin Lau
• William Yeoh

Orienteering Problems (OPs) are used to model many routing and trip planning problems. OPs are a variant of the well-known traveling salesman problem where the goal is to compute the highest reward path that includes a subset of vertices and has an overall travel time less than a specified deadline. However, the applicability of OPs is limited due to the assumption of deterministic and static travel times. To that end, Campbell et al. extended OPs to Stochastic OPs (SOPs) to represent uncertain travel times (Campbell et al. 2011). In this article, we make the following key contributions: (1) We extend SOPs to Dynamic SOPs (DSOPs), which allow for time-dependent travel times; (2) we introduce a new objective criterion for SOPs and DSOPs to represent a percentile measure of risk; (3) we provide non-linear optimization formulations along with their linear equivalents for solving the risk-sensitive SOPs and DSOPs; (4) we provide a local search mechanism for solving the risk-sensitive SOPs and DSOPs; and (5) we provide results on existing benchmark problems and a real-world theme park trip planning problem.

IJCAI Conference 2018 Conference Paper

Towards Improving the Expressivity and Scalability of Distributed Constraint Optimization Problems

• William Yeoh

Constraints have long been studied in centralized systems and have proven to be practical and efficient for modeling and solving resource allocation and scheduling problems. Slightly more than a decade ago, researchers proposed the distributed constraint optimization problem (DCOP) formulation, which is well suited for modeling distributed multi-agent coordination problems. In this paper, we highlight some of our recent contributions that are aiming towards improved expressivity of the DCOP model as well as improved scalability of the accompanying algorithms.

AAMAS Conference 2017 Conference Paper

A Distributed Constraint Optimization (DCOP) Approach to the Economic Dispatch with Demand Response

• Ferdinando Fioretto
• William Yeoh
• Enrico Pontelli
• Ye Ma
• Satishkumar J. Ranade

With the growing complexity of the current power grid, there is an increasing need for intelligent operations coordinating energy supply and demand. A key feature of the smart grid vision is that intelligent mechanisms will coordinate the production, transmission, and consumption of energy in a distributed and reliable way. Economic Dispatch (ED) and Demand Response (DR) are two key problems that need to be solved to achieve this vision. In traditional operations, ED and DR are implemented separately, despite the strong inter-dependencies between these two problems. Therefore, we propose an integrated approach to solve the ED and DR problems that simultaneously maximizes the benefits of customers and minimizes the generation costs, and introduce an effective multi-agent-based algorithm, based on Distributed Constraint Optimization Problems (DCOPs), acting on direct control of both generators and dispatchable loads. To cope with the high complexity of the problem, our solution employs General Purpose Graphical Processing Units (GPGPUs) to speed up the computational runtime. We empirically evaluate the proposed algorithms on standard IEEE bus systems and test the stability of the proposed solution with a state-of-the-art power system simulator on the IEEE 30-bus system.

AAMAS Conference 2017 Conference Paper

A Multiagent System Approach to Scheduling Devices in Smart Homes

• Ferdinando Fioretto
• William Yeoh
• Enrico Pontelli

Demand-side management (DSM) in the smart grid allows customers to make autonomous decisions on their energy consumption, helping energy providers to reduce the energy peaks in load demand. The automated scheduling of smart devices in residential and commercial buildings plays a key role in DSM. Due to data privacy and user autonomy, such an approach is best implemented through distributed multiagent systems. This paper makes the following contributions: (i) It introduces the Smart Home Device Scheduling (SHDS) problem, which formalizes the device scheduling and coordination problem across multiple smart homes as a multi-agent system; (ii) It describes a mapping of this problem to a distributed constraint optimization problem; (iii) It proposes a distributed algorithm for the SHDS problem; and (iv) It presents empirical results from a physically distributed system of Raspberry Pis, each capable of controlling smart devices through hardware interfaces, as well as larger scale synthetic experiments.

IJCAI Conference 2017 Conference Paper

Generalized Target Assignment and Path Finding Using Answer Set Programming

• Van Nguyen
• Philipp Obermeier
• Tran Cao Son
• Torsten Schaub
• William Yeoh

In Multi-Agent Path Finding (MAPF), a team of agents needs to find collision-free paths from their starting locations to their respective targets. Combined Target Assignment and Path Finding (TAPF) extends MAPF by including the problem of assigning targets to agents as a precursor to the MAPF problem. A limitation of both models is their assumption that the number of agents and targets are equal, which is invalid in some applications such as autonomous warehouse systems. We address this limitation by generalizing TAPF to allow for (1)~unequal number of agents and tasks; (2)~tasks to have deadlines by which they must be completed; (3)~ordering of groups of tasks to be completed; and (4)~tasks that are composed of a sequence of checkpoints that must be visited in a specific order. Further, we model the problem using answer set programming (ASP) to show that customizing the desired variant of the problem is simple one only needs to choose the appropriate combination of ASP rules to enforce it. We also demonstrate experimentally that if problem specific information can be incorporated into the ASP encoding then ASP based method can be efficient and can scale up to solve practical applications.

AAMAS Conference 2017 Conference Paper

Infinite-Horizon Proactive Dynamic DCOPs

• Khoi D. Hoang
• Ping Hou
• Ferdinando Fioretto
• William Yeoh
• Roie Zivan
• Makoto Yokoo

The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multi-agent coordination problems. Researchers have recently extended this model to Proactive Dynamic DCOPs (PD-DCOPs) to capture the inherent dynamism present in many coordination problems. The PD-DCOP formulation is a finite-horizon model that assumes a finite horizon is known a priori. It ignores changes to the problem after the horizon and is thus not guaranteed to find optimal solutions for infinite-horizon problems, which often occur in the real world. Therefore, we (i) propose the Infinite-Horizon PD-DCOP (IPD- DCOP) model, which extends PD-DCOPs to handle infinite horizons; (ii) exploit the convergence properties of Markov chains to determine the optimal solution to the problem after it has converged; (iii) propose three distributed greedy algorithms to solve IPD-DCOPs; (iv) provide theoretical quality guarantees on the new model; and (v) empirically evaluate both proactive and reactive algorithms to determine the tradeoffs between the two classes. The final contribution is important as, thus far, researchers have exclusively evaluated the two classes of algorithms in isolation. As a result, it is difficult to identify the characteristics of problems that they excel in. Our results are the first in this important direction.

IJCAI Conference 2017 Conference Paper

New Metrics and Algorithms for Stochastic Goal Recognition Design Problems

• Christabel Wayllace
• Ping Hou
• William Yeoh

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. The Stochastic GRD (S-GRD) model is an important extension that introduced stochasticity to the outcome of agent actions. Unfortunately, the worst-case distinctiveness (wcd) metric proposed for S-GRDs has a formal definition that is inconsistent with its intuitive definition, which is the maximal number of actions an agent can take, in the expectation, before its goal is revealed. In this paper, we make the following contributions: (1) We propose a new wcd metric, called all-goals wcd (wcdag), that remedies this inconsistency; (2) We introduce a new metric, called expected-case distinctiveness (ecd), that weighs the possible goals based on their importance; (3) We provide theoretical results comparing these different metrics as well as the complexity of computing them optimally; and (4) We describe new efficient algorithms to compute the wcdag and ecd values.

IS Journal 2016 Journal Article

AI's 10 to Watch

• Haris Aziz
• Elias Bareinboim
• Yejin Choi
• Daniel Hsu
• Shivaram Kalyanakrishnan
• Reshef Meir
• Suchi Saria
• Gerardo I. Simari

IEEE Intelligent Systems once again selected 10 young AI scientists as " AI's 10 to Watch. " This acknowledgment and celebration not only recognizes these young scientists and makes a positive impact in their academic career but also promotes the community and cutting-edge AI research among next-generation AI researchers, the industry, and the general public alike. The contributions are "Collective Decision Making in Multi-Agent Systems, " by Haris Aziz, "From Causal Inference and Data Fusion to an Automated Scientist, " by Elias Bareinboim, "Language, Vision, and Social AI, " by Yejin Choi, "Algorithms for Machine Learning, " by Daniel Hsu, "Learning Agents, " by Shivaram Kalyanakrishnan, "Strategy and Bounded Rationality, " by Reshef Meir, "; A Reasoning Engine for Tailoring Healthcare to the Individual, " by Suchi Saria, "Pushing the Limits of Knowledge Representation and Reasoning, " by Gerardo I. Simari, "Better Group Decision Making, " by Lirong Xia, and "Distributed Constraint Optimization, " by William Yeoh.

AAMAS Conference 2016 Conference Paper

ER-DCOPs: A Framework for Distributed Constraint Optimization with Uncertainty in Constraint Utilities

• Tiep Le
• Ferdinando Fioretto
• William Yeoh
• Tran Cao Son
• Enrico Pontelli

Distributed Constraint Optimization Problems (DCOPs) have been used to model a number of multi-agent coordination problems. In DCOPs, agents are assumed to have complete information about the utility of their possible actions. However, in many real-world applications, such utilities are stochastic due to the presence of exogenous events that are beyond the direct control of the agents. This paper addresses this issue by extending the standard DCOP model to Expected Regret DCOP (ER-DCOP) for DCOP applications with uncertainty in constraint utilities. Different from other approaches, ER-DCOPs aim at minimizing the overall expected regret of the problem. The paper proposes the ER-DPOP algorithm for solving ER-DCOPs, which is complete and requires a linear number of messages with respect to the number of agents in the problem. We further present two implementations of ER-DPOP— GPU- and ASP-based implementations—that orthogonally exploit the problem structure and present their evaluations on random networks and power network problems.

IJCAI Conference 2016 Conference Paper

Goal Recognition Design with Stochastic Agent Action Outcomes

• Christabel Wayllace
• Ping Hou
• William Yeoh
• Tran Cao Son

Goal Recognition Design (GRD) problems involve identifying the best ways to modify the underlying environment that the agents operate in, typically by making a subset of feasible actions infeasible, in such a way that agents are forced to reveal their goals as early as possible. Thus far, existing work assumes that the outcomes of the actions of the agents are deterministic, which might be unrealistic in real-world problems. For example, wheel slippage in robots cause the outcomes of their movements to be stochastic. In this paper, we generalize the GRD problem to Stochastic GRD (S-GRD) problems, which handle stochastic action outcomes. We also generalize the worst-case distinctiveness (wcd) measure, which measures the goodness of a solution, to take stochasticity into account. Finally, we introduce Markov decision process (MDP) based algorithms to compute the wcd and minimize it by making up to k actions infeasible.

AAAI Conference 2016 Conference Paper

Multi-Variable Agents Decomposition for DCOPs

• Ferdinando Fioretto
• William Yeoh
• Enrico Pontelli

The application of DCOP models to large problems faces two main limitations: (i) Modeling limitations, as each agent can handle only a single variable of the problem; and (ii) Resolution limitations, as current approaches do not exploit the local problem structure within each agent. This paper proposes a novel Multi-Variable Agent (MVA) DCOP decomposition technique, which: (i) Exploits the co-locality of each agent’s variables, allowing us to adopt efficient centralized techniques within each agent; (ii) Enables the use of hierarchical parallel models and proposes the use of GPUs; and (iii) Reduces the amount of computation and communication required in several classes of DCOP algorithms.

AAMAS Conference 2016 Conference Paper

Proactive Dynamic Distributed Constraint Optimization

• Khoi D. Hoang
• Ferdinando Fioretto
• Ping Hou
• Makoto Yokoo
• William Yeoh
• Roie Zivan

Current approaches that model dynamism in DCOPs solve a sequence of static problems, reacting to changes in the environment as the agents observe them. Such approaches thus ignore possible predictions on future changes. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PD-DCOPs), a novel formalism to model dynamic DCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PD-DCOPs are able to explicitly model the possible changes to the problem, and take such information into account proactively, when solving the dynamically changing problem. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) we introduce the PD-DCOP model, which explicitly captures dynamic changes of the DCOP over time; (ii) we discuss the complexity of this new class of DCOPs; and (iii) we develop both exact and approximation algorithms with quality guarantees to solve PD- DCOPs proactively.

IJCAI Conference 2016 Conference Paper

Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning

• Pritee Agrawal
• Pradeep Varakantham
• William Yeoh

Synergistic interactions between task/resource allocation and stochastic planning exist in many environments such as transportation and logistics, UAV task assignment and disaster rescue. Existing research in exploiting these synergistic interactions between the two problems have either only considered domains where tasks/resources are completely independent of each other or have focussed on approaches with limited scalability. In this paper, we address these two limitations by introducing a generic model for task/resource constrained multi-agent stochastic planning, referred to as TasC-MDPs. We provide two scalable greedy algorithms, one of which provides posterior quality guarantees. Finally, we illustrate the high scalability and solution performance of our approaches in comparison with existing work on two benchmark problems from the literature.

AAAI Conference 2016 Conference Paper

Solving Goal Recognition Design Using ASP

• Tran Son
• Orkunt Sabuncu
• Christian Schulz-Hanke
• Torsten Schaub
• William Yeoh

Goal Recognition Design involves identifying the best ways to modify an underlying environment that agents operate in, typically by making a subset of feasible actions infeasible, so that agents are forced to reveal their goals as early as possible. Thus far, existing work has focused exclusively on imperative classical planning. In this paper, we address the same problem with a different paradigm, namely, declarative approaches based on Answer Set Programming (ASP). Our experimental results show that one of our ASP encodings is more scalable and is significantly faster by up to three orders of magnitude than the current state of the art.

AAAI Conference 2016 Conference Paper

Solving Risk-Sensitive POMDPs With and Without Cost Observations

• Ping Hou
• William Yeoh
• Pradeep Varakantham

Partially Observable Markov Decision Processes (POMDPs) are often used to model planning problems under uncertainty. The goal in Risk-Sensitive POMDPs (RS-POMDPs) is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, unlike existing POMDP literature, we distinguish between the two cases of whether costs can or cannot be observed and show the empirical impact of cost observations. We also introduce a new search-based algorithm to solve RS-POMDPs and show that it is faster and more scalable than existing approaches in two synthetic domains and a taxi domain generated with real-world data.

AAAI Conference 2015 Conference Paper

Solving Distributed Constraint Optimization Problems Using Logic Programming

• Tiep Le
• Tran Son
• Enrico Pontelli
• William Yeoh

This paper explores the use of answer set programming (ASP) in solving distributed constraint optimization problems (DCOPs). It makes the following contributions: (i) It shows how one can formulate DCOPs as logic programs; (ii) It introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (iii) It experimentally shows that ASP-DPOP can be up to two orders of magnitude faster than DPOP (its imperative-programming counterpart) as well as solve some problems that DPOP fails to solve due to memory limitations; and (iv) It demonstrates the applicability of ASP in the wide array of multi-agent problems currently modeled as DCOPs.

AAAI Conference 2014 Conference Paper

A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints

• T. K. Satish Kumar
• Duc Thien Nguyen
• William Yeoh
• Sven Koenig

In this paper, we describe a simple randomized algorithm that runs in polynomial time and solves connected row convex (CRC) constraints in distributed settings. CRC constraints generalize many known tractable classes of constraints like 2- SAT and implicational constraints. They can model problems in many domains including temporal reasoning and geometric reasoning, and generally speaking, play the role of “Gaussians” in the logical world. Our simple randomized algorithm for solving them in distributed settings, therefore, has a number of important applications. We support our claims through a theoretical analysis and empirical results.

AAAI Conference 2014 Conference Paper

Decentralized Multi-Agent Reinforcement Learning in Average-Reward Dynamic DCOPs

• Duc Thien Nguyen
• William Yeoh
• Hoong Chuin Lau
• Shlomo Zilberstein
• Chongjie Zhang

Researchers have introduced the Dynamic Distributed Constraint Optimization Problem (Dynamic DCOP) formulation to model dynamically changing multi-agent coordination problems, where a dynamic DCOP is a sequence of (static canonical) DCOPs, each partially different from the DCOP preceding it. Existing work typically assumes that the problem in each time step is decoupled from the problems in other time steps, which might not hold in some applications. Therefore, in this paper, we make the following contributions: (i) We introduce a new model, called Markovian Dynamic DCOPs (MD-DCOPs), where the DCOP in the next time step is a function of the value assignments in the current time step; (ii) We introduce two distributed reinforcement learning algorithms, the Distributed RVI Q-learning algorithm and the Distributed R-learning algorithm, that balance exploration and exploitation to solve MD-DCOPs in an online manner; and (iii) We empirically evaluate them against an existing multiarm bandit DCOP algorithm on dynamic DCOPs.

AAAI Conference 2014 Conference Paper

Solving Uncertain MDPs by Reusing State Information and Plans

• Ping Hou
• William Yeoh
• Tran Cao Son

While MDPs are powerful tools for modeling sequential decision making problems under uncertainty, they are sensitive to the accuracy of their parameters. MDPs with uncertainty in their parameters are called Uncertain MDPs. In this paper, we introduce a general framework that allows off-theshelf MDP algorithms to solve Uncertain MDPs by planning based on currently available information and replan if and when the problem changes. We demonstrate the generality of this approach by showing that it can use the VI, TVI, ILAO*, LRTDP, and UCT algorithms to solve Uncertain MDPs. We experimentally show that our approach is typically faster than replanning from scratch and we also provide a way to estimate the amount of speedup based on the amount of information being reused.

IJCAI Conference 2013 Conference Paper

Automated Generation of Interaction Graphs for Value-Factored Decentralized POMDPs

• William Yeoh
• Akshat Kumar
• Shlomo Zilberstein

The Decentralized Partially Observable Markov Decision Process (Dec-POMDP) is a powerful model for multiagent planning under uncertainty, but its applicability is hindered by its high complexity – solving Dec-POMDPs optimally is NEXP-hard. Recently, Kumar et al. introduced the Value Factorization (VF) framework, which exploits decomposable value functions that can be factored into subfunctions. This framework has been shown to be a generalization of several models that leverage sparse agent interactions such as TI-Dec-MDPs, ND- POMDPs and TD-POMDPs. Existing algorithms for these models assume that the interaction graph of the problem is given. In this paper, we introduce three algorithms to automatically generate interaction graphs for models within the VF framework and establish lower and upper bounds on the expected reward of an optimal joint policy. We illustrate experimentally the benefits of these techniques for sensor placement in a decentralized tracking application.

AAMAS Conference 2012 Conference Paper

Lagrangian Relaxation for Large-Scale Multi-Agent Planning

• Geoff Gordon
• Pradeep Varakantham
• William Yeoh
• Hoong Chuin Lau
• Ajay Srinivasan Aravamudhan
• Shih-Fen Cheng

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limits. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of convergence of our algorithm to a near-optimal solution.

AAMAS Conference 2012 Conference Paper

Prioritized Shaping of Models for Solving DEC-POMDPs

• Pradeep Varakantham
• William Yeoh
• Prasanna Velagapudi
• Katia Sycara
• Paul Scerri

An interesting class of multi-agent POMDP planning problems can be solved by having agents iteratively solve individual POMDPs, find interactions with other individual plans, shape their transition and reward functions to encourage good interactions and discourage bad ones and then recompute a new plan. D-TREMOR showed that this approach can allow distributed planning for hundreds of agents. However, the quality and speed of the planning process depends on the prioritization scheme used. Lower priority agents shape their models with respect to the models of higher priority agents. In this paper, we introduce a new prioritization scheme that is guaranteed to converge and is empirically better, in terms of solution quality and planning time, than the existing prioritization scheme for some problems.

AAMAS Conference 2012 Conference Paper

Stochastic Dominance in Stochastic DCOPs for Risk Sensitive Applications

• Duc Thien Nguyen
• William Yeoh
• Hoong Chuin Lau

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems where the primary interactions are between local subsets of agents. However, one limitation of DCOPs is the assumption that the constraint rewards are without uncertainty. Researchers have thus extended DCOPs to Stochastic DCOPs (SDCOPs), where rewards are sampled from known probability distribution reward functions, and introduced algorithms to find solutions with the largest expected reward. Unfortunately, such a solution might be very \emph{risky}, that is, very likely to result in a poor reward. Thus, in this paper, we make three contributions: (1) we propose a stricter objective for SDCOPs, namely to find a solution with the most stochastically dominating probability distribution reward function; (2) we introduce an algorithm to find such solutions; and (3) we show that stochastically dominating solutions can indeed be less risky than expected reward maximizing solutions.

IJCAI Conference 2011 Conference Paper

Generalizing ADOPT and BnB-ADOPT

• Patricia Gutierrez
• Pedro Meseguer
• William Yeoh

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = &infin; and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < &infin; . We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

AAMAS Conference 2011 Conference Paper

Incremental DCOP Search Algorithms for Solving Dynamic DCOPs

• William Yeoh
• Pradeep Varakantham
• Xiaoxun Sun
• Sven Koenig

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.

AAMAS Conference 2010 Conference Paper

Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Moving target search is important for robotics applicationswhere unmanned ground vehicles (UGVs) have to followother friendly or hostile UGVs. Artificial intelligence researchers have recently used incremental search to speedup the computation of a simple strategy for the hunter. The fastest incremental search algorithm, Fringe-RetrievingA*, solves moving target search problems only on two-dimensional grids, which are rather unrealistic models forrobotics applications. We therefore generalize it to Generalized Fringe-Retrieving A*, which solves moving target searchproblems on arbitrary graphs, including the state latticesused for UGV navigation.

AAAI Conference 2010 Conference Paper

Model AI Assignments

• Todd Neller
• John DeNero
• Dan Klein
• Sven Koenig
• William Yeoh
• Xiaoming Zheng
• Kenny Daniel
• Alex Nash

AAMAS Conference 2010 Conference Paper

Moving Target D* Lite

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Incremental search algorithms, such as Generalized Fringe-Retrieving A* and D* Lite, reuse search trees from previous searches to speed up the current search and thus oftenfind cost-minimal paths for series of similar search problemsfaster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving targetsearch problems, where both the start and goal states canchange over time. In this paper, we therefore introduceMoving Target D* Lite, an extension of D* Lite that usesthe principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter tothe target in environments whose blockages can change overtime. We demonstrate experimentally that Moving TargetD* Lite is four to five times faster than Generalized AdaptiveA*, which so far was believed to be the fastest incrementalsearch algorithm for solving moving target search problemsin dynamic environments.

IJCAI Conference 2009 Conference Paper

• William Yeoh
• Xiaoxun Sun
• Sven Koenig

Distributed Constraint Optimization (DCOP) is a key technique for solving agent coordination problems. Because finding cost-minimal DCOP solutions is NP-hard, it is important to develop mechanisms for DCOP search algorithms that trade off their solution costs for smaller runtimes. However, existing tradeoff mechanisms do not provide relative error bounds. In this paper, we introduce three tradeoff mechanisms that provide such bounds, namely the Relative Error Mechanism, the Uniformly Weighted Heuristics Mechanism and the Non-Uniformly Weighted Heuristics Mechanism, for two DCOP algorithms, namely ADOPT and BnB-ADOPT. Our experimental results show that the Relative Error Mechanism generally dominates the other two tradeoff mechanisms for ADOPT and the Uniformly Weighted Heuristics Mechanism generally dominates the other two tradeoff mechanisms for BnB-ADOPT.

IJCAI Conference 2009 Conference Paper

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds.

AAMAS Conference 2009 Conference Paper

Dynamic Fringe-Saving A*

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Fringe-Saving A* is an incremental version of A* that repeatedly finds shortest paths from a fixed start cell to a fixed goal cell in a known gridworld in case the traversability of cells changes over time. It restores the content of the OPEN and CLOSED lists of A* at the point in time when an A* search for the current search problem could deviate from the A* search for the previous search problem. Thus, Fringe- Saving A* reuses the beginning of the previous A* search that is identical to the current A* search. In this paper, we generalize the correctness proof of Fringe-Saving A* to cover the case where the goal cell changes over time in addition to the traversability of cells. We then apply Fringe-Saving A* to the problem of moving an agent along a shortest path from its current cell to a fixed destination cell in a known gridworld, where the shortest path is replanned whenever the traversability of cells changes. Our experimental results show that the resulting Dynamic Fringe-Saving A* algorithm can outperform both repeated A* searches and D* Lite (a state-of-the-art incremental version of A*) in highly dynamic gridworlds, with runtime savings of up to a factor of about 2. 5.

AAMAS Conference 2009 Conference Paper

Simple Optimization Techniques for A*-Based Search

• Xiaoxun Sun
• William Yeoh
• Po-An Chen
• Sven Koenig

In this paper, we present two simple optimizations that can reduce the number of priority queue operations for A* and its extensions. Basically, when the optimized search algorithms expand a state, they check whether they will expand a successor of the state next. If so, they do not first insert it into the priority queue and then immediately remove it again. These changes might appear to be trivial but are well suited for Generalized Adaptive A*, an extension of A*. Our experimental results indeed show that they speed up Generalized Adaptive A* by up to 30 percent if its priority queue is implemented as a binary heap.

AAMAS Conference 2008 Conference Paper

BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm

• William Yeoh
• Ariel Felner
• Sven Koenig

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. It is often desirable to solve DCOP problems optimally with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB- ADOPT), a memory-bounded asynchronous DCOP algorithm that uses the message passing and communication framework of ADOPT, a well known memory-bounded asynchronous DCOP algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-andbound search. Our experimental results show that BnB- ADOPT is up to one order of magnitude faster than ADOPT on a variety of large DCOP problems and faster than NCBB, a memory-bounded synchronous DCOP algorithm, on most of these DCOP problems.

AAMAS Conference 2008 Conference Paper

Generalized Adaptive A*

• Xiaoxun Sun
• Sven Koenig
• William Yeoh

Agents often have to solve series of similar search problems. Adaptive A* is a recent incremental heuristic search algorithm that solves series of similar search problems faster than A* because it updates the h-values using information from previous searches. It basically transforms consistent hvalues into more informed consistent h-values. This allows it to find shortest paths in state spaces where the action costs can increase over time since consistent h-values remain consistent after action cost increases. However, it is not guaranteed to find shortest paths in state spaces where the action costs can decrease over time because consistent h-values do not necessarily remain consistent after action cost decreases. Thus, the h-values need to get corrected after action cost decreases. In this paper, we show how to do that, resulting in Generalized Adaptive A* (GAA*) that finds shortest paths in state spaces where the action costs can increase or decrease over time. Our experiments demonstrate that Generalized Adaptive A* outperforms breadth-first search, A* and D* Lite for moving-target search, where D* Lite is an alternative state-of-the-art incremental heuristic search algorithm that finds shortest paths in state spaces where the action costs can increase or decrease over time.

AAMAS Conference 2008 Conference Paper

Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms

• William Yeoh
• Sven Koenig
• Xiaoxun Sun

Distributed Constraint Optimization (DCOP) is a key technique for solving multiagent coordination problems. Unfortunately, finding minimal-cost DCOP solutions is NP-hard. We therefore propose two mechanisms that trade off the solution costs of two DCOP search algorithms (ADOPT and BnB-ADOPT) for smaller runtimes, namely the Inadmissible Heuristics Mechanism and the Relative Error Mechanism. The solution costs that result from these mechanisms are bounded by a more meaningful quantity than the solution costs that result from the existing Absolute Error Mechanism since they both result in solution costs that are larger than minimal by at most a user-specified percentage. Furthermore, the Inadmissible Heuristics Mechanism experimentally dominates both the Absolute Error Mechanism and the Relative Error Mechanism for BnB-ADOPT and is generally no worse than them for ADOPT.