Delay-tolerant Multi-Agent Path Finding: Delay-tolerant methods for solving multi-agent path finding problems in autonomous systems
Typ
Examensarbete för masterexamen
Program
Publicerad
2019
Författare
GYLLENSKEPP, JOAKIM
NORDENHÖG, KEVIN
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Multi-agent path finding algorithms find collision-free paths that agents should follow
according to a schedule. The schedules found by multi-agent path finding algorithms
are strict, meaning that when a robot in an autonomous system is delayed
and fall behind schedule, the schedule is invalidated and the movement of all agents
are paused until a new schedule is found. Computing these schedules is inherently
slow due to the hardness of multi-agent path finding problems. There are methods,
such as MAPF-POST, which find the delay tolerance of a given schedule and, in
some cases, allow agents to be delayed without doing expensive replanning.
We propose a modification to the multi-agent path finding algorithm Conflict-based
search, which makes the schedule found by the algorithm tolerant to delays. The
delay tolerance that the schedule should have can be selected by the user. Our results
show that the delay tolerant conflict-based search can successfully reduce the
number of recalculations in a system with delays, at the cost of a higher run-time.
We also propose a method called refined component stalling, which avoids recalculations
by purposefully delaying a subset of the agents in order to retain a valid
schedule. Our experiments show that this method successfully reduces the number
of agents affected by delays and the need for recalculations, at the cost of giving the
agents longer paths.
Our contributions reduces the time spent on recalculations significantly, which means
that the time it takes for the agents to follow a schedule may be faster compared to
existing multi-agent path finding algorithms, which sometimes spends a lot of time
on recalculations. This is especially clear when agents move fast, since the longer
path length of our contributions are less noticeable.
Beskrivning
Ämne/nyckelord
Computer science , multi-agent path finding , path finding , simulation , conflict-based search , autonomous systems