Decentralized control of free ranging automated guided vehicles in industrial environments
U ovom doktorskom radu opisan je decentralizirani algoritam upravljanja viserobotskim sustavima s automatski vodenim vozilima (engl. Automated Guided Vehicles - AGV) kojima se ostvaruje automatizirani prijevoz razlicitih tereta u robotiziranim proizvodnim postrojenjima, distribucijskim centrima i sk...
| Permalink: | http://skupni.nsk.hr/Record/fer.KOHA-OAI-FER:47508/Details |
|---|---|
| Glavni autor: | Draganjac, Ivica (-) |
| Ostali autori: | Kovačić, Zdenko (Thesis advisor) |
| Vrsta građe: | Knjiga |
| Jezik: | hrv eng |
| Impresum: |
Zagreb :
I. Draganjac, Fakultet elektrotehnike i računarstva,
2018.
|
| LEADER | 16509nam a22001937a 4500 | ||
|---|---|---|---|
| 005 | 20180308162811.0 | ||
| 008 | 180308s2018 ci ||||| |||| 00| 0 hrv d | ||
| 040 | |a HR-ZaFER |b hrv |c HR-ZaFER |e ppiak | ||
| 041 | |a eng | ||
| 100 | |9 39026 |a Draganjac, Ivica | ||
| 245 | |a Decentralized control of free ranging automated guided vehicles in industrial environments : |b doctoral thesis / |c Ivica Draganjac ; mentor Zdenko Kovačić | ||
| 260 | |a Zagreb : |b I. Draganjac, Fakultet elektrotehnike i računarstva, |c 2018. | ||
| 300 | |a xi, 140 str. : |b ilustr. u bojama ; |c 30 cm + |e CD | ||
| 504 | |a Bibliografija str. 119-130. | ||
| 520 | |a U ovom doktorskom radu opisan je decentralizirani algoritam upravljanja viserobotskim sustavima s automatski vodenim vozilima (engl. Automated Guided Vehicles - AGV) kojima se ostvaruje automatizirani prijevoz razlicitih tereta u robotiziranim proizvodnim postrojenjima, distribucijskim centrima i skladisnim prostorima. Predlozeni algoritam upravljanja razvijen je s ciljem ostvarivanja autonomije vozila pri izvrsavanju dodijeljenih transportnih zadataka te eliminacije razlicitih ogranicenja koja prate postojece sustave s AGV vozilima u praksi. Naime, unatoc dugogodisnjoj prisutnosti sustava s AGV vozilima u proizvodnim i logistickim procesima, metode upravljanja vozilima tradicionalno se zasnivaju na centraliziranoj arhitekturi upravljanja sa sredisnjom upravljackom jedinicom koja planira i koordinira gibanja svih vozila u sustavu po unaprijed projektiranoj mrezi putanja. Takvom nacinu upravljanja svojstveni su sljedeci nedostaci: ogranicena skalabilnost sustava pri povecanju broja vozila zbog eksponencijalne slozenosti centraliziranih algoritama upravljanja; ovisnost cjelovitog sustava o ispravnosti i dostupnosti sredisnje upravljacke jedinice; potreba zasebnog projektiranja mreze putanja u tlocrtu radnog prostora sto moze rezultirati suboptimalnim putanjama; te niska eksibilnost sustava u pogledu dinamickog dodjeljivanja transportnih zadataka i promjena u radnom okruzenju. Decentralizirani algoritam upravljanja, razvijen u sklopu doktorskoga rada, izvodi se na svakom vozilu u sustavu te se sastoji od modula za planiranje putanja i modula za koordinaciju gibanja. Modul za planiranje putanja omogucuje samostalno planiranje vlastitih putanja vozila, dok modul za koordinaciju gibanja omogucuje pouzdanu detekciju i razrjesavanje kon iktnih situacija s drugim vozilima u zajednickom radnom prostoru. Planiranje putanja provodi se odredivanjem optimalnih putanja izmedu pocetne i konacne lokacije u prostoru slobodnom od prepreka, uzimajuci u obzir neholonomska ogranicenja vozila. Za tu svrhu koristi se dvo-razinski koncept planiranja koji se zasniva na topoloskom prikazu karte prostora pomocu deniranih sektora te prikazu slobodnog prostora pomocu tzv. latice stanja. Vrste sektora ukljucuju otvorena podrucja odnosno terminale, podrucja za preuzimanje i dostavu tereta, podrucja za parkiranje i punjenje vozila te podrucja unutar uskih hodnika. Sukladno tome, proces odredivanja putanja od pocetnog polozaja vozila do konacnog polozaja zadanog trenutacnom misijom provodi se u dva koraka. U prvom koraku odreduje se topoloska ruta koja povezuje pocetni i konacni sektor vozila, koristenjem usmjerenog topoloskog grafa prostora ciji cvorovi predstavljaju sektore, a bridovi dozvoljene prijelaze izmedu susjednih sektora. Nakon odredivanja topoloske rute, u drugom koraku odreduje se najkraca izvediva putanja koja prolazi sektorima duz izracunate rute. Svojstva izvedivosti i optimalnosti putanja zagarantirana su prikazom navigacijskog prostora vozila pomocu latice stanja koja se sastoji od medusobno povezanih, unaprijed konstruiranih, osnovnih segmenata gibanja. Izvedivost osnovnih segmenta gibanja u latici zagarantirana je postupkom njihove konstrukcije. Odredivanje cjelovite putanje stoga ukljucuje odredivanje najkrace sekvence medusobno povezanih osnovnih segmenata gibanja izmedu pocetnog i konacnog polozaja vozila u diskretiziranom prostoru latice stanja. Slicno kao i u slucaju odredivanja topoloske rute, proces odredivanja optimalnih putanja na latici stanja svodi se na proces pretrazivanja pripadajuceg grafa ciji cvorovi predstavljaju diskretna stanja u radnom prostoru, a bridovi osnovne segmente gibanja koji svako diskretno stanje povezuju s ogranicenim skupom susjednih stanja. Nakon odredivanja optimalne izvedive putanje do zadanog konacnog polozaja u radnom prostoru, vozilo zapocinje s izvodenjem zadane misije gibajuci se duz izracunate putanje sukladno instrukcijama modula za koordinaciju gibanja. Temeljna zadaca modula za koordinaciju gibanja je osigurati gibanje vozila bez mogucnosti sudara s drugim vozilima u zajednickom radnom prostoru te takoder sprijeciti mogucnost pojave zaglavljenja i ciklickih sekvenci gibanja. Ispunjenje ove zadace zasniva se na pouzdanoj detekciji i razrjesavanju kon ikata s drugim vozilima na temelju medusobne komunikacije vozila unutar lokalnog komunikacijskog radijusa te izvodenja razvijenog protokola za razrjesavanje kon ikata. Rezultat izvodenja ovog protokola je skup medusobno koordiniranih akcija svih vozila u kon iktu kojima se osigurava nastavak gibanja uz izbjegavanje sudara. Razrjesavanje kon ikata zasniva se na uvazavanju prioriteta misija te strategiji zaustavljanja odnosno privremenog pomicanja vozila nizih prioriteta s putanja vozila visih prioriteta. Slobodan prostor za sigurno pomicanje vozila u kon iktnim situacijama, bez mogucnosti sudara s drugim vozilima, zagarantiran je gibanjem vozila unutar uvedenih privatnih zona na latici stanja, oblikovanih prema dimenzijama i kinematickim ogranicenjima vozila. Izvodeci projektirani upravljacki algoritam, vozila dinamicki alociraju privatne zone oko diskretnih stanja na vlastitim putanjama te rjesavaju individualne kon ikte s vozilima visih prioriteta koristeci iskljucivo prostor unutar vlastitih privatnih zona. S obzirom na njihov oblik i velicinu, strategija koordinacije koristenjem privatnih zona primjenjuje se iskljucivo u terminalima, dok se u preostalim vrstama sektora primjenjuje neposredna alokacija i koristenje prostornih resursa na putanjama vozila. Kako bi se unatoc nepostojanju sredisnje upravljacke jedinice i globalnog znanja u sustavu osigurao medusobno iskljucivi pristup prostornim resursima, alokacija resursa provodi se pomocu algoritma za distribuiranu alokaciju resursa. Izvodenjem ovog algoritma u sklopu modula za koordinaciju gibanja, vozila samostalno alociraju potrebne prostorne resurse na vlastitim putanja na temelju medusobne komunikacije i razmjene potrebnih informacija. viii U doktorskom radu naveden je i formalni dokaz stabilnosti razvijenog decentraliziranog algoritma upravljanja koji potvrduje svojstvo upravljanja vozilima bez mogucnosti pojave zaglavljenja i ciklickih sekvenci gibanja. Nadalje, algoritam upravljanja implementiran je na ROS (engl. Robot Operating System) platformi, a njegova ispravnost i performanse provjerene su u razlicitim scenarijima u simulacijskom okruzenju s najvise pedeset vozila te eksperimentalno na sustavu sa sest laboratorijskih robota tipa Pioneer 3DX. Algoritam je takoder preliminarno provjeren na industrijskom sustavu s dva automatski vodena vozila u realnim industrijskim uvjetima. Rezultati provjere algoritma potvrduju ispravnost njegove implementacije te uspjesnu eliminaciju ogranicenja svojstvenih postojecim centraliziranim sustavima upravljanja. Poboljsane karakteristike upravljanja postignute su ostvarivanjem autonomije vozila pri izvrsavanju dodijeljenih transportnih zadataka te linearne racunske slozenosti decentraliziranog algoritma upravljanja u ovisnosti o broju vozila u sustavu, cime je osigurano svojstvo visoke skalabilnosti prilikom dodavanja novih vozila u sustav. Pored visoke skalabilnosti, algoritam takoder osigurava eliminaciju jedinstvene tocke kvara koja pogada cijeli sustav, povecanu eksibilnost na promjene u radnom okruzenju, povecanu eksibilnost na dinamicko dodjeljivanje transportnih zadataka te odredeni stupanj robustnosti u pogledu kvarova na pojedinim vozilima. Performanse razvijenog algoritma usporedene su s performansama drugih algoritama upravljanja na temelju podataka dostupnih u literaturi. Rezultati usporedbe potvrduju da su performanse projektiranog algoritma, u smislu broja izvrsenih transportnih zadataka u jedinici vremena, na razini modernih centraliziranih sustava upravljanja. No medutim, uzimajuci u obzir svojstvo visoke skalabilnosti koje omogucuje dodavanje proizvoljnog broja vozila u sustav te eliminaciju ostalih ranije navedenih ogranicenja svojstvenih za centralizirane sustave, moze se zakljuciti da razvijeni algoritam unaprjeduje razlicite upravljacke aspekte postojecih sustava upravljanja AGV vozilima u industrijskim okruzenjima. Izvorni znanstveni doprinosi doktorskoga rada su: 1. Model navigacijskog prostora automatski vodenih vozila koristenjem prostorne latice stanja i njoj pridruzenih privatnih zona vozila, formiranih prema dimenzijama i kinematickim ogranicenjima vozila, sa svojstvom garantirane mogucnosti izbjegavanja sudara unutar zona. 2. Decentralizirani algoritam za koordinaciju automatski vodenih vozila sa slobodnim odabirom putanja koji uvazava prioritete misija i razrjesava kon iktne situacije medu vozilima. 3. Dokaz stabilnosti decentraliziranog algoritma upravljanja te eksperimentalna potvrda algoritma u simulacijskom, laboratorijskom i industrijskom okruzenju. ix Doktorska disertacija organizirana je kako slijedi. U poglavlju 1 dan je kratki uvod u problematiku upravljanja sustavima s automatski vodenim vozilima. Navedeni su osnovni ciljevi i preduvjeti upravljanja, analizirane su prednosti i mane centralizirane i decentralizirane arhitekture upravljanja, opisani su razliciti pristupi planiranju putanja te razlicite metode navigacije vozila. Takoder su opisana razlicita pravila za dodjeljivanje transportnih zadataka te strategije izbjegavanja zaglavljenja u sustavima. U drugom dijelu ovog poglavlja naveden je pregled relevantne literature iz podrucja upravljanja AGV sustavima, nakon cega su identicirane mane postojecih sustava upravljanja te opisani motivi i ciljevi ovoga doktorskoga rada. Poglavlje 2 sadrzi formulaciju problema upravljanja vozilima koji se razmatra u ovom radu, daje pretpostavke na kojima se zasniva njegovo rjesavanje te opisuje zeljenu upravlja cku strukturu sustava. U ovom poglavlju takoder se uvodi topoloski prikaz radnog prostora pomocu sektora te opisuje dvo-razinski pristup planiranju putanja. Modul za planiranje putanja koji omogucuje dvo-razinsko planiranje optimalnih putanja vozila u radnom okruzenju prikazanom pomocu sektora i latice stanja detaljno je opisan u poglavlju 3. Tri osnovna dijela ovog poglavlja ukljucuju opise neholonomskih ogranicenja vozila, postupka konstrukcije latice stanja te odredivanja optimalnih izvedivih putanja. U poglavlju 4 detaljno je opisan modul za koordinaciju gibanja koji uvazava prioritete misija te detektira i razrjesava razlicite kon iktne situacije medu vozilima. U ovom poglavlju uvodi se mehanizam privatnih zona te opisuje strategija koordinacije vozila zajedno s pripadajucim protokolom za razrjesavanje kon ikata. Poglavlje takoder opisuje algoritam za distribuiranu alokaciju prostornih resursa, analizira minimalni potrebni komunikacijski radijus vozila, navodi analizu kompleksnosti cjelovitog upravljackog algoritma te opisuje mehanizam oporavka od komunikacijskih kvarova na pojedinom vozilu, kao i mehanizam za detekciju i razrjesavanje kruznih cekanja u sustavu. Analiza stabilnosti razvijenog upravljackog algoritma s dokazom njegove otpornosti na pojavu zaglavljenja i ciklickih sekvenci gibanja navedena je u poglavlju 5. Poglavlje 6 opisuje programsku arhitekturu i nacin implementacije algoritma na ROS platformi te funkcionalnosti i nacin interakcije pojedinih programskih modula. Ovo poglavlje takoder opisuje simulacijsko i eksperimentalno okruzenje koristeno u postupku provjere performansi cjelovitog algoritma upravljanja. Poglavlje 7 posveceno je analizi i vrednovanju rezultata provjere algoritma u simulacijskom okruzenju s najvise pedeset virtualnih vozila, u laboratorijskim uvjetima koristenjem sest robota tipa Pioneer 3DX te industrijskom okruzenju koristenjem dva industrijska AGV vozila tipa Skilled 1000 i Skilled 1400. Zakljucni osvrt na provedeno istrazivanje i postignute rezultate, kao i na moguce smjerove daljnjeg istrazivanja, naveden je u poglavlju 8. x Kljucne rijeci: automatski vodena vozila, decentralizirano upravljanje, viserobotski sustavi, planiranje putanja, koordinacija gibanja, upravljanje prometom, razrjesavanje kon ikata, projektiranje i analiza algoritama, distribuirana alokacija resursa, automatizirani prijevoz tereta, automatizirani skladisni sustavi. | ||
| 520 | |a Systems with automated guided vehicles (AGVs) play an essential role in material handling processes within various manufacturing facilities, automatic warehouses and distribution centers. However, despite their long presence on the factory oor and signicant advances they experienced over the last decades, the current industrial state of the art still relies on a centralized controller, which dispatches transport missions to vehicles along a predetermined network of paths. While this approach makes it easier to ensure correct system operation, it suers from several drawbacks: the paths have to be laid out in advance, which is time-consuming and can be suboptimal; centralized planning does not scale well as the number of vehicles increases; and it introduces a single point of failure into the system. In order to eliminate the drawbacks of the centralized control architecture, this PhD thesis introduces a decentralized trac management algorithm that ensures high scalability and exibility of AGV systems by providing vehicles with full autonomy in the mission execution process. By executing on each vehicle in the system, the proposed control algorithm allows vehicles to autonomously plan their own paths to complete assigned missions and negotiate with other vehicles in the local area for right of way in order to avoid collisions and deadlocks. The algorithm relies on a two-layer control approach with topological representation of the working environment on the top layer and statelattice representation on the bottom layer. The path planning part of the algorithm implements a free-ranging motion scheme by determining the shortest feasible paths through dierent working space sectors, considering non-holonomic vehicle constraints. The motion coordination part of the algorithm ensures safe vehicle motions by reliable detection and resolution of dierent con ict situations with other vehicles in the shared workspace. Con ict resolution is based on a vehicle priority scheme and results in temporary stopping or removal of the lower priority vehicles taking part in the con ict. Removal actions are always performed within the vehicle's private zone, i.e. the dynamically allocated local region of the workspace surrounding the vehicle. By encoding information on the vehicle size and its kinematic constraints, the introduced private-zone mechanism provides the necessary physical space required for successful execution of every removal action. Algorithm correctness, and especially its deadlock-free and livelock-free properties, has been formally analyzed and proved, while its performance has been validated in simulation with up to fty virtual vehicles, and also experimentally on two dierent setups - a laboratory setup comprising six Pioneer 3DX vehicles and by two state-of-the-art autonomous forklifts in industrial-like operating conditions. Validation results conrm correct system operation and successful implementation of several advancements over the current state of the art, primarily in terms of high system scalability, increased exibility to changing requirements, and high tolerance to fault conditions. v Keywords: automated guided vehicles, decentralized control, multi-robot systems, algorithm design and analysis, path planning, motion coordination, trac management, con ict resolution, distributed resource allocation, material handling systems, automated warehousing. | ||
| 700 | |4 ths |9 9622 |a Kovačić, Zdenko | ||
| 942 | |2 udc |c D | ||
| 999 | |c 47508 |d 47508 | ||