In a Multi-Agent Pickup and Delivery (MAPD) problem, a group of agents has to accomplish subsequent pickup and delivery tasks while avoiding collisions. Tasks are provided at runtime, making MAPD a combination of Multi-Agent Path Finding (MAPF) and online task assignment. In this paper, we consider a new formulation of MAPD, in which a team of agents has to solve a MAPD problem without interfering or communicating with other agents not belonging to the team that are operating in the same environment. We address the problem from the point of view of the team of agents, and we propose that they build a model of the behavior of the agents external to the team and exploit this information in planning their paths. We consider diferent levels of knowledge that the team of agents can have about the other agents, and propose diferent solutions accordingly. Experimental results show that the inclusion of information about the behavior of external agents in the team's planning phase reduces the number of potential collisions and decreases tasks' completion time for the team.
The MAPD problem [
Since we conservatively assume that the team of agents cannot communicate with external agents and does not know their plans, collisions between a team agent and an external agent may happen. Every time there is a potential collision, the team agent has to reactively avoid the collision and replan its path. Frequent replans can slow down the completion of tasks, implying that team agents will need more time to solve their MAPD problem. To overcome this issue, we propose that agents in the team model the behavior of the external agents and use this information to plan better paths that attempt to avoid collisions.
To model the behavior of the external agents, we consider diferent levels of knowledge that can be available to the team, which trigger diferent solutions. The levels of knowledge considered are: (1) the team of agents knows the current positions of the external agents in real-time and the tasks they are assigned to; (2) the team of agents knows a set of paths followed by the external agents in the past; (3) the team of agents knows anything about external agents.
Our work is related to the problem of multi-agent moving obstacles’ avoidance [
The MAPD problem [
A task set contains all the tasks that have not been assigned and, due to the dynamic nature of the problem, new tasks can be added at any time. Each task ∈ is composed of a pickup location ∈ and a delivery location ∈ . Each agent can have a single task assigned at a time, and a task can be assigned to only one agent. To solve an assigned task, an agent has to plan and perform a sequence of actions = (1, . . . , ) that brings it from its current location to the pickup location and then to the delivery location of the task. Agents’ paths must not collide, that is: two diferent agents cannot be in the same location at the same time (vertex conflict ) and they cannot traverse the same edge in opposite directions at the same time (swapping conflict ). The aim of a MAPD problem is to plan paths that complete all the tasks in the shortest time.
Token Passing (TP) [
Given an environment represented as a graph = (, ), we define the MAPD problem in a dynamic environment from the perspective of a team = {1, ..., } of agents that has to perform a MAPD problem while in the same environment there are other external moving agents ℋ = {ℎ1, ..., ℎ}. Agents ℋ are not necessarily coordinated in performing their tasks.
We assume the team and the other agents are neither collaborative nor adversarial. We also make a no-interference assumption, namely, we assume external agents’ decisions to move to be immutable, irrespective of the presence of the team agents, and hence the team agents are in charge of implementing proactive and/or reactive behaviors to avoid collisions. To allow the team agents to implement reactive behaviors for collision avoidance, we assume that each team agent ∈ can detect external agents within a field of view () = {︀ ∈ | ∃ = (loc(), . . . , ) with | | ≤ 2︀} , which covers all locations of the environment that are reachable from the current location loc() of with paths of length 2 or less. We assume that the team agents know the location and the next move of external agents within their FOVs.
We now suppose the team of agents knows the current positions of external agents, the locations each one of them must reach, and the fact that external agents are coordinated and rational (i.e., they move along the shortest conflict-free paths). The idea is to simulate all possible paths external agents may take to complete their tasks so the team can avoid future potential conflicts.
We store all the possible shortest paths that external agents can follow to complete their tasks in a
Path Prediction Tree (PPT). Although we assume external agents plan their paths in a coordinated
way, we do not make any assumption on the algorithm they use to coordinate themselves or to
plan their paths, nor we make assumptions about whether hierarchies or priorities exist among
them (e.g., team agents know that external agents address a MAPD problem but do not know
the algorithms they employ). As a consequence, when we simulate external agents’ paths in the
PPT, we need to consider all possible priority orders that external agents could have followed
to make their conflict-free plans. This means that, when simulating the future behavior of each
external agent, we have to consider higher-priority agents’ paths as obstacles. Once all the
combinations of possible shortest paths for each possible priority order are found, the PPT is
complete. The tree is not immutable: at the end of each timestep, after all team and external
agents have executed their actions, all the predicted paths in the PPT are checked to see if they
are still valid given the new locations of external agents and are otherwise pruned. Moreover,
when an external agent completes a task and is assigned a new one, the PPT needs to be updated
accordingly. The PPT can be created and updated by any agent of the team and is stored in the
token so that all team agents can access it. As, especially in grid environments, the computation
of all possible combinations of shortest paths is prone to combinatorial explosion and becomes
computationally infeasible even for medium-sized environments, we also develop a windowed
version of the approach based on bounded-horizon planning [
We validate our approach on two types of grid environments: warehouses with narrow corridors and more open environments inspired by city layouts, with 3 external agents and 2 team agents. The metrics used for evaluation are the number of potential conflicts generated (i.e., team agents’ replans) and the service time, i.e., the average number of time steps needed to finish executing a task after it has been added to the task set . Although the non-windowed version allows to avoid potential conflicts completely, it is computationally unfeasible for environments bigger than 80 × 80 cells. When adopting the windowed version, a trade-of needs to be made between the computing time and number of potential conflicts admissible. For example, with a window size = 6 we observe an average decrease of around 50% in the number of potential conflicts without hurting the service time w.r.t. ignoring the presence of other agents.
This section deals with the case in which the team of agents knows a set of paths performed by the external agents in the past. The idea is to build a model of the external agents using past observations of their movements.
The first approach [
In the second approach, the focus is to estimate the position of each external agent maintaining a belief , that is a probability distribution over all possible vertices ∈ expressing the likelihood for agent to occupy a given vertex at time . The beliefs {} can then be aggregated into a probability () of occupancy for vertex (at time ) via the complement rule. To propagate the belief through time, the movement of an external agent is modeled with a n-th order Markov chain, where the states correspond to the vertices ∈ . We can interpret a belief as the probability distribution over the states of the Markov chain at time , and therefore we can obtain the corresponding belief state after time steps as + = , where is the transition matrix of the Markov chain learned from the set of paths performed by the external agents in the past using maximum likelihood estimation. This allows the model to make predictions on the future positions of the agents when it comes to planning, and to update the belief state in light of the observations collected via field of view at each time step. The idea of a weighted graph is maintained, however, the weight attributed to an edge is not 1 stationary anymore: ( ) = (1 − ) () + (, , ). Since the belief state of an agent is propagated over time, it now depends on the future time step at which the transition takes place. Term (, , ) combines the probability of a vertex conflict and of a swapping conflict.
Two types of grid environments are used for testing, both presenting the features of a warehouse with narrow corridors, using an observation window of 600 time steps, 4 external agents, and 3 team agents. Best results are obtained for = 0.2: a significant reduction of potential conflicts (i.e., team agents’ replans) w.r.t. a purely reactive approach is observed both for TP-CA-M (reduction of 37%) and, especially, Markovian models (79% for the second order). The service time is similar to the purely reactive approach, with a reduction of 2.5% for TP-CA-M and 4% for the second-order Markovian model, meaning that planning for paths with a lower number of potential conflicts results in a small reduction in the speed of completion of the tasks.
It can happen that team agents do not have information regarding the past behavior of external agents. For this reason, we discuss the case in which team agents have to build the behavioral model of the external agents relying solely on the information they observe when external agents enter their field of view. The models presented in Section 5 are preserved, with the diference that in the probabilistic matrix and the transition matrix of the first and second approach, respectively, the probability is initially uniformly distributed and is updated according to the observations made at runtime. In terms of computing efort, learning other agents’ behaviors in real-time when using the probability occupation matrix or a first-order Markov chain just requires the update of a matrix, which is feasible to perform online at runtime. For higher-order Markov chains, it could become computationally unfeasible to do it online.
The results collected under this scenario, without any initial window of observation, show that the performance of a trained probabilistic/Markovian model and an untrained one, that simply hypothesizes a uniform distribution for the probabilistic/transition matrix, are not that diferent. This highlights the dificulty of our models in learning a distinctive behavior for the external agents: a possible reason may involve the pattern of motion itself, which may be close to a random movement for an agent.
In this paper, we proposed and formalized a new MAPD variant in which a team of agents has to carry out its MAPD tasks in an environment with other external moving agents. Three diferent solving approaches have been proposed according to three possible levels of knowledge that team agents have of external agents. Interesting directions of future work include (i) the management of deadlocks, e.g., those conflicts that cannot be solved without violating the no-interference assumption; and (ii) a more in-depth investigation of the real-time approach. Benedetta Flammini is financially supported by the ABB – Politecnico di Milano Joint Research Center. This paper is supported by PNRR-PE-AI FAIR project funded by the NextGeneration EU program.