Associate professors at Aix-Marseille University (France)
Previous experience in optimization challenges CG:SHOP 2019—2024
We want to find the best algorithm with the best parameters for each instance.
Instance | Algorithm | Result (best) |
---|---|---|
I-01 | PlannerLazy | 10385 (10385) |
I-02 | PlannerLazy | 49181 (49186) |
I-03 | PlannerLong | 3042 (3042) |
I-04 | PlannerLong | 1741 (1741) |
I-05 | PlannerLazy | 7293 (7432) |
I-06 | PlannerLazy | 197275 (197275) |
I-07 | PlannerComb | 5809 (5914) |
I-08 | PlannerSAT | 6059 (6059) |
I-09 | PlannerGame | 19943 (28954) |
I-10 | PlannerLazy | 194677 (194677) |
Map | Agents | Algorithm | Result (best) |
---|---|---|---|
Random | 100 | PlannerLong | 1741 (1741) |
Random | 200 | PlannerLong | 3042 (3042) |
Random | 400 | PlannerLazy | 7293 (7432) |
Random | 600 | PlannerComb | 5809 (5914) |
Random | 800 | PlannerSAT | 6059 (6059) |
City | 1500 | PlannerLazy | 10385 (10385) |
City | 3000 | PlannerLazy | 49181 (49186) |
Sortation | 10 000 | PlannerLazy | 197275 (197275) |
Warehouse | 10 000 | PlannerLazy | 194677 (194677) |
Game | 6500 | PlannerGame | 19943 (28954) |
We want to plan the near future to make the best moves.
Formally, we compute a path for each agent such that:
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
Function find_path(a, λ)
uses A* search to find a collision-free path for agent a
. We stop searching if:
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.
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.
To avoid congestion, we combine two tools:
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() \).
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.
The competition
The science
We are open to collaborations, both industrial and academic
Thanks for listening. Questions?