The world according to MARP

Abstract

In multi-agent route planning (MARP), there is a set of agents each with a start location and a destination location on a shared infrastructure, and the goal of each agent is to reach its destination in the shortest possible time, without coming into conflict (e.g. because of a collision) with any of the other agents. The MARP problem is relevant in automated guided vehicle systems, with application domains in flexible manufacturing systems or at container terminals like Rotterdam or Singapore. Another application domain for MARP is airport taxi routing, where aircraft must taxi between runway and gate, while avoiding close proximity with other aircraft. In the literature, a number of approaches to MARP exist. The first is to have one planner make a plan for all agents. Because of its complete overview, the centralized planner can in principle find an optimal set of agent route plans. Unfortunately, finding an optimal set of plans is intractable (as we show in this thesis), and in practice optimal plans can only be found if there are not more than a handful of agents. A second approach, and the one we take in this thesis, is to let the agents plan one by one, each agent planning around the plans of the previous agents (in the sense that no conflict is introduced with any existing plans). In this prioritized approach (the agents plan in the order of their priority), it is possible to find an individually optimal route plan in reasonable time, although there is no guarantee that the combination of agent plans is also optimal. A third approach to MARP is to do very little planning (for example by choosing a fixed path between start and destination), and instead to check at every next step in the plan-execution phase whether it is safe to move forward, or whether a conflict will ensue. In this approach there are no guarantees for either local or global optimality, but it can be a convenient approach in dynamic environments, where unexpected changes can invalidate carefully crafted plans. If however there are no plans, then nothing can be disrupted, and any situation can be treated the same way. By contrast, the first two (planning) approaches to MARP require additional plan repair techniques to deal with unexpected incidents. We present a model for MARP in which the infrastructure is modeled as a graph of resources (like roads and intersections); each resource has a capacity, which is the maximum number of agents that may occupy the resource at the same time. A route plan is a sequence of resources each with an occupation time interval, and the objective in MARP is to find a set of agent route plans such that the capacities of the resources are never exceeded. In our model, we also identify a number of additional constraints that have to be satisfied depending on the application domain. For example, we formulate constraints to forbid overtaking, constraints that forbid cyclic plans, and constraints that require a minimum separation between agents of at least one empty resource. Even if no additional constraints need to be satisfied, finding an optimal solution to the MARP problem is intractable. Our route planning algorithms make use of free time windows on resources. A free time window is an interval during which an agent can make use of a resource without causing a conflict with any of the existing route plans. We search for a route plan by constructing a graph of the free time windows, and performing an adapted shortest-path search through this graph, which results in an optimal (shortest-time), conflict-free route plan for a single agent. Our contribution lies in the speed of our algorithm, which is much faster than previous optimal single-agent route planning algorithms. In addition, we also present a route planning algorithm that can find a conflict-free route plan along a sequence of locations (rather than from a start location to a single destination location), which is the first algorithm in its kind, as far as we know. Planning approaches to MARP require additional mechanisms to deal with unexpected incidents during plan execution. In this thesis, we consider vehicle incidents that temporarily immobilize an agent (which can be caused by e.g. a human that steps into the path of an agent). If, after the slowdown, all agents including the delayed agent ignore the disruption, then a deadlock situation can arise. In the literature there exists a mechanism that can prevent deadlocks, and thus ensure that each agent can reach its destination safely, albeit with a possible delay. This mechanism is based on the resource priority that agents inherit after the planning process: from the set of agent plans, we can infer the order in which agents visit a resource (and the first agent to visit a resource has the highest resource priority). The deadlock prevention mechanism is simply to respect these resource priorities during plan execution, which means that agents sometimes have to wait for a delayed agent with a higher priority. In some cases, there is no need to wait for a delayed agent, and the resource priority can be changed during plan execution without creating a deadlock situation. In the literature, one such priority-changing algorithm exists, but the conditions under which it allows a priority change are very strict, which limits the applicability of the algorithm. We developed a new priority-changing algorithm that allows changes in more situations, which therefore has the potential to achieve a bigger reduction in agent delay. Our algorithm makes use of a graph structure that can predict exactly which priority changes are safe, and which will lead to a deadlock. In our experiments we evaluated the robustness of agent route plans, i.e., the property of plans to remain efficient, in terms of minimizing delay, even if unexpected incidents necessitate minor plan revisions. Above, we described three schedule repair algorithms: either fully respect the resource priorities during plan execution, or allow some priority changes using the existing priority-changing algorithm, or using our new algorithm. Respecting resource priorities can be seen as a baseline approach to incident handling: if it results in short delays, then no priority changes are necessary; if it would result in long delays, then we can seek to reduce this delay by changing some priorities at run-time. In taxi route planning experiments on a model of Schiphol airport, the baseline method produced satisfactory results: in case there are only a few short incidents, then there is hardly any delay; in case there are many incidents of a long duration, then the average delay was still rarely more than 20% of the length of the agent plans. Experiments on other types of infrastructures (such as grid-like networks and small-world networks) also showed that delay is low for a small number of short incidents, but for a large number of long incidents, delays of around 100% were frequently reached. One reason why the results are so favourable for the airport experiments is that the locations of the start and destination points of the agents were not fully randomized, as aircraft agents travel between runways and gates. Hence, if aircraft agents use the same resource, then they are most likely heading in the same direction. Our experiments suggest that the most delay from incidents arises when agents that have to wait for each other travel in opposite directions. We also managed to reduce delay by changing priorities, and our algorithm, which produces the greatest number of priority changes, also managed the greatest reduction in delay. A different set of experiments evaluated the cost of the multi-agent plan (which can be measured by e.g. recording the finish time of the latest agent) that results from sequential single-agent planning, for arbitrary agent priorities. Under the assumption that the optimal set of agent priorities will result in a close-to-optimal global plan, then measuring the difference between the best and the worst observed set of priorities gives an indication of the worst-case global plan cost that can be obtained using prioritized planning. In our experiments, we tried 100 different sets of agent priorities for a single problem instance, and for each type of infrastructure, we tried numerous instances. The best results were again obtained for the airport infrastructure, and again the locations of the start and destination points seem to be the main reason: because all agents travel in more or less the same direction, they manage to organize themselves into flows, regardless of which agent is allowed to plan first. For other types of infrastructures, it proved to be important to have multiple routes between any two locations. Otherwise, if e.g. one road connects two parts of the infrastructure, then this road can become a bottleneck if agents on either side of the road need to cross; arbitrarily assigned priorities can then lead to a situation where the travel direction of the resource alternates with every other agent, which is much less efficient than many agents using the resource at the same time in the same direction. To conclude, we presented a prioritized approach to the multi-agent route planning problem. MARP has many important application domains like airport taxi routing and route planning for automated guided vehicles, and our new algorithm is fast enough to be applied to problem instances of realistic size. To deal with unexpected incidents, we have focussed on schedule repair methods, but in future work we can investigate how plan repair techniques (i.e., also allowing agents to choose a different route) can further reduce delay. Another direction of future research is how we can reduce the cost of the global plan. Our route planning algorithms are optimal for a single agent, and the combination of individually optimal route plans sometimes leads to high-quality global plans --- for example in the taxi route planning experiments, where the location of the start and destination points of the agents ensured that they travel in the same directions and therefore interfere little with each other. On other infrastructures, an arbitrary priority assignment can sometimes lead to a poor global plan. To improve global plan cost, one possibility is to find a better set of agent priorities. Another option is to investigate whether agents can coordinate before or during planning, such that an agent also takes into account the benefit of other agents during planning.