Multi-agent path planning by anticipating the behavior of other agents using prediction trees

Multi-Agent Pickup and Delivery for a home team (MAPD-h) is the problem of computing collision-free paths for a team of agents called home team, which has to reach delivery locations by first passing through pickup ones. The home team is completing its pickup and delivery tasks in its own environment, when another team of agents, called guest team, operates into the environment completing its own tasks. The home team has to compute its paths being careful about not colliding with the guest team, without communicating or interfering with it. In MAPD-h, the home team can exploit the fact of operating in its own environment to know the locations and the tasks assigned to the guest team to use this knowledge to improve its planning. To tackle this problem, we propose two reactive algorithms and two proactive algorithms. These algorithms are all based on trying to predict the possible shortest paths that the guest team might be using and in exploiting this information when planning. The home team computes its paths by considering and avoiding the possible locations that guests could be occupying in a certain timestep. Home agents use for planning a version of Token Passing that periodically computes partial paths, in order to interleave planning with execution. An extensive experimental campaign demonstrates the strengths and weaknesses of these approaches.

Il problema di Multi-Agent Pickup and Delivery for a home team (MAPD-h) consiste nel pianificare percorsi senza collisioni per un gruppo di agenti chiamato home team, il quale deve raggiungere delle postazioni di consegna passando prima per delle postazioni di prelievo. Mentre l’home team sta completando i suoi compiti di prelievo e consegna nel suo ambiente, un altro gruppo di agenti, chiamato guest team, opera nell’ambiente per eseguire i propri compiti. L’home team deve costruire i suoi percorsi stando attento a non scontrarsi con gli agenti del guest team, senza comunicare o interferire con essi. In MAPD-h, l’home team può sfruttare il fatto di stare operando nel suo ambiente per conoscere le posizioni e i compiti assegnati al guest team e sfruttare questa conoscenza per migliorare la sua pianificazione. Per affrontare questo problema, proponiamo due algoritmi reattivi e due algoritmi proattivi. Questi algoritmi sono tutti basati sul tentare di predire i possibili percorsi più brevi che il guest team potrebbe usare e sullo sfruttare tali informazioni nella pianificazione. L’home team pianifica i suoi percorsi considerando ed evitando le possibili posizioni che gli agenti guest potrebbero occupare in uno specifico istante di tempo. Gli agenti home usano per la pianificazione una versione di Token Passing che pianifica periodicamente dei percorsi parziali, in modo da intervallare la pianificazione con l’esecuzione. Un’estesa campagna sperimentale dimostra i punti di forza e di debolezza di questi approcci.