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
Citation
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Byggår
Modelltyp
Skala
Teknik / material