# Shadoks Approach for Lifelong MAPF

Aldo Gonzalez-Lorenzo, Guilherme D. da Fonseca
Aix-Marseille University (France), LIS

## Our Team

Associate professors at Aix-Marseille University (France)

Previous experience in optimization challenges CG:SHOP 2019—2024

### Methodology

• Make many different algorithms for different scenarios
• Ignore state-of-the-art (!)
• Understand the instances: map, number of agents, number of steps
• Test our algorithms locally on similar instances
• Submit to the server to check hypotheses

We want to find the best algorithm with the best parameters for each instance.

### Results

Instance Algorithm Result (best)
I-01PlannerLazy10385 (10385)
I-02PlannerLazy49181 (49186)
I-03PlannerLong3042 (3042)
I-04PlannerLong1741 (1741)
I-05PlannerLazy7293 (7432)
I-06PlannerLazy197275 (197275)
I-07PlannerComb5809 (5914)
I-08PlannerSAT6059 (6059)
I-09PlannerGame19943 (28954)
I-10PlannerLazy194677 (194677)
Map Agents Algorithm Result (best)
Random100PlannerLong1741 (1741)
Random200PlannerLong3042 (3042)
Random400PlannerLazy7293 (7432)
Random600PlannerComb5809 (5914)
Random800PlannerSAT6059 (6059)
City1500PlannerLazy10385 (10385)
City3000PlannerLazy49181 (49186)
Sortation10 000PlannerLazy197275 (197275)
Warehouse10 000PlannerLazy194677 (194677)
Game6500PlannerGame19943 (28954)

## PlannerLazy

### Problem Statement

• Large map, long paths in average
• Narrow corridors, risk of congestion
• Difficult to find a full path for all agents (like 15 puzzle)

### Approach

• Find a path of bounded length for all agents
• Update these paths as often as possible

We want to plan the near future to make the best moves.

Formally, we compute a path for each agent such that:

1. There are no collisions between the paths
2. Their lengths are bounded by a parameter $$\lambda \in \mathbb{Z}$$
3. A path can be empty

def initialize():
"""Initialize queue and paths"""
queue = [i for i in range(20)]
paths = [[] for _ in range(20)]

def plan(λ):
"""Compute the actions for each agent"""
while time() < 0.9:
a = queue.pop()
paths[a] = find_path(a, λ) # specialized A* search
queue.append(a)
return set_actions(paths, queues) # avoid collisions


### A* search

Function find_path(a, λ) uses A* search to find a collision-free path for agent a. We stop searching if:

• We find a path of length $$\lambda$$
• There are no nodes to explore

Moreover, we precompute distances between all pairs of locations and use them for the heuristic function $$h()$$.

For each pair of pixels (start, end), it is enough to save the directions (East or West, North or South) that get closer to the end with 2 bits.

### Avoid Collisions

Since paths have different length, there can be collisions

Function set_actions(paths, queues) detects colliding agents, clears their paths and moves them to the front of the queue.

### Congestion

To avoid congestion, we combine two tools:

• Add weights to the nodes in A* search
• Set moving directions

#### Avoiding Congestion: Weights

Objective: avoid many agents passing by the same location.

At each timestep, count the agents passing by each location using the current computed paths. This defines a weight for each location.

In the A* search algorithm, include the weights to the cost function $$g()$$.

#### Avoiding Congestion: Directions

Objective: allow only one direction between adjacent locations.

Set alternating directions between rows and columns. Then fix directions by hand until the map is strongly connected.

Use this map only for precomputing the distances. Agents can still move in any direction.

## Conclusion

The competition

• Thanks to organizers
• Fast Mover category is trivial
• Invitate winners to a good conference/journal
• Prevent participants from hiding good results
• Hide only the list of tasks

The science

• Prove the correctness of the algorithms: customized A* search, PlannerLazy...
• Understand impact of parameters and options of our algorithms
• Identify best suited algorithm for any instance
• Better design of moving directions using previous solutions
##### Take-home message

We are open to collaborations, both industrial and academic

Thanks for listening. Questions?