Shadoks Approach for Lifelong MAPF

Our Team

Shadoks

• Aldo Gonzalez-Lorenzo
  Topics: computational topology, geometrical optimization
• Guilherme D. da Fonseca
  Topics: computational geometry, geometrical optimization

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

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
• Follow these paths
• 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 reach the task
• 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?