A Network Flow Interpretation of Robust Goal Legibility in Path Finding

Authors

  • Sara Bernardini Royal Holloway University of London
  • Fabio Fagnani Politecnico di Torino
  • Santiago Franco Royal Holloway University of London
  • Alexandra Neacsu Royal Holloway University of London

Keywords:

Interpretable Agent Behaviour, Legibility, Path Finding, Network Flows

Abstract

In this paper, we define goal legibility in a multi-agent path-finding setting. We consider a set of identical agents moving in an environment and tasked with reaching a set of locations that need to be serviced. An observer monitors their movements from a distance to identify their destinations as soon as possible. Our algorithm constructs a set of paths for the agents, one to each destination, that overlap as little as possible while satisfying a budget constraint. In this way, the observer, knowing the possible agents' destinations as well as the set of paths they might follow, is guaranteed to determine with certainty an agent's destination by looking at the shortest possible fragment of the agent's trajectory, regardless of when it starts observing. Our technique is robust because the observer's inference mechanism requires no coordination with the agents' motions. By reformulating legible path planning into a classical minimum cost flow problem, we can leverage powerful tools from combinatorial optimization, obtaining fast and scalable algorithms. We present experiments that show the benefits offered by our approach.

Downloads

Published

2022-06-13

How to Cite

Bernardini, S., Fagnani, F., Franco, S., & Neacsu, A. (2022). A Network Flow Interpretation of Robust Goal Legibility in Path Finding. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 668-677. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/19856