Název: Plánování cest pro multi-robotické sklady
Překlad názvu: Path planning for multi-robot warehouses
Autoři: Tauchmanová, Klára ; Barták, Roman (vedoucí práce) ; Švancara, Jiří (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2021
Jazyk: cze
Abstrakt: [cze] [eng]
Práce se zabývá problémem hledání bezkolizních cest v automatizovaném skladu pro skupinu agentů, tzv. Multi-agent pickup and delivery (MAPD) problémem. Agentům ve skladu jsou kontinuálně zadávány nové úkoly, které vyžadují vyzvednout zboží na určeném místě a převézt ho na jiné místo v prostředí skladu. V práci je popsán hierarchický algo- ritmus na řešení MAPD problémů, který provádí plánování na dvou úrovních - globální a lokální. Algoritmus pracuje s prostředím skladu, které je ručně rozděleno na oblasti. Na globální úrovni dochází k zadávání úkolů volným agentům a následně k plánování posloupnosti oblastí, které agent při vykonávání úkolu navštíví. Úkol je zadán vždy nej- bližšímu volnému agentovi. Na lokální úrovni dochází k samotnému hledání bezkolizních cest v rámci jednotlivých oblastí, ke kterému se používají upravené Multi-agent path finding (MAPF) algoritmy. Navržený algoritmus byl otestován v simulovaném prostředí. Experimentálně jsme ukázali, že hierarchický algoritmus používající Conflict-based search (CBS) na lokální úrovni má menší runtime a nachází řešení s menším makespanem než algoritmus využívající redukci na SAT. Dále ukazujeme, že hierarchický přístup k řešení MAPD výrazně snižuje runtime algoritmu, zatímco nalezená řešení nejsou o mnoho horší než u nehierarchického přístupu. 1 Thesis covers the problem of finding non-colliding paths in automated warehouses for a group of agents - so called Multi-agent pickup and delivery (MAPD) problem. Agents in the warehouses are constantly engaged with new tasks which require picking up the object on certain coordinates and transporting it to another place in the warehouse. The- sis describes a hierarchical algorithm for MAPD problems that plans paths in two levels - global and local. The algorithm works with a warehouse environment manually divided into sectors. Planning on the global level consists of assigning tasks to free agents and selecting a sequence of sectors to go through. The task is always assigned to the closest free agent. On the local level, the actual path through the sector is planned using modi- fied Multi-agent path finding (MAPF) algorithms. The proposed algorithm was tested in a simulated environment. We showed that the hierarchical algorithm with Conflict-based search (CBS) on the local level has a smaller runtime and finds a solution with a lower makespan than the algorithm using reduction to SAT. Further, we showed that the hierar- chical approach for MAPD significantly lowers the runtime of the algorithm, meanwhile, the outputted solutions are not much worse than for non-hierarchical approaches. 1
Klíčová slova: Multi-agent pickup and delivery|Dvojúrovňové plánování|Multi-agentní hledání cest|Automatizované sklady; : Multi-agent pickup and delivery|Two-level planning|Multi-agent path finding|Automated warehouses

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/148276

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-451666


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce