Večagentno iskanje poti z algoritmom CCBS

Sedej, Matic (author), Klančar, Gregor (mentor)

Magistrsko delo obravnava problem večagentnega iskanja poti za skupino transportnih vozil, kjer je okolje predstavljeno z zemljevidom cest in nato pretvorjeno v graf prehajanja stanj. Iskanja v grafu izvedemo po zgledu sodobnih, v literaturi nedavno objavljenih, algoritmov iskanja v grafu na osnovi reševanja konfliktov, kot sta CCBS in CBS. Poleg svoje izvedbe algoritma predlagamo tudi nadgradnjo za učinkovitejše zaznavanje in reševanje konfliktov. Algoritem CCBS (ang. Continuous Conflic Based Search) je dvonivojski algoritem in temelji na iskanju konfliktov med agenti, pri čemer upošteva njihovo geometrijsko obliko. Algoritem CCBS deluje v zveznem časovnem prostoru in zato omogoča optimalnejšo rešitev, kot na primer CBS (ang. Conflic Based Search), ki deluje v diskretnem prostoru. CCBS na spodnjem nivoju uporablja algoritem SIPP (ang. Safe Interval Path Plannnig), ki je nadgradnja algoritma A* na način, da med iskanjem optimalne poti upošteva tudi varne intervale vozlišč ter povezav. Na zgornjem nivoju pa se izvaja iskanje najboljšega vozlišča v drevesu omejitev. Vozlišča v drevesu omejitev se ustvarijo z vsakim novo odkritim konfliktom med agenti. Učinkovitost in hitrost algoritma CCBS sta odvisni tudi od zaznavanja konfliktov. V ta namen smo predstavili dve različni obliki zaznavanja konfliktov, ki delujeta skupaj. Prva deluje na osnovi prilagodljivega vzorčenja poti agentov in zazna vse vrste konfliktov, tudi tiste, ki se zgodijo v različnih vozliščih in povezavah, vendar je zaradi vzorčenja računsko zahtevna. Druga deluje na osnovi preverjanja zasedenosti intervalov vozlišč in povezav agentov ter je računsko veliko manj zahtevna, vendar zazna le konflikte v istih vozliščih in povezavah. Algoritem CCBS je, tako kot podobni optimalni algoritmi, zaradi računske zahtevnosti v praktičnih primerih omejen na manjše število agentov in preprostejše oziroma manjše grafe prehajanja stanj. Njihova računska zahtevnost se namreč veča eksponentno z večanjem števila agentov.

• Language: Slovenian
• Keywords: načrtovanje poti, večagentno iskanje poti, varni intervali, zaznavanje konfliktov, algoritem CBS, algoritem SIPP, algoritem CCBS
• Work type: Master's thesis/paper
• Organization: FE - Faculty of Electrical Engineering
• Year: 2023
• PID: 20.500.12556/RUL-153106
• COBISS.SI-ID: 180790019
• Publication date in RUL: 18.12.2023

Secondary language

• Language: English
• Title: Multiagent pathfinding with the CCBS algorithm

Abstract

The master's thesis deals with the problem of multi-agent path finding for a group of transport vehicles, where the environment is presented with a road map and then converted into a state transition graph. The graph is searched using the graph search algorithms recently published in the literature, which are conflict resolution based, e.g., CCBS and CBS. In addition to executing the algorithm we also suggest an upgrade for a more efficient conflict detection and resolution. The CCBS (Continuous Conflict-Based Search) algorithm is a two-level algorithm that searches for conflicts between agents, while taking their geometric shape into account. The CCBS algorithm works in a continuous time framework and therefore provides a more optimal solution than, e.g., CBS (Conflict-Based Search), which works in a discrete time framework. The CCBS uses the SIPP (Safe Interval Path Planning) algorithm on the low level, which is an upgrade of the A* algorithm, as it also considers the safe node and connection intervals while searching for the optimal path. On the high level it searches for the best node in the constraints tree. Nodes are created in the constraints tree with each new conflict discovered between agents. The efficiency and speed of the CCBS algorithm also depend on conflict detection. For this purpose, we have presented two different types of conflict detection that work together. The first type uses adaptive sampling of the agents' path and detects all kinds of conflicts, including those that occur in different nodes and connections; however, the sampling makes it computationally demanding. The second type checks the occupancy intervals of the agents' nodes and connections and is computationally much less demanding, but only detects conflicts in the same nodes and connections. Due to being computationally demanding, the practical use of the CCBS algorithm is restricted to a smaller number of agents and to simpler or smaller state transition graphs, just as similar optimal algorithms. Namely, its computational complexity increases exponentially with increasing numbers of agents.

• Keywords: path planning, multi-agent path finding, safe intervals, conflict detection, CBS algorithm, SIPP algorithm, CCBS algorithm