A Network Flow Interpretation of Robust Goal Legibility in Path Finding

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationProceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022)
Pages668-677
Number of pages10
Volume32
Edition1
Publication statusPublished - 13 Jun 2022

Cite this