Multi-agent planning – the ability of a group of autonomous agents to reason about their actions and identifying sequences of actions (i.e., plans) that lead them to their goals – is a core area of AI research at the intersection of automated planning and multi-agent systems. Applications of multi-agent planning are abound, ranging from robots navigating in autonomous warehouses today to autonomous vehicles navigating on roads in the future.
Within this space, we are primarily investigating issues of fairness in multi-agent planning problems, especially on applications that involve humans as agents. For example, in ridesharing problems, as both the income of drivers and wait times of passengers are affected by how passenger requests are matched with available drivers, we seek to find approaches that find matches with fair and equitable outcomes.
Additionally, in collaboration with other researchers, we have also proposed several algorithms for multi-agent pathfinding (MAPF). MAPF approaches have been growing in popularity and form the basis of routing algorithms for robots in autonomous warehouses. Within this space, we are also interested in identifying algorithms that can find diagnoses for when the agents fail during execution.
The increasing use of multi-agent systems demands that many challenges be addressed. One such challenge is diagnosing failed multi-agent plan executions, sometimes in system setups where the different agents are not willing to disclose their private actions. One formalism for generating multi-agent plans is the well-known MA-STRIPS formalism. While there have been approaches for delivering as robust plans as possible, we focus on the plan execution stage. Specifically, we address the problem of diagnosing plans that failed their execution. We propose a Model-Based Diagnosis approach to solve this problem. Given an MA-STRIPS problem, a plan that solves it, and an observation that indicates execution failure, we define the MA-STRIPS diagnosis problem. We compile that problem into a boolean satisfiability problem (SAT) and then use an off-the-shelf SAT solver to obtain candidate diagnoses. We further expand this approach to address privacy by proposing a distributed algorithm that can find these same diagnoses in a decentralized manner. Additionally, we propose an enhancement to the distributed algorithm that uses information generated during the diagnosis process to provide significant speedups. We found that the improved algorithm runs more than 10 times faster than the basic decentralized version and, in one case, runs faster
than the centralized algorithm.
@inproceedings{conf/dx/NatanSK0S24,author={Natan, Avraham and Stern, Roni and Kalech, Meir and Yeoh, William and Son, Tran Cao},title={Diagnosing Multi-Agent STRIPS Plans},booktitle={International Conference on Principles of Diagnosis and Resilient Systems},pages={to appear},year={2024},}
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},pages={227--235},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},}
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},}
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},}
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},}
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},}
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},}
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},}
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},}