Delay-tolerant Multi-Agent Path Finding: Delay-tolerant methods for solving multi-agent path finding problems in autonomous systems

Visa enkel post
dc.contributor.authorGYLLENSKEPP, JOAKIM
dc.contributor.authorNORDENHÖG, KEVIN
dc.contributor.departmentChalmers tekniska högskola / Institutionen för data och informationstekniksv
dc.contributor.examinerLjunglöf, Peter
dc.contributor.supervisorSchiller, Elad Michael
dc.date.accessioned2019-10-08T10:05:42Z
dc.date.available2019-10-08T10:05:42Z
dc.date.issued2019sv
dc.date.submitted2019
dc.description.abstractMulti-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.sv
dc.identifier.coursecodeDATX05sv
dc.identifier.urihttps://hdl.handle.net/20.500.12380/300417
dc.language.isoengsv
dc.setspec.uppsokTechnology
dc.subjectComputer sciencesv
dc.subjectmulti-agent path findingsv
dc.subjectpath findingsv
dc.subjectsimulationsv
dc.subjectconflict-based searchsv
dc.subjectautonomous systemssv
dc.titleDelay-tolerant Multi-Agent Path Finding: Delay-tolerant methods for solving multi-agent path finding problems in autonomous systemssv
dc.type.degreeExamensarbete för masterexamensv
dc.type.uppsokH
Ladda ner
Original bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
CSE 19-81 Gyllenskepp Nordenhög.pdf
Storlek:
1.88 MB
Format:
Adobe Portable Document Format
Beskrivning:
Delay-tolerant Multi-Agent Path Finding: Delay-tolerant methods for solving multi-agent path finding problems in autonomous systems
Ladda ner
License bundle
Visar 1 - 1 av 1
Bild (thumbnail)
Namn:
license.txt
Storlek:
1.14 KB
Format:
Item-specific license agreed upon to submission
Beskrivning:
Ladda ner
Samling
Examensarbeten för masterexamen