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 its relation to traditional tie-breaking policies and provide theoretical findings. Finally, we study and empirically compare different ordering functions..
@inproceedings{conf/ijcai/SkylerSAFSC0K0U24,author={Skyler, Shawn and Shperberg, Shahaf and Atzmon, Dor and Felner, Ariel and Salzman, Oren and Chan, Shao-Hung and Zhang, Han and Koenig, Sven and Yeoh, William and Ulloa, Carlos Hernandez},title={Theoretical Study on Multi-objective Heuristic Search},booktitle={International Joint Conference on Artificial Intelligence},pages={to appear},year={2024},}
CP
Ex-Ante Constraint Elicitation in Incomplete DCOPs
Roie Zivan, Shiraz Regev, and William Yeoh
In International Conference on Principles and Practice of Constraint Programming, 2024
Distributed Constraint Optimization Problems (DCOPs) is a framework for representing and solving distributed combinatorial problems, where agents exchange messages to assign variables they own, such that the sum of constraint costs is minimized. When agents represent people (e.g., in meeting scheduling problems), the constraint information that the agents hold may be incomplete. For such scenarios, researchers proposed Incomplete DCOPs (I-DCOPs), which allow agents to elicit from their human users some of the missing information. Existing I-DCOP approaches evaluate solutions not only by their quality, but also the elicitation costs spent to find them (ex-post). Unfortunately, this may result in the agents spending a lot of effort (in terms of elicitation costs) to find high-quality solutions, and then ignoring them because previous lower-quality solutions were found with less effort.
Therefore, we propose a different approach for solving I-DCOPs by evaluating solutions based on their quality and considering the elicitation cost beforehand (ex-ante). Agents are limited in the amount of information that they can elicit and, therefore, need to make smart decisions on choosing which missing information to elicit. We propose several heuristics for making these decisions. Our results indicate that some of the heuristics designed produce high-quality solutions, which significantly outperform the previously proposed ex-post heuristics.
@inproceedings{conf/cp/ZivanR024,author={Zivan, Roie and Regev, Shiraz and Yeoh, William},title={Ex-Ante Constraint Elicitation in Incomplete {DCOP}s},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={to appear},year={2024},}
CP
Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization
Ben Rachmut, Roie Zivan, and William Yeoh
In International Conference on Principles and Practice of Constraint Programming, 2024
Researchers recently extended Distributed Constraint Optimization Problems (DCOPs) to Communication-Aware DCOPs so that they are applicable in scenarios in which messages can be arbitrarily delayed. Distributed asynchronous local search and inference algorithms designed for CA-DCOPs are less vulnerable to message latency than their counterparts for regular DCOPs. However, unlike local search algorithms for (regular) DCOPs that converge to k-opt solutions (with k > 1), that is, they converge to solutions that cannot be improved by a group of k agents), local search CA-DCOP algorithms are limited to 1-opt solutions only.
In this paper, we introduce Latency-Aware Monotonic Distributed Local Search-2 (LAMDLS-2), where agents form pairs and coordinate bilateral assignment replacements. LAMDLS-2 is monotonic, converges to a 2-opt solution, and is also robust to message latency, making it suitable for CA-DCOPs. Our results indicate that LAMDLS-2 converges faster than MGM-2, a benchmark algorithm, to a similar 2-opt solution, in various message latency scenarios.
@inproceedings{conf/cp/RachmutZ024,author={Rachmut, Ben and Zivan, Roie and Yeoh, William},title={Latency-Aware 2-Opt Monotonic Local Search for Distributed Constraint Optimization},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={to appear},year={2024},}
AAMAS
Algorithmic Filtering, Out-Group Stereotype, and Polarization on Social Media
Jean Springsteen, William Yeoh, and Dino Christenson
In International Conference on Autonomous Agents and Multiagent Systems, 2024
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.
@inproceedings{conf/aamas/Springsteen0C24,author={Springsteen, Jean and Yeoh, William and Christenson, Dino},title={Algorithmic Filtering, Out-Group Stereotype, and Polarization on Social Media},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={to appear},year={2024},}
2023
JAAMAS
Effect of Asynchronous Execution and Imperfect Communication on Max-Sum Belief Propagation
Roie Zivan, Ben Rachmut, Omer Perry, and
1 more author
Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems (DCOPs). 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.
@article{journals/aamas/ZivanRPY23,author={Zivan, Roie and Rachmut, Ben and Perry, Omer and Yeoh, William},title={Effect of Asynchronous Execution and Imperfect Communication on Max-Sum Belief Propagation},journal={Autonomous Agents and Multi-Agent Systems},volume={37},number={2},pages={40},year={2023},}
AIJ
Simple and Efficient Bi-Objective Search Algorithms via Fast Dominance Checks
Carlos Hernández, William Yeoh, Jorge A. Baier, and
4 more authors
Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Instead of looking for a single optimal path, we compute a Pareto-optimal frontier in bi-objective search, which is a set of paths in which no two paths dominate each other. Bi-objective search algorithms perform dominance checks each time a new path is discovered. Thus, the efficiency of these checks is key to performance. In this article, we propose algorithms for two kinds of bi-objective search problems. First, we consider the problem of computing the Pareto-optimal frontier of the paths that connect a given start state with a given goal state. We propose Bi-Objective A* (BOA*), a heuristic search algorithm based on A*, for this problem. Second, we consider the problem of computing one Pareto-optimal frontier for each state s of the search graph, which contains the paths that connect a given start state with s. We propose Bi-Objective Dijkstra (BOD), which is based on BOA*, for this problem. A common feature of BOA* and BOD is that all dominance checks are performed in constant time, unlike the dominance checks of previous algorithms. We show in our experimental evaluation that both BOA* and BOD are substantially faster than state-of-the-art bi-objective search algorithms.
@article{journals/ai/HernandezYBZSKS23,author={Hern{\'{a}}ndez, Carlos and Yeoh, William and Baier, Jorge A. and Zhang, Han and Suazo, Luis and Koenig, Sven and Salzman, Oren},title={Simple and Efficient Bi-Objective Search Algorithms via Fast Dominance Checks},journal={Artificial Intelligence},volume={314},pages={103807},year={2023},}
EAAI
A Particle Swarm Inspired Approach for Continuous Distributed Constraint Optimization Problems
Moumita Choudhury, Amit Sarker, Samin Yaser, and
3 more authors
Distributed Constraint Optimization Problems (DCOPs) are a widely studied framework for coordinating interactions in cooperative multi-agent systems. In classical DCOPs, variables owned by agents are assumed to be discrete. However, in many applications, such as target tracking or sleep scheduling in sensor networks, continuous-valued variables are more suitable than discrete ones. To better model such applications, researchers have proposed Continuous DCOPs (C-DCOPs), an extension of DCOPs, that can explicitly model problems with continuous variables. The state-of-the-art approaches for solving C-DCOPs experience either onerous memory or computation overhead and are unsuitable for non-differentiable optimization problems. To address this issue, we propose a new C-DCOP algorithm, namely Particle Swarm Optimization Based C-DCOP (PCD), which is inspired by Particle Swarm Optimization (PSO), a well-known centralized population-based approach for solving continuous optimization problems. In recent years, population-based algorithms have gained significant attention in classical DCOPs due to their ability in producing high-quality solutions. Nonetheless, to the best of our knowledge, this class of algorithms has not been utilized to solve C-DCOPs and there has been no work evaluating the potential of PSO in solving classical DCOPs or C-DCOPs. In light of this observation, we adapted PSO, a centralized algorithm, to solve C-DCOPs in a decentralized manner. The resulting PCD algorithm not only produces good-quality solutions but also finds solution without any requirement for derivative calculations. Moreover, we design a crossover operator that can be used by PCD to further improve the quality of solutions found. Finally, we theoretically prove that PCD is an anytime algorithm and empirically evaluate PCD against the state-of-the-art C-DCOP algorithms in a wide variety of benchmarks.
@article{journals/eaai/ChoudhurySYK0K23,author={Choudhury, Moumita and Sarker, Amit and Yaser, Samin and Khan, Md. Maruf Al Alif and Yeoh, William and Khan, Md. Mosaddek},title={A Particle Swarm Inspired Approach for Continuous Distributed Constraint Optimization Problems},journal={Engineering Applied Artificial Intelligence},volume={123},number={Part {B}},pages={106280},year={2023},}
ECAI
A Logic-Based Framework for Explainable Agent Scheduling Problems
Stylianos Loukas Vasileiou, Borong Xu, and William Yeoh
In European Conference on Artificial Intelligence, 2023
Agent Scheduling Problems (ASPs) are common in various real-world situations, requiring explainable decision-making processes to effectively allocate resources to multiple agents while fostering understanding and trust. To address this need, this paper presents a logic-based framework for providing explainable decisions in ASPs. Specifically, the framework addresses two types of queries: reason-seeking queries, which explain the reasoning behind scheduling decisions, and modification-seeking queries, which offer guidance on making infeasible decisions feasible. Acknowledging the importance of privacy in multi-agent scheduling, we introduce a privacy-loss function that measures the disclosure of private information in explanations, enabling a privacy-preserving aspect in our framework. By using this function, we introduce the notion of privacy-aware explanations and present an algorithm for computing them. Empirical evaluations demonstrate the effectiveness and versatility of our approach.
@inproceedings{conf/ecai/VasileiouX023,author={Vasileiou, Stylianos Loukas and Xu, Borong and Yeoh, William},title={A Logic-Based Framework for Explainable Agent Scheduling Problems},booktitle={European Conference on Artificial Intelligence},pages={2402--2410},year={2023},}
ECAI
PLEASE: Generating Personalized Explanations in Human-Aware Planning
Stylianos Loukas Vasileiou, and William Yeoh
In European Conference on Artificial Intelligence, 2023
Model Reconciliation Problems (MRPs) and their variant, Logic-based MRPs (L-MRPs), have emerged as popular methods for explainable planning problems. Both MRP and L-MRP approaches assume that the explaining agent has access to an assumed model of the human user receiving the explanation, and it reconciles its own model with the human model to find the differences such that when they are provided as explanations to the human, they will understand them. However, in practical applications, the agent is likely to be fairly uncertain on the actual model of the human and wrong assumptions can lead to incoherent or unintelligible explanations. In this paper, we propose a less stringent requirement: The agent has access to a task-specific vocabulary known by the human and, if available, a human model capturing confidently-known information. Our goal is to find a personalized explanation, which is an explanation that is at an appropriate abstraction level with respect to the human’s vocabulary and model. Using a logic-based method called knowledge forgetting for generating abstractions, we propose a simple framework compatible with L-MRP approaches, and evaluate its efficacy through computational and human user experiments.
@inproceedings{conf/ecai/Vasileiou023,author={Vasileiou, Stylianos Loukas and Yeoh, William},title={{PLEASE:} Generating Personalized Explanations in Human-Aware Planning},booktitle={European Conference on Artificial Intelligence},pages={2411--2418},year={2023},}
ICAPS
Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems
Ashwin Kumar, Yevgeniy Vorobeychik, and William Yeoh
In International Conference on Automated Planning and Scheduling, 2023
State-of-the-art order dispatching algorithms for ridesharing batch passenger requests and allocate them to a fleet of vehicles in a centralized manner, optimizing over the estimated values of each passenger-vehicle matching using integer linear programming (ILP). Using good estimates of future values, such ILP-based approaches are able to significantly increase the service rates (percentage of requests served) for a fixed fleet of vehicles. However, such approaches that focus solely on maximizing efficiency can lead to disparities for both drivers (e.g., income inequality) and passengers (e.g., inequality of service for different groups). Existing approaches that consider fairness only do it for naive assignment policies, require extensive training, or look at only single-sided fairness. We propose a simple incentive-based fairness scheme that can be implemented online as a part of this ILP formulation that allows us to improve fairness over a variety of fairness metrics. Deriving from a lens of variance minimization, we describe how these fairness incentives can be formulated for two distinct use cases for passenger groups and driver fairness. We show that under mild conditions, our approach can guarantee an improvement in the chosen metric for the worst-off individual. We also show empirically that our Simple Incentives approach significantly outperforms prior art, despite requiring no retraining; indeed, it often leads to a large improvement over the state-of-the-art fairness-aware approach in both overall service rate and fairness.
@inproceedings{conf/icaps/KumarV023,author={Kumar, Ashwin and Vorobeychik, Yevgeniy and Yeoh, William},title={Using Simple Incentives to Improve Two-Sided Fairness in Ridesharing Systems},booktitle={International Conference on Automated Planning and Scheduling},year={2023},}
DAI
Multi-Agent Planning and Diagnosis with Commonsense Reasoning
Tran Cao Son, William Yeoh, Roni Stern, and
1 more author
In International Conference on Distributed Artificial Intelligence, 2023
In multi-agent systems, multi-agent planning and diagnosis are two key subfields – multi-agent planning approaches identify plans for the agents to execute in order to reach their goals, and multi-agent diagnosis approaches identify root causes for faults when they occur, typically by using information from the multi-agent planning model as well as the resulting multi-agent plan. However, when a plan fails during execution, the cause can often be related to some commonsense information that is neither explicitly encoded in the planning nor diagnosis problems. As such existing diagnosis approaches fail to accurately identify the root causes in such situations.
To remedy this limitation, we extend the Multi-Agent STRIPS problem (a common multi-agent planning framework) to a Commonsense Multi-Agent STRIPS model, which includes commonsense fluents and axioms that may affect the classical planning problem. We show that a solution to a (classical) Multi-Agent STRIPS problem is also a solution to the commonsense variant of the same problem. Then, we propose a decentralized multi-agent diagnosis algorithm, which uses the commonsense information to diagnose faults when they occur during execution. Finally, we demonstrate the feasibility and promise of this approach on several key multi-agent planning benchmarks.
@inproceedings{conf/dai2/Son0SK23,author={Son, Tran Cao and Yeoh, William and Stern, Roni and Kalech, Meir},title={Multi-Agent Planning and Diagnosis with Commonsense Reasoning},booktitle={International Conference on Distributed Artificial Intelligence},pages={5:1--5:9},year={2023},}
2022
JAIR
Communication-Aware Local Search for Distributed Constraint Optimization
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.
@article{journals/jair/RachmutZ022,author={Rachmut, Ben and Zivan, Roie and Yeoh, William},title={Communication-Aware Local Search for Distributed Constraint Optimization},journal={Journal of Artificial Intelligence Research},volume={75},pages={637--675},year={2022},}
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.
@article{journals/jair/HoangFHYYZ22,author={Hoang, Khoi D. and Fioretto, Ferdinando and Hou, Ping and Yeoh, William and Yokoo, Makoto and Zivan, Roie},title={Proactive Dynamic Distributed Constraint Optimization Problems},journal={Journal of Artificial Intelligence Research},volume={74},pages={179--225},year={2022},}
JAIR
A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems
Stylianos Loukas Vasileiou, William Yeoh, Tran Cao Son, and
3 more authors
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 logicbased framework for explanation generation, where given a knowledge base KBa (of an agent) and a knowledge base KBh (of a human user), each encoding their knowledge of a planning problem, and that KBa entails a query q (e.g., that a proposed plan of the agent is valid), the goal is to identify an explanation ⊆KBa such that when it is used to update KBh, then the updated KBh 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.
@article{journals/jair/VasileiouYSKCM22,author={Vasileiou, Stylianos Loukas and Yeoh, William and Son, Tran Cao and Kumar, Ashwin and Cashmore, Michael and Magazzeni, Daniele},title={A Logic-Based Explanation Generation Framework for Classical and Hybrid Planning Problems},journal={Journal of Artificial Intelligence Research},volume={73},pages={1473--1534},year={2022},}
ICAPS
VizXP: A Visualization Framework for Conveying Explanations to Users in Model Reconciliation Problems
Ashwin Kumar, Stylianos Loukas Vasileiou, Melanie Bancilhon, and
2 more authors
In International Conference on Automated Planning and Scheduling, 2022
Advancements in explanation generation for automated planning algorithms have moved us a step closer towards realizing the full potential of human-AI collaboration in real-world planning applications. Within this context, a framework called model reconciliation has gained a lot of traction, mostly due to its deep connection with a popular theory in human psychology, known as the theory of mind. Existing literature in this setting, however, has mostly been constrained to algorithmic contributions for generating explanations. To the best of our knowledge, there has been very little work on how to effectively convey such explanations to human users, a critical component in human-AI collaboration systems. In this paper, we set out to explore to what extent visualizations are an effective candidate for conveying explanations in a way that can be easily understood. Particularly, by drawing inspiration from work done in visualization systems for classical planning, we propose a visualization framework for visualizing explanations generated from model reconciliation algorithms. We demonstrate the efficacy of our proposed system in a comprehensive user study, where we compare our framework against a text-based baseline for two types of explanations – domain-based and problem-based explanations. Results from the user study show that users, on average, understood explanations better when they are conveyed via our visualization system compared to when they are conveyed via a text-based baseline.
@inproceedings{conf/icaps/KumarVBO022,author={Kumar, Ashwin and Vasileiou, Stylianos Loukas and Bancilhon, Melanie and Ottley, Alvitta and Yeoh, William},title={VizXP: {A} Visualization Framework for Conveying Explanations to Users in Model Reconciliation Problems},booktitle={International Conference on Automated Planning and Scheduling},pages={701--709},year={2022},}
AAAI
Stochastic Goal Recognition Design Problems with Suboptimal Agents
Christabel Wayllace, and William Yeoh
In AAAI Conference on Artificial Intelligence, 2022
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.
@inproceedings{conf/aaai/Wayllace022,author={Wayllace, Christabel and Yeoh, William},title={Stochastic Goal Recognition Design Problems with Suboptimal Agents},booktitle={{AAAI} Conference on Artificial Intelligence},pages={9953--9961},year={2022},}
CCS
When Evil Calls: Targeted Adversarial Voice over IP Network
Han Liu, Zhiyuan Yu, Mingming Zha, and
4 more authors
In ACM Conference on Computer and Communications Security, 2022
As the COVID-19 pandemic fundamentally reshaped the remote life and working styles, Voice over IP (VoIP) telephony and video conferencing have become a primary method of connecting communities together. However, little has been done to understand the feasibility and limitations of delivering adversarial voice samples via such communication channels.
In this paper, we propose TAINT - Targeted Adversarial Voice over IP Network, the first targeted, query-efficient, hard label blackbox, adversarial attack on commercial speech recognition platforms over VoIP. The unique channel characteristics of VoIP pose significant new challenges, such as signal degradation, random channel noise, frequency selectivity, etc. To address these challenges, we systematically analyze the structure and channel characteristics of VoIP through reverse engineering. A noise-resilient efficient gradient estimation method is then developed to ensure a steady and fast convergence of the adversarial sample generation process.
We demonstrate our attack in both over-the-air and over-the-line settings on four commercial automatic speech recognition (ASR) systems over the five most popular VoIP Conferencing Software (VCS). We show that TAINT can achieve performance that is comparable to the existing methods even with the addition of VoIP channel. Even in the most challenging scenario where there is an active speaker in Zoom, TAINT can still succeed within 10 attempts while staying out of the speaker focus of the video conference
@inproceedings{conf/ccs/LiuYZ00VZ22,author={Liu, Han and Yu, Zhiyuan and Zha, Mingming and Wang, XiaoFeng and Yeoh, William and Vorobeychik, Yevgeniy and Zhang, Ning},title={When Evil Calls: Targeted Adversarial Voice over {IP} Network},booktitle={{ACM} Conference on Computer and Communications Security},pages={2009--2023},year={2022},}
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model multi-agent coordination problems that are distributed by nature. While DCOPs assume that variables are discrete and the environment does not change over time, agents often interact in a more dynamic and complex environment. To address these limiting assumptions, researchers have proposed Dynamic DCOPs (DDCOPs) to model how DCOPs dynamically change over time and Continuous DCOPs (C-DCOPs) to model DCOPs with continuous variables and constraints in functional form. However, these models address each limiting assumption of DCOPs in isolation, and it remains a challenge to model problems that both have continuous variables and are in dynamic environment. Therefore, in this paper, we propose Dynamic Continuous DCOPs (DC-DCOPs), a novel formulation that models both dynamic nature of the environment and continuous nature of the variables, which are inherent in many multi-agent problems. In addition, we introduce several greedy algorithms to solve DC-DCOPs and discuss their theoretical properties. Finally, we empirically evaluate the algorithms in random networks and in distributed sensor network application.
@inproceedings{conf/prima/HoangY22,author={Hoang, Khoi D. and Yeoh, William},title={Dynamic Continuous Distributed Constraint Optimization Problems},booktitle={International Conference on Principles and Practice of Multi-Agent Systems},pages={475--491},year={2022},}
2021
CP
The Effect of Asynchronous Execution and Message Latency on Max-Sum
Roie Zivan, Omer Perry, Ben Rachmut, and
1 more author
In International Conference on Principles and Practice of Constraint Programming, 2021
Max-sum is a version of belief propagation that was adapted for solving distributed constraint optimization problems (DCOPs). 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 a synchronous and an asynchronous algorithm, however, neither the differences in the performance of these two execution versions nor the implications of message latency 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 latency; 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 the drastic effect that message latency has on distributed local search, damped Max-sum is robust to message latency.
@inproceedings{conf/cp/ZivanPRY21,author={Zivan, Roie and Perry, Omer and Rachmut, Ben and Yeoh, William},title={The Effect of Asynchronous Execution and Message Latency on Max-Sum},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={60:1--60:18},year={2021},}
AAMAS
Latency-Aware Local Search for Distributed Constraint Optimization
Ben Rachmut, Roie Zivan, and William Yeoh
In International Conference on Autonomous Agents and Multiagent Systems, 2021
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.
@inproceedings{conf/aamas/RachmutZ021,author={Rachmut, Ben and Zivan, Roie and Yeoh, William},title={Latency-Aware Local Search for Distributed Constraint Optimization},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={1019--1027},year={2021},}
AAAI
On Exploiting Hitting Sets for Model Reconciliation
Stylianos Loukas Vasileiou, Alessandro Previti, and William Yeoh
In AAAI Conference on Artificial Intelligence, 2021
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 logic-based 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 state-of-the-art solver, and generic non-planning instances from recent SAT competitions, for which no other solver exists.
@inproceedings{conf/aaai/VasileiouP021,author={Vasileiou, Stylianos Loukas and Previti, Alessandro and Yeoh, William},title={On Exploiting Hitting Sets for Model Reconciliation},booktitle={{AAAI} Conference on Artificial Intelligence},pages={6514--6521},year={2021},}
JELIA
Model Reconciliation in Logic Programs
Tran Cao Son, Van Nguyen, Stylianos Loukas Vasileiou, and
1 more author
In European Conference on Logics in Artificial Intelligence, 2021
Inspired by recent research ε^+ in explainable planning, we investigate the model reconciliation problem between two logic programs \pi_a and \pi_h, which represent the knowledge bases of an agent and a human, respectively. Given \pi_a, \pi_h, and a query q such that \pi_a entails q and \pi_h does not entail q (or \pi_a does not entail q and \pi_h entails q), the model reconciliation problem focuses on the question of how to modify \pi_h, by adding + ⊆\pi_a to \pi_h and removing ε^- ⊆\pi_h from \pi_h such that the resulting program \hat\pi_h = (\pi_h ε^-) ∪ε^+ has an answer set containing q (or has no answer set containing q). The pair (ε^+, ε^-) is referred to as a solution for the model reconciliation problem (\pi_a, \pi_h, q) (or (\pi_a, \pi_h, \lnot q)). We prove that, for a reasonable selected set of rules ε^+ ⊆\pi_a there exists a way to modify \pi_h such that \hat\pi_h is guaranteed to credulously entail q (or skeptically entail \lnot q). Given that there are potentially several solutions, we discuss different characterizations of solutions and algorithms for computing solutions for model reconciliation problems.
@inproceedings{conf/jelia/SonNV021,author={Son, Tran Cao and Nguyen, Van and Vasileiou, Stylianos Loukas and Yeoh, William},title={Model Reconciliation in Logic Programs},booktitle={European Conference on Logics in Artificial Intelligence},pages={393--406},year={2021},}
DAI
Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics
Atena M. Tabakhi, William Yeoh, and Roie Zivan
In International Conference on Distributed Artificial Intelligence, 2021
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool to model cooperative multi-agent problems, especially when they are sparsely constrained with one another. A key assumption in this model is that all constraints are fully specified or known a priori, which may not hold in applications where constraints encode preferences of human users. In this paper, we extend the model to Incomplete DCOPs (I-DCOPs), where some constraints can be partially specified. User preferences for these partially-specified constraints can be elicited during the execution of I-DCOP algorithms, but they incur some elicitation costs. Additionally, we extend SyncBB, a complete DCOP algorithm, and ALS-MGM, an incomplete DCOP algorithm, to solve I-DCOPs. We also propose parameterized heuristics that those algorithms can utilize to trade off solution quality for faster runtime and fewer elicitation. They also provide theoretical quality guarantees when used by SyncBB when elicitations are free. Our model and heuristics thus extend the state-of-the-art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.
@inproceedings{conf/dai/TabakhiYZ21,author={Tabakhi, Atena M. and Yeoh, William and Zivan, Roie},title={Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics},booktitle={International Conference on Distributed Artificial Intelligence},pages={64--78},year={2021},}
2020
IROS
To Ask or Not to Ask: A User Annoyance Aware Preference Elicitation Framework for Social Robots
Balint Gucsi, Danesh S. Tarapore, William Yeoh, and
2 more authors
In International Conference on Intelligent Robots and Systems, 2020
In this paper we investigate how social robots can efficiently gather user preferences without exceeding the allowed user annoyance threshold. To do so, we use a Gazebo based simulated office environment with a TIAGo Steel robot. We then formulate the user annoyance aware preference elicitation problem as a combination of tensor completion and knapsack problems. We then test our approach on the aforementioned simulated environment and demonstrate that it can accurately estimate user preferences.
@inproceedings{conf/iros/GucsiT0AT20,author={Gucsi, Balint and Tarapore, Danesh S. and Yeoh, William and Amato, Christopher and Tran{-}Thanh, Long},title={To Ask or Not to Ask: {A} User Annoyance Aware Preference Elicitation Framework for Social Robots},booktitle={International Conference on Intelligent Robots and Systems},pages={7935--7940},year={2020},}
ICAPS
A Simple and Fast Bi-Objective Search Algorithm
Carlos Hernández Ulloa, William Yeoh, Jorge A. Baier, and
3 more authors
In International Conference on Automated Planning and Scheduling, 2020
Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Bi-objective search algorithms have to maintain the set of undominated paths from the start state to each state to compute the set of paths from the start state to the goal state that are not dominated by some other path from the start state to the goal state (called the Pareto-optimal solution set). Each time they find a new path to a state s, they perform a dominance check to determine whether this path dominates any of the previously found paths to s or whether any of the previously found paths to s dominates this path. Existing algorithms do not perform these checks efficiently. On the other hand, our Bi-Objective A* (BOA*) algorithm requires only constant time per check. In our experimental evaluation, we show that BOA* can run an order of magnitude (or more) faster than state-of-the-art bi-objective search algorithms, such as NAMOA*, NAMOA*dr, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.
@inproceedings{conf/icaps/Ulloa0BZSK20,author={Ulloa, Carlos Hern{\'{a}}ndez and Yeoh, William and Baier, Jorge A. and Zhang, Han and Suazo, Luis and Koenig, Sven},title={A Simple and Fast Bi-Objective Search Algorithm},booktitle={International Conference on Automated Planning and Scheduling},pages={143--151},year={2020},}
ICAPS
Online Traffic Signal Control through Sample-Based Constrained Optimization
Srishti Dhamija, Alolika Gon, Pradeep Varakantham, and
1 more author
In International Conference on Automated Planning and Scheduling, 2020
Traffic congestion reduces productivity of individuals by increasing time spent in traffic and also increases pollution. To reduce traffic congestion by better handling dynamic traffic patterns, recent work has focused on online traffic signal control. Typically, the objective in traffic signal control is to minimize expected delay over all vehicles given the uncertainty associated with the vehicle turn movements at intersections. In order to ensure responsiveness in decision making, a typical approach is to compute a schedule that minimizes the delay for the expected scenario of vehicle movements instead of minimizing expected delay over the feasible vehicle movement scenarios. Such an approximation degrades schedule quality with respect to expected delay as vehicle turn uncertainty at intersections increases.
We introduce TUSERACT (TUrn-SamplE-based Real-time trAffic signal ConTrol), an approach that minimizes expected delay over samples of turn movement uncertainty of vehicles. Specifically, our key contributions are: (a) By exploiting the insight that vehicle turn movements do not change with traffic signal control schedule, we provide a scalable constraint program formulation to compute a schedule that minimizes expected delay across multiple vehicle movement samples for a traffic signal; (b) a novel mechanism to coordinate multiple traffic signals through vehicle turn movement samples; and (c) a comprehensive experimental evaluation to demonstrate the utility of TUSERACT over SURTRAC, a leading approach for online traffic signal control which makes the aforementioned approximation. Our approach provides substantially lower (up to 60%) mean expected delay relative to SURTRAC with very few turn movement samples while providing real-time decision making on both real and synthetic networks.
@inproceedings{conf/icaps/DhamijaGV020,author={Dhamija, Srishti and Gon, Alolika and Varakantham, Pradeep and Yeoh, William},title={Online Traffic Signal Control through Sample-Based Constrained Optimization},booktitle={International Conference on Automated Planning and Scheduling},pages={366--374},year={2020},}
AAMAS
New Algorithms for Continuous Distributed Constraint Optimization Problems
Khoi D. Hoang, William Yeoh, Makoto Yokoo, and
1 more author
In International Conference on Autonomous Agents and Multiagent Systems, 2020
Distributed Constraint Optimization Problems (DCOPs) are a powerful tool to model multi-agent coordination problems that are distributed by nature. The formulation is suitable for problems where variables are discrete and constraint utilities are represented in tabular form. However, many real-world applications have variables that are continuous and tabular forms thus cannot accurately represent constraint utilities. To overcome this limitation, researchers have proposed the Continuous DCOP (C-DCOP) model, which are DCOPs with continuous variables. But existing approaches usually come with some restrictions on the form of constraint utilities and are without quality guarantees. Therefore, in this paper, we (i) propose an exact algorithm to solve a specific subclass of C-DCOPs; (ii) propose an approximation method with quality guarantees to solve general C-DCOPs; (iii) propose additional C-DCOP algorithms that are more scalable; and (iv) empirically show that our algorithms outperform existing state-of-the-art C-DCOP algorithms when given the same communication limitations.
@inproceedings{conf/aamas/Hoang0YR20,author={Hoang, Khoi D. and Yeoh, William and Yokoo, Makoto and Rabinovich, Zinovi},title={New Algorithms for Continuous Distributed Constraint Optimization Problems},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={502--510},year={2020},}
ECAI
Accounting for Observer’s Partial Observability in Stochastic Goal Recognition Design
Christabel Wayllace, Sarah Keren, Avigdor Gal, and
3 more authors
In European Conference on Artificial Intelligence, 2020
Motivated by security applications, where agent intentions are unknown, actions may have stochastic outcomes, and an observer may have an obfuscated view due to low sensor resolution, we introduce partially-observable states and unobservable actions into a stochastic goal recognition design framework. The proposed model is accompanied by a method for calculating the expected maximal number of steps before the goal of an agent is revealed and a new sensor refinement modification that can be applied to enhance goal recognition. A preliminary empirical evaluation on a range of benchmark applications shows the effectiveness of our approach.
@inproceedings{conf/ecai/WayllaceKGK0Z20,author={Wayllace, Christabel and Keren, Sarah and Gal, Avigdor and Karpas, Erez and Yeoh, William and Zilberstein, Shlomo},title={Accounting for Observer's Partial Observability in Stochastic Goal Recognition Design},booktitle={European Conference on Artificial Intelligence},pages={2394--2401},year={2020},}
PRIMA
The Smart Appliance Scheduling Problem: A Bayesian Optimization Approach
Atena M. Tabakhi, William Yeoh, and Ferdinando Fioretto
In International Conference on Principles and Practice of Multi-Agent Systems, 2020
Daily energy demand peaks induce high greenhouse gas emissions and are deleterious to the power grid operations. The autonomous and coordinated control of smart appliances in residential buildings represents an effective solution to reduce peak demands. This coordination problem is challenging as it involves, not only, scheduling devices to minimize energy peaks, but also to comply with user preferences. Prior work assumed these preferences to be fully specified and known a priori, which is, however, unrealistic. To remedy this limitation, this paper introduces a Bayesian optimization approach for smart appliance scheduling when the users’ satisfaction with a schedule must be elicited, and thus considered expensive to evaluate. The paper presents a set of ad-hoc energy-cost based acquisition functions to drive the Bayesian optimization problem to find schedules that maximize the user’s satisfaction. The experimental results demonstrate the effectiveness of the proposed energy-cost based acquisition functions which improve the algorithm’s performance up to 26%.
@inproceedings{conf/prima/Tabakhi0F20,author={Tabakhi, Atena M. and Yeoh, William and Fioretto, Ferdinando},title={The Smart Appliance Scheduling Problem: {A} Bayesian Optimization Approach},booktitle={International Conference on Principles and Practice of Multi-Agent Systems},pages={100--115},year={2020},}
2019
JAIR
Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm
Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, and
1 more author
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.
@article{journals/jair/NguyenYLZ19,author={Nguyen, Duc Thien and Yeoh, William and Lau, Hoong Chuin and Zivan, Roie},title={Distributed Gibbs: {A} Linear-Space Sampling-Based {DCOP} Algorithm},journal={Journal of Artificial Intelligence Research},volume={64},pages={705--748},year={2019},}
AAMAS
Parameterized Heuristics for Incomplete Weighted CSPs with Elicitation Costs
Atena M. Tabakhi, William Yeoh, and Makoto Yokoo
In International Conference on Autonomous Agents and Multiagent Systems, 2019
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.
@inproceedings{conf/aamas/Tabakhi0Y19,author={Tabakhi, Atena M. and Yeoh, William and Yokoo, Makoto},title={Parameterized Heuristics for Incomplete Weighted CSPs with Elicitation Costs},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={476--484},year={2019},}
PRIMA
New Distributed Constraint Reasoning Algorithms for Load Balancing in Edge Computing
Khoi D. Hoang, Christabel Wayllace, William Yeoh, and
5 more authors
In International Conference on Principles and Practice of Multi-Agent Systems, 2019
Edge computing is a paradigm for improving the performance of cloud computing systems by performing data processing at the edge of the network, closer to the users and sources of data. As data processing is traditionally done in large data centers, typically located far from their users, the edge computing paradigm will reduce the communication bottleneck between the user and the location of data processing, thereby improving overall performance. This becomes more important as the number of Internet-of-Things (IoT) devices and other mobile or embedded devices continues to increase. In this paper, we investigate the use of distributed constraint reasoning (DCR) techniques to model and solve the distributed load balancing problem in edge computing problems. Specifically, we (i) provide a mapping of the distributed load balancing problem in edge computing to a distributed constraint satisfaction and optimization problem; (ii) propose two DCR algorithms to solve such problems; and (iii) empirically evaluate our algorithms against a state-of-the-art DCR algorithm on random and scale-free networks.
@inproceedings{conf/prima/HoangW0BDMPS19,author={Hoang, Khoi D. and Wayllace, Christabel and Yeoh, William and Beal, Jacob and Dasgupta, Soura and Mo, Yuanqiu and Paulos, Aaron and Schewe, Jon},title={New Distributed Constraint Reasoning Algorithms for Load Balancing in Edge Computing},booktitle={International Conference on Principles and Practice of Multi-Agent Systems},pages={69--86},year={2019},}
PRIMA
A Scheduler for Smart Homes with Probabilistic User Preferences
Van Nguyen, William Yeoh, Tran Cao Son, and
2 more authors
In International Conference on Principles and Practice of Multi-Agent Systems, 2019
Scheduling appliances is a challenging and interesting problem aimed at reducing energy consumption at a residential level. Previous work on appliance scheduling for smart homes assumes that user preferences have no uncertainty. In this paper, we study two approaches to address this problem when user preferences are uncertain. More specifically, we assume that user preferences in turning on or off a device are represented by Normal distributions. The first approach uses sample average approximation, a mathematical model, in computing a schedule. The second one relies on the fact that a scheduling problem could be viewed as a constraint satisfaction problem and uses depth-first search to identify a solution. We also conduct an experimental evaluation of the two approaches to investigate the scalability of each approach in different problem variants. We conclude by discussing computational challenges of our approaches and some possible directions for future work.
@inproceedings{conf/prima/Nguyen0SKL19,author={Nguyen, Van and Yeoh, William and Son, Tran Cao and Kreinovich, Vladik and Le, Tiep},title={A Scheduler for Smart Homes with Probabilistic User Preferences},booktitle={International Conference on Principles and Practice of Multi-Agent Systems},pages={138--152},publisher={Springer},year={2019},}
DAI
A Distributed Solver for Multi-Agent Path Finding Problems
Poom Pianpak, Tran Cao Son, Phoebe O. Toups Dugas, and
1 more author
In International Conference on Distributed Artificial Intelligence, 2019
Multi-Agent Path Finding (MAPF) problems are traditionally solved in a centralized manner. There are works focusing on optimality, performance, or a tradeoff between them. However, there is not much work on solving them in a distributed manner, and even less through spatial distribution. In this paper, we introduce ros-dmapf, a distributed MAPF solver. It consists of multiple MAPF sub-solvers, which besides solving their assigned sub-problems, interact with each other to solve a given MAPF problem. In the current implementation, the sub-solvers are answer set planning systems for multiple agents, and are created based on spatial distribution of the problem. Interactions between components of ros-dmapf are facilitated by the Robot Operating System (ROS). The highlights of ros-dmapf are its scalability and a high degree of parallelism. We empirically evaluate ros-dmapf using the move-only domain of the asprilo system and results suggest that ros-dmapf scales up well. For instance, ros-dmapf gives a solution of length around 600 for a MAPF problem with 2000 robots in randomly generated 100x100 obstacle-free maps – a problem beyond the capability of a single subsolver – within 7 minutes on a consumer laptop. We also evaluate the system against some other MAPF solvers and results show that the system performs well. We also discuss possible improvements for future work.
@inproceedings{conf/dai/PianpakST019,author={Pianpak, Poom and Son, Tran Cao and Dugas, Phoebe O. Toups and Yeoh, William},title={A Distributed Solver for Multi-Agent Path Finding Problems},booktitle={International Conference on Distributed Artificial Intelligence},pages={2:1--2:7},publisher={{ACM}},year={2019},}
2018
JAIR
Distributed Constraint Optimization Problems and Applications: A Survey
Ferdinando Fioretto, Enrico Pontelli, and 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.
@article{journals/jair/FiorettoPY18,author={Fioretto, Ferdinando and Pontelli, Enrico and Yeoh, William},title={Distributed Constraint Optimization Problems and Applications: {A} Survey},journal={Journal of Artificial Intelligence Research},volume={61},pages={623--698},year={2018},}
AI Matt.
AI Buzzwords Explained: Distributed Constraint Optimization Problems
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 paper, 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.
@article{journals/tist/VarakanthamKLY18,author={Varakantham, Pradeep and Kumar, Akshat and Lau, Hoong Chuin and Yeoh, William},title={Risk-Sensitive Stochastic Orienteering Problems for Trip Optimization in Urban Environments},journal={{ACM} Transaction of Intelligent System Technologies},volume={9},number={3},pages={24:1--24:25},year={2018},}
Const.
Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs
Ferdinando Fioretto, Enrico Pontelli, William Yeoh, and
1 more author
Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including Weighted Constraint Programs (WCSPs), Distributed Constraint Optimization (DCOP), as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements.
This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts.
The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version.
@article{journals/constraints/FiorettoPYD18,author={Fioretto, Ferdinando and Pontelli, Enrico and Yeoh, William and Dechter, Rina},title={Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs},journal={Cons},volume={23},number={1},pages={1--43},year={2018},}
IJAIT
Communication-Sensitive Pseudo-Tree Heuristics for DCOP Algorithms
Atena M. Tabakhi, William Yeoh, Reza Tourani, and
2 more authors
International Journal on Artificial Intelligence Tools, 2018
Distributed Constraint Optimization Problem (DCOP) is a powerful paradigm to model multi-agent systems through enabling multiple agents to coordinate with each other to solve a problem. These agents are often assumed to be cooperative, that is, they communicate with other agents in order to optimize a global objective. However, the communication times between all pairs of agents are assumed to be identical in the evaluation of most DCOP algorithms. This assumption is impractical in almost all real-world applications. In this paper, we study the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary. In addition, we evaluate a DCOP algorithm using ns-2, a discrete-event simulator that is widely used in the computer networking community, to simulate the communication times, as opposed to the standard DCOP simulators that are used to evaluate DCOP algorithms in the AI community. Furthermore, we propose heuristics that exploit the non-uniform communication times to speed up DCOP algorithms that operate on pseudo-trees. Our empirical results demonstrate that the proposed heuristics improve the runtime of those algorithms up to 20%. These heuristics are evaluated on different benchmarks such as scale-free graphs, random graphs, and an instance of the smart grid, Customer-Driven Microgrid (CDMG) application.
@article{journals/ijait/VirvouBBTYTNM18a,author={Tabakhi, Atena M. and Yeoh, William and Tourani, Reza and Natividad, Francisco and Misra, Satyajayant},title={Communication-Sensitive Pseudo-Tree Heuristics for {DCOP} Algorithms},journal={International Journal on Artificial Intelligence Tools},volume={27},number={7},pages={1860008:1--1860008:24},year={2018},}
CP
A Large Neighboring Search Schema for Multi-agent Optimization
Khoi D. Hoang, Ferdinando Fioretto, William Yeoh, and
2 more authors
In International Conference on Principles and Practice of Constraint Programming, 2018
The Distributed Constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. Thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.
@inproceedings{conf/cp/HoangF0PZ18,author={Hoang, Khoi D. and Fioretto, Ferdinando and Yeoh, William and Pontelli, Enrico and Zivan, Roie},title={A Large Neighboring Search Schema for Multi-agent Optimization},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={688--706},publisher={Springer},year={2018},}
UAI
Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments
Pritee Agrawal, Pradeep Varakantham, and William Yeoh
In Conference on Uncertainty in Artificial Intelligence, 2018
Decentralized planning under uncertainty for agent teams is a problem of interest in many domains including (but not limited to) disaster rescue, sensor networks and security patrolling. Decentralized MDPs, Dec-MDPs have traditionally been used to represent such decentralized planning under uncertainty problems. However, in many domains, agents may not be dedicated to the team for the entire time horizon. For instance, due to limited availability of resources, it is quite common for police personnel leaving patrolling teams to attend to accidents. Such non-dedication can arise due to the emergence of higher priority tasks or damage to existing agents. However, there is very limited literature dealing with handling of non-dedication in decentralized settings. To that end, we provide a general model to represent problems dealing with cooperative and decentralized planning for non-dedicated agent teams. We also provide two greedy approaches (an offline one and an offline-online one) that are able to deal with agents leaving the team in an effective and efficient way by exploiting the submodularity property. Finally, we demonstrate that our approaches are able to obtain more than 90% of optimal solution quality on benchmark problems from the literature.
@inproceedings{conf/uai/AgrawalV018,author={Agrawal, Pritee and Varakantham, Pradeep and Yeoh, William},title={Decentralized Planning for Non-dedicated Agent Teams with Submodular Rewards in Uncertain Environments},booktitle={Conference on Uncertainty in Artificial Intelligence},pages={958--967},publisher={{AUAI} Press},year={2018},}
IJCAI
Bidding in Periodic Double Auctions Using Heuristics and Dynamic Monte Carlo Tree Search
Moinul Morshed Porag Chowdhury, Christopher Kiekintveld, Son Tran, and
1 more author
In International Joint Conference on Artificial Intelligence, 2018
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.
@inproceedings{conf/ijcai/ChowdhuryKT018,author={Chowdhury, Moinul Morshed Porag and Kiekintveld, Christopher and Tran, Son and Yeoh, William},title={Bidding in Periodic Double Auctions Using Heuristics and Dynamic Monte Carlo Tree Search},booktitle={International Joint Conference on Artificial Intelligence},pages={166--172},year={2018},}
AAMAS
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, and
1 more author
In International Conference on Autonomous Agents and Multiagent Systems, 2018
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.
@inproceedings{conf/aamas/KhanTYJ18,author={Khan, Md. Mosaddek and Tran{-}Thanh, Long and Yeoh, William and Jennings, Nicholas R.},title={A Near-Optimal Node-to-Agent Mapping Heuristic for GDL-Based {DCOP} Algorithms in Multi-Agent Systems},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={1604--1612},year={2018},}
AAMAS
Preference Elicitation with Interdependency and User Bother Cost
Tiep Le, Atena M. Tabakhi, Long Tran-Thanh, and
2 more authors
In International Conference on Autonomous Agents and Multiagent Systems, 2018
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 order 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.
@inproceedings{conf/aamas/LeTT0S18,author={Le, Tiep and Tabakhi, Atena M. and Tran{-}Thanh, Long and Yeoh, William and Son, Tran Cao},title={Preference Elicitation with Interdependency and User Bother Cost},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={1459--1467},year={2018},}
CIG
Multi-Agent Pathfinding with Real-Time Heuristic Search
Devon Sigurdson, Vadim Bulitko, William Yeoh, and
2 more authors
In IEEE Conference on Computational Intelligence and Games, 2018
Multi-agent pathfinding, namely finding collision-free paths for several agents from their given start locations to their given goal locations on a known stationary map, is an important task for non-player characters in video games. A variety of heuristic search algorithms have been developed for this task. Non-real-time algorithms, such as Flow Annotated Replanning (FAR), first find complete paths for all agents and then move the agents along these paths. However, their searches are often too expensive. Real-time algorithms have the ability to produce the next moves for all agents without finding complete paths for them and thus allow the agents to move in real time. Real-time heuristic search algorithms have so far typically been developed for single-agent pathfinding. We, on the other hand, present a real-time heuristic search algorithm for multiagent pathfinding, called Bounded Multi-Agent A* (BMAA*), that works as follows: Every agent runs an individual realtime heuristic search that updates heuristic values assigned to locations and treats the other agents as (moving) obstacles. Agents do not coordinate with each other, in particular, they neither share their paths nor heuristic values. We show how BMAA* can be enhanced by adding FAR-style flow annotations and allowing agents to push other agents temporarily off their goal locations, when necessary. In our experiments, BMAA* has higher completion rates and lower completion times than FAR.
@inproceedings{conf/cig/SigurdsonB0HK18,author={Sigurdson, Devon and Bulitko, Vadim and Yeoh, William and Hern{\'{a}}ndez, Carlos and Koenig, Sven},title={Multi-Agent Pathfinding with Real-Time Heuristic Search},booktitle={{IEEE} Conference on Computational Intelligence and Games},pages={1--8},year={2018},}
2017
TPLP
Solving Distributed Constraint Optimization Problems Using Logic Programming
Tiep Le, Tran Cao Son, Enrico Pontelli, and
1 more author
This paper explores the use of Answer Set Programming (ASP) in solving Distributed Constraint Optimization Problems (DCOPs). The paper provides the following novel contributions: (1) it shows how one can formulate DCOPs as logic programs; (2) it introduces ASP-DPOP, the first DCOP algorithm that is based on logic programming; (3) 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 (4) it demonstrates the applicability of ASP in a wide array of multi-agent problems currently modeled as DCOPs.
@article{journals/tplp/LeSPY17,author={Le, Tiep and Son, Tran Cao and Pontelli, Enrico and Yeoh, William},title={Solving Distributed Constraint Optimization Problems Using Logic Programming},journal={Theory and Practice of Logic Programming},volume={17},number={4},pages={634--683},year={2017},}
CP
Preference Elicitation for DCOPs
Atena M. Tabakhi, Tiep Le, Ferdinando Fioretto, and
1 more author
In International Conference on Principles and Practice of Constraint Programming, 2017
Distributed Constraint Optimization Problems (DCOPs) offer a powerful approach for the description and resolution of cooperative multi-agent problems. In this model, a group of agents coordinate their actions to optimize a global objective function, taking into account their preferences or constraints. A core limitation of this model is the assumption that the preferences of all agents or the costs of all constraints are specified a priori. Unfortunately, this assumption does not hold in a number of application domains where preferences or constraints must be elicited from the users. One of such domains is the Smart Home Device Scheduling (SHDS) problem. Motivated by this limitation, we make the following contributions in this paper: (1) We propose a general model for preference elicitation in DCOPs; (2) We propose several heuristics to elicit preferences in DCOPs; and (3) We empirically evaluate the effect of these heuristics on random binary DCOPs as well as SHDS problems.
@inproceedings{conf/cp/TabakhiLF017,author={Tabakhi, Atena M. and Le, Tiep and Fioretto, Ferdinando and Yeoh, William},title={Preference Elicitation for DCOPs},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={278--296},year={2017},}
IJCAI
New Metrics and Algorithms for Stochastic Goal Recognition Design Problems
Christabel Wayllace, Ping Hou, and William Yeoh
In International Joint Conference on Artificial Intelligence, 2017
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 likelihood of being the true goal; (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.
@inproceedings{conf/ijcai/WayllaceH017,author={Wayllace, Christabel and Hou, Ping and Yeoh, William},title={New Metrics and Algorithms for Stochastic Goal Recognition Design Problems},booktitle={International Joint Conference on Artificial Intelligence},pages={4455--4462},year={2017},}
IJCAI
Generalized Target Assignment and Path Finding Using Answer Set Programming
Van Nguyen, Philipp Obermeier, Tran Cao Son, and
2 more authors
In International Joint Conference on Artificial Intelligence, 2017
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. 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 methods can be efficient and can scale up to solve practical applications.
@inproceedings{conf/ijcai/NguyenOSS017,author={Nguyen, Van and Obermeier, Philipp and Son, Tran Cao and Schaub, Torsten and Yeoh, William},title={Generalized Target Assignment and Path Finding Using Answer Set Programming},booktitle={International Joint Conference on Artificial Intelligence},pages={1216--1223},year={2017},}
AAMAS
Infinite-Horizon Proactive Dynamic DCOPs
Khoi D. Hoang, Ping Hou, Ferdinando Fioretto, and
3 more authors
In International Conference on Autonomous Agents and Multiagent Systems, 2017
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.
@inproceedings{conf/aamas/HoangHF0ZY17,author={Hoang, Khoi D. and Hou, Ping and Fioretto, Ferdinando and Yeoh, William and Zivan, Roie and Yokoo, Makoto},title={Infinite-Horizon Proactive Dynamic DCOPs},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={212--220},year={2017},}
AAMAS
A Multiagent System Approach to Scheduling Devices in Smart Homes
Ferdinando Fioretto, William Yeoh, and Enrico Pontelli
In International Conference on Autonomous Agents and Multiagent Systems, 2017
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.
@inproceedings{conf/aamas/Fioretto0P17,author={Fioretto, Ferdinando and Yeoh, William and Pontelli, Enrico},title={A Multiagent System Approach to Scheduling Devices in Smart Homes},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={981--989},year={2017},}
AAMAS
A Distributed Constraint Optimization (DCOP) Approach to the Economic Dispatch with Demand Response
Ferdinando Fioretto, William Yeoh, Enrico Pontelli, and
2 more authors
In International Conference on Autonomous Agents and Multiagent Systems, 2017
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.
@inproceedings{conf/aamas/Fioretto0PMR17,author={Fioretto, Ferdinando and Yeoh, William and Pontelli, Enrico and Ma, Ye and Ranade, Satishkumar J.},title={A Distributed Constraint Optimization {(DCOP)} Approach to the Economic Dispatch with Demand Response},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={999--1007},year={2017},}
ICTAI
Pseudo-Tree Construction Heuristics for DCOPs and Evaluations on the ns-2 Network Simulator
Atena M. Tabakhi, Reza Tourani, Francisco Natividad, and
2 more authors
In IEEE International Conference on Tools with Artificial Intelligence, 2017
Distributed Constraint Optimization Problems (DCOPs) are commonly used to model multi-agent coordination problems. However, empirical evaluations of DCOP algorithms are typically done in simulation under the assumption that the communication times between all pairs of agents are identical, which is unrealistic in many real-world applications. In this paper, we investigate the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary and propose the use of ns-2, a de-facto simulator used by the computer networking community, to simulate the communication times. Additionally, we introduce heuristics that exploit the nonuniform communication times to speed up DCOP algorithms that operate on pseudo-trees.
@inproceedings{conf/ictai/TabakhiTN0M17,author={Tabakhi, Atena M. and Tourani, Reza and Natividad, Francisco and Yeoh, William and Misra, Satyajayant},title={Pseudo-Tree Construction Heuristics for DCOPs and Evaluations on the ns-2 Network Simulator},booktitle={{IEEE} International Conference on Tools with Artificial Intelligence},pages={1105--1112},year={2017},}
GameSec
Game-Theoretic Goal Recognition Models with Applications to Security Domains
Samuel Ang, Hau Chan, Albert Xin Jiang, and
1 more author
In International Conference on Decision and Game Theory for Security, 2017
Motivated by the goal recognition (GR) and goal recognition design (GRD) problems in the artificial intelligence (AI) planning domain, we introduce and study two natural variants of the GR and GRD problems with strategic agents, respectively. More specifically, we consider game-theoretic (GT) scenarios where a malicious adversary aims to damage some target in an (physical or virtual) environment monitored by a defender. The adversary must take a sequence of actions in order to attack the intended target. In the GTGR and GTGRD settings, the defender attempts to identify the adversary’s intended target while observing the adversary’s available actions so that he/she can strengthens the target’s defense against the attack. In addition, in the GTGRD setting, the defender can alter the environment (e.g., adding roadblocks) in order to better distinguish the goal/target of the adversary.
We propose to model GTGR and GTGRD settings as zero-sum stochastic games with incomplete information about the adversary’s intended target. The games are played on graphs where vertices represents states and edges are adversary’s actions. For the GTGR setting, we show that if the defender is restricted to playing only stationary strategies, the problem of computing optimal strategies (for both defender and adversary) can be formulated and represented compactly as a linear program. For the GTGRD setting, where the defender can choose K edges to block at the start of the game, we formulate the problem of computing optimal strategies as a mixed integer program, and present a heuristic algorithm based on LP duality and greedy methods. Experiments show that our heuristic algorithm achieves good performance (i.e., close to defender’s optimal value) with better scalability compared to the mixed-integer programming approach.
In contrast with our research, existing work, especially on GRD problems, has focused almost exclusively on decision-theoretic paradigms, where the adversary chooses its actions without taking into account the fact that they may be observed by the defender. As such an assumption is unrealistic in GT scenarios, our proposed models and algorithms fill a significant gap in the literature.
@inproceedings{conf/gamesec/AngCJY17,author={Ang, Samuel and Chan, Hau and Jiang, Albert Xin and Yeoh, William},title={Game-Theoretic Goal Recognition Models with Applications to Security Domains},booktitle={International Conference on Decision and Game Theory for Security},pages={256--272},year={2017},}
2016
Int. Sys.
AI’s 10 to Watch
Haris Aziz, Elias Bareinboim, Yejin Choi, and
7 more authors
@article{journals/expert/AzizBCHKMSSXY16,author={Aziz, Haris and Bareinboim, Elias and Choi, Yejin and Hsu, Daniel J. and Kalyanakrishnan, Shivaram and Meir, Reshef and Saria, Suchi and Simari, Gerardo I. and Xia, Lirong and Yeoh, William},title={AI's 10 to Watch},journal={{IEEE} Intelligent Systems},volume={31},number={1},pages={56--66},year={2016},}
CP
A Dynamic Programming-Based MCMC Framework for Solving DCOPs with GPUs
Ferdinando Fioretto, William Yeoh, and Enrico Pontelli
In International Conference on Principles and Practice of Constraint Programming, 2016
The field of Distributed Constraint Optimization (DCOP) has gained momentum in recent years, thanks to its ability to address various applications related to multi-agent coordination. Nevertheless, solving DCOPs is computationally challenging. Thus, in large scale, complex applications, incomplete DCOP algorithms are necessary. Recently, researchers have introduced a promising class of incomplete DCOP algorithms, based on sampling. However, this paradigm requires a multitude of samples to ensure convergence. This paper exploits the property that sampling is amenable to parallelization, and introduces a general framework, called Distributed MCMC (DMCMC), that is based on a dynamic programming procedure and uses Markov Chain Monte Carlo (MCMC) sampling algorithms to solve DCOPs. Additionally, DMCMC harnesses the parallel computing power of Graphical Processing Units (GPUs) to speed-up the sampling process. The experimental results show that DMCMC can find good solutions up to two order of magnitude faster than other incomplete DCOP algorithms.
@inproceedings{conf/cp/Fioretto0P16,author={Fioretto, Ferdinando and Yeoh, William and Pontelli, Enrico},title={A Dynamic Programming-Based {MCMC} Framework for Solving {DCOP}s with {GPU}s},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={813--831},year={2016},}
IJCAI
Goal Recognition Design with Stochastic Agent Action Outcomes
Christabel Wayllace, Ping Hou, William Yeoh, and
1 more author
In International Joint Conference on Artificial Intelligence, 2016
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.
@inproceedings{conf/ijcai/WayllaceH0S16,author={Wayllace, Christabel and Hou, Ping and Yeoh, William and Son, Tran Cao},title={Goal Recognition Design with Stochastic Agent Action Outcomes},booktitle={International Joint Conference on Artificial Intelligence},pages={3279--3285},year={2016},}
IJCAI
Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning
Pritee Agrawal, Pradeep Varakantham, and William Yeoh
In International Joint Conference on Artificial Intelligence, 2016
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.
@inproceedings{conf/ijcai/AgrawalV016,author={Agrawal, Pritee and Varakantham, Pradeep and Yeoh, William},title={Scalable Greedy Algorithms for Task/Resource Constrained Multi-Agent Stochastic Planning},booktitle={International Joint Conference on Artificial Intelligence},pages={10--16},year={2016},}
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 PDDCOPs proactively.
@inproceedings{conf/aamas/HoangFHY0Z16,author={Hoang, Khoi D. and Fioretto, Ferdinando and Hou, Ping and Yokoo, Makoto and Yeoh, William and Zivan, Roie},title={Proactive Dynamic Distributed Constraint Optimization},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={597--605},year={2016},}
AAMAS
ER-DCOPs: A Framework for Distributed Constraint Optimization with Uncertainty in Constraint Utilities
Tiep Le, Ferdinando Fioretto, William Yeoh, and
2 more authors
In International Conference on Autonomous Agents and Multiagent Systems, 2016
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.
@inproceedings{conf/aamas/LeF0SP16,author={Le, Tiep and Fioretto, Ferdinando and Yeoh, William and Son, Tran Cao and Pontelli, Enrico},title={ER-DCOPs: {A} Framework for Distributed Constraint Optimization with Uncertainty in Constraint Utilities},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={606--614},year={2016},}
AAAI
Solving Risk-Sensitive POMDPs With and Without Cost Observations
Ping Hou, William Yeoh, and Pradeep Varakantham
In AAAI Conference on Artificial Intelligence, 2016
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.
@inproceedings{conf/aaai/Hou0V16,author={Hou, Ping and Yeoh, William and Varakantham, Pradeep},title={Solving Risk-Sensitive POMDPs With and Without Cost Observations},booktitle={{AAAI} Conference on Artificial Intelligence},pages={3138--3144},year={2016},}
AAAI
Multi-Variable Agents Decomposition for DCOPs
Ferdinando Fioretto, William Yeoh, and Enrico Pontelli
In AAAI Conference on Artificial Intelligence, 2016
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.
@inproceedings{conf/aaai/Fioretto0P16,author={Fioretto, Ferdinando and Yeoh, William and Pontelli, Enrico},title={Multi-Variable Agents Decomposition for {DCOP}s},booktitle={{AAAI} Conference on Artificial Intelligence},pages={2480--2486},year={2016},}
AAAI
Solving Goal Recognition Design Using ASP
Tran Cao Son, Orkunt Sabuncu, Christian Schulz-Hanke, and
2 more authors
In AAAI Conference on Artificial Intelligence, 2016
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.
@inproceedings{conf/aaai/SonSSSY16,author={Son, Tran Cao and Sabuncu, Orkunt and Schulz{-}Hanke, Christian and Schaub, Torsten and Yeoh, William},title={Solving Goal Recognition Design Using {ASP}},booktitle={{AAAI} Conference on Artificial Intelligence},pages={3181--3187},year={2016},}
2015
IAT
Incremental DCOP Search Algorithms for Solving Dynamic DCOP Problems
William Yeoh, Pradeep Varakantham, Xiaoxun Sun, and
1 more author
In International Conferences on Intelligent Agent Technology, 2015
Distributed constraint optimization (DCOP) problems are well-suited for modeling multi-agent coordination problems. However, it only models static problems, which do not change over time. Consequently, researchers have introduced the Dynamic DCOP (DDCOP) model to model dynamic problems. In this paper, we make two key contributions: (a) a procedure to reason with the incremental changes in DDCOP problems and (b) an incremental pseudo-tree construction algorithm that can be used by DCOP algorithms such as any-space ADOPT and any-space BnB-ADOPT to solve DDCOP problems. Due to the incremental reasoning employed, our experimental results show that any-space ADOPT and any-space BnB-ADOPT are up to 42% and 38% faster, respectively, with the incremental procedure and the incremental pseudo-tree reconstruction algorithm than without them.
@inproceedings{conf/iat/YeohVSK15,author={Yeoh, William and Varakantham, Pradeep and Sun, Xiaoxun and Koenig, Sven},title={Incremental {DCOP} Search Algorithms for Solving Dynamic {DCOP} Problems},booktitle={International Conferences on Intelligent Agent Technology},pages={257--264},year={2015},}
CP
Exploiting GPUs in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming
Ferdinando Fioretto, Tiep Le, Enrico Pontelli, and
2 more authors
In International Conference on Principles and Practice of Constraint Programming, 2015
This paper proposes the design and implementation of a dynamic programming based algorithm for (distributed) constraint optimization, which exploits modern massively parallel architectures, such as those found in modern Graphical Processing Units (GPUs). The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The experimental analysis, performed on unstructured and structured graphs, shows the advantages of employing GPUs, resulting in enhanced performances and scalability.
@inproceedings{conf/cp/FiorettoLP0S15,author={Fioretto, Ferdinando and Le, Tiep and Pontelli, Enrico and Yeoh, William and Son, Tran Cao},title={Exploiting {GPU}s in Solving (Distributed) Constraint Optimization Problems with Dynamic Programming},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={121--139},year={2015},}
AAAI
Solving Distributed Constraint Optimization Problems Using Logic Programming
Tiep Le, Tran Cao Son, Enrico Pontelli, and
1 more author
In AAAI Conference on Artificial Intelligence, 2015
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.
@inproceedings{conf/aaai/LeSP015,author={Le, Tiep and Son, Tran Cao and Pontelli, Enrico and Yeoh, William},title={Solving Distributed Constraint Optimization Problems Using Logic Programming},booktitle={{AAAI} Conference on Artificial Intelligence},pages={1174--1181},year={2015},}
2014
CP
Improving DPOP with Branch Consistency for Solving Distributed Constraint Optimization Problems
Ferdinando Fioretto, Tiep Le, William Yeoh, and
2 more authors
In International Conference on Principles and Practice of Constraint Programming, 2014
The DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based techniques have been recognized to be among the most effective techniques for building complete DCOP solvers (e.g., DPOP). Unfortunately, they also suffer from a widely recognized drawback: their messages are exponential in size. Another limitation is that most current DCOP algorithms do not actively exploit hard constraints, which are common in many real problems. This paper addresses these two limitations by introducing an algorithm, called BrC-DPOP, that exploits arc consistency and a form of consistency that applies to paths in pseudo-trees to reduce the size of the messages. Experimental results shows that BrC-DPOP uses messages that are up to one order of magnitude smaller than DPOP, and that it can scale up well, being able to solve problems that its counterpart can not.
@inproceedings{conf/cp/FiorettoLYPS14,author={Fioretto, Ferdinando and Le, Tiep and Yeoh, William and Pontelli, Enrico and Son, Tran Cao},title={Improving {DPOP} with Branch Consistency for Solving Distributed Constraint Optimization Problems},booktitle={International Conference on Principles and Practice of Constraint Programming},pages={307--323},year={2014},}
AAAI
Solving Uncertain MDPs by Reusing State Information and Plans
Ping Hou, William Yeoh, and Tran Cao Son
In AAAI Conference on Artificial Intelligence, 2014
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-the-shelf 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.
@inproceedings{conf/aaai/HouYS14,author={Hou, Ping and Yeoh, William and Son, Tran Cao},title={Solving Uncertain {MDP}s by Reusing State Information and Plans},booktitle={{AAAI} Conference on Artificial Intelligence},pages={2285--2292},year={2014},}
AAAI
Decentralized Multi-Agent Reinforcement Learning in Average-Reward Dynamic DCOPs
Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, and
2 more authors
In AAAI Conference on Artificial Intelligence, 2014
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.
@inproceedings{conf/aaai/Nguyen0LZZ14,author={Nguyen, Duc Thien and Yeoh, William and Lau, Hoong Chuin and Zilberstein, Shlomo and Zhang, Chongjie},title={Decentralized Multi-Agent Reinforcement Learning in Average-Reward Dynamic {DCOP}s},booktitle={{AAAI} Conference on Artificial Intelligence},pages={1447--1455},year={2014},}
AAAI
A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints
T. K. Satish Kumar, Duc Thien Nguyen, William Yeoh, and
1 more author
In AAAI Conference on Artificial Intelligence, 2014
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.
@inproceedings{conf/aaai/KumarN0K14,author={Kumar, T. K. Satish and Nguyen, Duc Thien and Yeoh, William and Koenig, Sven},title={A Simple Polynomial-Time Randomized Distributed Algorithm for Connected Row Convex Constraints},booktitle={{AAAI} Conference on Artificial Intelligence},pages={2308--2314},year={2014},}
ICAPS
Revisiting Risk-Sensitive MDPs: New Algorithms and Results
Ping Hou, William Yeoh, and Pradeep Varakantham
In International Conference on Automated Planning and Scheduling, 2014
While Markov Decision Processes (MDPs) have been shown to be effective models for planning under uncertainty, the objective to minimize the expected cumulative cost is inappropriate for high-stake planning problems. As such, Yu, Lin, and Yan (1998) introduced the Risk-Sensitive MDP (RSMDP) model, where the objective is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, we revisit this problem and introduce new algorithms that are based on classical techniques, such as depth-first search and dynamic programming, and a recently introduced technique called Topological Value Iteration (TVI). We demonstrate the applicability of our approach on randomly generated MDPs as well as domains from the ICAPS 2011 International Probabilistic Planning Competition (IPPC).
@inproceedings{conf/icaps/Hou0V14,author={Hou, Ping and Yeoh, William and Varakantham, Pradeep},title={Revisiting Risk-Sensitive {MDP}s: New Algorithms and Results},booktitle={International Conference on Automated Planning and Scheduling},year={2014},}
2013
ADT
Budgeted Personalized Incentive Approaches for Smoothing Congestion in Resource Networks
Pradeep Varakantham, Na Fu, William Yeoh, and
2 more authors
In International Conference on Algorithmic Decision Theory, 2013
Congestion occurs when there is competition for resources by selfish agents. In this paper, we are concerned with smoothing out congestion in a network of resources by using personalized well-timed incentives that are subject to budget constraints. To that end, we provide: (i) a mathematical formulation that computes equilibrium for the resource sharing congestion game with incentives and budget constraints; (ii) an integrated approach that scales to larger problems by exploiting the factored network structure and approximating the attained equilibrium; (iii) an iterative best response algorithm for solving the unconstrained version (no budget) of the resource sharing congestion game; and (iv) theoretical and empirical results (on an illustrative theme park problem) that demonstrate the usefulness of our approach.
@inproceedings{conf/adt/VarakanthamF0CL13,author={Varakantham, Pradeep and Fu, Na and Yeoh, William and Cheng, Shih{-}Fen and Lau, Hoong Chuin},title={Budgeted Personalized Incentive Approaches for Smoothing Congestion in Resource Networks},booktitle={International Conference on Algorithmic Decision Theory},pages={375--386},year={2013},}
IJCAI
Automated Generation of Interaction Graphs for Value-Factored Dec-POMDPs
William Yeoh, Akshat Kumar, and Shlomo Zilberstein
In International Joint Conference on Artificial Intelligence, 2013
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, NDPOMDPs 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.
@inproceedings{conf/ijcai/YeohKZ13,author={Yeoh, William and Kumar, Akshat and Zilberstein, Shlomo},title={Automated Generation of Interaction Graphs for Value-Factored Dec-{POMDP}s},booktitle={International Joint Conference on Artificial Intelligence},pages={411--417},year={2013},}
AAMAS
Distributed Gibbs: A Memory-Bounded Sampling-Based DCOP Algorithm
Duc Thien Nguyen, William Yeoh, and Hoong Chuin Lau
In International Conference on Autonomous Agents and Multiagent Systems, 2013
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 paper, we introduce a new sampling-based DCOP algorithm called Distributed Gibbs, whose memory requirements per agent is linear in the number of agents in the problem. Additionally, we show empirically that our algorithm is able to find solutions that are better than DUCT; and computationally, our algorithm runs faster than DUCT as well as solve some large problems that DUCT failed to solve due to memory limitations.
@inproceedings{conf/aamas/NguyenYL13,author={Nguyen, Duc Thien and Yeoh, William and Lau, Hoong Chuin},title={Distributed Gibbs: A Memory-Bounded Sampling-Based {DCOP} Algorithm},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={167--174},year={2013},}
Distributed problem solving is a subfield within multiagent systems, where agents are assumed to be part of a team and collaborate with each other to reach a common goal. In this article, we illustrate the motivations for distributed problem solving and provide an overview of two distributed problem-solving models, namely distributed constraint-satisfaction problems (DCSPs) and distributed constraint-optimization problems (DCOPs), and some of their algorithms.
@article{journals/aim/YeohY12,author={Yeoh, William and Yokoo, Makoto},title={Distributed Problem Solving},journal={{AI} Magazine},volume={33},number={3},pages={53--65},year={2012},}
IAT
Lagrangian Relaxation for Large-Scale Multi-agent Planning
Geoffrey J. Gordon, Pradeep Varakantham, William Yeoh, and
3 more authors
In International Conferences on Intelligent Agent Technology, 2012
Multi-agent planning is a well-studied problem with various applications including disaster rescue, urban transportation and logistics, both for autonomous agents and for decision support to humans. Due to computational constraints, existing research typically focuses on one of two scenarios: 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 provide provably near-optimal solutions. By contrast, in this paper, we focus on providing provably near-optimal solutions for domains with large numbers of agents, by exploiting a common domain-general property: if individual agents each have limited influence on the overall solution quality, then we can take advantage of randomization and the resulting statistical concentration to show that each agent can safely plan based only on the average behavior of the other agents. 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. We demonstrate the scalability of our approach with a large-scale illustrative theme park crowd management problem.
@inproceedings{conf/iat/GordonVYLAC12,author={Gordon, Geoffrey J. and Varakantham, Pradeep and Yeoh, William and Lau, Hoong Chuin and Aravamudhan, Ajay S. and Cheng, Shih{-}Fen},title={Lagrangian Relaxation for Large-Scale Multi-agent Planning},booktitle={International Conferences on Intelligent Agent Technology},pages={494--501},year={2012},}
UAI
Dynamic Stochastic Orienteering Problems for Risk-Aware Applications
Hoong Chuin Lau, William Yeoh, Pradeep Varakantham, and
2 more authors
In Conference on Uncertainty in Artificial Intelligence, 2012
Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations – travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic SOP (DSOP) model, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature.
@inproceedings{conf/uai/LauYVNC12,author={Lau, Hoong Chuin and Yeoh, William and Varakantham, Pradeep and Nguyen, Duc Thien and Chen, HuaXing},title={Dynamic Stochastic Orienteering Problems for Risk-Aware Applications},booktitle={Conference on Uncertainty in Artificial Intelligence},pages={448--458},year={2012},}
ICAPS
Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search
Xiaoxun Sun, Tansel Uras, Sven Koenig, and
1 more author
In International Conference on Automated Planning and Scheduling, 2012
Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for movingtarget search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.
@inproceedings{conf/icaps/SunYUK12,author={Sun, Xiaoxun and Uras, Tansel and Koenig, Sven and Yeoh, William},title={Incremental {ARA}*: An Incremental Anytime Search Algorithm for Moving-Target Search},booktitle={International Conference on Automated Planning and Scheduling},year={2012},}
AAMAS
Stochastic Dominance in Stochastic DCOPs for Risk-Sensitive Applications
Duc Thien Nguyen, William Yeoh, and Hoong Chuin Lau
In International Conference on Autonomous Agents and Multiagent Systems, 2012
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 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.
@inproceedings{conf/aamas/NguyenYL12,author={Nguyen, Duc Thien and Yeoh, William and Lau, Hoong Chuin},title={Stochastic Dominance in Stochastic DCOPs for Risk-Sensitive Applications},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={257--264},year={2012},}
2011
IJCAI
Generalizing ADOPT and BnB-ADOPT
Patricia Gutierrez, Pedro Meseguer, and William Yeoh
In International Joint Conference on Artificial Intelligence, 2011
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 = infinity and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < infinity. 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.
@inproceedings{conf/ijcai/GutierrezMY11,author={Gutierrez, Patricia and Meseguer, Pedro and Yeoh, William},title={Generalizing {ADOPT} and {BnB-ADOPT}},booktitle={International Joint Conference on Artificial Intelligence},pages={554--559},year={2011},}
2010
JAIR
BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.
@article{journals/jair/YeohFK10,author={Yeoh, William and Felner, Ariel and Koenig, Sven},title={BnB-ADOPT: An Asynchronous Branch-and-Bound {DCOP} Algorithm},journal={Journal of Artificial Intelligence Research},volume={38},pages={85--133},year={2010},}
AAMAS
Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2010
Moving target search is important for robotics applications where unmanned ground vehicles (UGVs) have to follow other friendly or hostile UGVs. Artificial intelligence researchers have recently used incremental search to speed up the computation of a simple strategy for the hunter. The fastest incremental search algorithm, Fringe-Retrieving A*, solves moving target search problems only on two-dimensional grids, which are rather unrealistic models for robotics applications. We therefore generalize it to Generalized Fringe-Retrieving A*, which solves moving target search problems on arbitrary graphs, including the state lattices used for UGV navigation.
@inproceedings{conf/aamas/SunYK10a,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={1081--1088},year={2010},}
AAMAS
Moving Target D* Lite
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2010
Incremental search algorithms, such as Generalized FringeRetrieving A* and D* Lite, reuse search trees from previous searches to speed up the current search and thus often find cost-minimal paths for series of similar search problems faster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving target search problems, where both the start and goal states can change over time. In this paper, we therefore introduce Moving Target D* Lite, an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter to the target in environments whose blockages can change over time. We demonstrate experimentally that Moving Target D* Lite can be three to seven times faster than Generalized Adaptive A*, which so far was believed to be the fastest incremental search algorithm for solving moving target search problems in dynamic environments.
@inproceedings{conf/aamas/SunYK10,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Moving Target D* Lite},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={67--74},year={2010},}
2009
IJCAI
Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms
William Yeoh, Xiaoxun Sun, and Sven Koenig
In International Joint Conference on Artificial Intelligence, 2009
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.
@inproceedings{conf/ijcai/YeohSK09,author={Yeoh, William and Sun, Xiaoxun and Koenig, Sven},title={Trading Off Solution Quality for Faster Computation in {DCOP} Search Algorithms},booktitle={International Joint Conference on Artificial Intelligence},pages={354--360},year={2009},}
IJCAI
Efficient Incremental Search for Moving Target Search
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Joint Conference on Artificial Intelligence, 2009
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.
@inproceedings{conf/ijcai/SunYK09,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Efficient Incremental Search for Moving Target Search},booktitle={International Joint Conference on Artificial Intelligence},pages={615--620},year={2009},}
AAMAS
Caching Schemes for DCOP Search Algorithms
William Yeoh, Pradeep Varakantham, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2009
Nominated for Pragnesh Jay Modi Best Student Paper Award
Distributed Constraint Optimization (DCOP) is useful for solving agent-coordination problems. Any-space DCOP search algorithms require only a small amount of memory but can be sped up by caching information. However, their current caching schemes do not exploit the cached information when deciding which information to preempt from the cache when a new piece of information needs to be cached. Our contributions are three-fold: (1) We frame the problem as an optimization problem. (2) We introduce three new caching schemes (MaxPriority, MaxEffort and MaxUtility) that exploit the cached information in a DCOP-specific way. (3) We evaluate how the resulting speed up depends on the search strategy of the DCOP search algorithm. Our experimental results show that, on all tested DCOP problem classes, our MaxEffort and MaxUtility schemes speed up ADOPT (which uses best-first search) more than the other tested caching schemes, while our MaxPriority scheme speeds up BnB-ADOPT (which uses depth-first branch-andbound search) at least as much as the other tested caching schemes.
@inproceedings{conf/aamas/YeohVK09,author={Yeoh, William and Varakantham, Pradeep and Koenig, Sven},title={Caching Schemes for {DCOP} Search Algorithms},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={609--616},year={2009},}
AAMAS
Dynamic Fringe-Saving A*
Xiaoxun Sun, William Yeoh, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2009
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 FringeSaving 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. Unfortunately, our experimental results show that the resulting Dynamic Fringe-Saving A* algorithm tends to be dominated by either repeated A* searches or D* Lite (a state-of-the-art incremental version of A*).
@inproceedings{conf/aamas/SunYK09,author={Sun, Xiaoxun and Yeoh, William and Koenig, Sven},title={Dynamic Fringe-Saving A*},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={891--898},year={2009},}
AAMAS
Simple Optimization Techniques for A*-based Search
Xiaoxun Sun, William Yeoh, Po-An Chen, and
1 more author
In International Conference on Autonomous Agents and Multiagent Systems, 2009
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.
@inproceedings{conf/aamas/SunYCK09,author={Sun, Xiaoxun and Yeoh, William and Chen, Po{-}An and Koenig, Sven},title={Simple Optimization Techniques for A*-based Search},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={931--936},year={2009},}
2008
AAMAS
BnB-ADOPT: An Asynchronous Branch-and-Bound DCOP Algorithm
William Yeoh, Ariel Felner, and Sven Koenig
In International Conference on Autonomous Agents and Multiagent Systems, 2008
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-and-bound 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.
@inproceedings{conf/aamas/YeohFK08,author={Yeoh, William and Felner, Ariel and Koenig, Sven},title={{BnB-ADOPT}: An Asynchronous Branch-and-Bound {DCOP} Algorithm},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={591--598},year={2008},}
AAMAS
Generalized Adaptive A*
Xiaoxun Sun, Sven Koenig, and William Yeoh
In International Conference on Autonomous Agents and Multiagent Systems, 2008
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 h-values 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.
@inproceedings{conf/aamas/SunKY08,author={Sun, Xiaoxun and Koenig, Sven and Yeoh, William},title={Generalized Adaptive A*},booktitle={International Conference on Autonomous Agents and Multiagent Systems},pages={469--476},year={2008},}
Best Paper Award