multi-agent planning

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.

sponsors

CAREER: Decentralized Constraint-based Optimization for Multi-Agent Planning and Coordination.
National Science Foundation (2016 – 2021).


selected publications

  1. DX
    Diagnosing Multi-Agent STRIPS Plans
    Avraham Natan, Roni Stern, Meir Kalech, and 2 more authors
    In International Conference on Principles of Diagnosis and Resilient Systems, 2024
    :trophy: Best Paper Award
  1. 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
  2. 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
      1. 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
      1. 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
      1. 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
      2. 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
      1. 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
      1. 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
            1. 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