Goal Legibility and Recognition for Anonymous Multi-Agent Pathfinding Systems: A Graph Theoretical Approach

Goal legibility, one of the dimensions of agent interpretability, has gained significant attention in human-machine interaction research. This thesis explores goal legibility in relation to goal recognition in a multi-agent setting with an observer-in-the-loop. Specifically, it considers an environment where identical agents move from an origin to designated destinations, and an observer monitors their movements, aiming to infer their destinations as quickly as possible. Our approach generates legible paths that minimize overlap while satisfying budget constraints. We also developed a goal recognition framework that maps observation sequences to specific destinations, enabling the observer to infer an agent's goal with minimal (legibility) delay. The legible path planning problem is reformulated as a classical network flow problem for fully observable scenarios, using combinatorial optimization tools to create scalable algorithms. The method adapts efficiently to partially observable settings as well.

While effective, these techniques can become computationally demanding. To address this, we introduced initial goal legibility, where the observer begins monitoring agents from their entry point. This variant focuses on inferring destinations by observing initial trajectories. Through mathematical reformulations, our approach computes paths that minimize trajectory overlap, and agents then follow optimal routes. This method is applicable to both fully and partially observable environments. Empirical evaluations demonstrate the scalability and efficiency of our techniques, confirming their practical relevance.