Supervisor

Suitable for

Abstract

Prerequisites: Artificial Intelligence, programming

 

Background

Multi-Agent Path Finding (MAPF) is a core optimisation problem in multi-agent systems: given many agents sharing a space, compute time-coordinated, collision-free paths from their start locations to their assigned goals. Contemporary applications are many and include automated warehouses, UAV/drone flight scheduling and urban air-traffic management, autonomous-vehicle and robotaxi fleets, port and airport ground-vehicle coordination, factory and semiconductor-fab AGVs/AMHS, sidewalk delivery robots, hospital logistics robots, and crowd/character routing in games and simulation. All of these applications involve large agent populations and complex environments, making the MAPF problem challenging. Computing optimal MAPF plans is NP-hard, so practical deployments typically use bounded-suboptimal or anytime methods that trade exact optimality for speed while preserving high solution quality.

Most MAPF planners are centralised, i.e. one coordinator computes and dispatches all agents’ paths, which simplifies global reasoning but creates serious practical limits. First, scalability is poor: planning and re-planning latency and memory blow up with agent count and map size. Second, the architecture is brittle: a single point of failure and communication bottlenecks make performance degrade under packet loss or overload. Third, centralised schedules are hard to execute robustly in the real world: small timing errors, sensor noise, and model mismatch (e.g., grid abstractions that ignore robot kinematics and dynamics) quickly invalidate tightly coordinated plans. Finally, responsiveness is limited: disturbances such as delays, blockages, or new tasks often require expensive global re-planning, and heterogeneity in agent sizes and speeds further exacerbates these issues.

Focus

This project aims to develop a principled, decentralised framework for MAPF based on game theory. In particular, the idea is to formulate MAPF as a noncooperative game and draw on congestion game theory, mechanism and incentive design, and evolutionary dynamics to derive distributed algorithms with provable performance guarantees, explicitly characterising efficiency/complexity tradeoffs.

Noncooperative game theory naturally models systems of strategic, self-interested agents with potentially conflicting objectives, as in the applications above. This viewpoint allows us to use game-theoretic tools to optimise, or at least improve, system outcomes and welfare. In particular, mechanism design studies how to synthesise policies that enable a planner to efficiently allocate scarce resources to agents while ensuring that they are individually rational and strategy-proof. These desirable properties guarantee that each agent always benefits from participating in the mechanism and, at the same time, that agents are incentivised to report their private information truthfully to the mechanism. Additional classes of policies that can be designed to stir agents’ selfish behaviour towards socially desirable outcomes include dynamic congestion pricing, whereby the planner decides how much to charge the agents for using the available resources, as well as information design, which entails the planner choosing what information to disclose to the agents to best nudge them towards the desirable goal. 

Method

Goals:

• Game-theoretic modelling of MAPF problems
• Design of game-based mechanisms and policies with formal performance guarantees
• Development of efficient algorithms to solve MAPF leveraging the game-theoretic formulation
• Implementation for representative real-world problems

 

Related papers:

Friedrich, P., Zhang, Y., Curry, M., Dierks, L., McAleer, S., Li, J., Sandholm, T. and Seuken, S., Scalable Mechanism Design for Multi-Agent Path Finding. https://arxiv.org/pdf/2401.17044